报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！
第一章 概论 测验
1、【单选题】下列不属于线性结构的是：Which one of the followings does not belong to linear structure:（There is only one correct answer）
A、队列(queue)
B、散列表(hash table)
C、向量(vector)
D、图(graph)
2、【单选题】以下哪种结构是逻辑结构，而与存储和运算无关：Which of the following structure is a logical structure regardless of the storage or algorithm:（There is only one correct answer）
A、队列(queue)
B、双链表(doubly linked list)
C、数组(array)
D、顺序表(Sequential list)
3、【多选题】关于算法特性描述正确的有：Which one is right about algorithm’s characterization:（there are more than one correct answers）
A、算法保证计算结果的正确性。Algorithm will ensure the correctness of the calculation results.
B、组成算法的指令可以有限也可能无限。 Instructions which composite algorithms can be infinite or finite
C、算法描述中下一步执行的步骤不确定。 The next step in the implementation of the algorithm described is uncertain.
D、算法的有穷性指算法必须在有限步骤内结束。The finite nature of algorithms means algorithm must be completed within a limited step.
4、【多选题】下列说法正确的是：Which options may be correct?（there are more than one correct answers）
A、如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)是O(h(n))【 if f(n) is O(g(n))，g(n) is O(h(n))，then f(n) is O(h(n))】
B、如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)+g(n)是O(h(n))【if f(n) is O(g(n))，g(n) is O(h(n))，so f(n)+g(n) is O(h(n))】
C、如果a>b>1,<img src="http://img0.ph.126.net/VcgcoWIoh1hdXef557SAHg==/2607865659244339497.png" />是<img src="http://img2.ph.126.net/lYugWi8d7HjEDoJHIjrArw==/6597919689146936204.png" />，但<img src="http://img0.ph.126.net/vH-gb2PlQ1YHHJwAeEFCTQ==/1860549596157802668.png" />不一定是<img src="http://img1.ph.126.net/XQTa6fKcwp4eNZLMkj9JuQ==/6631686790749152974.png" />【if a>b>1,<img src="http://img0.ph.126.net/VcgcoWIoh1hdXef557SAHg==/2607865659244339497.png" /> is <img src="http://img2.ph.126.net/lYugWi8d7HjEDoJHIjrArw==/6597919689146936204.png" />， <img src="http://img0.ph.126.net/vH-gb2PlQ1YHHJwAeEFCTQ==/1860549596157802668.png" /> may not be <img src="http://img1.ph.126.net/XQTa6fKcwp4eNZLMkj9JuQ==/6631686790749152974.png" />】
D、函数f(n)是O(g(n))，当常数a足够大时，一定有函数g(n)是O(af(n))【if f(n)是O(g(n))，When constant a is big enough ，there must be g(n) is O(af(n))】
#如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)+g(n)是O(h(n))【if f(n) is O(g(n))，g(n) is O(h(n))，so f(n)+g(n) is O(h(n))】】
5、【多选题】已知一个数组a的长度为n，求问下面这段代码的时间复杂度: An array of a, its length is known as n. Please answer the time complexity of the following code.（There are more than one answers.）for (i=0,length=1;in-1;i++){ for (j = i+1;jn a[j-1]=a[j];j++) if(lengthj-i+1) length=j-i+1;}
A、<img src="http://img0.ph.126.net/DakUVgPB3SQIjucePny05w==/1821987524348412030.png" />
B、<img src="http://img2.ph.126.net/NOeIlef1tbfEWxHG0jY9jg==/6608269392097732547.png" />
C、<img src="http://img1.ph.126.net/2BKp4_g7LgdbsLswUsBsxQ==/1876875144807026971.png" />
D、<img src="http://img0.ph.126.net/14UjVmsVX7VP63LVcxeLIA==/2164824045982605549.png" />
6、【填空题】计算运行下列程序段后m的值：Calculate the value of m after running the following program segmentn = 9; m = 0; for (i=1;i=n;i++) for (j = 2*i; j=n; j++) m=m+1;求m的值
A、
7、【填空题】由大到小写出以下时间复杂度的序列： 答案直接写标号，如：(1)(2)(3)(4)(5) （提示：系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Write the following time complexity in descending sequence:Write down the answer labels such as (1)(2)(3)(4)(5). （Hint：This problem is judged by string matching, Please make sure your answer don't contain any blanks. ）<img src="http://edu-image.nosdn.127.net/F9C17984CEB68E4982E44269264FC8D1.png?imageView&thumbnail=890x0&quality=100" />
A、
第二章 线性表测验
1、【多选题】下面关于线性表的叙述中，正确的是哪些？Which of the followings about linear list are correct?（There are more than one answers.）Select the answer that matches
A、线性表采用顺序存储，必须占用一片连续的存储单元。Linear lists use sequential storage which must occupy a continuous memory units.
B、线性表采用顺序存储，便于进行插入和删除操作。Linear lists using sequential storage, it is easy to do insert and delete operations.
C、线性表采用链接存储，不必占用一片连续的存储单元。Linear lists using the linked storage, do not occupy a continuous memory units.
D、线性表采用链接存储，便于插入和删除操作。Linear lists using the linked storage, it is easy for insert and deleting operations.
2、【多选题】下面的叙述中正确的是：Select the answer that matches （There are more than one correct answers）
A、线性表在链式存储时，查找第i个元素的时间与i的数值无关。When the linear list stored in linked form, the time to find the i-th element is regardless of the value of i.
B、线性表在顺序存储时，查找第i个元素的时间与i的数值成正比。When the linear list stored sequentially, the time to find the i-th element is proportional to value with i.
C、线性表在顺序存储时，查找第i个元素的时间与i的数值无关。When the linear list stored sequentially, the time to find the i-th element is regardless of the value of i.
D、线性表在链式存储时，插入第i个元素的时间与i的数值成正比。When linear lists stored in the linked form, the time to insert the i-th element is proportional to value with i.
3、【多选题】完成在双循环链表结点p之后插入s的操作为：The operation to insert s after the doubly circular linked list’s node p is: (There are more than one answers.)
A、p->next->prev=s; s->prev=p; s->next=p->next; p->next=s;
B、p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C、s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D、s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
4、【填空题】对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(___),在给定值为x的结点后插入一个新结点的时间复杂度为O(___)。（请依次填入,格式为(a)(b),如果您的答案中出现字母，请使用小写;后一空系统基于字符匹配来判定答案，所以您的答案中不要出现空格）For a single linked list with n nodes, and after a known node *p to insert a new node, the time complexity is O (___); after a given node with x value insert a new node, the time complexity is O (___). (If your answer contains letters, use lowercase one.The second blank is judged by string matching, Please make sure your answer don't contain any blanks. )
A、
5、【填空题】设某循环链表长度为n，并设其中一节点为p1，然后按照链表的顺序将后面的节点依次命名为p2,p3,...,pn，那么请问pn.next=____(答案为一个节点名，注意所有字母为小写且答案中不包含空格)
A、
第三章 栈与队列测验
1、【单选题】设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是_____________。Assume that the stack S and queue Q’s initial state is empty, the elements e1, e2, e3, e4, e5 and e6 followed through stack S, an element out the stack means into the queue Q. If the sequence the six elements out of the queue is e2, e4, e3, e6, e5, e1 then stack S of capacity should be at least _____________. （There is only one correct answer）
A、2
B、3
C、4
D、6
2、【单选题】现有中缀表达式E=((100-4)/3+3*(36-7))*2。以下哪个是与E等价的后缀表达式？Existing infix expression E = ((100-4) / 3 + 3 * (36-7)) * 2. Which of the following is the equivalent postfix expression of E? （There is only one correct answer）
A、( ( 100 4 – ) 3 / 3 ( 36 7 – ) * + ) 2 *
B、* + / – 100 4 3 * 3 – 36 7 2
C、100 4 – 3 / 3 36 7 – * + 2 *
D、* ( + / ( – 100 4 ) 3 * 3 ( – 36 7 ) ) 2
3、【多选题】队列的特点包括：Queue’ features include:（There are more than one answers.）
A、后进先出Last-in first-out (LIFO)
B、先进后出First-in last-out (FILO)
C、先进先出First-in first-out (FIFO)
D、后进后出 Last-in last-out (LILO)
4、【多选题】以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有:In the following realizing ways of circular queue, the queue whose length is n can also contain the number of n elements is:（There are more than one answers.）
A、只用front和rear两个指针标记队列的头和尾，两个指针均为实指Only use front and rear as the queue’s head and tail pointers and the two pointers are actually referring to.
B、用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数With the queue’s head and tail pointers marked as front and rear, use the integer variable len to record the number of elements.
C、用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空With the queue’s head and tail pointers marked as front and rear, use Boolean variable empty record whether the queue is empty.
D、只用front和rear两个指针标记队列的头和尾，两个指针均为虚指Only use front and rear as the queue’s head and tail pointers and the two pointers are virtually referring to.
5、【填空题】编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台；则开出车站的顺序有______种可能。 注释：例如 1, 2, 3, 4 或 4, 3, 2，1 就是其中两种可能出站序列；而 4, 3, 1, 2 是 非法序列。Numbered 1,2,3,4 four trains, orderly entered a stack structure station. How many possible leaving sequences of that four trains ? ______ . Note: For instance, the leaving sequence could be 1,2,3,4 or 4,3,2,1 these two possibilities, but 4, 3, 1, 2 is not a possible sequence.
A、
6、【填空题】双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列，那么可以得到_____种不同的排列。double-ended queue can insert and delete operations on both ends of the queue. That it can insert / delete at its tail, but also at the head. Existing 4 different elements sequentially input to the double-ended queue, you can get _____ different permutations.
A、
第四章 字符串测验
1、【单选题】设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为( )（单选）There are two strings p q, q is p’s substring. The algorithm to search the first time q appeared in p is called ( )（There is only one correct answer）
A、求子串 Seeking substring
B、联接 Concatenation
C、匹配 Matching
D、求串长 Seeking length
2、【单选题】下列说法正确的是：（单选） Which of the following statements is correct? （There is only one correct answer）
A、空串就是空白串“Empty string” is blank string.
B、空串是任意字符串的子串 Empty string is a substring of arbitrary string.
C、串只可以采用顺序存储，不可以采用链式存储 String only can be stored in sequential method and cannot be stored in linked method.
D、在C++标准中，char S[M]最多能表示长度为M的字符串 In C ++ standards, char S[M] can represent up to a string of length M.
3、【单选题】若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))注意：substr(S,i,j)是对字符串S的下标为i开始取j个字符，这里的下标是从0开始的(单选)If the string S1 = 'ABCDEFG', S2 = '9898', S3 = '###', S4 = '012345', execute concat (replace (S1, substr (S1, length (S2), length (S3)), S3), substr (S4, index (S2, '8'), length (S2))) Note substr (S, i, j) is the operation to take string S’s j characters from subscript i. Subscript here is starting from 0.（There is only one correct answer）
A、ABC
B、
C、
D、G0123
E、ABCD
F、
G、
H、2345
I、ABCD
J、
K、
L、1234
M、ABC
N、
O、
P、G2345
4、【单选题】下面关于串的的叙述中，哪一个是不正确的:（单选） Which of the following descriptions about string is not correct? （There is only one correct answer）
A、串是字符的有限序列 String is a finite sequence of characters.
B、模式匹配是串的一种重要运算 Pattern matching is an important operation.
C、串是一种数据对象和操作都特殊的线性表 String is a linear list whose data objects and operations both special
D、空串是由空格构成的串 Empty string is a string consisting of spaces.
5、【单选题】Seek the string BAAABBBAA ‘s feature vector, where the feature vector is defined as follows:（There is only one correct answer）<img style="border-bottom-color: rgb(163, 163, 163); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(163, 163, 163); border-left-style: none; border-left-width: 0px; border-right-color: rgb(163, 163, 163); border-right-style: none; border-right-width: 0px; border-top-color: rgb(163, 163, 163); border-top-style: none; border-top-width: 0px; margin-top: 10px; max-width: 830px;" src="http://www.chinesemooc.org/attachment/homework/pic/20151021/2365/38203181445421312.png" />
A、{-1, 0, 0, 0, 0, 0, 0, 1, 2}
B、{-1, 0, 0, 0, 0, 1, 1, 1, 2}
C、{-1, 0, 0, 0, 0, 0, 1, 1, 2}
D、{-1, 0, 0, 0, 1, 1, 1, 1, 2}
6、【多选题】在字符{A, C, G, T}组成的DNA序列中，A和T、C和G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串）。下面DNA序列中存在互补回文串的是：（多选）In the DNA sequences consisting of character {A, C, G, T}, A and T, C and G are complementary pairs. Judging whether there is a complementary palindrome sequence in a DNA sequence (e.g., ATCATGAT’s complement strings is TAGTACTA, it is complementary palindrome sequence with the original sequence). Which of the following DNA sequences have complementary palindrome string? （There are more than one answers.）
A、CTGATCAG
B、AATTAATT
C、TGCAACGT
D、CATGGTAC
E、GTACGTAC
F、AGCTAGCT
7、【填空题】若字符串s=“software”，则其子串个数为： If the string s = software, then the number of its sub-string is:
A、
8、【填空题】若字符串s=”algorithm”，则其子串个数为： If the string s = algorithm, then the number of its sub-string is:
A、
9、【填空题】设有字符串变量String A ＝“”，B＝“MULE”，C＝“OLD”，D＝“MY” ; 请计算下列表达式 （3个答案本身不要出现空格，答案之间用空格分开） Assume that there is a string variable String A = , B = MULE, C = OLD, D = MY; Please calculate the following expression: (1) D+C+B(2) B.substr(3，2) (3) A.strlength()
A、
10、【填空题】一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：A text string can be encrypted by the given letters mapping table. For example, the letters mapping table is:<img src="http://edu-image.nosdn.127.net/7F736D39A07493A031C32019B0EA2338.png?imageViewencrypt被加密为tkzwsdf。则字符串 “algorithm”，被加密为________________（Hint： 1. 答案不需要加引号 2. 系统基于字符匹配来判定答案，所以您的答案中不要出现空格）。As the string encrypt is encrypted as tkzwsdf, then the algorithm is encrypted as ________ (Hint：1. please don’t include any quotes in your answer 2. This problem is judged by string matching, Please make sure your answer don't contain any blanks.).
A、
11、【填空题】S=“S1S2…Sn”是一个长为n的字符串，存放在一个数组中，编程序将S改造之后输出。S = S1S2 ... Sn is a string of length n, and stored in an array, output S after its programmable transformation.
1.将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分； 1.All the even-numbered characters of S should be placed in accordance with their subscript descending order in the second half of S;2.将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；2.All the odd-numbered characters of S should be placed in accordance with their subscript ascending order in the first half of S.例如：S=‘ABCDEFGHIJKL’，则改造后的S为‘ACEGIKLJHFDB’。则 S=’algorithm’, 改造后为____________（Hint： 1. 答案不需要加引号 2. 系统基于字符匹配来判定答案，所以您的答案中不要出现空格）。For example: S = 'ABCDEFGHIJKL', then after the transformation S is 'ACEGIKLJHFDB'. If S = 'algorithm', then after the transformation S is ____________ (Hint:1. please don’t include any quotes in your answer. 2.This problem is judged by string matching, Please make sure your answer don't contain any blanks ).
A、
12、【填空题】下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(abba)返回1，f(abab)返回0；Use the following procedures to determine whether the string s is symmetry, symmetry returns 1, otherwise return 0; such as f (abab) returns 0;int f(char s[])
{
int i=0,j=0;
while(s[j])
(1)__++;
for(j--; i j s[i] == s[j]; i++, j--);
return((2)__=(3)__);
}注：(1)和(2)和(3)三个答案之间用空格分隔，每个答案是一个字符,不要加空格
A、
13、【填空题】上一题中的字符串BAAABBBAA，与目标BAAABBBCDDDCCHHHHBBBAAABBBAADD进行匹配，至少需要多少次字符匹配（提示：利用优化后的Next数组):The string in question above BAAABBBAA matches with BAAABBBCDDDCCHHHHBBBAAABBBAADD. How many times character matching will need at least? (Hint: Use “Next” arrays ): <img style="border-bottom-color: rgb(163, 163, 163); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(163, 163, 163); border-left-style: none; border-left-width: 0px; border-right-color: rgb(163, 163, 163); border-right-style: none; border-right-width: 0px; border-top-color: rgb(163, 163, 163); border-top-style: none; border-top-width: 0px; margin-top: 10px; max-width: 830px;" src="http://www.chinesemooc.org/attachment/homework/pic/20151021/2365/38203181445421957.png" />
A、
第五章 二叉树前半部分（5.1~5.4）测验
1、【多选题】下列关于二叉树性质的说法正确的有：（多选）Which sentences of the followings are right about a binary tree's characterization:（There are more than one correct answers）
A、非空满二叉树的结点个数一定为奇数个。 The amount of nodes of a full binary tree with at least one node must be odd.
B、非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。Sequential storing structure can also be used to store an incomplete binary tree just like to store a complete binary tree.
C、当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。If a complete binary tree is a full binary tree, it will be possible that leaf nodes is no t on the nethermost layer.
D、完全二叉树最多只有最下面的一层结点度数可以小于2。For a complete binary tree, only the degrees of nodes on the nethermost layer could be less than 2.
E、一棵非空二叉树的为空的外部结点数目等于其结点数加1。The amount of external null nodes in a binary tree with at least one node equals to its amount of nodes plus 1.
F、满二叉树的所有结点的度均为2。All degrees of nodes in a full binary tree are 2.
2、【多选题】下列关于二叉树遍历的说法正确的有:Which sentences of the followings are right about traversal of a binary tree:
A、前序和中序遍历的顺序恰好一样的二叉树，只能是空二叉树或者独根二叉树这两种情况。Only the sequences of preorder and infix order of the binary tree with no nodes or only one node are the same.
B、所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。The sequences of preorder and infix order of a binary tree with all nodes without left child tree are the same.
C、所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。The sequences of preorder and infix order of a binary tree with all nodes without right child tree are the same.
D、只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。Only the sequences of preorder and post order of the binary tree with no nodes or only one node are the same.
E、所有结点左子树为空的二叉树的前序和后序遍历顺序恰好一样。The sequences of preorder and post order of a binary tree with all nodes without left child tree are the same.
F、所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。The sequences of preorder and post order of a binary tree with all nodes without left child tree are the same.
G、只有空二叉树和一个根结点的二叉树这两种二叉树的中序和后序遍历的顺序恰好一样。Only the sequences of infix order and post order of the binary tree with no nodes or only one node are the same.
H、所有结点左子树为空的二叉树的中序和后序遍历顺序恰好一样。The sequences of infix order and post order of a binary tree with all nodes without left child tree are the same.
I、所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。The sequences of infix order and post order of a binary tree with all nodes without right child tree are the same.
J、 存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。There exists a binary tree with at least one node, whose preorder, infix order and post order are all the same.
3、【填空题】一棵有510个结点的完全二叉树的高度为多少？（独根树高度为1)What is the height of a complete binary tree with 510 nodes? (the height of a tree with only a root is 1)
A、
4、【填空题】一棵有512个结点的完全二叉树的高度为多少？（独根树高度为1）What is the height of a complete binary tree with 512 nodes? (the height of a tree with only a root is 1)
A、
5、【填空题】在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n=________ (系统根据字符串匹配来判定答案，所以您的答案中请不要包含空格) For a binary tree with at least one node, if there are n nodes with degree 0 and m nodes with degree 2, then n = ________（This problem is judged by string matching, Please make sure your answer don't contain any blanks.）
A、
6、【填空题】已知一棵树的前序遍历为ABDEGCF，中序遍历为DBGEACF，求这棵树的后序遍历。（字母和字母之间不要有空格）The preorder sequence of a tree is ABDEGCF, and its infix order sequence is DBGEACF, please write down its post order sequence. (There is no blank space between letters)
A、
7、【填空题】已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这棵树的前序遍历。（字母和字母之间不要有空格）The infix order sequence of a tree is DBGEACF, and its post order sequence is DGEBFCA, please write down its preorder sequence. (There is no blank space between letters)
A、
8、【填空题】请写出下面这棵二叉树的前序遍历（字母和字母之间不要有空格）
Please write down the preorder sequence of the following binary tree. (There is no blank space between letters)<img src="http://edu-image.nosdn.127.net/6608B693B4B3B371B40A3A12EA63A790.png?imageView&thumbnail=890x0&quality=100" />
A、
9、【填空题】请写出下面这棵二叉树的中序遍历（字母和字母之间不要有空格）
Please write down the infix order sequence of the following binary tree. (There is no blank space between letters)<img src="http://edu-image.nosdn.127.net/F619CBB40A1D1EAB730526C85E30DA93.png?imageView
A、
10、【填空题】请写出下面这棵二叉树的后序遍历（字母和字母之间不要有空格）
Please write down the post order sequence of the following binary tree. (There is no blank space between letters)<img src="http://edu-image.nosdn.127.net/A097E5BAED7890E66F9D339C2AC9FB3D.png?imageView&thumbnail=890x0&quality=100" />
A、
第五章 二叉树后半部分（5.5~5.7）测验
1、【多选题】下列关于二叉搜索树的说法正确的有Which sentences of the followings are right about binary search tree:
A、二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。If we print a binary search tree's nodes according its infix order, the sequence will be from small to large.
B、如果结点χ的左子树有右子树，则存在某个结点的值介于结点χ的值和χ左儿子的值之间，并且这个结点在$$x$$的左子树之中。If the left child tree of a node x has a right child tree, then there exists some node whose value is between the value of node x and the value of its left child node, and this node is on the left child tree of node x.
C、当根结点没有左儿子时，根结点一定是值最小的结点。If the root node doesn't have left child, it must be the node with the smallest value.
D、 二叉搜索树一定是满二叉树。A binary search tree must be a full binary tree.
E、二叉搜索树一定是完全二叉树。A binary search tree must be a complete binary tree.
F、 从根结点一直沿右儿子向下找不一定能找到树中值最大的结点。Along the right child of nodes all the time from the root node, it is possible that we couldn't find out the node with the largest value.
2、【多选题】下列关于堆的说法正确的有: Which sentences of the followings are right:
A、堆一定是满二叉树。A heap must be a full binary tree.
B、最小堆中，最下面一层最靠右的结点一定是权值最大的结点。In a minimum heap, the rightest node on the nethermost layer must be the node with the largest value.
C、堆是实现优先队列的惟一方法。A heap is the only method to implement a priority queue.
D、堆一定是完全二叉树。A heap must be a complete binary tree.
E、最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。In a minimum heap, the largest value on some node's left child tree could be possibly smaller than the smallest value of its right child tree.
F、使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。Screening method has a higher efficiency than inserting elements one by one while constructing a heap.
3、【多选题】下列关于Huffman树和Huffman编码的说法正确的有:Which sentences of the followings are right about Huffman tree and Huffman code:
A、Huffman树一定是满二叉树。A Huffman tree must be a full binary tree.
B、Huffman编码是一种前缀编码。Huffman code is a kind of prefix code.
C、Huffman树一定是完全二叉树。A Huffman tree must be a complete binary tree.
D、Huffman编码中所有编码都是等长的。All codes in a Huffman code have the same length.
E、 对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。Different content with the same group of weights can get different Huffman codes.
F、使用频率越高的字母，Huffman编码越长。The higher a letter's frequency is, the longer its Huffman code is.
4、【多选题】一组包含不同权的字母已经对应好Huffman编码，如果某一个字母对应编码001,下面说法正确的有A group of letters with different weights has corresponded with Huffman codes, if a letter's corresponding code is 001, which sentences of the followings are right:
A、 以001开头的编码不可能对应其他字母。A code beginning with 001 couldn't correspond with other letters.
B、以000开头的编码不可能对应任何字母。Codes beginning with 000 couldn't correspond with any letter.
C、 以01开头和1开头的编码肯定对应某个字母。Codes beginning with 01 or 1 must correspongding with some letters.
D、建好的Huffman树至少包含4个叶结点。The Huffman tree contains at least 4 leaf nodes.
E、编码0和00可能对应于其他字母。Code 0 and 00 could corresponding with other letters.
5、【填空题】如果按关键码值递增的顺序依次将n个关键码值插入到二叉搜索树中，如果对这样的二叉搜索树进行检索时，每次检索的字符都等概率的从这n个关键码值中选取，平均比较次数为多少？If we insert n key values to a binary search tree successively from small to large, when we search this binary search tree, each time the search character is selected from these n key values with the same possibility, then how many times will the comparison be on average?
A、
6、【填空题】从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树，对该二叉搜索树按照前序遍历得到的序列为？（答案中每两个元素之间用一个空格隔开）From a null binary tree, insert key values {18, 73, 10, 5, 68, 99, 27, 41, 51, 32, 25} successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. Please write down the sequence of preorder of this binary search tree. (There is one blank space between two elements)
A、
7、【填空题】从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树，对该二叉搜索树按照后序遍历得到的序列为？（答案中每两个元素之间用一个空格隔开）From a null binary tree, insert key values {18, 73, 10, 5, 68, 99, 27, 41, 51, 32, 25} successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. Please write down the sequence of post order of this binary search tree. (There is one blank space between two elements)
A、
8、【填空题】从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码构造出一棵二叉树，以怎样的顺序插入关键码集合{14，32，47，6，9，12，78，63，29，81}可以使得树的深度最小？请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。如果有多组满足要求的方案，请使得你的答案中先插入的元素尽可能的小。From a null binary tree, insert key values successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. What is the insertion sequence that could make the tree have a smallest depth with a key value set {14，32，47，6，9，12，78，63，29，81}? Please write down the elements successively, and there is one blank space between two elements. If there are more than one answer that meet the condition, please make the element which needs to be inserted first as small as possible in your answer.
A、
9、【填空题】对于关键码序列{38，64，52，15，73，40，48，55，26，12}，用筛选法建最小值堆，若一旦发现逆序对就进行交换，共需要交换元素多少次？For the key value sequence {38，64，52，15，73，40，48，55，26，12}, use the screening method to constuct a minimum heap, if we exchange them when we find reversed order, then how many times should we exchange them?
A、
10、【填空题】对于如下图所示的最大堆，删除掉最大的元素后，堆的前序遍历结果是For the following maximum heap, after deleting the maximum element, the preorder traversal sequence is请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。Please write down the elements successively, and there is one blank space between two elements.<img src="http://edu-image.nosdn.127.net/99B353F4B8E7689AD7A53D3E323E01D8.png?imageView
A、
11、【填空题】对于如下图所示的最大堆，删除掉最大的元素后，堆的后序遍历结果是For the following maximum heap, after deleting the maximum element, the post order traversal sequence is<img src="http://edu-image.nosdn.127.net/B1D6BD4ED310A27D7C1AD3B13D02003E.png?imageView&thumbnail=890x0&quality=100" />
A、
12、【填空题】下表展示了在一段文本中每个字母出现的次数。The frequencies that each letter appears in a paragraph is represented as follow.<img src="http://edu-image.nosdn.127.net/32D940E26C5381A2A7A12FC43A6AA886.png?imageView对于这段文本使用Huffman编码相较使用等长编码能够节约多少比特的空间？Comparing to use codes that have the same length, how many bits of space could be saved when we use Huffman code for the paragraph?<img src="http://edu-image.nosdn.127.net/9ECB5ECCC57ABD293ACBF4489A3D2970.png?imageView
A、
13、【填空题】对于给定的一组权W={1,4,9,16,25,36,49,64,81,100}，构造一棵具有最小带权外部路径长度的三叉树，写出这棵树的带权外部路径长度。For a given group of weights W={1, 4, 9, 16, 25, 36, 49, 64, 81, 100}, please construct a ternary tree with a minimum weighted route length and write down this weighted route length.
A、
14、【填空题】请阅读下面一段代码 Please read the following codeC++：<img src="http://edu-image.nosdn.127.net/437E113CB6B47EF6B33ED279C606337A.png?imageView&thumbnail=890x0&quality=100" />Python：<img src="http://edu-image.nosdn.127.net/4837011A87CE1504BE9F042B70DF9D18.png?imageView&thumbnail=890x0&quality=100" />若此段代码的作用是用来进行前序遍历，那么应该在几号访问点进行访问？（只需要填写数字）if this code is used to do a preorder traversal, which visiting point should be visited? (You only need to write down the number)
A、
15、【填空题】请阅读下面一段代码Please read the following codeC++：<img src="http://edu-image.nosdn.127.net/5F9B8703C7ADC44BCC161FCDF4EFFB51.png?imageView&thumbnail=890x0&quality=100" />Python：<img src="http://edu-image.nosdn.127.net/4BB227C83AF894FA2FC1FBF0A66CD63A.png?imageView&thumbnail=890x0&quality=100" />若此段代码的作用是用来进行中序遍历，那么应该在几号访问点进行访问？（只需要填写数字）if this code is used to do an infix order traversal, which visiting point should be visited? (You only need to write down the number)
A、
16、【填空题】请阅读下面一段代码Please read the following code C++：<img src="http://edu-image.nosdn.127.net/70B46CD38B135B0A1D20C56DAA9E5608.png?imageViewPython：<img src="http://edu-image.nosdn.127.net/E5F447DC904597FF310FC7F95970003B.png?imageView若此段代码的作用是用来进行后序遍历，那么应该在几号访问点进行访问？（只需要填写数字）if this code is used to do an post order traversal, which visiting point should be visited? (You only need to write down the number)
A、
第六章 树测验
1、【单选题】一个深度为h的满k叉树，最多有多少个叶结点？（独根树深度为0）(单选)There is a full k-ary tree, whose depth is h. How many leaf nodes can it have at most? (The depth of a tree, which only has a root node, is 0.)（There is only one correct answer）
A、<img src="http://img1.ph.126.net/9OKi3I4MdCslKBltpCymHQ==/6632701639979432383.png" />
B、<img src="http://img1.ph.126.net/Bsd_i262wr4a75zcxAry6g==/6632702739491060131.png" />
C、<img src="http://img1.ph.126.net/vcJQLl5qogNzK7-N7ryySQ==/3081869520025011217.png" />
D、<img src="http://img1.ph.126.net/SHbRSZL9nlbhNumr-r8dtA==/92042317404418279.png" />
2、【单选题】一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.)
A、<img src="http://img1.ph.126.net/9OKi3I4MdCslKBltpCymHQ==/6632701639979432383.png" />
B、<img src="http://img1.ph.126.net/Bsd_i262wr4a75zcxAry6g==/6632702739491060131.png" />
C、<img src="http://img1.ph.126.net/vcJQLl5qogNzK7-N7ryySQ==/3081869520025011217.png" />
D、<img src="http://img1.ph.126.net/SHbRSZL9nlbhNumr-r8dtA==/92042317404418279.png" />
3、【单选题】设F是由T1,T2,T3三棵树组成的森林，其中T1,T2,T3的结点数分别为n1,n2和n3，与F对应的二叉树为B，则二叉树B的右子树中有_____________个结点(单选）Assume that F is a forest, made up of tree T1, T2, T3, and the node numbers of T1, T2, T3 are n1, n2, n3. Let B be the corresponding binary tree of F, then B's right sub-tree will has __________ nodes. (There is only one correct answer)
A、n2
B、n3
C、n1+n3
D、n2+n3
4、【单选题】设F是由T1,T2,T3三棵树组成的森林，其中T1,T2,T3的结点数分别为n1,n2和n3，与F对应的二叉树为B，则二叉树B的左子树中有_____________个结点(单选）Assume that F is a forest, made up of tree T1, T2, T3, and the node numbers of T1, T2, T3 are n1, n2, n3. Let B be the corresponding binary tree of F, then B's left sub-tree will has __________ nodes. (There is only one correct answer)
A、n2-1
B、n3-1
C、n1-1
D、 n2
5、【单选题】将一棵树T转换为左子/右兄链表表示的二叉树B，则T的后根次序遍历序列是B的相应_________序列。（单选） Transform a tree T into a binary tree B, which is represented by Left-Child/Right-Sibling implementation. Then the post-order traversal sequence of T is the same as the __________ sequence of B.（There is only one correct answer）
A、前序遍历
B、后序遍历
C、中序遍历
D、层次遍历
6、【多选题】2-3树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同；如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。 (多项)2-3 tree is a special kind of tree, it satisfy:（1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node.
If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers）
A、4
B、5
C、6
D、7
7、【填空题】给出一棵树的逻辑结构T=(N,R),其中：N={A,B,C,D,E,F,G,H,I,J,K}R={r}r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}Given a logical structure of a tree, T=(N, R), and N={A, B, C, D, E, F, G, H, I, J, K}, R={r}, r={(A,B), (B,E), (B,F), (F,G), (F,H), (A,C), (C,I), (C,J), (J,K), (A,D)}试回答下列问题：Please answer these questions: （1）哪个是根结点？which is the root node? （2）哪些是F的孩子？which are the child nodes of Node F?（3）结点K的层次是多少？ （注：根的层数为0，独根树深度为0，高度为1，其他题目同样如此；同一个选项的答案如果有多个字母，按照字典序排列，且不要以空格分隔） (P.S. the level of the root node is 0, the depth of a tree, which only has a root node, is 0, and its height is 1. Other problems have the same regulations. If there are several alphabets in one question, order them by lexicographical order, and do not add spaces.)
A、
8、【填空题】给出一棵树的逻辑结构T=(N,R),其中：N={A,B,C,D,E,F,G,H,I,J,K} R={r} r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}试回答下列问题：Given a logical structure of a tree, T=(N, R), and N={A, B, C, D, E, F, G, H, I, J, K}, R={r}, r={(A,B), (B,E), (B,F), (F,G), (F,H), (A,C), (C,I), (C,J), (J,K), (A,D)} Please answer these questions: （1）哪个是F的父结点？which is the parent node of Node F?（2）哪些是B的子孙？which are the offspring of Node B?（3）以结点C为根的子树的深度是多少？what is the depth of the sub-tree whose root node is Node C? （注：根的层数为0，独根树深度为0，高度为1，其他题目同样如此；各个选项之间的答案用空格分隔就好；同一个选项的答案如果有多个字母，按照字典序排列，且不要以空格分隔） （P.S. the level of the root node is 0, the depth of a tree, which only has a root node, is 0, and its height is 1. Other problems have the same regulations. If there are several alphabets in one question, order them by lexicographical order, and do not add spaces.)
A、
9、【填空题】给出一棵树的逻辑结构T=(N,R),其中：N={A,B,C,D,E,F,G,H,I,J,K}R={r}r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)} 试回答下列问题：Given a logical structure of a tree, T=(N, R), and N={A, B, C, D, E, F, G, H, I, J,K}, R={r}, r={(A,B), (B,E), (B,F), (F,G), (F,H), (A,C), (C,I), (C,J), (J,K), (A,D)} Please answer these questions: （1）哪些是叶结点？which are the leaf nodes? （2）哪些是F的祖先？which is the parent node of Node F? （3）树的深度是多少？what is the depth of the tree?（注：根的层数为0，独根树深度为0，高度为1，其他题目同样如此；同一个小题的答案如果有多个字母，按照字典序排列，且不要以空格分隔，不同小题用一个空格隔开）
A、
10、【填空题】若一个具有N个顶点，K条边的无向图是一个森林（NK且2K=N），则该森林有多少棵树？
There is an undirected graph. It has N nodes and K edges. (NK and 2K=N). If it is a forest, then how many trees will it has?
A、
11、【填空题】将下图的二叉树转换为对应的森林，按照先根次序列出其结点。（答案的字母之间没有空格）Transform this binary tree into the corresponding forest, and write down the pre-order node sequence. (Do not add spaces in your answer.)<img style="border: 0px none rgb(163, 163, 163); color: rgb(163, 163, 163); font-size: 16px; font-variant-numeric: normal; font-variant-east-asian: normal; margin-top: 10px; max-width: 830px; white-space: normal;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2368/38203181445494563.png" />
A、
12、【填空题】将下图的二叉树转换为对应的森林，按照后根次序列出其结点。（答案的字母之间没有空格）Transform this binary tree into the corresponding forest, and write down the post-order node sequence. (Do not add spaces in your answer.)<img style="border: 0px none rgb(163, 163, 163); color: rgb(163, 163, 163); font-size: 16px; font-variant-numeric: normal; font-variant-east-asian: normal; margin-top: 10px; max-width: 830px; white-space: normal;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2368/38203181445495012.png" />
A、
13、【填空题】一棵完全三叉树，下标为121的结点在第几层？（注：下标号从0开始，根的层数为0）In a complete 3-ary tree, what level is the node, whose subscript is 121, stand on?(P.S. the subscript starts form 0, and the level of root node is 0)
A、
14、【填空题】一棵完全三叉树，下标为120的结点在第几层？（注：下标号从0开始，根的层数为0）In a complete 3-ary tree, what level is the node, whose subscript is 120, stand on? (P.S. the subscript starts form 0, and the level of root node is 0)
A、
15、【填空题】根据树的双标记层次遍历序列，求其带度数的后根遍历序列Given the double-tagging level-order traversal sequence of a tree, please write down the post-order traversal sequence with degree.比如：已知一棵树的双标记层次遍历序列如下：For example, assume that a tree's double-tagging level-order traversal sequence is shown as followed:<img style="border: 0px none rgb(163, 163, 163); color: rgb(163, 163, 163); font-size: 16px; font-variant-numeric: normal; font-variant-east-asian: normal; margin-top: 10px; max-width: 830px; white-space: normal;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2368/38203181445496199.png" />
A、
16、【填空题】根据树的双标记层次遍历序列，求其带度数的后根遍历序列 Given the double-tagging level-order traversal sequence of a tree, please write down the post-order traversal sequence with degree.比如：已知一棵树的双标记层次遍历序列如下：For example, assume that a tree's double-tagging level-order traversal sequence is shown as followed:<img style="border: 0px none rgb(163, 163, 163); color: rgb(163, 163, 163); font-size: 16px; font-variant-numeric: normal; font-variant-east-asian: normal; margin-top: 10px; max-width: 830px; white-space: normal;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2368/38203181445496836.png" />
A、
17、【填空题】根据树的双标记层次遍历序列，求其带度数的后根遍历序列Given the double-tagging level-order traversal sequence of a tree, please write down the post-order traversal sequence with degree.<img style="border: 0px none rgb(163, 163, 163); color: rgb(163, 163, 163); font-size: 16px; font-variant-numeric: normal; font-variant-east-asian: normal; margin-top: 10px; max-width: 830px; white-space: normal;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2368/38203181445497373.png" />
A、
18、【填空题】对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父节点索引序列。For the following equivalence class, please use weighted union rule and UNION/FIND algorithm to write down the final parent node index sequence. 4-0 6-2 8-4 9-4 3-5 9-5 5-2 1-2 7-1 注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根节点的索引是它本身；数字之间用空格隔开。 Notice: When we join two trees with the same size, we let the root of the second tree point to the root of the first tree. The index of the root node is itself. Separate the numbers with only one spaces.
A、
19、【填空题】对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父节点索引序列。For the following equivalence class, please use weighted union rule and UNION/FIND algorithm to write down the final parent node index sequence. 8-9 3-2 7-4 5-9 6-1 8-6 7-3 2-5 8-0 注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根节点的索引是它本身；数字之间用空格隔开。Notice: When we join two trees with the same size, we let the root of the second tree point to the root of the first tree. The index of the root node is itself. Separate the numbers with only one spaces.
A、
第七章 图测验
1、【单选题】在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。In a undirected graph, the sum of degrees of all vertices is equal to the amount of all edges times ().
A、2
B、3
C、 1
D、1/2
2、【单选题】在有向图G的拓扑序列中，若顶点<img alt="32.png" src="https://i1.chinesemooc.org/course/formula/201510/6bc42131561d441ca849e9be8b2c0954.png" style="border-bottom-color: rgb(102, 102, 102); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(102, 102, 102); border-left-style: none; border-left-width: 0px; border-right-color: rgb(102, 102, 102); border-right-style: none; border-right-width: 0px; border-top-color: rgb(102, 102, 102); border-top-style: none; border-top-width: 0px; margin-bottom: 0px; margin-left: 4px; margin-right: 4px; margin-top: 0px; max-width: 650px; vertical-align: top;" />在顶点<img alt="33.png" src="https://i1.chinesemooc.org/course/formula/201510/be6b2dbd240f63232a26da942820d566.png" style="border-bottom-color: rgb(102, 102, 102); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(102, 102, 102); border-left-style: none; border-left-width: 0px; border-right-color: rgb(102, 102, 102); border-right-style: none; border-right-width: 0px; border-top-color: rgb(102, 102, 102); border-top-style: none; border-top-width: 0px; margin-bottom: 0px; margin-left: 4px; margin-right: 4px; margin-top: 0px; max-width: 650px; vertical-align: top;" />之前，则下列情形不可能出现的是（ ）。In the topological order sequences of the directed graph G, if vertex Vi appears before Vj, then the impossible situation of the following is ()
A、G中有一条从<img src="http://img0.ph.126.net/lRV34U_0fQrUUKwfvpzGRA==/1170935903134281510.png" />到<img src="http://img2.ph.126.net/8zVSWoxr5pG3wC_YJ5nxtg==/6608756475748268834.png" />的路径 There is a path from Vj to Vi in the G.
B、G中有边(<img src="http://img2.ph.126.net/8zVSWoxr5pG3wC_YJ5nxtg==/6608756475748268834.png" />，<img src="http://img0.ph.126.net/lRV34U_0fQrUUKwfvpzGRA==/1170935903134281510.png" />) G contains edge (Vi,Vj).
C、G中有一条从<img src="http://img2.ph.126.net/8zVSWoxr5pG3wC_YJ5nxtg==/6608756475748268834.png" />到<img src="http://img0.ph.126.net/lRV34U_0fQrUUKwfvpzGRA==/1170935903134281510.png" />的路径 G contains a path from Vi to Vj.
D、G中没有边(<img src="http://img2.ph.126.net/8zVSWoxr5pG3wC_YJ5nxtg==/6608756475748268834.png" />，<img src="http://img0.ph.126.net/lRV34U_0fQrUUKwfvpzGRA==/1170935903134281510.png" />) G doesn't contain edge(Vi,Vj)
3、【单选题】当各边上的权值满足什么要求时，宽度优先搜索算法可用来解决单源最短路径问题？
What requirement do the weight of edges should satisfied to make width-first search algorithm can solve single source shortest path problem?
A、均互不相等 Each edge is not equal to each other.
B、均相等Equal
C、不一定相等 No limitation.
D、不一定相等（忽略该选项）
4、【多选题】下面关于图的说法正确的有
The right statements of graphs in the following are:
A、 对于有向图，每个结点的出度必须要等于入度。As for directed graph, each vertices’ out-degree is equal to its in-degree.
B、对于一个连通图，一定存在一种给边添加方向的方案使得这个图变成强连通图。For a connected graph, there must be a way of directing all the edges of the original graph to make the graph strongly connected graph.
C、对于有向图，所有结点的入度加起来一定为奇数。For directed graph, the sum of in-degrees of all nodes must be odd number.
D、对于无向图，所有结点的度数加起来一定是偶数。As for undirected graphs, the sum of degrees of all vertices is definitely even number.
E、 将有向图的一个强连通分量中的边全部反向仍然是强连通分量。Reversion all the edges of a strongly connected component of a directed graph, then the subgraph is still a strongly connected component.
5、【多选题】下列关于最短路算法的说法正确的有：The right statements of the following are:
A、当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。 When the graph doesn't contain circuit of negative weight, but contains the edge of negative weight. Dijkstra algorithm can't guarantee the correctness of the algorithm.
B、当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。 When the graph doesn't contain edge of negative weight, Dijkstra algorithm can calculate the shortest path of each pair of vertices.
C、当图中存在负权回路时，Dijkstra算法也一定能求出源点到所有点的最短路。When the graph contains the circuit of negative weight, Dijkstra algorithm can certainly calculate the shortest path form the single source to all the vertices.
D、 Dijkstra算法不能用于每对顶点间最短路计算。Dijkstra algorithm can't be applied to calculate the shortest path of each pair of vertices.
6、【填空题】下图中的强连通分量的个数为多少个？ How many strongly connected graphs in the under graph? <img style="border-bottom-color: rgb(163, 163, 163); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(163, 163, 163); border-left-style: none; border-left-width: 0px; border-right-color: rgb(163, 163, 163); border-right-style: none; border-right-width: 0px; border-top-color: rgb(163, 163, 163); border-top-style: none; border-top-width: 0px; margin-top: 10px; max-width: 830px;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2369/38203181445500115.png" />
A、
7、【填空题】如果无向图G=(V,E)是简单图，并且|V|=n0，那么图G最多包含多少条边？If undirected graph G = (V,E) is simple graph, and |V| = n 0, then how many edges can graph G contains at most？（There is only one correct answer）
A、
8、【填空题】有向图G如下图所示，请写出所有拓扑排序序列。所有的顶点都直接用其数字标号表示，如拓扑排序序列为<img width="69" height="25" style="border-bottom-color: rgb(102, 102, 102); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(102, 102, 102); border-left-style: none; border-left-width: 0px; border-right-color: rgb(102, 102, 102); border-right-style: none; border-right-width: 0px; border-top-color: rgb(102, 102, 102); border-top-style: none; border-top-width: 0px; height: 25px; margin-bottom: 0px; margin-left: 4px; margin-right: 4px; margin-top: 0px; max-width: 650px; vertical-align: top; width: 69px;" alt="25.png" src="http://i1.chinesemooc.org/course/formula/201510/88c813fc85942f0a5d34232465896b7c.png" />，那么请写成1234（中间没有空格）。不同的拓扑排序序列按照字典序排序，中间用一个空格隔开。Directed graph G looks like following graph, please list all the topological order sequences. All the vertices are marked by numbers directly. Like topological order sequence V1V2V3V4, we write it as 1234(with no blank space).Different topological order sequences are sorted according to alphabet order, and separated by a blank space. <img style="border-bottom-color: rgb(163, 163, 163); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(163, 163, 163); border-left-style: none; border-left-width: 0px; border-right-color: rgb(163, 163, 163); border-right-style: none; border-right-width: 0px; border-top-color: rgb(163, 163, 163); border-top-style: none; border-top-width: 0px; margin-top: 10px; max-width: 830px;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2369/38203181445502389.png" />
A、
9、【填空题】无向图G=(V, E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}，对该图进行深度优先遍历（优先访问编号小的结点），得到的顶点序列为？注意：答案中没有空格 Undirected G = (V,E), concretely: V = {a,b,c,d,e,f}, E = {(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},perform depth-first traversal(visit the vertex of small number firstly), what vertices sequence do we get?
Notice: no blank space in answer.
A、
10、【填空题】请使用Kruskal算法求出下图的最小生成树，依次写出每次被选择的合法的合并代价最小的边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b (a b)之间的边编号为ab，例如图中权值为1的边编号为02。(不同编号之间用一个空格分隔） Please use Kruskal algorithm to the following graph and find the minimum spanning tree, and write the number of the valid vertex with minimum merging cost in turn(if there are many vertices satisfy requirement, choose the vertex with minimum number ). The number of the edge connecting vertex a and vertex b is ab. Like the edge with weight 1 in the graph, its number is 02(different numbers separated by a blank space). <img style="border-bottom-color: rgb(163, 163, 163); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(163, 163, 163); border-left-style: none; border-left-width: 0px; border-right-color: rgb(163, 163, 163); border-right-style: none; border-right-width: 0px; border-top-color: rgb(163, 163, 163); border-top-style: none; border-top-width: 0px; margin-top: 10px; max-width: 830px;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2369/38203181445504670.png" />
A、
11、【填空题】请使用Prim算法从结点0出发求下图的最小生成树，依次写出每次被加入到最小生成树中边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b (a b)之间的边编号为ab，例如图中权值为1的边编号为02。(不同编号之间用一个空格分隔）Please use prim algorithm starting from vertex 0 to find the minimum spanning tree of the following graph, write the number of the edge added into the minimum spanning tree in turn((if there are many vertices satisfy requirement, choose the vertex with minimum number). The number of the edge connecting vertex a and vertex b is ab. Like the edge with weight 1 in the graph, its number is 02(different numbers separated by a blank space). <img style="border-bottom-color: rgb(163, 163, 163); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(163, 163, 163); border-left-style: none; border-left-width: 0px; border-right-color: rgb(163, 163, 163); border-right-style: none; border-right-width: 0px; border-top-color: rgb(163, 163, 163); border-top-style: none; border-top-width: 0px; margin-top: 10px; max-width: 830px;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2369/38203181445504847.png" />
A、
12、【填空题】题图为一无向图,分别写出从顶点1出发,按深度优先搜索遍历算法得到的顶点序列,和按广度优先搜索遍历算法得到的顶点序列 <img style="border-bottom-color: rgb(163, 163, 163); border-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-source: none; border-image-width: 1; border-left-color: rgb(163, 163, 163); border-left-style: none; border-left-width: 0px; border-right-color: rgb(163, 163, 163); border-right-style: none; border-right-width: 0px; border-top-color: rgb(163, 163, 163); border-top-style: none; border-top-width: 0px; margin-top: 10px; max-width: 830px;" src="http://www.chinesemooc.org/attachment/homework/pic/20151022/2369/38203181445505004.png" />
A、
第八章 内排序前半部分（8.1~8.4）测验
1、【单选题】对于序列{E，A，S，Y，Q，U，E，S，T，I，O，N}，以{6，3，1}为增量采用Shell排序。头两趟{6，3}增量排序后，关键字的累积比较次数为()。
A、 16
B、17
C、 18
D、15
2、【单选题】下列排序方法的比较次数与记录的初始排列状态无关的是( )。
A、直接选择排序
B、直接插入排序
C、冒泡排序
D、快速排序
3、【单选题】需要对1000个大型的记录进行排序，记录本身存储在外存中，在内存中只保存了所有记录的排序码。排序码之间的比较非常快，但是移动代价很大，因为一旦移动一个排序码，相应的外存中的记录也要移动，将涉及上百个磁盘块的移动，应该使用何种排序方法()
A、直接选择排序
B、堆排序
C、快速排序
D、插入排序
4、【单选题】在图书馆里计算机类书籍区一共有12列书架，书架上的书本来都是按照编目号排列好的，其中有些书被读者放错了地方，但通常不会超过一个书架。来将这些书重新放回正确位置，应该使用何种排序方法()
A、插入排序
B、归并排序
C、快速排序
D、 直接选择排序
E、堆排序
5、【多选题】下面是图的拓扑排序的是？ (多选)<img src="http://edu-image.nosdn.127.net/7367959A8727518A338FA88AFC37DD5D.jpg?imageView
A、12 13 1 4 2 3 9 10 5 8 6 7 11
B、1 12 4 13 2 3 9 10 11 7 6 8 5
C、12 1 4 13 2 3 5 6 8 9 10 11 7
D、1 12 4 2 13 3 9 5 8 6 7 10 11
6、【多选题】下面是图的拓扑排序的是？(多选)<img src="http://edu-image.nosdn.127.net/999DCA01FDE3A1987986F7F004A4EFCC.png?imageView
A、2 8 0 7 1 3 5 6 4 9 10 11 12
B、2 8 7 0 6 9 11 12 10 1 3 5 4
C、8 2 7 3 0 6 1 5 4 9 10 11 12
D、 8 2 7 0 6 9 10 11 12 1 3 5 4
7、【填空题】已知一组元素的排序码为(46，74，16，53，14，26，40，38，86，65，27，34)，利用直接插入排序的方法（第一个数字不用插入）,写出第四次向前面有序表插入一个元素后的排列结果。注意：数字中间用一个空格隔开，不要写逗号和括号。答案一共有12个数字。
A、
8、【填空题】已知一组元素的排序码为(46，74，16，53，14，26，40，38，86，65，27，34)，利用直接选择排序方法写出第三次选择和交换后的排列结果。注意：数字中间用一个空格隔开，不要写逗号和括号。答案一共有12个数字。
A、
9、【填空题】某整型数组Ａ的１０个元素值依次为4,2,7,3,7,2,9,1,0,8,用快速排序方法（课程中介绍的快速排序实现方式），取第一个元素值4作为分割数，将Ａ中元素由小到大排序，写出快速排序第一次分隔后Ａ中的结果()。数字中间用一个空格隔开。
A、
10、【填空题】某整型数组Ａ的１０个元素值依次为6,2,9,7,3,8,4,5,0,1,用快速排序方法（课程中介绍的快速排序实现方式），取第一个元素值６作为分割数，将Ａ中元素由小到大排序，写出快速排序第一次分隔后Ａ中的结果()。数字中间用一个空格隔开。
A、
11、【填空题】某整型数组Ａ有11个元素，用最大堆排序方法，将Ａ中元素构造成一个最大堆，该最大堆的元素序列为X,T,S,P,L,R,A,M,O,E,E ,试写出将第一个选出的数据与Ａ的最后位置上的元素交换后，将Ａ重新调整成最大堆后，堆的元素序列为()。中间用一个空格隔开。
A、
12、【填空题】一组记录的关键字为45，80，55，40，42，85，则利用堆排序的方法建立的初始最大堆为________。（数字之间用一个空格隔开，答案中不含逗号和括号）
A、
13、【填空题】15个记录的冒泡排序算法所需最大交换次数为______，最小交换次数为______。注意：答案中，两个数字之间用一个空格隔开，其余不含任何符号。
A、
14、【填空题】在对一组记录（50，40，95，20，15，70，60，45，80）进行从小到大冒泡排序（从后往前冒泡）时，第一趟需进行相邻记录的交换的次数为（ ），在整个排序过程中共需进行（ ）趟才可完成。注意：答案是由一个空格隔开的两个数字
A、
第八章 内排序后半部分（8.5~8.10）测验
1、【单选题】对初始状态为递增的表按递增顺序排序，最省时间的是（ ）算法
A、插入排序
B、堆排序
C、快速排序
D、归并排序
2、【单选题】大部分排序算法是通过不断交换记录来减小序列中的逆置数，从而实现排序。假设有n个记录，那么交换序列中两个不同的记录，最多能减少()个逆置？
A、2n-3
B、2n-1
C、n-1
D、n+1
3、【单选题】假设数组长度为n (n=20)，基数为r (r=10)，排序码个数为d (d=3)，则采用顺序存储的基数排序的空间复杂度至少为 Θ(________)
A、 n+r
B、n
C、 r
D、n*r
4、【多选题】下列排序算法中，最坏情况下时间复杂度为Θ(nlog n)的是()
A、归并排序
B、堆排序
C、直接插入排序
D、选择排序
E、快速排序
F、shell排序
G、桶式排序
5、【多选题】请问下面哪些操作在已排序数据上实施比在无序的数据上快()？
A、 找最小值
B、 找中位数
C、计算算术平均值
D、 计算标准差
6、【多选题】下面的排序算法哪些是稳定的()。
A、 插入排序
B、冒泡排序
C、归并排序
D、桶式排序
E、shell排序
F、选择排序
G、 堆排序
H、 快速排序
7、【多选题】对于排序算法特性的叙述正确的是()
A、 冒泡排序不需要访问那些已排好序的记录
B、 shell排序过程中，当对确定规模的这些小序列进行插入排序时，要访问序列中的所有记录
C、快速排序过程中，递归树上根据深度划分的每个层次都要访问序列中的所有记录
D、选择排序需要访问那些已排好序的记录
E、归并排序过程中，递归树上每个层次的归并操作不需要访问序列中的所有记录
F、 基数排序过程中，按照每个排序码进行的桶式排序不需要访问序列中的所有记录
8、【多选题】排序算法大都是基于数组实现的，大部分的算法也能用链表来实现，但有些特殊的算法不适合线性链表存储，不适合（使算法复杂度增大）链式存储的算法有()
A、 堆排序
B、 shell排序
C、 直接选择排序
D、插入排序
E、归并排序
F、 快速排序
9、【多选题】对于如下数组：67 98 45 78 23 56 14 77使用索引排序，则辅助用的索引数组最后可以是 _______________
A、 6 4 2 5 0 7 3 1
B、4 7 2 6 1 3 0 5
C、 4 7 2 6 1 5 0 3
D、0 7 3 1 6 4 2 5
10、【填空题】已知一组元素的排序码为(67, 34, 56, 12, 88, 3, 15, 36, 27, 98, 11, 55)，利用自顶向下划分的非优化归并排序方法（划分到小于等于2个元素），写出第二趟二路归并排序后的结果()。中间用一个空格隔开。
A、
11、【填空题】已知一组元素的排序码为(46，74，16，53，14，26，40，38，86，65，27，34)，利用自顶向下划分的非优化归并排序方法（划分到小于等于2个元素），写出第二趟二路归并排序后的结果()。中间用一个空格隔开。
A、
12、【填空题】已知数组A如下： 45 23 64 15 90 87 61 42采用低位优先法的基数排序进行升序排序的第一轮之后的排序结果为？（数字间以一个空格分隔）
A、
数据结构与算法期中考试
1、【单选题】一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）For a full k-ary tree with depth h, how many nodes could it have at most? (the depth of a tree with only one node is 0)
A、<img src="http://img1.ph.126.net/vcJQLl5qogNzK7-N7ryySQ==/3081869520025011217.png" />
B、<img src="http://img1.ph.126.net/9OKi3I4MdCslKBltpCymHQ==/6632701639979432383.png" />
C、<img src="http://img1.ph.126.net/Bsd_i262wr4a75zcxAry6g==/6632702739491060131.png" />
D、<img src="http://img1.ph.126.net/SHbRSZL9nlbhNumr-r8dtA==/92042317404418279.png" />
2、【单选题】对二叉排序树（即BST，也称“二叉搜索树”）进行什么 遍历，可以得到该二叉树所有结点构成的排序序列？From which traversal can we get the ordered sequence of the nodes of a binary search tree?
A、前序 preorder
B、后序 postorder
C、按层次 levelorder
D、中序 inorder
3、【单选题】若无向图G的顶点度数最小值大于等于x时，G至少有一条回路。求x的最小值。If the minimum degree of vertices of undirected graph G is bigger than or equal to x, and G have at least one circuit. What is the minimum value of x?
A、1
B、2
C、3
D、4
4、【单选题】用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查_________的第 i 行第 j 列的元素是否为零即可。Using an adjacency matrix A to represent a graph, we just need to check whether the element in the row i, column j of ________ is zero to tell whether there is a path with length m connecting vertex Vi and Vj.
A、<img src="http://img2.ph.126.net/T5_Uu-8nlyEMg50wg5-KBw==/6597300664100490728.png" />
B、mA
C、A
D、<img src="http://img2.ph.126.net/lGEdyy2X8tj1sA5Egh9n9Q==/725079540107070545.png" />
5、【多选题】顺序栈是用一段连续的空间存储内容，本质是顺序表。链式栈则是采用单链表的方式存储。下列关于这两种存储方式的说法正确的是： Sequential stack stores elements in a contiguous space, which is essentially a sequential list. Linked stack is implemented by a single linked list instead. Which of the following about the two storage methods are correct? (multiple choice)
A、顺序栈的压栈和出栈操作只需常数时间。 The push and pop operation of sequence stack only needs constant time.
B、链式栈的压栈和出栈操作只需常数时间。 The push and pop operation of linked stack only needs constant time.
C、顺序栈需要指定一个具体的长度 Sequential stack needs to be assigned a specific length.
D、链式栈需要一个结构性开销 Linked stack needs a structural cost.
6、【多选题】在字符{A, C, G, T}组成的DNA序列中，A —— T和C —— G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串；即要求整个原串的补串是原串的逆序）；下面DNA序列中存在互补回文串的是：(多选)In DNA sequences consisting of characters {A, C, G, T}, A - T and C - G are complementary pairs respectively.Determine whether a DNA sequence has a complementary palindromic string (For example, ATCATGAT's complementary string is TAGTACTA, with is the palindromic sequence to the original string; in such case the complementary string is also the reverse of the original string);Which of the following DNA sequences have complementary palindromic string? （multiple choice）
A、CTGATCAG
B、AATTAATT
C、GTACGTAC
D、AGCTAGCT
7、【多选题】2-3树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同；如果一棵2-3树有10个叶结点，那么它可能有_________个非叶结点。 (多选)2-3 tree is a special kind of tree, which satisfies:（1） Every internal node has 2 or 3 children nodes. (2) All the leaf nodes have the same path length from the root node.If a 2-3 tree has 10 leaf nodes, then it may have __________ non-leaf nodes. （multiple choice）
A、8
B、7
C、5
D、6
8、【填空题】由小到大写出以下时间复杂度的序列：Ascending write the sequence of followings according to their time complexit：(1)n²+100n(2)3n²+100n²(3)10+3Log10n(4)10n+20nLog10n(5)<img src="http://img2.ph.126.net/qBQGx0Z9T_pt4PZJc8Nn7g==/6608560762678510607.png" />(6)1000n答案直接写标号，如：(1)(2)(3)(4)(5) （提示：系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Write down the answer labels such as (1)(2)(3)(4)(5). （Hint：This problem is judged by string matching, Please make sure your answer don't contain any blanks.
A、
9、【填空题】计算运行下列程序段后s的值：After running the following program segment, the value of s is:n=10; s=0;
for( k = 1; k n - 1; k++)
for( j = n; j = k; j--)
s = s + 1;
A、
10、【填空题】双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有11个不同的元素顺序输入到双端队列，那么可以得到多少种不同的排列？Deque can do insert and delete operations on both ends of the queue, can insert / delete in the team head and also in the tail. Existing 11 different elements enter the double-ended queue orderly, then how many different permutations can you get?
A、
11、【填空题】按照课程中介绍的机械的递归转换，将下列递归过程改写为非递归过程后，程序中需要设置____个语句标号。According to the description in class about recursive mechanical conversion, rewritten the following recursive procedure into non recursive process, the program needs set ____ statement labels.void test(int sum){
int x;
scanf(x);
if(x == 0){
test(sum);
sum = 0;
}else{
test(sum);
sum += x;
}
printf(sum);
}
A、
12、【填空题】若字符串s =DataMining，则其子串的数目为 （字串数目应该重复计算）If the string s = DataMining, then the number of its substrings is:________. （If we encounter the same substring , the total should be added one）
A、
13、【填空题】使用KMP算法求出模式p=”aabcaabbaa”的优化后的next数组。注意：只列出数字，数字之间用一个空格分隔。比如：0 0 0 0 0 0 0 0 0 0Use KMP algorithm to derive the optimized next array for the pattern p = aabcaabbaa.Note: Write down the numbers in the next array separated by single space.For example: 0 0 0 0 0 0 0 0 0 0
A、
14、【填空题】利用上题(KMP算法题)p=”aabcaabbaa”优化后的Next数组，对t=”aaabaabcabaabcaabbaab”进行匹配。有多少次字符比较？（注意：每一次p中的字符与t中的字符的一次比较计做一次）Use the optimized next array above for pattern p = aabcaabbaato match the target string t = aaabaabcabaabcaabbaab. How many character comparisons are needed?(Note: Each comparison of the characters between p and t counts once)
A、
15、【填空题】一个有4层结点的完全二叉树。按前序遍历周游给结点从1开始编号，则第21号结点的父结点是多少号？（注释：根的层数为0）For a complete binary tree with four levels, label the nodes starting from 1 according to the preorder traversal. what is the label of the parent node for node 21? (The root is on level 0)
A、
16、【填空题】假设一棵二叉树中，度为2的结点有20个，度为1的结点有10个，度为0的结点有多少个？In a binary tree, there are 20 nodes with a degree of 2 and 10 nodes with a degree of 1. How many nodes are with a degree of 0?
A、
17、【填空题】某二叉树中序序列为A,B,C,D,E,F,G, 前序序列为E,A,C,B,D,G,F, 则后序序列是？（注意：答案不要含空格和逗号，比如可以是ABCDEFG）The infix order sequence of a binary tree is ABCDEFG, and its preorder sequence is EACBDGF. Please write down its postorder sequence. (No blank space or comma in your answer. For example ABCDEFG is a valid format.)
A、
18、【填空题】对于键值序列{38,64,52,26,73,40,48,55,15,12}，用筛选法建最小值堆，共交换元素多少次？For the key value sequence {38,64,52,26,73,40,48,55,15,12}, use the bottom-up heapification method to construct a minimum heap. How many times should we exchange the elements in the array
A、
19、【填空题】以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树，其带权路径长度为？Construct a Huffman tree with the weights {4，5，6，7，10，12，18}. What is the weighted external path length?
A、
20、【填空题】从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{15, 82, 10, 4, 55, 89, 29, 45, 54, 35, 25}构造出一颗二叉搜索树，对该二叉搜索树按照后序遍历得到的序列为（每两个元素之间用一个空格隔开）Given a null binary tree, insert key values {15, 82, 10, 4, 55, 89, 29, 45, 54, 35, 25} successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. Please write down the sequence of post order of this binary search tree. (There is one blank space between two elements)
A、
21、【填空题】对于以下等价类，采用“加权合并规则”（也 称“重量权衡合并规则”），进行并查运算，给出最后父结点索引序列。1-2 5-1 1-6 0-3 7-4 6-9 5-3 0-8 4–8注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根结点的索引是它本身；数字之间用一个空格隔开Given the following equivalence pairs, please use the union-by-weight rule and the UNION/FIND algorithm to obtain the final parent node index sequence.1-2 5-1 1-6 0-3 7-4 6-9 5-3 0-8 4-8Notice: When we merge two trees with the same size, we let the root of the second tree point to the root of the first tree. The parent index of the root node is itself. Separate the numbers with only one space.
A、
22、【填空题】根据伪满二叉树的前序序列，求ltag-rlink的二叉树前序遍历比如：给出伪满二叉树的前序序列如下：A' B' D G' / H C' E' F I /则可以求出ltag-rlink的二叉树前序遍历为0A5 0B3 1D-1 1G4 1H-1 0C-1 0E8 1F-1 1I-1(注：各个结点按照“ltag结点名rlink”的方式给出，结点之间用一个空格分隔）现给出伪满二叉树的前序序列如下：A' B' C' / I H D' E' G / F则所求出ltag-rlink的二叉树前序遍历为According to the pre-order traversal sequence of a pseudo full binary tree, please write down the pre-order traversal sequence of this binary tree in an ltag-rlink form.For example: Given the pre-order traversal sequence of a pseudo full binary tree like this: A' B' D G' / H C' E' F I /Then we can get the pre-order traversal sequence of this binary tree in the ltag-rlink form: 0A5 0B3 1D-1 1G4 1H-1 0C-1 0E8 1F-1 1I-1(P.S. The form of each node should be LtagNodeRlink, and all the nodes are separated by a single space.)Now, given the pre-order traversal sequence of a pseudo full binary tree like A' B' C' / I H D' E' G / F, please write down the pre-order traversal sequence of this binary tree in the ltag-rlink form.
A、
23、【填空题】请使用Kruskal算法求出下图的最小生成树，依次写出每次被选择的合法的合并代价最小的边的编号，用一个空格分隔（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b（ab）之间的边编号为ab，例如图中权值为1的边编号为45。Please use Kruskal algorithm for the following graph to find the minimum spanning tree. Write down the edge labels which are selected in the minimum spanning tree one by one (if there are multiple valid edges, select the vertex with the minimum label). The label of an edge connecting vertex a and vertex b is ab (ab). For example, the edge with a weight of 1 in the graph is labeled 45. (Separate different labels with a single blank space.)<img src="http://edu-image.nosdn.127.net/994B7E55D931B70F07DF7E7F9AF59D71.png?imageView height: 269px;" />
A、
24、【填空题】求图的中心点。设V是有向图G的一个顶点， V的偏心度定义为：Find the central point of the graph. Let V be a vertex of the graph G, the definition of the eccentricity of V is:max{dist(w,v),∀w∈V(G)}如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。If the eccentricity of v is minimal in the graph G, then we call V a central point of G.请从以下代码语句中选择正确的5条，填入空白处。按空白的标号顺序依次列出代码语句的标号,用一个空格分隔。如A F D H CPlease choose 5 statements from the following, and put them into the blanks.List the number of the statement you choose according to the order of the blanks, and separate them with a single blank space. For instance, A F D H C.C++代码：void FLOYD_PXD(AdjMatrix g){ // 对以带权邻接矩阵表示的有向图g，求其中心点。
AdjMatrix w = g;
for(k = 1; k = n; k++)
for(i = 1; i = n; i++)
for(j = 1; j = n; j++)
if( (1) )
(2) ;
v = 1;
dist = MAXINT;
for(j = 1; j = n; j++){
s = 0;
for(i = 1; i = n; i++)
if( (3) )
s = w[i][j];
if( (4) ){
dist = s;
(5) ;
}
} //for
printf(有向图g的中心点是顶点%d,偏心度%d\n, v, dist);
}Python代码：def FLOYD_PXD(AdjMatrix g):
AdjMatrix w = g
for k in range(1, n+1):
for i in range(1, n+1):
for j in range (1, n+1):
if ( (1) )
(2)
v = 1
dist = MAXINT
for j in range(1, n+1):
s = 0
for i in range(1, n+1):
if ( (3) ):
s = w[i][j]
if ( (4) )
dist = s
(5)
print(有向图g的中心点是 + str(v) + ,顶点偏心度 + str(dist))选项：<img src="http://edu-image.nosdn.127.net/C634B90C54B62C5F6DFEA768558CD01E.png?imageView&thumbnail=890x0&quality=100" />
A、
微信扫码添加好友
如二维码无法识别，可拨打 13662661040 咨询。
