下标从1开始,在含有n个关键字的小根堆(堆顶元素最小)中,关键字最大的记录有可能存储在()位置上
A. [n/2]
B. [n/2]-1
C. 1
D. [n/2]+2
最大值在叶子结点上也就是n/2+xxx
小根堆中最大的数一定是放在叶子节点...
用户登录可进行刷题及查看答案
小根堆中最大的数一定是放在叶子节点上,堆本身是个完全二叉树,完全二叉树的叶子节点的位置大于[n/2]
首先要明白:中括号取整,就是不大于这个数的最大整数
第二要看清下标是从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了,但是人家说的是可能。只要具备可能性就行了。
登录后提交答案