首页 > 试题广场 >

下标从1开始,在含有n个关键字的小根堆(堆顶元素最小)中,关

[单选题]
下标从1开始,在含有n个关键字的小根堆(堆顶元素最小)中,关键字最大的记录有可能存储在()位置上 
  • [n/2]
  • [n/2]-1
  • 1
  • [n/2]+2
查看答案及解析
添加回答
好不好你知道头像 好不好你知道
小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]
编辑于 2021-01-15 21:22:49 回复(4)
晓宇大美女~头像 晓宇大美女~
首先要明白：中括号取整，就是不大于这个数的最大整数
第二要看清下标是从1开始的。那么
                                          1
                                     2       3
                                4     5   6    7
                              ...............n
n不论是左子树还是右子树，n的父结点一定是 [n/2]，注意中括号的取整规则，正数就是下取整
那么 [n/2] 这个结点还是有子结点的，从 [n/2] + 1 开始一直到 n 都是叶子结点，叶子结点就可能会是最大值，所以选D
看见前边有人回答说没有考虑n ==2 这种情况，诚然，如果n == 2的话，d选项就是3了，但是人家说的是可能。只要具备可能性就行了。
发表于 2016-03-28 11:22:17 回复(1)
furnace90头像 furnace90
你有考虑过n=2这种情况吗？
发表于 2015-08-29 23:48:53 回复(2)
zhisheng_blog头像 zhisheng_blog
小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于[n/2]+2 的结点上。
发表于 2016-08-19 17:42:06 回复(0)
我很绝望啊头像 我很绝望啊
小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]
发表于 2022-06-23 19:29:33 回复(0)
穷极一生做一场梦头像 穷极一生做一场梦
堆是一个完全二叉树，最有可能在最后一个父亲节点的左子树的位置上，因为数组从0开始计数，最后一个父亲节点所在位置为n/2+1,其左子树位置n/2+2
发表于 2017-11-03 20:32:59 回复(1)
revivedSuN头像 revivedSuN
排除法排除ABC
最大的数一定是放在叶子节点上， n/2 非最后一个非叶子结点,因此减1必然不是叶子，而1也必然不是叶子。 
发表于 2015-08-15 00:42:13 回复(0)
笑以头像 笑以
只有一个节点的话算不算堆？那答案C也可以啊，hhh
发表于 2018-11-26 16:20:40 回复(0)
啥头像 啥
只要是叶子节点就有可能，因为下标从1开始，最后一个叶子节点一定是[n/2]，所以只要大于[n/2]即可
但是考虑到存在问题，其实[n/2]+1是最好的答案，因为 [n/2]+1一定存在，其他大于 [n/2]的可能不存在
发表于 2015-12-04 13:05:35 回复(0)
夜悊头像 夜悊
题目中的最有可能，应该指的是四个选项比较中最有可能的
发表于 2022-10-08 00:24:08 回复(0)
辉小歌头像 辉小歌
看该点，可能有没有叶子。 ABC都有叶子，故一定有比该位置还大的数。
发表于 2022-09-06 13:58:48 回复(0)
不做人了头像 不做人了
可能 的位置 就是叶子节点 大于n/2
发表于 2020-05-29 08:56:51 回复(0)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa
举例子还简单作对这道题

1 2 3 的小根堆 D正确
1 2 3 的小跟堆 n/2+1

发表于 2018-06-20 16:24:41 回复(0)
飘过的小牛头像 飘过的小牛
遇到这种题我都是画个最简单的模型算的，比如只有三个节点的，，哈哈哈
发表于 2017-08-29 16:48:31 回复(0)
sunlight_run头像 sunlight_run
最大记录只可能在叶节点上，取n为2、3、4、5...依次比较得出，位置要大于[n/2]
发表于 2017-06-16 11:07:30 回复(0)
icy_i007头像 icy_i007
给出 1 2 3 4 5 6 7 ，n=7，根据最小堆规则，根要比左右节点小，所以只可能在4 5 6 7 这几个位置上，排除法
发表于 2017-06-09 11:49:57 回复(0)
LifeLearning头像 LifeLearning
转发 首先要明白：中括号取整，就是不大于这个数的最大整数 第二要看清下标是从1开始的。那么                                           1                                      2       3                                 4     5   6    7                               ...............n n不论是左子树还是右子树，n的父结点一定是 [n/2]，注意中括号的取整规则，正数就是下取整 那么 [n/2] 这个结点还是有子结点的，从 [n/2] + 1 开始一直到 n 都是叶子结点，叶子结点就可能会是最大值，所以选D 看见前边有人回答说没有考虑n ==2 这种情况，诚然，如果n == 2的话，d选项就是3了，但是人家说的是可能。只要具备可能性就行了。
发表于 2017-02-05 18:19:06 回复(0)
提交观点

问题信息

堆 排序
难度：
17条回答 14401浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号