试卷-算法分析与设计.doc

《试卷-算法分析与设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中国计量学院研究生2014~2015学年第1学期《算法分析与设计》课程考试试卷开课二级学院：信息工程学院，开课教师：曾宪庭考试时间：2014年11月24日10：00时，考试地点：D305考试形式：闭卷□、开卷□√，允许带资料入场考生姓名：学号：专业：题序一二三四五总分得分评卷人1.如下算法采用了什么设计策略，试阐述该策略的原理、优缺点及其可能的应用场合。（20分）ALGORITHMStringMatch(T[0..n−1],P[0..m−1])//Input:AnarrayT[0..n−1]ofncharactersrepresentingatext//AnarrayP[0..m−1]ofm

2、charactersrepresentingapattern//Output:Thepositionofthefirstcharacterinthetextthatstartsthefirstmatching//substringifthesearchissuccessfuland−1otherwiseforiß0ton−mdojß0whilej

3、ALGORITHMGaussElimination(A[1..n,1..n],b[1..n])foriß1tondoA[i,n+1]ßb[i]foriß1ton−1doforjßi+1tondoforkßiton+1doA[j,k]ßA[j,k]-A[i,k]*A[j,i]/A[i,i]（2）有两个算法解决同一问题，其中算法A的时间复杂性满足递归方程î算法B的时间复杂性满足递归方程î分析算法A和算法B的时间复杂度。若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？4.Space-timetradeoffs策略的指导思想是什么，使用该策略解决的经典问题中你了解了哪些

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