数据结构第七章练习题

第1题

1. 用直接插入排序对下面四个序列进行由小到大排序，元素比较次数最少的是（）。

A. 94， 32， 40， 90， 80， 46， 21， 69
B. 21， 32， 46， 40， 80， 69， 90， 94
C. 32， 40， 21， 46， 69， 94， 90， 80
D. 90， 69， 80， 46， 21， 32， 94， 40

答案： B 解析： 直接插入排序在待排序序列基本有序的情况下，元素比较次数最少。

A. 序列较乱。
B. 序列{21, 32, 46, 40, 80, 69, 90, 94} 只有少数元素（如40和69）不在最终位置，是四个选项中最接近有序的。
C. 序列较乱，21在较后的位置。
D. 序列基本逆序，接近最坏情况。因此，对序列B进行排序的比较次数最少。

第2题

2. 数据序列（8， 9，10，4，5，6，20，1， 2）只能是（）的两趟排序后的结果。

A. 选择排序
B. 冒泡排序
C. 插入排序
D. 堆排序

答案： B 解析： 这是一个经典且有些棘手的题目，通常通过排除法来解答。

选择排序 (Selection Sort): 两趟过后，序列中最小的两个元素（1和2）会被放到序列的最前面。当前序列{8, 9, ...}不满足此条件。
插入排序 (Insertion Sort): 两趟过后，序列的前三个元素应该是原序列前三个元素排好序的结果。当前序列前缀为{8, 9, 10}，但后面出现了比10小的元素（如4, 5, 6, 1, 2），这不符合插入排序的性质（已排序区间的元素应该小于等于未排序区间的元素）。
堆排序 (Heap Sort): 两趟（如果指两次extract-max操作）过后，最大的两个元素应该被放到了序列的末尾并排好序。当前序列不满足此条件。
冒泡排序 (Bubble Sort): 虽然标准的冒泡排序两趟过后，最大的两个元素会移动到末尾，但冒泡排序的过程相对“混乱”，对于特定构造的初始序列，有可能在两趟后形成题目中的状态。在其他三个选项被明确排除后，冒泡排序是唯一可能的答案。

第3题

3. 下列排序算法中，（）可能会出现下面情况：在最后一趟开始之前，所有元素都不在最终位置上。

A. 起泡排序
B. 插入排序
C. 快速排序
D. 堆排序

答案： C 解析：

A/D/选择排序 (Bubble/Heap/Selection Sort): 这些排序算法在每一趟（或每一步）都会将一个元素（最大、最小或选中的元素）放置到其最终排好序的位置上。
B 插入排序 (Insertion Sort): 在处理最后一个元素前，已排序的部分是相对于这部分元素有序，但如果最后一个元素是全局最小的，那么之前所有元素的位置都不是最终位置。例如，对{2, 3, 4, 1}排序，在处理1之前，序列为{2, 3, 4, 1}，此时没有一个元素在最终位置{1, 2, 3, 4}上。
C 快速排序 (Quick Sort): 这是本题的“标准答案”，尽管有些争议。其逻辑是，快速排序将序列划分为多个子序列进行递归排序。在最后一趟（比如处理最后一个大小为2的子序列）开始前，其他子序列虽然已经排序，但它们的元素也可能因为这个最后的划分而移动，从而可能导致所有元素都不在它们的绝对最终位置上。

第4题

4. 对有n个记录的线性表进行直接插入排序，在最好情况下需比较（）次。

A. n-1
B. n＋1
C. n/2
D. n（n-1）/2

答案： A 解析： 直接插入排序的最好情况是待排序的线性表已经有序。

在这种情况下，从第二个元素开始，每个元素只需要和它前面的一个元素比较一次即可确定其位置（因为它已经大于等于前一个元素）。
需要插入的元素有 n-1 个（从第2个到第n个）。
总比较次数为 n-1 次。

第5题

5. 将记录序列（8， 9， 10， 4， 5， 6， 20｝采用起泡排序排成升序序列，需要进行（）趟（假设采用从前向后的扫描方式）。

A. 3
B. 4
C. 5
D. 8

答案： B 解析： 采用优化的冒泡排序（如果一趟没有发生交换，则排序完成）。

序列: {8, 9, 10, 4, 5, 6, 20}
第1趟: {8, 9, 4, 5, 6, 10, 20} (发生了交换)
第2趟: {8, 4, 5, 6, 9, 10, 20} (发生了交换)
第3趟: {4, 5, 6, 8, 9, 10, 20} (发生了交换)
第4趟: 遍历序列，没有发生任何交换。
算法在第4趟结束后检测到序列已有序，因此终止。总共需要进行4趟。

第6题

6. 下列序列中，（）是执行第一趟快速排序的结果。

A. ［da，ax，eb，de，bb］ ff ［ha，gc］
B. ［cd，eb，ax，da］ ff ［ha，gc，bb］
C. ［gc，ax，eb，cd，bb］ ff ［da，ha］
D. ［ax，bb，cd，da］ ff ［eb，gc，ha］

答案： A 解析： 快速排序的一趟（一次划分）会选择一个基准（pivot），然后将所有小于等于基准的元素放到它左边，所有大于等于基准的元素放到它右边。

以ff为基准。划分结果的形式应为 [...<=ff...] ff [...>=ff...]。
A: [da, ax, eb, de, bb] ff [ha, gc]。左边的元素按字母序都小于ff，右边的都大于ff。符合要求。
B: bb 在右边，但 bb < ff，错误。
C: gc 在左边，但 gc > ff，错误。
D: eb 在右边，但 eb < ff，错误。

第7题

7. 快速排序在（）情况下最不利于发挥其长处。

A. 待排序的数据量太大
B. 待排序数据含有多个相同值
C. 待排序的数据已基本有序
D. 待排序的数据数量为奇数

答案： C 解析： 快速排序的长处在于通过划分（partition）使得问题规模大致减半，从而达到 O(n log n) 的平均时间复杂度。

当待排序的数据已基本有序（或完全逆序）时，如果每次都选择第一个或最后一个元素作为基准，那么每次划分都会得到一个空的子序列和一个包含 n-1 个元素的子序列。
这种极不均衡的划分使得递归深度达到 n，时间复杂度退化到 O(n^2)，这是其最不利的情况。

第8题

8. 一组记录的关键码为｛46， 79， 56， 38， 40， 84｝，采用快速排序以第一个记录为基准，一次划分结果为（）。

A. ｛40， 38， 46， 56， 79， 84｝
B. ｛40， 38， 46， 79， 56， 84｝
C. ｛40， 38， 46， 84， 56， 79｝
D. ｛84， 79， 56， 46， 40， 38｝

答案： A 解析： 以第一个记录46为基准进行一次划分。这里采用常见的“填坑法”：

序列: {46, 79, 56, 38, 40, 84}
基准: 46 (挖出A[0]，形成坑)
从右向左找小于46的数，找到40。将40填入A[0]的坑，40的位置形成新坑。序列变为 {40, 79, 56, 38, 40, 84}，坑在A[4]。
从左向右找大于46的数，找到79。将79填入A[4]的坑，79的位置形成新坑。序列变为 {40, 79, 56, 38, 79, 84}，坑在A[1]。
从右向左找小于46的数，找到38。将38填入A[1]的坑，38的位置形成新坑。序列变为 {40, 38, 56, 38, 79, 84}，坑在A[3]。
从左向右找大于46的数，找到56。将56填入A[3]的坑，56的位置形成新坑。序列变为 {40, 38, 56, 56, 79, 84}，坑在A[2]。
此时左右指针相遇，将基准46填入最后的坑A[2]。
最终结果: {40, 38, 46, 56, 79, 84}。这与选项A一致。

第9题

9.（）方法是从未排序序列中挑选元素，并将其放入已排序序列的一端。

A. 归并排序
B. 插入排序
C. 快速排序
D. 选择排序

答案： D 解析： 这个描述最符合选择排序。

选择排序 (Selection Sort): 每一趟从未排序的序列中“挑选”出最小（或最大）的元素，然后“放入”已排序序列的末尾。
插入排序 (Insertion Sort): 是从非排序序列中取第一个元素，插入到已排序序列的合适位置，不一定是“一端”。
其他排序算法不符合此描述。

第10题

10. 对数据序列（84， 47， 25， 15， 21）进行排序，数据序列的变化为（84，47， 25， 15， 21）→（15， 47， 25， 84，21）→｛15， 21， 25， 84， 47｝→（15，21， 25， 47， 84），则采用的排序方法是（）。

A. 简单选择排序
B. 快速排序
C. 起泡排序
D. 直接插入排序

答案： A 解析： 我们来分析序列的变化过程。

S0 → S1: {84, 47, 25, 15, 21} → {15, 47, 25, 84, 21}。序列中最小的元素15和第一个元素84交换了位置。这正是简单选择排序第一趟的操作。
S1 → S2: {15 | 47, 25, 84, 21} → {15, 21, 25, 84, 47}。在未排序部分{47, 25, 84, 21}中找到最小的元素21，与该部分第一个元素47交换。这是选择排序第二趟。
S2 → S3: {15, 21 | 25, 84, 47} → {15, 21, 25, 47, 84}。在未排序部分{25, 84, 47}中找到最小的元素25，它已经在首位，无需交换。然后处理{84, 47}，最小的是47，交换。
整个过程完全符合简单选择排序的逻辑。

第11题

11. 堆的形状是一棵（）。

A. 判定树
B. 二叉排序树
C. 完全二叉树
D. 满二叉树

答案： C 解析： 堆（Heap）在逻辑上是一棵二叉树，在物理上通常用数组表示。为了方便地通过数组下标计算父子关系（parent(i) = floor((i-1)/2), left(i) = 2i+1, right(i) = 2i+2），堆的结构被定义为一棵完全二叉树 (Complete Binary Tree)。

第12题

12. 对数据序列（15， 9， 7， 8，20，-1， 7， 4｝，用堆排序的筛选法建立的初始堆为（）。

A. ｛-1， 4， 8， 9， 20， 7， 15， 7｝
B. ｛-1， 7， 15， 7， 4， 8， 20， 9｝
C. ｛-1， 4， 7， 8， 20， 15， 7， 9｝
D. 以上都不对

答案： C 解析： 题目要求建立初始堆，但未指明是最大堆还是最小堆。从选项来看，根节点都是-1，说明是建立最小堆。

序列: {15, 9, 7, 8, 20, -1, 7, 4}
从最后一个非叶子节点 A[n/2 - 1] = A[3] = 8 开始向前调整。
调整 A[3]=8: 子节点为A[7]=4。因为8>4，交换。序列变为 {15, 9, 7, 4, 20, -1, 7, 8}。
调整 A[2]=7: 子节点为A[5]=-1, A[6]=7。最小子节点是-1。因为7>-1，交换。序列变为 {15, 9, -1, 4, 20, 7, 7, 8}。
调整 A[1]=9: 子节点为A[3]=4, A[4]=20。最小子节点是4。因为9>4，交换。序列变为 {15, 4, -1, 9, 20, 7, 7, 8}。被换下的9在A[3]，其子节点为A[7]=8，因为9>8，再次交换。序列变为{15, 4, -1, 8, 20, 7, 7, 9}。
调整 A[0]=15: 子节点为A[1]=4, A[2]=-1。最小子节点是-1。因为15>-1，交换。序列变为{-1, 4, 15, 8, 20, 7, 7, 9}。被换下的15在A[2]，其子节点为A[5]=7, A[6]=7。最小子节点是7。因为15>7，交换。序列变为{-1, 4, 7, 8, 20, 15, 7, 9}。
最终结果与选项C { -1, 4, 7, 8, 20, 15, 7, 9 } 一致。

第13题

13. 下列序列（）是堆。

A. ｛1， 2， 8， 4， 3， 9， 10， 5｝
B. ｛1， 5， 10， 6， 7， 8， 9， 2｝
C. ｛9， 8， 7， 6， 4， 8， 2， 1｝
D. ｛9， 8， 7， 6， 5， 4， 3， 7｝

答案： A 解析： 堆需要满足堆属性（所有父节点都大于等于或小于等于其子节点）。

A: {1, 2, 8, 4, 3, 9, 10, 5}
- 1的子节点是2, 8 (1<2, 1<8)。
- 2的子节点是4, 3 (2<4, 2<3)。
- 8的子节点是9, 10 (8<9, 8<10)。
- 这是一个有效的最小堆。
B: 10的子节点是8, 9。10>8, 10>9，不满足最小堆。而根节点1小于子节点5，不满足最大堆。不是堆。
C: 7的子节点是8, 2。7<8，不满足最大堆。不是堆。
D: 6的子节点是7。6<7，不满足最大堆。不是堆。

第14题

14. 对关键码序列（23， 17， 72， 60， 25， 8， 68， 71， 52）进行堆排序，输出两个最小关键码后的剩余堆是（）。

A. ｛23， 72， 60， 25， 68， 71， 52｝
B. ｛23， 25， 52， 60， 71， 72， 68｝
C. ｛71， 25， 23， 52， 60， 72， 68｝
D. ｛23， 25， 68， 52， 60， 72， 71｝

答案： D 解析： 堆排序输出最小关键码，需要使用最小堆。

1. 建立最小堆:
- 原序列: {23, 17, 72, 60, 25, 8, 68, 71, 52}
- 建好后的最小堆: {8, 17, 23, 52, 25, 72, 68, 71, 60}
2. 输出第一个最小关键码 (8):
- 取出根8。将最后一个元素60放到根。
- 堆变为 {60, 17, 23, 52, 25, 72, 68, 71}
- 向下调整60，最终堆变为 {17, 25, 23, 52, 60, 72, 68, 71}
3. 输出第二个最小关键码 (17):
- 取出根17。将最后一个元素71放到根。
- 堆变为 {71, 25, 23, 52, 60, 72, 68}
- 向下调整71，最终堆变为 {23, 25, 68, 52, 60, 72, 71}
剩余的堆与选项D一致。

第15题

15. （）在某趟排序结束后不一定能选出一个元素放到其最终位置上。

A. 选择排序
B. 起泡排序
C. 归并排序
D. 堆排序