还剩3页未读,继续阅读
文本内容:
西南交通高校2023-2023学年第(-)学期考试试卷课程代码3244152课程名称算法分析与设计考试时间120分钟阅卷老师签字、填空题(每空1分,共15分)程序是(序用某种程序设计语言的详细实现矩阵连乘问题的算法可由
(2)设计实现从分治法的一般设计模式可以看出,用它设计出的程序一般是(模大整数乘积算法是用(是来设计的贪心算法总是做出在当前看来
(5)的选择也就是说贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的
(6)o回溯法是一种既带有⑺又带有
(8)的搜寻算法平衡二叉树对于查找算法而言是一种变治策略,属于变治思想中的
(9)类型在忽视常数因子的状况下,
0、和三个符号中,
(10)供应了算法运行时间的一个上界算法的“确定性”指的是组成算法的每条
(11)是清楚的无歧义的问题的」a是该问题可用动态规划算法或贪心算法求解的关键特征算法就是一组有穷
(13)它们规定了解决某一特定类型问题的
(14)变治思想有三种主要的类型实例化简,变更表现,
(15)、选择题(每题2分,共20分)二分搜寻算法是利用()实现的算法A、分治策略B、动态规划法C、贪心法D、回溯法衡量一个算法好坏的标准是()oA、运行速度快B、占用空间少C、时间困难度低D、代码短能采纳贪心算法求最优解的问题,一般具有的重要性质为()A.最优子结构性质与贪心选择性质B.重叠子问题性质与贪心选择性质C.最优子结构性质与重叠子问题性质D.预排序与递归调用常见的两种分支限界法为()A、广度优先分支限界法与深度优先分支限界法;B、队列式FIFO分支限界法与堆栈式分支限界法;C、排列树法与子集树法;D、队列式FIFO分支限界法与优先队列式分支限界法;实现循环赛日程表利用的算法是A、分治策略B、动态规划法C、贪心法D、回溯法回溯法的效率不依靠于下列哪些因素A.满意显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间运用分治法求解不须要满意的条件是0A、子问题必需是一样的B、子问题不能够重复C、子问题的解可以合并D、原问题和子问题运用相同的方法解实现合并排序利用的算法是A、分治策略B、动态规划法C、贪心法D、回溯法背包问题的贪心算法所需的计算时间为A、0n2nB、0nlognC、02nD、0n广度优先是的一搜寻方式A、分支界限法B、动态规划法C、贪心法D、回溯法
三、算法及程序分析共25分.阅读下面的程序,按要求回答问题共10分ttincludestdio.h^includestring.hintvis
[101]
[101];intmap
[101]
[101];intRC;intdpintiintj;intmainintijansmax;scanfzz%d%dz/RC;fori=0;iR;i++forj=0;jC;j++scanf〃%d〃,map[i][j];max=0;fori=0;iR;i++{memsetvis[i]-1sizeofvis[i];forj=0;jC;j++{ans=dpij;ifansmaxmax=ans;}printfmax;return0;intdpintiintjintmax=0;ifvis[i][j]0returnvis[i][j];ifi-l=0ifmap[i-l][j]map[i][j]ifmaxdpi-ljmax=dpi-lj;if]+lRifmap[i+l][j]map[i]Lj]ifmaxdpi+1jmax=dpi+lj;ifj-l=0ifmap[i][j-1]map[i][j]ifmaxdpij-lmax=dpij-1;ifj+KCifmap[i][j+l]map[i][j]ifmaxdpij+1max=dpij+1;returnvis[i][j]=max+1;}1该程序采纳什么算法?2分2设R=5C=5map的值如下所示时程序执行结束之后max的值是多少?共5分2上述程序的时间困难度是多少?共3分.阅读下面的程序,按要求回答问题共15分typedefstructSqList{int*r;intLength;}SqList;voidHeapSortSqList*Hinti;intrc;fori=H-Length/2;i0;--iHeapAdjustHiH-Length;fori=H-Length;il;--i{rc=H-r
[1];H-r[l]=H-r[i];H-r[i]=rc;HeapAdjustH1i-l;return;voidHeapAdjustSqList*Hintsintmintrcrm;intj;rc=H-r[s];forj=2*s;j=m;j*=2{ifjmH-r[j]H-r[j+l]++j;ifrc=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设传递给函数voidHeapAdjustSqList*Hintsintm的参数如下:H-Length:8H-r:{151816321445783043}s=lm=8请问程序函数执行后H-〉r的佰共5分3该程序的时间困难度是多少,写出求解过程共8分
四、算法描述题(共20分)
1、已知某仓库有若干件商品,每件商品的重量为听价值为Vi某货车能装载的最大重量为W请将仓库中的部分商品装载到货车中,使其总价值最大要求每件商品只能装载1件,且全部货物的总重量不能超过货车的总装载量
(1)用文字描述采纳动态规划算法求解上述问题的步骤(6分)
(2)用文字描述采纳回溯法求解上述问题的步骤(6分)
(3)若仓库中有8件商品,货车能装载的最大重量为5000公斤,每件商品的重量及价值如下表所示,请用图的形式描述采纳分支限界法求解该问题时堆的变更过程(共8分)
五、算法设计及实现(共20分)
1、设某校最多有200门可选课程,而每个学生每学期最多可以选2门课程在期末考试时每天考试可支配在上午1次,下午1次,请编写程序求全部学生考试完所选课程须要支配的最少的考试次数(共20分)输入输入的第一行包含两个整数n和mn表示可选课程的数量,m表示学生的人数下面的m行,每行有两个整数,分别表示每个学生所选的两门课程的编号比如4523444输出输出1行,即全部学生考试完所选课程所须要的最少考试次数题号■1—四五总成果得分*商品编号12345678商品重量(公斤)10008001500400060040020003200商品价值(元)2000160032002800180080032004000。