《2021年算法期末复习题final.pdf》由会员分享，可在线阅读，更多相关《2021年算法期末复习题final.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与设计期末复习题目一、选择题1下列算法中通常以自底向上的方式求解最优解的是（B）。A、备忘录法B、动态规划法C、贪心法D、回溯法2、衡量一个算法好坏的标准是（C）。A 运行速度快B 占用空间少C 时间复杂度低D 代码短3、以下不可以使用分治法求解的是（D）。A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题4下列是动态规划算法基本要素的是（D）。A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质5采用广度优先策略搜索的算法是（A）。A、分支界限法B、动态规划法C、贪心法D、回溯法6、合并排序算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法7、
2、下列不属于影响程序执行时间的因素有哪些（C）A算法设计的策略B问题的规模C编译程序产生的机器代码质量D计算机执行指令的速度8、使用分治法求解不需要满足的条件是（A）。A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解9、下面问题（B）不能使用贪心法解决。A 单源最短路径问题B N皇后问题C 最小花费生成树问题D 背包问题精品w o r d 学习资料 可编辑资料-精心整理-欢迎下载-第 1 页，共 11 页10.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解11.以深度
3、优先方式系统搜索问题解的算法称为(D)。A、分支界限算法B、概率算法C、贪心算法D、回溯算法12.实现最长公共子序列利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法13下列算法具有最优子结构的算法是（D）A概率算法B回溯法C分支限界法D动态规划法14.算法分析是（C）A.将算法用某种程序设计语言恰当地表示出来B.在抽象数据集合上执行程序,以确定是否会产生错误的结果C.对算法需要多少计算时间和存储空间作定量分析D.证明算法对所有可能的合法输入都能算出正确的答案15 衡量一个算法好坏的标准是（C）16 A.运行速度快B.占用空间少C.时间复杂度低D.代码短16.二分搜索算法是利用
4、（A）实现的算法。A.分治法B.动态规划法 C.贪心法 D.回溯法17用贪心法设计算法的关键是（B）。A.将问题分解为多个子问题来分别处理B.选好最优量度标准C.获取各阶段间的递推关系式D.满足最优性原理18.找最小生成树的算法Kruskal的时间复杂度为（D）（其中 n 为无向图的结点数，m 为边数）AO(n2)BO(mlogn)CO(nlogm)DO(mlogm)19.回溯法搜索状态空间树是按照（C）的顺序。A.中序遍历B.广度优先遍历精品w o r d 学习资料 可编辑资料-精心整理-欢迎下载-第 2 页，共 11 页文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5
5、M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP
6、7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN
7、1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4
8、C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:
9、CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10
10、HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 Z
11、V4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4C.深度优先遍历D.层次优先遍历20.采用广度优先策略搜索的算法是（A）。A.分支界限法B.动态规划法C.贪心法D.回溯法21.函数 32n+10nlogn的渐进表达式是(B).(2n)B.O(32n)C.O(nlogn)D.O(10nlogn)22.二分搜索算法的时间复杂性为（C）。(2n)(n)(nlog)D.O(nnlog)2
12、3、快速排序算法的时间复杂性为（D）。(2n)(n)(nlog)D.O(nnlog)24、算法是由若干条指令组成的有穷序列，而且满足以下性质（D）A.输入：有 0 个或多个输入B.输出：至少有一个输出C.确定性：指令清晰，无歧义D.有限性：指令执行次数有限，而且执行时间有限A.(1)(2)(3)B.(1)(2)(4)C.(1)(3)(4)D.(1)(2)(3)(4)25、背包问题的贪心算法所需的计算时间为（B）A.O（n2n）B.O（nlogn）（2n）（n）26.下列算法中不能解决0/1 背包问题的是（A）A 贪心法 B 动态规划C 回溯法D 分支限界法27.在寻找 n 个元素中第 k 小元
13、素问题中，若使用快速排序算法思想，运用分治算法对 n 个元素进行划分，应如何选择划分基准下面(D)答案解释最合理。A随机选择一个元素作为划分基准B取子序列的第一个元素作为划分基准C用中位数的中位数方法寻找划分基准D以上皆可行。但不同方法，算法复杂度上界可能不同精品w o r d 学习资料 可编辑资料-精心整理-欢迎下载-第 3 页，共 11 页文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码
14、:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10
15、 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8
16、ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档
17、编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U
18、10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M
19、8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4
20、文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A428.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题(C)。A问题规模相同，问题性质相同B问题规模相同，问题性质不同C问题规模不同，问题性质相同D问题规模不同，问题性质不同29、下面是贪心算法的基本要素的是（C）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解30.函数nn1032的渐进表达式是（D）。A.O(23n)B.O(3)C.O(n10)(2n)二、填空题1、解决 0/1 背包问题可以使用动态规划
21、、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。2、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和 0/1 背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1 背包问题，只使用约束条件进行裁剪的是N 皇后问题。3.贪心算法基本要素有最优度量标准和 最优子结构。4.回溯法解旅行售货员问题时的解空间树是排列树。5.二分搜索算法是利用分治策略实现的算法。6.算法的复杂性有时间复杂性和空间复杂性之分。7、程序是算法用某种程序设计语言的具体实现。8、算法的“确定性”指的是组成算法的每条指令是清晰的
22、，无歧义的。9.矩阵连乘问题的算法可由动态规划设计实现。10回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。精品w o r d 学习资料 可编辑资料-精心整理-欢迎下载-第 4 页，共 11 页文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV
23、4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码
24、:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10
25、 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8
26、ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档
27、编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U
28、10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A411.任何可用计算机求解的问题所需的时间都与其规模有关。
29、12.快速排序算法的性能取决于划分的对称性。13.背包问题的贪心算法void Knapsack(int n,float M,float v,float w,float x)Sort(n,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=13.for j=1 to n4.count=count+15.end for6.n=n/27.end while end COUNT精品w o r d 学习资料 可编辑资料-精心整理-欢迎下载-第 5 页，共 11 页文档编码:CP7I9C8N2U10 HN1P8
30、T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M
31、9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7
32、I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1
33、P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C
34、5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:C
35、P7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 H
36、N1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A415.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。16.快速排序、插入排序和选择排序算法中，快速排序算法是分治算法。17.下 面 算 法 的 基 本 语 句 是 _ S=S+i*j;_,算 法 的 时 间 复 杂 度 是_O(2n)_int fun(int n)int S=0
37、;for(int i=1;i=n;i+)for(int j=1;j=1 while(1)xk=xk+1if color(k)then if(2)then flag=true;output x1.nelse k=(3)(4)end ifend if end while(5)end whileif not flag then output“no solution”end m-COLORING(1)xkm(2)k=n(3)k+1(4)xk=0(5)k=k-12下面是求解矩阵链乘问题的动态规划算法。矩阵链乘问题：给出 n 个矩阵 M1,M2,Mn,Mi 为 riri+1阶矩阵，i=1,2,n，求计算
38、M1M2Mn所需的最少数量乘法次数。记 Mi,j=MiMi+1Mj,i=j。设 Ci,j,1=i=j=n,表示计算 Mi,j的所需的最少数量乘法次数，则ji,rr rjCk,1-k,i Cminji,0j,i C1jkijki算法 MATCHAIN精品w o r d 学习资料 可编辑资料-精心整理-欢迎下载-第 7 页，共 11 页文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9
39、C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8
40、T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M
41、9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7
42、I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1
43、P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C
44、5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:C
45、P7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4输入：矩阵链长度n,n 个矩阵的阶 r1.n+1,其中 r1.n为 n 个矩阵的行数，rn+1为第 n 个矩阵的列数。输出：n 个矩阵链乘所需的数量乘法的最少次数。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 MATCHAIN(1)0(2)i+d(3)Ci,k-1+Ck,j+ri*rk*rj+1(
46、4)Ci,j(5)C1,n3.下面是用回溯法解n 皇后问题的算法（求出所有解）。n 皇后问题：在 n x n 棋盘上放置 n 个皇后使得任何两个皇后不能互相攻击。（如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻击。）算法 NQUEENS输入：正整数 n。输出：n 皇后问题的所有解x1.n,若无解，则输出 No solution。flag=false 精品w o r d 学习资料 可编辑资料-精心整理-欢迎下载-第 8 页，共 11 页文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV
47、4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码
48、:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10
49、 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8
50、ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档编码:CP7I9C8N2U10 HN1P8T7K2M8 ZV4C5M9K4A4文档