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

《算法设计与分析试卷计本3班》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析试卷填空题（20分，每空2分）1.算法的性质包括输入、输出、＿＿＿、有限性。2.动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求解子问题，然后从这些子问题的解得到原问题的解。3.设计动态规划算法的4个步骤：4.找出＿＿＿＿，并刻画其结构特征。＿＿＿＿＿＿＿。＿＿＿＿＿＿＿。5.根据计算最优值得到的信息，＿＿＿＿＿＿＿。6.流水作业调度问题的johnson算法：令N1=＿＿＿,N2={i

2、ai>=bj};将N1中作业依ai的＿＿＿。7.对于流水作业高度问题，必存在一个最优调度π，使得作业π（i）和π（i+1）满足Johnson不等式＿＿＿＿＿。8.最优二叉搜索树即是＿＿＿

3、的二叉搜索树。9.下面程序段的所需要的计算时间为（）。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(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}10,有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容

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

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

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

7、.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成布线Q.Add(nbr);}}20.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn））。BoolColor::OK(intk){//for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}21.旅行售货员问题的解空间

8、树是（排列树）。二、单选题1、模块化程序设计方法主要通过()来实现。    A.递归算法和递归程序    B.过程和函数的定义和调用C.程序的循环结构    D.对象          答案:B 2、text1.text的含义正确的是()。    A.text1是控件名称，text是控件属性    B.text1是窗体名称，text是控件C.text1是控件名称，text是方法    D.text1是控件属性，text是控件    答案:A 3