作者jimmylin1024 (shibaLover)
看板Grad-ProbAsk
標題Re: [理工] 109台大電信資演對答案
時間Sun Jan 3 14:22:23 2021
※ 引述《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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1609654945.A.1DB.html
2F：→ jimmylin1024: ult/files/exam//graduate/109/414_graduate-109.pd 01/03 14:24
3F：→ jimmylin1024: f 01/03 14:24
※ 編輯: jimmylin1024 (118.168.140.109 臺灣), 01/03/2021 14:27:10
※ 編輯: jimmylin1024 (118.168.140.109 臺灣), 01/03/2021 14:35:28
4F：推 shashayou: dp題組我誤會題意了，重算一次後跟你一樣 01/03 16:39
5F：推 shashayou: 今早跟別人討論過這整份的題目了 答案跟你一樣，謝謝 01/03 16:45
6F：→ shashayou: 祝考試順利 01/03 16:47
7F：→ jimmylin1024: 感謝s大，考試加油！ 01/03 17:51
8F：→ aa871220: 50有答案吧 01/08 20:49
9F：→ aa871220: 我寫ab 01/08 20:49
10F：推 z000000000: 想請問47題，D選項的splay tree不算是balanced tree嗎 01/22 22:53
11F：→ z000000000: ？ 01/22 22:53
12F：→ aa871220: Splay tree tree height會到O(N) 01/25 01:29
13F：→ aa871220: 怎麼會是balanced.. 01/25 01:29
14F：推 waes81224: 想問 37 題我覺得是A，他寫說 arrives at a gas sta 01/25 21:00
15F：→ waes81224: tion，所以他還沒有在那個點進行補充，所以不用考慮 01/25 21:00
16F：→ waes81224: t[a]吧？ 01/25 21:00
17F：推 JOKER9931: 雖然現在回好像有點晚了@@ 第19題我覺得是D,翻原文書上 01/30 13:19
18F：→ JOKER9931: 寫Delete-min與Delete的Actual condition(=worst) 是O( 01/30 13:19
19F：→ JOKER9931: n) 01/30 13:19