数据结构排序真题

2020年

【2020年题09】 下列关于大根堆（至少含 2 个元素）的叙述中，正确的是（ ）。

I. 可以将堆视为一棵完全二叉树

II. 可以采用顺序存储方式保存堆

III. 可以将堆视为一棵二叉排序树

IV. 堆中的次大值一定在根的下一层

A. 仅 I、II B. 仅 II、III C. 仅 I、II 和 IV D. I、III 和 IV

解析：

这是一道简单的概念题。堆是一棵完全二叉树，采用一维数组存储，故 I 正确，II 正确。大根堆只要求根结点值大于左右孩子值，并不要求左右孩子值有序，III 错误。堆的定义是递归的，所以其左右子树也是大根堆，所以堆的次大值一定是其左孩子或右孩子，IV 正确。

【2020年题10】 依次将关键字 5, 6, 9, 13, 8, 2, 12, 15 插入初始为空的 4 阶 B 树后，根结点中包含的关键字是（ ）。

A. 8 B. 6, 9 C. 8, 13 D. 9, 12

解析：

一个 4 阶 B 树的任意非叶结点至多含有 $m-1=3$ 个关键字，在关键字依次插入的过程中，会导致结点的不断分裂，插入过程如下所示。