武科大算法设计与分析试卷A及答案(2008级).doc

（附 5 页 ） 试题纸（A卷） 课程名称： 算法设计与分析 适用专业年级： 2008级计算机、电本 考生学号： 考 生 姓 名： 题号一二三四总分分数一、 填空题（10空2分，共20分）1、 算法在运行时占有的机器资源的量称为算法复杂性，主要包括（ ）和（ ）。2、 当一个算法的运行时间为n2+n+1时，由于n2+n+1与n2的数量级相等，则称n2为这个算法的（ ）。3、 多项式A(n)=amnm+ a2n2+ a1n+ a0的上界为（ ）。4、 递归算法设计的关键在于找出（ ）和（ ）。5、 （ ）是问题能用贪婪算法或动态规划方法求解的前提。6、 拆半查找、合并排序、二叉树遍历等算法中均采用了（ ）策略。7、 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种（ ）的思想作为其控制结构。8、 用分支限界法解决布线问题时，对问题解空间搜索尝试结束的标志是（ ）。二、 判断题（10题2分，共20分）1. 若c是正常数，则O(cf(n)=O(f(n)。2. 在最好情况下、最坏情况下、平均情况下的时间复杂度中，可操作性最好的且最有实际价值的，是平均情况下的时间复杂度。3. 所有的递归函数都能找到对应的非递归定义。4. 好的算法在很大程度上取决于问题中数据所采用的数据结构。5. 迭代模型是通过小规模问题的解逐步求解大规模问题的解，正好与递归算法设计相反。6. 用贪婪算法解决零钱兑换问题时，总能找到问题的最优解。7. 适用动态规划算法解决问题应该具有最优化原理和子问题重叠。8. 深度优先搜索算法可以搜索到问题所有可能的解方案。9. 解决马的遍历问题采用回溯法，对解空间树的搜索采用广度优先搜索方式10. 分支限界法的求解目标是找出满足约束条件的一个解或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解。三、 简答题（3题6分，共18分）1、叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。2、在算法设计的实际应用中，遇到的问题主要分为4类：判定性问题、计算问题、最优化问题和构造性问题，请指出递归法、递推法、贪婪算法、分治法、动态规划法、搜索算法各自适合解决的问题。3、简述回溯法求解问题的一般步骤。四、 程序填空题（6空3分，共18分）1、 找出n个自然数(1，2，3，n)中取r个数的组合。例如，当n=4,r=3时，所有的组合为：4 3 2 4 3 14 2 13 2 1以下是算法，请填空。void comb(int n,int r) int i,j; for(i=n; ; i-) ;if(r1) ;else for(j=a0; j0; j-) printf(%3d,aj); printf(n); 2、 走迷宫问题。迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（用 “1”表示）有的是路（用“0”表示）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)，出口是右下角(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。 数据结构：数组maze88存放迷宫；用数组fx4=1,-1,0,0,fy4=0,0,-1,1模拟上下左右搜索时的下标的变化过程；用迷宫原有的存储空间置元素值为“-1”时，标识已经访问过该方格。用数组做队的存储空间，队中的成员有三个：行号、列号、前一个方格在队列中的下标。struct int x,y,presq100;search() qh=0; qe=1; maze11= ; sq1.pre=0; sq1.x=1; sq1.y=1; while( ) qh=qh+1; for(k=1;k=rar=icomb(i-1,r-1)2-1qhqeqe=qe+1五、 算法设计题（2题12分，共24分）1、main( ) long b,c,d; int a256,i,j,n;char s1256;input(s1,c);n=strlen(s1);d=0;for(i=0,j=n-1;i=0;i-) print(ai); 2、main( ) int a50503,i,j,n; print( please input the number of rows:); input(n);for(i=1;i=n;i+) for(j=1;j=1;i-) for(j=1;j=i ;j+)if(ai+1j2ai+1j+12) aij2=aij2+ai+1j2; aij3=0; else aij2=aij2+ai+1j+12; aij3=1; print(“max=“,a112);j=1;for(i=1;i); j=j+aij3; print(anj1); 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。