2024年算法分析与设计期末考试试卷B卷.docx

《2024年算法分析与设计期末考试试卷B卷.docx》由会员分享，可在线阅读，更多相关《2024年算法分析与设计期末考试试卷B卷.docx（5页珍藏版）》请在优知文库上搜索。

1、中科BvH*SvBBH-A1.Aiv*HAHV*BIBHVABVBvBveHa*BvBva三BBBBBVftvBB*BB*SvI郛H熊甯)?摞籍筮层热甯题号三四五总成果得分西南交通高校2024-2024学年第（一）学期考试试卷课程代码3244152课程名称算法分析与设计考试时间120分*阅卷老师签字：填空题（每空1分，共15分）1、 程序是1.U用某种程序设计语言的详细实现。2、 矩阵连乘问题的第法可由（2）设计实现.3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是（3）.4、 大整数乘积算法是用（4）来设计的。5、 5心算法总是做出在当前看来（5）的选择。也就是说贪心算法并不从整

2、体最优考虑，它所做出的选择只是在某种意义上的（6）。6、 回溯法是一种既带有又带有的搜寻算法.7、 平衡二叉树对于杳找算法而言是一种变治策略，屈于变治思想中的（9）类型。8、 在忽视常数因了的状况下，0、C和。三个符号中，（10）供应了算法运行时间的一个上界.9、 算法的“确定性”指的是组成鸵法的每条（ID是消整的,无歧义的。10、问题的（12）是该问题可用动态规划算法或贪心算法求解的关键特征。11、 算法就是一组有穷3）,它们规定了解决某一特定类型问题的（14.12、 变治思想有三种主要的类型：实例化简，变更表现，（15）选择题（每题2分，共20分）1、 二分搜寻算法是利用（）实现的算法。A

3、、分治策略B、动态规划法C、贪:心法D、回溯法2、 衡域一个算法好坏的标准是（）,A、运行速度快B、占用空间少C、时间困难度低D、代码短3、 能采纳贪心算法求最优解的问题，一般具有的重要性质为：（）A.最优子结构性质与贪心选择性质B.全叠子问即性质与贪心选择性质C.最优了结构性质与重叠子问题性质D.预排序与递归调用4、 常见的两种分支限界法为（）A、广度优先分支限界法与深度优先分支限界法：B、队列式（FIFO）分支限界法与堆栈式分支限界法：C,排列树法与子集树法；D、队列式（FIFO）分支限界法与优先队列式分支限界法:5、 实现循环赛日程表利用的知法是（）,A、分治策略B,动态规划法C,贪心法

4、【）、回溯法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 .阅读卜

5、.面的程序，按要求回答问题：(共10分)*inc1.udeinc1.udeinivis1011.01);intmap101101：intR1C:intdp(inti,intj)；intmain()(inti1j,ans,max：SCanf(飞d,&R,&C)：for(i=0;iR：i+)for(j=0JCJ+)scanf(,ft三pij):max=0：for(i=0：iR：i+)memset(visi,-1,sizeof(visi);for(j=0Jmax)max=ans：Printf(dn”,max)：return0;intdp(inti,intj)intmax=0;if(visij0)re

6、turnvisij;if(i-1.=0)if(mapi-1.,mapij)if(max-1.j)；if(i+1.R)if(mapi+1.jmapiJ)if(max=O)if(mapi.i-1.mapij)if(maxdp(i,j-1.)max=dp(,j-1.);if(j+iC)i(napij+1.mapij)if(maxgth2:i0:-i)HeapAdjust(H,i,H-1.ength);for(i=H-1.ength;i1.：i)rc=H-r1.：H-r1.=H-ri:H-ri=rc;HeapAdjust(H,1,i-1.);)return;)voidHeapAdjust(Sq1.is

7、t*H,ints,intm)(intrc,nn：intj;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)设传递给函数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分)四、

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行，即全部学生考试完所选谡程所须要的最少考试次数。