[理工] 107台大資演對答案

[qscez (天使在身旁 xD)]

想討論一下答案

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1548657950.A.4B9.html
推 j92415: 你算3.8多那題請問是怎麼算的呢？ 我想的很簡單是直接13/5
→ j92415: 等於2.6
→ j92415: 還有第14題我寫b 但好像BC都行？ 不是拿左邊最大或右邊最
→ j92415: 小取代嗎？ 你有想法嗎
→ j92415: 其他都一樣
推 j92415: 我是指選擇
→ qscez: 1/13*(4*5+2*3+2*3+2*3+3*4) 不過剛看洪毅筆記變成3.4 ...
→ qscez: 對 BC都可以
→ qscez: 說錯 4.4 平均的話應該就是你說的2.6沒錯 k不一定在裡面
※ 編輯: qscez (1.171.152.240), 01/30/2019 11:51:04
推 Leaving: 1.4是c
推 Leaving: VI.a是找minimum bottleneck tree
→ Leaving: bottleneck是整條path中weight最大edge的weight
→ Leaving: 要把Dijkstra改一點點
推 Leaving: VI.b.2 應該可以用bfs
→ Leaving: 啊說錯 VI.b.1才對
→ Leaving: VI.a 名字講錯了 不是min. bottleneck tree 是應該叫mini
→ Leaving: max path problem
→ Leaving: http://i.imgur.com/c7c9W7F.jpg
※ 編輯: qscez (1.171.152.240), 01/30/2019 15:55:34
→ qscez: 感謝L大補充 把heapify跟create搞混了哈
→ qscez: 請問是因為他說要fixed at the same time所以用minimax嗎
→ qscez: 查了一下感覺大部分都用在棋局
→ Leaving: 對，就是因為那句
→ Leaving: 用在哪我是沒研究過XD
推 j92415: 請問結論所以那題平均長度是多少呀？
→ j92415: 就2.6怕嗎
→ qscez: 把它想成所有data的平均失敗搜尋比較次數