对于n个元素的关键字序列{k1,k2,…,kn}, 当且仅当满足关系ki≤2i且ki≤k2i+1(i=1,2,…,)时称其为小根堆(小顶堆)。以下序列中,___________不是小根堆。

admin2018-04-19  43

问题 对于n个元素的关键字序列{k1,k2,…,kn},  当且仅当满足关系ki2i且ki≤k2i+1(i=1,2,…,)时称其为小根堆(小顶堆)。以下序列中,___________不是小根堆。

选项 A、16,25,40,55,30,50,45
B、16,40,25,50,45,30,55
C、16,25,39,41,45,43,50
D、16,40,25,53,39,55,45

答案D

解析 本题考查数据结构基础知识。
    将序列中的元素以完全二叉树的方式呈现,满足小顶堆的条件为ki≤k2i且ki≤k2i+1,其中的ki2i、k2i+1正好形成父结点、左孩子和右孩子的关系,很容易判断其是否满足堆的定义。
    题中选项A、B和C的序列如下图所示,树中每个非叶子结点都不大于其左孩子结点和右孩子结点,因此都是小根堆。

    选项D中序列对应的完全二叉树如下图所示,其中40大于其右孩子39,因此不是小根堆。
转载请注明原文地址:https://jikaoti.com/ti/8jI7FFFM
0

随机试题
最新回复(0)