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

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

Revised at 16:25 am on June 10, 2021

I hope tomorrow will definitely be better

算法分析与设计期末复习题

一、 选择题

1.应用Johnson 法则的流水作业调度采用的算法是D

A. 贪心算法

B. 分支限界法

C.分治法

D. 动态规划算法

塔问题如下图所示;现要求将塔座A 上的的所有圆盘移到塔座B 上,并仍按同样顺序叠置;移动圆盘时遵守Hanoi 塔问题的移动规则;由此设计出解Hanoi 塔问题的递归算法正确的为：B

3. 动态规划算法的基本要素为C A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用

4. 算法分析中,记号O 表示B , 记号Ω表示A , 记号Θ表示D ; A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界

5. 以下关于渐进记号的性质是正确的有：A A.f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ⇒=Θ B. f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==⇒= C. Ofn+Ogn = Omin{fn,gn} D. f (n)O(g(n))g(n)O(f (n))=⇔=

Hanoi 塔

A. void hanoiint n, int A, int C, int B { if n > 0 {

hanoin-1,A,C, B; moven,a,b;

hanoin-1, C, B, A; } B. void hanoiint n, int A, int B, int C { if n > 0 {

hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; }

C. void hanoiint n, int C, int B, int A { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; }

D. void hanoiint n, int C, int A, int B { if n > 0 {

hanoin-1, A, C, B; moven,a,b;

hanoin-1, C, B, A; }

6.能采用贪心算法求最优解的问题,一般具有的重要性质为：A

A. 最优子结构性质与贪心选择性质

B．重叠子问题性质与贪心选择性质

C．最优子结构性质与重叠子问题性质

D. 预排序与递归调用

7. 回溯法在问题的解空间树中,按D策略,从根结点出发搜索解空间树;广度优

先 B. 活结点优先 C.扩展结点优先 D. 深度优先

8. 分支限界法在问题的解空间树中,按A策略,从根结点出发搜索解空间树;

A．广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先

9. 程序块A是回溯法中遍历排列树的算法框架程序;

A.

B.

C.

D.

10.

xk的个数;

11. 常见的两种分支限界法为D

A. 广度优先分支限界法与深度优先分支限界法；

B. 队列式FIFO分支限界法与堆栈式分支限界法；

C. 排列树法与子集树法；

D. 队列式FIFO分支限界法与优先队列式分支限界法；

12. k带图灵机的空间复杂性Sn是指B

A.k带图灵机处理所有长度为n的输入时,在某条带上所使用过的最大方格数;

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

和;

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

D.k带图灵机处理所有长度为n的输入时,在某条带上所使用过的最小方格数;

13. N P类语言在图灵机下的定义为D

A.NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}；

B.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；

C.NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}；

D.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；14. 记号O

的定义正确的是A;

A.Ogn = { fn | 存在正常数c和n0使得对所有n≥n0有：0≤ fn ≤

cgn }；

B.Ogn = { fn | 存在正常数c和n0使得对所有n≥n0有：0≤ cgn ≤

fn }；

>0使得对所有n≥n0

C.Ogn = { fn | 对于任何正常数c>0,存在正数和n

有：0 ≤fn

>0使得对所有n≥n0

D.Ogn = { fn | 对于任何正常数c>0,存在正数和n

有：0 ≤cgn < fn }；

15. 记号Ω的定义正确的是B;

A.Ogn = { fn | 存在正常数c和n0使得对所有n≥n0有：0≤ fn ≤

cgn }；

B.Ogn = { fn | 存在正常数c和n0使得对所有n≥n0有：0≤ cgn ≤

fn }；

>0使得对所有n≥n0有：C.gn = { fn | 对于任何正常数c>0,存在正数和n

0 ≤fn

D.gn = { fn | 对于任何正常数c>0,存在正数和n0 >0使得对所有n≥n0有：

0 ≤cgn < fn }；

二、 填空题

1. 下面程序段的所需要的计算时间为 2O(n ) ;

2.

3.

4. 5.

6. 用回溯法解题的一个显着特征是在搜索过程中动态产生问题的解空间;

在任何时刻,算法只保存从根结点到当前扩展结点的路径;如果解空间树 中从根结点到叶结点的最长路径的长度为hn,则回溯法所需的计算空间通常为Ohn ;

7. 回溯法的算法框架按照问题的解空间一般分为

子集树算法框架与排列树算法框架;

8. 用回溯法解0/1背包问题时,该问题的解空间结构为子集树结构; 9.用回溯法解批处理作业调度问题时,该问题的解空间结构为排列树结构; 10.用回溯法解0/1背包问题时,计算结点的上界的函数如下所示,请在空格中填入合适的内容：

11. n m

12. 用回溯法解图的m着色问题时,使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性,则需耗时渐进时间上限Omn;

13.

;设分

分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用fn个单位时间;用Tn表示该分治法解规模为|P|=n的问题所需的计算时间,

则有：

(1)1 ()

(/)()1

O n

T n

kT n m f n n

=

⎧

=⎨

+>

⎩

通过迭代法求得Tn的显式表达式为：

log1

log

()(/)

n

m

k j j

m

j

T n n k f n m

-

=

=+∑

试证明Tn的显式表达式的正确性;

2. 举反例证明0/1背包问题若使用的算法是按照p i/w i的非递减次序考虑选择的物品,即只要正在被考虑的物品装得进就装入背包,则此方法不一定能得到最优解此题说明0/1背包问题与背包问题的不同;

证明：举例如：p={7,4,4},w={3,2,2},c=4时,由于7/3最大,若按题目要求的方法,只能取第一个,收益是7;而此实例的最大的收益应该是8,取第2,3 个;

3. 求证：Ofn+Ogn = Omax{fn,gn} ;

证明：对于任意f1n∈ Ofn ,存在正常数c1和自然数n1,使得对所有n≥n1,有

f1n≤ c1fn ;

类似地,对于任意g1n ∈ Ogn ,存在正常数c2和自然数n2,使得对所有n≥n2,有g1n ≤c2gn ;

令c3=max{c1, c2}, n3 =max{n1, n2},hn= max{fn,gn} ;

则对所有的 n ≥ n3,有

f1n +g1n ≤ c1fn + c2gn

≤c3fn + c3gn

= c3fn + gn

≤ c32 max{fn,gn} = 2c3hn = Omax{fn,gn} .

4. 求证最优装载问题具有贪心选择性质;

最优装载问题：有一批集装箱要装上一艘载重量为c 的轮船;其中集装箱i 的重量为Wi;最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船; 设集装箱已依其重量从小到大排序,x 1,x 2,…,x n 是最优装载问题的一个最优解;又设1min{|1}i i n

k i x ≤≤== ;如果给定的最优装载问题有解,则有

1k n ≤≤;

证明： 四、 解答题

1. 机器调度问题;

问题描述：现在有n 件任务和无限多台的机器,任务可以在机器上得到处理;每件任务的开始时间为s i ,完成时间为f i ,s i

问题实例：若任务占用的时间范围是{1,4,2,5,4,5,2,6,4,7},则按时完成所有任务最少需要几台机器提示：使用贪心算法

画出工作在对应的机器上的分配情况;

2. 已知非齐次递归方程：f (n)bf (n 1)g(n)

f (0)c =-+⎧⎨=⎩ ,其中,b 、c 是常数,gn 是

n 的某一个函数;则fn 的非递归表达式为：n

n

n i i 1f (n)cb b g(i)-==+∑;

现有Hanoi 塔问题的递归方程为：h(n)2h(n 1)1

h(1)1=-+⎧⎨=⎩ ,求hn 的非递归表达

式;

解：利用给出的关系式,此时有：b=2, c=1, gn=1, 从n 递推到1,有： 3. 单源最短路径的求解;

问题的描述：给定带权有向图如下图所示G =V,E,其中每条边的权是非负实数;另外,还给定V 中的一个顶点,称为源;现在要计算从源到所有其它各顶点的最短路长度;这里路的长度是指路上各边权之和;这个问题通常称为单源最短路径问题;

解法：现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径;请将

此过程填入下表中;

4. 请写出用回溯法解装载问题的函数; 装载问题：有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船,

其中集装箱i 的重量为wi,且121n

i i w c c =≤+∑;装载问题要求确定是否有一个合理的装载方案可将这n 个集装箱装上这2艘轮船;如果有,找出一种装载方案;

解：void backtrack int i

{用分支限界法解装载问题时,对算法进行了一些改进,下面的程序段给出了改进部分；试说明斜线部分完成什么功能,以及这样做的原因,即采用这样的方式,算法在执行上有什么不同;

初始时将;也就是说,

重量仅在搜索进入左子树是增加,因此,可以在算法每一次进入左子树时更新bestw 的值;

4

3 2 1

100

30

maxint

10 - {1} 初始 dist5 dist4 dist3 dist2 u S 迭代

7. 最长公共子序列问题：给定2个序列X={x 1,x2,…,xm }和Y={y 1,y2,…,yn },找出X 和Y 的最长公共子序列;

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系;用cij 记录序列Xi 和Yj 的最长公共子序列的长度;其中, Xi={x1,x2,…,xi}；Y j={y1,y2,…,yj};当i=0或j=0时,空序列是Xi 和Yj 的最长公共子序列;故此时Cij=0;其它情况下,由最优子结构性质可建立递归关系如下：

00,0[][][1][1]1

,0;max{[][1],[1][]},0;i j i j

i j c i j c i j i j x y c i j c i j i j x y ⎧==⎪

=--+>=⎨⎪-->≠⎩

在程序中,bij 记录Cij 的值是由哪一个子问题的解得到的;

8.1.2.3.4.5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________;

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

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

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

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

10.二分搜索算法是利用_______________实现的算法;

二、综合题50分

1.写出设计动态规划算法的主要步骤;

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

3.若n=4,在机器M1和M2上加工作业i所需的时间分别为a

i 和b

i

,且

a 1,a

2

,a

3

,a

4

=4,5,12,10,b

1

,b

2

,b

3

,b

4

=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,并画出其解空间树,计算其最优值及最优解;

5.设S=｛X

1,X

2

,···,X

n

｝是严格递增的有序集,利用二叉树的结点来存储S中

的元素,在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形,1在

二叉搜索树的内结点中找到X=X

i ,其概率为b

i

;2在二叉搜索树的叶结点中确定X

∈X

i ,X

i+1

,其概率为a

i

;在表示S的二叉搜索树T中,设存储元素X

i

的结点深度为

C i ；叶结点X

i

,X

i+1

的结点深度为d

i

,则二叉搜索树T的平均路长p为多少假设二

叉搜索树Tij=｛X

i ,X

i+1

,···,X

j

｝最优值为mij,Wij= a

i-1

+b

i

+···+b

j

+a

j

,则

mij1<=i<=j<=n递归关系表达式为什么

6.描述0-1背包问题;

三、简答题30分

1.流水作业调度中,已知有n个作业,机器M1和M2上加工作业i所需的时间分

别为a

i 和b

i

,请写出流水作业调度问题的johnson法则中对a

i

和b

i

的排序算法;

函数名可写为sorts,n

2.最优二叉搜索树问题的动态规划算法设函数名binarysearchtree

答案：

一、填空

1．确定性有穷性可行性 0个或多个输入一个或多个输出

2.时间复杂性空间复杂性时间复杂度高低

3. 该问题具有最优子结构性质

4.{BABCD}或{CABCD}或{CADCD｝

5.一个最优解

6.子问题子问题子问题

7.回溯法

8. on2n omin{nc,2n}

9.最优子结构重叠子问题

10.动态规划法

二、综合题

1.①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造最优解；

2. ①令N

1={i|a

i

i

},N

2

={i|a

i

>=b

i

}；②将N

1

中作业按a

i

的非减序排序得到N

1

’,

将N

2中作业按b

i

的非增序排序得到N

2

’；③N

1

’中作业接N

2

’中作业就构成

了满足Johnson法则的最优调度;

3.步骤为：N1={1,3},N2={2,4}；

N 1’={1,3}, N

2

’={4,2}；

最优值为：38

4.解空间为{0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1, 1,1,0,1,1,1}; 解空间树为：

该问题的最优值为：16 最优解为：1,1,0 5.二叉树T 的平均路长P=∑=+n

i 1Ci)(1*bi +∑=n

j 0

dj *aj

{

mij=0 i>j

6.已知一个背包的容量为C,有n 件物品,物品i 的重量为W i ,价值为V i ,求应如何选择装入背包中的物品,使得装入背包中物品的总价值最大; 三、简答题 1.

void sortflowjope s,int n {

int i,k,j,l;

fori=1;i<=n-1;i++ag=0 k++; ifk>n break;ag==0

ifsk.a>sj.a k=j; swapsi.index,sk.index; swapsi.tag,sk.tag;

} }

l=i;

swapsi.index,sk.index; ag,sk.tag; }

mij=Wij+min{mik+mk+1j} 1<=i<=j<=n,mii-1=0

}

2.

void binarysearchtreeint a,int b,int n,int m,int s,int w

{

int i,j,k,t,l;

fori=1;i<=n+1;i++

{

wii-1=ai-1;

mii-1=0;

}

forl=0;l<=n-1;l++Init-single-sourceG,s

2. S=Φ

3. Q=VG

Q<> Φ

do u=minQ

S=S∪{u}

for each vertex 3

do 4

四、算法理解题本题10分

根据优先队列式分支限界法,求

下图中从v1点到v9点的单源

最短路径,请画出求得最优解的

解空间树;要求中间被舍弃的结

点用×标记,获得中间解的结点

用单圆圈○框起,最优解用双圆

圈◎框起;

五、算法理解题本题5分

设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表：

①每个选手必须与其他n-1名选手比赛各一次；

②每个选手一天至多只能赛一次；

③循环赛要在最短时间内完成;

1如果n=2k,循环赛最少需要进行几天；

2当n=23=8时,请画出循环赛日程表;

六、算法设计题本题15分

分别用贪心算法、动态规划法、回溯法设计0-1背包问题;要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间;

七、算法设计题本题10分

通过键盘输入一个高精度的正整数nn的有效位数≤240,去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数;编程对给定的n 和s,寻找一种方案,使得剩下的数字组成的新数最小;

样例输入

178543

S=4

样例输出

13

一、填空题本题15分,每小题1分

1．规则一系列运算

2. 随机存取机RAMRandom Access Machine；随机存取存储程序机RASPRandom Access Stored Program Machine；图灵机Turing Machine

3. 算法效率

4. 时间、空间、时间复杂度、空间复杂度

5．2n

6．最好局部最优选择

7. 贪心选择最优子结构

二、简答题本题25分,每小题5分

1、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,

这些子问题互相独立且与原问题相同；对这k个子问题分别求解;如果子

问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直

到问题规模足够小,很容易求出其解为止；将求出的小规模的问题的解合

并为一个更大规模的问题的解,自底向上逐步求出原来问题的解;

2、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题,需

要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是

最优的;

3、某个问题的最优解包含着其子问题的最优解;这种性质称为最优子结构性

质;

4、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度

优先搜索,解为叶子结点;搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,退回到上层父结点,继续下一步深度优先搜索过程;在

回溯法中,并不是先构造出整棵状态空间树,再进行搜索,而是在搜索过程,逐步构造出状态空间树,即边搜索,边构造;

5、PPolynomial问题：也即是多项式复杂程度的问题;

NP就是Non-deterministicPolynomial的问题,也即是多项式复杂程度的非确定性问题;

NPCNP Complete问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP里面最难的问题,这种问题就是NPC问题;

三、算法填空本题20分,每小题5分

1、n后问题回溯算法

1 Mj&&Li+j&&Ri-j+N

2 Mj=Li+j=Ri-j+N=1;

3 tryi+1,M,L,R,A

4 Aij=0

5 Mj=Li+j=Ri-j+N=0 2、数塔问题; 1c<=r

2trc+=tr+1c 3trc+=tr+1c+1 3、Hanoi 算法 1movea,c

2Hanoin-1, a, c , b 3Movea,c 4、1pv=NIL 2pv=u

3 v ∈adju 4Relaxu,v,w

四、算法理解题本题10分

五、18天2分；

2当n=23=8时,循环赛日程表3分;

六、算法设计题本题15分 1贪心算法 Onlogn ➢ 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包;若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包;依此策略一直地进行下去,直到背包装满为止; ➢ 具体算法可描述如下：

void Knapsackint n,float M,float v,float w,float x {Sortn,v,w; int i;

for i=1;i<=n;i++ xi=0; float c=M;

for i=1;i<=n;i++ {if wi>c break; xi=1; c-=wi; }

if i<=n xi=c/wi; }

2动态规划法 Onc

mi,j 是背包容量为j,可选择物品为i,i+1,…,n 时0-1背包问题的最优值;由0-1背包问题的最优子结构性质,可以建立计算mi,j 的递归式如下;

void KnapSackint v,int w,int c,int n,int m11 {int jMax=minwn-1,c;

for j=0;j<=jMax;j++ /mn,j=0 0=

1 2 3 4 5 6 7 8

2 1 4

3 6 5 8 7

3 4 1 2 7 8 5 6

4 3 2 1 8 7 6 5

5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3

7 8 5 6 3 4 1 2

8 7 6 5 4 3 2 1

for j=wn;j<=c;j++ /mn,j=vn j>=wn/

mnj=vn;

for i=n-1;i>1;i--

{ int jMax=minwi-1,c;

for j=0;j<=jMax;j++ /mi,j=mi+1,j 0=

mij=mi+1j;

for j=wi;j<=c;j++/mn,j=vn j>=wn/

mij=maxmi+1j,mi+1j-wi+vi;

}

m1c=m2c;

ifc>=w1

m1c=maxm1c,m2c-w1+v1;

}

3回溯法 O2n

cw:当前重量 cp:当前价值 bestp：当前最优值

voidbacktrack int i

//回溯法 i初值1

{ifi>n //到达叶结点

{ bestp=cp; return; }

ifcw+wi<=c //搜索左子树

{cw+=wi;

cp+=pi;

backtracki+1;

cw-=wi;

cp-=pi;

}

ifBoundi+1>bestp

//搜索右子树

backtracki+1;

}

七、算法设计题本题10分

为了尽可能地逼近目标,我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字符;然后回到串首,按上述规则再删除下一个数字;重复以上过程s次,剩下的数字串便是问题的解了;

具体算法如下：

输入s, n;

while s > 0

{ i=1; //从串首开始找

while i < lengthn && ni

{i++;}

deleten,i,1; //删除字符串n的第i个字符

s--;

}

while lengthn>1&& n1=‘0’

deleten,1,1; //删去串首可能产生的无用零输出n;

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

算法设计与分析 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分） 7、试用回溯法解决下列整数变换问题：关于整数i 的变换f 和g 定义如下：??2/)(;3)(i i g i i f ==。对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。（16分）

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

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai=bi}； ②将N1中作业按ai的非减序排序得到N1’，将N2中作业按bi的非增序排序得到N2’； ③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且 (a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={4，2}； 最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的 0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为：

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

《算法分析与设计》期末复习题 一、选择题 1.应用Johnson法则的流水作业调度采用的算法是（D） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解 Hanoi塔问题的递归算法正确的为：（B） Hanoi塔

3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O表示（B），记号Ω表示（A），记号Θ表示（D）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A） A.f(n)(g(n)),g(n)(h(n))f(n)(h(n)) =Θ=Θ?=Θ B. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n)) ==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f(n)O(g(n))g(n)O(f(n)) =?= 6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质

C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。 A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先 8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。 A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先 9. 程序块（A）是回溯法中遍历排列树的算法框架程序。 A. B. C.

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

《算法设计与分析》试卷及答案 算法设计与分析考试复习试卷 《算法设计与分析》试卷1 一、多项选择题（每空2分，共20分）： 1、以下关于算法设计问题的叙述中正确的是__________。 A、计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关 B、利用计算机无法解决非数值问题 C、计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中，主要进行的是判断、比较，而不是算术运算 D、算法设计与分析主要研究对象是非数值问题，当然也包含某些数值问题 2、算法的特征包括_________。 A、有穷性 B、确定性 C、输入和输出 D、能行性或可行性 3、以下描述是有关算法设计的基本步骤： ①问题的陈述②算法分析③模型的拟制④算法的实现 ⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起 其中正确的顺序是__________。

A、①②③④⑤⑥ B、①③⑤②④⑥ C、②④①③⑤⑥ D、⑥①③⑤②④ 4、以下说法正确的是__________。 A、数学归纳法可以证明算法终止性 B、良序原则是证明算法的正确性的有力工具 C、x = 小于或等于x的最大整数（x的低限） D、x = 小于或等于x的最大整数（x的高限） 5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C 上所用的次数，则递归方程 为__________，其初始条件为__________，将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数，则有递归方程为__________，其中F1=F2=__________。 A、Fn=Fn-1+Fn-2 B、h（n）= 2h（n-1）+1 C、1 D、h（1）= 1 E、h（n）=2n-1 F、0 6、在一个有向连通图中（如下图所示），找出点A到点B的一条最短路为____ ______。 A、最短路：1→3→5→8→10，耗费：20 B、最短路：1→4→6→9→10，耗费： 16

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

1． 按分治策略求解棋盘覆盖问题时，对于如图所示的24×24的特殊棋盘，共需要多少个L 型骨 牌；并在棋盘上填写L 型骨牌的覆盖情况。 2． 假设有7个物品，给出重量和价值。若这些物品均不能被分割，且背包容量M ＝140，使用回 溯方法求解此0-1背包问题。请画出状态空间搜索树。 3． 假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M ＝140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。 W （35,30,50,60,40,10,25）p （10,40,30,50,35,40,30） 4． 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定 a 到 b 的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。 5． 画出字符表的哈夫曼编码对应的二叉树。 6． 已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=8，r 5=5，r 6=20，r 7=6，求 矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序。 7． 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树， 描述出用优先队列式分支限界法求解时的搜索情况。表示出优先队列、当前扩展结点等的变化情况。 8． 依据优先队列式分支限界法，求从s 点到t 点的单源最短路径，画出求得最优解的解空间树。 一、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M ＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。 答：按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】

计算机算法设计和分析习题及答案解析

计算机算法设计与分析习题及答案 一．选择题 1、二分搜索算法是利用 A 实现的算法; A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是 A ; A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是A 的一搜索方式; A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是 A ; A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是B ; A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是 C ; A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是 D ; A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是A ; A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是D ; A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是D ; A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形; B A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为B ; A、On2n B、Onlogn C、O2n D、On 13．分支限界法解最大团问题时,活结点表的组织形式是B ; A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是B; A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是A ; A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是C ; A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素 D A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略B A．递归函数 B.剪枝函数 C;随机数函数 D.搜索函数 19. D是贪心算法与动态规划算法的共同点; A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由 B 设计实现; A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法

算法设计与分析(第二版)王红梅试题及解析

算法设计与分析（第二版）王红梅试题及解析 本文主要介绍了《算法设计与分析（第二版）》一书中的王红梅试题及解析，旨在帮助读者更好地掌握算法的基础知识，提高算法设计与分析的能力。 一、算法设计与分析 算法是计算机科学的重要组成部分，是解决计算问题的一种方法。算法设计与分析是计算机科学的一项核心技术，也是计算机科学专业必修的一门课程。算法的好坏将直接影响计算机程序的运行效率。

王红梅编写的《算法设计与分析（第二版）》是一本通俗易懂的教材，作者通过详细解析 算法设计和分析的基本概念和方法，给出了 很多数学原理和实例，帮助读者深刻理解算 法设计和分析的基本原则和方法。 二、王红梅试题及解析 1. 下面哪个算法的时间复杂度最小？ A. 插入排序 B. 选择排序 C. 冒泡排序 D. 快速排序

答案：D 解析：快速排序是一种分治算法，基于递归 的思想进行排序，每次划分找到一个基准点，将比基准点小的数放到左边，比基准点大的 数放到右边，递归进行排序，因此它的时间 复杂度为O(nlogn)，是四种算法中最小的。 2. 下列哪些数据结构可以用来实现递归算法？ A. 数组 B. 栈 C. 队列 D. 链表

答案：B、D 解析：递归算法通常使用栈和链表来实现， 因为它们具有后进先出或者先进先出的特点，符合递归算法的调用过程。 3. 下列哪个算法不是稳定排序？ A. 插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 答案：D

解析：稳定排序表示排序后，具有相同值得 元素，排序前后其相对位置不变。插入排序、冒泡排序和归并排序都是稳定排序算法，只 有堆排序不是稳定排序算法。 4. 设有n个元素的数组，采用冒泡排序，平均比较次数和平均移动次数分别是多少？ 答案：平均比较次数为n(n-1)/2，平均移动次数为3 n(n-1)/4。 解析：冒泡排序的平均时间复杂度为O(n²)。在n个元素的数组中，每个元素最多需要比 较n-1次，所以平均比较次数为(n-1 + n-2

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

计算机算法设计与分析考试复习题 一.选择题 1、二分搜索算法是利用（）实现的算法。［单选题］* A、分治策略。 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（1 ［单选题］* A、找出最优解的性质。 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（）的一搜索方式。［单选题］* A、分支界限法V B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（\ ［单选题］* A、分支界限法

B、动态规划法V空1答案：规模 11、计算一个算法时间复杂度通常可以计算循环次数、或计算步。［填空题］*空1答案：基本操作的频 率 12、回溯法搜索解空间树时，常用的两种剪枝函数为和限界函数［填空题］*空1答案：约束函数 14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是,需要排序的是［填空题］*空1答案：动态规划法空2答案：回溯法空3答案：分支限界法 15、使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界，N［单选题］* 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进， 行裁剪的是｛0/1背包问题｝,只使用约束条件进行裁剪的是｛N皇后问题｝。 17、回溯法是一种既带有又带有的搜索算法。［填空题］*空1答案：系统性空2答案：跳跃性 18.动态规划算法的两个基本要素是.最优子结构性质和性质［填空题］*空1答案：重叠子问题 19.贪心算法的基本要素是性质和性质。［填空题］*空1答案：贪心选择空2答案：最优子结构 21.动态规划算法的基本思想是将待求解问题分解成若干 ,先求解 ,然后从这些的解得到原问题的解。［填空题］*空1答案：子问题空2答案：子问题空3答案：子问题 22.算法是由若干条指令组成的有穷序列，且要满足和四条性质。［填空题］*

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

计算机算法设计与分析考试复习题 一、选择题 1、二分搜索算法是利用（）实现的算法。[单选题] * A、分治策略√ B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（）。[单选题] * A、找出最优解的性质√ B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（）的一搜索方式。[单选题] * A、分支界限法√ B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（）。[单选题] * A、分支界限法 B、动态规划法√

C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（）。[单选题] * A、子集树√ B、排列树 C、深度优先生成树 D、广度优先生成树 6．下列算法中通常以自底向上的方式求解最优解的是（）。[单选题] * A、备忘录法 B、动态规划法√ C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（）。[单选题] * A 运行速度快 B 占用空间少 C 时间复杂度低√ D 代码短 8、以下不可以使用分治法求解的是（）。[单选题] * A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题√

9. 实现循环赛日程表利用的算法是（）。[单选题] * A、分治策略√ B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（）。[单选题] * A、分治策略 B、动态规划法√ C、贪心法 D、回溯法 11．下面不是分支界限法搜索方式的是（）。[单选题] * A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先√ 12．下列算法中通常以深度优先方式系统搜索问题解的是（）。[单选题] * A、备忘录法 B、动态规划法 C、贪心法 D、回溯法√ 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的[单选题] * （B ）。√

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

一、填空题〔20分〕 1.一个算法就是一个有穷规那么的集合，其中之规那么规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度上下。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子构造性质。 4.假设序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个〔最优〕解。 6.动态规划算法的根本思想是将待求解问题分解成假设干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n),用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个根本要素是最优子构造和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题〔50分〕 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子构造性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai=bi}； ②将N1中作业按ai的非减序排序得到N1’，将N2中作业按bi的非增序排序得到N2’； ③N1’中作业接N2’中作业就构成了满足Johnson法那么的最优调度。 3.假设n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且 (a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N1’={1，3}，N2’={4，2}； 最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3 的0-1向量组成，要求用一棵完全二叉树表示其解空间〔从根出发，左1右0〕，并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：〔1，1，0〕 5.设S=｛X1，X2，···，Xn｝是严格递增的有序集，利用二叉树的结点来存储S中的元素， 在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，〔1〕在二叉搜索树的结点中找到X=Xi，其概率为bi。〔2〕在二叉搜索树的叶结点中确定X∈〔Xi，Xi+1〕，其概率为ai。在表示S的二叉搜索树T中，设存储元素Xi的结点深度为Ci；叶结点〔Xi，Xi+1〕的结点深度为di，那么二叉搜索树T的平均路长p为多少.假设二叉搜索树T[i][j]=

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

一、填空题（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），并画出其解空间树，计算其最优值及最优解。 5。设S=｛X1,X2，···，X n｝是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i，其概率为b i。(2）在二叉搜索树的叶结点中确定X∈（X i，X i+1）,其概率为a i。在表示S的二叉搜索树T中，设存储元素X i的结点深度为C i；叶结点（X i，X i+1）的结点深度为d i，则二叉搜索树T的平均路长p为多少?假设二叉搜索树T[i][j］={X i，X i+1,···,X j｝最优值为m［i][j］,W ［i］［j]= a i—1+b i+···+b j+a j，则m[i]［j］（1〈=i<=j〈=n)递归关系表达式为什么？ 6.描述0—1背包问题. 三、简答题（30分） 1。流水作业调度中，已知有n个作业，机器M1和M2上加工作业i 所需的时间分别为a i和b i，请写出流水作业调度问题的johnson法则

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

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个作业的最优调度方案，

(完整word版)《算法设计与分析》考试题目及答案

《算法分析与设计》期末复习题 一、 选择题 1。应用Johnson 法则的流水作业调度采用的算法是(D ） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi 塔问题的移动规则.由此设计出解Hanoi 塔问题的递归算法正确的为：(B ） Hanoi 塔 A 。 void hanoi(int n ， int A ， int C, int B) ｛ if (n > 0) B 。 void hanoi(int n, int A, int B ， int C ） { if (n 〉 0) C. void hanoi （int n ， int C, int B, int A) ｛ if （n > 0）

3。 动态规划算法的基本要素为(C ） A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D 。 预排序与递归调用 4。 算法分析中，记号O 表示（B)， 记号Ω表示(A)， 记号Θ表示(D)。 A 。渐进下界 B 。渐进上界 C.非紧上界 D.紧渐进界 E 。非紧下界 5. 以下关于渐进记号的性质是正确的有：（A ） A 。f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ⇒=Θ B 。 f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==⇒= C 。 O(f （n)）+O(g(n ）) = O （min ｛f(n ）,g(n ）｝） D 。 f (n)O(g(n))g(n)O(f (n))=⇔= 6。 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A ） D. void hanoi （int n, int C ， int A ， int B) ｛ if (n > 0）