作者bernachom (Terry)
看板Grad-ProbAsk
标题[问题] 资结－是非题..
时间Sun Apr 5 04:49:01 2009
1. For a complete binary tre represented in memory as an array,if there is
a node at index 4i+3 it must be a child of a child (grandchild) of the
node at i.
2. Searching for a key in a heap takes worst-case time O(n).
解答写： 1.T 2.T
第一题我不太清楚...
第二题最差的case 不是应该为nlogn才是吗?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.99.70
1F：推 ixjnpns:第一题，不太清楚的时候建议自己画个图看看喔 04/05 09:08
2F：→ ixjnpns:第二题，BST TAKES logn time 而heap最差的情况为将所有 04/05 09:09
3F：→ ixjnpns:key 值都search过後才找到目标key，所以为 O(n) 04/05 09:09
4F：→ ixjnpns:我想你是将BST的search time 记成nlogn罗 04/05 09:10
5F：推 ixjnpns:第一题回在下面罗 04/05 09:12