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

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

admin2018-04-19  83
问题 对于n个元素的关键字序列{k1，k2，…，kn}，  当且仅当满足关系ki≤2i且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，其中的ki与2i、k2i+1正好形成父结点、左孩子和右孩子的关系，很容易判断其是否满足堆的定义。
    题中选项A、B和C的序列如下图所示，树中每个非叶子结点都不大于其左孩子结点和右孩子结点，因此都是小根堆。

    选项D中序列对应的完全二叉树如下图所示，其中40大于其右孩子39，因此不是小根堆。
转载请注明原文地址:https://kaotiyun.com/show/2iWZ777K
本试题收录于： 多媒体应用设计师上午基础知识考试题库软考中级分类
0

多媒体应用设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)