[理工] [資演]台大電機 對答案

看板Grad-ProbAsk作者 (qianling)時間4年前 (2020/02/06 21:00), 4年前編輯推噓12(12推 0噓 57→)
留言69則, 8人參與, 4年前最新討論串1/1
版上好像沒找到 所以來跟大家對答案 但是我考台大電機通常都錯滿多的... 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1580994019.A.E84.html
推
02/06 21:04, 4年前 , 1F
今年的嗎？我大後天會寫到
02/06 21:04, 1F
※ 編輯: zaqxsw2230 (42.72.234.74 臺灣), 02/06/2020 21:13:27
→
02/06 21:14, 4年前 , 2F
抱歉漏打年份 已補上 謝謝
02/06 21:14, 2F
推
02/06 21:16, 4年前 , 3F
02/06 21:16, 3F
→
02/06 21:21, 4年前 , 4F
我還想說為什麼是大後天寫到XDD
02/06 21:21, 4F
看了文章 目前比較疑惑的是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
推
02/06 21:53, 4年前 , 5F
你說BFS的mem需求較大，有來源嗎？ 我是以遞迴去想喔
02/06 21:53, 5F
→
02/06 21:53, 4年前 , 6F
2. heapify不是應該是lgn嗎
02/06 21:53, 6F
→
02/06 21:53, 4年前 , 7F
13.e 我也不知道 我覺得這題比較偏向觀落音
02/06 21:53, 7F
→
02/06 21:56, 4年前 , 8F
D大說的heapify應該是維持heap的性質？但這邊是COMPLETE
02/06 21:56, 8F
→
02/06 21:56, 4年前 , 9F
BT轉換成heap
02/06 21:56, 9F
→
02/06 21:57, 4年前 , 10F
02/06 21:57, 10F
→
02/06 21:57, 4年前 , 11F
02/06 21:57, 11F
→
02/06 21:58, 4年前 , 12F
我覺得13D用遞迴去解釋不太適合，因為遞迴都可以迴圈去
02/06 21:58, 12F
→
02/06 21:58, 4年前 , 13F
做
02/06 21:58, 13F
推
02/06 21:58, 4年前 , 14F
原來不一樣 了解了
02/06 21:58, 14F
→
02/06 22:00, 4年前 , 15F
那quadratic probing不是xi+yi^2嗎？
02/06 22:00, 15F
→
02/06 22:00, 4年前 , 16F
DFS要遞迴 但是BFS也需要用到Q DFS最長的呼叫長度是V
02/06 22:00, 16F
→
02/06 22:00, 4年前 , 17F
-1(之後的呼叫會釋放空間）但是BFS沒有限制的感覺
02/06 22:00, 17F
→
02/06 22:03, 4年前 , 18F
我16D算O(n*logn*logn)
02/06 22:03, 18F
→
02/06 22:06, 4年前 , 19F
我發現我D沒看到for迴圈..謝謝m大
02/06 22:06, 19F
→
02/06 22:08, 4年前 , 20F
我16B算O(n)，我把它當成T(n)=T(n-1)+O(1)
02/06 22:08, 20F
→
02/06 22:09, 4年前 , 21F
因為只是把算到an-1的部分乘上x，再加an，所以是constan
02/06 22:09, 21F
→
02/06 22:09, 4年前 , 22F
t time
02/06 22:09, 22F
推
02/06 22:11, 4年前 , 23F
quadratic 如果 10格，打中 4，基本上對不到 7
02/06 22:11, 23F
→
02/06 22:11, 4年前 , 24F
不過那要是資料剛好都避開了某些值的情況
02/06 22:11, 24F
→
02/06 22:14, 4年前 , 25F
現在回來看覺得 13E 應該可以選，雖然我當初沒選的原
02/06 22:14, 25F
→
02/06 22:14, 4年前 , 26F
因是 不確定是否 acyclic，但如果真的有那也會在時間
02/06 22:14, 26F
→
02/06 22:14, 4年前 , 27F
內 return false
02/06 22:14, 27F
→
02/06 22:15, 4年前 , 28F
m大我覺得他每解一個括號變數多一個 第一個括號是a0*x
02/06 22:15, 28F
→
, , 29F
解第二個括號就變成算兩個 a0x*x 跟a1*x ......最是1+...+n=O（n^2
）02/06 22:15
→
02/06 22:16, 4年前 , 30F
15的E我可以解釋他解決primary cluster但是沒解決seco
02/06 22:16, 30F
→
02/06 22:16, 4年前 , 31F
nd cluster這樣嗎
02/06 22:16, 31F
→
02/06 22:17, 4年前 , 32F
D大想問你回答的是哪題
02/06 22:17, 32F
→
02/06 22:18, 4年前 , 33F
02/06 22:18, 33F
→
02/06 22:18, 4年前 , 34F
ial-evaluation/
02/06 22:18, 34F
※ 編輯: zaqxsw2230 (42.72.234.74 臺灣), 02/06/2020 22:18:55
→
02/06 22:20, 4年前 , 35F
啊啊抱歉 是7
02/06 22:20, 35F
推
02/06 22:20, 4年前 , 36F
秦久韶演算法是O(n)沒錯
02/06 22:20, 36F
→
02/06 22:20, 4年前 , 37F
不過dfs不用遞迴的話要用stack吧...
02/06 22:20, 37F
→
02/06 22:23, 4年前 , 38F
對，那樣dfs的stack大小最大就是dfs tree的高
02/06 22:23, 38F
推
02/06 22:23, 4年前 , 39F
是說BFS把全部點都放進去Q也是O(V) 所以這題如果不選理由
02/06 22:23, 39F
→
02/06 22:23, 4年前 , 40F
是因為要求的記憶體大小是一樣的？
02/06 22:23, 40F
→
02/06 22:26, 4年前 , 41F
DFS的space complexity會是O(h) BFS則是O(max degree)? 應該
02/06 22:26, 41F
→
02/06 22:26, 4年前 , 42F
沒有那個一定大於哪個 我覺得要看樹長怎樣
02/06 22:26, 42F
→
02/06 22:28, 4年前 , 43F
BFS那樣講好像不對
02/06 22:28, 43F
→
02/06 22:28, 4年前 , 44F
D大我覺得計算完hash function後如果overflow i 次就
02/06 22:28, 44F
→
02/06 22:28, 4年前 , 45F
變成(h(k)+i^2)%m （我不是很懂你問的意思 所以就回
02/06 22:28, 45F
→
02/06 22:28, 4年前 , 46F
答這個）但是現在看如果這題是不是錯在collision 因
02/06 22:28, 46F
→
02/06 22:28, 4年前 , 47F
為collision不一定會overflow
02/06 22:28, 47F
→
02/06 22:29, 4年前 , 48F
如果考慮一直線的tree DFS要的空間就比BFS大得多 這樣解釋呢
02/06 22:29, 48F
推
02/06 22:30, 4年前 , 49F
我也覺得好像要看給的問題是什麼才能決定BFS DFS需要的記
02/06 22:30, 49F
→
02/06 22:30, 4年前 , 50F
憶體大小 那這個選項不應該選 感謝各位
02/06 22:30, 50F
→
02/06 22:33, 4年前 , 51F
比如說對linear probing第i個collision就是加i 但對quadrati
02/06 22:33, 51F
→
02/06 22:33, 4年前 , 52F
c probing可以加xi+yi^2 x,y為常數 而不是單純的i^2？
02/06 22:33, 52F
→
02/06 22:33, 4年前 , 53F
我覺得在worst case下BFS與DFS空間複雜度一樣 但是ave
02/06 22:33, 53F
→
02/06 22:33, 4年前 , 54F
.下DFS小於BFS
02/06 22:33, 54F
→
02/06 22:33, 4年前 , 55F
然後想問遞迴呼叫不也是用stack支援的嗎
02/06 22:33, 55F
→
02/06 22:36, 4年前 , 56F
喔喔對欸
02/06 22:36, 56F
→
02/06 22:38, 4年前 , 57F
我本來一直以為定義是沒有常數的（因為線性沒有） 但
02/06 22:38, 57F
→
02/06 22:38, 4年前 , 58F
是剛剛查了才發現quadratic prob定義是有兩個常數的
02/06 22:38, 58F
→
02/06 22:38, 4年前 , 59F
謝謝D大
02/06 22:38, 59F
推
02/06 22:42, 4年前 , 60F
對耶 現在才知道有這種的prob方式
02/06 22:42, 60F
→
02/06 22:44, 4年前 , 61F
這樣講的話best case應該是bfs優於dfs吧
02/06 22:44, 61F
推
02/07 00:28, 4年前 , 62F
應該是說DFS的best case(max degree=n-1)
02/07 00:28, 62F
→
02/07 00:28, 4年前 , 63F
會是BFS的worst case, DFS的worst case(一直線)
02/07 00:28, 63F
→
02/07 00:28, 4年前 , 64F
會是BFS的best case
02/07 00:28, 64F
※ 編輯: zaqxsw2230 (42.72.234.74 臺灣), 02/07/2020 10:59:55
推
02/07 11:04, 4年前 , 65F
我覺得第三題是false耶～
02/07 11:04, 65F
→
02/07 12:02, 4年前 , 66F
Min Heap : A[]={1,2,5,3,4,6,7}
02/07 12:02, 66F
→
02/07 13:12, 4年前 , 67F
there is a min. heap 有這樣的一個heap 可以滿足他
02/07 13:12, 67F
→
02/07 13:12, 4年前 , 68F
的preorder 是sorted order即可
02/07 13:12, 68F
推
02/07 14:01, 4年前 , 69F
哦哦哦懂了 沒看清楚題目 感謝！！
02/07 14:01, 69F
‣ 更多 zaqxsw2230 的文章
文章代碼(AID): #1UF0tZw4 (Grad-ProbAsk)