[理工] 104台大電機丙資演對答案

[goldflower (金色小黃花)]

(2/17更新  感謝各位回文及推文的版友們QQ
我把大家說法跟我自己的一些觀點整理一下)

這張幾乎全部考我弱點...
我各種heap其實不是很熟XD

是非:
1.F(沒特別說要怎麼著色  應該False吧?)
jerry大說法:此題可能在問此問題是否為NPC
而考慮2-coloring即為False

FRAXIS大說法:若此題為True  則我們變成確定N!=NP

2.F
3.F
4.F(Fixed size讓我有點猶豫...)
5.F(更正為T)
其實我覺得False的理由是因為不管是不是amortize分析都是O(1)
所以覺得他的語法有瑕疵
但是以事實來說的話應該是True
6.(更新為F)
應該可跑DFS看finish time解?  O(V+E)
7.F
External Node要在同一層
有個好網站推薦給大家
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
可以看大部份會考的資料結構的操作過程

要選T也行
但是equal to 1的情況不會發生
就只能大家自行選擇了
這些老師不能出的稍微好一點嗎  QQ

8.T
9.T(嗎??)
dddm49:complete graph至少砍n-1邊
10.(更新為T)

這邊還是不確定
但是答案是T基本上是肯定的
大家給的圖都是bottom up的2-3 tree
但是top down的操作模式有點不同
https://www.youtube.com/watch?v=2679VQ26Fp4
我只能找到2-3-4的top down但是找不到2-3tree的
我照2-3-4的方法做會遇到尷尬的地方...
還是說對2-3來說兩個會一樣呢?

複選:
11.
BCDE

12.
CE(更新為ACE)
f1256421:Binomisl heap會存指向min的pointer
如果沒有保存就需要用O(logn)

D:他是要合成兩棵Binomial Tree變一棵Binomial Tree,那這選項應該沒意義吧?
如果兩棵樹同level那O(1)就可以合併
若不同level則不一定可直接合併
而如果是合成兩個Binomial Heap應是花O(logn)

13.
BC(更新為DE)
pups003: http://i.imgur.com/pyvKtoS.jpg
str[i]<<(i*2)
為向左shift

14.
CE(D不確定)

D應該是False吧?
這題我考量的點在於他是問paths而不是path的長度
所以感覺比較像是窮舉所有路徑的組合數?
我英文爛爛不是很確定...

15.
CE(目前應該ABCE都是False所以刪去法可能是D)

A:好像大於O(2^n)?
我跟jerry大一樣建出O(n!)之tree
D:因為黑白建期望為logn高度  所以反過來看應該也是50%而不會greter than?
E:我看到這個就以為他是問別種問題XD

16.
DE

B:不太清楚,是八個嗎?
E:感覺要用reduce 但是不知道怎麼設計


感覺我這張錯超多

希望各位高手指正QQ


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.60.217.209
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455636494.A.B8E.html
→ yaxauw: 明天早上才要寫qq
→ goldflower: 那明天指教一下QQ
推 FRAXIS: 6 應該是 false O(n) 連 BFS 都不行了..
推 f1256421: 15 E是錯的吧  全黑就沒有紅了 然後我寫A是對的全滿的
→ f1256421: node數是O(2^(n+1)-1)=O(2*(2^n)-1)=O(2^n)  我是這
→ f1256421: 樣看的QQ
→ f1256421: 14 D我有寫 O(log(max(na,nb)+1)  我就把1刪了...
→ f1256421: 12 我有寫A   Binomial Heap有指標會指向最小的node
→ f1256421: http://i.imgur.com/EpDM2n6.jpg 10的圖
→ f1256421: 7 我寫T 因為看到can be =_=
→ jerry031181: 15A沒選 一題意他的full node的子點會隨著level增加
→ jerry031181: 然後我就推出了一個n!的node數QQ  6.false跟F大一樣
推 pups003: 11B為什麼錯啊？？
推 pups003: 12A好像有兩種說法，O(log n)是指沒有指標只想最小node
→ pups003: 的版本，所以要checklist n個root,但是洪逸書上寫的是有
→ pups003: 最小node指標的版本，只要O(1)
推 pups003: 13我是這樣想 http://i.imgur.com/pyvKtoS.jpg
→ pups003: <<是shift left
推 dddm49: 13 e也是對的吧
推 dddm49: 想問第5題 雖然我也是選F 但不太確定概念是否正確
→ pups003: 13e我手誤忘了寫哈哈
推 dddm49: 11b 是因為要先找到last前一node. 要花O(n)
→ pups003: 懂了，感謝d大，另外5我寫true，wiki上也是寫「work in c
→ pups003: onstant amortized time」
推 dddm49: insert 的 amortized complexity 是O(1) 但扣掉之後我就不
→ dddm49: 太清楚分攤成本是多少了
→ dddm49: 有看到Horowitz寫複雜度是O(i+c+dk+(dm+d)logi)
推 janus7799: 6是true喔！如果是DAG就
→ janus7799: 走一次topology即可
推 dddm49: false吧 要O(V+E)不是嗎
推 janus7799: 因為題目用can，我想說edge最少是(n-1)，所以就選了
推 leo258x: 7寫T +1 想說小於等於敘述對
→ leo258x: 12題c資結和演算不同 d我有寫@@
→ leo258x: 16題 b後來查是正八面體 一堆正三角形那個 順便問一下16
→ leo258x:  d
推 odanaga: 7是true吧
→ odanaga: 2-3-4樹 外部結點高度相等
推 dddm49: 可是7 兩邊高度不能相差1吧
推 odanaga: 有道理 那又是題意問題惹QQ
推 iwtes: 想問4為什麼false 如果array是sort過的而且是遞減 這樣也沒
→ iwtes: 辦法嗎
→ goldflower: 如果sorted且知道最後一個為min那就可以
→ goldflower: 但是一般來說不行
→ goldflower: 我覺得即使用can也有點太牽強  不足以讓我選T哈哈
※ 編輯: goldflower (61.60.217.209), 02/17/2016 19:13:33
→ yaxauw: 題目講的是一般的情況 所以不能自己加條件
推 leoturkey: 15 所以台大的TREE高度要從0開始看喔@@
→ yaxauw: 台大題目寫起來都是這樣的 或你直接用Fh+2-1來看更保險
推 prosperous: 可是Fh+2-1看也不能確定是0開始還1開始吧QQ
→ odanaga: 古代台大電機題目是假設root是1
推 leoturkey: 只好看他會不會說了冏
→ yaxauw: 像這題 就h=3 算F5-1 就避掉root是0還是1開始的問題了
→ yaxauw: 上一行講錯了
→ yaxauw: 這樣必須要h=4 才會是7個node啊
→ yaxauw: 因為洪逸很常用h=5 12個點的例子 所以我看到7個點
→ yaxauw: 直覺就是 h是4才對
→ goldflower: 我寫成F5=8了= =所以算錯QQ
※ 編輯: goldflower (61.60.217.209), 02/18/2016 01:44:11