作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
标题Re: [理工] 台大资工 109 资演 对答案+问问题
时间Fri Jan 29 11:02:38 2021
重新整理一下
1. 有争议，最tight是3，但是因为是多选题，也没有说最tight，所以45不知道该不该选
2. 有争议，没有给最小的min(n,m)导致这题唯一可能的解是3，也可能是none
3. none，是小o，sorting有机会等於nlgn
4. 1245
5. 1245，3一样是tight不tight不知道该不该选= =
6. 345，感谢版友提供，clrs有类似题
7. 13
8. 12吧， 4应该是常数，从小到大进去就不一定会是i了，5太紧
9. 145， 2会太紧，skewed的状况会变O(n)，3也是
10. 45
11. merge sort变形，O(1.5n)
12. 题目 total revenue = l_i+l_j这一段看不懂
13. a) 版友提供，测是否连通无cycle
14. 我自己的图是长这样啦，拜托错了告诉我QQ
感谢版友
a是TRUE
b是False
https://i.imgur.com/gBqcmPz.jpg
证明用矛盾证法
15. vertex cover reduce to set cover
前三题最简单却也最像猜猜乐QQ
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.228.118.3 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1611889360.A.89B.html
※ 编辑: joywilliamjo (223.140.6.98 台湾), 01/29/2021 11:03:41
1F：推 try66889: 第三题2不能选吗OAO? o(nn^1/2)应该大於nlogn惹?01/29 12:03
那这样答案就要变245了，哭啊= =根本在考文字游戏的感觉
2F：→ try66889: 9-3 如果是right skewed BST的话找最大值应该是O(n)?01/29 12:10
我改一下= =没看到worst case，感谢
※ 编辑: joywilliamjo (223.140.6.98 台湾), 01/29/2021 12:14:13
3F：→ try66889: 希望今年考试可以写清楚要不要tightness QQ 123题01/29 12:23
4F：→ try66889: 真的不知道要怎麽选~"~01/29 12:23
不写又没有正确答案，哭啊
5F：推 lin130917: 14题a我觉得是false因为diameter是要取最大的只有一个01/29 12:37
6F：→ lin130917: 值01/29 12:37
7F：→ lin130917: 14b我也觉得是false因为tree的center最多两个01/29 12:38
8F：→ lin130917: 阿抱歉14a应该是true如果他的定义是path的话01/29 12:40
我对题目理解是同长度不同path，B的话我画的那个图算tree吗？对center的定义不太熟
悉
※ 编辑: joywilliamjo (223.140.6.98 台湾), 01/29/2021 12:42:04
※ 编辑: joywilliamjo (223.140.6.98 台湾), 01/29/2021 12:42:37
9F：推 lin130917: 你画的b不是tree吧tree不能有cycle01/29 12:45
感谢QQ
※ 编辑: joywilliamjo (223.140.6.98 台湾), 01/29/2021 13:34:13
12F：推 Henry658: 109 台大清大都考center联合出题48401/29 16:01
13F：推 nasa930022: 10-3把新的点插入leaf再连到null的黑点之後就离开了 01/30 22:09
14F：→ nasa930022: 这样不会改变root到leaf之间的black node数量吧?01/30 22:10
我个人是觉得3不用选QQ，毕竟就是插 一个红的进去一个本来就是正常的红黑树，不会影
响路径上的黑node 数，我改个
※ 编辑: joywilliamjo (223.137.255.128 台湾), 01/31/2021 12:10:29