从MOOC直接爬的
2 概论
1、(1分)关于算法特性描述正确的有：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.
解析
算法保证计算结果的正确性。指令必须有限算法具有确定性算法不能含有死循环，必须在有限步骤内结束
答案：A,D
2、(1分)以下哪种结构是逻辑结构，而与存储和运算无关：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)
解析
队列：可以是顺序或链式存储，是逻辑结构双链表：链式存储数组：按索引值从小到大存放在一片相邻的连续区域，定义了存储结构顺序表：按索引值从小到大存放在一片相邻的连续区域，定义了存储结构
答案：A
3、(1分)计算运行下列程序段后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的值
解析
答案：20
4、(1分)下列说法正确的是：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,logan是O(logbn)，但logbn不一定是O(logan)【if a>b>1,logan is O(logbn)， logbn may not be O(logan)】
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))】
解析
(1) 根据O()定义可知.(2) 如果f(n)是O(g(n))，g(n)是O(h(n)), 则f(n)是O(h(n)),所以f(n)+g(n)是O(h(n))(3)logan=log(n)/log(a),logbn=log(n)/log(b),所以前者与后者只差了一个常数项，所以logbn一定是O(logan)(4)当f(n)=n,g(n)=n*2, 无论a多大，g(n)都不可能是O(af(n)).
答案：A,B
5、(1分)已知一个数组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;i<n-1;i++){
for (j = i+1;j<n && a[j-1]<=a[j];j++)
if(length<j-i+1)
length=j-i+1;}
图片
A、 如图，A选项
B、 如图，B选项
C、 如图，C选项
D、 如图，D选项
解析
本代码实际上是求a中有序子数组中最长的长度。譬如，在[1, 8, 1, 2, 5, 0, 11, 9]中，最长的是[1, 2, 5]，长度为3 。其时间复杂度与a中元素的实际取值状态相关。 1)若a的所有元素是按照降序方式排列。则外层循环n-1次，每次内层只执行一次，整个开销为θ(n) 2)若a的所有元素是按照升序方式排列。则外层循环n-1次，每次内层需要执行n-i-1次，整个开销为θ(n^2) 所以，一般来说，时间复杂度是Ω(n)的，也是O(n^2)
答案：A,B
3 线性表
1、(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.
解析
顺序存储是按索引值从小到大存放在一片相邻的连续区域采用链接存储，便于插入和删除操作，如果采用顺序存储，插入和删除时需要大量移动元素，参考数组的元素删除线性表采用链接存储，在结点中存储link信息，不需占用连续存储单元采用链接存储，便于插入和删除操作
答案：A,C,D
2、(1分)下面的叙述中正确的是：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 insert 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.
解析
线性表在链式存储时，查找第i个元素的时间与i的数值无关。因为存储空间是不连续的，需要从头或者尾结点开始查找元素，i越大，时间越长，时间不可能与i无关线性表在顺序存储时，查找第i个元素的时间与i的数值成正比。因为存储空间是连续的，直接由i可以得到元素位置线性表在顺序存储时，查找第i个元素的时间与i的数值无关。因为存储空间是连续的，直接由i可以得到元素位置线性表在链式存储时，插入第i个元素的时间与i的数值成正比。因为存储空间是不连续的，插入第i个元素不需要移动其他元素。但是在插入之前从头搜索到第i个元素的指针，所以插入时间跟i相关
答案：C,D
3、(1分)对于一个具有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. )
答案：(1)(n)
4、(1分)带头结点head的循环链表的尾结点tail的特点是:
_（提示： 1.请使用“=” 2.系统基于字符匹配来判定
答案，所以您的
答案中不要出现空格）The circular linked list with a head node, its tail node’s character is: _.(Hint:1. Please use “=” 2.This problem is judged by string matching, Please make sure your answer don’t contain any blanks. )
解析
答案：tail->next=head
5、(1分)完成在双循环链表结点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;
解析
p->next->prev=s; s->prev=p; s->next=p->next; p->next=s;最后更改p->next是正确的，否则会造成原来的p结点后来的next信息丢失p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;先更改会造成原来的p结点后来的next信息丢失s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;先更改p->next成s再更改p->next->prev，会造成原来的p结点后来的next信息丢失s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;最后更改p->next是正确的，否则会造成原来的p结点后来的next信息丢失
答案：A,D
4 栈与队列
1、(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、 5
解析
队列的特点是先进先出，因此出队的顺序就是入队的顺序，也就是出栈的顺序。因此，可以得到栈的状态变化：栈顶<-空 (初始状态)栈顶<-e1 (e1入栈)栈顶<-e2|e1 (e2入栈)栈顶<-e1 (e2出栈)栈顶<-e3|e1 (e3入栈)栈顶<-e4|e3|e1 (e4入栈)栈顶<-e3|e1 (e4出栈)栈顶<-e1 (e3出栈)栈顶<-e5|e1 (e5入栈)栈顶<-e6|e5|e1 (e6入栈)栈顶<-e5|e1 (e6出栈)栈顶<-e1 (e5出栈)栈顶<-空 (e1出栈)可以看到，栈的容量至少为3。
答案：B
2、(1分)双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有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 >
答案：8
3、(1分)编号为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.
答案：14
4、(1分)现有中缀表达式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
解析
题中中缀表达式用二叉树表示如图：Infix expression is represented by binary tree as the following diagram:图片
答案：C
5、(1分)以下循环队列的实现方式中，长度为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.
解析
只用front和rear两个指针标记队列的头和尾，无法区分空队列和满队列两种状态，所以只能容纳n-1个元素。而增加len或empty都可以区分这两种状态，因此可以容纳n个元素
答案：B,C
5 字符串
1、(1分)若字符串s=“software”，则其子串个数为： If the string s = “software”, then the number of its sub-string is:
答案：37
2、(1分)设有字符串变量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()
答案：MYOLDMULE E 0
3、(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
解析
A.求子串：求子串是给定首字符在原字符串中位置和子串长度，输出子串的运算
Seeking substring is operation that outputs substring, given that first character’s location of substring’s characters in string and the substring’s lengthB.联接：是把两个字符串连接到一起输出新字符串的运算
Concatenation is the algorithm to connect the two strings together to output a new string.C.匹配：是求子串在父串中位置的运算
Matching is the algorithm to seek the substring’s location in the original string.D.求串长：求字符串的长度 Seeking string’s length
答案：C
4、(1分)下列程序判断字符串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;图片注：(1)和(2)和(3)三个
答案之间用空格分隔，每个
答案是一个字符,不要加空格
解析
答案：j i j
5、(1分)Seek the string “BAAABBBAA” ‘s feature vector, where the feature vector is defined as follows:（There is only one correct answer）图片
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}
答案：B
6 二叉树
1、(1分)一棵有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)
解析
答案：9
2、(1分)请写出下面这棵二叉树的中序遍历（字母和字母之间不要有空格） Please write down the infix order sequence of the following binary tree. (There is no blank space between letters)图片
解析
答案：LXMECKPBQHDA
3、(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.
解析
A.非空满二叉树只有度为0或者度为2两种结点，而这两种结点的个数差为1，所以加起来必为奇数。There are only 2 kinds of nodes, which are
with degree 0 or degree 2, in a binary tree with at least one node. And the difference of the amounts of these two kinds of nodes is 1, so their sum must be odd.
B.非完全二叉树无法知道每一层哪些位置缺了结点，不能像完全二叉树那样直接计算出两个儿子的编号，所以不能用顺序存储结构存储。Since we don’t know which locations are lack of nodes on each layer for an incomplete binary tree, we couldn’t calculate the indexes of the two children directly. So sequential storing structure can’t be used.
C.只要倒数第二层的度都为0或者2，此棵完全二叉树即为满二叉树，最下面一层不一定要全满。If the degrees of nodes on the second layer in inverted order are 0 or 2, the complete binary tree is a full binary tree, so the nethermost layer doesn’t need to be full.D.倒数第二层也可以有度数为0的结点。The degrees of nodes on the second layer in inverted order could also be 0.E.设度为0,1和2的结点数为，和，那么为空的外部结点数目等于2+=+++1，于是等于节点数加1。F.结点度数还可以为0。The degrees could also be 0.
答案：A,C,E
4、(1分)已知一棵树的前序遍历为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)
解析
答案：DGEBFCA
5、(1分)下列关于二叉树遍历的说法正确的有: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.
解析
A.前序为中左右，而中序为左中右，所有结点都没有左子树后，两者恰好一样。所以所有结点左子树为空的二叉树也满足要求。Preorder is middle, left, then right, while infix order is left, middle, then right. These two are the same when all nodes don’t have left child tree. So a binary tree with all nodes without left child tree also meets the condition. B.前序为中左右，而中序为左中右，所有结点都没有左子树后，两者恰好一样。Preorder is middle, left, then right, while infix order is left, middle, then right. If all nodes don’t have left child tree, they are the same.C.前序为中左右，而中序为左中右，所有结点都没有左子树后，两者恰好一样。所以所有结点左子树为空的二叉树才满足要求。Preorder is middle, left, then right, while infix order is left, middle, then right. These two are the same when all nodes don’t have left child tree. So a binary tree with all nodes without left child tree meets the condition.
D.前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能让两者一样。Preorder is middle, left, then right, while post order is left, right, then middle. So lack of left child tree or right child tree couldn’t make them the same.
E.前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能让两者一样。Preorder is middle, left, then right, while post order is left, right, then middle. So lack of left child tree or right child tree couldn’t make them.F.前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能让两者一样。Preorder is middle, left, then right, while post order is left, right, then middle. So lack of left child tree or right child tree couldn’t make them the same.G.中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。所以所有结点右子树为空的二叉树也满足要求。Infix order is left, middle, then right, while post order is left, right, then middle. These two are the same when all nodes don’t have right child tree. So a binary tree with all nodes without right child tree also meets the condition.H.中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。所以所有结点右子树为空的二叉树才满足要求。Infix order is left, middle, then right, while post order is left, right, then middle. These two are the same when all nodes don’t have right child tree. So a binary tree with all nodes without right child tree meets the condition.I.中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。Preorder is middle, left, then right, while infix order is left, middle, then right. If all nodes don’t have left child tree, they are the same.J.只有一个根结点的二叉树满足要求。A binary tree with only one node meets the condition.
答案：B,D,I,J
7 二叉树
1、(1分)对于如下图所示的最大堆，删除掉最大的元素后，堆的后序遍历结果是For the following maximum heap, after deleting the maximum element, the post order traversal sequence is图片
解析
答案：12 23 24 28 5 37 43 48 3 57 59
2、(1分)请阅读下面一段代码Please read the following code
图片若此段代码的作用是用来进行后序遍历，那么应该在几号访问点进行访问？（只需要填写数字）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)图片
解析
答案：3
3、(1分)从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{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)
解析
答案：18 10 5 73 68 27 25 41 32 51 99
4、(1分)题目如下
解析
答案：6
5、(1分)对于给定的一组权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.
解析
答案：705
8 🌲
1、(1分)一个深度为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、 k^(h-1)
B、 k^h
C、 (k^(h+1)-1)/(k-1)
D、 (k^h-1)/(k-1)
解析
层数—节点数number of levels—number of nodes图片
答案：C
2、(1分)根据树的双标记层次遍历序列，求其带度数的后根遍历序列
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:图片
解析
答案：G0 B1 H0 D1 C1 E0 I0 F1 A4
3、(1分)若一个具有N个顶点，K条边的无向图是一个森林（N>K且2K>=N），则该森林有多少棵树？ There is an undirected graph. It has N nodes and K edges. (N>K and 2K>=N). If it is a forest, then how many trees will it has?
解析
答案：N-K
4、(1分)设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
解析
B的根是T1的根，右子树是从森林F’＝{T2，T3}转换而成的二叉树。换句话，B右子数的结点数=T2结点数+T3结点数=n2+n3B’s root node is T1’s root node, and B’s right sub-tree is a binary tree, corresponding to the forest F’={T2, T3}. So, the number of nodes of B’s right sub-tree equals to the sum of nodes of T2 and T3, namely, n2+n3.
答案：D
5、(1分)对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父节点索引序列。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.
解析
答案：4 4 6 4 4 3 4 4 4 4
9 图
1、(1分)下面关于图的说法正确的有 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.
解析
A.所有结点的出度之和等于入度之和，但是每个结点并没有出度和入度相等的性质。The sum of in-degrees of all nodes is equal to the sum of out-degrees of all nodes. But for each node, it doesn’t work.B.给两个结点新增一条边相连，能够形成一个连通图，但是不管怎么给边定向都不能使其成为强连通图。Add an edge of two vertex, then we can get a connected graph. But we can’t make it strongly connected graph however we direct the edges.C.只有一个结点构成的有向图，所有结点入度之和为0。In the case of the graph consist of only one vertex, the sum of in-degrees of all nodes is 0.D.结点度数是边数的2倍，故一定为偶数。The sum of degrees of vertices is equal to the amount of edge times 2, so it must be even numberE.原来强连通分量中的点必须能够互达，边全部反向后，仍然能够互达。而原来强连通分量外的点和强连通分量内的点之间的边没有变化，以前不能互达现在还是不能，这样保证了仍然是极大的强连通子图。In the original strongly connected component, every pair of vertices in the subgraph is connected by a path.After reversion, this property doesn’t change. And the connectivity of the vertices outside of the subgraph and vertices in the subgraph don’t change too. So we can guarantee it still be the
答案：D,E
2、(1分)在一个无向图中，所有顶点的度数之和等于所有边数的(
)倍。In a undirected graph, the sum of degrees of all vertices is equal to the amount of all edges times ().
解析
答案：2
3、(1分)有向图G如下图所示，请写出所有拓扑排序序列。所有的顶点都直接用其数字标号表示，如拓扑排序序列为图片，那么请写成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.图片
解析
答案：1234 1324 2134
4、(1分)下列关于最短路算法的说法正确的有：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.
解析
A.即使是只有负权边，也会导致以前已经被选出来更新其它结点最短路值的结点的最短路值被更新，造成错误。Even if there is only the edge of negative weight, it would result in that the shortest path of the node which be selected previously to update the shortest path of the other vertices changes, then cause errors.B.可以执行多次Dijkstra算法实现这一要求。We can perform Dijkstra algorithm repeatedly to satisfy this requirement.
C.Dijkstra算法无法处理图中存在任何负权边的情况。Dijkstra algorithm can’t handle the situation that graph contains any edge of negative weight.D.可以执行多次Dijkstra算法实现这一要求。We can perform Dijkstra algorithm repeatedly to satisfy this requirement.
答案：A,B
5、(1分)题图为一无向图,分别写出从顶点1出发,按深度优先搜索遍历算法得到的顶点序列,和按广度优先搜索遍历算法得到的顶点序列图片
解析
答案：123456 123564