首页 线上实习 课程 找实习 必考题 咨询 专栏 组团学 稳拿计划
校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 堆排序
题目

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

A.[n/2]

B.[n/2]-1

C.1

D.[n/2]+2

上一题 下一题
解答

正确答案是 D

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

C 10条回复 评论
一圓江月

我想学习黑客，但是我没有文化

发表于 2024-08-07 22:00:00
0 0
清廉阁老周延儒

太强了，学完框架再回来看

发表于 2024-04-03 21:00:00
0 0
窦先生

只要是叶子节点就有可能，因为下标从1开始，最后一个叶子节点一定是[n/2]，所以只要大于[n/2]即可

但是考虑到存在问题，其实[n/2]+1是最好的答案，因为 [n/2]+1一定存在，其他大于 [n/2]的可能不存在

发表于 2018-10-13 15:29:58
0 0
遇见

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

发表于 2018-10-13 15:29:33
0 0
碧海问舟

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

发表于 2018-10-13 15:29:24
0 0
王王王

遇到这种题我都是画个最简单的模型算的，比如只有三个节点的，，哈哈哈

发表于 2018-10-13 15:29:13
0 0
小洁癖

堆是一个完全二叉树，最有可能在最后一个父亲节点的左子树的位置上，因为数组从0开始计数，最后一个父亲节点所在位置为n/2+1,其左子树位置n/2+2

发表于 2018-10-13 15:29:05
0 0
几米的思维

举例子还简单作对这道题

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

发表于 2018-10-13 15:28:55
0 0
星辰大海

小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于[n/2]+2 的结点上

发表于 2018-10-13 15:28:46
0 0
岁月长歌

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

第二要看清下标是从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了，但是人家说的是可能。只要具备可能性就行了。

发表于 2018-10-13 15:28:35
0 0
问题信息
分类：数据结构 - 堆排序
难度:
最新校招难题刷题，快来进刷题群吧
相关试题