※ 引述《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
我是画这样 答案一样是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)是对的吧？