对于n个元素的关键字序列{k1,k2,…,kn},当且仅当满足关系ki≤K2i且ki≤K2i(2i≤n,2i+1≤n)称其为小根堆,反之则为大根堆。以下序列中,(38)不符合堆的定义。

admin2013-02-02  38

问题 对于n个元素的关键字序列{k1,k2,…,kn},当且仅当满足关系ki≤K2i且ki≤K2i(2i≤n,2i+1≤n)称其为小根堆,反之则为大根堆。以下序列中,(38)不符合堆的定义。

选项 A、(5,10,15,76,39,27,18)
B、(5,10,18,76,39,27,15)
C、(59,27,36,15,8,25,9)
D、(59,36,27,15,8,25,9)

答案B

解析 将4个选项序列的元素放入一棵完全二叉树,如图4-6所示,以便于观察节点ki、k2i、k2i+1(2i≤n,2i+1≤n)之间的关系。

按照小根堆的定义检查选项A、B的二叉树,按照大根堆的定义检查选项C、D的二叉树,显然,选项B不符合小根堆的定义。
转载请注明原文地址:https://jikaoti.com/ti/vxL7FFFM
0

随机试题
最新回复(0)