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