作者ponwar87123 (干我屁事喔北七)
看板Grad-ProbAsk
标题[理工] 104中央 资演
时间Sun Dec 15 12:10:26 2019
1.第一题
https://i.imgur.com/7xfFccb.jpg
这题我很勉强选了B，
但其实我觉得BC都蛮可以的啊(?
而且有时候我觉得递回没有很好懂就是了
2.第四题
https://i.imgur.com/a5WaKAd.jpg
这题我选E是因为算成full binary tree了
可是如果logn不为整数，那要算取多少？
上界还下届？
3.第九题
https://i.imgur.com/5AMdnzP.jpg
想问这题该选A还是C?
两个都可以做出DFS吧？但哪个比较优质我就不知道了
4.第十七题
https://i.imgur.com/2cPzkQp.jpg
这题有大大能解说一下该怎麽做吗QQ
完全没想法
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 175.97.13.57 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1576383030.A.7FC.html
1F：推 mistel: reduction那题是把欲sort的instance转换成x轴上的坐标，x 12/15 12:22
2F：→ mistel: 1->(x1,0) x2->(x2,0)... 12/15 12:22
3F：推 mistel: 第四题应该要选D吧 3颗节点的complete BT高不是2？ 12/15 12:26
4F：→ zuchang: 17是演算法convex hill 课本有reduce过程 12/15 12:38
5F：推 mistel: 楼上，这题是reduce到MST，应该不一样喔 12/15 12:38
6F：→ zuchang: 等等 不用那麽难 用kruskal reduce过去应该就好 12/15 12:40
7F：→ mistel: 欲证明MST的lower bound应该是把sorting的instance转换成 12/15 12:44
8F：→ mistel: MST的 12/15 12:44
10F：→ zuchang: 这题立宇有放在np的例题 mi大的想法比较好OAO 12/15 12:52
11F：→ ponwar87123: 谢谢大家，那请问其他题呢 12/15 16:02
12F：→ ponwar87123: 还有这题 12/15 16:02
14F：→ ponwar87123: 为何第十五题A要选？如果全为负不是return最大负值就 12/15 16:02
15F：→ ponwar87123: 好了吗 12/15 16:02
16F：推 Aa841018: 1.rerecuresive很难设计和debug，因为通常一直递下去， 12/15 16:31
17F：→ Aa841018: 追踪都有一定难度，何况设计或是除错 12/15 16:31
18F：推 mathtsai: 1.我觉得不好debug这点要看和啥比 12/15 20:26
19F：→ mathtsai: 3.recursive就是用stack叠代 12/15 20:27
那这题该选哪个呢？
20F：→ mathtsai: 15.return最大的 所以S'不就有一个负数了 12/15 20:28
※ 编辑: ponwar87123 (175.97.13.57 台湾), 12/15/2019 22:11:07
21F：→ mathtsai: 两个都对吧 反正实作都能做出来 12/15 23:50
22F：→ ponwar87123: 这样考试该怎麽选XDD 它单选啊啊啊 12/16 14:09