网站首页人卫慕课习题 正文

第一章 概论

第一章 概论 测验

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,是，但不一定是【if a>b>1, is ， may not be 】
    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))】

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;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、
    B、
    C、
    D、

6、计算运行下列程序段后m的值： Calculate the value of m after running the following program segment n = 9; m = 0; for (i=1;i<=n;i++) for (j = 2*i; j<=n; j++) m=m+1; 求m的值

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. ）

编程作业

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.

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. )

5、带头结点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. )

第二章 线性表编程作业

1、字符串插入

2、约瑟夫问题

第二章 线性表编程作业

1、字符串插入

2、约瑟夫问题

第三章 栈与队列

第三章 栈与队列测验

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、队列的特点包括： 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)

3、以下循环队列的实现方式中，长度为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.

4、编号为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.

5、双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有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.

栈与队列编程作业

1、中缀表达式求值

2、HTML

第五章 二叉树

编程作业

1、由中根序列和后根序列重建二叉树

2、表达式·表达式树·表达式求值

第六章 树

第六章 树测验

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、
    B、
    C、
    D、

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、
    B、
    C、
    D、

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.)

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.)

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，其他题目同样如此；同一个小题的答案如果有多个字母，按照字典序排列，且不要以空格分隔，不同小题用一个空格隔开）

10、若一个具有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?

11、将下图的二叉树转换为对应的森林，按照先根次序列出其结点。（答案的字母之间没有空格） Transform this binary tree into the corresponding forest, and write down the pre-order node sequence. (Do not add spaces in your answer.)

12、将下图的二叉树转换为对应的森林，按照后根次序列出其结点。（答案的字母之间没有空格） Transform this binary tree into the corresponding forest, and write down the post-order node sequence. (Do not add spaces in your answer.)

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)

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)

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:

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:

17、根据树的双标记层次遍历序列，求其带度数的后根遍历序列 Given the double-tagging level-order traversal sequence of a tree, please write down the post-order traversal sequence with degree.

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.

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.

第七章 图

第七章 图测验

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的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。 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中有一条从到的路径 There is a path from Vj to Vi in the G.
    B、G中有边(，) G contains edge (Vi,Vj).
    C、G中有一条从到的路径 G contains a path from Vi to Vj.
    D、G中没有边(，) 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?

7、如果无向图G=(V,E)是简单图，并且|V|=n>0，那么图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）

8、有向图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.

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.

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).

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).

12、题图为一无向图,分别写出从顶点1出发,按深度优先搜索遍历算法得到的顶点序列,和按广度优先搜索遍历算法得到的顶点序列

编程作业

1、兔子与星空

期末考试

2019-2020学年度春季学期数据结构与算法设计考试题

1、以下哪种逻辑结构描述了数据元素之间多对多的关系_______。
    A、线性结构
    B、树形结构
    C、图形结构
    D、集合结构

2、下面程序段的时间复杂度是_______。 for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;
    A、O(n*m)
    B、O(n)
    C、O(m)
    D、O(n+m)

3、下面程序段的时间复杂度是_______。 i=s=0; while(s<n) { i++; s+=i; }
    A、O(n)
    B、O(s)
    C、O(sqrt(n)) 其中：sqrt(n)表示对n开方
    D、O(n^2) 其中：n^2表示求n的平方

4、已知数据 3, 4, -2, 0, 8 存储在顺序存储结构中，编程实现删除x的操作为_______。 （其中：数据从顺序存储结构的第0个位置开始存储）
    A、void del(SqList L, elemtype x) { int i=0, bfind=0; while(i<L.length-1) { if(bfind==0 && x==L.data[i]) bfind=1; if(bfind){L.data[i]=L.data[i+1];} i++; } }
    B、void del(SqList L,elemtype x) { int i=0; while(i<L.length) { if(x==L.data[i])L.data[i]=0; i++; } }
    C、void del(SqList L, elemtype x) { int i=0; while(i<L.length) { if(x==L.data[i])L.data[i]=-1; i++; } }
    D、void del(SqList L, elemtype x) { int i=L.length; while(i>0 ) { if(x!=L.data[i])L.data[i-1]=L.data[i]; i--; } }

5、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是_______。
    A、rear+1==front
    B、(front+1)%m==rear
    C、front==rear
    D、(rear+1)%m==front

6、中缀表达式 (a+b)/c-(d^2+3)*e的后缀表达式是_______。
    A、ab+c/3d2^+e*-
    B、ab+c/d2^3+e*-
    C、abc+/d2^3+e*-
    D、ab+c/ed2^3+*-

7、一个高度为9的满二叉树上共有______个分支结点。
    A、254
    B、255
    C、256
    D、257

8、已知一棵二叉树结点的先序遍历序列为：F,B,E,D,A,C, 中序遍历序列为 F,E,D,B,A,C, 则结点E的右孩子为 _______。
    A、A
    B、D
    C、C
    D、F

9、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序 _______。
    A、都不相同
    B、完全相同
    C、先序和中序相同，而与后序不同
    D、中序和后序相同，而与先序不同

10、如果一颗二叉树具有10个度为2 的结点和5个度为1的结点，则有 _______个叶子结点。
    A、9
    B、11
    C、15
    D、14

11、假设完全二叉树的树根为第1层，树中第10层有5个叶子结点，则完全二叉树最多有 _______个结点。
    A、2047
    B、2048
    C、2037
    D、2038

12、给定权值总数有n个，其哈夫曼树的结点总数是 _______。
    A、不确定
    B、2n
    C、2n+1
    D、2n-1

13、已知一个有序森林描述如下图所示，它的中序遍历序列为________。
    A、DGBFHECA
    B、DBGFHCEA
    C、DBGFHECA
    D、DGBFHCEA

14、设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为_______。
    A、5，3，4，6，1，2
    B、3，2，5，6，4，1
    C、3，1，2，5，4，6
    D、1，5，4，6，2，3

15、一个有n个顶点的无向图，包含2个连通分量，则它至少有______条边。
    A、n-1
    B、n
    C、n-2
    D、n+1

16、不是下图的深度优先遍历序列的是___________。
    A、A,B,C,E,F,D,J,H,I,G,K,O,L,M,N
    B、A,B,C,E,J,H,I,G,K,D,F,O,M,N,L
    C、A,B,C,E,D,K,G,I,H,J,F,O,M,N,
    D、A,B,C,E,F,D,K,G,I,H,J,L,M,N,O

17、数据的关系有逻辑关系和存储关系。其中逻辑关系是进行算法分析和设计需要考虑与使用的，而存储关系是编程实现的时候需要考虑的，逻辑关系和存储关系之间并没有关系。

18、算法和程序都不能无穷的，否则会进入死循环。

19、算法可以用不同的语言描述，比如C或者java，所以算法实际上就是程序。

20、下面的递归函数时间复杂度是O(1) int fact(int n) { if(n<=1)return 1; else return n*fact(n-1); }

21、顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。

22、线性表中的数据元素有一个前驱多个后继。

23、数组data[30]作为循环队列SQ的存储空间,front指向队头，则data[(front+1)%30]为队头元素。

24、空串与空格串是相同的。

25、循环队列是采用循环链表来实现的。

26、二叉排序树的中序遍历结果是一个关键字的递增有序序列。

27、无向图由n个连通分量组成，则需要执行n次宽度优先遍历才能遍历完所有顶点。

28、无向图由n个连通分量组成，则需要执行n次宽度优先遍历（广度优先遍历）才能遍历完所有顶点。

29、一棵完全二叉树具有100个结点，则该树高度为6。

30、假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。 // 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C){ LinkList pa,pb,qa,qb; pa=A; pb=B; qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; A->next=NULL; C=A; while(pa&&pb){ if(pa->data<pb->data){ qa=pa; pa=pa->next; qa->next=A->next; A->next=qa; } else{ qb=pb; pb=pb->next; // <----- 将当前最小结点插入A表表头 A->next=qb; } } while(pa){ qa=pa; pa=pa->next; qa->next=A->next; A->next=qa; } while(pb){ qb=pb; pb=pb->next; qb->next=A->next; A->next=qb; } pb=B; free(pb); return OK; } (答案不要有空格，注意字母大小写)

31、假设称正度和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。 Status SymmetryString(char* p){ Queue q; if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(*p){ Push(s,*p); ; //<-----补全程序 p++; } while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK; } (答案不要有空格，注意字母大小写)

32、对一个高度为8的二叉搜索树进行先序遍历，得到的遍历序列恰好是按照关键字从小到大的次序排列，则该二叉搜索树所包含的关键字数量为______。

33、含有10个顶点的有向完全图，具有_______条边。

34、假设一棵含有19个结点的完全二叉树中，按层次从上到下、每层结点从左到右的顺序，从0开始编号，则编号为7的结点的左孩子编号为_______（如果孩子不存在，则填写NULL）。

35、一棵二叉树中，若叶结点的个数为11，度为1的结点个数为18，度为2的结点的个数为_______。

36、如果一颗二叉树具有10个度为2 的结点和5个度为1的结点，则有_______个叶子结点。

37、Status ExchangeBiTree(BiTree& T) { BiTree p; if(T != NULL){ p=T->lchild; T->lchild=T->rchild; T->rchild=p; ___________; ExchangeBiTree(T->rchild); } return OK; } (答案不要有空格，注意字母大小写)

38、一个有n个顶点的有向图(n>1)，至少要存在______条边，才能成为强连通图。

39、已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，对字母进行哈夫曼编码，得到的哈夫曼树的WPL值为_________。（其中：要求对应的哈夫曼树上任意结点的左孩子权值不大于右孩子权值)

40、设串的长度为n，则它的子串个数为_________。（答案不要有空格）

41、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为m1，m2和m3。与森林F对应的二叉树根结 点的右子树上的结点个数是_________。(答案不要有空格，注意大小写字母)

42、一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有_________个结点。(答案中不要有空格)