《算法设计与分析》练习题库

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

1、《算法设计与分析》练习题库（加粗红色字体为2013下新增题目）一.概念题：请解释下列术语。1.数据类型2.队列3.多项式复杂度4.满二叉树5.HP-难度6.算法7.S1MD（并行算法）8.连通图9.抽象数据类型1.指数复杂度11・递归12.完全二叉树13.状态空间树14.NP-完全的15.算法与过程16.有向图与无向图17.树18.P类问题19.确定的算法20.NP问题21.最小生成树22.动态规划23.数据结构24.排序二、填空题1.简单递选分类过程中所需进行移动存储的操作次数较少，其最大值为中，其算法复杂性为3.动态规划

2、实际上是研究-类的算法，其应用非常广泛。4.BFS算法的中文名称是算法。5.—棵树屮定义为该树的高度或深度。6-二分检索树要求树中所有结点中的元素满足7•比较树的结点由称为和的两种结点组成。8・外结点用个——结点表示，在二分检索算法屮它表示不成功检索的一种情况。9・由根到所有内部结点的距离之和称为—；由根到所有外部结点的距离之和称为.10.max和min被看成是两个内部函数，它们分別求取两个元素的大者和小者，并认为每次调用其中的一个函数都只需作次元素比较。II.如果用分治策略来设计分类算法，则可使最坏情况吋间变为o(nlog

3、n)o这样的算法称为O12.贪心算法可行的第一个基本要素是。13.当一个问题的最优解包含着它的了问题的最优解时，称此问题具有性质。14.二路归并模式可以用树来表示。15.kruskal算法对于每一个无向连通图g产生一棵。16.因为如果有坏，则可去掉这个坏口不增加这条路径的长度(不含有负长度的环)。如果k是这条最短路径上的一个中间结点，那么一in到k和由k至Ijj的这两条子路径应分为别是由i到k和.由k到j的最短路径。否则,这条由i到j的路径就不是具有最小长度的路径。于是，原理成立。17.为了把动态规划应用于得到一棵最优二分检

4、索树的问题，需要把构造这样的一棵树看成是一系列决策的结果，而且要能列出求取序列的递推式.18.所谓可靠性设计最优化问题是在的约束下，如何使系统的可靠性19.货郎担问题是求取具有的周游路线问题。20.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性：,12.算法的复杂性有和之分，衡量一个算法好坏的标准是o13.某一问题可用动态规划算法求解的显著特征是o14.若序列X二{B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的_个

5、最长公共子序列o三、程序填空题。1.对二叉树的先根次序周游算法递归表示为：procedurePREORDER(T)//T是一棵二元树。T中每个结点有三个信息段：ICHILD,,DATA,RCH1LD//ifTHOthencallVISIT(T)(2)endifendPREORDER1.递归求取最大和最小元索procedureMAXM1N(i・j.fmax,fmin)//A(l：n)是含有n个元素的数组，参数i,j是整数，lWi,jWn////该过程把A(i,j)中的最大和最小元素分别赋给fmax和fmin//intcgcri

6、,j；globaln,A(l：n)case:i=j：fmax<-fmin<-A(i):i=j~l:ifA(i))/2・(1)(2)fmax<-max(gmax,hmax)fmin<-min(gmin,hmin)endcaseendMAXMIN1.用回溯法求子集和数问题的递归回溯算法procedureSUMOFSUB

7、,…，X(k-l)-Ins=工W(j)X(刀且厂=工WO)的值已确定。闫戶k。这些对W(j)按非降次序排列。假定W(1)WM・//globalintegerM,n;globalrealW(l：n)；globalBooleanX(l：n)realr,s；iniegerk,j//牛成左儿子。注意，由于B^=true9因此s+W(k)WM//x(k)eiifs+W(k)=Mthen//子集找到//print(X(j),j<-ltok)elseifs+W(k)+W(k+1)<=Mthen//Bk=yrue//(1)endif〃牛成右

8、儿子和计算Ba的值//endififs+r-W(k)ands+W(k+l)WM//B*=true//thenX(k)《0endSUMOFSUB1.用冋溯法求n-皇后问题的所有解procedureNQUEENS(n)〃此过程使用回溯法求岀在一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有