《算法设计与分析》练习题库及答案(加粗红色字体为2013下新增题目) 一、概念题：请解释下列术语。

1．数据类型2．队列3．多项式复杂度4．满二叉树5． NP-难度6．算法7． SIMD(并行算法)8．连通图9．抽象数据类型10．指数复杂度11．递归12．完全二叉树13．状态空间树14． NP-完全的15．算法与过程16．有向图与无向图17．树18． P类问题19. 确定的算法20. NP问题21. 最小生成树22. 动态规划23. 数据结构24. 排序二、填空题1. 简单递选分类过程中所需进行移动存储的操作次数较少，其最大值为___________。

2. 一组有序的n个数，采用逐个查找算法查找一给定的数是否出现在序列中，其算法复杂性为_____________。

3. 动态规划实际上是研究一类__________________的算法，其应用非常广泛。

4. BFS算法的中文名称是______________________算法。

5. 一棵树中定义为该树的高度或深度。

6. 二分检索树要求树中所有结点中的元素满足。

7. 比较树的结点由称为和的两种结点组成。

8. 外结点用一个结点表示，在二分检索算法中它表示不成功检索的一种情况。

9. 由根到所有内部结点的距离之和称为 ;由根到所有外部结点的距离之和称为 .10．max和min被看成是两个内部函数，它们分别求取两个元素的大者和小者，并认为每次调用其中的一个函数都只需作次元素比较。

11．如果用分治策略来设计分类算法，则可使最坏情况时间变为o(n logn)。

这样的算法称为。

12.贪心算法可行的第一个基本要素是。

13. 当一个问题的最优解包含着它的子问题的最优解时，称此问题具有性质。

14. 二路归并模式可以用树来表示。

15. kruskal算法对于每一个无向连通图g产生一棵。

16．因为如果有环，则可去掉这个环且不增加这条路径的长度(不含有负长度的环)。

如果k是这条最短路径上的一个中间结点，那么—由i到k和由k 到j的这两条子路径应分为别是由i到k和．由k到j的最短路径。

否则，这条由i到j的路径就不是具有最小长度的路径。

于是，原理成立。

17.为了把动态规划应用于得到一棵最优二分检索树的问题，需要把构造这样的一棵树看成是一系列决策的结果，而且要能列出求取序列的递推式.18. 所谓可靠性设计最优化问题是在的约束下，如何使系统的可靠性达到最优的问题。

19.货郎担问题是求取具有的周游路线问题。

20.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性：__________，__________，__________，__________，__________。

21.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是___________。

22.某一问题可用动态规划算法求解的显著特征是_____________________。

23.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。

三、程序填空题。

1．对二叉树的先根次序周游算法递归表示为：procedure PREORDER(T)//T是一棵二元树。

T中每个结点有三个信息段：ICHILD，，DATA，RCHILD// if T≠0 then call VISIT(T)__________(1)_____________________(2)___________endifend PREORDER2．递归求取最大和最小元素procedure MAXMIN(i．j. fmax，fmin)//A(1：n)是含有n个元素的数组，参数i，j是整数，1≤i，j≤n// //该过程把A(i，j)中的最大和最小元素分别赋给fmax和fmin// integer i，j；global n，A(1：n)case：i=j：fmax←fmin←A(i)：i=j-1：if A(i)<A(j) then fmax←A(j)；fmin←A(i)else fmax←A(i)；fmin←A(j)endif: else: mid ← ⎣⎦2/)(j i +___________(1)_________________________(2)______________fmax ←max(gmax ，hmax)fmin ←min(gmin ，hmin)endcaseend MAXMIN3．用回溯法求子集和数问题的递归回溯算法procedure SUMOFSUB<s ，k ，r)//找W(1：n)中和数为M 的所有子集，进入此过程时X(1)，…，X(k-1)的值已确定。

∑∑-====11)()()(k j n k j j W r j X j W s 且。

这些对Ｗ(j)按非降次序排列。

假定W(1)≤M.//global integer M ，n; global real W(1：n)；global Boolean X(1：n)real r,s ；integer k ，j//生成左儿子。

注意，由于 true B k =-1，因此s+W(k)≤M//X(k)←1if s+W(k)=M then //子集找到／／print (X(j),j ←1 to k )elseif s+W(k)+W(k+1)<=M then //B k =yrue//______________(1)__________________endif//生成右儿子和计算B k 的值//endifif s+r-W(k)≥M and s+W(k+1)≤M ／／B k ＝true ／／then X(k)←0_______________(2)_________________endifend SUMOFSUB4．用回溯法求n-皇后问题的所有解procedure NQUEENS(n)//此过程使用回溯法求出在一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有可能位置//integer k，n，X(1:n)X(1)←0；k←1 //k是当前行；X(k)是当前列//while k>0 do //对所有的行执行以下语句//X(k)←X(k)+1 //移到下一列//while X(k)≤n and not PLACE(k) do //此处能放这个皇后吗//____________(1)___________repeatif X(k)≤n //找到一个位置//then if k＝n //是一个完整的解吗//then print(X) //是，打印这个数组//else _______(2)_______；_______(3)_______； //转向下一行// endifelse _______(4)_______ //回溯//endifrepeatend NQUEENS5.二分查找算法procedure binsrch1 (a，n，x，j)//除n>0外，其余说明与binsrch同//integer low ，high ，mid ，j ，n;low ←1;high ← (1) //high 总比可能的取值大1// while low< (2) domid ←⎣⎦2/)(high low +if x<a(mid) //在循环中只比较一次// then (3)else (4) //x ≥a(mid)//endifrepeatif x=a(low) then j ←low //x 出现//else j ←o //x 不出现//endif ；end binsrch16.求图中每对顶点之间的最短路径。

procedure all—Paths(cost，a, n)／／cost(n，n)是n结点图的成本邻接矩阵；a(i，j)是结点vi到vj的最短路径的成本；cost(i，j)＝0，1≤i≤n／／integer i，j，k，n；real cost(n，n)，a(n，n)for i←1 to n dofor j<--1 to n doa(i，j)<--cost(i，j)repeatrepeat／／将cost(i，j)复制到a（i,j）／／for k<--1to on do ／／对最高下标为k的结点的路径//for i←-1 to n do ／／对于所有可能的结点对／／for i<--1 to n doa(i，j)<--min{ (1) ， (2) } repeatrepeatrepeatend all—Paths7.简单的合并与查找运算procedureu(i，j)//根为i和j的两个不相交集合用它们的并来取代// integeri，jParent(i)<--j;end uproceduref(i)//找包含元素i的树的根//integeri，jj<--i;while ⑴ do //若此结点是根，则Parent(j)<--0//⑵ ;repeatreturn(j)end f8. 插入分类procedure insertionsort(a，n)／／将a(1：n)中的元素按非降次序分类，n≥1//a(0)←-∞／／开始时生成一个虚拟值//for j←⑴ to n do ／／a(1:j-1)已分类//item←a(j)；i←⑵while item<a(i) do ／／0≤i<j／／a(i+1)←a(i)；i ←i-1repeata(i+1)←-itemrepeatend insertionsort9. 归并分类procedure mergesort(low, high)／／a(low: high)是一个全程数组，它含有high-low+1≥0个待分类的元素// integer low, high ；if low<high ；then mid ←⎣⎦2/)(high low + //求这个集合的分割点//call ⑴ ／/将一个子集合分类／／call ⑵ ／／将另一个子集合分类／／call ⑶／／归并两个已分类的子集合//endifend mergesort10. 使用链接表归并已分类的集合procedure merge1 (q，r，p)／／q和r是全程数组link(1:n)中两个表的指针。

这两个表可用来获得全程数组a(1：n)中已分类元素的子集合。

此算法执行后构造出一个由p所指示的新表，利用此表可以得到按非降次序把a中元素分好类的元素表，同时q和r所指示的表随之消失。