判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。 (1){ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }(2){ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }

题目

判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。 (1){ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }

(2){ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }

相似考题

1.一堆钢管，最上层有5根，最下层有21根，如果自然堆码，这堆钢管最多能堆（ ）根。A．208B．221C．416D．442

2.对于n个元素的关键字序列{k1，k2，…，kn}，当且仅当满足关系ki≤k2i，且ki≤k2i+1(2i≤ n,2i+1≤n)称其为小根堆，反之则为大根堆。以下序列中，(56)不符合堆的定义。A．(4,10,15,72,39,23,18)B．(58,27,36,12,8,23,9)C．(4,10,18,72,39,23,15)D．(58,36,27,12,8,23,9)

3.一组记录的关键字序列为(40,80,65,100,14,30,55,50),利用堆排序的方法建立的初始小根堆为()。A.40，14，30，50，80，65，55，100B.40，80，65，50，14，30，55，100C.14，40，30，50，80，65，55，100D.40，80，30，50，14，65，55，100

4.已知序列{11,19,5,4,7,13,2,10}(1)试给出用归并排序法对该序列作升序排序时的每一趟的结果。(2)对上述序列用堆排序的方法建立初始堆(要求小根堆,以二叉树描述建堆过程)。

参考答案和解析
正确答案：(1)不是小根堆。调整为：{12,24,33,65,33,56,48,92,86,70}
(2)是小根堆。
更多“判断以下序列是否是小根堆? 如果不是,将它调整为小根堆。 (1){ 12, 70, 33, 65, 24, 56, 48, 92 ”相关问题

  • 第1题：

    对于序列{26,33,35,29,19,12,22}, (1)判断它是否是堆,若是,写出其是大顶堆还是小顶堆;若不是,把它调整为堆,写出调整的过程和调整后的序列。 (2)写出对该序列进行直接插入排序每一趟结束时的关键字状态。


    参考答案：

  • 第2题：

    对于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不符合小根堆的定义。

  • 第3题：

    对于n个元素的关键字序列K1，K2，…，Kn，若有Ki≤K2i≤且Ki≤2i+1(i=1，2，…，[n/2]，2i+1≤n)，则称其为小根堆。以下关于小根堆及其元素关系的叙述中，错误的是( )。

    A．关键字序列K1，K2，…，Kn呈非递减排序时一定为小根堆

    B．小根堆中的序列K1，K2，K4…，K2j(2j≤n)一定为非递减序列

    C．小根堆中元素K2i与K2i+1(2i≤n，2i+1≤n)之间的大小关系不能确定

    D．小根堆的最后一个元素一定是序列的最大元素


    正确答案：D
    解析：小根堆中元素比它本身的根小，它和它的兄弟没有大小关系。

  • 第4题：

    中从任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。

    A．二叉排序树

    B．大顶堆

    C．小顶堆

    D．最优二叉树


    正确答案：C

  • 第5题：

    对于n个元素的关键码序列{k1，k2，…，Kn}，当且仅当满足下列关系时称其为堆。以下关键码序列中，（ ）不是堆。

    A.12, 25, 22, 53, 65, 60, 30 B.12, 25, 22, 30, 65,60, 53C.65, 60,25, 22, 12, 53, 30 D.65,60, 25, 30, 53, 12,22


    正确答案：C

  • 第6题：

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

    A.12, 20, 36, 48, 25, 50, 40
    B.12, 36, 20, 48, 40, 25, 50
    C.12, 20, 25, 36, 40, 48, 50
    D.12, 36, 20, 48, 25, 50, 40

    答案：D
    解析：
    在完全二义树中对结点可如下编号：根结点为1号，其左孩子结点为2号，右孩子结点为3号,对于编号为i的结点，其左孩子结点若存在，则编号为2i,其右孩子结点若存在，则编号为2i+1。可将序列中的元素放入一棵完全二叉树上进行判断，如下图所示。

    根据堆的定义，可知选项D不是堆。

  • 第7题：

    下列序列中，满足堆定义的是()。

    A.(100，86，48，73，35，39，42，57，66，21)
    B.(12，70，33，65，24，56，48，92，86，33)
    C.(103，97，56，38，66，23，42，12，30，52，6，26)
    D.(5，56，20，23，40，38，29，61，36，76，28，100)

    答案：A
    解析：
    n个元素的序列{K1，K2，…，Kn}当且仅当满足下面关系：Ki＜=K2i和Ki＜=K(2i+1)或者Ki＞=K2i和Ki＞K(2i+1)时，称之为堆。B项，其构成的是小顶堆，70和24之间不满足小顶堆性质；C项，其构成的是大顶堆，23和26不满足大顶堆性质；D项，其构成的是小顶堆，56和23，40和28不满足小顶堆性质。A项对应的是大顶堆，满足大顶堆性质。

  • 第8题：

    利用筛选法，把序列{37，77，62，97，11，27，52，47}建成堆（小根堆），画出相应的完全二叉树，并写出对上述堆所对应的二叉树进行前序遍历得到的序列。
    （1）

    （2）11，37，47，97，77，27，62，52
    略

  • 第9题：

    已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是（）

    • A、3，5，12，8，28，20，15，22，19
    • B、3，5，12，19，20，15，22，8，28
    • C、3，8，12，5，20，15，22，28，19
    • D、3，12，5，8，28，20，15，22，19

    正确答案:A

  • 第10题：

    在一个小根堆中，堆顶结点的值是所有结点中的（），在一个大根堆中，堆顶结点的值是所有结点中的（）。


    正确答案:最小值；最大值

  • 第11题：

    填空题
    在一个小根堆中，堆顶结点的值是所有结点中的（），在一个大根堆中，堆顶结点的值是所有结点中的（）。

    正确答案： 最小值,最大值
    解析： 暂无解析

  • 第12题：

    单选题
    假定对元素序列（7， 3， 5， 9， 1， 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（）。
    A

     1， 3， 5， 7， 9， 12

    B

     1， 3， 5， 9， 7， 12

    C

     1， 5， 3， 7， 9， 12

    D

     1， 5， 3， 9， 12， 7


    正确答案： D
    解析： 暂无解析

  • 第13题：

    判断以下序列是否是堆,若不是,把它调整为堆(要求记录交换次数最少),写出调整后的序列。 1){5,26,20,60,80,35,53,70} 2){26,33,35,29,19,12,22}


    参考答案：第一个序列是堆
    　　第二个序列不是堆。调整为堆后的序列为{35，33，26，29，19，12，22}

  • 第14题：

    下面各序列中，只有(60)不是小顶堆。

    A．(16，18，32，65，43，57，66)

    B．(9，21，34，35，47，66，37)

    C．(17，22，56，77，36，39，58)

    D．(31，46，50，88，67，101，92)


    正确答案：C
    解析：小顶堆要求序列中的元素满足ki=k2i且ki=k2i+1，可以将序列用一个完全二叉树表示出来，所有非终端结点的值要不大于其左右孩子结点的值。

  • 第15题：

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

    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个选项的序列中元素放入一棵完全二叉树，如图1-7所示，以便于观察节点ki、k2i、k2i+1≤n,2i+1≤n)之间的关系。按照小根堆的定义检查选项A、B的二叉树，按照大根堆的定义检查选项C、D的二叉树，显然，选项B不符合小根堆的定义。

  • 第16题：

    对于n个元素的关键宇序列{k1,k2, ...kn}，当且仅当满足关系ki≤k2i且ki≤k2i+1{i=1.2...[n/2]} 时称其为小根堆(小顶堆)。以下序列中，（ ）不是小根堆。

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


    正确答案：D

  • 第17题：

    一堆钢管，最上层有5根，最下层有21根，如果自然堆码，这堆钢管最多能堆（ ）根。

    A. 208

    B. 221

    C. 416

    D. 442


    正确答案：B

    如果是自然堆码，最多的情况是：每相邻的下一层比它的上一层多1根，即构成了以5为首项，1为公差的等差数列，故可知21为第17项，从而这堆钢管最多能堆（5+21）×17/2＝221(根)。

  • 第18题：

    在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储的位置是()。


    答案：D
    解析：

  • 第19题：

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

    A.12,20,36,48,25,50,40
    B.12,36,20,48,40,25,50
    C.12,20,25,36,40,48,50
    D.12,36,20,48,25,50,40

    答案：D
    解析：
    在完全二义树中对结点可如下编号：根结点为1号，其左孩子结点为2号，右孩子结点为3号,对于编号为i的结点，其左孩子结点若存在，则编号为2i,其右孩子结点若存在，则编号为2i+1。可将序列中的元素放入一棵完全二叉树上进行判断，如下图所示。



    根据堆的定义，可知选项D不是堆。

  • 第20题：

    利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）并写出对上述堆对应的完全二叉树进行中序遍历得到的序列。
    （1）

    （2）102，52，42，82，16，67，32，57
    略

  • 第21题：

    假定一组记录为（46，79，56，38，40，84），则利用堆排序方法建立的初始小根堆为（）


    正确答案:(38,40,56,79,46,84)

  • 第22题：

    判断题
    在堆中，以任何结点为根的子树仍然为堆。
    A

    对

    B

    错


    正确答案： 对
    解析：

  • 第23题：

    填空题
    假定一组记录为（46，79，56，38，40，84），则利用堆排序方法建立的初始小根堆为（）

    正确答案： (38,40,56,79,46,84)
    解析： 暂无解析

相关内容