作者mistel (Mistel)
看板Grad-ProbAsk
标题[理工] 108电机丙 资结对答案
时间Mon Dec 23 17:02:48 2019
硬体直接崩溃，就不对答案了..
1.F
2.T
3.F
4.T
5.T
6.F
7.T
8.F
9.F
10.F
11.ABCDE
12.BCDE
13.BCD
14.BC
15.CD
16.AB
最後一题B选项完全不知道是什麽
另外也不清楚是非题第7题这样叙述该是对还是错
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.137.243.184 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577091770.A.A30.html
※ 编辑: mistel (223.137.243.184 台湾), 12/23/2019 17:07:57
※ 编辑: mistel (223.137.243.184 台湾), 12/23/2019 17:08:28
※ 编辑: mistel (223.137.243.184 台湾), 12/23/2019 17:09:32
※ 编辑: mistel (223.137.243.184 台湾), 12/23/2019 17:09:56
1F：推 jeremyyuan: 12 E AVL tree delete rotation 是O(n)12/23 18:42
感谢，发现E应该是错的，不过他应该是考single rotation跟double rotation？
所以正确应该改成 one single rotation or double rotation....
2F：→ jeremyyuan: 14 ABD 都会因为一开始是小到大或大到小而sensitive12/23 18:44
3F：→ jeremyyuan: 所以是CE吧12/23 18:44
selection sort无论input data是什麽都是O(n^2)吧？
Radix sort我是觉得不知道input data range 算不算sensitive所以没选
4F：→ jeremyyuan: 其他的我13选BE 15选CE 16选ABD 然後是非都跟你一样12/23 18:47
13.E只讲directed没讲到acylic不知道能不能选？
C我选是因为DFS要用到递回，D是因为BFS可以在无权图上找到最短边，而且枫叶本有提到Di
jkstra's是从BFS延伸的（page.594）
16.D请问大大复杂度算出来是多少呢？
※ 编辑: mistel (223.137.243.184 台湾), 12/23/2019 19:06:30
※ 编辑: mistel (223.137.243.184 台湾), 12/23/2019 19:06:53
5F：→ jeremyyuan: 13 14你应该没错 我看错了12/23 19:22
6F：→ jeremyyuan: 16 AB没错12/23 19:41
7F：→ jeremyyuan: 目前不一样的就是 15 D quadratic 会有probe不到的问12/23 19:48
8F：→ jeremyyuan: 题 E 我也不确定12/23 19:48
9F：→ jeremyyuan: 拍谢刚刚边吃饭边看 现在才回到家找之前写的答案 所以12/23 19:53
10F：→ jeremyyuan: 错有点多XD 你可以修掉没关系12/23 19:53
感谢j大帮忙对答案！
目前修改成这样，不确定的我先标起来了
https://i.imgur.com/RQi994W.jpg
15我觉得j大是对的，E选项我再查查有没有课文是有讲过
※ 编辑: mistel (223.137.243.184 台湾), 12/23/2019 21:57:05
11F：推 ekids1234: AVL 2 rotation 有例子吗 ?12/23 22:27
是指double rotation (RL,LR), single rotation (RR,LL)
one single rotation意思是一个RR,LL的rotation，这样就错了
12F：→ b10007034: 16 的B是false，枫叶本有 12/23 22:28
请问b大连CLRS都写完了吗QQ? 太强了...
13F：→ ekids1234: 我觉得 4 是 F (平均约n) ,6 T12/23 22:32
https://i.imgur.com/7Nz233Y.jpg
4.参考洪逸第四章
6.我认为错是错在rehashing跟chain都是碰撞的解决方法，而如果chain会使一个链结过长
，那代表hashing function本身就有问题了，所以应该改善hashing function才对
14F：→ ekids1234: 16 这样的话好像只剩 A，但又觉得好像不包含合并时间 12/23 22:33
15F：→ ekids1234: 又或是 cut the problem 的时间已经包含合并的时间了?12/23 22:34
不一定吧？合并成本可能低於切割时间，所以在notation下我们就看不出来了~
※ 编辑: mistel (223.137.243.184 台湾), 12/24/2019 12:02:05
16F：→ mistel: 答案晚上一并更新~ 12/24 12:02
17F：→ ekids1234: 4. 的确，之前说n有点太随便了，不过题目是说 1/4 of n 12/24 12:33
18F：→ ekids1234: (n+1)/2 的话接近 n*(1/2)，不知道这有没有差 12/24 12:33
19F：→ ekids1234: 6 的话改善 hash function 应该同 rehashing ? 12/24 12:34
20F：→ b10007034: 没人写得完CLRS吧，没意义 12/24 12:35
21F：→ b10007034: 4.题意看起来是说n/4？还是我搞错了 12/24 12:35
22F：→ mistel: 我是想说单纯只论insert和delete，link list跟array比较 12/24 12:51
23F：→ mistel: 的话，前者只要O(1)後者要O(n)，但仔细看看题目说到n/4好 12/24 12:51
24F：→ mistel: 像主要错在这边？ 12/24 12:51
25F：→ Fanchien: 可是我在网路上看Horner’s method是n^2耶QQ 12/24 13:56
26F：→ Fanchien: 16的A 网路上也有PPT是写logn 12/24 13:56
27F：→ jeremyyuan: 恩恩 4应该是错在n/4了 Horner best 是O(logn) worst 12/24 14:02
28F：→ jeremyyuan: 才是n^2 12/24 14:02
29F：→ jeremyyuan: *O(nlogn) 12/24 14:04
30F：推 misaka0120: 16. C如果是python的话那个回圈会跑7次 01/17 18:53
31F：推 Fanchien: 3.是true 只要找到存在即可 01/18 20:10
32F：→ mistel: 3是true没错 感谢 01/27 18:00