作者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/cn.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