作者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/cn.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