作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
標題[理工] 台大資工 109 資演 對答案+問問題
時間Mon Jan 18 10:54:01 2021
如題
選擇題上來跟大家對對看
順便問問
1. 3
2. 4
3. 3
4. 14
5. 235
6. 1
7. 134
8. 1245
9. 1234
10. 4
11. a)
1. 將input兩兩分組，input = 偶數分成n/2組，input = 奇數則分成[n/2]+1組
2. 將這些兩兩一組先比出大小
3. 將每組大的和大的比，小的和小的比
4. 遞迴做step3
5. return (min,Max)
b)
(3n/2) - 2
12. 看不懂題目中第二句的敘述，估計是用dp做類似rod cutting
13.
14.
a)
b)
o
/ | \
o o o
/ | \ / | \ / | \
o o oo o oo o o
c) 用矛盾證法，如果說center不在T的diameter裡面的話，會違背題目對center的
定
(radius為T中的min，如果T的diameter長度一定會超過radius，那表示這條路
徑?
radius)
15. a)
不太確定題意，但應該是在說set cover
u = {1,2,3,4,5,6,7,8}
F1 = {1,2,3,4}
F2 = {5,6,7,8}
F3 = {1,3,4,5,6}
F4 = {1,7,8}
F5 = {2}
greedy: C = {F3, F4, F5}
optimal = {F1, F2}
b)
given a subset D{Fi~Fj}，可以在polynimal time(O(n))確定是否每個元素都在
u?
----NP check
再來證NP-complete 應該用vertex cover去reduce但我不會QQ，可以硬寫但應
該拿不了分就不寫了而且我也沒有很確定REDUCE要怎麼做，還請大家提供意見QQ
大概是這樣，大家考試加油
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.137.253.17 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1610938443.A.BC2.html
1F：推 naive131: 2我選3，他只是算AB兩個sorted list合併會比較幾次，wor01/21 14:44
2F：→ naive131: st case就是一下A大一下B大01/21 14:44
我一題一題慢慢回
二應該是要選3沒錯，但認真寫的話好像應該是omega(min(n,m))，發生在其中一邊最大的
比另一邊最小的小
3F：→ naive131: 4我選1245，2的話對吧？如果最大key還有child代表那孩子01/21 14:44
4F：→ naive131: 比它大，5的話第三小的值高度不會大於2（root height =01/21 14:44
5F：→ naive131: 0）01/21 14:44
6F：→ naive131: 5我選1245，3的話他的分析不夠tight應該O(n)就可以01/21 15:02
其實這樣我會不知道3要不要選欸
他沒有說要做到最tight，所以單論敘述的話我覺得3沒有錯
7F：→ naive131: 6我覺得1錯，既然我已經隨機挑pivot了那我原本array有沒01/21 15:02
8F：→ naive131: 有sorted就不影響我比較次數了吧？01/21 15:02
我以為1是說input是sort過的，所以就是worst case的quick sort,所以這邊的意思是指
因為sort過所以不用再比較的意思嗎@@
9F：推 naive131: 8-5 theta應該是錯的？如果我隨機從大挑到小只需要n就可01/21 15:14
10F：→ naive131: 可了01/21 15:14
對
這個我大意了= =theta太緊了
11F：→ naive131: 9-2 BST高度是O(n)吧01/21 15:19
對哦，skewed tree對ㄅ
12F：→ naive131: 13-a 就check是否連通無cycle這樣就好了唄01/21 15:27
13F：→ naive131: 然後12題他說選si, sj然後我的收入是li+lj 可是l是dista 01/21 15:29
14F：→ naive131: nce我覺得怪怪的01/21 15:29
對我也看不懂這在寫啥
15F：推 try66889: 想請問n大5的1為什麼會對呢? 我的想法是當選到最小的數01/21 21:19
16F：→ try66889: (ROOT)時可以O(1)比較出來~01/21 21:19
17F：→ try66889: 1我覺得應該要改成O(n)，不知道有沒有沒考慮到的地方01/21 21:20
18F：→ naive131: 回樓上，最少比較次數就是他本來就已經是min-heap，可是01/22 08:33
19F：→ naive131: 不會因為他是從最後一個父點check發現說我root比兩個子01/22 08:33
20F：→ naive131: 點小就認定它是min-heap，還是要從最後一個父點檢查，每01/22 08:33
21F：→ naive131: 次檢查（best case）只比兩次（一次看兩個孩子誰小一次01/22 08:33
22F：→ naive131: 看root跟這個孩子誰小） 所以全部差不多是n次01/22 08:33
23F：→ try66889: 感謝n大~ 沒考慮要從最後一個父點開始比較> < 了解惹OWO01/22 09:46
24F：推 summit: 1. O(n^3)應該同時屬於4、5吧01/22 16:21
...那第一題變成要選345第二題要變選12了，這樣選不下手了
25F：推 summit: 2.是問 min 比較次數欸01/22 16:33
他給的演算法
如果A是[1,2,3],B是[4,5,6,7]，則A中三個全部拿出去後A變空，然後直接放入B，這樣就
變成只要比三次就好
這樣是最min了吧？但這樣問題就是你不知道是A比較小還是B比較小@@
有夠模糊
※ 編輯: joywilliamjo (114.136.197.106 臺灣), 01/22/2021 17:42:55
※ 編輯: joywilliamjo (114.136.197.106 臺灣), 01/22/2021 17:59:31
※ 編輯: joywilliamjo (114.136.197.106 臺灣), 01/22/2021 18:01:05
26F：→ naive131: 我回6就好 其它就比較有爭議哈哈哈01/22 19:30
27F：→ naive131: 我的理解是它的input原本就排好了沒錯，可是我是隨機挑p01/22 19:30
28F：→ naive131: ivot呀我也有可能挑到可以切成兩塊相等大小的所以他說al01/22 19:30
29F：→ naive131: ways be maximized是錯的，我的想法啦 01/22 19:30
我的想法是
今天input = [1,2,3,4,5,6,7]
pivot = 4
那兩邊[1,2,3]還是要比n(n-1)/2次這樣
所以怎麼切都還是有一邊要比到O(n^2)
怎麼感覺這份考卷這麼多極端
唉...
※ 編輯: joywilliamjo (114.136.197.106 臺灣), 01/22/2021 20:19:35
30F：→ naive131: 沒呀Quick sort的best case怎麼會比到n^2次，他是每一輪01/22 22:39
31F：→ naive131: pivot去跟剩下n-1個數比較再分成兩個集合 01/22 22:39
那n大你第六題選哪個啊
4、5我不太會算不知道對不對@@
上面
至於第5題的3選項
我越看越像top down的寫法欸
因為是先從n/2到n先做完，再做剩下的，再組合起來
比較不像是bottom up，全部放完再排
所以是O(nlogn)吧
不知道你怎麼看
※ 編輯: joywilliamjo (223.136.28.84 臺灣), 01/23/2021 08:36:27
32F：→ naive131: 6我後面兩個選項沒算 01/23 10:06
33F：→ naive131: 5你看最後三行有說最後一個父點做完會往前做heapify 01/23 10:06
34F：→ naive131: 另外7的4應該是錯的，我的first pointer points to top01/23 10:06
35F：→ naive131: element of the stack所以你給我一個指向最下面的沒幫助01/23 10:06
36F：推 booowei1203: 想問一下第9題的第5個選項哪裡錯了（想說4有選的話，01/23 15:00
37F：→ booowei1203: 5應該也要選）01/23 15:00
我感覺當下寫的時候沒想仔細，事後想想兩個好像都得選...
9的5是說把y的左子樹接到y的parent,然後y取代z對吧
38F：推 booowei1203: 還有第10題的第5個選項我有選，想問一下你的想法～01/23 15:11
※ 編輯: joywilliamjo (223.136.28.84 臺灣), 01/23/2021 19:00:45
39F：推 jackycheny: 第二題沒給n,m誰小不知道怎選 01/23 21:13
40F：推 jackycheny: 答案只能選3 01/23 21:17
41F：推 aa871220: 第6題完全就是拿clrs randomized quick sort出來考啊 01/24 23:54
42F：→ aa871220: 我寫cde 關於d e這兩個選項clrs裡面都有證哦 01/24 23:54
43F：推 jordan1997: 這份不是有說沒有正確答案的話可以填none嗎，所以第三 01/25 10:44
44F：→ jordan1997: 題我覺得是none 01/25 10:44
45F：推 jordan1997: 6的4，5選項在這邊 ，但是5是錯的吧，ki不一定剛好等 01/25 11:47
47F：→ aa871220: 回樓上 ki不會剛好等於i沒錯 01/25 11:51
48F：→ aa871220: 但他是permutations of <1,2,...,n> 01/25 11:51
49F：→ aa871220: 所以這樣加總起來所有條件都會被考慮到啊 01/25 11:51
50F：推 jordan1997: 喔喔沒看到那句，那這樣5應該是對的 01/25 12:00
51F：推 nyms: 我以為123題都是複選？題目沒特別要求tight不是對的就要選嗎 01/25 17:04
52F：→ nyms: …？ 01/25 17:04
53F：推 jordan1997: 剛剛查了一下最後一題，原po的想法是對的 https://i.i 01/25 22:07
54F：→ jordan1997: mgur.com/rIyNIRU.jpg 01/25 22:07