算法设计与分析试卷计本3班

1、文档供参考，可复制、编制，期待您的好评与关注！ 算法设计与分析试卷填空题（20分，每空2分）1.算法的性质包括输入、输出、有限性。2.动态规划算法的基本思想就将待求问题、先求解子问题，然后从这些子问题的解得到原问题的解。3.设计动态规划算法的4个步骤：4.找出，并刻画其结构特征。5.根据计算最优值得到的信息，。6.流水作业调度问题的johnson算法：令N1=,N2=i|ai>=bj;将N1中作业依ai的。7.对于流水作业高度问题，必存在一个最优调度，使得作业（i）和（i+1）满足Johnson不等式。8.最优二叉搜索树即是的二叉搜索树。9.下面程序段的所需要的计算时间为（ ）。int

2、MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(int i=1;i<=n;i+) int thissum=0;for(int j=i;j<=n;j+) thissum+=aj;if(thissum>sum)sum=thissum;besti=i;bestj=j;return sum;10,有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（ 1，4，8

3、，11 ）。1413121110987654fi122886535031Si1110987654321i11,所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。12,所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。13,回溯法是回溯法是指（具有限界函数的深度优先生成法）。14. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n)）。15. 回溯法的算法框架按照问题的解空间一般

4、分为（子集树）算法框架与（排列树）算法框架。16. 用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。17.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。18.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：Typep Knap<Typew, Typep>:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i <= n && wi <= cle

5、ft) cleft -= wi; b += pi; i+; / 装满背包 if (i <= n) （b += pi/wi * cleft）; return b;19. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。for (int i = 0; i < NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (

6、gridnbr.rownbr.col = 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) && (nbr.col = finish.col) break; / 完成布线 Q.Add(nbr); 20. 用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn）。Bool Color:OK(int k)/ for(int j=1;j<=n;j+)if(akj= =1)&&a

7、mp;(xj= =xk) return false;return true;21. 旅行售货员问题的解空间树是（排列树）。二、单选题1、模块化程序设计方法主要通过()来实现。    A.递归算法和递归程序    B.过程和函数的定义和调用C.程序的循环结构    D.对象           答案:B 2、text1.text的含义正确的是()。  

8、;  A.text1是控件名称，text是控件属性    B.text1是窗体名称，text是控件C.text1是控件名称，text是方法    D.text1是控件属性，text是控件    答案:A 3、以下程序段运行后S的值是()。s = 0For i = 1 To 14    x = 2 * i - 1    If x Mod 3 = 0 Then s = s + 1Next i

9、    A.0  B.4    C.5    D.14    答案:C    4、数列1，4，7，10，13，的递推公式为()。    A.f(1)=1;f(n)=n+3    B.f(1)=1;f(n)=n*2-1    C.f(1)=1;f(n)=n*2+1

10、0;   D.f(1)=1;f(n)=f(n-1)+3    答案:D 5、对于对象及其特征的错误理解是()。    A.对象都具有一个标识自己以区别其他对象的名字。    B.对象都具有自身的属性及其属性值。    C.对象一般只用数据表示属性，但不用代码表示行为。    D.对象都具有自身的行为(操作)。    答

11、案:C 6、VB函数Left ()从字串左端取部分字串，那么Left("Visual Basic 6.0", 8)的值为()。    A.Visual B    B.Visual    C.Visual Ba    D.asic 6.0    答案:A 7、程序段如下：c ="1234"For i = 1 To 4  

12、  Print _，Next如果要让程序运行后得到如下结果：1 12 123 1234则在下划线处应填入的内容为()。    A.Right(c,i)    B.Left(c,i)    C.Mid(c,i,1)    D.Mid(c,i,i)    答案:B8、若X = True，执行If X Then X = 0 Else X = 1后X的结果为()。A.True 

13、0;  B.编译错误    C.1    D.0    答案:D 9、若x = False, y = True，执行If x And y  Then x = 0Else x = 1后X的结果为()。    A.False    B.1    C.编译错误    D.0 

14、   答案:B 10、以下程序段运行时语句k=k+1执行次数为()次。k=20do while (k=0)    k=k+1loop    A.20    B.无数次    C.1    D.0    答案:D 11、如果A=30，B=40,执行T=B:A=T:B=A语句后,A、B和T的值是()。  

15、;  A.30、40、30    B.40、40、40    C.30、30、30    D.40、30、40    答案:B 12、用选择排序法对数据7，6，3，9，2从大到小排序，共需经过()次数据对调。    A.3    B.4    C.5   &#

16、160;D.10    答案:A 13、采用模块化方法得到的系统是由()的模块构成的。    A.没有连接    B.函数    C.互相连接    D.过程    答案:C    14、(1.5分)下列程序段运行后X的值是()。x = 0For i = 1 To 5    Fo

17、r j = i To 3        x = x + 1    Next jNext i    A.0    B.5    C.6    D.15    答案:C 15、要从n个数据元素中顺序查找一个元素，最多查找次数是()。    A.1

18、0;   B.n    C.n/2    D.lgn    答案:B        16、对半查找算法的前提是()。    A.被查找数据元素个数是奇数    B.被查找数据元素个数是偶数    C.被查找数据元素是有序的  &#

19、160; D.被查找数据元素是无序的    答案:C 17、用折半查找法从数列3，6，7，10，12，16，25，30，75中找到数据10的最少查找次数是()。    A.2    B.3    C.4    D.7    答案:B 18、对象的特征称为()，我们可以把()看作对象的响应，把()看作对象的动作。 

20、60;  A.属性，事件，方法    B.属性，方法，事件    C.方法，事件，属性    D.方法，属性，事件    答案:A    19、设置一个控件在窗体上的位置可修改控件的()属性。    A.Width、Height    B.Visible、Enabled  

21、60; C.Top、Left    D.Style    答案:C    20、算法与程序的关系()。    A.算法是对程序的描述    B.算法决定程序，是程序设计的核心    C.算法与程序之间无关系    D.程序决定算法，是算法设计的核心    答案:B

22、60;   21、当a=5,b=7,c=-2,d=1时，下列结果为False的是()。    A.a + b c + d And a = 5 Or Not c 0 Or d 0    B.c + d a + b And a = 5 Or Not c 0 Or d 0    C.a + b c + d And a 5 Or Not c 0 Or d 0    D.a + d b + c And a = 5 O

23、r Not c 0 Or d 0    答案:D    22、在流程图中表示算法中的条件判断时使用()图形框。    A.菱形框     B.矩形框    C.圆形框    D.平行四边形框    答案:A    23、VB语言中，下列各种基本数据类型说明符中表示单精度

24、实型数的是()。    A.Integer    B.Boolean    C.Single    D.String    答案:C    24、程序的基本结构有顺序结构、()和循环结构。    A.逻辑结构    B.选择结构    C.

25、模块结构    D.层次结构    答案:B   25、一个算法应该具备几个方面的基本特征，下面不属于算法基本特征的是()。    A.输入输出    B.有穷性    C.确定性    D.执行性    答案:D 26、人们利用计算机解决问题的基本过程一般有如下四个步骤（），请

26、按各步骤的先后顺序在下列选项中选择正确的答案()。调试程序 分析问题 设计算法 编写程序    A.    B.    C.    D.    答案:B    27、以下哪个是合法的变量名()。    A.sqr    B.2pai    

27、C.cj1    D.a+b    答案:C    28、VB中保存工程文件的文件扩展名为()。    A.vbp    B.frm    C.doc    D.pas    答案:A    29、VB表达式5 + 2 * 12 Mod 8

28、 的值是()。    A.13    B.5    C.28    D.8    答案:B    30、由二进制编码指令组表示程序的程序设计语言是()。    A.自然语言    B.机器语言    C.汇编语言  &#

29、160; D.高级语言    答案:B31.应用Johnson法则的流水作业调度采用的算法是（D）A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法32.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）A. void hanoi(int n, int A, int C, int B) if (n > 0) hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1,

30、 C, B, A); Hanoi塔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); C. void hanoi(int n, int C, int B, int A) if (n > 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); D. void hanoi(int n, int C, int A, int B) if (n > 0) hanoi

31、(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); 33. 动态规划算法的基本要素为（C）A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用34. 算法分析中，记号O表示（B）， 记号表示（A）， 记号表示（D）。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界 35. 以下关于渐进记号的性质是正确的有：（A）A.B. C. O(f(n)+O(g(n) = O(minf(n),g(n) D. 36. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A. 最优

32、子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用37. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A.广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先38. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。 A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先39. 程序块（A）是回溯法中遍历排列树的算法框架程序。void backtrack (int t) if (t>n) output(x); else for (int i=t;i<=n;i+) s

33、wap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); A.void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t+1); B. void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t-1); C.void backtrack

34、(int t) if (t>n) output(x); else for (int i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); D.40. 回溯法的效率不依赖于以下哪一个因素？（C ）产生xk的时间；满足显约束的xk值的个数；问题的解空间的形式； 计算上界函数bound的时间；满足约束函数和上界函数约束的所有xk的个数。计算约束函数constraint的时间；41. 常见的两种分支限界法为（D）A. 广度优先分支限界法与深度优先分支限界法；B. 队列式（FIFO）分支限界法与堆栈式分支限界法；C. 排列树法与子集树

35、法；D. 队列式（FIFO）分支限界法与优先队列式分支限界法；42. k带图灵机的空间复杂性S(n)是指（B）k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数。43. NP类语言在图灵机下的定义为（D）NP=L|L是一个能在非多项式时间内被一台NDTM所接受的语言；NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言；NP=L|L是一个能在多项式时间内被一台DTM所

36、接受的语言；NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言；44. 记号O的定义正确的是（A）。O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 f(n) cg(n) ；O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) ；O(g(n) = f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 f(n)<cg(n) ；O(g(n) = f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 cg(n) < f(n) ；45. 记

37、号的定义正确的是（B）。O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 f(n) cg(n) ；O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) ；(g(n) = f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 f(n)<cg(n) ；(g(n) = f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 cg(n) < f(n) ；三、判断题1、VB表达式（A & B & C）的值一定是字符型数据。 &#

38、160;  对2、程序循环结构中的循环体语句将根据实际情况（条件）确定执行次数。    对3、程序通过编译可以有效发现程序的语法错误。    对4、在VB中，Int(100 * Rnd + 1)的取值范围是1100之间的所有整数（包括1和100）对5、运行程序时，程序中的所有语句都要运行一次或多次。    错6、算法有五大特征，其中包括输入和输出这两种，意思就是说一个算法必须要有输入，也必须要有输出。    错7、在

39、VB中，编写程序代码在代码编辑窗口中进行。代码由语句、常数和声明部分组成。    对8、VB的所有控件在程序运行以后都是可见的。    错9、在VB程序设计中，方法表示了对象的行为，即对象所能完成的某种操作。  对10、控件是应用程序的图形界面中显示可供用户操纵，并可控制应用程序的图形界面元素，是VB可视化编程的基本操作对象。   对11、如果知道一个三角形的两个角和一条边的值，可以用解析法设计程序求解该三角形的面积。   对12、在面

40、向对象程序设计中，类是对多个对象的抽象，因此，同一类的不同对象只能有不同的对象名，属性值则相同。    错13、列举一切与命题相关的情况，然后根据问题设定的条件，逐个加以检查，找到满足条件的解答的方法称为穷举法。    对14、递归算法就是一种直接或间接地调用自身的算法。    对15、对一个排好序的数组来说，要查找其中的一个元素，使用二分查找法查找速度最快。  错16、已知三角形的两边分别为a、b，它们的夹角为0.6弧度，在VB中可用公式(a * b *

41、 Sin(0.6) / 2)求出该三角形的面积。   对17、条件语句在执行过程中将由电脑随机选择执行哪部分语句。    错18、汇编语言实际是一种符号化的机器语言，它采用英文助记符代替机器指令，比机器语言容易识别和记忆，从而提高了程序的可读性。    对19、在一个循环语句的循环体中含有另一个循环语句，肯定出现死循环。    错20、算法就是用计算机语言编写的程序。    错21、用计算机解决某个问题的算法只有一种

42、。    错22、VB中的算术运算符*(乘)、/(除)、(整除)、Mod(取余数)的运算优先级相同。   错23、用高级语言编写的必须经过翻译器将其翻译成机器语言，才能在计算机上执行。  对24、所有的程序都是从程序中的第一条语句开始按顺序执行的。    错25、在VB程序设计中，对象的行为称为方法。    对26、如果程序经过编译未发现错误，那么程序的调试就完成了。    错27、算法是程序设计的核心，是

43、程序设计的灵魂。    对28、窗体是VB程序设计的基础，各种控件对象必须建立在窗体上，一个窗体对应一个窗体模块。    对29、在面向对象程序设计中，一个程序对象的属性用变量来表示，而对象的行为用对象中的代码段来实现。    对30、程序循环结构中的循环体语句至少会执行一次。    错31、在VB中，开发的每个应用程序都被称为工程，工程是组成一个应用程序的文件集合。    对32、凡是能够用解析

44、法求解的问题都可以通过定量分析，并能用解析表达式来描述。  对33、VB中的事件只能由用户引发。    错34、已知三角形的两边分别为a、b，它们的夹角为60度，在VB中可用公式(a * b * Sin(60) / 2)求出该三角形的面积。    错35、条件语句在执行过程中会根据逻辑表达式的值选择执行哪部分语句。    对36、对半查找的实质是在一个有限且有序的对象中，通过每次减缩一半查找范围而达到迅速确定目标的一个有效算法。   &

45、#160;对38、递归算法的实质是把问题转化为规模缩小了的同类问题的子问题，然后递归调用函数或过程来表示问题的解。   对39、在一个循环语句的循环体中含有另一个循环语句，就形成了嵌套循环。   对40、列举一切与命题相关的情况，然后根据问题设定的条件，逐个加以检查，找到满足条件的解答的方法称为解析法。   错四、综合题（50分）1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为ak(2<=k<=4)（5分）2、由流水作业调度问题的最优子结构性

46、质可知，T（N，0）=（5分）3、最大子段和问题的简单算法(10分)int maxsum(int n,int *a,int & bestj)intsum=0;for (int i=1;i<=n;i+)for (int j=i;j<=n;j+)int thissum=0;for(int k=i;k<=j;k+);if(thissum>sum)sum=thissum;；bestj=j; return sum;设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分)Void OptimalBinarysearchTree(int

47、 a,int n,int * * m, int * * w)for(int i=0;i<=n;i+) wi+1i=ai; mi+1i=;for(int r=0;r<n;r+)for(int i=1;i<=n-r;i+)int j=i+r;wij=wij-1+aj+bj;mij=;sij=i;for(int k=i+1;k<=j;k+)int t=mik-1+mk+1j;if() mij=t; sij=k;mij=t; sij=k;5、设n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用两种方法求4个作业的最

48、优调度方案并计算其最优值？（15分）五、简答题（30分）1、将所给定序列a1:n分为长度相等的两段a1:n/2和an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有哪三种情形？(10分)答： 2、由01背包问题的最优子结构性质，可以对m（i,j）建立怎样的递归式? (10分)3、01背包求最优值的步骤分为哪几步？（10分）七证明题1. 一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治

49、法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得T（n）的显式表达式为：试证明T（n）的显式表达式的正确性。2. 举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。证明：举例如：p=7,4,4,w=3,2,2,c=4时，由于7/3最大，若按题目要求的方法，只能取第一个，收益是7。而此实例的最大的收益应该是8，取第2，3 个。3. 求证：O(f(n)+O(g(n) = O(maxf(n),g(n) 。证明：对于任意f1(n) O(f(n) ，存

50、在正常数c1和自然数n1，使得对所有nn1，有f1(n) c1f(n) 。类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2，使得对所有nn2，有g1(n) c2g(n) 。令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。则对所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) = 2c3h(n) = O(maxf(n),g(n) .4. 求证最优装载问题具有贪心选择性质。（最优装载问题：有一批集装箱要装

51、上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。设集装箱已依其重量从小到大排序，(x1,x2,xn)是最优装载问题的一个最优解。又设 。如果给定的最优装载问题有解，则有。） 证明：六解答题机器调度问题。问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi，si<fi 。si，fi为处理任务i的时间范围。两个任务i，j重叠指两个任务的时间范围区间有重叠，而并非指i，j的起点或终点重合。例如：区间1，4与区间2，4重叠，而与4，7不重叠。一个可行的任务分配是指

52、在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。问题实例：若任务占用的时间范围是1，4，2，5，4，5，2，6，4，7，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）画出工作在对应的机器上的分配情况。2. 已知非齐次递归方程： ，其中，b、c是常数，g(n)是n的某一个函数。则f(n)的非递归表达式为：。现有Hanoi塔问题的递归方程为： ，求h(n)的非递归表达式。解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n递推到1，有：3. 单源最短路径的求解。问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代4. 请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且。装载问题要求确定是否有一个合理的装载