《算法设计与分析》

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

1、123890123456789.。11・41X_亠1£11・41X1X_亠《算法设计与分析》复习题一、概念题：请解释下列术语。数据类型队列多项式复杂度满二叉树NP-难度算法SIMD併行算法)连通图抽象数据类型指数复杂度递归完全二叉树状态空间树NP-完全的算法与过程有向图与无向图树P类问题确定的算法NP问题二、填空题1.简单递选分类过程中所需进行移动存储的操作次数较少，其最大值为02.一组有序的n个数，釆用逐个查找算法查找一给定的数是否出现在序列中，其算法复杂性为03.动态规划实际上是研究一类的算法，其应用非常广泛。4.BFS算法的

2、中文名称是算法。5.一棵树屮定义为该树的高度或深度。6.二分检索树要求树中所有结点中的元素满足。7.比较树的结点由称为和的两种结点组成。&外结点用一个—结点表示，在二分检索算法中它表示不成功检索的一种情况。9.由根到所有内部结点的距离之和称为;由根到所有外部结点的距离之和称为.10.max和min被看成是两个内部函数，它们分别求取两个元素的大者和小者，并认为每次调用其中的一个函数都只需作次元素比较。11.如果用分治策略来设计分类算法，则可使最坏情况时间变为o(nlogn)o这样的算法称为O12.贪心算法可行的第一个基本要素是o13

3、.当一个问题的最优解包含着它的子问题的最优解时，称此问题具有性质。14.二路归并模式可以用树来表示。15.kruskal算法对于每一个无向连通图£产生一棵。16.因为如果有环，则可去掉这个环且不增加这条路径的长度(不含有负长度的环)。如果k是这条最短路径上的一个中间结点，那么一由i到k和由k到j的这两条子路径应分为别是由i到k和.由k到j的最短路径。否则，这条由i到j的路径就不是具有最小长度的路径。于是，原理成立。17.为了把动态规划应用于得到一棵最优二分检索树的问题，需要把构造这样的一棵树看成是一系列决策的结果，而且要能列出求取

4、序列的递推式.1&所谓可靠性设计最优化问题是在的约朿下，如何使系统的可靠性达到最优的问题。19.货郎担问题是求取具有的周游路线问题。三、程序填空题。1.对二叉树的先根次序周游算法递归表示为：procedurePREORDER(T)//T是一棵二元树。T中每个结点有三个信息段：ICIIILD,,DATA,RCHILD//ifTHOthencallVISIT(T)(1)(2)endifendPREORDER2.递归求取最大和最小元素procedureMAXMIN(i.j.fmax,fmin)//A(l：n)是含有n个元素的数组，参数i

5、,j是整数，lWi,jWn//〃该过程把A(i,j)中的最大和最小元素分别赋给fmax和fmin//integeri,j；globaln,A(1:n)case:i=j：fmax<-fmin<-A(i):i=j-l：ifA(i)

6、cedureSUMOFSUB

7、W(k+1)<=Mthen//Bk=yrue//(1)endif//生成右儿子和计算B*的值//endififs+r~W(k)ands+W(k+l)WM//B«=true//thenX(k)《0(2)endifendSUMOFSUB1.用回溯法求n-皇后问题的所有解procedureNQUEENS(n)//此过程使用回溯法求出在一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有可能位置//integerk,n,X(1:n)X(1)GO；k《l//k是当前行；X(k)是当前列//whilek>0do//对所有的行执行以下语句//X

8、(k)《X(k)+l〃移到下一列//whileX(k)WnandnotPLACE(k)do//此处能放这个皇后吗//COrepeatifX(k)Wn〃找到一个位置//thenifk=n〃是一个完整的解吗//thenprint(X)//是，打印这个数