首页 > 试题广场 >

序列{49, 33, 55, 80, 20, 15, 49}

[单选题]

序列{49, 33, 55, 80, 20, 15, 49}用堆排序使其递增,输出第一个数后,调整之后新堆的层序遍历是()

  • 20, 55, 49, 80, 30, 49
  • 20,33,49,80,49,55
  • 20, 49, 49, 30, 80, 55
  • 20, 30, 49, 49, 55, 80
讲道理,我做出来的结果是20,33,49,80,49,55,实在没这个选项,就蒙了一个相近的,竟然对了。。。。
发表于 2018-07-27 15:43:44 回复(8)
堆排序递增就是升序,根据选项用最小堆。
用二叉树初始化序列,并调整为最小堆(调整为最小堆可参考:https://blog.csdn.net/qq_38038143/article/details/89811319

题中输出第一个数后,即删除根节点(15),根据堆的特点,将最右下叶节点(49)移动到根节点,再次调整为最小堆:

所以,层序遍历:20 33 49 80 49 55 
编辑于 2019-05-08 19:30:06 回复(0)
首先,升序一般用大根堆做,降序用小根堆做。这题是升序,但是选项却都是小根堆的选项。
其次,即使用小根堆做,也没有正确选项。应该是 20,33, 49,80,49, 55才对。
发表于 2018-10-01 14:05:19 回复(1)

🙃🙃🙃33哪里去了?30咋弄出来的?wtm

发表于 2018-10-26 15:48:09 回复(0)
选B
发表于 2020-07-19 07:21:14 回复(0)
递增是从小到大,先输出小的,用小顶堆
发表于 2019-10-13 09:55:27 回复(0)
堆的生成:从最后一个非叶节点开始逐个向下过滤。
发表于 2019-03-09 15:41:13 回复(1)
递增,所以用大根堆,在所有节点都依次筛选过之后原数组中的值呈增序状态。所以应该是55,49,49,33,20,15
发表于 2018-12-09 10:22:51 回复(1)
递增不是大根堆吗?但是这样做出来完全不对,所以用小根堆做,然而出的结果是20,30,49,80,49,55,简直呵呵
发表于 2018-08-31 16:58:23 回复(0)
虽然做对了,但感觉这题有问题,直接屏蔽这题
发表于 2018-08-17 22:47:14 回复(0)
神TM 30
发表于 2018-08-10 10:22:08 回复(0)