8.4 选择排序·习题
复习入口
8.4 选择排序 · 8.4.1 简单选择排序 · 8.4.2 堆的定义 · 8.4.2.1 建堆与堆排序 · 8.4.2.2 堆的插入与删除 · 8.4.2.3 堆的应用与性能
本节共29题:选择题21题,综合应用题8题。每题答案紧接题目折叠显示。
文字转录进度:29/29题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P361 · 解析P364 · 目视转录
每次从未排序记录中选取最小关键字记录,加入已排序记录末尾,该算法是( )。
A. 简单选择排序
B. 冒泡排序
C. 堆排序
D. 直接插入排序
查看答案与解析
答案:A。
单项选择题 02
原书题目P361 · 解析P364 · 目视转录
简单选择排序的比较次数和移动次数分别为( )。
A. ,
B. ,
C. ,
D. ,
查看答案与解析
答案:C。
应熟练掌握各排序算法的思想、过程与特点。
单项选择题 03
原书题目P361 · 解析P364 · 目视转录
若只想得到 100000 个元素序列中前 10 个最小元素的部分排序序列,用( )最快。
A. 冒泡排序
B. 快速排序
C. 归并排序
D. 堆排序
查看答案与解析
答案:D。
读入前 10 个元素建立大根堆,再扫描其余元素:大于堆顶则舍弃,否则替换堆顶并调整。扫描结束后堆内即最小 10 个元素。冒泡需从后往前进行 10 趟,两者都与 n 线性相关,但堆排序常数更小。快速、归并每趟不能保证得到当前最小值,也不能按此方式达到线性时间。
单项选择题 04
原书题目P361 · 解析P364 · 目视转录
下列( )是一个堆。
A. 19,75,34,26,97,56
B. 97,26,34,75,19,56
C. 19,56,26,97,34,75
D. 19,34,26,97,56,75
查看答案与解析
答案:D。
把序列表示为完全二叉树,检查所有父子关系。例如 A 最小值 19 在根,只可能是小根堆,但 75 与其孩子 26 不满足要求,故不是堆。其他同理分析。
单项选择题 05
原书题目P361 · 解析P364 · 目视转录
含 n 个元素的小根堆,下标从 1 开始,最大关键字可能存于( )位置。
A. n/2
B. n/2+2
C. 1
D. n/2−1
查看答案与解析
答案:B。
最大值一定在完全二叉树叶结点中,最后一个非叶结点存于 L[⌊n/2⌋],故最大值存储范围为 ⌊n/2⌋+1~n。也可类比大根堆最小值范围。
单项选择题 06
原书题目P361 · 解析P364 · 目视转录
向含 n 个结点的堆插入一个元素的时间复杂度为( ),删除一个元素的时间复杂度为( )。
A.
B.
C.
D.
查看答案与解析
答案:C、C。
插入需向上调整,比较次数最多为树高减 1。树高为 ⌊log₂n⌋+1,因此向上调整最多比较 ⌊log₂n⌋ 次。应区别“调整堆”和“建初始堆”的时间复杂度,仔细分析执行过程。
单项选择题 07
原书题目P361 · 解析P364 · 目视转录
构建 n 个记录的初始堆,时间复杂度为( );对 n 个记录堆排序,最坏时间复杂度为( )。
A.
B.
C.
D.
查看答案与解析
答案:A、D。
建堆中向下调整时间与子树高 h 有关,为 ,而大部分结点高度较小,可证明建堆为 。堆排序最好与最坏均为 。
单项选择题 08
原书题目P361 · 解析P364 · 目视转录
下列算法中,排序比较次数与序列初态无关的是( )。
A. 简单选择排序
B. 直接插入排序
C. 快速排序
D. 冒泡排序
查看答案与解析
答案:A。
简单选择的比较次数始终为 n(n−1)/2,与初态无关。
单项选择题 09
原书题目P361 · 解析P364 · 目视转录
由相同 n 个整数组成的二叉排序树与小根堆,下列不正确的是( )。
A. 二叉排序树高度大于或等于小根堆高度
B. 二叉排序树中序遍历可得从小到大序列
C. 小根堆根到任意叶结点路径构成从小到大序列
D. 小根堆层序遍历可得从小到大序列
查看答案与解析
答案:D。
堆是顺序存储的完全二叉树,高度不大于相同结点数的二叉排序树,A 正确。B 显然正确;由堆定义根到叶路径有序,C 正确。兄弟结点之间无大小要求,层序不能保证有序,D 错误。
单项选择题 10
原书题目P362 · 解析P365 · 目视转录
数据 (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. A、B、C均不对
查看答案与解析
答案:C。
从 ⌊n/2⌋ 到 1 依次筛选,数组变化如下。
| 筛选结点 | 结果 |
|---|---|
| 8 | 15,9,7,4,20,−1,7,8 |
| 7 | 15,9,−1,4,20,7,7,8 |
| 9 | 15,4,−1,8,20,7,7,9 |
| 15 | −1,4,7,8,20,15,7,9 |
单项选择题 11
原书题目P362 · 解析P365 · 目视转录
对 {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。
筛选法初始堆为 {8,17,23,52,25,72,68,71,60};输出 8 后重建为 {17,25,23,52,60,72,68,71};输出 17 后重建为 {23,25,68,52,60,72,71}。
单项选择题 12
原书题目P362 · 解析P365 · 目视转录
堆排序先建初始堆,再逐次输出堆顶并调整。序列 {48,62,35,77,55,14,35,98} 第一阶段建大根堆,交换元素次数为( )。
A. 5
B. 6
C. 7
D. 8
查看答案与解析
答案:B。
按从下到上、从右到左调整。交换依次为 98与77、98与62、77与62、98与48、77与48、62与48,共 6 次。其间还比较 14与35、35与35(不交换)、98与55、77与55、48与62 等,以选择正确下移路径。
单项选择题 13
原书题目P362 · 解析P365 · 目视转录
大根堆 {62,34,53,12,8,46,22} 删除堆顶后重新调整,关键字比较次数为( )。
A. 2
B. 3
C. 4
D. 5
查看答案与解析
答案:B。
将堆尾 22 放根,先比较 34与53(第1次),较大者53与22比较(第2次),交换;22 只有左孩子46,直接比较(第3次)并交换。调整完成为 {53,34,46,12,8,22}。
单项选择题 14
原书题目P362 · 解析P365 · 目视转录
根到任意叶结点的路径都是有序序列的数据结构是( )。
A. 红黑树
B. 二叉查找树
C. 哈夫曼树
D. 堆
查看答案与解析
答案:D。
红黑树、二叉查找树的中序有序,根到叶路径未必有序;哈夫曼树按权值规则构造,与关键字次序无关。小根堆根到叶升序,大根堆根到叶降序。
单项选择题 15
原书题目P362 · 解析P365 · 目视转录
【2009 统考真题】小根堆 {5,8,12,19,28,20,15,22} 插入 3,调整后是( )。
A. 3,5,12,8,28,20,15,22,19
B. 3,5,12,19,20,15,22,8,28
C. 3,8,12,5,20,15,22,28,19
D. 3,12,5,8,28,20,15,22,19
查看答案与解析
答案:A。
3 放在末尾为 19 的右孩子,依次与 19、8、5 交换,得到 A。
单项选择题 16
原书题目P362 · 解析P366 · 目视转录
【2011 统考真题】大根堆 {25,13,10,12,9} 在尾部插入 18,调整中元素间比较次数为( )。
A. 1
B. 2
C. 4
D. 5
查看答案与解析
答案:B。
18 与 10 比较并交换,再与 25 比较、不交换,共 2 次。
单项选择题 17
原书题目P362 · 解析P366 · 目视转录
【2015 统考真题】小根堆 8,15,10,21,34,16,12,删除 8 后重建,关键字比较次数为( )。
A. 1
B. 2
C. 3
D. 4
查看答案与解析
答案:C。
12 移到堆顶,先比较 15与10,再比较 10与12并交换,最后还比较 12与16,共 3 次。
单项选择题 18
原书题目P362 · 解析P366 · 目视转录
【2018 统考真题】将 (6,1,5,9,8,4,7) 建立大根堆,正确变化过程为( )。
A. 6,1,7,9,8,4,5 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
B. 6,9,5,1,8,4,7 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
C. 6,9,5,1,8,4,7 → 9,6,5,1,8,4,7 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
D. 6,1,7,9,8,4,5 → 7,1,6,9,8,4,5 → 7,9,6,1,8,4,5 → 9,7,6,1,8,4,5 → 9,8,6,1,7,4,5
查看答案与解析
答案:A。
从后向前处理非叶结点。先比较 4、7,将 7与5交换;再比较 9、8,将 9与1交换;接着比较 9、7,将 9与6交换;6 下沉再与 8 交换,得 A。
单项选择题 19
原书题目P362 · 解析P366 · 目视转录
【2020 统考真题】关于至少含 2 个元素的大根堆,正确的是( )。
Ⅰ.可以将堆视为完全二叉树。
Ⅱ.可以采用顺序存储方式保存堆。
Ⅲ.可以将堆视为二叉排序树。
Ⅳ.堆中次大值一定在根的下一层。
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ、Ⅲ
C. 仅Ⅰ、Ⅱ和Ⅳ
D. Ⅰ、Ⅲ和Ⅳ
查看答案与解析
答案:C。
堆是完全二叉树,可用一维数组,Ⅰ、Ⅱ正确。只要求父值大于孩子,不要求左右孩子有序,Ⅲ错误。左右子树也为大根堆,次大值必为根的左或右孩子,Ⅳ正确。
单项选择题 20
原书题目P362 · 解析P366 · 目视转录
【2021 统考真题】依次将 6,9,1,5,8,4,7 插入初始为空的大根堆 H,所得 H 是( )。
A. 9,8,7,6,5,4,1
B. 9,8,7,5,6,1,4
C. 9,8,7,5,6,4,1
D. 9,6,7,5,8,4,1
查看答案与解析
答案:B。
逐次插入并上调,数组依次为 {6}、{9,6}、{9,6,1}、{9,6,1,5}、{9,8,1,5,6}、{9,8,4,5,6,1}、{9,8,7,5,6,1,4}。
注意:依次插入空堆与把完整序列直接筛选成堆,结果可能不同。若直接调整给定序列,会得到 C。
单项选择题 21
原书题目P362 · 解析P367 · 目视转录
【2024 统考真题】关键字 28,22,20,19,8,12,15,5 是大根堆,进行两次删除后的新堆是( )。
A. 20,19,15,12,8,5
B. 20,19,15,5,8,12
C. 20,19,12,15,8,5
D. 20,19,8,12,15,5
查看答案与解析
答案:B。
删除 28,将 5 放顶。比较 22与20,22较大并与5交换;比较19与8,19较大并与5交换,得到 {22,19,20,5,8,12,15}。
再删除22,将15放顶。比较19与20,20较大并与15交换;15再与其唯一左孩子12比较,不交换。新堆 {20,19,15,5,8,12}。
综合应用题
综合应用题 01
原书题目P363 · 解析P367 · 目视转录
指出堆与二叉排序树的区别。
查看答案与解析
以小根堆为例,父关键字必小于或等于孩子关键字,两个孩子之间无次序规定。二叉排序树中,父关键字大于左子树所有关键字,小于右子树所有关键字,父、左、右具有次序关系。因此中序遍历排序树可得有序序列,堆不一定。
综合应用题 02
原书题目P363 · 解析P367 · 目视转录
画一棵二叉树,使其既满足大根堆又满足二叉排序树要求。
查看答案与解析
大根堆根值≥左、右孩子;二叉排序树根值>左孩子、<右孩子。可兼容的是只有左孩子的树,而大根堆必须完全二叉树,所以非单结点例子只有两个结点,如根 5、左孩子 2。一个结点也满足,但此处用两结点体现差异。
综合应用题 03
原书题目P363 · 解析P368 · 目视转录
若只想得到序列中前 k(k≥5)个最小元素的部分有序序列,最好采用什么排序算法?
查看答案与解析
堆排序较合适。原书比较:插入、快速、归并需全部排序才能得到前 k 个最小元素序列,效率不高;冒泡、堆、简单选择每趟均可确定一个最小元素。n 个元素建初始堆时间不超过 4n,取得前 k 个有序元素约需 klog₂n,总计 4n+klog₂n;冒泡、简单选择约 kn,k≥5 时堆排序更优。
注意:求前 k 个最小元素的有序序列,可用冒泡、堆和简单选择排序。
综合应用题 04
原书题目P363 · 解析P368 · 目视转录
二叉堆用完全二叉树实现,每个结点最多两个孩子。也可有用完全 m 叉树实现的 m 叉堆。
- 下面是 m 叉小根堆,m 是多少?插入 65 后、再删除堆顶后,分别画出树形。根 0 的孩子从左到右为 23、67、88、90;23 的孩子为 30、44、49、60;67 的第一个孩子为 70。
- 完全 4 叉树从 0 开始按层从左到右编号,结点 k 的父结点编号、其第 i(i=1,2,3,4)个孩子编号分别是多少(若存在)?
- m 叉堆插入和删除的时间复杂度是多少?
查看答案与解析
- 除最后一个分支结点外,每个分支都有 4 个孩子,因此是完全 4 叉树,m=4。插入65后,根0的孩子为23、65、88、90,23的孩子仍为30、44、49、60,65的孩子为70、67。再删除0后,根为23,孩子为30、65、88、90,30的孩子为67、44、49、60,65的孩子为70。
按层数组表示为:初始 [0,23,67,88,90,30,44,49,60,70];插入后 [0,23,65,88,90,30,44,49,60,70,67];删除顶后 [23,30,65,88,90,67,44,49,60,70]。
- 父编号为 ⌊(k−1)/4⌋(k>0),第 i 个孩子编号为 4k+i。
- 与二叉堆类似,插入与删除涉及向上、向下调整,时间与树高有关。固定 m 时均为 ,n 为元素数。
综合应用题 05
原书题目P363 · 解析P368 · 目视转录
编写算法,在基于单链表表示的待排序关键字序列上进行简单选择排序。
查看答案与解析
每趟从原链摘下关键字最大的结点,插在结果链最前。原链中摘下的值越来越小,最后结果链按关键字非递减。设链表不带头结点。
void selectSort(LinkedList &L) {
LinkNode *h = L, *p, *q, *r, *s;
L = NULL;
while (h != NULL) {
p = s = h;
q = r = NULL;
// s、r 记录最大结点及其前驱,p、q 为工作指针及前驱
while (p != NULL) {
if (p->data > s->data) { s = p; r = q; }
q = p;
p = p->link;
}
if (s == h)
h = h->link;
else
r->link = s->link;
s->link = L;
L = s;
}
}
综合应用题 06
原书题目P363 · 解析P369 · 目视转录
设计算法,判断一个数据序列是否构成小根堆。
查看答案与解析
将 L[1..n] 视为完全二叉树,扫描所有分支结点,若孩子值小于父值,返回 false;全部满足则返回 true。
bool IsMinHeap(ElemType A[], int len) {
int i;
if (len % 2 == 0) {
if (A[len / 2] > A[len]) return false;
for (i = len / 2 - 1; i >= 1; i--)
if (A[i] > A[2 * i] || A[i] > A[2 * i + 1])
return false;
}
else {
for (i = len / 2; i >= 1; i--)
if (A[i] > A[2 * i] || A[i] > A[2 * i + 1])
return false;
}
return true;
}
偶数长度有一个仅左孩子的结点,先单独判断;奇数长度不存在单分支结点。
综合应用题 07
原书题目P363 · 解析P369 · 目视转录
优先队列类似普通队列,但元素按优先级排序,出队取优先级最高者。元素定义:
typedef struct {
int value;
int priority; // 值越大,优先级越高
} PriorityQueueElement;
设计优先队列,满足:① 初始为空;② 入队不允许增加占用空间;③ 出队后空间可重复使用,整体占用空间不变;④ 入队、出队时间复杂度始终保持 。要求:
- 选择链式还是顺序存储?
- 给出数据结构定义。
- 伪代码给出入队、出队基本过程,关键处可用文字描述。
查看答案与解析
- 用顺序存储,即数组实现按 priority 比较的大根堆,可满足固定空间及对数时间要求。
- 定义如下。
typedef struct {
PriorityQueueElement heap[MAX_SIZE];
int size; // 当前元素数,初值为 0
} PriorityQueue;
- 入队伪代码:
void enqueue(PriorityQueue *pq, int value, int priority) {
if (pq->size >= MAX_SIZE) {
队列已满,无法入队;
return;
}
将新元素添加到堆末尾,并增加 size;
按 priority 向上调整堆;
}
出队伪代码:
PriorityQueueElement dequeue(PriorityQueue *pq) {
if (pq->size == 0) {
队列为空,直接退出;
}
保存堆顶元素(优先级最高者);
将最后一个元素放到堆顶,并减少 size;
按 priority 向下调整堆;
返回保存的出队元素;
}
综合应用题 08
原书题目P363 · 解析P370 · 目视转录
【2022 统考真题】一维数组 M 中有 n(n>100000)个数,需查找最小的 10 个数。
- 设计算法,要求平均比较次数尽可能少,简述思想,无需编码。
- 说明平均时间和空间复杂度。
查看答案与解析
- 方法一:定义含10元素数组A,初值均为类型最大值MAX。遍历M中每个s,若s<A[9],丢弃A[9]并把s升序插入A;扫描后A[0..9]为最小10个数。
方法二:定义含10元素的大根堆H,初值均为类型最大值MAX。遍历M中每个s,若s小于堆顶,则删除堆顶并插入s;扫描后堆内为最小10个数。
- 两者平均时间复杂度均为 ,额外空间为固定10元素,复杂度 。