这里写自定义目录标题
- 国科大计算机算法考试2021（陈玉福）
- 1.利用快速Fourier变换计算
g
(
x
)
,
f
(
x
)
g(x),f(x)
g(x),f(x)的乘积
- 2.给定
a
～
h
a \sim h
a～h字符的频率，画出huffman树，写出huffman编码
- 3.矩阵连乘问题。给定5个矩阵：
A
1
,
A
2
.
A
3
,
A
4
,
A
5
A_1,A_2.A_3,A_4,A_5
A1?,A2?.A3?,A4?,A5?，
P
0
,
P
1
,
P
2
,
P
3
,
P
4
,
P
5
P_0,P_1,P_2,P_3,P_4,P_5
P0?,P1?,P2?,P3?,P4?,P5?给定，利用动态规划算法给出最优加括号策略。
- 4.0/1背包问题的分支界限算法。给定6个物品，
(
w
1
,
w
2
,
w
3
,
w
4
,
w
5
,
w
6
)
,
(
p
1
,
p
2
,
p
3
,
p
4
,
p
5
,
p
6
)
(w_1,w_2,w_3,w_4,w_5,w_6),(p_1,p_2,p_3,p_4,p_5,p_6)
(w1?,w2?,w3?,w4?,w5?,w6?),(p1?,p2?,p3?,p4?,p5?,p6?)，画出分枝界限算法搜索的状态空间树，给出节点搜索顺序，给出最优值。
- 5.NPC问题的证明。
- 6.打破对称——AC(4)算法；
-
国科大计算机算法考试2021（陈玉福）
考试题目回忆版
1.利用快速Fourier变换计算
g
(
x
)
,
f
(
x
)
g(x),f(x)
g(x),f(x)的乘积
2.给定
a
～
h
a \sim h
a～h字符的频率，画出huffman树，写出huffman编码
3.矩阵连乘问题。给定5个矩阵：
A
1
,
A
2
.
A
3
,
A
4
,
A
5
A_1,A_2.A_3,A_4,A_5
A1?,A2?.A3?,A4?,A5?，
P
0
,
P
1
,
P
2
,
P
3
,
P
4
,
P
5
P_0,P_1,P_2,P_3,P_4,P_5
P0?,P1?,P2?,P3?,P4?,P5?给定，利用动态规划算法给出最优加括号策略。
4.0/1背包问题的分支界限算法。给定6个物品，
(
w
1
,
w
2
,
w
3
,
w
4
,
w
5
,
w
6
)
,
(
p
1
,
p
2
,
p
3
,
p
4
,
p
5
,
p
6
)
(w_1,w_2,w_3,w_4,w_5,w_6),(p_1,p_2,p_3,p_4,p_5,p_6)
(w1?,w2?,w3?,w4?,w5?,w6?),(p1?,p2?,p3?,p4?,p5?,p6?)，画出分枝界限算法搜索的状态空间树，给出节点搜索顺序，给出最优值。
5.NPC问题的证明。
（1）证明旅行商问题是NPC问题；
（2）证明旅行商问题的
?
\epsilon
?近似算法是NP难问题。
6.打破对称——AC(4)算法；
6-皇后问题，给出
x
3
,
x
4
,
x
5
,
x
6
x_3,x_4,x_5,x_6
x3?,x4?,x5?,x6?的值域。
（1）补全counter矩阵和s矩阵；
（2）说明AC-4的执行过程；
（3）SDBS：当目前有
x
3
=
s
,
x
4
=
r
{x_3=s,x_4=r}
x3?=s,x4?=r时，需要添加哪几种对称约束？
注意事项：带计算器！
|