试卷算法分析与设计.doc

试卷算法分析与设计

7
2020年4月19日
文档仅供参考，不当之处，请联系改正。
中国计量学院研究生201 4 ~ 201 5 年第 1 学期
《算法分析与设计》课程考试试卷
开课二级学院： 信息工程学院 ， 开课教师： 曾宪庭
考试时间： 年 11 月 24 日 10：00 时，考试地点： D305
考试形式：闭卷□、 开卷□√， 允许带 资料 入场
考生姓名： 学号： 专业：
题序
一
二
三
四
五
总分
得分

评卷人

1. 如下算法采用了什么设计策略，试阐述该策略的原理、优缺点及其可能的应用场合。（20分）
ALGORITHM StringMatch(T[0..n−1], P[0..m−1])
//Input: An array T[0..n−1] of n characters representing a text
// An array P[0..m−1] of m characters representing a pattern
//Output: The position of the first character in the text that starts the first matching
// substring if the search is successful and −1 otherwise
for i ß 0 to n−m do
j ß 0
while j<m and P[j]=T[i+j] do
j ß j+1
if j=m return i
return −1

2. 比较Prim算法和Kruskal算法的异同，这两种算法采用什么设计策略，阐述该策略可能的应用场合。（20分）

3. 算法复杂度分析。（每小题10分，共20分）
（1）ALGORITHM GaussElimination(A[1..n,1..n], b[1..n])
for i ß 1 to n do
A[i, n+1] ß b[i]
for i ß 1 to n−1 do
for j ß i+1 to n do
for k ß i to n+1 do
A[j, k] ß A[j, k]-A[i, k]*A[j, i]/A[i, i]

（2）有两个算法解决同一问题，其中算法A的时间复杂性满足递归方程
î
算法B的时间复杂性满足递归方程
î
分析算法A和算法B的时间复杂度。若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？

4. Space-time tradeoffs策略的指导思想是什么，使用该策略解决的经典问题中你了解了哪些？（20分）

5. 有8个选手参加循环赛，循环赛一共进行7天，每个选手必须与其它的7个选手各赛一场，每个选手一天只比赛一次，设计一个满足上述要求的比赛日程表。若有16个选手参加循环赛呢，试提出解决该问题的算法。（20分）