《算法设计与分析》复习题
一、 概念题：请解释下列术语。
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问题
二、填空题
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.货郎担问题是求取具有 的周游路线问题。
三、程序填空题。
1．对二叉树的先根次序周游算法递归表示为： procedure PREORDER(T)
//T是一棵二元树。T中每个结点有三个信息段：ICHILD，，DATA，RCHILD// if T≠0 then call VISIT(T) __________(1)___________ __________(2)___________ endif
end PREORDER
2．递归求取最大和最小元素
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) endif ? : else: mid? ? ___________(1)______________ ___________(2)______________ fmax?max(gmax，hmax) fmin?min(gmin，hmin) endcase end MAXMIN 3．用回溯法求子集和数问题的递归回溯算法 procedure SUMOFSUB 。这些对Ｗ(j)按非降次序排列。假定W(1)≤M.// global integer M，n; global real W(1：n)；global Boolean X(1：n) real r,s；integer k，j j?1j?k(i?j)/2s??W(j)X(j)且r??W(j)k?1n//生成左儿子。注意，由于 Bk?1?true，因此s+W(k)≤M// X(k)?1 if s+W(k)=M then //子集找到／／ print (X(j),j?1 to k ) else if s+W(k)+W(k+1)<=M then //B k=yrue// ______________(1)__________________ endif //生成右儿子和计算B k的值// endif if s+r-W(k)≥M and s+W(k+1)≤M ／／B k＝true／／ then X(k)?0 _______________(2)_________________ endif end SUMOFSUB 4．用回溯法求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)___________ repeat if X(k)≤n //找到一个位置// then if k＝n //是一个完整的解吗// then print(X) //是，打印这个数组// else _______(2)_______； _______(3)_______； //转向下一行// endif else _______(4)_______ //回溯// endif repeat end NQUEENS 5. 二分查找算法 procedure binsrch1 (a，n，x，j) //除n>0外，其余说明与binsrch同// integer low，high，mid，j，n; low?1;high? (1) //high总比可能的取值大1// while low< (2) do mid??(low?high)/2? if x then (3) else (4) //x≥a(mid)// endif repeat if x=a(low) then j?low //x出现// else j?o //x不出现// endif； end binsrch1 6.求图中每对顶点之间的最短路径。 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 do for j<--1 to n do a(i，j)<--cost(i，j) repeat repeat ／／将cost(i，j)复制到a（i,j）／／ for k<--1to on do ／／对最高下标为k的结点的路径// for i?-1 to n do ／／对于所有可能的结点对／／ for i<--1 to n do a(i，j)<--min{ (1) ， (2) } repeat repeat repeat end all—Paths 7. 简单的合并与查找运算 procedureu(i，j) //根为i和j的两个不相交集合用它们的并来取代// integeri，j Parent(i)<--j; end u proceduref(i) //找包含元素i的树的根// integeri，j j<--i; while ⑴ do //若此结点是根，则Parent(j)<--0// ⑵ ; repeat return(j)
