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

看板Grad-ProbAsk作者jimmylin1024 (shibaLover)時間5年前 (2021/01/03 14:22)推噓2(2推 0噓 5→)

留言7則, 2人參與討論串2/2 (看更多)

※ 引述《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

01/03 14:24, 5年前 , 1^F

01/03 14:24, 1^F

→

jimmylin1024

01/03 14:24, 5年前 , 2^F

01/03 14:24, 2^F

→

jimmylin1024

01/03 14:24, 5年前 , 3^F

01/03 14:24, 3^F