2022年太原理工大学软件学院算法设计与分析复习题目及答案.docx

《2022年太原理工大学软件学院算法设计与分析复习题目及答案.docx》由会员分享，可在线阅读，更多相关《2022年太原理工大学软件学院算法设计与分析复习题目及答案.docx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 一、挑选题1、二分搜寻算法是利用（A ）实现的算法；A、分治策略 B、动态规划法 C、贪心法 D、回溯法2、以下不是动态规划算法基本步骤的是（A ）；A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解3、最大效益优先是（A ）的搜寻方式；A、分支界限法 B 、动态规划法 C、贪心法 D、回溯法4. 回溯法解旅行售货员问题时的解空间树是（ B ）；A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树5以下算法中通常以自底向上的方式求解最优解的是（B ）；A、备忘录法 B、动态规划法 C、贪心法 D、回溯法6、衡量一个算

2、法好坏的标准是（C ）；A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短7、以下不行以使用分治法求解的是（D ）；A 棋盘掩盖问题 B 挑选问题 C 归并排序 D 0/1 背包问题8. 实现循环赛日程表利用的算法是（A ）；D D、回溯法A、分治策略B、动态规划法C、贪心法9下面不是分支界限法搜寻方式的是（D ）；D、深度优先A、广度优先B、最小耗费优先C、最大效益优先10以下算法中通常以深度优先方式系统搜寻问题解的是（）；A、备忘录法B、动态规划法C、贪心法D、回溯法11. 备忘录方法是那种算法的变形； （ B ）名师归纳总结 A、分治法B、动态规划法C、贪心法D、回溯法第 1

3、页,共 18 页12最长公共子序列算法利用的算法是（B ）；A、分支界限法B、动态规划法C、贪心法D、回溯法13实现棋盘掩盖算法利用的算法是（A ）；A、分治法B、动态规划法C、贪心法D、回溯法14. 下面是贪心算法的基本要素的是（C ）；A、重叠子问题B、构造最优解C、贪心挑选性质D、定义最优解- - - - - - -精选学习资料 - - - - - - - - - 15. 回溯法的效率不依靠于以下哪些因素（ D ）A. 满意显约束的值的个数 B. 运算约束函数的时间C. 运算限界函数的时间 D. 确定解空间的时间16. 下面哪种函数是回溯法中为防止无效搜寻实行的策略（B ）A递归函数 B

4、.剪枝函数 C. 随机数函数 D. 搜寻函数17. （D ）是贪心算法与动态规划算法的共同点；A、重叠子问题 B、构造最优解 C、贪心挑选性质 D、最优子结构性质18. 矩阵连乘问题的算法可由（B）设计实现；A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法19. 分支限界法解旅行售货员问题时,活结点表的组织形式是（A ）；A、最小堆 B、最大堆 C、栈 D、数组20、Strassen 矩阵乘法是利用（A ）实现的算法；A、分治策略 B、动态规划法 C、贪心法 D、回溯法21、使用分治法求解不需要满意的条件是（A ）；A 子问题必需是一样的B 子问题不能够重复C 子问题的解可以合并

5、D 原问题和子问题使用相同的方法解22、下面问题（ B ）不能使用贪心法解决；A 单源最短路径问题 B N 皇后问题C 最小花费生成树问题 D 背包问题23、以下算法中不能解决0/1 背包问题的是（ A ）A 贪心法 B 动态规划 C 回溯法 D 分支限界法 24、回溯法搜寻状态空间树是依据（C ）的次序；A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历名师归纳总结 25实现合并排序利用的算法是（A ）；第 2 页,共 18 页A、分治策略B、动态规划法C、贪心法D、回溯法26以下是动态规划算法基本要素的是（D ）；A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质

6、- - - - - - -精选学习资料 - - - - - - - - - 27以下算法中通常以自底向下的方式求解最优解的是（B ）；A、分治法 B、动态规划法 C、贪心法 D、回溯法28采纳广度优先策略搜寻的算法是（A ）；A、分支界限法 B、动态规划法 C、贪心法 D、回溯法29、合并排序算法是利用（ A ）实现的算法；A、分治策略 B、动态规划法 C、贪心法 D、回溯法30、背包问题的贪心算法所需的运算时间为（B ）A、O（n2 n） B 、O（nlogn ） C、O（2 n）D、O（n）31实现大整数的乘法是利用的算法（C ）；A、贪心法 B、动态规划法 C、分治策略 D、回溯法320

7、-1 背包问题的回溯算法所需的运算时间为（A ）A、O（n2 n）B、O（nlogn ）C、O（2 n）D、O（n）33采纳最大效益优先搜寻方式的算法是（A ）；A、分支界限法 B、动态规划法 C、贪心法 D、回溯法34贪心算法与动态规划算法的主要区分是（B ）；A、最优子结构 B、贪心挑选性质 C、构造最优解 D、定义最优解35. 优先队列式分支限界法选取扩展结点的原就是（C ）；A、先进先出 B、后进先出 C、结点的优先级 D、随机36. 背包问题的贪心算法所需的运算时间为（B ）；A、O（n2 n）B、O（nlogn ）C、O（2 n）D、O（n）37、广度优先是（A ）的搜寻方式；A、

8、分支界限法 B 、动态规划法 C、贪心法 D、回溯法38. 一个问题可用动态规划算法或贪心算法求解的关键特点是问题的（B ）；A、重叠子问题 B、最优子结构性质 C、贪心挑选性质 D、定义最优解39采纳贪心算法的最优装载问题的主要运算量在于将集装箱依其重量从小到大排序,故算法的时间复杂度为 B ；A、O（n2 n）B、O（nlogn ）C、O（2 n） D、O（n）名师归纳总结 40. 以深度优先方式系统搜寻问题解的算法称为 D ；第 3 页,共 18 页A、分支界限算法 B、概率算法C、贪心算法 D、回溯算法- - - - - - -精选学习资料 - - - - - - - - - 41.

9、实现最长公共子序列利用的算法是（B ）；A、分治策略 B、动态规划法 C、贪心法 D、回溯法42、算法是由如干条指令组成的有穷序列,而且满意以下性质（D）（1） 输入：有 0 个或多个输入（2） 输出：至少有一个输出（3） 确定性：指令清楚,无歧义（4） 有限性：指令执行次数有限,而且执行时间有限A 123 B124 C134 D 1 234 43、函数 32 n+10nlog n 的渐进表达式是 B . A. 2 n B. 32 n C. nlog n D. 10nlog n44、大整数乘法算法是 A .算法A.分治 B.贪心 C.动态规划 D.穷举45、解决活动支配问题,最好用（B ）算法

10、A.分治 B.贪心 C.动态规划 D.穷举46、设 fN,gN 是定义在正数集上的正函数 ,假如存在正的常数 C 和自然数 N0,使得当 NN0 时有 fN CgN, 就称函数 fN 当 N 充分大时有下界 gN,记作fN gN, 即 fN 的阶 A gN的阶 . A.不高于 B.不低于 C.等价于 D.靠近47、回溯法在解空间树 T 上的搜寻方式是 A . A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先48、回溯算法和分支限界法的问题的解空间树不会是 D. A.有序树 B.子集树 C.排列树 D.无序树49、在对问题的解空间树进行搜寻的方法中 结点的是 B . ,一个活结点最多

11、有一次机会成为活A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题50、从活结点表中挑选下一个扩展结点的不同方式将导致不同的分支限界法 ,以下除 C 之外都是最常见的方式 . 名师归纳总结 A.队列式分支限界法B.优先队列式分支限界法第 4 页,共 18 页C.栈式分支限界法D.FIFO 分支限界法- - - - - - -精选学习资料 - - - - - - - - - 二、 填空题1. 算法的复杂性有 时间 复杂性和 空间 复杂性之分；2、程序是 算法 用某种程序设计语言的详细实现；3、算法的“ 确定性” 指的是组成算法的每条 指令 是清楚的,无歧义的；4. 矩阵

12、连乘问题的算法可由 动态规划 设计实现；5、算法是指解决问题的 一种方法 或 一个过程；6、从分治法的一般设计模式可以看出,用它设计出的程序一般是 递归算法；7、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特点；8、以深度优先方式系统搜寻问题解的算法称为回溯法；基本操作的频率9、运算一个算法时间复杂度通常可以运算循环次数、或运算步；10、解决 0/1 背包问题可以使用动态规划、回溯法和分支限界法, 其中不需要排序的是 动态规划,需要排序的是 回溯法,分支限界法；11、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界, N皇后问题和 0/1 背包问

13、题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是 0/1 背包问题,只使用约束条件进行裁剪的是 N 皇后问题；12、贪心挑选性质 是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区分；名师归纳总结 13、矩阵连乘问题的算法可由动态规划设计实现；第 5 页,共 18 页14. 贪心算法的基本要素是贪心挑选性质和最优子结构性质 ；15. 动态规划算法的基本思想是将待求解问题分解成如干子问题,先求解子问题,然后从这些子问题的解得到原问题的解；16. 算法是由如干条指令组成的有穷序列,且要满意输入、输出、确定性和有限性四条性质；17、大整数乘积算法是用分治法来设计

14、的；18、以广度优先或以最小耗费方式搜寻问题解的算法称为分支限界法；19、贪心挑选性质是贪心算法可行的第一个基本要素,也是贪心算法与动态- - - - - - -精选学习资料 - - - - - - - - - 规划算法的主要区分；20. 快速排序算法是基于分治策略的一种排序算法；21. 动 态 规 划 算 法 的 两 个 基 本 要 素 是 最 优 子 结 构 性 质 和 重 叠 子 问 题性质 ；22. 回溯法是一种既带有 系统性又带有 跳动性的搜寻算法；23. 分支限界法主要有队列式（FIFO）分支限界法和 优先队列式分支限界法；24分支限界法是一种既带有 系统性又带有 跳动性 的搜寻算

15、法；25回溯法搜寻解空间树时,常用的两种剪枝函数为约束函数 和限界函数；26. 任何可用运算机求解的问题所需的时间都与其 规模 有关；27. 快速排序算法的性能取决于 划分的对称性；28. Prim 算法利用贪心策略求解最小生成树问题,其时间复杂度是 On2；29. 图的 m 着色问题可用 回溯法求解,其解空间树中叶子结点个数是 mn,解空间树中每个内结点的孩子数是 m；三、算法的程序填空1. 背包问题的贪心算法void Knapsackint n,float M,float v,float w,float x Sortn,v,w; int i; for i=1;i=n;i+ xi=0; fl

16、oat c=M; for i=1;ic break; xi=1; c - =wi; if i=n xi=c/wi; 2. 最大子段和 : 动态规划算法名师归纳总结 - - - - - - -第 6 页,共 18 页精选学习资料 - - - - - - - - - int MaxSumint n, int a int sum=0, b=0； /sum 储备当前最大的 bj, b 储备 bj forint j=1； j0 b+= aj ； else b=ai; ； / 一旦某个区段和为负, 就从下一个位置累和 ifbsum sum=b; return sum； 3. 快速排序 template v

17、oid QuickSort Type a, int p, int r if pr int q=Partitiona,p,r; QuickSort a,p,q-1; / 对左半段排序 QuickSort a,q+1,r; / 对右半段排序 4. 排列问题 Template void permType list, int k, int m /产生 listk:m的全部排列 ifk=m / 只剩下一个元素 for int i=0;i=m;i+ coutlisti; coutendl; 名师归纳总结 - - - - - - -第 7 页,共 18 页精选学习资料 - - - - - - - - - e

18、lse / 仍有多个元素待排列,递归产生排列 for int i=k; i=m; i+ swaplistk,listi; permlist,k+1;m; swaplistk,listi; 5. 给定已按升序排好序的 素 x；n 个元素 a0:n-1,现要在这 n 个元素中找出一特定元据此简洁设计出二分搜寻算法：template int BinarySearchType a, const Type& x, int l, int r while l=r int m = l+r/2 ; if x = am return m; if x am r = m-1; else l = m+1; return

19、 -1; 6、合并排序描述如下：template void MergesortType a , int left, int right if leftright int i= left+right /2; Mergesorta, left, i ; 名师归纳总结 - - - - - - -第 8 页,共 18 页精选学习资料 - - - - - - - - - Mergesorta, i+1, right ; Mergea,b, left,i,right ;/合并到数组 b Copya,b, left,right ; /复制到数组 a 7、分治法求最大、最小元 template void So

20、rtableList:MaxMinint i, int j, T& max, T& min const / 前置条件： i 和 j,0ij表长,是表的下标范畴的界 T min1, max1; if i=j max=min=li; /表中只有一个元素时else if i=j-1 /表中有两个元素时 if lilj max=lj; min=li; else max=li; min=lj; else /表中多于两个元素时 int m=i+j/2; /对半分割MaxMini, m, max, min; /求前半部子表中的最大、最小元MaxMinm+1, j, max1, min1 / 求后半部子表中的

21、最大、最小元 if maxmin1 min=min1; /两子表最小元的小者为原表最小元四、问答题 1.用运算机求解问题的步骤：1、问题分析 2、数学模型建立 3、算法设计与挑选 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制名师归纳总结 - - - - - - -第 9 页,共 18 页精选学习资料 - - - - - - - - - 2. 算法定义：算法是指在解决问题时,依据某种机械步骤肯定可以得到问题结果的处理过程3.算法的三要素 （1）操作（ 2）掌握结构（ 3）数据结构4. 算法具有以下 5 个属性 ：有穷性：一个算法必需总是在执行有穷步之后终止,内完成

22、；且每一步都在有穷时间确定性：算法中每一条指令必需有准确的含义；不存在二义性； 只有一个入 口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本 运算执行有限次来实现的；输入：一个算法有零个或多个输入,这些输入取自于某个特定对象的集合；输出：一个算法有一个或多个输出, 这些输出同输入有着某些特定关系的量；5. 算法设计的质量指标：正确性：算法应满意详细问题的需求；可读性：算法应当好读,以有利于读者对程序的懂得；健壮性：算法应具有容错处理, 当输入为非法数据时, 算法应对其作出反应,而不是产生莫名其妙的输出结果；效率与储备量需求： 效率指的是算法执行的时间； 储备量需

23、求指算法执行过 程中所需要的最大储备空间；一般这两者与问题的规模有关；常常采纳的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分 支限界法 6. 迭代法 : 也称“ 辗转法” ,是一种不断用变量的旧值递推出新值的解决问题的方法；7. 利用迭代算法解决问题,需要做好以下三个方面的工作：1 、确定迭代模型； 在可以用迭代算法解决的问题中,至少存在一个直接或 间接地不断由旧值递推出新值的变量,这个变量就是迭代变量；名师归纳总结 - - - - - - -第 10 页,共 18 页精选学习资料 - - - - - - - - - 2 、建立迭代关系式； 所谓迭代关系式, 指如何从变量的前一个值

24、推出其下一个值的公式（或关系）；迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成；3 、对迭代过程进行掌握； 在什么时候终止迭代过程？这是编写迭代程序必须考虑的问题； 不能让迭代过程无休止地重复执行下去；分为两种情形： 一种是所需的迭代次数是个确定的值,迭代过程的掌握通常可 可以运算出来； 另一种是所需的迭代次数无法确定； 对于前一种情形, 可以构建一个固定次数的循环来实 现对迭代过程的掌握； 对于后一种情形, 需要进一步分析出用来终止迭代过程的 条件；8. 分治法的基本思想是：将一个规模为 n 的问题分解为 k 个规模较小的子问题,这些子问题相互独立 且与原问题相同；

25、 递归地解这些子问题, 然后将各个子问题的解合并得到原问题 的解；9.分治法所能解决的问题一般具有以下几个特点：（1）该问题的规模缩小到肯定的程度就可以简洁地解决；（2）该问题可以分解为如干个规模较小的相同问题,即该问题具有 最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的,即子问题之间不 包含公共的子问题；10、分治法的基本步骤 分治法在每一层递归上都有三个步骤：（1）分解：将原问题分解为如干个规模较小,相互独立,与原问题 形式相同的子问题；（2）解决：如子问题规模较小而简洁被解决就直接解,否就递归地 解各个子问题；（3）合

26、并：将各个子问题的解合并为原问题的解；11. 动态规划的基本思想前文主要介绍了动态规划的一些理论依据,我们将前文所说的具有明显的阶名师归纳总结 - - - - - - -第 11 页,共 18 页精选学习资料 - - - - - - - - - 段划分和状态转移方程的动态规划称为标准动态规划 ,这种标准动态规划是在研究多阶段决策问题时推导出来的, 具有严格的数学形式, 适合用于理论上的分析；在实际应用中, 很多问题的阶段划分并不明显, 这时假如刻意地划分阶段法反而 麻烦；一般来说, 只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解（即满意最优子化原理）决；,就可以

27、考虑用动态规划解动态规划的实质是 分治思想 和解决冗余 ,因此,动态规划 是一种将问题实例 分解为更小的、 相像的子问题, 并储备子问题的解而防止运算重复的子问题,以 解决最优化问题的算法策略；由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为 更小的、相像的子问题,并通过求解子问题产生一个全局最优解；贪心法的当前挑选可能要依靠已经作出的全部挑选,但不依靠于有待于做出的挑选和子问题；因此贪心法自顶向下,一步一步地作出贪心挑选；而分治法中的各个子问题是独立的（即不包含公共的子问题）,因此一旦递归地 求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解；不足之处：假如当前挑

28、选可能要依靠子问题的解时,就难以通过局部的贪心 策略达到全局最优解； 假如各子问题是不独立的, 就分治法要做很多不必要的工 作,重复地解公共的子问题；解决上述问题的方法是利用动态规划；该方法主要应用于最优化问题,这类 问题会有多种可能的解, 每个解都有一个值, 而动态规划找出其中最优 （最大或 最小）值的解；如存在如干个取最优值的解的话,它只取其中的一个；在求解过 程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划答应这些子问题不独立,问题）也答应其通过自身子问题的解作出挑选,（亦即各子问题可包含公共的子 该方法对每一个子问题只解一次,并将结果储存起来,

29、防止每次遇到时都要重复运算；因此,动态规划法所针对的问题有一个显著的特点,即它所对应的子问题树 中的子问题出现大量的重复； 动态规划法的关键就在于, 对于重复显现的子问题,只在第一次遇到时加以求解, 并把答案储存起来, 让以后再遇到时直接引用, 不 必重新求解；名师归纳总结 - - - - - - -第 12 页,共 18 页精选学习资料 - - - - - - - - - 12、动态规划算法的基本步骤设计一个标准的动态规划算法,通常可按以下几个步骤进行：（1）划分阶段：依据问题的时间或空间特点,把问题分为如干个阶段；留意这如干个阶段肯定要是有序的或者是可排序的（即无后向性）动态规划求解；,否

30、就问题就无法用（2）挑选状态：将问题进展到各个阶段时所处于的各种客观情形用不同的状态 表示出来；当然,状态的挑选要满意无后效性；（3）确定决策并写出状态转移方程：之所以把这两步放在一起,是由于决策和 状态转移有着自然的联系, 状态转移就是依据上一阶段的状态和决策来导出本阶 段的状态； 所以,假如我们确定了决策, 状态转移方程也就写出来了； 但事实上,我们常常是反过来做,依据相邻两段的各状态之间的关系来确定决策；（4）写出规划方程 （包括边界条件）：动态规划的基本方程是规划方程的通用形 式化表达式；一般说来,只要阶段、状态、决策和状态转移确定了,这一步仍是比较简洁的；动态规划的主要难点在于理论上

31、的设计, 一旦设计完成,实现部分就会特别简洁；依据动态规划的基本方程可以直接递归运算最优值,但是一般将其改为递推计 算；实际应用当中常常不显式地依据上面步骤设计动态规划,而是按以下几个步 骤进行：（1）分析最优解的性质,并刻划其结构特点；（2）递归地定义最优值；（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）运算出最优值；（4）依据运算最优值时得到的信息,构造一个最优解；步骤（1）（3）是动态规划算法的基本步骤；在只需要求出最优值的情形,步 骤（4）可以省略,如需要求出问题的一个最优解,就必需执行步骤（4）；此时,在步骤（ 3）中运算最优值时,通常需记录更多的信息,以便在步骤（4）中,

32、根 据所记录的信息,快速地构造出一个最优解；总结：动态规划实际上就是最优化的问题,是指将原问题的大实例等价于同 一最优化问题的较小实例, 自底向上的求解最小实例, 并将所求解存放起来, 存名师归纳总结 放的结果就是为了预备数据； 与递归相比, 递归是不断的调用子程序求解,是自第 13 页,共 18 页- - - - - - -精选学习资料 - - - - - - - - - 顶向下的调用和求解；13. 分治法与动态规划法的相同点是：将待求解的问题分解成如干个子问题,先求解子问题,然后从这些子问题的 解得到原问题的解；两者的不同点是 ：适合于用动态规划法求解的问题,经分解得到的子问题往 往不是相

33、互独立的； 而用分治法求解的问题, 经分解得到的子问题往往是相互独 立的；14. 回溯法 回溯法也称为摸索法,该方法第一临时舍弃关于问题规模大小的限制,并将 问题的候选解按某种次序逐一枚举和检验；当发觉当前候选解不行能是解时,就 挑选下一个候选解； 假如当前候选解除了仍不满意问题规模要求外,满意全部其他要求时, 连续扩大当前候选解的规模,并连续摸索； 假如当前候选解满意包括问题规模在内的全部要求时, 该候选解就是问题的一个解；在回溯法中, 舍弃当前候选解, 查找下一个候选解的过程称为回溯；摸索的过程称为向前摸索；15. 分支限界法：扩大当前候选解的规模, 以连续这是一种用于求解组合优化问题的排

34、除非解的搜寻算法；类似于回溯法,分 枝定界法在搜寻解空间时, 也常常使用树形结构来组织解空间；然而与回溯法不同的是,回溯算法使用深度优先方法搜寻树结构,而分枝定界一般用宽度优先或最小耗费方法来搜寻这些树； 因此,可以很简洁比较回溯法与分枝定界法的异同；相对而言, 分枝定界算法的解空间比回溯法大得多,溯法胜利的可能性更大；因此当内存容量有限时, 回算法思想：分枝限界（branch and bound）是另一种系统地搜寻解空间的方法,它与回溯法的主要区分在于对E-节点的扩充方式；每个活节点有且仅有一次机会变成 E-节点；当一个节点变为 E-节点时,就生成从该节点移动一步即可到达的全部新节点；在生成

35、的节点中,抛弃那些不行能导出（最优）可行解的节点,其余节点加入活节点表,然后从表中挑选一个节点作为下一个 E-节点；从活节点表中取出所挑选的节点并进行扩充,束；直到找到解或活动表为空, 扩充过程才结名师归纳总结 - - - - - - -第 14 页,共 18 页精选学习资料 - - - - - - - - - 有两种常用的方法可用来挑选下一个E-节点（虽然也可能存在其他的方法） ：1 先进先出（F I F O） 即从活节点表中取出节点的次序与加入节点的次序相同,因此活节点表的性质与队列相同；2 （优先队列）最小耗费或最大收益法在这种模式中,每个节点都有一个对应的耗费或收益；假如查找一个具有最

36、小耗费的解,就活节点表可用最小堆来建立,下一个 E-节点就是具有最小耗费 的活节点；假如期望搜寻一个具有最大收益的解,就可用最大堆来构造活节点表,下一个 点E-节点是具有最大收益的活节16. 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T 中搜寻问题解的算法；不同点：（1）求解目标不同；（2）搜寻方式不同；（3）对扩展结点的扩展方式不同；（4）储备空间的要求不同；17. 分治法所能解决的问题一般具有的几个特点是：（1）该问题的规模缩小到肯定的程度就可以简洁地解决；（2）该问题可以分解为如干个规模较小的相同问题,即该问题具有最优子 结构性质 ;（3）利用该问题分解出的子问题的解可以合并

37、为该问题的解；（4）原问题所分解出的各个子问题是相互独立的,的子问题；18. 用分支限界法设运算法的步骤是：即子问题之间不包含公共1针对所给问题,定义问题的解空间（对解进行编码）；2确定易于搜寻的解空间结构（按树或图组织解）3以广度优先或以最小耗费（最大收益）优先的方式搜寻解空间,并在搜寻过程中用剪枝函数防止无效搜寻；19. 常见的两种分支限界法的算法框架：名师归纳总结 - - - - - - -第 15 页,共 18 页精选学习资料 - - - - - - - - - （1）队列式 FIFO 分支限界法：依据队列先进先出（节点为扩展节点；FIFO）原就选取下一个（2）优先队列式分支限界法：

38、依据优先队列中规定的优先级选取优先级最高 的节点成为当前扩展节点；20. 回溯法中常见的两类典型的解空间树是子集树和排列树；当所给的问题是从n 个元素的集合 S 中找出满意某种性质的子集时, 相应的解空间树称为子集树；这类子集树通常有2n 个叶结点,遍历子集树需O2n运算时间；当所给的问题是确定n 个元素满意某种性质的排列时, 相应的解空间树称为排列树；这类排列树通常有n.个叶结点；遍历排列树需要On.运算时间；21. 分支限界法的搜寻策略是：在扩展结点处,先生成其全部的儿子结点（分支）,然后再从当前的活结点表中挑选下一个扩展结点； 为了有效地挑选下一扩展结点,加速搜寻的进程, 在每一个活结点

39、处,运算一个函数值（限界）,并依据函数值,从当前活结点表中挑选一个最有利的结点作为扩展结点,使搜寻朝着解空间上有最优解的分支推 进,以便尽快地找出一个最优解；22. 请表达动态规划算法与贪心算法的异同；共同点：都需要最优子结构性质,都用来求有优化问题；不同点：动态规划：每一步作一个挑选 贪心方法：每一步作一个挑选- 依靠于子问题的解；- 不依靠于子问题的解 ；动态规划方法的条件：子问题的重叠性质；可用贪心方法的条件：最优子结构性质；贪心挑选性质；动态规划：自底向上求解；贪心方法：自顶向下求解；可用贪心法时,动态规划方法可能不适用；可用动态规划方法时,贪心法可能不适用；名师归纳总结 - - -

40、- - - -第 16 页,共 18 页精选学习资料 - - - - - - - - - 23. 请说明动态规划方法为什么需要最优子结构性质；答：最优子结构性质是指大问题的最优解包含子问题的最优解；动态规划方法是自底向上运算各个子问题的最优解,即先运算子问题的最优解,然后再利用子问题的最优解构造大问题的最优解,24. 请说明：1 优先队列可用什么数据结构实现？2 优先队列插入算法基本思想？3 优先队列插入算法时间复杂度？答：（1）堆；（2）在小根堆中,将元素 x 插入到堆的末尾,因此需要最优子结构 . 然后将元素 x 的关键字与其双亲的关键字比较,如元素 x 的关键字小于其双亲的关键字,就将元素 x 与其双亲交换,然后再将元素 x 与其新双亲的关键字相比,直到元素 x 的关键字大于双亲的关键字,或元素 x 到根为止；（3）O log n 25. 衡量算法时间效率的方法有哪两种？请表达；答：有事前分析法和事后分析法两种；事后分析法：先将算法用程序设计语言实现,然后度量程序的运行时间；事前分析法：算法的时间效率是问题规模的函数,假如,随着问题规模 n 的增长,算法执行时间的增长率和函数 fn的增长率相同,就可记作：Tn= fn 称 Tn为算法的渐进时间复杂度；简称时间复杂度；26. 在算法复杂性分析中,O、 、 这三个记号