[問題] 資結－是非題..

看板Grad-ProbAsk作者 (Terry)時間17年前 (2009/04/05 04:49), 編輯推噓2(2推 0噓 3→)
留言5則, 1人參與, 最新討論串1/3 (看更多)
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
推
04/05 09:08, , 1F
第一題，不太清楚的時候建議自己畫個圖看看喔
04/05 09:08, 1F
→
04/05 09:09, , 2F
第二題，BST TAKES logn time 而heap最差的情況為將所有
04/05 09:09, 2F
→
04/05 09:09, , 3F
key 值都search過後才找到目標key，所以為 O(n)
04/05 09:09, 3F
→
04/05 09:10, , 4F
我想你是將BST的search time 記成nlogn囉
04/05 09:10, 4F
推
04/05 09:12, , 5F
第一題回在下面囉
04/05 09:12, 5F
‣ 更多 bernachom 的文章
文章代碼(AID): #19ryU-sK (Grad-ProbAsk)
‣ 更多 bernachom 的文章
文章代碼(AID): #19ryU-sK (Grad-ProbAsk)