作者zaqxsw2230 (qianling)
看板Grad-ProbAsk
标题[理工] [资演]108台大电机 对答案
时间Thu Feb 6 21:00:17 2020
版上好像没找到 所以来跟大家对答案 但是我考台大电机通常都错满多的...
1.B 6.B 11.ABCDE 16.AB
2.A 7.A 12.BCD
3.A 8.B 13.BCD
4.B 9.B 14.BC
5.A 10.B 15.CE
答案已更新
想请问第15题的C E选项在讲甚麽
还有16的D我算(logn*logn) 这个复杂度是对的吗
谢谢大家
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.72.234.74 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1580994019.A.E84.html
1F：推 mistel: 今年的吗？我大後天会写到02/06 21:04
※ 编辑: zaqxsw2230 (42.72.234.74 台湾), 02/06/2020 21:13:27
2F：→ zaqxsw2230: 抱歉漏打年份 已补上 谢谢02/06 21:14
4F：→ DLHZ: 我还想说为什麽是大後天写到XDD02/06 21:21
看了文章 目前比较疑惑的是m大13题选C 但是BFS空间需求不是比dfs大没错吗 还
有E选项 如果要找TOPOLOGICAL SORT可以用DFS做 同时DFS也可以测试有无CYCLE 若
有 就是没有TOPOLOGICAL SORT 这样解释会太牵强吗 02/06 21:39
※ 编辑: zaqxsw2230 (42.72.234.74 台湾), 02/06/2020 21:49:37
※ 编辑: zaqxsw2230 (42.72.234.74 台湾), 02/06/2020 21:51:08
5F：推 mistel: 你说BFS的mem需求较大，有来源吗？ 我是以递回去想喔02/06 21:53
6F：→ DLHZ: 2. heapify不是应该是lgn吗02/06 21:53
7F：→ mistel: 13.e 我也不知道 我觉得这题比较偏向观落音02/06 21:53
8F：→ mistel: D大说的heapify应该是维持heap的性质？但这边是COMPLETE02/06 21:56
9F：→ mistel: BT转换成heap02/06 21:56
12F：→ meng0415: 我觉得13D用递回去解释不太适合，因为递回都可以回圈去02/06 21:58
13F：→ meng0415: 做02/06 21:58
14F：推 DLHZ: 原来不一样 了解了02/06 21:58
15F：→ DLHZ: 那quadratic probing不是xi+yi^2吗？02/06 22:00
16F：→ zaqxsw2230: DFS要递回 但是BFS也需要用到Q DFS最长的呼叫长度是V 02/06 22:00
17F：→ zaqxsw2230: -1(之後的呼叫会释放空间）但是BFS没有限制的感觉02/06 22:00
18F：→ meng0415: 我16D算O(n*logn*logn)02/06 22:03
19F：→ zaqxsw2230: 我发现我D没看到for回圈..谢谢m大02/06 22:06
20F：→ meng0415: 我16B算O(n)，我把它当成T(n)=T(n-1)+O(1) 02/06 22:08
21F：→ meng0415: 因为只是把算到an-1的部分乘上x，再加an，所以是constan02/06 22:09
22F：→ meng0415: t time 02/06 22:09
23F：推 ekids1234: quadratic 如果 10格，打中 4，基本上对不到 7 02/06 22:11
24F：→ ekids1234: 不过那要是资料刚好都避开了某些值的情况02/06 22:11
25F：→ ekids1234: 现在回来看觉得 13E 应该可以选，虽然我当初没选的原02/06 22:14
26F：→ ekids1234: 因是 不确定是否 acyclic，但如果真的有那也会在时间02/06 22:14
27F：→ ekids1234: 内 return false02/06 22:14
28F：→ zaqxsw2230: m大我觉得他每解一个括号变数多一个 第一个括号是a0*x02/06 22:15
29F：→ zaqxsw2230: 解第二个括号就变成算两个 a0x*x 跟a1*x ......最是1+...+n=O（n^2
）02/06 22:15
30F：→ zaqxsw2230: 15的E我可以解释他解决primary cluster但是没解决seco02/06 22:16
31F：→ zaqxsw2230: nd cluster这样吗02/06 22:16
32F：→ zaqxsw2230: D大想问你回答的是哪题02/06 22:17
34F：→ meng0415: ial-evaluation/02/06 22:18
※ 编辑: zaqxsw2230 (42.72.234.74 台湾), 02/06/2020 22:18:55
35F：→ DLHZ: 啊啊抱歉 是7 02/06 22:20
36F：推 mistel: 秦久韶演算法是O(n)没错 02/06 22:20
37F：→ mistel: 不过dfs不用递回的话要用stack吧... 02/06 22:20
38F：→ meng0415: 对，那样dfs的stack大小最大就是dfs tree的高 02/06 22:23
39F：推 mistel: 是说BFS把全部点都放进去Q也是O(V) 所以这题如果不选理由 02/06 22:23
40F：→ mistel: 是因为要求的记忆体大小是一样的？ 02/06 22:23
41F：→ DLHZ: DFS的space complexity会是O(h) BFS则是O(max degree)? 应该 02/06 22:26
42F：→ DLHZ: 没有那个一定大於哪个 我觉得要看树长怎样 02/06 22:26
43F：→ DLHZ: BFS那样讲好像不对 02/06 22:28
44F：→ zaqxsw2230: D大我觉得计算完hash function後如果overflow i 次就 02/06 22:28
45F：→ zaqxsw2230: 变成(h(k)+i^2)%m （我不是很懂你问的意思 所以就回 02/06 22:28
46F：→ zaqxsw2230: 答这个）但是现在看如果这题是不是错在collision 因 02/06 22:28
47F：→ zaqxsw2230: 为collision不一定会overflow 02/06 22:28
48F：→ DLHZ: 如果考虑一直线的tree DFS要的空间就比BFS大得多 这样解释呢 02/06 22:29
49F：推 mistel: 我也觉得好像要看给的问题是什麽才能决定BFS DFS需要的记 02/06 22:30
50F：→ mistel: 忆体大小 那这个选项不应该选 感谢各位02/06 22:30
51F：→ DLHZ: 比如说对linear probing第i个collision就是加i 但对quadrati 02/06 22:33
52F：→ DLHZ: c probing可以加xi+yi^2 x,y为常数 而不是单纯的i^2？ 02/06 22:33
53F：→ zaqxsw2230: 我觉得在worst case下BFS与DFS空间复杂度一样 但是ave 02/06 22:33
54F：→ zaqxsw2230: .下DFS小於BFS 02/06 22:33
55F：→ zaqxsw2230: 然後想问递回呼叫不也是用stack支援的吗 02/06 22:33
56F：→ zaqxsw2230: 喔喔对欸02/06 22:36
57F：→ zaqxsw2230: 我本来一直以为定义是没有常数的（因为线性没有） 但 02/06 22:38
58F：→ zaqxsw2230: 是刚刚查了才发现quadratic prob定义是有两个常数的 02/06 22:38
59F：→ zaqxsw2230: 谢谢D大 02/06 22:38
60F：推 mistel: 对耶 现在才知道有这种的prob方式 02/06 22:42
61F：→ mistel: 这样讲的话best case应该是bfs优於dfs吧 02/06 22:44
62F：推 mi981027: 应该是说DFS的best case(max degree=n-1) 02/07 00:28
63F：→ mi981027: 会是BFS的worst case, DFS的worst case(一直线) 02/07 00:28
64F：→ mi981027: 会是BFS的best case 02/07 00:28
※ 编辑: zaqxsw2230 (42.72.234.74 台湾), 02/07/2020 10:59:55
65F：推 booowei1203: 我觉得第三题是false耶～ 02/07 11:04
66F：→ b10007034: Min Heap : A[]={1,2,5,3,4,6,7} 02/07 12:02
67F：→ zaqxsw2230: there is a min. heap 有这样的一个heap 可以满足他 02/07 13:12
68F：→ zaqxsw2230: 的preorder 是sorted order即可 02/07 13:12
69F：推 booowei1203: 哦哦哦懂了 没看清楚题目 感谢！！ 02/07 14:01