作者booowei1203 (wei)
看板Grad-ProbAsk
标题[理工] 108 台大电信 资演B 选择题 对答案
时间Sat Jan 16 16:28:24 2021
这份考卷板上好像还没有答案，想跟大家对一下选择题的答案
是非题：
1~ 5: TTFTF
6~10: TTTFT
选择题：
11~15: DCCDC
16~20: AECCA
21~25: CDEEA
26~30: AAADB
31~32: BC
多选题：
33. ABCD
已更新答案！
附上题目网址：
https://pse.is/38gt6q
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.137.214.145 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1610785707.A.B50.html
1F：→ juzowa: 26怎麽算是A的？ 01/16 21:45
2F：推 jordan1997: 是非的第5题是False吧，它只说weight是real number 没 01/17 11:51
3F：→ jordan1997: 说没有负边 01/17 11:51
阿阿没看清楚题目 感谢！
4F：推 jordan1997: 多选的E应该不能选，如果f(n)为2log(n)，那麽2^(2log( 01/17 11:56
5F：→ jordan1997: n))就会是n^2就不会是O(n) 01/17 11:56
同意！没想清楚 感谢！
6F：推 jordan1997: binomial tree问deg可以想成是问有多少子树Bk tree， 01/17 12:06
7F：→ jordan1997: 像有一颗B5 tree的话就有一个node degree为5，B6也是1 01/17 12:06
8F：→ jordan1997: 因爲其中一个B5会变子树，而另一个则是B6 root degree 01/17 12:06
9F：→ jordan1997: 为6，B7的话则会有2颗B5子树（2*1），B8则是4颗（2*( 01/17 12:06
10F：→ jordan1997: 2*1))依此类推 01/17 12:06
11F：推 jordan1997: 第30题我会选B，因为它只问x的子点，如果该成successo 01/17 12:15
12F：→ jordan1997: r 才会对 01/17 12:15
哦哦哦！同意～～
13F：推 jimmylin1024: 想问是非第九题为什麽是F? 01/17 12:49
我觉得 NP 应该要改成 NPC～
详细地说的话，因为一个问题是 NP-Complete，代表那个问题属於 NP，也属於 NP-hard。
也就是说，解 NP 的问题，不会比解 NP-Complete 的问题难
（因为 NP-Complete 包含於 np-hard）
所以若有一个 NP 问题有 polynomial time 的解法，不一定所有 NP-complete 的问题
也可以在 polynomial time 被解掉。
以上是自己的想法～
14F：推 jimmylin1024: 想问Jordan大 30题改成successor以後什麽才会对？ 01/17 12:52
15F：推 jordan1997: 从下图来看如果今天问的是x的子点中degree 为0的点 01/17 13:50
16F：→ jordan1997: 有哪些，那麽依旧只有一个，取到B5的话就看B4这个图也 01/17 13:50
17F：→ jordan1997: 只会有一个 01/17 13:50
已更新答案！
※ 编辑: booowei1203 (223.137.25.210 台湾), 01/17/2021 14:59:49
※ 编辑: booowei1203 (223.137.25.210 台湾), 01/17/2021 15:01:06
※ 编辑: booowei1203 (223.137.25.210 台湾), 01/17/2021 15:12:28
19F：推 gj94jo3a12: 32题选c是因为worst case要find的key没有被compressed 01/17 15:33
20F：→ gj94jo3a12: 吗 01/17 15:33
对对！
21F：推 jackycheny: 我觉得31,32是AA 01/17 16:58
22F：→ jackycheny: 32说根据31题，然後31有说考虑path compression 01/17 16:59
这两题我是参考蔡欣穆教授的投影片
https://imgur.com/38ipV48.jpg
※ 编辑: booowei1203 (223.136.242.149 台湾), 01/18/2021 10:42:32
※ 编辑: booowei1203 (223.136.242.149 台湾), 01/18/2021 10:45:13
※ 编辑: booowei1203 (223.136.242.149 台湾), 01/18/2021 10:46:40
23F：推 z000000000: 想问一下23题要怎麽画出7个黑点呢? 01/18 11:42
我发现我写错了QQ 应该是 11 个黑点 感谢～
https://imgur.com/ej69mDH.jpg
24F：推 jackycheny: 32看了下应该是我没考虑到一开始第一次的find最差会是 01/18 13:59
25F：→ jackycheny: O(logn) 01/18 13:59
※ 编辑: booowei1203 (114.136.235.31 台湾), 01/21/2021 16:44:12
※ 编辑: booowei1203 (114.136.235.31 台湾), 01/21/2021 16:45:21