算法期末复习题final

1、算法分析与设计期末复习题目一. 选择题1 -下列算法中通常以自底向上的方式求解最优解的是)oA、备忘录法 B.动态规划法C.贪心法D.回溯法2、衡量一个算法好坏的标准是（C ）。A运行速度快B占用空间少C时间复杂度低D代码短3、以下不可以使用分治法求解的是（D ）oA棋盘覆盖问题B选择问题C归并排序D 0/1背包问题4. 下列是动态规划算法基本要素的是（A、定义最优解B、构造最优解题重叠性质5. 采用广度优先策略搜索的算法是（A、分支界限法B、动态规划法法6. 合并排序算法是利用（ AC.算出最优解子问A)oC贪心法D、回溯）实现的算法。A、分治策略B、动态规划法 C贪心法D、回溯法7下列不属

2、于影响程序执行时间的因素有哪些（C ）A. 算法设计的策略B问题的规模C.编译程序产生的机器代码质量D.计算机执行指令的速度8、使用分治法求解不需要满足的条件是（A ）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解9、下面问题（B ）不能使用贪心法解决。A单源最短路径问题B N皇后问题C最小花费生成树问题D背包问题10. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B）A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解11.以深度优先方式系统搜索问题解的算法称为(D )。A、分支界限算法B、概率算法C、贪心算法D、回溯算

3、法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. 二分搜索算法是利用（A）实现的算法。A.分治法B.动态规划法C.贪心法D.回溯法1

4、7. 用贪心法设计算法的关键是（B ）。A. 将问题分解为多个子问题来分别处理B. 选好最优量度标准C. 获取各阶段间的递推关系式D. 满足最优性原理1&找最小生成树的算法Kruskal的时间复杂度为（D ）（其中n为无向图 的结点数，m为边数）A. 0（n2） B. 0 （mlogn） C. 0 （nlogm） D. 0（mlogm）19.回溯法搜索状态空间树是按照（C ）的顺序。A中序遍历B.广度优先遍历C.深度优先遍历D.层次优先遍历20采用广度优先策略搜索的算法是（A ）oA.分支界限法B.动态规划法C.贪心法D.回溯法21.函数32n+10nlogn的渐进表达式是（B ） (

5、2n) B. 0( 32°)C. 0( nlogn )D. 0( 10nlogD)Oglog")22二分搜索算法的时间复杂性为（C ）o （心（“）（l°g"） D.23. 快速排序算法的时间复杂性为（D ）（心 （“）（10g,?） I24. 算法是由若干条指令组成的有穷序列，而且满足以下性质（D ） A.输入：有0个或多个输入 B.输出：至少有一个输出C.确定性：指令清晰，无歧义D.有限性：指令执行次数有限，而且执行 时间有限A.（3） B.（4） C.（4） D.25. 背包问题的贪心算法所需的计算时间为（B ） A. 0 （n2n）B. 0 （n

6、logn） （2n）（n）26下列算法中不能解决0/1背包问题的是（A ）A贪心法B动态规划C回溯法D分支限界法27. 在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运 用分治算法对n个元素进行划分，应如何选择划分基准下面（D）答案解释最 合理。A. 随机选择一个元素作为划分基准B. 取子序列的第一个元素作为划分基准C. 用中位数的中位数方法寻找划分基准D.以上皆可行。但不同方法，算法复杂度上界可能不同28. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的 子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要 求原问题和子问题（C ）。A.问题规模相同

7、，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同29. 下面是贪心算法的基本要素的是（C）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解30. 函数加+5的渐进表达式是（D ）。A. 0（3心B. 0（3）C. 0（1°）（爪）二、填空题1、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需 要排序的是一动态规划,需要排序的是_回溯法,分支限界法 O2、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目 标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用 约束条件和目

8、标函数的界进行裁剪的是 0/1背包问题,只使用约束条件 进行裁剪的是 N皇后问题 。3. 贪心算法基本要素有最优度量标准和最优子结构。4. 回溯法解旅行售货员问题时的解空间树是排列树 。5. 二分搜索算法是利用分治策略实现的算法。6. 算法的复杂性有时迥寝杂性和 空间复杂性之分。7、程序是用某种程序设计语言的具体实现。8、算法的“确定性”指的是组成算法的每条 指令 是清晰的,无歧义的。9. 矩阵连乘问题的算法可由 动态规划 设计实现。10. 回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数O11. 任何可用计算机求解的问题所需的时间都与其有关。12. 快速排序算法的性能取决于划分的

9、对称性。13. 背包问题的贪心算法void Knapsack (in t n, float M, floa t v,floa t w, floa t x)Sort (n, v, w);int i;for (i=l;i<=n;i+) xi=0;float c=M;for (i=l;i<=n;i+) if (wi>c) break;xi=l;c - =wi;辻(i二n) xi二c/wi;14. 下面算法的基本运算是加法(或：赋值)运算，该算法中第4步 执行了_2n-l次。算法COUNT输入：正整数n (n=2k )o输出：count的值。1. count=02. wh订e n&g

10、t;=l3. for j=lto n4. count =count+15. end for6. n=n/27. end whileend COUNT15算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性 和有限性四条性质。16快速排序.插入排序和选择排序算法中，快速排序算法是分治 算法。17.下面算法的基本语句是_ S二S + i*j：_,算法的时间复杂度是0(心int fun(int n)int S = 0;for (int i=l; i <=n; i卄)for(int j=l; j<n - i ; j+)S = S + i*j;return S;18. 最小生成树的M

11、im算法应用的是贪心算法思想。19. 分治算法的基本步骤包括 分解子问题，递归求解子问题，合并解20. 归并排序和快速排序在平均情况下的时间复杂度都是0 (nlogn),但是 最坏情况下两种算法有区别，其中归并排序为_0 (nlogn),快速排序为 o(2)二、算法设计1. 下面是用回溯法求解图的m着色问题的算法(求出所有解)。图的m着色问题：给定一个无向连通图G和m种颜色，给图G的所有顶点着 色，使得任何两相邻顶点的颜色不同。已有函数color (k)用于在前k-1个顶点 已着色的情况下，判断第k个顶点是否可着颜色xk；是则返回true,否则返 回 false。输入：正整数m, n和含n个顶

12、点的无向连通图G的邻接矩阵graph。输出：图G的m着色问题的所有解，若无解，则输出no solutiono flag=falsek=l; xl=0while k>=lwhile (1)xk=xk+lif color (k) thenif thenflag=true; output xl. nelsek=(3)end ifend ifend whileend whileif not flag then output "no solution"end m-COLORING(1) x k <m(4) xk=0(3) k+1k=n(5) k=k-l2. 下面是求解矩阵

13、链乘问题的动态规划算法。矩阵链乘问题：给出n个矩阵Mx, M2,此，肚为阶矩阵，i=l,2, n,求计算所需的最少数量乘法次数。记 Mi.产MiMi+严虬，i<=jo 设 Ci, j, l<=i<=j<=n,表示计算的所需的最少数量乘法次数，则JO,i = jCH，jminCi,k-l+Ck ” + 叭如 ,i< jI igj算法 MATCHAIN输入：矩阵链长度n, n个矩阵的阶rl.n+l,其中rl.n为n个矩 阵的行数，rn+l为第n个矩阵的列数。输出：n个矩阵链乘所需的数量乘法的最少次数。for i=l to n Ci, i=Q)for d=l to nT

14、for i=l to ndj= (2)Ci, j= 8for k=i+l to jx=if x<Ci, j then =xend辻end forend forend forreturn(5)end MATCHAIN(1) 0(2) i+d(3) Ci, k-l+Ck,刃 +ri*rk*rj+l Ci, j (5) Cl, n3. 下面是用回溯法解n皇后问题的算法(求出所有解)。n皇后问题：在nxn棋盘上放置n个皇后使得任何两个皇后不能互相攻 击。(如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻 击。)算法 NQUEENS输入：正整数n。输出：n皇后问题的所有解xl. .n

15、,若无解，则输出No solution。flag=falsek=l ;xl=0while (1)while xk<nx k二(2)if place(k) thenif k=n thenflag=true； output xl. nelsek= (3)(41end ifend辻end whileend whileif not flag then output "No solution” end NQUEENS过程 place (k)递归的快速排序算法：template <class Type>void Quicksort (Type a , int low, int

16、high) if (1)int i=Partition(a, low, high); Quicksort (a, low, i-1);(2);解：(1) low < high(2) QuickSort (a, i+1, high)5. n后问题的递归的回溯算法-设己经存在全局变量n代表皇后个数。void Queen:Backtrack(int t) if (1) )sum+;用动态规划法求如下0/1背包问题的最优解：有5个物品,其重量分别为(3, 2,1,4,5),价值分别为(25, 20,15, 40, 50),背包 容量为6.写出求解过程(设计表格和填写表格)解：设计一个二维表V(i

17、, j)表示将前i个物品装进容量为j的背包所能 获得的最大价值，根据以下递推式填表：若 > j, v(i, j)二 V(i - 1, j)若 Wt <= j, V(i, j) = max V(i-1, j) , V(i-1, j-wi) + vi)j = 0j = 1J = 2j = 3J = 4j = 5j = 6i=00000000i=100025252525i=2002025254545i=30152035404560i=40152035405560i=50152035405565V(5, 6)即为问题的最优解，最大价值为65。经过回溯得到物品组合为第3和第5个物品装入背包。

18、4. 归并排序算法对下列实例排序，写出算法执行过程。A=(48, 12,61,3, 5, 19, 32, 7)解：拆分:48, 12, 61, 34& 1261, 348126135, 19, 32, 75,1932, 7519327合并：12, 483, 613, 12,4& 613, 5, 7,12,5,197, 325, 7, 19, 3219, 32, 4&615、简述分治法的基本思想。答分治法的基本思想是将一个规模为n的问题分解为k个规模较小的 子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。 如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下 去，直到问题