下载文档原格式
决战2021：高考数学专题精练〔十二〕算法
一、选择题
1．假如执行右面的程序框图，那么输出的s 是 〔 〕 A ．2550 B ．2550- C ．2548 D ．2552-
2．如右图所示的程序框图的输出结果是 〔 〕
A ． 2
B ． 4
C ． 8
D ． 16
3．数列{}n a 满足*111
33,(2,)n n n a a a n n N a --==-
≥∈，
记M 为以下程序框图的输出结果，那么行列式1 1 M
-1 1 M 1 1 1
中元素1-的代数余子式的值是〔 〕
A ． 2
B ．2-
C ．132
D ．13
2
-
二、填空题
1．假如执行下面的程序框图，那么输出的S =_________ ．
2．运行如下图的程序流程图，那么输出I 的值是_________________．
〔第2题图〕 〔第3题图〕
〔第1题图〕
k=，那么输出的S=________________．3．执行右面的程序框图，假如输入的50
4．根据右面的框图，打印的最后一个数据是．
第13局部：算法
参考答案
一、选择题
1－3CCA
二、填空题
1．10000
2．7
3．2548
4．63。
算法考试题目及答案详解一、单项选择题（每题 2 分，共 10 题）1. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序答案：C2. 在图的遍历算法中，深度优先搜索（DFS）使用的栈是什么类型的栈？A. 后进先出栈B. 先进后出栈C. 先进先出栈D. 随机顺序栈答案：B3. 哈希表中解决冲突的线性探测法中，如果当前槽位已满，下一个槽位的计算公式是什么？A. hash(i) + 1B. hash(i) - 1C. hash(i) % table_sizeD. hash(i) / table_size答案：A4. 动态规划和贪心算法的主要区别是什么？A. 贪心算法每一步都做出最优选择，而动态规划不是B. 动态规划每一步都做出最优选择，而贪心算法不是C. 动态规划需要记忆化，贪心算法不需要D. 动态规划需要回溯，贪心算法不需要答案：B5. 在二叉树中，哪种类型的树可以保证左子树上所有节点的值都小于它的根节点？A. 随机二叉树B. 完全二叉树C. 平衡二叉树D. 二叉搜索树答案：D6. 以下哪个算法是用于解决最近公共祖先问题的？A. 快速幂算法B. KMP算法C. 并查集D. 拓扑排序答案：C7. 以下哪个算法是用于解决最小生成树问题的？A. 迪杰斯特拉算法B. 弗洛伊德算法C. 克鲁斯卡尔算法D. 普里姆算法答案：C8. 在大O表示法中，O(1)表示什么？A. 常数时间复杂度B. 对数时间复杂度C. 线性时间复杂度D. 二次时间复杂度答案：A9. 以下哪个算法是用于解决最长公共子序列问题的？A. 动态规划B. 贪心算法C. 深度优先搜索D. 广度优先搜索答案：A10. 以下哪个算法是用于解决背包问题的？A. 动态规划B. 贪心算法C. 深度优先搜索D. 广度优先搜索答案：A二、多项选择题（每题 2 分，共 10 题）1. 以下哪些算法属于图算法？A. 深度优先搜索B. 广度优先搜索C. 快速排序D. 迪杰斯特拉算法答案：A, B, D2. 以下哪些数据结构可以用于实现哈希表？A. 数组B. 链表C. 树D. 图答案：A, B, C3. 以下哪些算法是用于字符串匹配的？A. KMP算法B. Rabin-Karp算法C. 快速排序D. 深度优先搜索答案：A, B4. 以下哪些算法是用于图的遍历？A. 深度优先搜索B. 广度优先搜索C. 快速幂算法D. 拓扑排序答案：A, B, D5. 以下哪些算法是用于解决动态规划问题的？A. 斐波那契数列B. 最长公共子序列C. 快速排序D. 最小生成树答案：A, B6. 以下哪些算法是用于解决排序问题的？A. 快速排序B. 归并排序C. 深度优先搜索D. 拓扑排序答案：A, B7. 以下哪些算法是用于解决图的连通性问题的？A. 深度优先搜索B. 广度优先搜索C. 迪杰斯特拉算法D. 克鲁斯卡尔算法答案：A, B8. 以下哪些算法是用于解决最短路径问题的？A. 迪杰斯特拉算法B. 弗洛伊德算法C. 快速幂算法D. 拓扑排序答案：A, B9. 以下哪些算法是用于解决字符串匹配问题的？A. KMP算法B. Rabin-Karp算法C. 快速排序D. 深度优先搜索答案：A, B10. 以下哪些算法是用于解决动态规划问题的？A. 斐波那契数列B. 最长公共子序列C. 快速排序D. 最小生成树答案：A, B三、判断题（每题 2 分，共 10 题）1. 快速排序的平均时间复杂度是O(n log n)。
填空题：1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性：确定性有穷性可行性0个或多个输入一个或多个输出2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度局低。
3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个(最优)解6.动态规划算法的基本思想是将待求解问题分解成若干子问题先求解子问题，然后从这些子问题的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为回溯法。
8.0-1背包问题的回溯算法所需的计算时间为o(n*2"),用动态规划算法所需的计算时间为o(min{nc, 2n})。
9.动态规划算法的两个基本要素是最优子结构和重叠子问题。
10.二分搜索算法是利用动态规划法实现的算法。
11.一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。
12.出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。
13.动态规划算法有一个变形方法备忘录方法。
这种方法不同于动态规划算法“自底向上"的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。
14.这种不断回头寻找目标的方法称为回溯法。
15.直接或间接地调用自身的算法称为递归算法。
16.3记号在算法复杂性的表示法中表示渐进确界或紧致界。
17.由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
18.建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。
19.下列各步骤的先后顺序是②③④①。
①调试程序②分析问题③设计算法④编写程序。
20.最优子结构性质的含义是问题的最优解包含其子问题的最优解。
一。
选择题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．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题9. 实现循环赛日程表利用的算法是（ A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（）C、O（2n）D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。
一。
选择题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．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法B、动态规划法C、贪心法 D、回溯法7、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题9. 实现循环赛日程表利用的算法是（ A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先B、最小耗费优先C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法B、动态规划法C、贪心法 D、回溯法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法 D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（nlogn）C、O（2n） D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。
算法考试题目及答案详解一、选择题（每题2分，共10分）1. 下列哪种排序算法的时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 冒泡排序D. 堆排序答案：C2. 在图的遍历中，深度优先搜索（DFS）使用的栈是什么类型的栈？A. 后进先出（LIFO）B. 先进后出（FILO）C. 先进先出（FIFO）D. 后进后出（LILO）答案：A3. 哈希表解决冲突的常用方法不包括以下哪一项？A. 分离链接法B. 开放寻址法C. 链地址法D. 二分查找法答案：D4. 在动态规划问题中，状态转移方程是解决问题的关键，以下哪个不是状态转移方程的特点？A. 递归性B. 确定性C. 重复性D. 随机性答案：D5. 算法的时间复杂度为O(2^n)，这种算法通常被称为什么？A. 指数级算法B. 对数级算法C. 多项式级算法D. 线性算法答案：A二、填空题（每题2分，共10分）1. 在算法分析中，我们通常使用____来表示算法的时间复杂度。
答案：大O符号2. 递归算法的基本结构包括______和______。
答案：基本情况；递归情况3. 在数据库中，索引是用来提高____性能的数据结构。
答案：查询4. 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法，这种算法的特点是______。
答案：局部最优5. 在图论中，一个图的顶点集V和边集E满足V=E时，这个图被称为______。
答案：完全图三、简答题（每题5分，共20分）1. 请简述分治法的基本思想。
答案：分治法的基本思想是将一个难以直接解决的大问题分解成若干个规模较小的相同问题，递归地解决这些子问题，然后再将子问题的解合并得到原问题的解。
2. 动态规划与贪心算法在解决问题时有何不同？答案：动态规划和贪心算法都是解决优化问题的方法。
动态规划适用于具有重叠子问题和最优子结构的问题，它通过存储子问题的解来避免重复计算，而贪心算法则在每一步选择局部最优解，希望得到全局最优解，但并不保证。
算法考试题目及答案详解 一、单项选择题（每题2分，共10题） 1. 在算法中，时间复杂度为O(n^2)的排序算法是： A. 快速排序 B. 归并排序 C. 冒泡排序 D. 堆排序 答案：C
2. 以下哪个算法不是动态规划算法？ A. 斐波那契数列 B. 最长公共子序列 C. 最短路径问题 D. 二分查找 答案：D
3. 哈希表的平均查找时间复杂度是： A. O(n) B. O(1) C. O(log n) D. O(n^2) 答案：B
4. 在图的遍历算法中，深度优先搜索（DFS）使用的是： A. 栈 B. 队列 C. 链表 D. 堆 答案：A
5. 以下哪种数据结构最适合实现LRU缓存淘汰算法？ A. 数组 B. 链表 C. 哈希表 D. 哈希表和双向链表的组合 答案：D
6. 快速排序算法中，选择基准元素的方法不包括： A. 第一个元素 B. 最后一个元素 C. 随机元素 D. 排序好的元素 答案：D
7. 以下哪个不是二叉树的性质？ A. 每个节点最多有两个子节点 B. 左子树的所有节点值小于根节点值 C. 右子树的所有节点值大于根节点值 D. 所有节点的值都相等 答案：D
8. 在算法分析中，大O表示法描述的是： A. 最小时间复杂度 B. 平均时间复杂度 C. 最大时间复杂度 D. 最坏情况下的时间复杂度 答案：D 9. 以下哪个排序算法是稳定的？ A. 快速排序 B. 归并排序 C. 堆排序 D. 冒泡排序 答案：B
10. 算法的时间复杂度为O(n log n)的排序算法是： A. 快速排序 B. 归并排序 C. 冒泡排序 D. 堆排序 答案：B
二、填空题（每题2分，共5题） 1. 在二叉搜索树中，查找一个元素的时间复杂度最坏情况下是________。 答案：O(n)
2. 动态规划与贪心算法的主要区别在于动态规划考虑了________。 答案：子问题的解
一、单项选择题 1、 衡量一个算法好坏的标准是（） A．运行速度快 B.占用空间少 C.时间复杂度低 D.代码短 2、选择排序算法的时间复杂度是（） A．O（n2） B.O（nlogn） C.O（22） D.O（n） 3、快速排序算法的平均时间复杂度是（） A．O（n2） B.O（nlogn） C.O（22） D.O（n） 4、快速排序算法是利用（）实现的算法 A．分治策略 B.动态规划法 C.贪心法 D.回溯法 5、实现合并排序利用的算法是（） A．分治策略 B. 动态规划法 C.贪心法 D.回溯法 6、实现棋盘覆盖算法利用的算法是（） A．分治策略 B. 动态规划法 C.贪心法 D.回溯法 7、下列算法中通常以自底向上的方式求解最优解的是（） A．备忘录法 B. 动态规划法 C.贪心法 D.回溯法 8、最长公共子序列利用的算法是（） A．分治策略 B. 动态规划法 C.贪心法 D.回溯法 9、以下不可以使用分治法求解的是（） A．棋盘覆盖问题 B.选择问题 C.归并排序 D.0/1背包问题 10、下列算法不能解决0/1背包问题的是（） A．贪心法 B.动态规划法 C.回溯法 D.分支限界法 11、下面问题（）不能使用贪心法解决。 A．单源最短路径问题 B.N皇后问题 C．最小花费生成树问题 D.背包问题 12、（）是贪心算法与动态规划算法的共同点 A．重叠自问题 B.构造最优解 C.贪心选择性质 D.最优子结构性质 13、蛮力法所依赖的基本技术是（） A．扫描技术 B.查找技术 C.分治技术 D.动态规划 14、回溯法解旅行售货员问题时的解空间树是（） A．子集树 B.排列树 C.深度优先生成树 D.广度优先生成树 15、下列算法中通常以深度优先方式系统搜索问题的解是（） A．备忘录法 B. 动态规划法 C.贪心法 D.回溯法 16、.采用广度优先策略搜索的算法是（） A.分支限界法 B.动态规划法 C.贪心法 D.回溯法 17、优先队列式分支限界法选取扩展结点的原则是（） A．先进先出 B.后进后出 C.结点的优先级 D.随机 18、回溯法的效率不依赖于下列哪些因素（） A.满足显约束的值的个数 B.计算约束函数的时间 C.计算限界函数的时间 D.确定解空间的时间 19、下面哪种函数是回溯法中为避免无效搜索采取的策略（） A.递归函数 B.剪枝函数 C. 随机数函数 D.搜索函数 20、下设函数f（n）和g（n）是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f（n）≤cg（n），则记作（） A．f（n）=O（g（n）） B.f（n）=Ω（g（n）） C.f（n）=⊙（g（n）） D.f(n)~g(n) 21、下设函数f（n）和g（n）是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f（n）≥cg（n），则记作（）
填空题 动态规划算法的基本要素为：最优子结构性质与重叠子问题性质 1) 算法分析中，记号O表示渐进上界，记号表示渐进下界， 记号表示紧渐进界。 2) 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。 3) 分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树。
所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪
心选择来达到）。 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。 回溯法是指（具有限界函数的深度优先生成法）。 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。 4) 二分搜索算法是利用分治策略实现的算法。 5) 衡量一个算法好坏的标准是时间复杂度低 6) 最长公共子序列算法利用的算法是动态规划法 7) Strassen矩阵乘法是利用分治策略实现的算法 8) 回溯法搜索状态空间树是按照深度优先遍历的顺序。 9) 算法中通常以自底向下的方式求解最优解的是动态规划法 10) 背包问题的贪心算法所需的计算时间为O（nlogn） 11) 0-1背包问题的回溯算法所需的计算时间为O（n2n） 12) 用动态规划算法解决最大字段和问题，其时间复杂性为n 13) 一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性，确定性，可行性，输入，输出。
1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。 2、程序是 算法 用某种程序设计语言的具体实现。 3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。 4.矩阵连乘问题的算法可由 动态规划 设计实现。 6、算法是指解决问题的 一种方法 或 一个过程 。 7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。 8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。 9、以深度优先方式系统搜索问题解的算法称为 回溯法 。 10、数值概率算法常用于 数值问题 的求解。 15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。 16、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 17、矩阵连乘问题的算法可由 动态规划 设计实现。 19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。 21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。 23、大整数乘积算法是用 分治法 来设计的。 26、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 27.快速排序算法是基于 分治策略 的一种排序算法。 30.回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。 33．回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数 。 34.任何可用计算机求解的问题所需的时间都与其 规模 有关。 35.快速排序算法的性能取决于 划分的对称性 。 37. 图的m着色问题可用 回溯 法求解，其解空间树中叶子结点个数是 mn ，解空间树中每个内结点的孩子数是 m 。 简答题
1.用计算机求解问题的步骤： 1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制 2.最优二叉搜索树问题的动态规划算法 void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) { int i,j,k,t,l; for(i=1;i<=n+1;i++) { w[i][i-1]=a[i-1]; m[i][i-1]=0; }
for(l=0;l<=n-1;l++)算法定义： 算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3.算法的三要素 1、操作2、控制结构3、数据结构 4. 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
经常采用的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支限界法 8.分治法的基本思想是： 将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 9.分治法所能解决的问题一般具有以下几个特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
10、分治法的基本步骤 分治法在每一层递归上都有三个步骤： （1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； （2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； （3）合并：将各个子问题的解合并为原问题的解。 11. 动态规划的基本思想 动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。 13. 分治法与动态规划法的相同点是： 将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 14. 回溯法 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 20. 回溯法中常见的两类典型的解空间树是子集树和排列树。 当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间 。 当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。 22. 请叙述动态规划算法与贪心算法的异同。 共同点： 都需要最优子结构性质， 都用来求有优化问题。 不同点： 动态规划：每一步作一个选择—依赖于子问题的解。 贪心方法：每一步作一个选择—不依赖于子问题的解。 动态规划方法的条件：子问题的重叠性质。 可用贪心方法的条件：最优子结构性质；贪心选择性质。 动态规划：自底向上求解； 贪心方法： 自顶向下求解。 可用贪心法时，动态规划方法可能不适用； 可用动态规划方法时，贪心法可能不适用。 23. 请说明动态规划方法为什么需要最优子结构性质。 答： 最优子结构性质是指大问题的最优解包含子问题的最优解。 动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构. 26. 在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么在忽略常数因子的情况 下，O、Ω、Θ分别提供了算法运行时间的什么界 答： 如果存在两个正常数c和N0,对于所有的N≥N0，有|f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。这时我们说f(N)的阶不高于g(N)的阶。 若存在两个正常数C和自然数N0，使得当N ≥ N0时有|f(N)|≥C|g(N)|，记为f(N)=Ω(g(N))。这时我们说f(N)的阶不低于g(N)的阶。 如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)| 则记作 f(N)= (g,(N)) O、Ω、Θ分别提供了算法运行时间的上界、下界、平均 1．用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程。 （2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。 答： (1)
时y0且xj当i,)j]1,c[i1],jmax(c[i,时y0且xj当i,11]j1,c[i0时0或j当i0j]c[i,
iiii
(2) Ｙ Ａ Ｂ Ｃ Ｂ Ｘ 0 0 0 0 Ｂ 0 0 1 1 1 Ｃ 0 0 1 2 2 Ｄ 0 0 1 2 2 Ａ 0 1 1 2 2 最长公共子序列：｛ＢＣ｝
2．对下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω(g (n))或f(n) =θ(g(n))，并简要说明理由。 (1) f(n)=2n； g(n)=n! (2) f(n)=n； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g(n)= 3n (5) f(n)=3n； g(n)=2n 答： (1) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。 (2) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。
