作者a020304888a (張小台)
看板Grad-ProbAsk
標題[理工] 台大電機丙 資結 104/105/106 對答案
時間Sat Jan 6 09:03:06 2018
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1515200589.A.552.html
1F：→ V1V1V1V1V1V: 資結B是不是都會偷考到演算法？ 可是電機丙不考演算 01/06 16:04
2F：→ V1V1V1V1V1V: 法不是嗎？ 01/06 16:04
3F：推 FRAXIS: dominating set 是 NPC，但是 104 第六題是問 dominator 01/06 16:42
4F：→ FRAXIS: 雖然名字像 但是定義完全不同 01/06 16:43
5F：→ a020304888a: 台大電機丙考題風格還特別的 有考些離散及演算法 01/07 08:16
6F：→ howard31622: 106等我寫完再一起對答案吧 01/07 09:22
7F：推 hank292: 105第13題D選項可以是他其中之一的postorder 01/12 13:40
8F：推 PunchShadow: 104. 15(C) tree root的height 不是應該是0嗎？ 01/15 17:29
9F：→ PunchShadow: 104. (D)(E)可以稍微解釋一下你是怎麼想的嗎？謝謝 01/15 17:30
11F：→ PunchShadow: 104 16(D)(E) F大在別的板有這樣解釋，我覺得蠻合理 01/15 17:38
12F：推 sfriend: 106.11我做完還有選(d) (a)做1次rotation (b)b是root 嗎 01/20 16:56
13F：→ sfriend: 106.14我選c沒選e 我都用十進位算<<8就乘256 不知道對否 01/20 17:04
14F：推 zuchang: 回一下105的13因為是bst 所以中序確定是12345 D不能選 01/14 14:20