2022年算法设计与分析考试题及答案.docx

《2022年算法设计与分析考试题及答案.docx》由会员分享，可在线阅读，更多相关《2022年算法设计与分析考试题及答案.docx（23页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 一、填空题 （20 分）1. 一个算法就是一个有穷规章的集合, 其中之规章规定明白决某一特 殊类型问题的一系列运算,此外,算法仍应具有以下五个重要特 性:_,_,_,_,_ ；2. 算法的复杂性有 _和_之分,衡量一个算法 好坏的标准是 _；3. 某 一 问 题 可 用 动 态 规 划 算 法 求 解 的 显 著 特 征 是 _；4. 如序列 X=B,C,A,D,B,C,D ,Y=A,C,B,A,B,D,C,D,请给出序列 X 和 Y的一个最长公共子序列 _；5. 用回溯法解问题时, 应明确定义问题的解空间, 问题的解空间至少 应包含 _；6.

2、 动 态 规 划 算 法 的 基 本 思 想 是 将 待 求 解 问 题 分 解 成 如 干 _,先求解 _,然后从这些 _的 解得到原问题的解；7. 以深度优先方式系统搜寻问题解的算法称为 8.0-1 背包问题的回溯算法所需的运算时间为_；_,用动态规划算法所需的运算时间为 _；9. 动态规划算法的两个基本要素是_和_；10. 二分搜寻算法是利用 _实现的算法；二、综合题 （50 分）1. 写出设计动态规划算法的主要步骤；名师归纳总结 - - - - - - -第 1 页,共 13 页精选学习资料 - - - - - - - - - 2. 流水作业调度问题的johnson 算法的思想；3.

3、如 n=4,在机器 M1和 M2上加工作业 i 所需的时间分别为 ai 和 bi,且a 1,a 2,a 3,a 4=4,5,12,10,b 1,b 2,b 3,b 4=8,2,15,9 求 4 个作业的最优调度方案,并运算最优值；4. 使用回溯法解 0/1 背包问题： n=3,C=9,V=6,10,3 ,W=3,4,4,其解空间有长度为 3 的 0-1 向量组成,要求用一棵完全二叉树表示其解空间（从根动身,左 及最优解；1 右 0）,并画出其解空间树,运算其最优值5. 设 S=X1,X2, ,Xn是严格递增的有序集,利用二叉树的结点来储备 S中的元素,在表示 S的二叉搜寻树中搜寻一个元素 X,

4、返回的结果有两种情形,（1）在二叉搜寻树的内结点中找到 X=Xi ,其概率为 bi ；（2）在二叉搜寻树的叶结点中确定X（Xi ,Xi+1）,其概率为ai；在表示 S的二叉搜寻树 T 中,设储备元素 Xi 的结点深度为 Ci ；叶结点（Xi,Xi+1 ）的结点深度为 di,就二叉搜寻树 T 的平均路长 p 为多少？假设二叉搜寻树 Tij=Xi ,Xi+1 , ,Xj 最优值为 mij,Wij= a i-1 +bi+ +bj +aj ,就 mij1=i=j=n 递归关系表达式为什么？6. 描述 0-1 背包问题；三、简答题 （30 分）1.流水作业调度中,已知有n 个作业,机器 M1和 M2上加

5、工作业 i 所名师归纳总结 需的时间分别为 ai 和 bi ,请写出流水作业调度问题的johnson 法就中第 2 页,共 13 页对 ai 和 bi 的排序算法；（函数名可写为 sorts,n）- - - - - - -精选学习资料 - - - - - - - - - 2.最优二叉搜寻树问题的动态规划算法（设函数名 答案：一、填空binarysearchtree）1确定性 有穷性 可行性 0 个或多个输入 一个或多个输出2. 时间复杂性 空间复杂性 时间复杂度高低3. 该问题具有最优子结构性质4.BABCD或CABCD或CADCD5. 一个（最优）解6. 子问题子问题子问题7. 回溯法8.

6、on*2 n ominnc,2 n 9. 最优子结构 重叠子问题10. 动态规划法二、综合题1. 问题具有最优子结构性质；构造最优值的递归关系表达式；最优值的算法描述；构造最优解；2. 令 N1=i|a i=bi ；将 N1中作业按 ai 的非减序排序得到 N1 ,将 N2中作业按 bi 的非增序排序得到 N2 ；N1中作业接 N2中作业就构成了满意 Johnson 法就的最优调度；3. 步骤为： N1=1,3 ,N2=2,4 ；N1=1,3 , N2=4,2 ；最优值为： 38 名师归纳总结 - - - - - - -第 3 页,共 13 页精选学习资料 - - - - - - - - -

7、4. 解空间为 0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1, 1,1,0,1,1,1；解空间树为：1 A 0 1 D 1 B 0 0 1 1 C 0 0 0 1 E F 0 G 1 H I J K L M N O 该问题的最优值为： 16 最优解为：（1,1,0）5. 二叉树 T 的平均路长 P=nbi*1Ci+naj*dji 1j 0mij=Wij+minmik+mk+1j 1=i=jj 6. 已知一个背包的容量为C,有 n 件物品,物品 i 的重量为 W i,价值为 Vi ,求应如何挑选装入背包中的物品,使得装入背包中物品的总价值最大；三、简答题1. void

8、sortflowjope s,int n 名师归纳总结 - - - - - - -第 4 页,共 13 页精选学习资料 - - - - - - - - - int i,k,j,l; fori=1;i=n-1;i+/- 挑选排序 k=i; whilekn break;/-没有 ai,跳出 else forj=k+1;jsj.a k=j; swapsi.index,sk.index; swapsi.tag,sk.tag; l=i;/- 登记当前第一个 bi 的下标 fori=l;i=n-1;i+ k=i; forj=k+1;j=n;j+ ifsk.bsj.b k=j; swapsi.index,s

9、k.index; /- 只移动 index 和 tag 名师归纳总结 - - - - - - -第 5 页,共 13 页精选学习资料 - - - - - - - - - swapsi.tag,sk.tag; 2. void binarysearchtreeint a,int b,int n,int *m,int *s,int *w int i,j,k,t,l; fori=1;i=n+1;i+ wii-1=ai-1; mii-1=0; forl=0;l=n-1;l+/-l 是下标 j-i 的差 fori=1;i=n-l;i+ j=i+l; wij=wij-1+aj+bj; mij=mii-1+m

10、i+1j+wij; sij=i; fork=i+1;k=j;k+ t=mik-1+mk+1j+wij; 名师归纳总结 - - - - - - -第 6 页,共 13 页精选学习资料 - - - - - - - - - iftmij mij=t; sij=k; 名师归纳总结 - - - - - - -第 7 页,共 13 页精选学习资料 - - - - - - - - - 一、填空题（此题15 分,每道题1 分）1、 算法就是一组有穷的,它们规定明白决某一特定类型问题的；3 个基2、 在进行问题的运算复杂性分析之前,第一必需建立求解问题所用的运算模型；和本运算模型是、；3、 算法的复杂性是的度量

11、,是评判算法优劣的重要依据；4、 运算机的资源最重要的是和资源；因而,算法的复杂性有之分；5、 fn= 62n+n2,fn 的渐进性态fn= O 6、 贪心算法总是做出在当前看来的挑选；也就是说贪心算法并不从整体最优考虑,它所做出的挑选只是在某种意义上的；性质和性7、 很多可以用贪心算法求解的问题一般具有2 个重要的性质：质；二、简答题（此题25 分,每道题5 分）1、 简洁描述分治法的基本思想；2、 简述动态规划方法所运用的最优化原理；3、 何谓最优子结构性质？4、 简洁描述回溯法基本思想；5、 何谓 P、 NP、NPC问题三、算法填空（此题20 分,每道题5 分）1、n 后问题回溯算法1

12、用二维数组ANN 储备皇后位置 , 如第 i 行第 j 列放有皇后 , 就 Aij为非 0 值, 否就值为 0；2 分别用一维数组 MN 、L2*N-1 、R2*N-1 表示竖列、 左斜线、 右斜线是否放有棋子,有就值为 1, 否就值为 0；forj=0;j=0;r- / 自底向上递归运算forc=0; 1 ;c+ 名师归纳总结 if tr+1ctr+1c+1 2 ；第 8 页,共 13 页else 3 - - - - - - -精选学习资料 - - - - - - - - - 3、Hanoi 算法 Hanoin,a,b,c if （n=1） 1 ；else 2 ； 3 ；Hanoin-1,b

13、, a, c; 4、Dijkstra 算法求单源最短路径 du:s 到 u 的距离 pu: 记录前一节点信息Init-single-sourceG,s for each vertex vVG do dv= ; 1 ds=0 Relaxu,v,w if dvdu+wu,v then dv=du+wu,v; 2 dijkstraG,w,s 1. Init-single-sourceG,s 2. S= 3. Q=VG 4.while Q do u=minQ S=Su for each vertex 3 do 4 四、算法懂得题（此题 10 分）依据优先队列式分支限界法,求下 图中从 v1 点到 v9

14、 点的单源最短路径,请画出求得最优解的解空间树；要求中间被舍弃的结点用 标记,获得中间解的结点用单圆圈 框 起,最优解用双圆圈 框起；五、算法懂得题（此题 5 分）设有 n=2k个运动员要进行循环赛,现设计一个满意以下要求的竞赛日程表：每个选手必需与其他 n-1 名选手竞赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内完成；（1）假如 n=2k,循环赛最少需要进行几天；（2）当 n=23=8 时,请画出循环赛日程表；名师归纳总结 六、算法设计题（此题15 分）第 9 页,共 13 页- - - - - - -精选学习资料 - - - - - - - - - 分别用贪心算法、动态规划法

15、、回溯法设计0-1 背包问题；要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间；七、算法设计题（此题 10 分）通过键盘输入一个高精度的正整数 nn 的有效位数 240,去掉其中任意 s 个数字后,剩下的数字按原左右次序将组成一个新的正整数；编程对给定的 n 和 s,查找一种方案,使得剩下的数字组成的新数最小；【样例输入】178543 S=4 【样例输出】13 一、填空题（此题15 分,每道题1 分）1规章 一系列运算2. 随机存取机 RAMRandom Access Machine ；随机存取储备程序机 RASPRandom Access Stored Program Ma

16、chine ；图灵机 Turing Machine 3. 算法效率4. 时间 、空间、时间复杂度、空间复杂度52 n 6 最好 局部最优挑选7. 贪心挑选 最优子结构二、简答题（此题 25 分,每道题 5 分）6、 分治法的基本思想 是将一个规模为 n 的问题分解为 k 个规模较小的子问题,这些子问题相互独立且与原问题相同；对这k 个子问题分别求解；假如子问题的规模仍旧不够小,就再划分为 k 个子问题,如此递归的进行下去,直到问题规模足够小,很简洁求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原先问题的解；7、 “ 最优化原理 ”用数学化的语言来描述：假设

17、为明白决某一优化问题,需要依次作出 n个决策 D1,D2, ,Dn,如如这个决策序列是最优的,对于任何一个整数 k,1 k n,不论前面 k 个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2, ,Dn也是最优的；8、 某个问题的最优解包含着其子问题的最优解；这种性质称为 最优子结构性质；9、 回溯法的基本思想 是在一棵含有问题全部可能解的状态空间树上进行深度优先搜寻,解为叶子结点；搜寻过程中,每到达一个结点时,就判定该结点为根的子树是否含有 问题的解,假如可以确定该子树中不含有问题的解,就舍弃对该子树的搜寻,退回到 上层父结点,连续下一步深度优先

18、搜寻过程；在回溯法中,并不是先构造出整棵状态 空间树,再进行搜寻,而是在搜寻过程,逐步构造出状态空间树,即边搜寻,边构造；名师归纳总结 10、PPolynomial问题 ：也即是多项式复杂程度的问题；第 10 页,共 13 页- - - - - - -精选学习资料 - - - - - - - - - NP 就是 Non-deterministicPolynomial的问题,也即是多项式复杂程度的非确定性问题；NPCNP Complete 问题,这种问题只有把解域里面的全部可能都穷举了之后才能得出 答案,这样的问题是 NP里面最难的问题,这种问题就是 NPC问题；三、算法填空（此题 20 分,每

19、道题 5 分）1、n 后问题回溯算法 1 .Mj&.Li+j&.Ri-j+N 2 Mj=Li+j=Ri-j+N=1; 3 tryi+1,M,L,R,A 4 Aij=0 5 Mj=Li+j=Ri-j+N=0 2、数塔问题；（1）c=r 2trc+=tr+1c （3）trc+=tr+1c+1 3、Hanoi 算法（1）movea,c （2）Hanoin-1, a, c , b （3）Movea,c 4、（ 1）pv=NIL （2）pv=u 3 vadju （4）Relaxu,v,w 四、算法懂得题（此题 10 分）1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7

20、8 5 6 4 3 2 1 8 7 6 5 名师归纳总结 五、（1）8 天（2 分）；（ 3 分）；5 6 7 8 1 2 3 4 第 11 页,共 13 页6 5 8 7 2 1 4 3 （2）当 n=23=8 时,循环赛日程表7 8 5 6 3 4 1 2 六、算法设计题（此题15 分）8 7 6 5 4 3 2 1 - - - - - - -精选学习资料 - - - - - - - - - （1）贪心算法 O（ nlog（n）.第一运算每种物品单位重量的价值Vi/Wi ,然后,依贪心挑选策略,将尽可能多的单位重量价值最高的物品装入背包；如将这种物品全部装入背包后,背包内的物品总重量未超过

21、 C,就挑选单位重量价值次高的物品并尽可能多地装入背包；依此策 略始终地进行下去,直到背包装满为止；. 详细算法可描述如下：void Knapsackint n,float M,float v,float w,float x Sortn,v,w; int i; for i=1;i=n;i+ xi=0; float c=M; for i=1;ic break; xi=1; c-=wi; if i=n xi=c/wi; （2）动态规划法Onc i,i+1 , ,n 时 0-1 背包问题的最优值；由0-1mi,j是背包涵量为j,可挑选物品为背包问题的最优子结构性质,可以建立运算mi ,j的递归式如下

22、；m i,jmaxm i,1j,m ij,1jw iv ijw im i,10jw im n ,jv n0jjw n0w nvoid KnapSackint v,int w,int c,int n,int m11 int jMax=minwn-1,c; for j=0;j=jMax;j+ /*mn,j=0 0=jwn*/ mnj=0; for j=wn;j=wn*/ mnj=vn; for i=n-1;i1;i- int jMax=minwi-1,c; for j=0;j=jMax;j+ /*mi,j=mi+1,j 0=jwi*/ mij=mi+1j; for j=wi;j=wn*/ mij=

23、maxmi+1j,mi+1j-wi+vi; m1c=m2c; ifc=w1 m1c=maxm1c,m2c-w1+v1; 名师归纳总结 - - - - - - -第 12 页,共 13 页精选学习资料 - - - - - - - - - （3）回溯法 O2n cw:当前重量cp:当前价值bestp：当前最优值void backtrack int i /回溯法 i 初值 1 ifi n /到达叶结点 bestp = cp; return; ifcw + wi bestp /搜寻右子树 backtracki+1; 七、算法设计题（此题 10 分）为了尽可能地靠近目标,我们选取的贪心策略为：每一步总是挑选一个使剩下的数最 小的数字删去,即按高位到低位的次序搜寻,如各位数字递增,就删除最终一个数字,否就删除第一个递减区间的首字符；然后回到串首,按上述规章再删除下一个数字；重复以 上过程 s 次,剩下的数字串便是问题的解了；详细算法如下：输入 s, n; while （ s 0 ） i=1; /从串首开头找while i lengthn & ni1& n1= 0 deleten,1,1; / 删去串首可能产生的无用零 输出 n; 名师归纳总结 - - - - - - -第 13 页,共 13 页