🏷️ 知识点：堆的概念
一组数据 (30,20,10,15,35,1,10,5)，用堆排序（小顶堆）的筛选方法建立的初始堆为（ ）。
A. 1,5,15,20,35,10,30,10 B. 1,10,30,10,5,15,35,20 C. 1,5,10,15,35,30,10,20 D. A、B 和 C 均不正确
[tag_link]
正确答案：C
考查初始堆的建立。 首先对以第
个结点为根的子树（也即最后一个结点的父结点为根的子树）筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，直到筛选到根结点。
从 依次筛选堆的过程如下图所示：
>下列关于大根堆（至少含 2 个元素）的叙述中正确的是（ ）。
I. 可以将堆看成一颗完全二叉树；II. 可采用顺序存储方式保存堆；
III. 可以将堆看成一棵二叉排序树；IV. 堆中的次大值一定在根的下一层。
A. 仅 I，II B. 仅 II，III C. 仅 I，II，IV D. 仅 I，III，IV
[tag_link]
正确答案：C
堆 是一棵完全树，采用一维数组存储，故 I 正确，II 正确。 大根堆 只要求根结点值大于左右孩子值，并不要求左右孩子值有序，III 错误。堆的定义是递归的，所以其左右子树也是大根堆，所以堆的次大值一定是其左孩子或右孩子，IV 正确。
已知关键字序列 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
[tag_link]
正确答案：B
本题考察 堆的删除操作，先根据初始序列建堆，然后依次删除堆项元素，过程如下图：
从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是（ ）。
A. 二叉排序树 B. 大顶堆 C. 小顶堆 D. 平衡二叉树
[tag_link]
正确答案：C
在小顶堆中，每个结点的关键字都小于或等于其子结点的关键字。
因此，从任意结点出发，向上遍历父结点直至根结点，所经过的结点关键字会逐渐减小或保持不变，即序列必然是降序排列。
对于大顶堆，父结点的关键字大于或等于子结点的关键字，路径上的结点关键字序列是升序排列，不符合要求。 二叉排序树和平衡二叉树的关键字排列没有统一规则，路径上的结点序列不一定满足降序排列。
堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶元素。设给定序列{48,62,35,77,55,14,35,98}，若在堆排序的第一阶段将该序列建成一个堆（大根堆），那么交换元素的次数为（ ）。
A. 5 B. 6 C. 7 D. 8
[tag_link]
正确答案：B
考查初始堆的构造过程。 首先对以第
个结点为根的子树筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，直到筛选到根结点。
序列 建立初始堆的过程如下所示：
>对关键序列为{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,23,25,60,72,68} D. {23,25,68,52,60,72,71}
[tag_link]
正确答案：D
首先，将关键序列 {23,17,72,60,25,8,68,71,52} 构建成最小堆。
构建过程如下：从最后一个非叶子节点开始向下调整，最终得到最小堆序列为 {8,17,23,52,25,72,68,71,60}。
输出第一个最小关键字 8：将堆顶 8 与最后一个元素 60 交换，移除 8，对剩余前 8 个元素调整堆，得到新堆 {17,25,23,52,60,72,68,71}。
输出第二个最小关键字 17：将堆顶 17 与最后一个元素 71 交换，移除 17，对剩余前 7 个元素调整堆，得到新堆 {23,25,68,52,60,72,71}。
因此，输出两个最小关键字后的剩余堆为 {23,25,68,52,60,72,71}，对应选项 D。
已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。
A. 1 B. 2 C. 3 D. 4
[tag_link] 正确答案：C删除 8 后，将 12 移动到堆顶，第一 次是 15 和 10 比较，第二次是 10 和 12 比较并交换，第三次还需比较 12 和 16, 故比较次数为 3 次。
假定我们从下图所示的堆中删除了值为 11 的结点，那么值为 70 的结点将出现在图中哪个指定位置（ ）。
A. A
B. B
C. C
D. D
[tag_link]
正确答案：C
本题考查堆的调整过程。 堆的调整流程如下图所示，可知 70 最后的位置为 C。
已知序列 25,13,10,12,9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）
A. 1
B. 2
C. 4
D. 5
[tag_link]
正确答案：B
插入 18 后，首先将 18 与 10 比较，交换位置，再将 18 与 25 比较，不交换位置。共比较了 2次，调整的过程如下图所示。
在将数据序列 (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
[tag_link]
正确答案：A
参考构造初始堆，该题的堆变化过程如下图所示：答案选择 A。
将关键字 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
[tag_link]
正确答案：B
参考 构造初始堆 的过程：
(10分)现有 n(n>100000)个数保存在一维数组 M中，需要查找 M中最小的10个数，请回答下列 问题。
(1) 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不 需要程序实现。
(2)说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
[tag_link]
[tag_link]
【答案 1】 定义含 10 个元素的数组 A，初始时元素值均为该数组类型能表示的最大数 MAX。 for M 中的每个元素 s if (s < A[9]) 丢弃 A[9]并将 s 按升序插入到 A 中； 当数据全部扫描完毕，数组 A[0]~A[9]保存的即是最小的 10 个数。 【答案 2】 定义含 10 个元素的大根堆 H，元素值均为该堆元素类型能表示的最大数 MAX。 for M 中的每个元素 s if （s < H 的堆顶元素） 删除堆顶元素并将 s 插入到 H 中； 当数据全部扫描完毕，堆 H 中保存的即是最小的 10 个数。 组成原理 43 某 CPU 中部分数据通路如图所示，其中，GPRs 为通用寄存器组；FR 为标志寄存器，用于存放 ALU 产生的标志信息；带箭头虚线表示控制信号，如控制信号 ReaD. Write 分别表示主存读、主存写，MDRin 表示内部总线上数据写入 MDR，MDRout 表示 MDR 的内容送内部总线。 MAR