如题
选择题上来跟大家对对看
顺便问问
1. 3
2. 4
3. 3
4. 14
5. 235
6. 1
7. 134
8. 1245
9. 1234
10. 4
11. a)
1. 将input两两分组，input = 偶数分成n/2组，input = 奇数则分成[n/2]+1组
2. 将这些两两一组先比出大小
3. 将每组大的和大的比，小的和小的比
4. 递回做step3
5. return (min,Max)
b)
(3n/2) - 2
12. 看不懂题目中第二句的叙述，估计是用dp做类似rod cutting
13.
14.
a)
b)
o
/ | \
o o o
/ | \ / | \ / | \
o o oo o oo o o
c) 用矛盾证法，如果说center不在T的diameter里面的话，会违背题目对center的
定
(radius为T中的min，如果T的diameter长度一定会超过radius，那表示这条路
径?
radius)
15. a)
不太确定题意，但应该是在说set cover
u = {1,2,3,4,5,6,7,8}
F1 = {1,2,3,4}
F2 = {5,6,7,8}
F3 = {1,3,4,5,6}
F4 = {1,7,8}
F5 = {2}
greedy: C = {F3, F4, F5}
optimal = {F1, F2}
b)
given a subset D{Fi~Fj}，可以在polynimal time(O(n))确定是否每个元素都在
u?

2我选3，他只是算AB两个sorted list合并会比较几次，worst case就是一下A大一下B大4我选1245，2的话对吧？如果最大key还有child代表那孩子比它大，5的话第三小的值高度不会大于2（root height =0）5我选1245，3的话他的分析不够tight应该O(n)就可以6我觉得1错，既然我已经随机挑pivot了那我原本array有没有sorted就不影响我比较次数了吧？8-5 theta应该是错的？如果我随机从大挑到小只需要n就可可了9-2 BST高度是O(n)吧13-a 就check是否连通无cycle这样就好了呗然后12题他说选si, sj然后我的收入是li+lj 可是l是distance我觉得怪怪的

想请问n大5的1为什么会对呢? 我的想法是当选到最小的数(ROOT)时可以O(1)比较出来~1我觉得应该要改成O(n)，不知道有没有没考虑到的地方

回楼上，最少比较次数就是他本来就已经是min-heap，可是不会因为他是从最后一个父点check发现说我root比两个子点小就认定它是min-heap，还是要从最后一个父点检查，每次检查（best case）只比两次（一次看两个孩子谁小一次看root跟这个孩子谁小） 所以全部差不多是n次

感谢n大~ 没考虑要从最后一个父点开始比较> < 了解惹OWO

1. O(n^3)应该同时属于4、5吧2.是问 min 比较次数欸

我回6就好 其它就比较有争议哈哈哈我的理解是它的input原本就排好了没错，可是我是随机挑pivot呀我也有可能挑到可以切成两块相等大小的所以他说always be maximized是错的，我的想法啦没呀Quick sort的best case怎么会比到n^2次，他是每一轮pivot去跟剩下n-1个数比较再分成两个集合6我后面两个选项没算5你看最后三行有说最后一个父点做完会往前做heapify另外7的4应该是错的，我的first pointer points to topelement of the stack所以你给我一个指向最下面的没帮助

想问一下第9题的第5个选项哪里错了（想说4有选的话，5应该也要选）还有第10题的第5个选项我有选，想问一下你的想法～

第二题没给n,m谁小不知道怎选答案只能选3

第6题完全就是拿clrs randomized quick sort出来考啊我写cde 关于d e这两个选项clrs里面都有证哦

这份不是有说没有正确答案的话可以填none吗，所以第三题我觉得是none6的4，5选项在这边 ，但是5是错的吧，ki不一定刚好等于i 吧https://i.imgur.com/zcgeiZW.jpg

回楼上 ki不会刚好等于i没错但他是permutations of <1,2,...,n>所以这样加总起来所有条件都会被考虑到啊

喔喔没看到那句，那这样5应该是对的

我以为123题都是复选？题目没特别要求tight不是对的就要选吗…？

刚刚查了一下最后一题，原po的想法是对的 https://i.imgur.com/rIyNIRU.jpghttps://i.imgur.com/4ourOyr.jpg