2015年算法分析与设计期末考试试卷B卷

西南交通大学2015－2016学年第(一)学期考试试卷课程代码3244152课程名称算法分析与设计考试时间120分钟题号一二三四五总成绩得分·阅卷教师签字：一、填空题（每空1分，共15分）1、程序是（1）用某种程序设计语言的具体实现。2、矩阵连乘问题的算法可由（2）设计实现。3、从分治法的一般设计模式可以看出，用它设计出的程序一般是（3）。4、大整数乘积算法是用（4）来设计的。5、贪心算法总是做出在当前看来（5）的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的（6）。6、回溯法是一种既带有（7）又带有（8）的搜索算法。7、平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的（9）类型。8、在忽略常数因子的情况下，O、和三个符号中，（10）提供了算法运行时间的一个上界。9、算法的“确定性”指的是组成算法的每条(11)是清晰的，无歧义的。10、问题的(12)是该问题可用动态规划算法或贪心算法求解的关键特征。11、算法就是一组有穷(13)，它们规定了解决某一特定类型问题的(14)。12、变治思想有三种主要的类型：实例化简，改变表现，(15)。二、选择题（每题2分，共20分）1、二分搜索算法是利用（）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法2、衡量一个算法好坏的标准是（）。A、运行速度快B、占用空间少C、时间复杂度低D、代码短3、能采用贪心算法求最优解的问题，一般具有的重要性质为：（）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用4、常见的两种分支限界法为（）班级学号姓名密封装订线密封装订线密封装订线A、广度优先分支限界法与深度优先分支限界法；B、队列式（FIFO）分支限界法与堆栈式分支限界法；C、排列树法与子集树法；D、队列式（FIFO）分支限界法与优先队列式分支限界法；5、实现循环赛日程表利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法6、回溯法的效率不依赖于下列哪些因素（）A.满足显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间7、使用分治法求解不需要满足的条件是（）。A、子问题必须是一样的B、子问题不能够重复C、子问题的解可以合并D、原问题和子问题使用相同的方法解8、实现合并排序利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法9、背包问题的贪心算法所需的计算时间为（）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）10、广度优先是（）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法三、算法及程序分析（共25分）。1．阅读下面的程序，按要求回答问题：（共10分）#includestdio.h#includestring.hintvis[101][101];intmap[101][101];intR,C;intdp(inti,intj)；intmain(){inti,j,ans,max;scanf(%d%d,&R,&C);for(i=0;iR;i++)for(j=0;jC;j++)scanf(%d,&map[i][j]);max=0;for(i=0;iR;i++){memset(vis[i],-1,sizeof(vis[i]));for(j=0;jC;j++){ans=dp(i,j);if(ansmax)max=ans;}}printf(%d\n,max);return0;}intdp(inti,intj){intmax=0;if(vis[i][j]0)returnvis[i][j];if(i-1=0)if(map[i-1][j]map[i][j])if(maxdp(i-1,j))max=dp(i-1,j);if(i+1R)if(map[i+1][j]map[i][j])if(maxdp(i+1,j))max=dp(i+1,j);if(j-1=0)if(map[i][j-1]map[i][j])if(maxdp(i,j-1))max=dp(i,j-1);if(j+1C)if(map[i][j+1]map[i][j])if(maxdp(i,j+1))max=dp(i,j+1);returnvis[i][j]=max+1;}（1）该程序采用什么算法？（2分）（2）设R=5,C=5,map的值如下所示时程序执行结束之后max的值是多少？（共5分）[123106530151245720131411252320141816151930]（2）上述程序的时间复杂度是多少？（共3分）2．阅读下面的程序，按要求回答问题。（共15分）typedefstructSqList{int*r;intLength;}SqList;voidHeapSort(SqList*H){inti;intrc;for(i=H-Length/2;i0;--i)HeapAdjust(H,i,H-Length);for(i=H-Length;i1;--i){rc=H-r[1];H-r[1]=H-r[i];H-r[i]=rc;HeapAdjust(H,1,i-1);}return;}voidHeapAdjust(SqList*H,ints,intm){intrc,rm;intj;rc=H-r[s];for(j=2*s;j=m;j*=2){if(jm&&H-r[j]H-r[j+1])++j;if(rc=H-r[j])break;rm=H-r[s];H-r[s]=H-r[j];H-r[j]=rm;s=j;}H-r[s]=rc;return;}（1）该程序采用什么算法?（2分）（2）设传递给函数voidHeapAdjust(SqList*H,ints,intm)的参数如下：H-Length:8H-r:{15,18,16,32,14,45,78,30,43}s=1m=8请问程序函数执行后H-r的值。（共5分）（3）该程序的时间复杂度是多少，写出求解过程。（共8分）四、算法描述题（共20分）。1、已知某仓库有若干件商品，每件商品的重量为Wi,价值为Vi。某货车能装载的最大重量为W，请将仓库中的部分商品装载到货车中，使其总价值最大。要求每件商品只能装载1件，且所有货物的总重量不能超过货车的总装载量。（1）用文字描述采用动态规划算法求解上述问题的步骤。（6分）（2）用文字描述采用回溯法求解上述问题的步骤。（6分）（3）若仓库中有8件商品，货车能装载的最大重量为5000公斤，每件商品的重量及价值如下表所示，请用图的形式描述采用分支限界法求解该问题时堆的变化过程。（共8分）商品编号12345678商品重量（公斤）10008001500400060040020003200商品价值（元）2000160032002800180080032004000五、算法设计及实现(共20分)1、设某校最多有200门可选课程，而每个学生每学期最多可以选2门课程。在期末考试时，每天考试可安排在上午1次，下午1次，请编写程序求所有学生考试完所选课程需要安排的最少的考试次数。（共20分）输入：输入的第一行包含两个整数n和m，n表示可选课程的数量，m表示学生的人数。下面的m行，每行有两个整数，分别表示每个学生所选的两门课程的编号。比如：451223341424输出：输出1行，即所有学生考试完所选课程所需要的最少考试次数。