注：本套试卷由强连通计算机考研完成解析，但难免有疏漏，如果发现错误请及时与我们反馈。 勘误：对微信公众号“强连通计算机考研”回复“重邮802勘误”。
2021年答案 一、 选择题（本大题共 15小题，每小题 2分，共 30分）
二、填空题（本大题共10小题，每小题3分，共30分）
三、综合应用题（本大题共7小题，共60分） 
1、设 N是描述问题规模的非负整数，下列程序段的时间复杂度是( )。
static int fun(int N) {if (N == 1) return 0;return 1 + fun(N/2);}AO(logN)O(logN)O(logN) B.O(N)O(N)O(N) C.O(NlogN)O(NlogN)O(NlogN) D.O(N 2 )O(N^2)O(N2)
2、一些随机产生的数采用线性链表存储，在下面这些排序方法中，( )的时间复杂度是最小的。 A．插入排序 B. 快速排序 C. 堆排序 D. 归并排序
3、一个栈的输入序列为 a b c d e，则下列序列中不可能是栈的输出序列的是（ ）。 A.b c d a e B.e d a c b C.b c a d e D.a e d c b
4、实现一个队列需要（ ）个栈。 A.1 B. 2 C. 3 D. 4
5、下面（ ）是一颗满二叉树的结点个数。 A. 8 B. 13 C. 14 D. 15
6、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右的结点 D.X的左子树中最右的结点
7、下列序列中，哪一个是堆（ ）？ A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15 C.75,45,65,30,15,25,20,15 D.75,45,65,10,25,30,20,15
8、一棵Huffman树共有203个结点，对其Huffman编码，共能得到（）个不同的码字。 A.100 B.102 C.200 D.203
9、下面说法错误的是（）。 A.一个有n个顶点和n条边的无向图一定是有环的。 B.建立十字链表的时间复杂度和建立邻接表是相同的。 C.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 D.在某些图的应用问题中，如果需要找到表示同一条边的两个结点，那么采用邻接多重表比邻接表作为储存结构更为适宜。
10、图的广度优先遍历算法中使用队列作为其辅助数据结构，那么在算法执行过程中每个顶点进队次数最多为（）。 A.1 B.2 C.3 D.4
11、设一个有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，E={,,,,,}不属于该图的拓扑排序有序序列是（ ）。 A.v1,v2,v3,v4,v5,v6 B.v1,v4,v2,v3,v5,v6 C.v4,v5,v1,v2,v3,v6 D.v4,v1,v2,v3,v5,v6
12、判断一个有向图是否存在回路，除可利用拓扑排序方法外，还可以用（）。 A.求关键路径的方法 B.求最短路径的方法 C.广度优先遍历的方法 D.深度优先遍历的方法
13、设有一个二叉排序树（二叉查找树），其结点上存储有数字1到100。现在需要查找数字55，下面（ ）序列不可能是查找过程中访问过的结点序列。 A.{10,75,64,43,60,57,55} B.{90,12,68,34,62,45,55} C.{9,85,47,68,43,57,55} D.{79,14,72,56,16,53,55}
14、在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做（ ）次关键码比较。 A.2 B.3 C.5 D.4
15、一颗3阶B-树中有2047个关键字，包括叶结点层，该树的最大深度为（）。 A.11 B.12 C.13 D.14
二、填空题（本大题共10小题，每小题3分，共30分）16、一颗深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。 17、Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below. 
The maximum possible number of iterations of the while loop in the algorithm is（ ）。 18、对于模式串“aabaac”给出其next数组（ ）。 19、现有按中序遍历二叉树的结果为abc，有（ ）种不同形态的二叉树可以得到这一遍历结果。 20、设一棵二叉树有20个叶子结点，则在该树中有2个孩子的结点个数为（ ）。 21、设G是一个非连通无向图，有10条边，则该图的顶点数至少有（ ）个。 22、顺序查找3个元素的顺序表，若查找第1、第2和第3个元素的查找概率分布是1/2、1/3和1/6，则查找任一元素的平均查找长度为（）。 23、散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。（请在最大概率、最小概率、平均概率、同等概率这些术语中选择正确的进行填空） 24、假设某算法在输入规模为n时的计算时间为T(n)=n 2 n^2n2。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台计算机的64倍，那么在这台计算机上用同一算法在t秒内能解输入规模（）的问题。 25、表达式 a × b - c - d $ e $ f - g - h × i中，运算符的优先级由高到低依次为－， ×，$，均右结合，则相应的后缀式是（ ）。
26、假设称正读和反读都相同的字符序列为“回文"，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。下面代码判别读入的一个以‘@’为结束符的字符序列是否是“回文”。请给出缺失的5行代码。
Status SymmetryString(char* p){Queue q;if(!InitQueue(q)) return 0;Stack s;InitStack(s);ElemType e1, e2;while((1)) {Push(s, *p);EnQueue(q, *p);(2)}while(!StackEmpty(s)) {(3)(4)if((5)) return FALSE;}return OK;}27、(5分）阅读下面代码：
int count = 0;int N = a.length;sort(a);for (int i = 0; i