[理工] [資結] 98台大電機

看板Grad-ProbAsk作者 (有錢低調56)時間14年前 (2011/12/13 01:27), 編輯推噓2(2推 0噓 2→)
留言4則, 1人參與, 最新討論串1/3 (看更多)
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/098/098398.pdf 13. (C)想請問一下這create heap是O(n)嗎 (E)請問一下為什麼不是O(n)? 如果剛好是skew-tree的話 最差的情況 不就要搜尋height = n 才能找到插入位置嗎@@? 16. (A)這我真的不知道要不要選 如果想成把空鍊結也看成黑色的話要選 但這敘述...!? 17. (E)這選項有點卡 這怎麼算的阿 --- 麻煩各位解答一下Orz 謝謝各位@@ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.116.13.191
推
12/13 08:09, , 1F
13.min heap為complete binary tree 不會有skewed
12/13 08:09, 1F
→
12/13 08:10, , 2F
create heap有兩種 top-down o(nlogn)
12/13 08:10, 2F
→
12/13 08:10, , 3F
bottom up為o(n)
12/13 08:10, 3F
推
12/13 08:15, , 4F
16 應該是對的 不能有連續紅節點存在 所以子點為黑色
12/13 08:15, 4F
...我好想撞牆我竟然忘了heap是complete tree這麼基本的東西T______T 謝謝!!解答! ※ 編輯: RichLowkey56 來自: 122.116.13.191 (12/13 10:19)
‣ 更多 RichLowkey56 的文章
文章代碼(AID): #1EvZbh8s (Grad-ProbAsk)
‣ 更多 RichLowkey56 的文章
文章代碼(AID): #1EvZbh8s (Grad-ProbAsk)