一个数据结构题

Sean__xh

把数组中100个元素调整为小根堆，需要多少次关键字比较
a 164
b 195
c 220
d 257

来自Android客户端

liuzuhagn

不知道这题的背景是用的哪个创建堆算法。
根据我掌握到的堆创建算法，这题应该问至少或者至多的关键字比较次数。
1、至少的情况，即已经是最小堆，从有子节点的节点开始调整，即从100/2 = 50号开始调整，每个节点与它的两个子节点比较完即结束(因为已经是最小堆，故子节点均比父节点大)，又由于50号只有一个子节点(由堆逻辑上是完全二叉树算的)，故至少49*2+1 = 99次关键字比较。这样是没有答案符合的。
2、至多情况下，画图算，18*2+1+6*2+3+9*4+3*4+5*6+6+3*8+2*10+12 = 192，也没有这个选项。如果50号节点也算成是两次比较那就是195。选B

不知道这题标准答案是啥，如果我错了，一定要告诉我啊啊啊啊……

来自Android客户端

liuzuhagn

评论又进入审核了……神烦……

来自Android客户端

Sean__xh

liuzuhagn 发表于 2015-11-12 10:24
不知道这题的背景是用的哪个创建堆算法。
根据我掌握到的堆创建算法，这题应该问至少或者至多的关键字比较 ...

问题就在于没有答案，= =，只有题，应该是范围内的一个数，我不是很确定范围的上限

来自Android客户端

hrhseven

liuzuhagn 发表于 2015-11-12 10:25
评论又进入审核了……神烦……

你是哪个学校？考哪哦？

来自iPhone客户端

liuzuhagn

hrhseven 发表于 2015-11-13 18:05
你是哪个学校？考哪哦？

大连海事大学，大连理工大学

来自Android客户端

hrhseven

liuzuhagn 发表于 2015-11-13 18:53
大连海事大学，大连理工大学

408么？冲刺有什么资料哈？我825

来自iPhone客户端

liuzuhagn

hrhseven 发表于 2015-11-13 18:55
408么？冲刺有什么资料哈？我825

大工改成810自主命题了，没有冲刺资料，就看了课本+王道单科

来自Android客户端

hrhseven

貌似很厉害的样子 这个至多比较次数怎么算的不是很明白求教

来自iPhone客户端

hrhseven

小帅哥 在计算机系统结构有个帖子呜呜

来自iPhone客户端