山东大学2021算法期末
2021 SDU算法导论期末考试
2019 计科
计算题 三道 35’
- (1) 画BFS树 (2) 做DFS 说明各种边的分类
- Floyd 求最短路径矩阵
- 最大流以及最小割的求解(注意最小割怎么写)
证明题 两道 20’
- 图有负环，证明不管做多少次 R e l a x Relax Relax 都有 d [ v i + 1 ] > = d [ v i ] ] + w ( v i , v i + 1 ) d[v_{i+1}] >= d[v_{i]}]+w({v_i},{v_i+1}) d[vi+1]>=d[vi]]+w(vi,vi+1) 成立(负环求和)
- 证明 e 不在任何最小生成树中 等价于 G有环，e是最大的边(边权不同) (课后题)
辨析判断 两道 20’
- 对于一个 C u t ( X , Y ) E x y 是 这 些 割 边 Cut(X,Y) E_{xy} 是这些割边 Cut(X,Y)Exy是这些割边 问 每一个MST 用且仅用一条 E x y E_{xy} Exy中的边 每一个MST 至少用一条 E x y E_{xy} Exy中的边
- 进行了若干次 R e l a x Relax Relax 之后有 π [ y ] = x pi[y] = x π[y]=x d [ y ] = d [ x ] + w ( x , y ) d[y] = d[x] + w(x,y) d[y]=d[x]+w(x,y) 三角不等式
我写的是1.2 和 2.2是对的，但是感觉第一题不是很确定~
算法设计与分析题 两道 25’
- 红蓝交替路径变式，即颜色交替路径，有RGB三种颜色，要求路径上相邻两点颜色不同，求s->t 的颜色路径有几条。(DP思想)
- 完全单连通 即任意(u,v) u->v v->u 都是有且仅有一条简单路，给出判断算法以及算法正确性证明 (我做的是 SCC强连通 + 单连通判断)
