作者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