我要招人

去企业版

首页 > 试题广场 >

在堆排序算法中我们用一个数组A来模拟二叉树T，如果该A[0]

[单选题]

在堆排序算法中我们用一个数组A来模拟二叉树T，如果该A[0]存放的是T的根节点，那么A[K](K>0)的父亲节点是

```
(K-1)/2
```
```
K/2
```
```
(K+1)/2
```
```
都不对
```

查看答案及解析

推荐

陋室

我觉得答案是A
一般堆排序的话我们都把A[0]作为一个哨兵，不存储实际数据，此时（父节点=子节点/2），而题目要求是A[0]存放的是根节点，则我们可以用相同的转换（父节点=（子节点-1）/2）。
这种类型的题建议直接画图就能看出来。

编辑于 2015-07-30 16:53:29 回复(5)

Erya_尔雅

由于根节点是从0开始存储，因此父节点 i 的左孩子为 2*i+1，右孩子为 2*i+2。

故当孩子节点为k时要分情况讨论，此时设父节点为x

1,k为左孩子

2*x+1=k 解得：x=(k-1)/2

2,k为右孩子

2*x+2=k 解得：x=(k-2)/2

发表于 2015-12-11 11:28:27 回复(7)

AndyJee

当数组从0开始时，下标为k的结点的父结点下标为(k-1)/2；

当数组从1开始时，下标为k的结点的父结点下标为k/2；

发表于 2015-07-30 13:30:17 回复(0)

生生不息志存千里

发表于 2017-08-19 08:03:33 回复(0)

Immanual9402

严格来说，缺乏取整运算

发表于 2017-05-03 16:24:37 回复(0)

zhisheng_blog

这种题目就是自己画个图，然后算一下就可以出答案的。（考试技巧）

发表于 2016-08-18 21:27:20 回复(0)

dragonhaw

堆是完全二叉树，完全二叉树K的父节点为(K - 1) / 2。

但是不懂为什么堆排序的堆结构还是以层来标记节点标号的。

发表于 2017-04-08 21:45:45 回复(0)

Z皓

把k=1代进去直接得答案啊

发表于 2017-11-25 16:38:29 回复(0)

luckychenfan

k为奇数，父结点是：(k-1)/2;

k为偶数，父结点是：(k-2)/2.

发表于 2017-02-25 17:41:17 回复(0)

武汉孙一峰

2333333333~，，，，我选错了，根节点是从0开始的。

发表于 2016-08-31 14:20:14 回复(0)

DY后生

不应该有取整的那个符号么。。。

发表于 2016-04-20 20:37:23 回复(1)

小🐮客

简单方法：

假设堆排序码为（A, B, C); 那么 B 和 C 的父节点就是 A 啦。

A 的索引为 0，B 和 C 的索引分别为 1、2，代进去运算就 😃😁

发表于 2019-09-22 15:32:50 回复(0)

后生仔、666

一般A[0]为空，用于暂存数值，而题目说A[0]存放根结点，所以是(k-1)/2

发表于 2019-08-26 16:00:37 回复(0)

嗷嗷_

特殊例子代入法

发表于 2019-01-07 11:10:25 回复(0)

Ramon_and_I

有疑问啊！A[0]存放的是T的根节点，那么A[K](K>0)的父亲节点是：

1 2

3 4 5 6

如上所示：3的父节点是（3-1）/ 2，4的父节点是（4-2）/ 2，按照规律，A[K](K>0)的父亲节点应该是 A [(K-1)/2取下整] .

编辑于 2018-10-03 20:15:55 回复(0)

黑翅膀的白天使

如果二叉树从1,2,3,…,n进行编号，则节点i 的父节点编号为[i/2]（向下取整）；
如果二叉树从0,1,2,…,m进行编号，则节点i的父节点编号为[(i-1)/2] (向下取整)；

发表于 2018-03-13 14:33:25 回复(0)

梦境迷离

二叉堆简称堆必为完全二叉树，这是堆的结构性同时堆还必须满足堆序性

编辑于 2017-12-15 21:09:46 回复(0)

孤单的跟鞋声和你的笑丶

严格来说没答案。。。。别争了

发表于 2017-11-21 21:04:24 回复(0)

努力努力再努力max

代入一些简单数据即可得A。但如果要知其所以然的话，我的理解如下：

在A[1]存储根节点时，A[K+1]的父节点毫无疑问是A[(K+1)/2]。

在这道题里，A[0]存储根节点，则相当于整体左移，因此，A[K+1]现在往左移了一位，变成A[K]，那么它的父亲也应该由原来的A[(K+1)/2]往左移一位，也就是

(K+1)/2-1=(K-1)/2

所以，答案选择A。

发表于 2017-09-12 15:39:38 回复(0)

jokervsbat

只有完全二叉树可以，但题目并没有说是完全二叉树

发表于 2017-08-14 18:20:02 回复(0)

sunlight_run

1 2

3 4 5 6 从这里可以看得出来是A选项

发表于 2017-06-27 14:51:03 回复(0)

提交观点

问题信息

谷歌树堆排序

上传者：三间雀

难度：

37条回答 534收藏 15824浏览

在堆排序算法中我们用一个数组A来模拟二叉树T，如果该A[0]

问题信息

热门推荐

相关试题