算法分析与设计考博试题1
需积分: 10 139 浏览量
2017-10-13
11:47:28
上传
评论
收藏 104KB PDF 举报
2011
年博士研究生入学考试试卷
考试科目：算法分析与设计
试卷内容：（算法设计可采用
C
语言、
C++
或
PASCAL
等语言来描述）
一、简要描述分治法的基本思想，并以快速排序算法为例，说明算法的各步
骤及其操作内容：（
10
分）
二、求解下面问题：（
15
分）
（
1
）简要描述求最小生成树的
Prim
算法的基本思想及求解步骤。
（
2
）分析
Prim
算法的时间性能。
（
3
）证明
Prim
算法的正确性。
三、求解下面问题：（
20
分）
（
1
）描述贪心算法的基本思想和主要原理；
（
2
）假设有
n
个活动
E={1,2,…,n}
都需要使用同一会议室，但同一时间内
只能有一个活动来使用。每个活动的使用时间用起止时间表示为
si,fi
。设计算法
求解出最大的相容活动子集合。并对下面示例给出求解的结果。
i
1
2
3
4
5
6
7
8
9
10
11
si
1
3
0
5
3
5
6
8
8
2
12
fi
4
5
6
7
8
9
10
11
12
13
14
（
3
）以反例说明贪心算法不能保证所求结果为最优解。
四、已知矩阵
A1A2A3 A4A5A6
的维数分别如下：（
15
分）
A1
A2
A3
A4
A5
A6
30*35
35*15
15*5
5*10
10*20
20*25
请采用动态规划法求解出最优的计算矩阵连乘
A1A2A3 A4A5A6
的计算次
序。
五、设计算法求从顶点 v0 到图中其余每个顶点的最短路径（以弧数为单位）,
要求尽可能节省时间。（15 分）
六、设计算法将一棵以二叉链表形式存储的二叉树按顺序方式存储到数组
A[]
中。（
10
分）
七、设计算法求出从（
a
1
,a
2
,a
3
,…,a
n
）取出
k
个元素的所有组合。(15 分)
例如，从集合{1,2,3,4}中选取 3 个元素的所有组合的解为：
资源评论
