我要招人

去企业版

首页 > 试题广场 >

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

[单选题]

下标从1开始,在含有n个关键字的小根堆(堆顶元素最小)中,关键字最大的记录有可能存储在()位置上

```
[n/2]
```
```
[n/2]-1
```
```
1
```
```
[n/2]+2
```

查看答案及解析

好不好你知道

小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]

编辑于 2021-01-15 21:22:49 回复(4)

晓宇大美女~

首先要明白：中括号取整，就是不大于这个数的最大整数

第二要看清下标是从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

你有考虑过n=2这种情况吗？

发表于 2015-08-29 23:48:53 回复(1)

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

排除法排除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

举例子还简单作对这道题

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

最大记录只可能在叶节点上，取n为2、3、4、5...依次比较得出，位置要大于[n/2]

发表于 2017-06-16 11:07:30 回复(0)

icy_i007

给出 1 2 3 4 5 6 7 ，n=7，根据最小堆规则，根要比左右节点小，所以只可能在4 5 6 7 这几个位置上，排除法

发表于 2017-06-09 11:49:57 回复(0)

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条回答 1132收藏 13975浏览

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

问题信息

热门推荐

相关试题