PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] [資演]108台大電機 對答案
作者:
zaqxsw2230
(qianling)
2020-02-06 21:00:17
版上好像沒找到 所以來跟大家對答案 但是我考台大電機通常都錯滿多的...
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
今年的嗎?我大後天會寫到
作者:
zaqxsw2230
(qianling)
2020-02-06 21:14:00
抱歉漏打年份 已補上 謝謝
作者:
mistel
(Mistel)
2020-02-06 21:16:00
#1U08Awem (Grad-ProbAsk)
作者:
DLHZ
( )
2020-02-06 21:21:00
我還想說為什麼是大後天寫到XDD
作者:
mistel
(Mistel)
2020-02-06 21:53:00
你說BFS的mem需求較大,有來源嗎? 我是以遞迴去想喔
作者:
DLHZ
( )
2020-02-06 21:53:00
2. heapify不是應該是lgn嗎
作者:
zaqxsw2230
(qianling)
2020-02-06 21:57:00
https://i.imgur.com/m0cK57z.jpg
https://www.itread01.com/content/1549758996.html
作者:
meng0415
(meng)
2020-02-06 21:58:00
我覺得13D用遞迴去解釋不太適合,因為遞迴都可以迴圈去做
作者:
DLHZ
( )
2020-02-06 21:58:00
原來不一樣 了解了那quadratic probing不是xi+yi^2嗎?
作者:
zaqxsw2230
(qianling)
2020-02-06 22:00:00
DFS要遞迴 但是BFS也需要用到Q DFS最長的呼叫長度是V-1(之後的呼叫會釋放空間)但是BFS沒有限制的感覺
作者:
meng0415
(meng)
2020-02-06 22:03:00
我16D算O(n*logn*logn)
作者:
zaqxsw2230
(qianling)
2020-02-06 22:06:00
我發現我D沒看到for迴圈..謝謝m大
作者:
meng0415
(meng)
2020-02-06 22:08:00
我16B算O(n),我把它當成T(n)=T(n-1)+O(1)因為只是把算到an-1的部分乘上x,再加an,所以是constant time
作者:
ekids1234
(∵:☆星痕╭☆)
2020-02-06 22:11:00
quadratic 如果 10格,打中 4,基本上對不到 7不過那要是資料剛好都避開了某些值的情況現在回來看覺得 13E 應該可以選,雖然我當初沒選的原因是 不確定是否 acyclic,但如果真的有那也會在時間內 return false
作者:
zaqxsw2230
(qianling)
2020-02-06 22:15:00
m大我覺得他每解一個括號變數多一個 第一個括號是a0*x15的E我可以解釋他解決primary cluster但是沒解決second cluster這樣嗎D大想問你回答的是哪題
作者:
meng0415
(meng)
2020-02-06 22:18:00
https://www.geeksforgeeks.org/horners-method-polynom
ial-evaluation/
作者:
DLHZ
( )
2020-02-06 22:20:00
啊啊抱歉 是7
作者:
mistel
(Mistel)
2020-02-06 22:20:00
秦久韶演算法是O(n)沒錯不過dfs不用遞迴的話要用stack吧...
作者:
meng0415
(meng)
2020-02-06 22:23:00
對,那樣dfs的stack大小最大就是dfs tree的高
作者:
mistel
(Mistel)
2020-02-06 22:23:00
是說BFS把全部點都放進去Q也是O(V) 所以這題如果不選理由是因為要求的記憶體大小是一樣的?
作者:
DLHZ
( )
2020-02-06 22:26:00
DFS的space complexity會是O(h) BFS則是O(max degree)? 應該沒有那個一定大於哪個 我覺得要看樹長怎樣BFS那樣講好像不對
作者:
zaqxsw2230
(qianling)
2020-02-06 22:28:00
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?
作者:
zaqxsw2230
(qianling)
2020-02-06 22:33:00
我覺得在worst case下BFS與DFS空間複雜度一樣 但是ave.下DFS小於BFS然後想問遞迴呼叫不也是用stack支援的嗎喔喔對欸我本來一直以為定義是沒有常數的(因為線性沒有) 但是剛剛查了才發現quadratic prob定義是有兩個常數的謝謝D大
作者:
mistel
(Mistel)
2020-02-06 22:42:00
對耶 現在才知道有這種的prob方式這樣講的話best case應該是bfs優於dfs吧
作者:
mi981027
(呱呱竹)
2020-02-07 00:28:00
應該是說DFS的best case(max degree=n-1)會是BFS的worst case, DFS的worst case(一直線)會是BFS的best case
作者:
booowei1203
(wei)
2020-02-07 11:04:00
我覺得第三題是false耶~
作者:
b10007034
(Warren)
2020-02-07 12:02:00
Min Heap : A[]={1,2,5,3,4,6,7}
作者:
zaqxsw2230
(qianling)
2020-02-07 13:12:00
there is a min. heap 有這樣的一個heap 可以滿足他的preorder 是sorted order即可
作者:
booowei1203
(wei)
2020-02-07 14:01:00
哦哦哦懂了 沒看清楚題目 感謝!!
繼續閱讀
[理工] 109 交大計系16題
Zhu81801
[理工] 一題OS
ok8752665
[理工] 108台科 現代
kate04267426
[理工] 關於page size影響page table
Chen334
[理工] 107 成大程設(algo)
ben4562002
[理工] 108台科線代
rustw2010
108成大電機 計組
Pin66
[理工] 台大電機 計組
gash55025502
[理工] 清大109 計科
mistel
[理工] 台科資工 數學跟計組
deangogi
Links
booklink
Contact Us: admin [ a t ] ucptt.com