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

看板Grad-ProbAsk作者 (金色小黃花)時間8年前 (2016/02/16 23:28), 8年前編輯推噓20(20推 0噓 36→)
留言56則, 13人參與, 最新討論串1/3 (看更多)
(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
→
02/16 23:31, , 1F
明天早上才要寫qq
02/16 23:31, 1F
→
02/16 23:32, , 2F
那明天指教一下QQ
02/16 23:32, 2F
推
02/17 00:00, , 3F
6 應該是 false O(n) 連 BFS 都不行了..
02/17 00:00, 3F
推
02/17 00:10, , 4F
15 E是錯的吧 全黑就沒有紅了 然後我寫A是對的全滿的
02/17 00:10, 4F
→
02/17 00:11, , 5F
node數是O(2^(n+1)-1)=O(2*(2^n)-1)=O(2^n) 我是這
02/17 00:11, 5F
→
02/17 00:11, , 6F
樣看的QQ
02/17 00:11, 6F
→
02/17 00:13, , 7F
14 D我有寫 O(log(max(na,nb)+1) 我就把1刪了...
02/17 00:13, 7F
→
02/17 00:16, , 8F
12 我有寫A Binomial Heap有指標會指向最小的node
02/17 00:16, 8F
→
02/17 00:17, , 9F
10的圖
02/17 00:17, 9F
→
02/17 00:23, , 10F
7 我寫T 因為看到can be =_=
02/17 00:23, 10F
→
02/17 00:29, , 11F
15A沒選 一題意他的full node的子點會隨著level增加
02/17 00:29, 11F
→
02/17 00:30, , 12F
然後我就推出了一個n!的node數QQ 6.false跟F大一樣
02/17 00:30, 12F
推
02/17 09:58, , 13F
11B為什麼錯啊？？
02/17 09:58, 13F
推
02/17 10:04, , 14F
12A好像有兩種說法，O(log n)是指沒有指標只想最小node
02/17 10:04, 14F
→
02/17 10:04, , 15F
的版本，所以要checklist n個root,但是洪逸書上寫的是有
02/17 10:04, 15F
→
02/17 10:04, , 16F
最小node指標的版本，只要O(1)
02/17 10:04, 16F
推
02/17 10:15, , 17F
02/17 10:15, 17F
→
02/17 10:15, , 18F
<<是shift left
02/17 10:15, 18F
推
02/17 10:21, , 19F
13 e也是對的吧
02/17 10:21, 19F
推
02/17 10:28, , 20F
想問第5題 雖然我也是選F 但不太確定概念是否正確
02/17 10:28, 20F
→
02/17 10:30, , 21F
13e我手誤忘了寫哈哈
02/17 10:30, 21F
推
02/17 10:33, , 22F
11b 是因為要先找到last前一node. 要花O(n)
02/17 10:33, 22F
→
02/17 10:38, , 23F
懂了，感謝d大，另外5我寫true，wiki上也是寫「work in c
02/17 10:38, 23F
→
02/17 10:38, , 24F
onstant amortized time」
02/17 10:38, 24F
推
02/17 10:49, , 25F
insert 的 amortized complexity 是O(1) 但扣掉之後我就不
02/17 10:49, 25F
→
02/17 10:49, , 26F
太清楚分攤成本是多少了
02/17 10:49, 26F
→
02/17 10:52, , 27F
有看到Horowitz寫複雜度是O(i+c+dk+(dm+d)logi)
02/17 10:52, 27F
推
02/17 11:06, , 28F
6是true喔！如果是DAG就
02/17 11:06, 28F
→
02/17 11:06, , 29F
走一次topology即可
02/17 11:06, 29F
推
02/17 11:12, , 30F
false吧 要O(V+E)不是嗎
02/17 11:12, 30F
推
02/17 11:18, , 31F
因為題目用can，我想說edge最少是(n-1)，所以就選了
02/17 11:18, 31F
推
02/17 11:24, , 32F
7寫T +1 想說小於等於敘述對
02/17 11:24, 32F
→
02/17 11:30, , 33F
12題c資結和演算不同 d我有寫@@
02/17 11:30, 33F
→
02/17 11:32, , 34F
16題 b後來查是正八面體 一堆正三角形那個 順便問一下16
02/17 11:32, 34F
→
02/17 11:32, , 35F
d
02/17 11:32, 35F
推
02/17 12:43, , 36F
7是true吧
02/17 12:43, 36F
→
02/17 12:44, , 37F
2-3-4樹 外部結點高度相等
02/17 12:44, 37F
推
02/17 12:49, , 38F
可是7 兩邊高度不能相差1吧
02/17 12:49, 38F
推
02/17 12:55, , 39F
有道理 那又是題意問題惹QQ
02/17 12:55, 39F
推
02/17 18:51, , 40F
想問4為什麼false 如果array是sort過的而且是遞減 這樣也沒
02/17 18:51, 40F
→
02/17 18:51, , 41F
辦法嗎
02/17 18:51, 41F
→
02/17 19:07, , 42F
如果sorted且知道最後一個為min那就可以
02/17 19:07, 42F
→
02/17 19:07, , 43F
但是一般來說不行
02/17 19:07, 43F
→
02/17 19:08, , 44F
我覺得即使用can也有點太牽強 不足以讓我選T哈哈
02/17 19:08, 44F
※ 編輯: goldflower (61.60.217.209), 02/17/2016 19:13:33
→
02/17 19:12, , 45F
題目講的是一般的情況 所以不能自己加條件
02/17 19:12, 45F
推
02/17 21:58, , 46F
15 所以台大的TREE高度要從0開始看喔@@
02/17 21:58, 46F
→
02/17 22:12, , 47F
台大題目寫起來都是這樣的 或你直接用Fh+2-1來看更保險
02/17 22:12, 47F
推
02/17 22:35, , 48F
可是Fh+2-1看也不能確定是0開始還1開始吧QQ
02/17 22:35, 48F
→
02/17 22:45, , 49F
古代台大電機題目是假設root是1
02/17 22:45, 49F
推
02/17 22:51, , 50F
只好看他會不會說了冏
02/17 22:51, 50F
→
02/17 23:01, , 51F
像這題 就h=3 算F5-1 就避掉root是0還是1開始的問題了
02/17 23:01, 51F
→
02/18 00:07, , 52F
上一行講錯了
02/18 00:07, 52F
→
02/18 00:13, , 53F
這樣必須要h=4 才會是7個node啊
02/18 00:13, 53F
→
02/18 00:13, , 54F
因為洪逸很常用h=5 12個點的例子 所以我看到7個點
02/18 00:13, 54F
→
02/18 00:13, , 55F
直覺就是 h是4才對
02/18 00:13, 55F
→
02/18 01:41, , 56F
我寫成F5=8了= =所以算錯QQ
02/18 01:41, 56F
※ 編輯: goldflower (61.60.217.209), 02/18/2016 01:44:11
‣ 更多 goldflower 的文章
文章代碼(AID): #1Mmq0EkE (Grad-ProbAsk)
‣ 更多 goldflower 的文章
文章代碼(AID): #1Mmq0EkE (Grad-ProbAsk)