[理工] 108 台大電信 資演B 選擇題 對答案

[booowei1203 (wei)]

這份考卷板上好像還沒有答案，想跟大家對一下選擇題的答案

是非題：
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1610785707.A.B50.html
→ juzowa: 26怎麼算是A的？
推 jordan1997: 是非的第5題是False吧，它只說weight是real number 沒
→ jordan1997: 說沒有負邊
阿阿沒看清楚題目 感謝！

推 jordan1997: 多選的E應該不能選，如果f(n)為2log(n)，那麼2^(2log(
→ jordan1997: n))就會是n^2就不會是O(n)
同意！沒想清楚 感謝！

推 jordan1997: binomial tree問deg可以想成是問有多少子樹Bk tree，
→ jordan1997: 像有一顆B5 tree的話就有一個node degree為5，B6也是1
→ jordan1997: 因爲其中一個B5會變子樹，而另一個則是B6 root degree
→ jordan1997:  為6，B7的話則會有2顆B5子樹（2*1），B8則是4顆（2*(
→ jordan1997: 2*1))依此類推
推 jordan1997: 第30題我會選B，因為它只問x的子點，如果該成successo
→ jordan1997: r 才會對
哦哦哦！同意～～

推 jimmylin1024: 想問是非第九題為什麼是F?
我覺得 NP 應該要改成 NPC～

詳細地說的話，因為一個問題是 NP-Complete，代表那個問題屬於 NP，也屬於 NP-hard。

也就是說，解 NP 的問題，不會比解 NP-Complete 的問題難
（因為 NP-Complete 包含於 np-hard）

所以若有一個 NP 問題有 polynomial time 的解法，不一定所有 NP-complete 的問題
也可以在 polynomial time 被解掉。

以上是自己的想法～

推 jimmylin1024: 想問Jordan大 30題改成successor以後什麼才會對？
推 jordan1997:  從下圖來看如果今天問的是x的子點中degree 為0的點
→ jordan1997: 有哪些，那麼依舊只有一個，取到B5的話就看B4這個圖也
→ jordan1997: 只會有一個
→ jordan1997: https://i.imgur.com/xxLCTEk.jpg

已更新答案！
※ 編輯: 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
推 gj94jo3a12: 32題選c是因為worst case要find的key沒有被compressed
→ gj94jo3a12: 嗎
對對！

推 jackycheny: 我覺得31,32是AA
→ jackycheny: 32說根據31題，然後31有說考慮path compression
這兩題我是參考蔡欣穆教授的投影片
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
推 z000000000: 想問一下23題要怎麼畫出7個黑點呢?
我發現我寫錯了QQ 應該是 11 個黑點 感謝～
https://imgur.com/ej69mDH.jpg

推 jackycheny: 32看了下應該是我沒考慮到一開始第一次的find最差會是
→ jackycheny: O(logn)
※ 編輯: booowei1203 (114.136.235.31 臺灣), 01/21/2021 16:44:12
※ 編輯: booowei1203 (114.136.235.31 臺灣), 01/21/2021 16:45:21