试卷算法分析与设计.docx

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

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

2、/AnarrayP[0..m-1]ofmcharactersrepresentingapattern//Output:Thepositionofthefirstcharacterinthetextthatstartsthefirstmatching//substringifthesearchissuccessfuland-1otherwisefori0ton-mdoj0whilej

3、系改正。2.比较Prim算法和Kruskal算法的异同，这两种算法采用什么设计策略，阐述该策略可能的应用场合。（20分）42020年4月19日文档仅供参考，不当之处，请联系改正。3.算法复杂度分析。（每小题10分，共20分）（1）ALGORITHMGaussElimination(A[1..n,1..n],b[1..n])fori1tondoA[i,n+1]b[i]fori1ton-1doforji+1tondoforkiton+1doA[j,k]A[j,k]-A[i,k]*A[j,i]/A[i,i]52020年4月19日