Re: [理工] 109台大電信資演對答案

[jimmylin1024 (shibaLover)]

※ 引述《shashayou ()》之銘言：

: 一、T/F
:     1-5: T/T/F/T/T
:     6-10:T/T/T/T/T
1我覺得是F，題目改成at least k edges就會是T了
67都是F，Dijkstra只會relax每個edge一次，這樣才會保證這個algorithm的正確性，也是
為什麼不能有負邊的原因。7的話，如果從s到某個v不會經過negative cycle的話，
bellman ford就會算出正確的shortest path distance。
9應該是F，如果vertex t和s之間的邊數小於|V| - 1，且t在negative cycle上，cycle邊
數也小於|V| - 1，則經過|V|-1次relaxation後，s到t的shortest path不會是acyclic的
: 二、單選
:     11-15:CACBC
14題我覺得是A，binomial heap insertion amortized是O(1)，所以O(logn) consecutive
insertion就會是O(logn)
:     16-20:CCACA
:     21-25:CCCBB
:     26-30:DDCDB
29題是B，h是n^n，一定是最大的
:     31-35:DBADB
32題是A，題目描述的case是quicksort的worst case O(n^2)，insertion sort的best case
O(n)
34題我寫C，我選index 1 5 8 9四個job，想問你選的是哪幾個？

:     36-40:BDBCB
37題選項只有AB，我選B
39題是D，S[2] = 11，因為40 + 70 = 110，所以一定得在x1加油，所以total cost會是
5 + 6 = 11
:     41-42:AC
41 42我寫BD，就是按照36題的遞迴式去算的，想知道你是怎麼算的
: 三、多選
:     43:BD
:     44:ABCDE
CE，splay tree是amortized才會是O(logn)
:     45:ACDE
:     46:ABCDE
:     47:BCE
:     48:ABE
48的Ｃ選項根據AA tree的定義是對的吧？
:     49:ABCDE
BST應該只support ABC，Find-min跟delete-min是priority queue才support
:     50:CD
50題我覺得沒有答案，C的話，15在decrease key後會被往上提，他的parent12 因為已經被marked了
所以也會往上提，總共會是3顆tree
D, delete-min後要merge degree相同的tree，root 14, 8的兩顆tree degree都是1
merge完後只會剩下一顆tree

: 麻煩指教，謝謝～

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.168.140.109 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1609654945.A.1DB.html
→ jimmylin1024: 題目支援：https://exam.lib.ntu.edu.tw/sites/defa
→ jimmylin1024: ult/files/exam//graduate/109/414_graduate-109.pd
→ jimmylin1024: f
※ 編輯: jimmylin1024 (118.168.140.109 臺灣), 01/03/2021 14:27:10
※ 編輯: jimmylin1024 (118.168.140.109 臺灣), 01/03/2021 14:35:28
推 shashayou: dp題組我誤會題意了，重算一次後跟你一樣
推 shashayou: 今早跟別人討論過這整份的題目了 答案跟你一樣，謝謝
→ shashayou: 祝考試順利
→ jimmylin1024: 感謝s大，考試加油！
→ aa871220: 50有答案吧
→ aa871220: 我寫ab
推 z000000000: 想請問47題，D選項的splay tree不算是balanced tree嗎
→ z000000000: ？
→ aa871220: Splay tree tree height會到O(N)
→ aa871220: 怎麼會是balanced..
推 waes81224: 想問 37 題我覺得是A，他寫說 arrives at a gas sta
→ waes81224: tion，所以他還沒有在那個點進行補充，所以不用考慮
→ waes81224: t[a]吧？
推 JOKER9931: 雖然現在回好像有點晚了@@ 第19題我覺得是D,翻原文書上
→ JOKER9931: 寫Delete-min與Delete的Actual condition(=worst) 是O(
→ JOKER9931: n)