2026-03-30 练习题答案与解析
基本数据结构 - 栈、队列与列表 答案与解析
单项选择题
1. 设有三个元素 X，Y，Z 顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是（ ）。
答案：C. ZXY
解析： 要得到 ZXY，必须先让 Z 出栈，即 X、Y、Z 依次进栈后弹出 Z。此时栈中为 X（底）、Y（顶），下一个只能弹出 Y，而不是 X，因此 ZXY 不可能实现。卡特兰数约束下，对于 3 个元素的合法出栈序列共 5 种：XYZ、XZY、YXZ、YZX、ZYX，不包含 ZXY。
2. 链表不具有的特点是（ ）。
答案：A. 可随机访问任意元素
解析： 链表是顺序访问结构，只能从头结点开始沿指针逐个遍历，不支持像数组那样通过下标直接访问第 i 个元素（即随机访问）。B、C、D 都是链表的特点。
3. 判定一个无序表 Q（链表实现）为空的条件是（ ）。
答案：A. Q.head == None
解析： 链表实现的无序表以 head 引用指向第一个结点，当 head 为 None 时表示链表为空。Q 本身是链表对象而非 None，所以 B 不正确。
4. 有 n² 个整数，找到其中最小整数需要比较次数至少为（ ）次。
答案：C. n²-1
解析： 在无序的 n² 个元素中查找最小值，每次比较只能淘汰一个元素，因此至少需要 n²-1 次比较。这是基于锦标赛（比赛树）的下界论证。
5. 允许表达式内多种括号混合嵌套，检查表达式中括号是否正确配对的算法，通常选用（ ）。
答案：A. 栈
解析： 括号匹配是栈的经典应用。遇到左括号入栈，遇到右括号时弹出栈顶检查是否匹配。栈的后进先出（LIFO）特性恰好对应括号的嵌套结构。
6. 双向链表中在 p 前插入 q，正确的操作为（ ）。
答案：D. p.prev.next=q; q.next=p; q.prev=p.prev; p.prev=q;
解析： 在双向链表中于 p 之前插入 q，需要修改四个引用：
p.prev.next = q：p 的前驱的 next 指向 qq.next = p：q 的 next 指向 pq.prev = p.prev：q 的 prev 指向 p 的原前驱p.prev = q：p 的 prev 指向 q
关键在于操作顺序：必须在修改 p.prev 之前完成对 p.prev 的读取。选项 D 的顺序正确保证了这一点。选项 A 中先执行 p.prev=q 会导致后续 p.prev.next 实际访问的是 q.next，产生错误。
7. 递归二分查找栈的最小容量应为（ ）。
答案：D. ⌈log₂(N+1)⌉
解析： 二分查找每次将搜索区间减半，递归深度等于搜索树的高度。对于 N 个元素，二分搜索树的高度为 ⌈log₂(N+1)⌉。每层递归需要一个栈帧，因此栈的最小容量为 ⌈log₂(N+1)⌉。
8. 下列概念中属于存储结构的是（ ）。
答案：B. 链表
解析： 线性表、字符串、二叉树都是逻辑结构（描述数据元素之间的逻辑关系）。链表是存储结构（也称物理结构），它描述数据在内存中的实际存储方式，通过指针链接各结点。
9. 循环队列的队首元素实际位置是（ ）。
答案：B. (1+rear+m-length) % m
解析： rear 表示队尾元素的实际位置，length 为当前元素个数。从队尾往前推 length-1 个位置即为队首：front = (rear - length + 1 + m) % m = (1 + rear + m - length) % m。加 m 是为了避免负数取模的问题。
10. 下列不影响算法时间复杂性的因素有（ ）。
答案：C. 计算结果
解析： 影响算法时间复杂度的主要因素有：问题的规模（A）、输入值/数据的初始状态（B）、算法的策略/设计（D）。计算结果（C）是算法执行后的输出，不会反过来影响算法的时间复杂度。
判断题
11. 队列是动态集合，其定义的出队列操作所移除的元素总是在集合中存在时间最长的元素。
答案：A. 正确
解析： 队列遵循先进先出（FIFO）原则，最先入队的元素在队列中存在时间最长，也最先被出队操作移除。这正是 FIFO 的定义。
12. 考虑一个长度为 n 的顺序表中各个位置插入新元素的概率是相同的，则顺序表的插入算法平均时间复杂度为 O(n)。
答案：A. 正确
解析： 在长度为 n 的顺序表中，可以在 n+1 个位置插入。在第 i 个位置插入需要移动 n-i+1 个元素。等概率下平均移动次数为 ，即 O(n)。
13. 分治算法通常将原问题分解为几个规模较小但类似于原问题的子问题，并要求算法实现写成某种递归形式，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
答案：A. 正确
解析： 这是分治法（Divide and Conquer）的标准描述：分解（Divide）→ 递归求解（Conquer）→ 合并（Combine）。典型例子包括归并排序、快速排序、二分查找等。
14. 考察某个具体问题是否适合应用动态规划算法，必须判定它是否具有最优子结构性质。
答案：A. 正确
解析： 动态规划的两个关键要素是：① 最优子结构性质（问题的最优解包含子问题的最优解）；② 重叠子问题。判断一个问题能否用动态规划求解，首先需要验证其是否具有最优子结构。
填空题
15. 线性表的顺序存储与链式存储是两种常见存储形式；当表元素有序排序进行二分检索时，应采用_____存储形式。
答案：顺序
解析： 二分查找要求能够通过下标随机访问元素，只有顺序存储（数组）才支持 O(1) 时间的随机访问。链式存储无法直接定位中间元素，不适用二分查找。
16. 环形队列容量为 20，front=18，rear=11，队列中有_____个元素。
答案：13
解析： 在此定义中，rear 是待插入元素的位置（即队尾的下一个位置）。元素个数 = (rear - front + capacity) % capacity = (11 - 18 + 20) % 20 = 13。队列占据的位置为：18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，共 13 个。
17. 朴素模式匹配算法中字符的最多比较次数是_____。
答案：O(nm)
解析： 朴素匹配算法最坏情况下，目标串每个起始位置都需要比较 m 个字符才发现不匹配，共有 n-m+1 个起始位置，因此最多比较次数为 (n-m+1)×m，用大 O 表示法为 O(nm)。
18. 查找的平均比较元素个数为_____。
答案：7/4
解析： 顺序查找第 i 个元素需要比较 i 次。各元素查找概率为 1/2、1/4、1/8，概率之和为 7/8，查找失败概率为 1/8（需比较 3 次）。
19. 删除长度为 n 的顺序表的第 i 个数据元素需要移动_____个数据元素。
答案：n-i
解析： 删除第 i 个元素后，第 i+1 到第 n 个元素都需要向前移动一个位置，共需移动 n-i 个元素。
20. 调用三次 F() 后，S1 栈顶保存的值是_____。
答案：32.5
解析：
- S1（底→顶）：5, 8, 3, 2；S2（底→顶）：*, -, /
- 第 1 次 F()： 弹出 a=2, b=3；弹出 op=/；计算 3/2=1.5；压入 S1 → S1: 5, 8, 1.5
- 第 2 次 F()： 弹出 a=1.5, b=8；弹出 op=-；计算 8-1.5=6.5；压入 S1 → S1: 5, 6.5
- 第 3 次 F()： 弹出 a=6.5, b=5；弹出 op=*；计算 5×6.5=32.5；压入 S1 → S1: 32.5
算法填空题
21. 单链表颠倒算法填空
答案：
- ①
node - ②
node - ③
None - ④
p.next - ⑤
self.head - ⑥
self.head = q
解析：
构造部分（__init__）：
p.next = node # ① 将当前尾结点的 next 指向新创建的结点
p = node # ② 移动 p 到新结点，使其成为新的尾结点这是标准的尾插法建立链表。
反转部分（reverse）：
采用头插法实现链表反转：
self.head.next = None # ③ 原头结点反转后变为尾结点，next 置为 Nonep = p.next # ④ 在将 q 摘下前，先保存 p 的下一个结点
q.next = self.head # ⑤ 将 q 插到当前 head 之前（头插法）
self.head = q # ⑥ 更新 head 为 q，完成头插反转过程相当于不断将后续结点摘下并插入到链表头部，遍历完成后链表即被翻转。完整执行流程示例（输入 1 2 3）：
| 步骤 | head → | 说明 |
|---|---|---|
| 初始 | 1→2→3 | p=2, head.next=None → head: 1→None |
| 第1轮 | 2→1→None | q=2, p=3, q.next=head(1), head=q(2) |
| 第2轮 | 3→2→1→None | q=3, p=None, q.next=head(2), head=q(3) |