作者qscez (天使在身旁 xD)
看板Grad-ProbAsk
標題[理工] 107台大資演對答案
時間Mon Jan 28 14:45:43 2019
想討論一下答案
I.
EDBCA AC
II.
CBA
III.
D (討論後更正為B)
C
IV.
CCCC
V.
(a)
(b)
(1)
S,T stack
enque(Q,x){
if S是滿的 return "Q滿"
else push(S,x)
}
dequeue(Q){
if T空 {
if S空 return "Q空"
else pop(S) into T until S空
}
x = pop(T)
return x
}
(2)(3)
VI.
(a) 對Va.Vb 做 Dijkastra Time:O(VlogV+E)
(b)
(1)
(2) 一樣做Dijkastra... Time:O(VlogV+E)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.152.240
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548657950.A.4B9.html
1F：推 j92415: 你算3.8多那題請問是怎麼算的呢？ 我想的很簡單是直接13/5 01/29 16:46
2F：→ j92415: 等於2.6 01/29 16:46
3F：→ j92415: 還有第14題我寫b 但好像BC都行？ 不是拿左邊最大或右邊最 01/29 16:47
4F：→ j92415: 小取代嗎？ 你有想法嗎 01/29 16:47
5F：→ j92415: 其他都一樣 01/29 16:47
6F：推 j92415: 我是指選擇 01/29 16:59
7F：→ qscez: 1/13*(4*5+2*3+2*3+2*3+3*4) 不過剛看洪毅筆記變成3.4 ... 01/30 11:42
8F：→ qscez: 對 BC都可以 01/30 11:44
9F：→ qscez: 說錯 4.4 平均的話應該就是你說的2.6沒錯 k不一定在裡面 01/30 11:49
※ 編輯: qscez (1.171.152.240), 01/30/2019 11:51:04
10F：推 Leaving: 1.4是c 01/30 12:35
11F：推 Leaving: VI.a是找minimum bottleneck tree 01/30 12:37
12F：→ Leaving: bottleneck是整條path中weight最大edge的weight 01/30 12:38
13F：→ Leaving: 要把Dijkstra改一點點 01/30 12:39
14F：推 Leaving: VI.b.2 應該可以用bfs 01/30 12:58
15F：→ Leaving: 啊說錯 VI.b.1才對 01/30 12:58
16F：→ Leaving: VI.a 名字講錯了 不是min. bottleneck tree 是應該叫mini 01/30 13:03
17F：→ Leaving: max path problem 01/30 13:03
※ 編輯: qscez (1.171.152.240), 01/30/2019 15:55:34
19F：→ qscez: 感謝L大補充 把heapify跟create搞混了哈 01/30 15:56
20F：→ qscez: 請問是因為他說要fixed at the same time所以用minimax嗎 01/30 15:57
21F：→ qscez: 查了一下感覺大部分都用在棋局 01/30 15:58
22F：→ Leaving: 對，就是因為那句 01/30 16:13
23F：→ Leaving: 用在哪我是沒研究過XD 01/30 16:13
24F：推 j92415: 請問結論所以那題平均長度是多少呀？ 01/30 17:30
25F：→ j92415: 就2.6怕嗎 01/30 17:30
26F：→ qscez: 把它想成所有data的平均失敗搜尋比較次數 02/08 23:01