作者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/cn.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