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有點多想說幾乎都選擇就一口氣寫完, 問題蠻多的麻煩各位大神了