🏷️ 知识点：选择排序
在以下排序算法中，每趟从待排序记录中选出关键字最小的记录，并将其与当前待排序 部分的首记录交换，从而使有序区从前向后逐步扩大的是()。
A. 简单选择排序 B. 冒泡排序 C. 堆排序 D. 直接插入排序
[tag_link]
正确答案：A
简单选择排序算法的比较次数和移动次数分别为()。
A. O(n),O(log₂n) B.O(log₂n),O(n²) C. O(n²),O( n) D.O(nlog₂n),O(n)
[tag_link]
正确答案：C
若只想得到100000个元素组成的序列中第10个最小元素之前的部分排序的序列，用() 方法最快。
A. 冒泡排序 B. 快速排序 C. 归并排序 D. 堆排序
[tag_link]
正确答案：D
下列()是 一 个堆。
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
[tag_link]
正确答案：D
在含有n 个元素的小根堆中(下标从1开始),关键字最大的元素可能存储在()位置。
A. n/2 B . n/2+2 C.1 D.n/2-1
[tag_link]
正确答案：B
向具有 n 个结点的堆中插入一个新元素的时间复杂度为(),删除一个元素的时间复 杂度为( ) 。
A. O(1) B.O(n) C.O(log₂n) D.O(nlog₂n)
[tag_link]
正确答案：【解答】
构建n 个记录的初始堆，其时间复杂度为();对n 个记录进行堆排序，最坏情况下 其时间复杂度为()。
A. O(n) B.O(n²) C.O(log₂n) D.O(nlog₂n)
[tag_link]
正确答案：【解答】
下列4种排序算法中，排序过程中的比较次数与序列初始状态无关的是()。
A. 简单选择排序 B. 直接插入排序 C. 快速排序 D. 冒泡排序
[tag_link]
正确答案：A
对由相同的 n 个整数构成的二叉排序树和小根堆，下列说法中不正确的是()。
A. 二叉排序树的高度大于或等于小根堆的高度 B. 对二叉排序树进行中序遍历可以得到从小到大的序列 C. 从小根堆的根结点到任意叶结点的路径构成从小到大的序列 D. 对小根堆进行层序遍历可以得到从小到大的序列
[tag_link]
正确答案：D
有一组数据(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 均不对
[tag_link]
正确答案：C
对关键字序列{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}
[tag_link]
正确答案：D
堆排序分为两个阶段：第一阶段将给定的序列构造成一个初始堆，第二阶段逐次输出堆 顶元素，并调整使其保持堆的性质。设有给定序列{48,62,35,77,55,14,35,98},若在 堆排序的第一阶段将该序列构造成一个大根堆，则交换元素的次数为()。
A. 5 B.6 C.7 D. 8
[tag_link]
正确答案：B
已知大根堆{62,34,53,12,8,46,22},删除堆顶元素后需要重新调整堆，则在此过程中 关键字的比较次数为()。
A. 2 B.3 C.4 D.5
[tag_link]
正确答案：B
从根结点到任意叶结点的路径都是有序的数据结构是()。
A. 红黑树 B. 二叉查找树 C. 哈夫曼树 D. 堆
[tag_link]
正确答案：D
指出堆和二叉排序树的区别?
[tag_link]
A
画出一棵二叉树，使得它既满足大根堆的要求又满足二叉排序树的要求。
[tag_link]
C
若只想得到一个序列中第 k(k≥5) 个最小元素之前的部分的排序序列，则最好采用什 么排序算法?
[tag_link]
D
通常使用的堆也称二叉堆，因为它是用完全二叉树来实现的，树中结点最多只有两个孩 子。同理可以有 m 叉堆，即用完全m 叉树来实现的堆。 1)下图是一个 m 叉小根堆，问 m 值是多少?向这个堆插入一个元素65后，堆中的元 素如何变化?再删除堆顶元素呢?请画出变化后的树形。 904 90 4 2)从0开始对完全4叉树中的结点从左到右、从上到下进行编号。若给定一个结点k, 其父结点的编号是多少?(若存在),其第i(i=1,2,3,4) 个孩子的编号是多少? 3 ) 在m 叉堆中进行插入和删除操作的时间复杂度是多少?
[tag_link]
D
编写一个算法，在基于单链表表示的待排序关键字序列上进行简单选择排序。
[tag_link]
B
试设计一个算法，判断一个数据序列是否构成一个小根堆。
[tag_link]
【解答】
优先队列( Priority Queue) 是一种数据结构，它类似于普通队列，但每个元素都有一个 优先级。元素在入队时会根据其优先级来排序，而不按照先入先出的顺序来排序。每次 从优先队列中出队时，出队的是优先级最高的元素，而不是最早进入队列的元素。 队列中的元素的数据结构的定义如下： typedef struct{int value; //元素的值int priority; //元素的优先级，priority 越大，优先级越高}PriorityQueueElement; typedef struct{ int value; //元素的值 int priority; //元素的优先级，priority 越大，优先级越高 }PriorityQueueElement; 请设计一个优先队列，要求满足：①初始时队列为空；②入队时，不允许增加队列的 占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间 不变；④入队操作和出队操作的时间复杂度始终保持为O(log₂n) 。请回答：
- 该队列是应选择链式存储结构，还是选择顺序存储结构? 2)给出优先队列的数据结构的定义。 3)用伪代码给出入队操作和出队操作的基本过程(关键之处可用文字描述)。
[tag_link]
【解答】