※ 引述《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
: 麻烦指教，谢谢～