作者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/cn.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