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

班 级 学 号 姓 名 密封装订线 密封装订线 密封装订线西南交通大学20152016学年第(一)学期考试试卷课程代码 课程名称 算法分析与设计 考试时间 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最优子结构性质与重叠子问题性质 4、 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分） #include #include int vis101101; int map101101;int R,C;int dp(int i,int j)；int main() int i,j,ans,max; scanf(%d%d,&R,&C); for(i=0;iR;i+) for(j=0;jC;j+) scanf(%d,&mapij); max = 0; for(i=0;iR;i+) memset(visi,-1,sizeof(visi); for(j=0;jmax) max = ans; printf(%dn,max); return 0;int dp(int i,int j) int max = 0;if(visij0) return visij;if(i-1=0) if(mapi-1jmapij) if(maxdp(i-1,j) max = dp(i-1,j); if(i+1R) if(mapi+1jmapij) if(max=0) if(mapij-1mapij) if(maxdp(i,j-1) max = dp(i,j-1); if(j+1C) if(mapij+1mapij) if(maxLength/2;i0;-i) HeapAdjust(H,i,H-Length);for(i=H-Length;i1;-i) rc=H-r1; H-r1=H-ri; H-ri=rc; HeapAdjust(H,1,i-1); return;void HeapAdjust(SqList *H,int s, int m) int rc,rm; int j; rc=H-rs;for(j=2*s;j=m;j*=2) if(jrjrj+1) +j; if(rc=H-rj) break; rm=H-rs; H-rs=H-rj; H-rj=rm; s=j; H-rs=rc; return;（1） 该程序采用什么算法? （2分）（2） 设传递给函数void HeapAdjust(SqList *H,int s, int m)的参数如下：H-Length: 8H-r: 15, 18,16,32,14,45,78,30,43s=1m=8请问程序函数执行后H-r的值。 （共5分） （3）该程序的时间复杂度是多少，写出求解过程。（共8分）四、 算法描述题（共20分）。1、已知某仓库有若干件商品，每件商品的重量为Wi,价值为Vi。某货车能装载的最大重量为W，请将仓库中的部分商品装载到货车中，使其总价值最大。要求每件商品只能装载1件，且所有货物的总重量不能超过货车的总装载量。（1）用文字描述采用动态规划算法求解上述问题的步骤。（6分）（2）用文字描述采用回溯法求解上述问题的步骤。（6分）（3）若仓库中有8件商品，货车能装载的最大重量为5000公斤，每件商品的重量及价值如下表所示，请用图的形式描述采用分支限界法求解该问题时堆的变化过程。（共8分）商品编号12345678商品重量（公斤）1000800 1500 4000 600 4002000 3200商品价值（元）2000160032002800180080032004000五、 算法设计及实现(共20分) 1、设某校最多有200门可选课程，而每个学生每学期最多可以选2门课程。在期末考试时，每天考试可安排在上午1次，下午1次，请编写程序求所有学生考试完所选课程需要安排的