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

算法设计与分析试卷填空题（20分，每空2分）1.算法的性质包括输入、输出、＿＿＿、有限性。2.动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求解子问题，然后从这些子问题的解得到原问题的解。3.设计动态规划算法的4个步骤：4.找出＿＿＿＿，并刻画其结构特征。＿＿＿＿＿＿＿。＿＿＿＿＿＿＿。5.根据计算最优值得到的信息，＿＿＿＿＿＿＿。6.流水作业调度问题的johnson算法：令N1=＿＿＿,N2={i|ai=bj};将N1中作业依ai的＿＿＿。7.对于流水作业高度问题，必存在一个最优调度π，使得作业π（i）和π（i+1）满足Johnson不等式＿＿＿＿＿。8.最优二叉搜索树即是＿＿＿的二叉搜索树。9.下面程序段的所需要的计算时间为（2O(n)）。10,有11个待安排的活动，它们具有下表所示的开始时间与结束时间，intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i=n;i++){intthissum=0;for(intj=i;j=n;j++){thissum+=a[j];if(thissumsum){sum=thissum;besti=i;bestj=j;}}}returnsum;}如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（{1，4，8，11}）。11,所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。12,所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。13,回溯法是回溯法是指（具有限界函数的深度优先生成法）。14.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n))）。15.回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。16.用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。17.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。1413121110987654f[i]122886535031S[i]1110987654321i18.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：19.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为nm的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时(O(mn))，构造相应的最短距离需要（O(L)）时间。for(inti=0;iNumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//该方格未标记grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;TypepKnapTypew,Typep::Bound(inti){//计算上界Typewcleft=c-cw;//剩余容量Typepb=cp;//结点的上界//以物品单位重量价值递减序装入物品while(i=n&&w[i]=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i=n)（b+=p[i]/w[i]*cleft）;returnb;}20.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn））。21.旅行售货员问题的解空间树是（排列树）。BoolColor::OK(intk){//for(intj=1;j=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}二、单选题1、模块化程序设计方法主要通过()来实现。A.递归算法和递归程序B.过程和函数的定义和调用C.程序的循环结构D.对象答案:B2、text1.text的含义正确的是()。A.text1是控件名称，text是控件属性B.text1是窗体名称，text是控件C.text1是控件名称，text是方法D.text1是控件属性，text是控件答案:A3、以下程序段运行后S的值是()。s=0Fori=1To14x=2*i-1IfxMod3=0Thens=s+1NextiA.0B.4C.5D.14答案:C4、数列1，4，7，10，13，……的递推公式为()。A.f(1)=1;f(n)=n+3B.f(1)=1;f(n)=n*2-1C.f(1)=1;f(n)=n*2+1D.f(1)=1;f(n)=f(n-1)+3答案:D5、对于对象及其特征的错误理解是()。A.对象都具有一个标识自己以区别其他对象的名字。B.对象都具有自身的属性及其属性值。C.对象一般只用数据表示属性，但不用代码表示行为。D.对象都具有自身的行为(操作)。答案:C6、VB函数Left()从字串左端取部分字串，那么Left(VisualBasic6.0,8)的值为()。A.VisualBB.VisualC.VisualBaD.asic6.0答案:A7、程序段如下：c=1234Fori=1To4Print_____，Next如果要让程序运行后得到如下结果：1121231234则在下划线处应填入的内容为()。A.Right(c,i)B.Left(c,i)C.Mid(c,i,1)D.Mid(c,i,i)答案:B8、若X=True，执行IfXThenX=0ElseX=1后X的结果为()。A.TrueB.编译错误C.1D.0答案:D9、若x=False,y=True，执行IfxAndyThenx=0Elsex=1后X的结果为()。A.FalseB.1C.编译错误D.0答案:B10、以下程序段运行时语句k=k+1执行次数为()次。k=－20dowhile(k=0)k=k+1loopA.20B.无数次C.1D.0答案:D11、如果A=30，B=40,执行T=B:A=T:B=A语句后,A、B和T的值是()。A.30、40、30B.40、40、40C.30、30、30D.40、30、40答案:B12、用选择排序法对数据7，6，3，9，2从大到小排序，共需经过()次数据对调。A.3B.4C.5D.10答案:A13、采用模块化方法得到的系统是由()的模块构成的。A.没有连接B.函数C.互相连接D.过程答案:C14、(1.5分)下列程序段运行后X的值是()。x=0Fori=1To5Forj=iTo3x=x+1NextjNextiA.0B.5C.6D.15答案:C15、要从n个数据元素中顺序查找一个元素，最多查找次数是()。A.1B.nC.n/2D.lgn答案:B16、对半查找算法的前提是()。A.被查找数据元素个数是奇数B.被查找数据元素个数是偶数C.被查找数据元素是有序的D.被查找数据元素是无序的答案:C17、用折半查找法从数列3，6，7，10，12，16，25，30，75中找到数据10的最少查找次数是()。A.2B.3C.4D.7答案:B18、对象的特征称为()，我们可以把()看作对象的响应，把()看作对象的动作。A.属性，事件，方法B.属性，方法，事件C.方法，事件，属性D.方法，属性，事件答案:A19、设置一个控件在窗体上的位置可修改控件的()属性。A.Width、HeightB.Visible、EnabledC.Top、LeftD.Style答案:C20、算法与程序的关系()。A.算法是对程序的描述B.算法决定程序，是程序设计的核心C.算法与程序之间无关系D.程序决定算法，是算法设计的核心答案:B21、当a=5,b=7,c=-2,d=1时，下列结果为False的是()。A.a+b＞c+dAnda＞=5OrNotc＞0Ord＜0B.c+d＞a+bAnda＞=5OrNotc＞0Ord＞0C.a+b＞c+dAnda＜5OrNotc＞0Ord＜0D.a+d＜b+cAnda＞=5OrNotc＜0Ord＜0答案:D22、在流程图中表示算法中的条件判断时使用()图形框。A.菱形框B.矩形框C.圆形框D.平行四边形框答案:A23、VB语言中，下列各种基本数据类型说明符中表示单精度实型数的是()。A.IntegerB.BooleanC.SingleD.String答案:C24、程序的基本结构有顺序结构、()和循环结构。A.逻辑结构B.选择结构C.模块结构D.层次结构答案:B25、一个算法应该具备几个方面的基本特征，下面不属于算法基本特征的是()。A.输入输出B.有穷性C.确定性D.执行性答案:D26、人们利用计算机解决问题的基本过程一般有如下四个步骤（①～④），请按各步骤的先后顺序在下列选项中选择正确的答案()。①调试程序②分析问题③设计算法④编写程序A.①②③④B.②③④①C.③②④①D.②③①④答案:B27、以下哪个是合法的变量名()。A.sqrB.2paiC.cj1D.a+b答案:C28、VB中保存工程文件的文件扩展名为()。A.vbpB.frmC.docD.pas答案:A29、VB表达式5+2*12Mod8的值是()。A.13B.5C.28D.8答案:B30、由二进制编码指令组表示程序的程序设计语言是()。A.自然语言B.机器语言C.汇编语言D.高级语言答案:B31.应用Johnson法则的流水作业调度采用的算法是（D）A.贪心算法B.分支限界法C.分治法D.动态规划算法32.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）Hanoi塔A.voidhanoi(intn,intA,intC,intB){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}B.voidhanoi(intn,intA,intB,intC){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}C.voidhanoi(intn,intC,intB,intA){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}D.voidhanoi(intn,intC,intA,intB){if(n0){hanoi(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.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))36.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用37.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A.广度优先B.活结点优先C.扩展结点优先D.深度优先38.分支限界法在问题的解空间树