[理工] [DS]100台大電機丙

[winnie48 (winnie)]

100年題目連結：
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100412.pdf

1. 第10題的E 為什麼是對的 : B-tree的搜尋時間是O(h logm) , 當m增加時，雖然高度h
會變小，但是logm會變大，要怎麼保證時間一定變小呢？況且不管m是多少，space usage
都是O(n) (n是元素個數)？

2. 第16題的C為什麼是錯的：查到clique cover problem 是指圖中的點能被分成幾個cli
que。我畫出來是這樣：
http://i.imgur.com/kJQk5JQ.jpg

還是我哪裡誤會了？
謝謝大家！


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1420766736.A.203.html
推 kather: 1. 我覺得是access disk成本降低 影響遠大於在mem裡search
→ kather: 2. 我畫出來也是3個 囧?
→ kather: edge clique cover=>每邊都要cover到
→ kather: vertex clique cover=>每點
→ kather: 而題目沒說是哪種 假設是兩個都包含(所有邊 所有點)
→ kather: 那就不只了
→ winnie48: 原來clique cover 還分這兩種！謝謝！