[理工] [DS]清大99 第9跟 第12

[aoqq12 (阿任)]

http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/99/1901.pdf


第九題是要求什麼?

(1)O(n^2) n=人數

(2) ?

(3) ?

(b)..阿災= =


第十二題

這是要找出每個spanning tree 來比最小的diameter

還是說有比較快的方法能找呢?


另外問個第10題 binary tree 刪掉點要怎麼調整


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 123.204.97.149
→ dy957:(b)應該是n用2^30帶入nlogn 再除以速率求時間吧
推 cakeboy:BST找左邊最大或右邊,移到root就好
→ aoqq12:疑 可是他不是找minimun diameter 從下面的圖嗎
→ aoqq12:所以要從下面那個圖找spanning tree
→ aoqq12:還是我搞錯意思= =
→ aoqq12:喔喔(b)懂了 感謝XD