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