Re: [理工] 107台大資演對答案

看板Grad-ProbAsk作者Moderator (ㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒx)時間5年前 (2020/01/24 00:47)推噓3(3推 0噓 18→)

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

: http://0rz.tw/fLPOZ : 題目PDF如上又來問這張考卷>"< 想請問題號V.a.2 題目說要用O(n^2)的時間以一個雙邊queue(dequeue)製造max alternative sum -- 我的想法是把input sequence先由小到大sort 然後都往dequeue的一邊push進去最後pop時輪流先從數字大的邊pop 然後小的邊pop 大的邊pop ... 總而言之就是較大的數都是+ 較小的數都是- 最後應該可以製造出optimal alternative sum? 而且耗費的時間應該就是O(nlogn)而非題目上限O(n^2) 不知道這樣的想法有沒有瑕疵(至少題目範例可以成功)...謝謝! ※ 引述《Moderator (ㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒx)》之銘言： : http://0rz.tw/fLPOZ : 題目PDF如上 : 想請問關於樹高 : 下面兩題都在問BINARY TREE樹高 : II(8) : IV(13) : 台大的考卷有公定ROOT高度是1還是0嗎? : 有一說法是ROOT層不會有高度但是眾說紛紜啊@@ : ※ 引述《qscez (天使在身旁 xD)》之銘言： : : 想討論一下答案 : : I. : : EDBCA AC : : II. : : CBA : : III. : : D (討論後更正為B) : : C : : IV. : : CCCC : : V. : : (a) : : (b) : : (1) : : S,T stack : : enque(Q,x){ : : if S是滿的 return "Q滿" : : else push(S,x) : : } : : dequeue(Q){ : : if T空 { : : if S空 return "Q空" : : else pop(S) into T until S空 : : } : : x = pop(T) : : return x : : } : : (2)(3) : : VI. : : (a) 對Va.Vb 做 Dijkastra Time:O(VlogV+E) : : (b) : : (1) : : (2) 一樣做Dijkastra... Time:O(VlogV+E) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.28.142 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579798052.A.C6A.html

→

cossetannie

01/24 01:34, 5年前 , 1^F

01/24 01:34, 1^F

→

cossetannie

01/24 01:34, 5年前 , 2^F

01/24 01:34, 2^F

→

cossetannie

01/24 01:38, 5年前 , 3^F

01/24 01:38, 3^F