一、单项选择题（共 20 题，每题 1 分，共 20 分）
1. 堆排序中使用的堆逻辑结构上属于 ( )
选项：
A. 完全二叉树
B. 顺序表
C. 满二叉树
D. 链表
答案： A
解析： 堆在逻辑上是一棵完全二叉树，但在物理存储上通常使用数组（顺序表）实现。
2. 对一个单链表，不借助外部指针的情况下，在表尾插入一个新结点的时间代价为 ( )
选项：
A. Θ(nlogn)
B. Θ(n)
C. Θ(n²)
D. Θ(1)
答案： B
解析： 单链表不保存尾指针时，需要从头遍历到尾部才能插入，时间复杂度为 O (n)。
3. 一个栈的入栈序列是 a,b,c,d,e，则不可能的输出序列是 ( )
选项：
A. a,b,e,c,d
B. e,d,c,b,a
C. d,e,c,b,a
D. c,d,e,b,a
答案： A
解析： 对于序列 a,b,e,c,d：入栈 a→出栈 a→入栈 b→出栈 b→入栈 c→入栈 d→入栈 e→出栈 e，此时栈顶是 d，不能直接出栈 c。
4. 外部查找算法的主要目标应为 ( )
选项：
A. 减少存储空间占用
B. 减少比较次数
C. 减少磁盘访问次数
D. 减少数据移动次数
答案： C
解析： 外部查找主要考虑磁盘 I/O 次数，因为磁盘访问比内存访问慢得多。
5. 一般情况下，当线性表的元素数目 ( )，最好使用链表实现
选项：
A. 较小
B. 变化较小
C. 较大
D. 变化较大
答案： D
解析： 链表适合频繁插入删除的场景，即元素数目变化较大时。
6. 从不带头结点，栈顶指针为 top 的链栈中进行出栈操作，并用 x 保存被删除结点的值，则执行 ( )
选项：
A. x = top->next->val; top = top->next
B. top = top->next; x = top->val
C. x = top->val; top = top->next
D. x = top->val; top->next=top->next->next
答案： C
解析： 先保存栈顶值，再移动栈顶指针到下一个结点。
7. 对任何一棵二叉树 T，如果其叶结点的个数为 400，度为 2 的结点个数为 ( )
选项：
A. 396
B. 399
C. 401
D. 200
答案： B
解析： 二叉树性质：n₀ = n₂ + 1，所以 n₂ = n₀ – 1 = 400 – 1 = 399。
8. 对结点数量一定的二叉树，高度最小的应为 ( )
选项：
A. 完全二叉树
B. 哈夫曼树
C. 二叉查找树
D. 平衡二叉树
答案： A
解析： 完全二叉树是所有形态中高度最小的二叉树，高度为⌊log₂n⌋+1。
9. 设树的度为 4，其中度为 1、2、3、4 的结点数分别为 40、30、20、10 个，则该树共有 ( ) 个叶子结点
选项：
A. 100
B. 200
C. 101
D. 无法确定
答案： C
解析： 树中结点总数 n = n₀ + n₁ + n₂ + n₃ + n₄
边数 e = n – 1 = n₁ + 2n₂ + 3n₃ + 4n₄
代入：n₀ + 40 + 30 + 20 + 10 – 1 = 40 + 60 + 60 + 40
n₀ + 99 = 200，n₀ = 101
10. 求下面题图的最小生成树时，可能是克鲁斯卡 (Kruskal) 算法第二次选中但不是普里姆 (Prim) 算法 (从 v₄开始) 第 2 次选中的边是 ( )
选项：
A. (v₂, v₃)
B. (v₃, v₄)
C. (v₁, v₂)
D. (v₁, v₃)
答案： C
解析： Kruskal 按边权排序选择，Prim 从起点逐步扩展。需要原图信息才能确定，但通常 (v₁, v₂) 可能权重较小但不在 v₄的邻接范围内。
11. 以下数据结构中，属于线性数据结构的有_____
选项：
A. 平衡二叉树
B. B 树
C. 队列
D. 图
答案： C
解析： 队列是典型的线性数据结构，其他都是非线性结构。
12. 对于 n (n≥0) 个元素构成的线性表 L，需要频繁进行插入和删除操作，适合采用以下哪种存储结构_____
选项：
A. 带尾指针的单循环链表
B. 队列
C. 顺序表
D. 顺序栈
答案： A
解析： 链表适合频繁插入删除，带尾指针的单循环链表便于在尾部操作。
13. 设循环队列的元素存放在一维数组 Q [46]，队列非空时，front 指示队头元素，rear 指示队尾元素的后一个位置。如果队列中元素的个数为 35，front 的值是 28，则 rear 的值是_____
选项：
A. 16
B. 17
C. 18
D. 19
答案： C
解析：原题情况
rear 指向队尾元素的后一个位置（即下一个空位），队列长度公式为：n=(rear−front+m)modm
代入 n=35, front=28, m=46：35=(rear−28+46)mod46rear=17
拓展：如果 rear 指向队尾元素本身
队列长度公式变为：n=(rear−front+1+m)modm
代入得：35=(rear−28+1+46)mod46rear=16
总结
定义不同，rear 值差 1。原题按第一种定义，结果 rear=17，对应选项 B。
14. 下列算法的时间复杂度为_____
c
运行
s = 0;
for(i = 1; i < n; i *= 2){
j = 0;
while(j < i){
s = s + j;
j ++;
}
}
选项：
A. O(log₂n)
B. O(nlog₂n)
C. O(n)
D. O(n²)
答案： C
解析： 外层循环 log₂n 次，内层循环次数：1+2+4+…+2^n = 2n-1，所以总时间复杂度 O (n)。
15. 一棵完全二叉树有 134 个结点，其中叶子结点有_____个
选项：
A. 68
B. 67
C. 7
D. 8
答案： B
解析： 完全二叉树中，n₀ = ⌈n/2⌉ = ⌈134/2⌉ = 67。
16. 下列关于 m 阶 B – 树的说法中，错误的是_____
选项：
A. 所有结点中的数据是有序的
B. 所有叶子结点都在同一层次上
C. 所有结点至少有 m/2 棵子树
D. 根结点至多有 m 棵子树
答案： C
解析： B – 树中，除根结点外，其他结点至少有⌈m/2⌉棵子树，根结点至少 2 棵子树（除非是叶子）。
17. 设有一个顺序栈 S，元素 S1、S2、S3、S4、S5、S6 依次进栈，如果 6 个元素出栈的顺序是 S2、S3、S6、S5、S4、S1，则栈的容量至少应该是_____
选项：
A. 5
B. 3
C. 6
D. 4
答案： D
解析： 模拟过程：S1 入、S2 入、S2 出、S3 入、S3 出、S4 入、S5 入、S6 入、S6 出、S5 出、S4 出、S1 出。最大栈深为 4。
18. 树 F 的根结点有三棵子树，其结点个数分别为 N1、N2 和 N3。与该树对应的二叉树根结点的右子树上的结点个数是_____
选项：
A. N2
B. N2+N3
C. N1+N2
D. 0
答案： B
解析： 树转二叉树（左孩子右兄弟）：根的第一棵子树转为左子树，其他子树转为右子树链。所以右子树包含第二、三棵子树的所有结点。
19. 在双循环链表结点 p 之前插入 s 结点的操作是_____
选项：
A. s->prior=p->prior; s->next=p; p->prior=s; p->prior->next=s;
B. p->prior=s; s->prior=p->prior; s->next=p; s->prior->next=s;
C. s->prior=p->prior; s->next=p; s->prior->next=s; p->prior=s;
D. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
答案： C
解析： 标准插入步骤：1. s 连接前后；2. 前驱连接 s；3. 后继连接 s。
20. 下面关于串的的叙述中，正确的是_____
选项：
A. 串只能采用顺序存储
B. 串是由零个或多个字符组成的有限序列
C. 串的操作对象是单个的字符
D. 空串是由空格构成的串
答案： B
解析： 串是字符的有限序列，可以顺序或链式存储，空串是长度为 0 的串。
二、填空题（共 20 题，每题 1 分，共 20 分）
21. 由 3 个结点所构成的二叉树有____________种形态
答案： 5
解析： 卡特兰数 C₃ = (2×3)!/(3!×4!) = 5。
22. 算法的有穷性是指_______________________________
答案： 算法必须在有限步骤内结束
解析： 有穷性是算法的重要特性之一。
23. 对于 n (n≥0) 个元素构成的线性表 L，当需要频繁进行随机查找操作时，适合采用存储结构是_____________________
答案： 顺序表 / 数组
解析： 顺序表支持随机访问，时间复杂度 O (1)。
24. 有一个循环队列存放在一维数组 M [45] 中，队列的头指针（指向最早未出队元素）是 front，尾指针（指向最新入队的元素的下一个位置）是 rear，如果队列中元素的个数为 35，front 的值是 28，则 rear 的值是_________________
答案： 18
解析： rear = (front + 元素个数) % 数组大小 = (28 + 35) % 45 = 63 % 45 = 18。
25. 表达式 a+b*(c+d*e) 的波兰式是
答案： + a * b + c * d e
解析： 波兰式（前缀表达式）的构造。
26. 已知串 S=”abaabaab”，假设串位置（数组下标）从 1 开始，其 next 值为_________________
答案： 0 1 1 2 3 4 5 6
解析： KMP 算法的 next 数组。
27. 给定一个关键字序列 {2,3,8,9,5,4,1}，以第一个数为枢轴，快速排序第一趟的结果为______________________
答案： 1,2,8,9,5,4,3
解析： 以 2 为枢轴，将小于 2 的放左边，大于 2 的放右边。
28. 采用折半查找法，在有序表 {14，19，31，45，56，79，86，99} 中查找元素 14 和 79 时，其查找长度分别为___(1)和(2)___
答案： (1) 3 (2) 2
解析： 查找 14：比较 56、19、14，共 3 次。查找 79：比较 56、86、79，共 3 次？等等：比较 56 (小)→86 (大)→79 (等)，也是 3 次。或者：比较 56 (小)→79 (等)，2 次？需要实际模拟。
29. 在各种查找方法中，平均查找长度与结点个数 n 无关的查找方法是
答案： 哈希查找
解析： 理想情况下哈希查找的时间复杂度为 O (1)。
30. 若要求一个稠密图 G 的最小生成树，最好用____________算法来求解
答案： Prim
解析： 稠密图适合用 Prim 算法（O (n²)），稀疏图适合 Kruskal（O (eloge)）。
31. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示__________
答案： 一个或多个操作
解析： 算法的定义。
32. 哈希查找的基本思想是由___________决定数据的存储地址
答案： 关键字
解析： 哈希函数根据关键字计算存储地址。
33. 图的 BFS 生成树的树高比 DFS 生成树的树高____________（填大小关系）
答案： 小或相等
解析： BFS 按层次遍历，通常树高较小。
34. 若要求一个稀疏图 G 的最小生成树，最好用__________算法来求解
答案： Kruskal
解析： 稀疏图边少，适合 Kruskal 算法。
35. 在线性结构中，第一个结点____(1)前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点(2)____后续结点，其余每个结点有且只有 1 个后续结点
答案： (1) 没有 (2) 没有
解析： 线性结构的基本特性。
36. 已知串 S=”aaabaab”，假设串位置（即数组下标）从 1 开始，其 next 值为____________
答案： 0 1 2 1 2 3 4
解析： next 数组计算。
37. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：堆排序初始建堆的结果是_______________(以顺序表形式填写答案）
答案： 需要实际建堆结果
解析： 建大根堆的结果。
38. 有一个表长为 m 的哈希表，初始状态为空，现将 n (n<m) 个不同的关键码插入到哈希表中，解决冲突的方法是用线性探测法。如果这 n 个关键码的散列地址都相同，则探测的总次数（遇冲突进行下一次尝试的操作记为一次探测）是________________
答案： n(n-1)/2
解析： 第一个元素 0 次，第二个 1 次，…，第 n 个 n-1 次，总次数 0+1+…+(n-1)=n (n-1)/2。
39. 用 6 个权值 {3, 2, 4, 5, 1, 6} 构造的赫夫曼（Huffman）树的带权路径长度是______________________
答案： 45
解析： WPL 计算。
40. 一棵深度为 6 的满二叉树有_____(1)个分支结点和_(2)_______个叶子结点
答案： (1) 31 (2) 32
解析： 深度 k 的满二叉树：总结点 2^k-1=63，叶子 2^(k-1)=32，分支结点 31。
三、综合题（共 2 题，总分 20 分）
41. AOE 网络问题
41-1 邻接矩阵
答案： 需要原图信息才能填写。
41-2 最早开始时间和最迟开始时间
答案： 需要计算各活动的 earliest 和 latest 时间。
41-3 关键路径
答案： 关键路径是图中最长路径，长度需要计算。
41-4 拓扑排序
答案： 需要根据图计算拓扑序列。
42. 画图题
42-1 高度为 3 的完全二叉树
plaintext
1
/ \
2 3
/ \ /
4 5 6
42-2 二叉搜索树
plaintext
5
/ \
3 7
/ \ / \
2 4 6 8
42-3 4 个顶点、5 条边的无向连通图
plaintext
A
/|\
B | C
\|/
D
42-4 3 个顶点的有向环图
plaintext
X → Y
↑ ↓
Z ← M
