2024年算法分析与设计期末考试试卷B卷.docx
中科Bv«H*SvBB«H»-A1.««Aiv*HAHV»*BIBHVABVBvBveHa*Bv«>Bva三B«»BBBBVftvBB*BB«*Sv«I>郛H熊甯««)?摞籍«筮层热甯«题号三四五总成果得分西南交通高校2024-2024学年第（一）学期考试试卷课程代码3244152课程名称算法分析与设计考试时间120分*阅卷老师签字：填空题（每空1分，共15分）1、 程序是1.U用某种程序设计语言的详细实现。2、 矩阵连乘问题的第法可由（2）设计实现.3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是（3）.4、 大整数乘积算法是用（4）来设计的。5、 5心算法总是做出在当前看来（5）的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的（6）。6、 回溯法是一种既带有又带有的搜寻算法.7、 平衡二叉树对于杳找算法而言是一种变治策略，屈于变治思想中的（9）类型。8、 在忽视常数因了的状况下，0、C和。三个符号中，（10）供应了算法运行时间的一个上界.9、 算法的“确定性”指的是组成鸵法的每条（ID是消整的,无歧义的。10、问题的（12）是该问题可用动态规划算法或贪心算法求解的关键特征。11、 算法就是一组有穷3）,它们规定了解决某一特定类型问题的（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,贪心法【）、回溯法6、 回溯法的效率不依靠于下列哪些因素（）A.满意显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间7、 运用分治法求解不须要满意的条件是（A、了问题必需是一样的C,子问返的解可以合并8、实现合并排序利用的修法是（A,分治策略B、动态规划法Bx子问题不能够揖匆【）、原间网和子问网运用相同的方法解）.C、贪心法I）、回测法9、 背包问题的贪心兑法所需的计兑时间为（）A、0（n2,）B、0（n1.ogn）C、0（2,）D、0（n）10、 广度优先是（）的一搜寻方式。A、分支界限法B、动态规划法C、贪心怯D、回溯法三、算法及程序分析（共25分）。1 .阅读卜.面的程序，按要求回答问题：(共10分)*inc1.ude<stdio.h>inc1.ude<string.h>inivis1011.01);intmap101101：intR1C:intdp(inti,intj)；intmain()(inti1j,ans,max：SCanf(飞d,&R,&C)：for(i=0;i<R：i+)for(j=0J<CJ+)scanf(,¾<,ft三pij):max=0：for(i=0：i<R：i+)memset(visi,-1,sizeof(visi);for(j=0J<CJ+)ans=dp(i,j);if(ans>max)max=ans：Printf("dn”,max)：return0;intdp(inti,intj)intmax=0;if(visij>0)returnvisij;if(i-1.>=0)if(mapi-1.,<mapij)if(max<dp(i-1.,.i)max-dp(>-1.j)；if(i+1.<R)if(mapi+1.j<mapiJ)if(max<dp(i+1.,.i)max=dp(i+1.,j);if(j-1.>=O)if(mapi.i-1.<mapij)if(max<dp(i,j-1.)max=dp(,j-1.);if(j+i<C)i(napij+1.<mapij)if(max<dp(i,j+1.)max=dp(i,j+1.);returnvisij=max+1;)(1)该程序采纳什么算法？(2分)(2)设R=5,C=5,map的值如下所示时程序执行结束之后max的值是多少？(共5分)(2)上述程序的时间困难度是多少？(共3分)2 .阅读卜面的程序，按要求回答问题。(共15分)typedofstructSq1.ist(int*r;int1.ength：)Sq1.ist;voidHeapSort(Sq1.ist*H)Iinii;intrc：for(i=H->gth2:i>0:-i)HeapAdjust(H,i,H->1.ength);for(i=H->1.ength;i>1.：i)rc=H->r1.：H->r1.=H->ri:H->ri=rc;HeapAdjust(H,1,i-1.);)return;)voidHeapAdjust(Sq1.ist*H,ints,intm)(intrc,nn：intj;rc=H->rs:for(j=2*s：j<=m：j*=2)if(j<m&&H->rj<H->rj+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)设传递给函数VOidHeapAdjust(Sq1.ist*H,ints,intm)的参数如下:H->1.ength:8H->r:15,18,16,32,14,45,78,30,43)S=Im=8请问程序函数执行后H->r的值.(共5分)(3)该程序的时间困难度是多少，写出求解过程。(共8分)四、算法描述题（共20分）。1、已知某仓库有若干件商品，每件商品的重量为Wi,价值为Yi°某货车能装载的最大重量为肌清将仓库中的部分商品装载到货车中，使其总价值最大。要求每件商品只能装载1件，且全部货物的总重量不能超过货车的总装载很。（1）用文字描述采纳动态规划算法求解上述问题的步骤。（6分）（2）用文字描述采纳回溯法求解上述问题的步豚。（6分）（3）若仓库中有8件商品，货车能装载的最大重量为5000公斤，每件商品的重责及价值如卜表所示，请用图的形式描述采纳分支限界法求解该问题时堆的变更过程。（共8分）商品编号12345678商品重量（公斤）100O80015001000600WO20003200商品价值（元）200016003200280018008003200100O五、算法设计及实现（共20分）1、设某校最多有200门可选课程，而每个学生每学期最多可以选2门课程。在期末考试时,每天考试可支配在上午1次,下午1次，请编写程序求全部学生考试完所选课程须要支配的最少的考试次数。（共20分）输入：输入的第一行包含两个整数n和m.n表示可选课程的教量，m表示学生的人数。下面的m行，每行有两个整数，分别表示每个学生所选的两门课程的编号.比如：451 22 33 44 45 4输出：输出1行，即全部学生考试完所选谡程所须要的最少考试次数。
