作者ccapricorntw (11)
看板Grad-ProbAsk
标题Re: [理工] 台大电机丙 资结 104/105/106 对答案
时间Sat Dec 28 18:11:26 2019
※ 引述《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的部分
: 106:
: 是非 (A:True B:False)
: 1.A
我是选(B)
这题比较tight的big O应该是O((n+1)!)吧？
这样好像就牵扯到题目big O不tight要不要选的问题
我的想法是有提到 "complexity" 的就要选tight的
没提到的像 "It takes O(f(n)) time..." 或是 "f(n)=O(g(n))"这类比较的就可以选不tight的
不知道这个想法有没有问题... 恳请理论派的演算法大师们开示一下
: 2.B
: 3.A
: 4.B
: 5.B
: 6.B
这不是(A)吗？
: 7.A
: 8.A
不太知道cadinality到底是指 "有几个largest clique"
还是指 "largest clique里面有几个vertex"
如果是前者的话这题应该是(B)吧？
: 9.A
: 10.B
: 复选
: 11.C
: 12.D(E)
: E选项不知道该不该选, 爬文有人提到可以在O(N)甚至O(1)完成
我是选(B)(D)(E)
看到之前FRAXIS大大有讲解 不过还是有点疑问
(A)说要在n = 2^k-1的情况下balenced的机率很小 所以F大在
#1SH42OOb应该是打错了？
(B)amortized应该是一串差不多复杂度的operation 突然出现一个worst case可以忽略的
意思吧？
#1QFdFK8A 这篇中F大好像讲相反了？
所以我认为BST insertion只要不要变成斜曲树 应该大部分都还是O(logn)吧？
: 13.AB
https://imgur.com/RAjnqss
我是画这样 答案一样是AB 应该是对的吧？
: 14.E
: 15.E
: 我用Lazy merge下去想的
答案不确定 有人是选只选(B)
但(B)worst case下两个binomial heap各有log na和log nb颗子树 然後同order的由小到
大两两做merge 不是应该最多是merge O(log(max(na, nb)))次吗？
(D)感觉错 但正确不知道是什麽 好像也不是O(log(na+nb))
(E)感觉是错的 如果ra跟rb在order一样的子树merge完会在同一颗
: 16.BE
(A)是对的吧？
https://imgur.com/bZAl1mW
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.176.55.182 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577527888.A.474.html
1F：推 mistel: 1.洪逸说选择题要选符合上界的，看一些题目除非像电机丙1 12/28 18:16
2F：→ mistel: 04年的12b选项才不选 但真的蛮难分的 12/28 18:16
了解！不过洪逸说104 12b不选的原因是甚麽？
3F：→ mistel: 6 我也选A 12/28 18:16
4F：→ mistel: 8他是问of its largest clique，单纯指最大的团吧 话说这 12/28 18:18
5F：→ mistel: 个子嘉那本图论题库最後面也有一样的定义 12/28 18:18
所以是指largest clique有几个vertex罗？ 我回去再翻一下小黄的书
6F：推 mistel: 12的B就不知道了，但我想不出来要怎麽用potential method 12/28 18:22
7F：→ mistel: 证logn，因为我们不能预期BST长怎样，所以我觉得这个是错 12/28 18:22
8F：→ mistel: 的 12/28 18:22
9F：推 mistel: 15应该只有B吧，你是不是没有考虑到两棵merge後出来的新t 12/28 18:28
10F：→ mistel: ree可能会跟另一棵继续merge? 12/28 18:28
我是有想到 不过细节要怎麽merge有点想不出来 不过以符合上界来讲应该是对的
11F：→ mistel: 16A是对的 12/28 18:28
12F：推 FRAXIS: 12 (A) 是错的 (B) 应该是错的 但是题义不是很清楚 12/28 22:46
13F：→ FRAXIS: 你没有办法保证对於所有的 random BST, amortized O(lgn) 12/28 22:47
14F：→ FRAXIS: 虽然有很高的机率 amortized O(lg n) 12/28 22:48
原来如此！先谢过m大跟F大~
15F：→ mistel: 请问F大，12的A要怎麽改才会是正确的叙述？ 12/28 23:14
16F：推 mistel: 其实104 12b我也不确定...我是看到如果符合上界我就选啦Q 12/28 23:17
17F：→ mistel: Q不然根本跟观落音一样 12/28 23:17
其实考研就是在观落阴啦
※ 编辑: ccapricorntw (180.176.55.182 台湾), 12/28/2019 23:26:48
18F：→ jeremyyuan: 12A 把上界拿掉就对了 12/28 23:33
19F：→ mistel: j大说的上界是？ ceiling？ 请问有来源可以参考吗>< 12/29 18:15
20F：推 bochengchen: 想请问大大为什麽14题的Ｃ不选 01/20 14:27