作者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/m.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