作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
标题[理工] 台大资工 109 资演 对答案+问问题
时间Mon Jan 18 10:54:01 2021
如题
选择题上来跟大家对对看
顺便问问
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?
----NP check
再来证NP-complete 应该用vertex cover去reduce但我不会QQ，可以硬写但应
该拿不了分就不写了而且我也没有很确定REDUCE要怎麽做，还请大家提供意见QQ
大概是这样，大家考试加油
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.137.253.17 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1610938443.A.BC2.html
1F：推 naive131: 2我选3，他只是算AB两个sorted list合并会比较几次，wor01/21 14:44
2F：→ naive131: st case就是一下A大一下B大01/21 14:44
我一题一题慢慢回
二应该是要选3没错，但认真写的话好像应该是omega(min(n,m))，发生在其中一边最大的
比另一边最小的小
3F：→ naive131: 4我选1245，2的话对吧？如果最大key还有child代表那孩子01/21 14:44
4F：→ naive131: 比它大，5的话第三小的值高度不会大於2（root height =01/21 14:44
5F：→ naive131: 0）01/21 14:44
6F：→ naive131: 5我选1245，3的话他的分析不够tight应该O(n)就可以01/21 15:02
其实这样我会不知道3要不要选欸
他没有说要做到最tight，所以单论叙述的话我觉得3没有错
7F：→ naive131: 6我觉得1错，既然我已经随机挑pivot了那我原本array有没01/21 15:02
8F：→ naive131: 有sorted就不影响我比较次数了吧？01/21 15:02
我以为1是说input是sort过的，所以就是worst case的quick sort,所以这边的意思是指
因为sort过所以不用再比较的意思吗@@
9F：推 naive131: 8-5 theta应该是错的？如果我随机从大挑到小只需要n就可01/21 15:14
10F：→ naive131: 可了01/21 15:14
对
这个我大意了= =theta太紧了
11F：→ naive131: 9-2 BST高度是O(n)吧01/21 15:19
对哦，skewed tree对ㄅ
12F：→ naive131: 13-a 就check是否连通无cycle这样就好了呗01/21 15:27
13F：→ naive131: 然後12题他说选si, sj然後我的收入是li+lj 可是l是dista 01/21 15:29
14F：→ naive131: nce我觉得怪怪的01/21 15:29
对我也看不懂这在写啥
15F：推 try66889: 想请问n大5的1为什麽会对呢? 我的想法是当选到最小的数01/21 21:19
16F：→ try66889: (ROOT)时可以O(1)比较出来~01/21 21:19
17F：→ try66889: 1我觉得应该要改成O(n)，不知道有没有没考虑到的地方01/21 21:20
18F：→ naive131: 回楼上，最少比较次数就是他本来就已经是min-heap，可是01/22 08:33
19F：→ naive131: 不会因为他是从最後一个父点check发现说我root比两个子01/22 08:33
20F：→ naive131: 点小就认定它是min-heap，还是要从最後一个父点检查，每01/22 08:33
21F：→ naive131: 次检查（best case）只比两次（一次看两个孩子谁小一次01/22 08:33
22F：→ naive131: 看root跟这个孩子谁小） 所以全部差不多是n次01/22 08:33
23F：→ try66889: 感谢n大~ 没考虑要从最後一个父点开始比较> < 了解惹OWO01/22 09:46
24F：推 summit: 1. O(n^3)应该同时属於4、5吧01/22 16:21
...那第一题变成要选345第二题要变选12了，这样选不下手了
25F：推 summit: 2.是问 min 比较次数欸01/22 16:33
他给的演算法
如果A是[1,2,3],B是[4,5,6,7]，则A中三个全部拿出去後A变空，然後直接放入B，这样就
变成只要比三次就好
这样是最min了吧？但这样问题就是你不知道是A比较小还是B比较小@@
有够模糊
※ 编辑: joywilliamjo (114.136.197.106 台湾), 01/22/2021 17:42:55
※ 编辑: joywilliamjo (114.136.197.106 台湾), 01/22/2021 17:59:31
※ 编辑: joywilliamjo (114.136.197.106 台湾), 01/22/2021 18:01:05
26F：→ naive131: 我回6就好 其它就比较有争议哈哈哈01/22 19:30
27F：→ naive131: 我的理解是它的input原本就排好了没错，可是我是随机挑p01/22 19:30
28F：→ naive131: ivot呀我也有可能挑到可以切成两块相等大小的所以他说al01/22 19:30
29F：→ naive131: ways be maximized是错的，我的想法啦 01/22 19:30
我的想法是
今天input = [1,2,3,4,5,6,7]
pivot = 4
那两边[1,2,3]还是要比n(n-1)/2次这样
所以怎麽切都还是有一边要比到O(n^2)
怎麽感觉这份考卷这麽多极端
唉...
※ 编辑: joywilliamjo (114.136.197.106 台湾), 01/22/2021 20:19:35
30F：→ naive131: 没呀Quick sort的best case怎麽会比到n^2次，他是每一轮01/22 22:39
31F：→ naive131: pivot去跟剩下n-1个数比较再分成两个集合 01/22 22:39
那n大你第六题选哪个啊
4、5我不太会算不知道对不对@@
上面
至於第5题的3选项
我越看越像top down的写法欸
因为是先从n/2到n先做完，再做剩下的，再组合起来
比较不像是bottom up，全部放完再排
所以是O(nlogn)吧
不知道你怎麽看
※ 编辑: joywilliamjo (223.136.28.84 台湾), 01/23/2021 08:36:27
32F：→ naive131: 6我後面两个选项没算 01/23 10:06
33F：→ naive131: 5你看最後三行有说最後一个父点做完会往前做heapify 01/23 10:06
34F：→ naive131: 另外7的4应该是错的，我的first pointer points to top01/23 10:06
35F：→ naive131: element of the stack所以你给我一个指向最下面的没帮助01/23 10:06
36F：推 booowei1203: 想问一下第9题的第5个选项哪里错了（想说4有选的话，01/23 15:00
37F：→ booowei1203: 5应该也要选）01/23 15:00
我感觉当下写的时候没想仔细，事後想想两个好像都得选...
9的5是说把y的左子树接到y的parent,然後y取代z对吧
38F：推 booowei1203: 还有第10题的第5个选项我有选，想问一下你的想法～01/23 15:11
※ 编辑: joywilliamjo (223.136.28.84 台湾), 01/23/2021 19:00:45
39F：推 jackycheny: 第二题没给n,m谁小不知道怎选 01/23 21:13
40F：推 jackycheny: 答案只能选3 01/23 21:17
41F：推 aa871220: 第6题完全就是拿clrs randomized quick sort出来考啊 01/24 23:54
42F：→ aa871220: 我写cde 关於d e这两个选项clrs里面都有证哦 01/24 23:54
43F：推 jordan1997: 这份不是有说没有正确答案的话可以填none吗，所以第三 01/25 10:44
44F：→ jordan1997: 题我觉得是none 01/25 10:44
45F：推 jordan1997: 6的4，5选项在这边 ，但是5是错的吧，ki不一定刚好等 01/25 11:47
47F：→ aa871220: 回楼上 ki不会刚好等於i没错 01/25 11:51
48F：→ aa871220: 但他是permutations of <1,2,...,n> 01/25 11:51
49F：→ aa871220: 所以这样加总起来所有条件都会被考虑到啊 01/25 11:51
50F：推 jordan1997: 喔喔没看到那句，那这样5应该是对的 01/25 12:00
51F：推 nyms: 我以为123题都是复选？题目没特别要求tight不是对的就要选吗 01/25 17:04
52F：→ nyms: …？ 01/25 17:04
53F：推 jordan1997: 刚刚查了一下最後一题，原po的想法是对的 https://i.i 01/25 22:07
54F：→ jordan1997: mgur.com/rIyNIRU.jpg 01/25 22:07