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

看板Grad-ProbAsk作者 (howard)時間8年前 (2018/01/20 21:47), 編輯推噓17(17推 0噓 49→)
留言66則, 10人參與, 8年前最新討論串1/1
因為我沒有答案 所以就把我的答案放上來給大家對看看 題目如下： https://imgur.com/E3eGWak
https://imgur.com/Cj1IXew
https://imgur.com/zZfwSIW
https://imgur.com/XcPsNUG
單選 1-5 ABAAB 6-10 AAABB 11 ABE 12 BE 13 A 14 C 15 BC 16 E 16題的C跟去年一樣我還錯ＱＱ 有問題大家一起來討論吧！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.80.130.221 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1516456058.A.D2C.html
推
01/20 22:22, 8年前 , 1F
嗨第四題我只有找到find min是O(log n)所以會不會是B?
01/20 22:22, 1F
→
01/20 22:24, 8年前 , 2F
第九題我沒有覺得哪裡錯欸 想知道你的想法~
01/20 22:24, 2F
→
01/20 22:26, 8年前 , 3F
11題我選CD 我只有single rotation 最後root是b
01/20 22:26, 3F
→
01/20 22:27, 8年前 , 4F
11題能看你的過程嗎QQ
01/20 22:27, 4F
→
01/20 22:43, 8年前 , 5F
13我選AB 16我選ABE
01/20 22:43, 5F
→
01/20 22:44, 8年前 , 6F
12和15我不會 可以教我嗎QQ
01/20 22:44, 6F
→
01/20 22:44, 8年前 , 7F
第四題是因為高度只有log吧
01/20 22:44, 7F
→
01/20 22:50, 8年前 , 8F
9是logn
01/20 22:50, 8F
→
01/20 22:57, 8年前 , 9F
01/20 22:57, 9F
→
01/20 22:57, 8年前 , 10F
13長這樣
01/20 22:57, 10F
→
01/20 22:58, 8年前 , 11F
16a 立方體就不是plannar
01/20 22:58, 11F
→
01/20 22:58, 8年前 , 12F
b我不會
01/20 22:58, 12F
→
01/20 23:12, 8年前 , 13F
11題可以用你的想法告訴我嗎？
01/20 23:12, 13F
→
01/20 23:12, 8年前 , 14F
12 a我不知道
01/20 23:12, 14F
→
01/20 23:12, 8年前 , 15F
01/20 23:12, 15F
→
01/20 23:12, 8年前 , 16F
d乾好像可以在worse case 是skew tree
01/20 23:12, 16F
→
01/20 23:12, 8年前 , 17F
e就用avl tree
01/20 23:12, 17F
→
01/20 23:12, 8年前 , 18F
15a order0不至於吧
01/20 23:12, 18F
→
01/20 23:12, 8年前 , 19F
b這個洪逸有上過103中山考過
01/20 23:12, 19F
→
01/20 23:12, 8年前 , 20F
c你就帶數字看看就知道了
01/20 23:12, 20F
→
01/20 23:12, 8年前 , 21F
d我不太會這個選項
01/20 23:12, 21F
→
01/20 23:12, 8年前 , 22F
e不一定 有可能一個比較小就當root
01/20 23:12, 22F
→
01/20 23:14, 8年前 , 23F
然後歡迎神人來打我臉ＸＤ這樣我才學到更多
01/20 23:14, 23F
→
01/20 23:16, 8年前 , 24F
13題我確定圖長那樣我查了很多2-3-4樹的建法
01/20 23:16, 24F
→
01/20 23:17, 8年前 , 25F
然後11題的時候我有點猶豫我覺得有做錯
01/20 23:17, 25F
→
01/20 23:20, 8年前 , 26F
15a single node 就是order 0
01/20 23:20, 26F
推
01/20 23:31, 8年前 , 27F
9. 如果他是指Min heap的話，應該不知道最大值是在左右
01/20 23:31, 27F
→
01/20 23:31, 8年前 , 28F
子樹其中之一吧？會不會還是用陣列的找法O(n)？
01/20 23:31, 28F
→
01/20 23:56, 8年前 , 29F
11 我選CE，T4 +1 node時a不平衡使得b當root
01/20 23:56, 29F
→
01/20 23:58, 8年前 , 30F
13 我選ab，1,2,3那個就是4-node
01/20 23:58, 30F
推
01/21 00:11, 8年前 , 31F
11我寫CD
01/21 00:11, 31F
→
01/21 00:12, 8年前 , 32F
Minheap用陣列找只要找葉子處，O(long)
01/21 00:12, 32F
推
01/21 00:15, 8年前 , 33F
14我寫BCE欸XDD 不過沒有很認真算，計算紙很雜亂
01/21 00:15, 33F
推
01/21 00:18, 8年前 , 34F
16b不是這樣嗎@@? https://i.imgur.com/x1deCAr.jpg
01/21 00:18, 34F
→
01/21 00:30, 8年前 , 35F
想問w大，leaf不是會有n/2個嗎？
01/21 00:30, 35F
推
01/21 00:35, 8年前 , 36F
阿我也想說leaf有n/2個 所以想說第九題是否為O(n/2)
01/21 00:35, 36F
→
01/21 00:41, 8年前 , 37F
14題我算(a)33 (b)79/29 (c)45/56 (d)79/86
01/21 00:41, 37F
→
01/21 00:42, 8年前 , 38F
(e)因為a選項會從33變成133所以這個選項不對?
01/21 00:42, 38F
推
01/21 00:44, 8年前 , 39F
我搞錯qq 但是top down一直往大的那邊找就會找到了
01/21 00:44, 39F
→
01/21 00:44, 8年前 , 40F
我想問大家是把<<8換成*256這樣都用十進位算嗎?
01/21 00:44, 40F
→
01/21 00:44, 8年前 , 41F
可是他還是mod 100啊，沒說變成mod 200
01/21 00:44, 41F
→
01/21 00:45, 8年前 , 42F
不對往大的找也不一定會找到
01/21 00:45, 42F
→
01/21 00:47, 8年前 , 43F
那好像要O(n)欸 xd
01/21 00:47, 43F
推
01/21 01:03, 8年前 , 44F
w大喔喔我以為200buckets代表要換成mod100 QQ
01/21 01:03, 44F
→
01/21 01:03, 8年前 , 45F
感謝你肯定O(n) (已累癱
01/21 01:03, 45F
→
01/21 01:04, 8年前 , 46F
11題我不太確定https://imgur.com/EnpU1FI
01/21 01:04, 46F
→
01/21 01:12, 8年前 , 47F
我x,y,z寫反了抱歉 改成z,y,x rotate的方法是圖中的(a)
01/21 01:12, 47F
→
01/21 01:12, 8年前 , 48F
01/21 01:12, 48F
→
01/21 01:13, 8年前 , 49F
z是新增node後往上數第一個遇到的unbalanced node
01/21 01:13, 49F
→
01/21 01:15, 8年前 , 50F
y:z的有比較大的height的child, x:y的有比較大的height的
01/21 01:15, 50F
→
01/21 01:15, 8年前 , 51F
child
01/21 01:15, 51F
→
01/21 01:16, 8年前 , 52F
那個冒號":"是"是"的意思
01/21 01:16, 52F
推
01/21 14:14, 8年前 , 53F
13題我用B-tree visualization這個網站跑出來的結果只
01/21 14:14, 53F
→
01/21 14:14, 8年前 , 54F
有E是對的啊？能否問下大大們的建置步驟是?
01/21 14:14, 54F
推
01/21 14:20, 8年前 , 55F
喔喔沒注意到是top down
01/21 14:20, 55F
推
01/21 14:47, 8年前 , 56F
第四題不同binomial tree之間沒排序關係，找任意元素有可
01/21 14:47, 56F
→
01/21 14:47, 8年前 , 57F
能需要到O(n)吧？
01/21 14:47, 57F
→
01/21 15:05, 8年前 , 58F
11我的算法跟sfriend大一樣
01/21 15:05, 58F
推
01/21 18:20, 8年前 , 59F
15題因該是BE
01/21 18:20, 59F
推
01/21 18:42, 8年前 , 60F
更正只有B
01/21 18:42, 60F
推
01/21 21:51, 8年前 , 61F
感謝sarsman大 不然原本我很懷疑11題那樣做對不對哈哈
01/21 21:51, 61F
推
01/21 22:47, 8年前 , 62F
第9如果是用min-max heap下去看的話呢？root是min，
01/21 22:47, 62F
→
01/21 22:47, 8年前 , 63F
左右子樹其中一個就是max?
01/21 22:47, 63F
推
01/24 19:46, 8年前 , 64F
16（a)是對的吧
01/24 19:46, 64F
→
01/24 19:46, 8年前 , 65F
01/24 19:46, 65F
推
02/06 23:48, 8年前 , 66F
13題答案是BD吧ㄏㄏ
02/06 23:48, 66F
‣ 更多 howard31622 的文章
文章代碼(AID): #1QOqXwqi (Grad-ProbAsk)