版上好像没找到 所以来跟大家对答案 但是我考台大电机通常都错满多的...
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) 这个复杂度是对的吗
谢谢大家
作者:
mistel (Mistel)
2020-02-06 21:04:00今年的吗？我大后天会写到
作者:
mistel (Mistel)
2020-02-06 21:16:00作者:
DLHZ ( )
2020-02-06 21:21:00我还想说为什么是大后天写到XDD
作者:
mistel (Mistel)
2020-02-06 21:53:00你说BFS的mem需求较大，有来源吗？ 我是以递回去想喔
作者:
DLHZ ( )
2020-02-06 21:53:002. heapify不是应该是lgn吗
我觉得13D用递回去解释不太适合，因为递回都可以循环去做
作者:
DLHZ ( )
2020-02-06 21:58:00原来不一样 了解了那quadratic probing不是xi+yi^2吗？
DFS要递回 但是BFS也需要用到Q DFS最长的呼叫长度是V-1(之后的呼叫会释放空间）但是BFS没有限制的感觉
我16B算O(n)，我把它当成T(n)=T(n-1)+O(1)因为只是把算到an-1的部分乘上x，再加an，所以是constant time
quadratic 如果 10格，打中 4，基本上对不到 7不过那要是资料刚好都避开了某些值的情况现在回来看觉得 13E 应该可以选，虽然我当初没选的原因是 不确定是否 acyclic，但如果真的有那也会在时间内 return false
m大我觉得他每解一个括号变量多一个 第一个括号是a0*x15的E我可以解释他解决primary cluster但是没解决second cluster这样吗D大想问你回答的是哪题
作者:
DLHZ ( )
2020-02-06 22:20:00啊啊抱歉 是7
作者:
mistel (Mistel)
2020-02-06 22:20:00秦久韶算法是O(n)没错不过dfs不用递回的话要用stack吧...
对，那样dfs的stack大小最大就是dfs tree的高
作者:
mistel (Mistel)
2020-02-06 22:23:00是说BFS把全部点都放进去Q也是O(V) 所以这题如果不选理由是因为要求的内存大小是一样的？
作者:
DLHZ ( )
2020-02-06 22:26:00DFS的space complexity会是O(h) BFS则是O(max degree)? 应该没有那个一定大于哪个 我觉得要看树长怎样BFS那样讲好像不对
D大我觉得计算完hash function后如果overflow i 次就变成(h(k)+i^2)%m （我不是很懂你问的意思 所以就回答这个）但是现在看如果这题是不是错在collision 因为collision不一定会overflow
作者:
DLHZ ( )
2020-02-06 22:29:00如果考虑一直线的tree DFS要的空间就比BFS大得多 这样解释呢
作者:
mistel (Mistel)
2020-02-06 22:30:00我也觉得好像要看给的问题是什么才能决定BFS DFS需要的内存大小 那这个选项不应该选 感谢各位
作者:
DLHZ ( )
2020-02-06 22:33:00比如说对linear probing第i个collision就是加i 但对quadratic probing可以加xi+yi^2 x,y为常数 而不是单纯的i^2？
我觉得在worst case下BFS与DFS空间复杂度一样 但是ave.下DFS小于BFS然后想问递回呼叫不也是用stack支援的吗喔喔对欸我本来一直以为定义是没有常数的（因为线性没有） 但是刚刚查了才发现quadratic prob定义是有两个常数的谢谢D大
作者:
mistel (Mistel)
2020-02-06 22:42:00对耶 现在才知道有这种的prob方式这样讲的话best case应该是bfs优于dfs吧
应该是说DFS的best case(max degree=n-1)会是BFS的worst case, DFS的worst case(一直线)会是BFS的best case
Min Heap : A[]={1,2,5,3,4,6,7}
there is a min. heap 有这样的一个heap 可以满足他的preorder 是sorted order即可