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

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

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

中南大学网络教育课程考试复习题及参考答案

算法分析与设计

一、名词解释:

1.算法

2.程序

3.递归函数

4.子问题的重叠性质

5.队列式分支限界法

6.多机调度问题

7.最小生成树 二、简答题:

1.备忘录方法和动态规划算法相比有何异同?简述之。

2.简述回溯法解题的主要步骤。

3.简述动态规划算法求解的基本要素。

4.简述回溯法的基本思想。

5.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。

6.简要分析分支限界法与回溯法的异同。

7.简述算法复杂性的概念,算法复杂性度量主要指哪两个方面? 8.贪心算法求解的问题主要具有哪些性质?简述之。

9.分治法的基本思想是什么?合并排序的基本思想是什么?请分别简述之。 10.简述分析贪心算法与动态规划算法的异同。 三、算法编写及算法应用分析题:

1.已知有3个物品:(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20,根据0-1背包动态规划的递推式求出最优解。

2.按要求完成以下关于排序和查找的问题。

①对数组A={15,29,135,18,32,1,27,25,5},用快速排序方法将其排成递减序。 ②请描述递减数组进行二分搜索的基本思想,并给出非递归算法。 ③给出上述算法的递归算法。

④使用上述算法对①所得到的结果搜索如下元素,并给出搜索过程:18,31,135。

3.已知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=12,r 5=5,r 6=50,r 7=6,求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序(要求给出计算步骤)。

4.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20,(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。

5.试用贪心算法求解汽车加油问题:已知一辆汽车加满油后可行驶n 公里,而旅途中有若干个加油站。试设计一个有效算法,指出应在哪些加油站停靠加油,使加油次数最少,请写出该算法。

6.试用动态规划算法实现下列问题:设A 和B 是两个字符串。我们要用最少的字符操作,将字符串A 转换为字符串B ,这里所说的字符操作包括: ①删除一个字符。 ②插入一个字符。

③将一个字符改为另一个字符。 请写出该算法。

7.对于下图使用Dijkstra 算法求由顶点a 到顶点h 的最短路径。

8.试写出用分治法对数组A[n]实现快速排序的算法。

9.有n 个活动争用一个活动室。已知活动i 占用的时间区域为[s i ,f i ],

活动i,j 相容的条件是:sj ≥f i

,问题的解表示为(x i | x i =1,2…,n,),x i 表示顺序为i 的活动编号活动,求一个相容的活动子

集,且安排的活动数目最多。

10.设x 1、x 2、x 3是一个三角形的三条边,而且x 1+x 2+x 3=14。请问有多少种不同的三角形?给出解答过

程。

11.设数组A 有n 个元素,需要找出其中的最大最小值。

①请给出一个解决方法,并分析其复杂性。

②把n 个元素等分为两组A1和A2,分别求这两组的最大值和最小值,然后分别将这两组的最大值和最小值相比较,求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个,则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想?请给出该方法的算法描述,并分析其复杂性。

12.有n 个程序和长度为L 的磁带,程序i 的长度为a i ,已知

L a

n

i i

∑=1

求最优解(x i ,x 2 ,...,x i ,…, x n ),x i =0,1, x i =1,表示程序i 存入磁带,x i =0,表示程序i 不存入磁带,满足L a

x n

i i

i ≤∑=1

且存放的程序数目最多。

13.试用分治法实现有重复元素的排列问题:设),...,,{21n r r r R =是要进行排列的n 个元素,其中元素

n r r r ,...,,21可能相同,试设计计算R 的所有不同排列的算法。

14.试用动态规划算法实现0-1闭包问题,请写出该算法。

15.试用贪心算法求解下列问题:将正整数n 分解为若干个互不相同的自然数之和,使这些自然数的乘

积最大,请写出该算法。

16.试写出用分治法对一个有序表实现二分搜索的算法。

17.试用动态规划算法实现最长公共子序列问题,请写出该算法。

18.假设有7个物品,它们的重量和价值如下表所示。若这些物品均不能被分割,且背包容量M =150,

使用回溯方法求解此背包问题,请写出状态空间搜索树。

19.求解子集和问题:对于集合S={1,2 ,6,8},求子集,要求该子集的元素之和d=9。

①画出子集和问题的解空间树;

②该树运用回溯算法,写出依回溯算法遍历节点的顺序;

③如果S 中有n 个元素,指定d ,用伪代码描述求解子集和问题的回溯算法。

20.求解填字游戏问题:在3×3个方格的方阵中要填入数字1到N (N ≥10)内的某9个数字,每个方

格填一个整数,似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一种数字填法的算法和满足这个要求的全部数字填法的算法。

21.试用动态规划算法实现最大子矩阵和问题:求n m ?矩阵A 的一个子矩阵,使其各元素之和为最大。

22.试用回溯法解决下列整数变换问题:关于整数i 的变换f 和g 定义如下:??2/)(;3)(i i g i i f ==。

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

23.关于15谜问题。在一个4×4的方格的棋盘上,将数字1到15代表的15个棋子以任意的顺序置入

各方格中,空出一格。要求通过有限次的移动,把一个给定的初始状态变成目标状态。移动的规则是:每次只能把空格周围的四格数字(棋子)中的任意一个移入空格,从而形成一个新的状态。为了有效的移动,设计了估值函数C 1(x),表示在结点x 的状态下,没有到达目标状态下的正确位置的棋子的个数。

请使用该估计函数,对图示的初始状态,给出使用分支限界方法转换到目标状态的搜索树。

初始状态 目标状态

参考答案

一、名词解释:

1.算法:算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列,满足性质:(1)输入:有零个或多个外部量作为算法的输入;(2)输出:算法产生至少一个量作为输出;(3)确定性:组成算法的每条指令清晰、无歧义;(4)有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。

2.程序:程序是算法用某种程序设计语言的具体实现。

3.递归函数:用函数自身给出定义的函数称为递归函数。

4.子问题的重叠性质:递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算

多次,这种性质称为子问题的重叠性质。

5.队列式分支限界法:队列式(FIFO)分支限界法是将活结点表组织成一个队列,并按照队列的先进先出

(FIFO)原则选取下一个结点为扩展结点。

6.多机调度问题:多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m

台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。

作业不能拆分成更小的子作业。

7.最小生成树:G=(V,E)是无向连通带权图,G的子图称为G的生成树,生成树上各边权的总和称为该生成

树的耗费,在G的所有生成树中,耗费最小的生成树称为G的最小生成树。

二、简答题:

1.备忘录方法和动态规划算法相比有何异同?简述之。

备忘录方法是动态规划算法的变形。与动态规划算法一样,备忘录方法用表格保存已解决的子问题的答案,在下次需要解此问题时,只要简单地查看该子问题的解答,而不必重新计算。

备忘录方法与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上递归的。因此,备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同的子问题的重复求解,而直接递归方法没有此功能。

2.简述回溯法解题的主要步骤。

回溯法解题的主要步骤包括:

1)针对所给问题,定义问题的解空间;

2)确定易于搜索的解空间结构;

3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

3.简述动态规划算法求解的基本要素。

动态规划算法求解的基本要素包括:

1)最优子结构是问题能用动态规划算法求解的前提;

2)动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果,即重叠子问题。

4.简述回溯法的基本思想。

回溯法的基本做法是搜索,在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。

5.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。

将递归算法转化为非递归算法的方法主要有:

1)采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强,但本质上还是递归,只不过人工做了本来由编译器做的事情,优化效果不明显。

2)用递推来实现递归函数。

3)通过Cooper变换、反演变换能将一些递归转化为尾递归,从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善,但其适用范围有限。

6.简要分析分支限界法与回溯法的异同。

1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。

2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

7.简述算法复杂性的概念,算法复杂性度量主要指哪两个方面?

算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身,而且用C表示复杂性,那么,应该有C=F(N,I,A)。

算法复杂性度量主要包括算法的时间复杂性和算法的空间复杂性。

8.贪心算法求解的问题主要具有哪些性质?简述之。

贪心算法求解的问题一般具有二个重要的性质:

一是贪心选择性质,这是贪心算法可行的第一个基本要素;

另一个是最优子结构性质,问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

9.分治法的基本思想是什么?合并排序的基本思想是什么?请分别简述之。

分治法的基本思想:将n个输入分成k个不同子集合,得到k个不同的可独立求解的子问题,其中1

合并排序基本思想:将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。

10.简述分析贪心算法与动态规划算法的异同。

贪心算法和动态规划算法都要求问题具有最优子结构性质,这是两类算法的一个共同点。

动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。

三、算法编写及算法应用分析题:

1.已知有3个物品:(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10), 背包的容积M=20,根据0-1背包动态规划的递推式求出最优解。

解:

根据递推式

f i(X)=max{f i-1(X),f i-l(X—w i)+p i |X≥wi }

从i=1开始,最后得到f n(M)

f1(1) ~ f1(11)= 0

f1(12) ~ f1(20)= p1=15

f2(1) ~ f2(9)= 0

f2(10) ~ f2(11)= max{f1(10),f1(10 – w2)+p2} =13

f2(12) ~ f2(20)= max{f1(12),f1(12 – w2)+p2}=15

f3(20)=max{f2(20),f2(20 – w3)+p3} = f2(20 –6)+10=25

可获得的最大利润为25,最优解为:(1,0,1)

2.按要求完成以下关于排序和查找的问题。

(1)对数组A={15,29,135,18,32,1,27,25,5},用快速排序方法将其排成递减序。

(2)请描述递减数组进行二分搜索的基本思想,并给出非递归算法。

(3)给出上述算法的递归算法。

(4)使用上述算法对(1)所得到的结果搜索如下元素,并给出搜索过程:18,31,135。

解:(1)第一步:15 29 135 18 32 1 27 25 5

第二步:29 135 18 32 27 25 15 1 5

第三步:135 32 29 18 27 25 15 5 1

第四步:135 32 29 27 25 18 15 5 1

(2)基本思想:首先将待搜索元素v 与数组的中间元素2n A ??????进行比较,如果2n v A ??

>????,则在前半部分

元素中搜索v ;若2n v A ??

=????

,则搜索成功;否则在后半部分数组中搜索v 。

非递归算法:

输入:递减数组A[left:right],待搜索元素v 。

输出:v 在A 中的位置pos ,或者不在A 中的消息(-1)。 步骤:【3分】

int BinarySearch(int A[],int left,int right,int v) {

int mid;

while (left<=right) {

mid=int((left+right)/2); if (v==A[mid]) return mid;

else if (v>A[mid]) right=mid-1; else left=mid+1; }

return -1; }

(3)递归算法:

输入:递减数组A[left:right],待搜索元素v 。

输出:v 在A 中的位置pos ,或者不在A 中的消息(-1)。 步骤:

int BinarySearch(int A[],int left,int right,int v) {

int mid;

if (left<=right) {

mid=int((left+right)/2); if (v==A[mid]) return mid;

else if (v>A[mid]) return BinarySearch(A,left,mid-1,v); else return BinarySearch(A,mid+1,right,v); } else

return -1; }

(4)搜索18:首先与27比较,18<27,在后半部分搜索;再次与18比较,搜索到,返回5。

搜索31:首先与27比较,31>27,在前半部分搜索;再次32比较,31<32,在后半部分搜索,与29比较,31>29,此时只有一个元素,未找到,返回-1。

搜索135:首先与27比较,135>27,在前半部分搜索;再次32比较,135>32,在前半部分搜索;与135比较,相同,返回0。

3.已知()

1*()k k

ij i i r r A a +=,k =1,2,3,4,5,6,r 1

=5,r 2

=10,r 3

=3,r 4

=12,r 5

=5,r 6

=50,r 7

=6,求

矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序(要求给出计算步骤)。

解:使用动态规划算法进行求解。

求解矩阵为:

因此,最佳乘积序列为(A1A2)((A3A4)(A5A6)),共执行乘法2010次。

4.根据分枝限界算法基本过程,求解0-1背包问题。已知,n=3,M=20,(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10)。

解:用x(i)表示第i步选择的物品号,

x(1)=1,∧

c(2)=0,U(2)=23 ;

x(1)=2,∧

c(3)=15,U(3)=25,

x(1)=3,∧

c(4)=28,U (4)=28 ,

U=min{23,25,28}=23, 由于∧

c(4)=28>U 所以节点4删除。活节点表L={2,3},取最小代价估值节点2

作为扩展节点:

x(2)=2,w1+w2>M,节点5是不合理节点;

x(2)=3,这是答案节点c(6)=13,即找到了代价为13的解,修改U=13,

由于活节点表中的节点3有∧

c(3)=25,所以节点3可以删除。

这时L={},算法结束。最优解X={1,3} 搜索产生的状态空间树如下图:

5、试用贪心算法求解汽车加油问题:已知一辆汽车加满油后可行驶n公里,而旅途中有若干个加油站。试设计一个有效算法,指出应在哪些加油站停靠加油,使加油次数最少,请写出该算法。

解:int greedy(vecterx,int n)

{

int sum=0,k=x.size();

for(int j=0;j

if(x[j]>n){

cout<<”No solution”<

return -1;

}

for(int i=0,s=0;i

s+=x[i];

if(s>n){ sum++;s=x[i];}

}

return sum;

}

6、试用动态规划算法实现下列问题:设A和B是两个字符串。我们要用最少的字符操作,将字符串A转换为字符串B,这里所说的字符操作包括:

(1)删除一个字符。

(2)插入一个字符。

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

请写出该算法。

解:此题用动态规划算法求解:

int dist( )

{

int m=a.size( );

int n=b.size( );

vectord(n+1,0);

for(int i=1;i<=n;i++) d[i]=i;

for(i=1;i<=m;i++){

int y=i-1;

for(int j=1;j<=n;j++){

int x=y;

y=d[j];

int z=j>1?d[j-1]:i;

int del=a[i-1]= =b[j-1]?0:1;

d[j]=min(x+del,y+1,z+1);

}

}

return d[n];

}

7、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

解:用V 1表示已经找到最短路径的顶点,V 2表示与V 1中某个顶点相邻接且不在V 1中的顶点;E 1表示加入到最短路径中的边,E 2为与V 1中的顶点相邻接且距离最短的路径。 步骤 V 1 V 2 E 1 E 2 1. {a} {b} {} {ab} 2. {a,b} {d} {ab} {bd}

3. {a,b,d} {c,f} {ab,bd} {dc,df}

4. {a,b,d,c} {f} {ab,bd} {df}

5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe}

6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg}

7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh}

8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 结果:从a 到h 的最短路径为a b d f e g h →→→→→→,权值为18。

求所有顶点对之间的最短路径可以使用Dijkstra 算法,使其起始节点从a 循环到h ,每次求起始节点到其他节点的最短路径,最终可以求得所有顶点对之间的最短路径。 8、试写出用分治法对数组A[n]实现快速排序的算法。 解:用分治法求解的算法代码如下:

int partition(float A[],int p,int r) {

int i=p,j=r+1; float x=a[p]; while (1) {

while(a[++i]x); if(i>=j) break; a[i]];[j a ?

};

a[p]=a[j]; a[j]=x; return j;

}

void Quicksort( float a[], int p, int r ) {

if( p

int q=partition(a,p,r); Quicksort(a,p,q-1); Quicksort(a,q+1,r); }

};

Quicksort(a,0,n-1);

9、有n 个活动争用一个活动室。已知活动i占用的时间区域为[s i,f i],活动i,j相容的条件是:sj≥f i,问题的解表示为(x i| x i =1,2…,n,),x i表示顺序为i的活动编号活动,求一个相容的活动子集,且安排的活动数目最多。

解:解决这个问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排,好给后面的活动安排留出更多的空间,从而达到安排最多活动的目标。据此,贪心准则应当是:在未安排的活动中挑选结束时间最早的活动安排。在贪心算法中,将各项活动的开始时间和结束时间分别用两个数组s和f存储,并使得数组中元素的顺序按结束时间非减排列:

f1≤ f2≤…≤ fn。算法如下:

GreedyAction(s, f,n) // s[1:n]、f[1:n]分别代表n项活动的起始

//时间和结束时间, 并且满足f[1]≤ f[2]≤…≤ f[n]

j=1; solution={1}; //解向量初始化为空集

for i ←2 to n do

if si≥fj then

solution=solution ? {j}; // 将j加入解中

j=i;

endif

endfor

return(solution);

end Greedy

10、设x1、x2、x3是一个三角形的三条边,而且x1+x2+x3=14。请问有多少种不同的三角形?给出解答过程。

解:由于x1、x2、x3是三角形的三条边,从而xi+xj>xk,|xi-xj|

x3

即有4个可行解:(6,6,2),(6,5,3),(6,4,4,)(5,5,4)。

11、设数组A有n个元素,需要找出其中的最大最小值。

(1)请给出一个解决方法,并分析其复杂性。

(2)把n个元素等分为两组A1和A2,分别求这两组的最大值和最小值,然后分别将这两组的最大值和最小值相比较,求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个,则

再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想?

请给出该方法的算法描述,并分析其复杂性。

解:(1)基本思想:从头到尾逐个扫描,纪录最大和最小元素。

输入:具有n个元素的数组

输出:最大值和最小值

步骤:

void FindMaxMin(int A[], int n, int max, int min) {

max=min=A[0]; for (i=1;i

if (A[i]>max) max=A[i]; if (A[i]

复杂性分析:由于是从头到尾扫描各个元素,而每个元素都要与max 和min 比较一遍,从而时间复杂性为:O(n)。

(2)void FindMaxMin(int left,int right, int max, int min) { if (left==right) max=min=A[left]; else if (left=right-1) {

max=(A[left]

mid=(left+right)/2;

FindMaxMin(left,mid,gmax,gmin); FindMaxMin(mid+1,right,hmax,hmin); max=(gmax

} 12、有n 个程序和长度为L 的磁带,程序i 的长度为a i ,已知

L a

n

i i

∑=1

,求最优解(x i ,x 2 ,...,x i ,…,

x n ),x i =0,1, x i =1,表示程序i 存入磁带,x i =0,表示程序i 不存入磁带,满足

L a

x n

i i

i ≤∑=1

,且存放

的程序数目最多。

解:由于目标是存放的程序数目最多,所以最优量度应该是 min{a i | a i 为程序i 的长度},

即每次选入的程序都是当前最短的。我们可以将n 个程序按a[1]≤a[2]≤…≤a[n]顺序排序,然后从i=1开始依次选择。算法如下:

procedure programming(L,n, a, x) begin

//n 个程序按a[1]≤a[2]≤…≤a[n]顺序排序 x ←0; i=1;

while (a[i] ≤L and i ≤n) do { x[i] ←1; L ←L-a[i];i ←i+ 1; } end.

13、试用分治法实现有重复元素的排列问题:设),...,,{21n r r r R =是要进行排列的n 个元素,其中元素

n r r r ,...,,21可能相同,试设计计算R 的所有不同排列的算法。

解:解答如下:

Template

void Perm(Type list[],int k,int m)

{

if(k= =m){

for(int i=0;i<=m;i++) cout<

cout<

}

else for(int i=k;i<=m;i++)

if(ok(list,k,i)){

swap(list[k],list[i]);

Perm(list,k+1,m);

swap(list[k],list[i]);

};

}

其中ok用于判别重复元素。

Template

int ok(Type list[],int k,int i)

{

if(i>k)

for(int t=k;t

if(list[t]= =list[i]) return 0;

return 1;

}

14、试用动态规划算法实现0-1闭包问题,请写出该算法。

解:解答如下:

Template

void Knapsack(Type v,int w,int c,int n,Type **m)

{

Int jMax=min(w[n]-1,c);

for(int j=0;j<=jMax;j++) m[n][j]=0;

for(int j=w[n];j<=c;j++) m[n][j]=v[n];

for(int i=n-1;i>1;i--){

jMax=min(w[i]-1,c);

for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];

for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

};

m[1][c]=m[2][c];

if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

}

Template

Void Traceback(Type **m,int w,int c,int n,int x)

{

for(int i=1;i

if(m[i][c]= =m[i+1][c]) x[i]=0;

else { x[i]=1,c-=w[i];};

x[n]=(m[n][c])?1:0;

}

15、试用贪心算法求解下列问题:将正整数n分解为若干个互不相同的自然数之和,使这些自然数的乘积最大,请写出该算法。

解:解答如下:

void dicomp(int n,int a[])

{

k=1;

if(n<3){ a[1]=0;return;};

if(n<5){ a[k]=1;a[++k]=n-1;return;};

a[1]=2;n-=2;

while(n>a[k]){

k++;

a[k]=a[k-1]+1;

n-=a[k];

};

if(n= =a[k]){ a[k]++;n--;};

for(int i=0;i

}

16、试写出用分治法对一个有序表实现二分搜索的算法。

解:解答如下:

Template

int BinarySearch(Type a[],const Type& x,int n)

{//假定数组a[]已按非递减有序排列,本算法找到x后返回其在数组a[]中的位置,//否则返回-1 int left=0,right=n-1;

while(left<=right){

int middle=(left+right)/2;

if(x= =a[middle]) return middle+1;

if(x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

17、试用动态规划算法实现最长公共子序列问题,请写出该算法。

解:用动态规划算法求解的算法代码如下:

int lcs_len(char *a,char *b,int c[][N])

{

int m=strlen(a),n=strlen(b),i,j;

for(i=0;i<=m;i++) c[i][0]=0;

for(j=1;j<=n;j++) c[0][j]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if(a[i-1]= =b[j-1]) c[i][j]=c[i-1][j-1]+1;

else if(c[i-1][j]>=c[i][j-1])

c[i][j]=c[i-1][j];

else c[i][j]=c[i][j-1];

return c[m][n];

};

char *build_lcs(char s[],char *a,char *b)

{

int k,i=strlen(a),j=strlen(b),c[N][N]; k=lcs_len(a,b,c); s[k]=’\0’; while(k>0){

if(c[i][j]= =c[i-1][j]) i--;

else if(c[i][j]= =c[i][j-1]) j--; else{

s[--k]=a[i-1]; i--,j--; } }

return s;

}

18、假设有7个物品,它们的重量和价值如下表所示。若这些物品均不能被分割,且背包容量M =150,使用回溯方法求解此背包问题,请写出状态空间搜索树。

1~7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:

5x =6x =7x =a .1501154040305035190.62540

-++++?= 7(1,1,1,1,,0,0)8

b. 1501154040305030177.560

-++++?=7(1,1,1,1,0,,0)12

c .4040305010170++++=

(1,1,1,1,0,0,1)

d. 1501054040303530167.560

-++++?= 3(1,1,1,0,1,,0)4

e. 150130404050353017560

-++++?=

1

(1,1,0,1,1,,0)3

f. 1501304040503510170.7135

-++++?=

4(1,1,0,1,1,0,)7

g. 40405030160+++=

(1,1,0,1,0,1,0)

h. 1501404040353010146.8535-++++?= 2(1,1,0,0,1,1,)7

i.1501254030503530167.560-++++?=5(1,0,1,1,1,,0)12

j. 150145

4030503530157.560-++++?=1(0,1,1,1,1,,0)12

在Q 1处获得该问题的最优解为(1,1,1,1,0,0,1),背包效益为170。即在背包中装入物品F 、B 、G 、D 、A 时达到最大效益,为170,重量为150。

19、求解子集和问题:对于集合S={1,2 ,6,8},求子集,要求该子集的元素之和d=9。

①画出子集和问题的解空间树;

②该树运用回溯算法,写出依回溯算法遍历节点的顺序;

③ 如果S 中有n 个元素,指定d ,用伪代码描述求解子集和问题的回溯算法。 解答:满足要求的子集有[1,2,6], [1,8]

①解空间树如下:

ê G N ? ?O ? ?

③用伪代码描述算法如下: #include #define N 100 int as=0,t=0; int sum;

void backtrackiter(int i,int s[],int n,int d,int sum) {

if(i>n)

return;

else

{

if(as==d)

{

t++;

return;

}

sum-=s[i];

if(as+s[i]<=d)

{

as+=s[i];

backtrackiter(i+1,s,n,d,sum);

as-=s[i];

}

if(as+sum>=d)

backtrackiter(i+1,s,n,d,sum);

sum+=s[i];

}

}

20、求解填字游戏问题:在3×3个方格的方阵中要填入数字1到N(N≥10)内的某9个数字,每个方格填一个整数,似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一种数字填法的算法和满足这个要求的全部数字填法的算法。

解:为找到一个满足要求的9个数的填法,从还未填一个数开始,按某种顺序(如从小到大的顺序)每次在当前位置填入一个整数,然后检查当前填入的整数是否能满足要求。在满足要求的情况下,继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求,就改变填入的整数。如对当前方格试尽所有可能的整数,都不能满足要求,就得回退到前一方格,并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查,直到找到一个满足问题要求的解,将解输出。

回溯法找一个解的算法:

{ int m=0,ok=1;

int n=8;

do{

if (ok) 扩展;

else 调整;

ok=检查前m个整数填放的合理性;

} while ((!ok||m!=n)&&(m!=0))

if (m!=0) 输出解;

else 输出无解报告;

}

如果要找全部解,则在将找到的解输出后,应继续调整最后位置上填放的整数,试图去找下一个解。相应的算法如下:

回溯法找全部解的算法:

{ int m=0,ok=1;

int n=8; do{

if (ok)

{ if (m==n)

{ 输出解;

调整; }

else 扩展;

}

else 调整;

ok=检查前m 个整数填放的合理性; } while (m!=0);

}

21、试用动态规划算法实现最大子矩阵和问题:求n m ?矩阵A 的一个子矩阵,使其各元素之和为最大。 解:解答如下:

int MaxSum2(int m,int n,int **a) {

int sum=0;

int *b=new int[n+1]; for(int i=1;i<=m;i++){

for(int k=1;k<=n;k++) b[k]=0; for(int j=i;j<=m;j++){

for(int k=1;k<=n;k++) b[k]+=a[j][k]; int max=MaxSum(n,b);

if(max>sum) sum=max;

} }

return sum; }

int MaxSum(int n,int *a)

{

int sum=0,b=0;

for(int i=1;i<=n;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; }

Return sum; } 22、试用回溯法解决下列整数变换问题:关于整数i 的变换f 和g 定义如下:??2/)(;3)(i i g i i f ==。对于给定的两个整数n 和m ,要求用最少的变换f 和g 变换次数将n 变为m 。 解:解答如下:

void compute() { k=1;

while(!search(1,n)){

k++;

if(k>maxdep) break;

init();

};

if(found) output();

else cout<<”No Solution!”<

}

bool search(int dep,int n)

{

If(dep>k) return false;

for(int i=0;i<2;i++){

int n1=f(n,i);t[dep]=i;

if(n1= =m||search(dep+1,n1)){

Found=true;

Out();

return true;

}

return false;

}

23、关于15谜问题。在一个4×4的方格的棋盘上,将数字1到15代表的15个棋子以任意的顺序置入各方格中,空出一格。要求通过有限次的移动,把一个给定的初始状态变成目标状态。移动的规则是:每次只能把空格周围的四格数字(棋子)中的任意一个移入空格,从而形成一个新的状态。为了有效的移动,设计了估值函数C1(x),表示在结点x的状态下,没有到达目标状态下的正确位置的棋子的个数。

请使用该估计函数,对图示的初始状态,给出使用分支限界方法转换到目标状态的搜索树。

初始状态目标状态

解:

7

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

算法设计与分析考试题 及答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题(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.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质;②构造最优值的递归关系表达式; ③最优值的算法描述;④构造最优解; 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i };②将N 1中作业按a i 的非减序排序得到N 1’,将N 2中作业按b i 的非增序排序得到N 2’;③N 1’中作业接N 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个作业的最优调度方案,并计算最优值。 步骤为:N1={1,3},N2={2,4}; N 1’={1,3}, N 2’={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={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 为多少假设二叉搜索树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)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

算法分析与设计试卷

《算法分析与设计》试卷(A) (时间90分钟满分100分) 一、填空题(30分,每题2分)。 1.最长公共子序列算法利用的算法是( B )。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2.在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3.实现最大子段和利用的算法是( B )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4..广度优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5.衡量一个算法好坏的标准是( C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6.Strassen矩阵乘法是利用( A)实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是( A )。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8.用动态规划算法解决最大字段和问题,其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题,最好用( B )算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略( B ) A.递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是( C )。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14.下面是贪心算法的基本要素的是( C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15.回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题(20分,每空1分)。 1.算法由若干条指令组成的又穷序列,且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法,用一个队列来存储结点的表叫活节点表。

2015年算法分析与设计期末考试试卷B卷

西南交通大学2015 — 2016学年第(一)学期考试试卷 课程代码 3244152课程名称 算法分析与设计 考试时间 120分钟 阅卷教师签字: __________________________________ 填空题(每空1分,共15分) 1、 程序是 (1) 用某种程序设计语言的具体实现。 2、 矩阵连乘问题的算法可由 (2) 设计实现。 3、 从分治法的一般设计模式可以看出,用它设计出的程序一般是 (3) 4、 大整数乘积算法是用 (4) 来设计的。 5、 贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优 考虑,它所做出的选择只是在某种意义上的 (6) o 6、 回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、 平衡二叉树对于查找算法而言是一种变治策略,属于变治思想中的 (9) 类型 8、 在忽略常数因子的情况下,0、门和0三个符号中, (10) 提供了算法运行时 间的一个上界。 9、 算法的“确定性”指的是组成算法的每条 (11) 是清晰的,无歧义的。 10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13),它们规定了解决某一特定类型问题的 (14) o 12、 变治思想有三种主要的类型:实例化简,改变表现, (15) o 、 ___________________________________________________________________________________ L 线订装封密 线订装封密 、 __________________ 二 线订装封密 级班 选择题(每题2分,共20 分)

系统与设计复习题

《系统分析与设计》复习题 一.选择题: 1.面向对象的特点主要概括为(C )。 A. 可分解性、可组合性、可分类性 B. 继承性、封装性、 多态性 C. 抽象性、继承性、封装性、多态性 D. 封装性、易维护性、 可扩展性、可重用性 2.信息按照( C )可以分为战略信息、战术信息和作业信息。 A. 应用领域 B. 加工顺序 C. 管理的层次 D. 反映形式 3.按照处理的对象,可把组织的信息系统分为(B )和管理 信息系统两大类。 A. 电子数据处理系统 B. 作业信息系统 C. 决策支持系统 D. 情报处理系统 4.在开发一个企业管理信息系统时,首先要进行用户调查,调查 中收集的主要信息包括( D )。 A. 管理目标、人力资源、业务流程和数据流程信息 B. 组织结构、功能体系、业务流程和数据流程信息 C. 企业性质、客户资源、业务流程和数据流程信息 D. 管理目标、功能体系、业务流程和数据流程信息 5.系统流程图也称为业务流程图,它表达的是(B )。 A. 数据在系统各部件间的流动情况 B. 对数据进行加工

处理的控制过程 C. 逻辑数据流图 D. 白盒子形式的组成系统 的每个部件 6.一般子系统的划分是在系统( C )阶段,根据对系统的功 能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计 7.信息系统流程图是以新系统的( D )为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流图 8.在关系规范化过程中,一般来讲,满足(C )的关系即可 满足信息处理的要求,就可以认为是比较规范的关系。 A. 第一范式 B. 第二范式 C. 第三范式 D. BC范式 9.信息系统开发的结构化方法的一个主要原则是( A )。 A. 自顶向下原则 B. 自底向上原则 C. 分步实施原则 D. 重点突破原则 10.用户开发应用系统的主要手段是( A )。 A. 生命周期法 B. 原型法 C. 第四代语言 D. 面向对象 方法 11.系统规划的主要任务包括( A )。 A. 明确组织的信息需求、制定系统总体结构方案 B. 对系统进行经济、技术和使用方面的可行性研究 C. 选择计算机和网络系统的方案 D. 确定软件系统的模块结构

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

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算法的思想。

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

考试课程: 班级: 姓名: 学号: ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

考试课程: 班级: 姓名: 学号: ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作; 高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高; 高级语言不依赖于机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可植性好、重用率高; 把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短,程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量。 2、 ①不能保证最后求得的解是最佳的;即多半是近似解。(少数问题除外) ②策略容易发现(关键:提取清楚问题中的维度), 而且运用简单,被广泛运用。 ③策略多样,结果也多样。 ④算法实现过程中,通常用到辅助算法:排序 3、解:① 因为:;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知: 1-10n n 2 2+是n ;的渐近表达式。 ② 因为:;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知: 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质,并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息,构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为:FBGDECA 。将它们的序号分别记为1~7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】 5x =6x =7x =

信息系统分析与设计考试相关习题及答案

一、选择填空 4. 业务系统规划法(BSP)的核心是() A. 明确企业目标 B. 定义(识别)业务过程 C. 进行数据分析 D. 确定信息结构答案: C 5. 下面哪一项企业关键成功因素的特点是错误的:()。 A. 少量的易于识别的可操作的目标 B. 可确保企业的成功 C. 由企业的所有CSF决定组织的信息需求答案: B 7. 一般子系统的划分是在系统()阶段,根据对系统的功能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计答案: A 10. 信息系统流程图是以新系统的()为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流程图答案: D 14. 信息系统开发的结构化方法的一个主要原则是()。 A. 自顶向下原则 B. 自底向上原则 C. 分步实施原则 D. 重点突破原则答案: A 16. 一般来说,占维护工作比例最高的是()。 A. 纠错性维护 B. 适应性维护 C. 完善性维护 D. 预防性维护答案: C 19. 系统规划的主要任务包括()。 A. 明确组织的信息需求、制定系统总体结构方案 B. 对系统进行经济、技术和使用方面的可行性研究 C. 选择计算机和网络系统的方案 D. 确定软件系统的模块结构答案: A 20. 系统设计阶段的主要成果是()。 A. 用户的决策方针 B. 用户的分析方案 C. 系统设计说明书 D. 系统总体设计方案答案: C 21. 信息系统建设的结构化方法中用户必须参与的原则是用户必须参与()。 A. 系统建设中各阶段工作 B. 系统分析工作 C. 系统设计工作 D. 系统实施工作答案: A 22. 结构化生命周期法的主要缺点之一是()。 A. 系统开发周期长 B. 缺乏标准、规范 C. 用户参与程度低 D. 主要工作集中在实施阶段答案: A 23. MIS规划的主要内容是()。 A. MIS战略规划,组织信息需求分析,系统目标 B. 组织信息需求分析,系统目标,资源分配 C. MIS战略规划,资源分配,系统目标 D. MIS战略规划,组织信息需要分析,资源分配答案: A 28. 生命周期法的特点之一是()。 A. 整个系统的开发工作是非劳动密集型的 B. 系统开发时间短 C. 对用户需求的变更不能做出迅速响应 D. 适合大型复杂系统答案: C 29. 系统测试中应遵循的一条原则是:测试工作应该由以下人员来承担()。 A. 原程序作者 B. 专门的测试人员 C. 系统设计人员 D. 用户答案: B 30. 系统维护中要解决的问题来源于()。 A. 系统分析阶段 B. 系统设计阶段 C. 系统实施阶段 D. 三者都包括答案: D 31. 在原型法中,原型是进行开发的系统的()。 A. 反映用户最基本需求的可以运行的实验模型 B. 某一主要部分的详细设计方案(物理模型)

(完整版)算法设计与分析期末考试卷及答案a

一.填空题(每空 2 分,共30分) 1.算法的时间复杂性指算法中的执行次数。 2.在忽略常数因子的情况下,O、和三个符号中,提供了算法运行时间的一个上界。 3.设D n表示大小为n的输入集合,t(I)表示输入为I时算法的运算时间, p(I)表示输入 I 出现的概率,则算法的平均情况下时间复杂性A(n)= 。 4.分治算法的时间复杂性常常满足如下形式的递归方程: f (n) d , n n0 f(n) af(n/c) g(n) , n n0 其中,g(n)表示。 5. 分治算法的基本步骤包括。6.回溯算法的基本思想是。 7.动态规划和分治法在分解子问题方面的不同点是。 8.贪心算法中每次做出的贪心选择都是最优选择。 9.PQ 式的分支限界法中,对于活结点表中的结点,其下界函数值越小,优先级 10.选择排序、插入排序和归并排序算法中,算法是分治算法。 11.随机算法的一个基本特征是对于同一组输入,不同的运行可能得到的结果。12. 对于下面的确定性快速排序算法,只要在步骤3 前加入随机 化步骤,就可得到一个随机化快速排序算法,该随机化步骤的功能是。 算法QUICKSORT 输入:n 个元素的数组A[1..n] 。 输出:按非降序排列的数组 A 中的元素

1. quicksort(1, n) end QUICKSORT _ _ 过程 quicksort(A, low, high) _ _ // 对 A[low..high] 中的元素按非降序排序。 _ 号 学 2. if low

5.《算法设计与分析》试题库

《算法分析与设计》试题库 (一) 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是(D ) A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上,并 D.动态规划算法

3. 动态规划算法的基本要素为(C) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质

D.预排序与递归调用 4. 算法分析中,记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有:(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题,一般具有的重要性质为:(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中,按(D)策略,从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先

算法设计与分析试卷(2010)

内部资料,转载请注明出处,谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 ( 选择1-4个正确的答案, 每题2分,共20分) (1)计算机算法的正确描述是: A .一个算法是求特定问题的运算序列。 B .算法是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型的问题的运算序列。 C .算法是一个对任一有效输入能够停机的图灵机。 D .一个算法,它是满足5 个特性的程序,这5个特性是:有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 (2)影响程序执行时间的因素有哪些? A .算法设计的策略 B .问题的规模 C .编译程序产生的机器代码质量 D .计算机执行指令的速度 (3)用数量级形式表示的算法执行时间称为算法的 A .时间复杂度 B .空间复杂度 C .处理器复杂度 D .通信复杂度 (4)时间复杂性为多项式界的算法有: A .快速排序算法 B .n-后问题 C .计算π值 D .prim 算法 (5)对于并行算法与串行算法的关系,正确的理解是: A .高效的串行算法不一定是能导出高效的并行算法 B .高效的串行算法不一定隐含并行性 C .串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 (6)衡量近似算法性能的重要标准有: A .算法复杂度 B .问题复杂度 C .解的最优近似度 D .算法的策略 (7)分治法的适用条件是,所解决的问题一般具有这些特征: A .该问题的规模缩小到一定的程度就可以容易地解决; B .该问题可以分解为若干个规模较小的相同问题; C .利用该问题分解出的子问题的解可以合并为该问题的解 D .该问题所分解出的各个子问题是相互独立的。 (8)具有最优子结构的算法有: A .概率算法 B .回溯法 C .分支限界法 D .动态规划法 (9)下列哪些问题是典型的NP 完全问题: A .排序问题 B .n-后问题 C .m-着色问题 D .旅行商问题 (10)适于递归实现的算法有: A .并行算法 B .近似算法 C .分治法 D .回溯法 二、算法分析题(每小题5分,共10分) (11)用展开法求解递推关系: (12)分析当输入数据已经有序时快速排序算法的不足,提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

软件系统分析与设计考试题

题目内容: 一、单项选择题:(本大题共20小题,每题1分,共20分) ? 1. 组成UML有三种基本的建筑块是:(?A ),事物和图 A、关系?????????????????? B、类 C、用例?????????????????? D、实体 2、UML体系包括三个部分:UML基本构造块,(?A )和UML公共机制 A、UML规则????????????? B、UML命名 C、UML模型????????????? D、UML约束 3、UML中的事物包括:结构事物,分组事物,注释事物和( D) A、实体事物?????????? ???????? B、边界事物 C、控制事物?????????????????? D、动作事物 4、( A)模型的缺点是缺乏灵活性,特别是无法解决软件需求不明确或不准确的问题 A、瀑布模型?????????????????? B、原型模型 C、增量模型?????????????????? D、螺旋模型 5、下面哪个不是UML中的静态视图(A? ) A.状态图??????????????????? B.用例图 C.对象图??????????????????? D.类图 6、(?A )技术是将一个活动图中的活动状态进行分组,每一组表示一个特定的类、人或部门,他们负责完成组内的活动。 ? A、泳道??????????????????? B、分叉汇合 ? C、分支??????????????????? D、转移 7、下列关于状态图的说法中,正确的是( C ) A. 状态图是UML中对系统的静态方面进行建模的五种图之一。 B. 状态图是活动图的一个特例,状态图中的多数状态是活动状态 C.活动图和状态图是对一个对象的生命周期进行建模,描述对象随时间变化的 行为。 D. 状态图强调对有几个对象参与的活动过程建模,而活动图更强调对单个反应 型对象建模 8、对反应型对象建模一般使用(?A )图 A、状态图??????????????????? B、顺序图 ?C、活动图??????????????????? D、类图

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

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:120分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分,共计30 分) 1、用O、Ω与θ表示函数f与g之间得关系______________________________。 2、算法得时间复杂性为,则算法得时间复杂性得阶为__________________________。 3、快速排序算法得性能取决于______________________________。 4、算法就是_______________________________________________________。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是_________________________。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是_____情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越___________,结果就越有价值。。 8、____________________________就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指____________________________________________________________________________________________________________________。 10、回溯法在问题得解空间树中,按______________策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计30分) 1、试述回溯法得基本思想及用回溯法解题得步骤。 2、有8个作业{1,2,…,8}要在由2台机器M1与M2组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M1与M2加工作业i所需得时间分别为: M110 2 8 12 6 9414

信息系统分析与设计考试题库及答案

一、选择填空 1. 信息按照(C )可以分为战略信息、战术信息和作业信息)可以分为战略信息、战术信息和作业信息。 A. 应用领域 B. 加工顺序 C. 管理的层次 D. 反映形式 2. 按照处理的对象,可把组织的信息系统分为( B ) 和管理信息系统两大类。按照处理的对象,可把组织的信息系统分为) 和管理信息系统两大类。 A. 电子数据处理系统 B. 作业信息系统 C. 决策支持系统 D. 情报处理系统 3. 信息系统对管理职能的支持,归根到底是对( D ) 的支持。 A. 计划 B. 组织 C. 控制 D. 决策 4. 业务系统规划法(BSP)的核心是(C ) A. 明确企业目标 B. 定义(识别)业务过程 C. 进行数据分析 D. 确定信息结构 5. 下面哪一项企业关键成功因素的特点是错误的:( B )。 A. 少量的易于识别的可操作的目标 B. 可确保企业的成功 C. 由企业的所有CSF决定组织的信息需求 6. 下面哪一项不是信息系统局部开发层次的优势:( D )。 A. 相对简单的IT开发 B. 帮助理论的证明 C. 组织变化的阻力最小 D. 优化组织过程 7. 一般子系统的划分是在系统( A )阶段,根据对系统的功能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计 8. 在新产品开发机构重组中,以开发某一新产品为目标,组织集设计、工艺、生产、供应、检验人员为一体的承包组,打破部门的界限,实行团队管理,以及将设计、工艺、生产制造并行交叉的作业管理,这属于( C )。 A. 功能内的BPR B. 组织间的BPR C. 功能间的BPR D. 功能内的BPR 9. 数据存贮设计则根据数据资源分布具体确定了数据存贮的( A )。 A. 逻辑方式 B. 物理方式 10. 信息系统流程图是以新系统的( D )为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流程图 11. 在关系规范化过程中,一般来讲,满足( C )的关系即可满足信息处理的要求,就可以认为是比较规范的关系。 A. 第一范式 B. 第二范式 C. 第三范式 D. BC范式 12. RUP中的软件生命周期在时间上被分解为四个顺序的阶段,分别是:初始阶段(Inception)、细化阶段(Elaboration)、构造阶段(Construction)和交付阶段(Transition),每个阶段结束于一个主要的里程碑(Major Milestones)。构建阶段结束时是第三个重要的里程碑:( C ) A. 生命周期目标(Lifecycle Objective)里程碑 C. 初始功能(Initial Operational)里程碑 B. 生命周期结构(Lifecycle Architecture)里程碑 D. 产品发布(Product Release)里程碑 13. 从社会经济发展的角度来看,信息化是指( D )。 A. 计算机和网络的应用规模与效益不断增长的过程 B. 社会上进行交换的信息量不断增长的过程 C. 计算机硬件产业、软件产业、信息服务产业不断发展的过程 D. 人们的信息活动的规模不断扩大以致在国民经济中起主导作用的过程

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

算法分析与设计复习题及答案一、单选题 1.D 2.B 3.C 4.D 5.D 6.D 7.C 8.D 9.B 10.C 11.D 12.B 13.D 14.C 15.C 16.D 17.D 18.D 19.D 20.C 1.与算法英文单词algorithm具有相同来源的单词是()。 A logarithm B algiros C arithmos D algebra 2.根据执行算法的计算机指令体系结构,算法可以分为()。 A精确算法与近似算法B串行算法语并行算法 C稳定算法与不稳定算法D32位算法与64位算法 3.具有10个节点的完全二叉树的高度是()。 A6B5C3D 2 4.下列函数关系随着输入量增大增加最快的是()。 Alog2n B n2 C 2n D n! 5.下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6.Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7.4个盘子的汉诺塔,至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8.下列序列不是堆的是()。 A 99,85,98,77,80,60,82,40,22,10,66 B 99,98,85,82,80,77,66,60,40,22,10 C 10,22,40,60,66,77,80,82,85,98,99 D 99,85,40,77,80,60,66,98,82,10,22 9.Strassen矩阵乘法的算法复杂度为()。 AΘ(n3)BΘ(n2.807) CΘ(n2) DΘ(n) 10.集合A的幂集是()。 A.A中所有元素的集合 B. A的子集合 C. A 的所有子集合的集合 D. 空集 11.与算法英文单词algorithm具有相同来源的单词是()。 A logarithm B algiros C arithmos D algebra 12.从排序过程是否完全在内存中显示,排序问题可以分为()。 A稳定排序与不稳定排序B内排序与外排序 C直接排序与间接排序D主排序与辅助排序 13.下列()不是衡量算法的标准。 A时间效率B空间效率 C问题难度D适应能力 14.对于根树,出度为零的节点为()。 A0节点B根节点C叶节点D分支节点 15.对完全二叉树自顶向下,从左向右给节点编号,节点编号为10的父节点编号为()。 A0B2C4D6 16.下列程序段的算法时间的复杂度为()。 for i ←0 to n do for j ←0 to m do

系统分析与设计复习题

《系统分析与设计》复习题 一、复习要点 1.系统是由处于一定环境中的若干相互联系和相互作用的要素组成并为达到整体目的而存在的集 合。 2.信息系统是指利用计算机、网络、数据库等现代信息技术,处理组织中的数据、业务、管理和 决策等问题,并为组织目标服务的综合系统。信息系统开发的步骤是,在系统规划后,循环进行系统分析、系统设计、系统构建与实施、系统评价工作。信息系统的经济效益可分为三大类:一次性收益,非一次性收益和不可定量的收益 3.系统规划阶段的任务是对组织的环境、战略、目标、现行系统的状况进行初步调查,根据组织 目标和发展战略,确定信息系统的发展战略,对建设新系统的需求做出分析和预测,同时考虑建设新系统所受的各种约束,研究建设新系统的必要性和可能性。对于确定的信息系统项目,要明确其目标,并对目标进行权衡和量化。 4.系统分析的主要活动有系统初步调查、系统可行性研究、系统详细调查研究和新系统逻辑方案 的提出,主要任务是尽可能弄清用户对信息的需求,完成新系统的逻辑设计,规定新系统应当做什么。 5.常用的调查研究的方法有问卷调查法、召开调查会、业务实践、专家访谈、电子问卷。如果系 统初步调查结果表明,拟开发项目有必要也有可能进行时,可向主管单位提出系统开发建议书,需要进行可行性研究安排。 6.可行性研究又叫可行性分析,它是所有工程项目在开始阶段必须进行的一项工作。可行性研究 是指项目正式开发之前,先投入一定的精力,通过一套准则,从经济、技术、社会等方面对项目的必要性、可能性、合理性,以及项目所面临的重大风险进行分析和评价,得出项目是否可行的结论。可行性研究的主要成果是可行性研究报告和系统开发任务书。 7.需求分析是强调用户对新开发的信息系统的需要和要求,结合组织的目标、现状、实力和技术 等因素,通过深入细致的分析,确定出合理可行的信息系统需求,并通过规范的形式描述需求的过程。需求分析结束时,应当提出需求分析报告交上级审查。信息系统需求分为功能需求和非功能需求两类。 8.系统设计用来确定系统的结构,即系统的组成以及各组成成分之间的相互关系,详细设计用来 确定模块内部的算法和数据结构,产生描述各模块程序过程的详细设计文档。系统设计是对系统分析的深化和细化,其目的是提出能够指导信息系统实现的设计方案。系统实施以系统分析

《算法分析与设计》期末试题及参考答案

《算法分析与设计》期末试题及参考答案 一、简要回答下列问题: 1.算法重要特性是什么? 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么? 2.分析算法占用计算机资源的情况,对算法做出比较和评价,设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关? 3. 算法的时间复杂性与问题的规模相关,是问题大小n的函数。 4.算法的渐进时间复杂性的含义? 4.当问题的规模n趋向无穷大时,影响算法效率的重要因素是T(n)的数量级,而其他因素仅是使时间复杂度相差常数倍,因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同? 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时,不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度: W(n) = max{ T(n,I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和: A(n) =∑P(I)T(n,I) I∈Dn 6.简述二分检索(折半查找)算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i:j] 和x,选取A[(i+j)/2]与x比较, 如果A[(i+j)/2]=x,则返回(i+j)/2,如果A[(i+j)/2]

信息系统分析与设计考试题库和答案1.doc

信息系统分析与设计考试题库和答案1 信息系统分析与设计考试题库及答案 一,选择填空 1. 信息按照( )可以分为战略信息,战术信息和作业信息)可以分为战略信息,战术信息和作业信息. A. 应用领域 B. 加工顺序 C. 管理的层次 D. 反映形式 答案: C 2. 按照处理的对象,可把组织的信息系统分为( ) 和管理信息系统两大类. A. 电子数据处理系统 B. 作业信息系统 C. 决策支持系统 D. 情报处理系统 答案: B 3. 信息系统对管理职能的支持,归根到底是对( ) 的支持.

A. 计划 B. 组织 C. 控制 D. 决策 答案: D 4. 业务系统规划法(BSP)的核心是( ) A. 明确企业目标 B. 定义(识别)业务过程 C. 进行数据分析 D. 确定信息结构 答案: C 5. 下面哪一项企业关键成功因素的特点是错误的: ( ). A. 少量的易于识别的可操作的目标 B. 可确保企业的成功 C. 由企业的所有CSF决定组织的信息需求 答案: B 6. 下面哪一项不是信息系统局部开发层次的优势:( ).

A. 相对简单的IT开发 B. 帮助理论的证明 C. 组织变化的阻力最小 D. 优化组织过程 答案: D 7. 一般子系统的划分是在系统( )阶段,根据对系统的功能/数据分析的结果提出的. A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计 答案: A 8. 在新产品开发机构重组中,以开发某一新产品为目标,组织集设计,工艺,生产,供应,检验人员为一体的承包组,打破部门的界限,实行团队管理,以及将设计,工艺,生产制造并行交叉的作业管理,这属于( ). A. 功能内的BPR B. 组织间的BPR C. 功能间的BPR

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

一、选择题 1.一个.java文件中可以有()个public类。 A.一个B.两个C.多个D.零个 2.一个算法应该是() A.程序B.问题求解步骤的描述 C.要满足五个基本特性D.A和C 3.用计算机无法解决“打印所有素数”的问题,其原因是解决该问题的算法违背了算法特征中的()A.唯一性B.有穷性C.有0个或多个输入D.有输出 4.某校有6位学生参加学生会主席竞选,得票数依次为130,20,98,15,67,3。若采用冒泡排序算法对其进行排序,则完成第二遍时的结果是() A.3,15,130,20,98,67B.3,15,20,130,98,67 C.3,15,20,67,130,98 D.3,15,20,67,98,130 5.下列关于算法的描述,正确的是() A.一个算法的执行步骤可以是无限的B.一个完整的算法必须有输出 C.算法只能用流程图表示D.一个完整的算法至少有一个输入 6.Java Application源程序的主类是指包含有()方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7.找出满足各位数字之和等于5的所有三位数可采用的算法思路是() A.分治法B.减治法C.蛮力法D.变治法 8.在编写Java Application程序时,若需要使用到标准输入输出语句,必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9.计算某球队平均年龄的部分算法流程图如图所示,其中:c用来记录已输入球员的人数,sum用来计算有效数据之和,d用来存储从键盘输入的球员年龄值,输入0时表示输入结束。

相关主题
相关文档 最新文档