当前位置：文档之家 › 《算法设计与分析》复习题参考答案

《算法设计与分析》复习题参考答案

  • 格式：doc
  • 大小：138.00 KB
  • 文档页数：15

《算法设计与分析》复习题一、概念题：请解释下列术语。

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)___________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 nk 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/)(highlow+//求这个集合的分割点//call ⑴／/将一个子集合分类／／call ⑵／／将另一个子集合分类／／call ⑶／／归并两个已分类的子集合//endifend mergesort10. 使用链接表归并已分类的集合procedure merge1 (q，r，p)／／q和r是全程数组link(1:n)中两个表的指针。

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

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

假定link(0)被定义,且假定表由0所结束／／global n, a(1:n),link(0:n)local integer i，j，ki←q；j←r；k←0 ／／新表在link(0)处开始//while ⑴ and ⑵ do //当两表皆非空时作//if a(i)≤a(j) ／／找较小的关键字／／then link(k)←i;k←i；i←link(i) ／／加一个新关键字到此表// else ⑶endifrepeatif i=0 then ⑷else link(k)←iendifp←link(0)end mergel11.作业排序算法的概略描述procedure greedy-job(d，j，n)／／作业按p1≥p：≥…≥Pn的次序输入，它们的期限值d(i)≥1,1≤i≤n,n≥1.j 是在它们的截止期限前完成的作业的集合／／j←{1}for ⑴ to n doif j∪{i}所有作业都能在它们的截止期限前完成then ⑵endifrepeatend greedy—job12. 生成二元归并树算法line proceduretree (l，n)／／l是n个单结点二元树的表//for i←1 to n-1 docall getnode(t) ／／用于归并两棵树／／lchild (t)<--least(l) ／／最小的长度／rchild (t)<--least(l)weight(t)<-- ⑴call insert(l，t)repeat ⑵／／留在l中的树是归并树"end tree13.kruskal算法line procedure kruskal(e, cost ，n，t ,mincost)／／g有n个结点，e是g的边集。

合集下载

《算法设计与分析》考试题目及答案(DOC)

《算法设计与分析》考试题目及答案(DOC)

《算法设计与分析》考试题目及答案(DOC)D. 预排序与递归调用7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。

A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。

A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。

A.B.C.D. void backtrack (int t){if (t>n) output(x);elsefor (int i=t;i<=n;i++) {swap(x[t], x[i]);if (legal(t)) backtrack(t+1); swap(x[t], x[i]);}}void backtrack (int t){if (t>n) output(x);elsefor (int i=0;i<=1;i++) {x[t]=i;if (legal(t)) backtrack(t+1); }}10. 回溯法的效率不依赖于以下哪一个因素？（C ）A.产生x[k]的时间；B.满足显约束的x[k]值的个数；C.问题的解空间的形式；D.计算上界函数bound的时间；E.满足约束函数和上界函数约束的所有x[k]的个数。

F.计算约束函数constraint的时间；11. 常见的两种分支限界法为（D）A. 广度优先分支限界法与深度优先分支限界法；B. 队列式（FIFO）分支限界法与堆栈式分支限界法；C. 排列树法与子集树法；D. 队列式（FIFO）分支限界法与优先队列式分支限界法；12. k带图灵机的空间复杂性S(n)是指（B）A.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。

B.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。

C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。

算法设计与分析试卷及答案

算法设计与分析试卷及答案

算法设计与分析1、(1) 证明：O(f)+O(g)=O(f+g)（7分）(2) 求下列函数的渐近表达式：（6分）① 3n 2+10n;② 21+1/n;2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。

（15分）(1);5log )(;log )(2+==n n g n n f (2);)(;log )(2n n g n n f == (3);log )(;)(2n n g n n f == 3、试用分治法对数组A[n]实现快速排序。

（13分）4、试用动态规划算法实现最长公共子序列问题。

（15分）5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。

试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。

（12分）6、试用动态规划算法实现下列问题：设A 和B 是两个字符串。

我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括：(1)删除一个字符。

(2)插入一个字符。

(3)将一个字符改为另一个字符。

将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到B 的编辑距离，记为d(A,B)。

试设计一个有效算法，对任给的两个字符串A 和B ，计算出它们的编辑距离d(A,B)。

（16分）⎣⎦2/)(;3)(i i g i i f ==。

对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。

（16分）1、⑴证明：令F(n)=O(f),则存在自然数n 1、c 1，使得对任意的自然数n ≥n 1，有：F(n)≤c 1f(n)……………………………..（2分）同理可令G(n)=O(g),则存在自然数n 2、c 2，使得对任意的自然数n ≥n 2，有：G(n)≤c 2g(n)……………………………..（3分）令c 3=max{c 1,c 2},n 3=max{n 1,n 2},则对所有的n ≥n 3，有： F(n)≤c 1f(n)≤c 3f(n)G(n)≤c 2g(n)≤c 3g(n)……………………………..（5分） 故有：O(f)+O(g)=F(n)+G(n)≤c 3f(n)+c 3g(n)=c 3(f(n)+g(n)) 因此有：O(f)+O(g)=O(f+g)……………………………..（7分） ⑵ 解：① 因为;01033)103(lim 222=+-+∞→n n n n n n 由渐近表达式的定义易知： 3n 2是3n 2+10n 的渐近表达式。

算法设计与分析考试题及答案

算法设计与分析考试题及答案

一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。

2.算法的困难性有_____________和___________之分，衡量一个算法好坏的标准是______________________。

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

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

5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。

6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。

7.以深度优先方式系统搜寻问题解的算法称为_____________。

8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。

9.动态规划算法的两个基本要素是___________和___________。

10.二分搜寻算法是利用_______________实现的算法。

二、综合题（50分）1.写出设计动态规划算法的主要步骤。

2.流水作业调度问题的johnson算法的思想。

3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。

4.运用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根动身，左1右0），并画出其解空间树，计算其最优值及最优解。

算法分析与设计考试复习题及参考答案

算法分析与设计考试复习题及参考答案

一、简要回答下列问题 ： 1. 算法重要特性是什么？ 2. 算法分析的目的是什么？ 3. 算法的时间复杂性与问题的什么因素相关？ 4. 算法的渐进时间复杂性的含义？ 5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 6. 简述二分检索（折半查找）算法的基本过程。 7. 背包问题的目标函数和贪心算法最优化量度相同吗？ 8. 采用回溯法求解的问题，其解如何表示？有什么规定？ 9. 回溯法的搜索特点是什么？ 10. n皇后问题回溯算法的判别函数place的基本流程是什么？ 11. 为什么用分治法设计的算法一般有递归调用？ 12. 为什么要分析最坏情况下的算法时间复杂性？ 13. 简述渐进时间复杂性上界的定义。 14. 二分检索算法最多的比较次数？ 15. 快速排序算法最坏情况下需要多少次比较运算？ 16. 贪心算法的基本思想？ 17. 回溯法的解（x1,x2,……xn）的隐约束一般指什么？ 18. 阐述归并排序的分治思路。 19. 快速排序的基本思想是什么。 20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结 构？ 21. 什么是哈密顿环问题？ 22. 用回溯法求解哈密顿环，如何定义判定函数？ 23. 请写出prim算法的基本思想。 二、复杂性分析 1、 MERGESORT(low，high) if low<high； then mid←(low，high)/2； MERGESORT(low，mid)； MERGESORT(mid+1，high)； MERGE(low，mid，high)； endif end MERGESORT 2、 procedure S1(P，W，M，X，n) i←1; a←0
15．.最坏情况下快速排序退化成冒泡排序，需要比较n2次。 16. 是一种依据最优化量度依次选择输入的分级处理方法。基本思 路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n 个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加 入，不满足约束条件，则不把此输入加到这部分解中。 17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满 足的某种关系。 18. 将数组一分为二，分别对每个集合单独排序，然后将已排序的 两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还 很大，则继续分治，直到一个元素。 19.快速排序的基本思想是在待排序的N个记录中任意取一个记录， 把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字 比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并 把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复 上述过程，直到每一部分内只有一个记录为止。 20.在定义一个过程或者函数的时候又出现了调用本过程或者函数 的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调 用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用 到栈这种数据结构。 21.哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个 节点一次并且返回它的开始位置。 22.当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2, …,k-1)，且C(X[k-1], X[k])≠∞，如果k=-1，则C(X[k], X[1]) ≠∞。 23. 思路是：最初生成树T为空，依次向内加入与树有最小邻接边 的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到 T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变 的邻接边排序，再选择下一条边加入，直至加入n-1条边。 二、复杂性分析 1、 递归方程