武科大算法设计与分析考试试卷

《武科大算法设计与分析考试试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机09级算法设计与分析期末考试试卷试题2011年~2012年第2学期课程名称：算法设计与分析专业年级：2009级计算机考生学号：考生姓名：试卷类型：A卷■B卷□考试方式:开卷□闭卷▋………………………………………………………………………………………………………一.选择题（每题2分，共20分）1.算法的控制结构有3种，分别是顺序结构、选择结构和（）。A.队列结构B.二叉树结构C.循环结构D.数据结构2.显式图在搜索算法中用的比较多，显式图常见搜索策略有广度优先搜索和（）两种。A.深度优先搜索B.回溯法C.分支限界法D.穷举法.3.算

2、法可以用4种质量指标衡量，分别是正确性、可读性、（）、高效率性及低存储性。A.目的性B.稳健性C.操作性D.有序性.4.回溯法在解空间树T上的搜索方式是（）　　A．深度优先B．广度优先　　C．最小耗费优先D．活结点优先5．用计算机程序解决实际问题的过程中，需要进行算法设计，算法指的是（）A、最终结果B、数值计算的方法C、实际问题的描述D、解决问题的方法和步骤6.如果一个问题存在多项式时间的算法，则可称之为P类问题；如果至今没有找到多项式时间算法解，则可称之为NP问题，下列哪种时间复杂度问题属于P类问题。A.O(n3)B.O(2n)C.

3、O（n!）D.O(4n)7.下述算法时间复杂度为（）x=0；y=0；for(k=1；k<=n；k++)x++；for(i=1；i<=n；i++)for(j=1；j<=n；j++)y++；A.O(n)B.O(n2)C.O(n3)D.O(2n)8．迭代算法有两种方法，分别是递推法和（）.A.循环法B.递归法.C.倒推法D.动态规划法9.流程图是描述算法的常用工具，下列哪种组件表示条件选择().注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型

4、、考试方式后打勾注明。（第4页）计算机09级算法设计与分析期末考试试卷A.B.C.D.10.下了哪种有关贪心算法描述是不正确（）.A.贪心算法可用于求解最优解问题。B.所求解全局最优.C.能够用很快的方式求取问题的一个解。D.贪心算法一般要求问题具有无后向性。二.简答题（每个6分，6*4=24分）1.简述用递归算法解题的步骤2.简述分治法基本思想，使用分治法的条件？3.什么是活结点,E结点和死结点？4.如果问题算法可以抽象为T(n)=2T(n/2)+1，则它的时间复杂度是多少?（设n=2k,写出推导过程）三、把下列程序或者算法填写完整

5、（2*10=20分）注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第4页）计算机09级算法设计与分析期末考试试卷1．利用分支法求含有16个数据的数组中最大的两个数。#defineM16#includeinta[M]={-8,3,6,0,1,7,8,20,,40,16,24,10,18,32,50,28};voidmaxtwo(inti,intj,int*max1,int*max2){intlm

6、ax1,lmax2,rmax1,rmax2;intmid;if(i==j){*max1=a[i];*max2=a[i];}elseif(i==（1）){if(a[i]rmax1){注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题

7、册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第4页）计算机09级算法设计与分析期末考试试卷*max1=lmax1;if(（4）)*max2=lmax2;else*max2=rmax1;}else{*max1=（5）;if(rmax2>lmax1)*max2=rmax2;else*max2=lmax1;}}}voidmain(){intmax1,max2;maxtwo(0,M-1,&max1,&max2);printf("max1=%d,max2=%d",max1,max2);}2．

8、A,B,C,D,E5人为某次竞赛的前五名，他们在名次公布前猜名次。A说：B得第三名，C得第五名。B说：D得第二名，E得第四名。C说：B得第一名，E得第四名。D说：C得第一名，B得第二名。E说：D得第二名，A得第三名。结果