[理工] 台大電機丙 資結 104/105/106 對答案

[a020304888a (張小台)]

Hi 大家早

昨日寫了近3年的資結

由於年份較近的考古題答案不太好找

想跟大家對一下答案順便討論

在此附上考題連結 (p.s.剛剛縮址不知道為啥縮不了 晚點再修)

106:
http://140.112.115.12/exam/sites/default/files/exam/graduate/106g/106_graduate_407.pdf

105:
http://140.112.115.12/exam/sites/default/files/exam/graduate/105/414_2016_graduate.pdf

104:
http://140.112.115.12/exam/sites/default/files/exam//graduate/104/417_104graduate.pdf

以及附上我個人檢討過+網路上的答案

106年討論很少 我個人寫的應該有不少錯誤請見諒= =

106:

是非 (A:True B:False)
 1.A
 2.B
 3.A
 4.B
 5.B
 6.B
 7.A
 8.A
 9.A
10.B

複選
11.C
12.D(E)
     E選項不知道該不該選, 爬文有人提到可以在O(N)甚至O(1)完成

13.AB
14.E
15.E
     我用Lazy merge下去想的

16.BE


105:

是非 (A:True B:False)
 1.B
 2.B
 3.A
 4.B
 5.B
 6.A
 7.A
 8.B 此題有人說是A 不過我個人覺得是B, 空樹插入三個點蠻好找到一黑兩紅
 9.A
10.B

單選
11.C 乍看之下以為是不可能產生這樣的結果,
     仔細看是在問中間經過什麼運算可以產生這樣的結果

12.C
13.E
14.E


非選

(三)很常見的比較, 課本網路上很多

(五)考undirected的SCC, 前面有文章討論過這邊也不多說明

主要是想討論第(四)題, 不知道大家有什麼看法
我個人想到的就使用min heap 或 fibonacci heap
不知道對不對 有請大大開示



104:

是非
 1.B
 2.B
 3.B
 4.B
 5.A
 6.A 這題不是很懂, dominator set不是 NPC嗎
     可是看到有人說可以用拓譜排序在O(N)完成
 7.B
 8.A
 9.A
10.A 這題我覺得好像出錯了
     top down我記得演算法定義至少要從2-3-4 tree開始
     bottom up才是從2-3 tree, 所以這題用top down是畫不出來的

複選
11.ABCDE
     這題A選項我覺得要看題目指的_last是 pointer 還是 data,
     我認為是data所以就選了

12.ACE
13.DE
14.CE
15.D
16.DE
     B選項是問最大clique個數還是最大的那個clique是幾個點?
     D,E不知道在問什麼= =



一次po有點多想說幾乎都選擇就一口氣寫完, 問題蠻多的麻煩各位大神了


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.235.17.57
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1515200589.A.552.html
→ V1V1V1V1V1V: 資結B是不是都會偷考到演算法？  可是電機丙不考演算
→ V1V1V1V1V1V: 法不是嗎？
推 FRAXIS: dominating set 是 NPC，但是 104 第六題是問 dominator
→ FRAXIS: 雖然名字像 但是定義完全不同
→ a020304888a: 台大電機丙考題風格還特別的 有考些離散及演算法
→ howard31622: 106等我寫完再一起對答案吧
推 hank292: 105第13題D選項可以是他其中之一的postorder
推 PunchShadow: 104. 15(C) tree root的height 不是應該是0嗎？
→ PunchShadow: 104. (D)(E)可以稍微解釋一下你是怎麼想的嗎？謝謝
→ PunchShadow: https://imgur.com/47AiJUp
→ PunchShadow: 104 16(D)(E) F大在別的板有這樣解釋，我覺得蠻合理
推 sfriend: 106.11我做完還有選(d) (a)做1次rotation (b)b是root 嗎
→ sfriend: 106.14我選c沒選e 我都用十進位算<<8就乘256 不知道對否
推 zuchang: 回一下105的13因為是bst  所以中序確定是12345 D不能選