LogicLab

Appearance

3.1节后习题 ​

题目要求 ​

一、判断题 ​

二叉堆的根节点一定是全堆的最小值。
正确
错误
在最大堆中插入新元素后，只需调整根节点即可恢复堆性质。
正确
错误

二、选择题 ​

下列选项中，符合堆性质的结构是？
A根节点为5，左子节点为3，右子节点为7
B根节点为5，左子节点为7，右子节点为3
C根节点为5，左子节点为5，右子节点为5
D以上均符合
删除堆顶元素后，堆调整的方式是？
A将末元素移至堆顶，然后向下交换
B将堆顶元素与末元素交换后删除
C直接删除堆顶元素，无需调整
D重新构建整个堆

三、填空题 ​

在空堆中依次插入元素3、1、5，形成最大堆后，根节点的值为____。
堆的时间复杂度主要取决于树的____，其值为____。

四、简答题 ​

  1. 简述堆的"子树自堆性"对插入操作的意义。
答案
  • 局部调整高效性：插入新元素时，只需从插入位置向上调整，无需遍历整个堆。
  • 保持堆结构完整性：调整过程中仅影响当前路径，其他子树保持堆性质。
  • 时间复杂度可控：最多 O(log n) 次交换。
  1. 为什么删除堆顶元素后，未参与交换的子树仍保持堆性质。
答案
  • 子树自堆性保证未被交换的子树本身已是合法堆。
  • 下沉调整仅影响当前路径，其他子树堆性质不受破坏。