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有点多想说几乎都选择就一口气写完, 问题蛮多的麻烦各位大神了

资结B是不是都会偷考到算法？ 可是电机丙不考算法不是吗？

dominating set 是 NPC，但是 104 第六题是问 dominator虽然名字像 但是定义完全不同

台大电机丙考题风格还特别的 有考些离散及算法

106等我写完再一起对答案吧

105第13题D选项可以是他其中之一的postorder

104. 15(C) tree root的height 不是应该是0吗？104. (D)(E)可以稍微解释一下你是怎么想的吗？谢谢https://imgur.com/47AiJUp104 16(D)(E) F大在别的板有这样解释，我觉得蛮合理