《2023计算机算法设计与分析期终考试复习题.docx》由会员分享，可在线阅读，更多相关《2023计算机算法设计与分析期终考试复习题.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机算法设计与分析复习题一、填空题1、一个算法困难性的凹凸体现在计算机运行该算法所需的时间和存储器资源上, 因此算法的困难性有时间 困难性和空间困难性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同03、运用二分搜寻算法在n个有序元素表中搜寻一个特定元素，在最佳状况下， 搜寻的时间困难性为0(1),在最坏状况下，搜寻的时间困难性为0(_logn_)。4、已知一个分治算法耗费的计算时间T(n), T(n)满意如下递归方程：27(/2) +。() n2解得此递归方可得T(n)=0)0 5、动态规划算法有一个变形方法备忘录方法o这种方法不
2、同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过 的子问题建立了备忘录以备须要时查看，同样也可避开相同子问题的重复求解。6 .递归的二分查找算法在divide阶段所花的时间是, conquer阶段 所花的时间是 T(n/2),算法的时间困难度是 0( /or n)。7 . Prim算法利用皿策略求解最小生成树问题,其时间困难度是 0(1?)。8 .背包问题可用 贪心法 ， 回溯法等策略求解。9 .用动态规划算法计算矩阵连乘问题的最优值所花的时间是一 0(n。，子问题空间大小是一 0(E)。10 .图的m着色问题可用回溯法求解,其解空间树中叶子结点个数是工，解空间树
3、中每个内结点的孩子数是_mo12、11 .单源最短路径问题可用贪心法、分支限界 等策略求解。一个算法的优劣可以用(时间困难度)与(空间困难度)与来衡量。13、回溯法在问题的解空间中，按(深度优先方式)从根结点动身搜寻解空间树。14、干脆或间接地调用自身的算法称为(递归算法)。15、。记号在算法困难性的表示法中表示(渐进确界或紧致界)。16、在分治法中，使子问题规模大致相等的做法是出自一种(平衡(banlancing)子问题)的思想。17、动态规划算法适用于解(具有某种最优性质)问题。18、贪心算法做出的选择只是(在某种意义上的局部)最优选择。Vo（2）若当前代价F=当前最优解代价如s排，则剪枝
4、。2分（3）见（1）中所画的图。5分（4）最优解为3, 1, 2,最优值为25。3分4.【Gray码构造问题】（8分）一一提示：此题可采纳分治递归算法实现问题描述：“格雷码”是一个长度为2的序列，满意：（a）每个元素都是长度为n比特的串（b）序列中无相同元素（c）连续的两个元素恰好只有1个比特不同例如：n=2时，格雷码为00, 01, 11, 10 oGray码是一种编码，这种编码可以避开在读取时，因各数据位时序上的差 异造成的误读。格雷码在工程上有广泛应用。但格雷码不便于运算，请你设计一 种构造方法，输入长度序列n,输出格雷码（你只要做出一种构造方案即可，格 雷码并不唯一）。参考解答：此题可
5、用分治法解决。当n=l时，输出格雷码0, 1当nl时，格雷码的长度为2,即共有2个码序列。此时，将问题一分为 二，即上半部分和下半部分。上半部分最高位设为0,下半部分最高位设为1。 剩下nT位的格雷码的构造采纳递归的思路。评分准则：1）答到运用分治算法，并且推导出分治算法的过程，边界设定清楚（即当 仅输出1位的格雷码如何处理），本题即可得满分；2）说明运用分治算法，但漏边界条件，扣2分以上；其它状况酌情考虑。5. (13分)给定带权有向 实数。另外，还给定V中白 点的最短路长度。这里路E 算从源顶点1到其它顶点IIE),其中每条边的权是非负 生要计算从源到全部其它各顶 .和。现采纳Dijkst
6、ra算法计 填入下表中。迭代SUdist2dist3dist4dist5初始11234参考解答：(13分)迭代Sudist2dist3dist4dist5初始1103010011, 2210603010021, 2, 4)41050309031, 2, 4, 3)31050306041, 2, 3, 4, 55105030606. (13分)有0T背包问题如下：n=6, c=20, P= (4, 8, 15, 1, 6, 3), W= (5, 3, 2, 10, 4, 8)o其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的 重量。请问对于此0T背包问题，应如何选择放进去的物品，
7、才能使到 放进背包的物品总价值最大。P=(15, 8, 6, 4, 3, 1)W=(2, 3, 4, 5, 8, 10),单位重量物品价值(7.5, 2. 67, 1.5, 0.8, 0. 375, 0. 1)参考解答：(13分)可知随着物品的重量增加，物品的价值削减；因此可以用贪心算法来求解。以选 取单位重量物品价值高为贪心策略。1 .先把重量为2的物品放进背包，此时剩余载重量为17, P为15。2 .把重量为3的物品放进背包，此时剩余载重量为14, P为23；3 .把重量为4的物品放进背包，此时剩余载重量为10, P为29；4把重量为5的物品放进背包，此时剩余载重量为5, P为33.由于8
8、5,所以不能再放进背包。结果是把重量为2, 3, 4, 5的物品装进背包，总价值最大为33.7、将所给定序列al:n分为长度相等的两段al:n/2和an/2+l:n,分别求 出这两段的最大子段和，则al:n的最大子段和有哪三种情形？(10分)参考解答：(1) al:n的最大子段和与al:n/2的最大子段和相同。(2) al :n的最大子段和与的最大子段an/2+l :n和相同。al :n的最大子段和为Eak(i=k=J)且 l=i=n/2, n/2+l=J=no8写出maxmin算法对下列实例中找最大数和最小数的过程。数组 A=(48, 12,61,3,5, 19, 32, 7)参考解答：写出
9、maxmin算法对下列实例中找最大数和最小数的过程。数组A=()1、 48, 12,61,3,5, 19, 32, 72、48, 1261,35, 1932,73、4861, 12319-32, 5-74、6132355、6139速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过 程。A=(65, 70, 75, 80, 85, 55, 50, 2)参考解答：第一个分割元素为65(1)(2)(3)(4)(5)(6)(7)(8)1P657Q75808555502286527580855550703765250808555757046 依据符号 0 的定义 0（f）+0（g）等于
10、 O（maxf （n）, g（n）。23、二分搜寻技术是运用（分治）策略的典型例子。24、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。25、:优子结构性质）和（子问题重叠性质）是采纳动态规划算法的两个基本 要素。26、（最优子结构性质）和（贪心选择性质）是贪心算法的基本要素。27、（选择能产生最优解的贪心准则）是设计贪心算法的核心问题。28、分支限界法常以（广度优先）或（以最小耗费（最大效益）优先）的方式搜寻问题的解空间树。29、贪心选择性质是指所求问题的整体最优解可以通过一系列（局部最优）的选 择，即贪心选择达到。30、依据活结点表的组织方式的不同，分支限界法包括（队列
11、式（FIFO）分支限界 法）和（优先队列式分支限界法）两种形式。31、假如对于同一实例，蒙特卡洛算法不会给出两个不同的正确解答，则称该蒙 特卡洛算法是（一样的）。32、哈夫曼编码可利用（贪心法）算法实现。33概率算法有数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法34以自顶向下的方式求解最优解的有（贪心算法）35、下列算法中通常以自顶向下的方式求解最优解的是（贪心法）。36、在对问题的解空间树进行搜寻的方法中，一个活结点有多次机会成为活结点 的是（回溯法）37、旅行售货员问题不能用（）解决可以用回溯法解决，分支限界法，
12、NP完 全性理论与近似算法38、贪心算法不能解决（0-1背包问题N皇后问题）。可以解决背包问题39、投点法是（概率算法）的一种。40、若线性规划问题存在最优解，它肯定不在（可行域内部）二、简答题1、（8分）写出下列困难性函数的偏序关系（即依据渐进阶从低到高排序）:2 3 log n log n2 nn 103参考解答：IO3 log log n2 2 3 n - nn2、(8分)现在有8位运动员要进行网球循环赛，要设计一个满意以下要求的竞 赛日程表：(1) 每个选手必需与其他选手各赛一次；(2) 每个选手一天只能赛一次；(3) 循环赛一共进行n - 1天。请利用分治法的思想，给这8位运动员设计
13、一个合理的竞赛日程。参考解答：表示结束租用时刻，10个客户的申请如下表所示:12345678910s(i)03153511886f(i)65498713121110同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用支配方案，在 这10位客户里面，使得体育馆能尽可能满意多位客户的需求，并算出针对上表 的10个客户申请，最多可以支配几位客户申请。参考解答：将这10位客户的申请依据结束时间f(i)递增排序，如下表：* 112345678910S13053568811f(i)45678910111213选择申请1 (1,4)依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直 到全
14、部申请检查完毕。申请4 (5,7)、申请8 (8,11)、申请10 (11, 13)最终，可以满意：申请1 (1,4)、申请4 (5可)、申请8 (8, 11)、申请10(11, 13)共4个客户申请。这已经是可以满意的最大客户人数。4、（8分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为:根,/ =k + tvk +1, j + p._x pk pj 1 = J KJ其中mi, j为计算矩阵连乘AiAj所需的最少数乘次数，p-为矩阵Ai的行,P,为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为:AiA2A3a450x1010x4040x3030x5PoX PiP 1X p2P2X p3
15、p3x p4请依据以上的递归关系，计算出矩阵连乘积AAA3A4所须要的最少数乘次数。参考解答： ml 1 + m2 4 + pop1p4=O +8000 + 50x10x5 = 10500 ml4 = min /加 1 2 + m34 + pQp2 p4 = 20000 + 6000 + 50x40x5 = 36000 ml 3 + m44 + pQp3p, = 27000 + 0 + 50x30x5 = 34500= 105005、（8分）有这样一类特别OT背包问题：可选物品重量越轻的物品价值越高。n=6, c=20, P= （4, 8, 15, 1, 6, 3）, W= （5, 3, 2,
16、 10, 4, 8）。其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重 量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的 物品总价值最大，能获得的最大总价值多少？参考解答：因为该0 1背包问题比较特别，恰好重量越轻的物品价值越高，所 以优先取重量轻的物品放进背包。最终可以把重量分别为2, 3, 4, 5的三个物 品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33,为最大值。6 .请用英文写出三种以上能求解0-1背包问题的设计算法策略。参考解答：Dynamic ProgrammingBacktrackBranch-and-Bound（每答对
17、一条给一分）7 .请说明动态规划方法为什么须要最优子结构性质。参考解答：最优子结构性质是指大问题的最优解包含子问题的最优解。动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解, 然后再利用子问题的最优解构造大问题的最优解，因此须要最优子结构8 .请说明：（1）优先队列可用什么数据结构实现？（2）优先队列插入算法基本思想？（3）优先队列插入算法时间困难度？参考解答：（1）堆。（1分）（2）在小根堆中，将元素x插入到堆的末尾，然后将元素x的关键字与其双亲的关键字比较，若元素x的关键字小于其双亲的关键字，则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比, 直到元素x的关
18、键字大于双亲的关键字，或元素x到根为止。（4分）（3） 0（ log n）（1 分）9 .设计动态规划算法的主要步骤是怎么的？请简述。参考解答：（1）找出最优解的性质，并刻划其结构特征。（6分）（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）依据计算最优值时得到的信息，构造最优解。10 .分治法所能解决的问题一般具有哪几个特征？请简述。参考解答：（1）该问题的规模缩小到肯定的程度就可以简洁地解决；（6分）（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最 优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独
19、立的，即子问题之间不包 含公共的子问题。11 .分支限界法的搜寻策略是什么？参考解答：在扩展结点处，先生成其全部的儿子结点（分支），然后再从当前的 活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜寻的进 程，在每一个活结点处，计算一个函数值（限界），并依据函数值，从当前活结 点表中选择一个最有利的结点作为扩展结点，使搜寻朝着解空间上有最优解的分 支推动，以便尽快地找出一个最优解。（6分）12算法的要特性是什么？参考解答：确定性、可实现性、输入、输出、有穷性13算法分析的目的是什么？参考解答：分析算法占用计算机资源的状况，对算法做出比较和评价，设计出额 更好的算法。14算法的时间
20、困难性与问题的什么因素相关？参考解答：算法的时间困难性与问题的规模相关，是问题大小n的函数。15算法的渐进时间困难性的含义？参考解答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T（n）的 数量级，而其他因素仅是使时间困难度相差常数倍，因此可以用T（n）的数量级(阶)评价算法。时间困难度T(n)的数量级(阶)称为渐进时间困难性。16最坏状况下的时间困难性和平均时间困难性有什么不同？参考解答：最坏状况下的时间困难性和平均时间困难性考察的是n固定时，不同 输入实例下的算法所耗时间。最坏状况下的时间困难性取的输入实例中最大的时 间困难度：W(n) = max T (n, I) , IDn平均
21、时间困难性是全部输入实例的处理时间与各自概率的乘积和：A(n) =UP(I)T(n, I) IDn17简述二分检索(折半查找)算法的基本过程。参考解答:设输入是一个按非降次序排列的元素表和x,选取A(i+j)/2 与 x 比较，假如 A(i+j)/2=x,则返回(i+j)/2,假如 A(i+j)/2x,则 Ai： (i+j)/2T找x,否则在A (i+j)/2+L j找x。上述过程被反复递归调用。18背包问题的目标函数和贪心算法最优化量度相同吗？参考解答：不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。19采纳回溯法求解的问题，其解如何表示？有什么规定？参考解答：问题的解可以表示为
22、n元组:(X1, x2,xQ, XjWSi, Si为有穷集合, XiSi, (X1, x2, Xn)具备完备性,即(X1, x2, Xn)是合理的，则(Xi, x2, Xi) (i No,有 T(n)f(n),这种关系记作 T(n)=0(f (n)。25二分检索算法最多的比较次数？参考解答：二分检索算法的最多的比较次数为log n o26快速排序算法最坏状况下须要多少次比较运算？参考解答：最坏状况下快速排序退化成冒泡排序，须要比较祐次。27贪心算法的基本思想？参考解答：是一种依据最优化量度依次选择输入的分级处理方法。基本思路是: 首先依据题意，选取一种量度标准；然后按这种量度标准对这n个输入排
23、序，依 次选择输入量加入部分解中。假如当前这个输入量的加入，不满意约束条件，则 不把此输入加到这部分解中28回溯法的解(xb x2,xn)的隐隐束一般指什么？参考解答：回溯法的解(xi, X2,X)的隐隐束一般指个元素之间应满意的某 种关系。29阐述归并排序的分治思路。参考解答：讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序 列归并成一个含n个元素的分好类的序列。假如分割后子问题还很大，则接着分 治，直到一个元素。30快速排序的基本思想是什么。参考解答：快速排序的基本思想是在待排序的N个记录中随意取一个记录，把该 记录放在最终位置后，数据序列被此记录分成两部分。全部关键字比该记录
24、关键 字小的放在前一部分，全部比它大的放置在后一部分，并把该记录排在这两部分 的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有 一个记录为止。31什么是干脆递归和间接递归？消退递归一般要用到什么数据结构？参考解答：在定义一个过程或者函数的时候又出现了调用本过程或者函数的成 分，既调用它自己本身，这称为干脆递归。假如过程或者函数P调用过程或者函 数Q, Q又调用P,这个称为间接递归。消退递归一般要用到栈这种数据结构。 32什么是哈密顿环问题？参考解答：哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点 一次并且返回它的起先位置。33用回溯法求解哈密顿环，如何定义判
25、定函数？参考解答：当前选择的节点Xk是从未到过的节点，即Xk丰XLi(i=l,2,-,k-l),且 C(Xk-1, Xk)W8,假如 k=-1,则 C(Xk, Xl) 28。34请写出prim算法的基本思想。参考解答：思路是：最初生成树T为空，依次向内加入与树有最小邻接边的nT 条边。处理过程：首先加入最小代价的一条边到T,依据各节点到T的邻接边排 序，选择最小边加入，新边加入后，修改由于新边所变更的邻接边排序，再选择 下一条边加入，直至加入nT条边。三、算法设计题1.【最长上升子序列问题】(8分)一一提示：此题可采纳动态规划算法实现对于给定的一个序列(,。2，,心)，IWNGOOO。我们可以
26、得到一些递增上升的子序列(,%，,。火)，这里，2 “ N。比如，对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子 序列中最长的长度是4,比如子序列(1, 3, 5, 8)o你的任务：就是对于给定的 序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公 式表达。.参考解答：设/表示：从左向右扫描过来直到以a口元素结尾的序列，获得的最长上升子序列的长度，且子序列包含。元素(lZ)o1i= 1/(/) = j1Z1；都有。田=0力即，/是从1), /(2)到/。-1)中找最大的一个值，再加lo或者就是1。主
27、要是看ai这个元素能否加入到之前已经获得的最长上升子序列，假 如能加入，是之前已获得的最长上升子序列长度加一；假如不能加入，就取这最 终一个元素作为一个单独子序列，长度为1。最终，所要求的整个序列的最长公共子序列长度为maxf(i): l=i=n例如，对于序列：4 2 6 3 1 5 211234567array4263152f(i)1122132评分准则：1)答到运用动态规划算法，并且推导出动态规划算法的递推函数公式表达, 边界设定清楚，本题即可得满分；(阅卷时细致看递推公式表达，公式表 达含义正确即可，因其表达形式可能不唯一)2)说明运用动态规划算法，但对递推函数表达错误或模糊，扣2分以上
28、；3)其它状况酌情考虑。2. (10分)对下图所示的连通网络G,用克鲁斯卡尔(Kruskal)算法求G的最小生 成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的 贪心策略和算法的基本思想，并简要分析算法的时间困难度。1182参考解答TE=（3,4）, （2, 3）, （1,5）, （4,6） （4,5） （5 分）贪心策略是每次都在连接两个不同连通重量的边中选权值最小的边。基本思想：首先将图中全部顶点都放到生成树中，然后每次都在连接两个不 同连通重量的边中选权值最小的边，将其放入生成树中，直到生成树中有nT 条边。（4分）时间困难度为：O（eloge） （1分）3. （15分）考虑n=3的批处理作业调度实例：机器1机器2作业1 作业2 作业3其中1是作业须要在机器j上处理的时间。对于给定的3个作业，制定 一个最佳作业调度方案，使其完成时间和达到最小。（5分）要求：（1）画出该问题的解空间树;（2）写出该问题的剪枝策略（即限界条件），要求只保留第一个最优解；（2分）（3）按优先队列式分支限界法搜寻解空间树，并用剪枝策略对解空间树中该（5分）（3分）剪枝的位置打x；（4）给出最优解及最优值。参考解答（1） 5分