2009级算法设计与分析试题A

计算机09级算法设计与分析期末考试试卷注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第1页）试题2011年~2012年第2学期课程名称：算法设计与分析专业年级：2009级计算机考生学号：考生姓名：试卷类型：A卷■B卷□考试方式:开卷□闭卷▋………………………………………………………………………………………………………一.选择题（每题2分，共20分）1.算法的控制结构有3种，分别是顺序结构、选择结构和（）。A.队列结构B.二叉树结构C.循环结构D.数据结构2.显式图在搜索算法中用的比较多，显式图常见搜索策略有广度优先搜索和（）两种。A.深度优先搜索B.回溯法C.分支限界法D.穷举法.3.算法可以用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.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.流程图是描述算法的常用工具，下列哪种组件表示条件选择().计算机09级算法设计与分析期末考试试卷注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第2页）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,写出推导过程）三、把下列程序或者算法填写完整（2*10=20分）1．利用分支法求含有16个数据的数组中最大的两个数。#defineM16#includestdio.hinta[M]={-8,3,6,0,1,7,8,20,,40,16,24,10,18,32,50,28};voidmaxtwo(inti,intj,int*max1,int*max2){intlmax1,lmax2,rmax1,rmax2;intmid;if(i==j){*max1=a[i];*max2=a[i];}elseif(i==（1）){if(a[i]a[j]){*max1=a[j];*max2=a[i];}else{*max1=a[i];*max2=a[j];}}else{mid=（2）;maxtwo(i,mid,&lmax1,&lmax2);maxtwo(mid+1,（3）,&rmax1,&rmax2);if(lmax1rmax1){计算机09级算法设计与分析期末考试试卷注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第3页）*max1=lmax1;if(（4）)*max2=lmax2;else*max2=rmax1;}else{*max1=（5）;if(rmax2lmax1)*max2=rmax2;else*max2=lmax1;}}}voidmain(){intmax1,max2;maxtwo(0,M-1,&max1,&max2);printf(max1=%d,max2=%d\n,max1,max2);}2．A,B,C,D,E5人为某次竞赛的前五名，他们在名次公布前猜名次。A说：B得第三名，C得第五名。B说：D得第二名，E得第四名。C说：B得第一名，E得第四名。D说：C得第一名，B得第二名。E说：D得第二名，A得第三名。结果每人都猜对了一半，填充下列算法求取名次。#includestdio.hmain(){inta,b,c,d,e;for(a=1;a=5;a=a+1)for(b=1;b=5;b=b+1)if(a!=b)for(c=1;（6）;c=c+1)if(b!=a&&c!=a)for(d=1;d=5;d=d+1)if(d!=a&&（7）&&d!=c)for(e=1;e=5;e=e+1){e=（8）;if(e!=a&&e!=b&&e!=c&&e!=d)if(((b==3)+(c==5))==1&&（9）&&((b==1)+(e==4))==1&&((c==1)+(b==2))==1&&((d==2)+(a==3))==（10）)计算机09级算法设计与分析期末考试试卷注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第4页）printf(“a,b,c,d,e=%d,%d,%d,%d”,a,b,c,d,e);}四．算法设计与编程（18+18=36分，对于每个问题，先分析算法策略，提出解决办法的基本思路,，然后用C语言编程实现）1.八皇后问题：要在8*8的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。下图为一种方案，求所有的解。2．某工业生产部门根据国家计划的安排，拟将某种高效率的5台机器，分配给A，B，C三个工厂，各工厂在获得这种机器后，可以为国家盈利如下表所示。请编程找出一种5台机器的分配方式，使得这5台机器盈利最大。012345A0万3万7万9万12万13万B0万5万8万10万11万12万C0万4万6万11万12万12万台数工厂