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

[zaqxsw2230 (qianling)]

版上好像沒找到 所以來跟大家對答案  但是我考台大電機通常都錯滿多的...
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
推 mistel: 今年的嗎？我大後天會寫到
※ 編輯: zaqxsw2230 (42.72.234.74 臺灣), 02/06/2020 21:13:27
→ zaqxsw2230: 抱歉漏打年份 已補上 謝謝
推 mistel: #1U08Awem (Grad-ProbAsk)
→ DLHZ: 我還想說為什麼是大後天寫到XDD
看了文章 目前比較疑惑的是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
推 mistel: 你說BFS的mem需求較大，有來源嗎？ 我是以遞迴去想喔
→ DLHZ: 2. heapify不是應該是lgn嗎
→ mistel: 13.e 我也不知道 我覺得這題比較偏向觀落音
→ mistel: D大說的heapify應該是維持heap的性質？但這邊是COMPLETE
→ mistel: BT轉換成heap
→ zaqxsw2230:  https://i.imgur.com/m0cK57z.jpg
→ zaqxsw2230: https://www.itread01.com/content/1549758996.html
→ meng0415: 我覺得13D用遞迴去解釋不太適合，因為遞迴都可以迴圈去
→ meng0415: 做
推 DLHZ: 原來不一樣 了解了
→ DLHZ: 那quadratic probing不是xi+yi^2嗎？
→ zaqxsw2230: DFS要遞迴 但是BFS也需要用到Q  DFS最長的呼叫長度是V
→ zaqxsw2230: -1(之後的呼叫會釋放空間）但是BFS沒有限制的感覺
→ meng0415: 我16D算O(n*logn*logn)
→ zaqxsw2230: 我發現我D沒看到for迴圈..謝謝m大
→ meng0415: 我16B算O(n)，我把它當成T(n)=T(n-1)+O(1)
→ meng0415: 因為只是把算到an-1的部分乘上x，再加an，所以是constan
→ meng0415: t time
推 ekids1234: quadratic 如果 10格，打中 4，基本上對不到 7
→ ekids1234: 不過那要是資料剛好都避開了某些值的情況
→ ekids1234: 現在回來看覺得 13E 應該可以選，雖然我當初沒選的原
→ ekids1234: 因是 不確定是否 acyclic，但如果真的有那也會在時間
→ ekids1234: 內 return false
→ zaqxsw2230: m大我覺得他每解一個括號變數多一個 第一個括號是a0*x
→ zaqxsw2230:  解第二個括號就變成算兩個 a0x*x 跟a1*x ......最是1+...+n=O（n^2
）02/06 22:15
→ zaqxsw2230: 15的E我可以解釋他解決primary cluster但是沒解決seco
→ zaqxsw2230: nd cluster這樣嗎
→ zaqxsw2230: D大想問你回答的是哪題
→ meng0415: https://www.geeksforgeeks.org/horners-method-polynom
→ meng0415: ial-evaluation/
※ 編輯: zaqxsw2230 (42.72.234.74 臺灣), 02/06/2020 22:18:55
→ DLHZ: 啊啊抱歉 是7
推 mistel: 秦久韶演算法是O(n)沒錯
→ mistel: 不過dfs不用遞迴的話要用stack吧...
→ meng0415: 對，那樣dfs的stack大小最大就是dfs tree的高
推 mistel: 是說BFS把全部點都放進去Q也是O(V) 所以這題如果不選理由
→ mistel: 是因為要求的記憶體大小是一樣的？
→ DLHZ: DFS的space complexity會是O(h) BFS則是O(max degree)? 應該
→ DLHZ: 沒有那個一定大於哪個 我覺得要看樹長怎樣
→ DLHZ: BFS那樣講好像不對
→ zaqxsw2230: D大我覺得計算完hash function後如果overflow i 次就
→ zaqxsw2230: 變成(h(k)+i^2)%m  （我不是很懂你問的意思 所以就回
→ zaqxsw2230: 答這個）但是現在看如果這題是不是錯在collision 因
→ zaqxsw2230: 為collision不一定會overflow
→ DLHZ: 如果考慮一直線的tree DFS要的空間就比BFS大得多 這樣解釋呢
推 mistel: 我也覺得好像要看給的問題是什麼才能決定BFS DFS需要的記
→ mistel: 憶體大小 那這個選項不應該選 感謝各位
→ DLHZ: 比如說對linear probing第i個collision就是加i 但對quadrati
→ DLHZ: c probing可以加xi+yi^2 x,y為常數 而不是單純的i^2？
→ zaqxsw2230: 我覺得在worst case下BFS與DFS空間複雜度一樣 但是ave
→ zaqxsw2230: .下DFS小於BFS
→ zaqxsw2230: 然後想問遞迴呼叫不也是用stack支援的嗎
→ zaqxsw2230: 喔喔對欸
→ zaqxsw2230: 我本來一直以為定義是沒有常數的（因為線性沒有） 但
→ zaqxsw2230: 是剛剛查了才發現quadratic prob定義是有兩個常數的
→ zaqxsw2230:  謝謝D大
推 mistel: 對耶 現在才知道有這種的prob方式
→ mistel: 這樣講的話best case應該是bfs優於dfs吧
推 mi981027: 應該是說DFS的best case(max degree=n-1)
→ mi981027: 會是BFS的worst case, DFS的worst case(一直線)
→ mi981027: 會是BFS的best case
※ 編輯: zaqxsw2230 (42.72.234.74 臺灣), 02/07/2020 10:59:55
推 booowei1203: 我覺得第三題是false耶～
→ b10007034: Min Heap : A[]={1,2,5,3,4,6,7}
→ zaqxsw2230: there is a min. heap 有這樣的一個heap 可以滿足他
→ zaqxsw2230: 的preorder 是sorted order即可
推 booowei1203: 哦哦哦懂了 沒看清楚題目 感謝！！