2022年算法设计与分析期末考试卷及答案a .pdf

一填空题（每空2 分，共 30 分）1算法的时间复杂性指算法中的执行次数。2在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。3设 Dn表示大小为 n 的输入集合， t(I)表示输入为 I 时算法的运算时间 , p(I)表示输入I 出现的概率，则算法的平均情况下时间复杂性A(n)= 。4分治算法的时间复杂性常常满足如下形式的递归方程：00nn,g(n)af(n/c)f(n)nn,d)n(f其中， g(n)表示。5. 分治算法的基本步骤包括。6回溯算法的基本思想是。7动态规划和分治法在分解子问题方面的不同点是。8贪心算法中每次做出的贪心选择都是最优选择。9PQ 式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级越。10选择排序、插入排序和归并排序算法中，算法是分治算法。11随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的结果。12. 对 于 下 面 的 确 定 性 快 速 排 序 算 法 ， 只 要 在 步 骤3 前 加 入 随 机 化 步骤，就可得到一个随机化快速排序算法，该随机化步骤的功能是。算法 QUICKSORT输入： n 个元素的数组 A1.n 。输出：按非降序排列的数组A 中的元素。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 考生信息栏学院系专业年级姓名学号装订线1. quicksort(1, n)end QUICKSORT过程 quicksort(A, low, high)/ 对 Alow.high 中的元素按非降序排序。2. if lowhigh then3. w=SPLIT(A, low, high) /算法 SPLIT 以 Alow 为主元将 Alow.high 划分成两部/分，返回主元的新位置。4. quicksort (A, low, w-1)5. quicksort (A, w+1, high)6 end ifend quicksort13下面算法的基本运算是运算，该算法的时间复杂性阶为( )。算法 SPLIT输入：正整数 n，数组 A1.n 。输出：。i=1x=A1for j=2 to nif Aj0 then output ielse output “no solution”end SEARCH过程 find (low, high)/ 求 Alow.high 中使得 Ai=i 的一个下标并返回，若不存在，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - /则返回 0。if (2) then return 0elsemid=2/)highlow(if (3) then return midelse if Amidmid then return find( (4) )elsereturn (5) end ifend ifend ifend find2(10 分) 下面是求解矩阵链乘问题的动态规划算法。矩阵链乘问题：给出 n 个矩阵 M1, M2, , Mn , Mi 为 riri+1阶矩阵，i=1, 2, , n，求计算 M1M2Mn所需的最少数量乘法次数。记 Mi, j=MiMi+1Mj , i=j。 设 Ci, j, 1=i=j=n, 表示计算 Mi, j的所需的最少数量乘法次数，则ji ,rrrjCk,1-k, i Cminji ,0j, i C1jkijki算法 MATCHAIN输入：矩阵链长度 n, n 个矩阵的阶 r1.n+1, 其中 r1.n为 n个矩阵的行数， rn+1为第 n 个矩阵的列数。输出：n 个矩阵链乘所需的数量乘法的最少次数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 考生信息栏学院系专业年级姓名学号装订线for i=1 to n Ci, i= （1）for d=1 to n-1 for i=1 to n-d j= (2) Ci, j= for k=i+1 to jx= (3) if xCi, j then(4) =xend if end forend forend forreturn (5) end MATCHAIN3(14 分) 下面是用回溯法求解马的周游问题的算法。马的周游问题：给出一个nxn 棋盘，已知一个中国象棋马在棋盘上的某个起点位置（x0, y0） ，求一条访问每个棋盘格点恰好一次，最后回到起点的周游路线。 （设马走日字。）算法 HORSETRAVEL输入：正整数 n，马的起点位置 (x0, y0)，1=x0, y0=n 。输出：一条从起点始访问nxn 棋盘每个格点恰好一次， 最后回到起点的周游路线；若问题无解，则输出no solution。tag1.n, 1.n=0 dx1.8=2, 1, -1, -2, -2, -1, 1, 2dy1.8=1, 2, 2, 1, -1, -2, -2, -1flag=false 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - x=x0; y=y0 ; tagx, y=1 m=n*n i=1; ki=0while (1) and not flag while kihigh (3) Amid=mid (4) mid+1, high (5) find(low, mid -1)2. (1) 0 (2) i+d (3) Ci, k -1+Ck, j+ri*rk*rj+1(4) Ci, j (5) C1, n3. (1) i=1 (2)ki+1 (3) 1 (4) i+1 (5) ki=0 (6) tagx, y=0 (7) x=x-dxki; y=y-dyki四. 算法设计题：1. 贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。算法MINSTOPS输入： A、B 两地间的距离s，A、B 两地间的加油站数n，车加满油后可行驶的公里数m，存储各加油站离起点A 的距离的数组d1.n 。输出：从 A 地到 B 地的最少加油次数k 以及最优解x1.k （xi 表示第 i 次加油的加油站序号），若问题无解，则输出no solution。dn+1=s; /设置虚拟加油站第n+1 站。for i=1 to nif di+1 -dim then output “no solution”; return /无解，返回end ifend fork=1; xk=1 /在第 1 站加满油。s1=m /s1 为用汽车的当前油量可行驶至的地点与A 点的距离i=2while s1s1 then /以汽车的当前油量无法到达第i+1 站。k=k+1; xk=i /在第 i 站加满油。s1=di+m /刷新 s1 的值end ifi=i+1end whileoutput k, x1.kMINSTOPS最坏情况下的时间复杂性：(n)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -