算法分析与设计期末复习题目一、选择题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、下列不属于影响程序执行时间的因素有哪些（ 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、回溯算法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.回溯法17．用贪心法设计算法的关键是（ B ）。

A.将问题分解为多个子问题来分别处理B.选好最优量度标准C.获取各阶段间的递推关系式D.满足最优性原理18.找最小生成树的算法Kruskal 的时间复杂度为（ D ）（其中n 为无向图的结点数，m 为边数）A ．O(n 2)B ．O(mlogn)C ．O(nlogm)D ．O(mlogm)19.回溯法搜索状态空间树是按照（C ）的顺序。

A.中序遍历B.广度优先遍历C.深度优先遍历D.层次优先遍历20.采用广度优先策略搜索的算法是（ A ）。

A.分支界限法B.动态规划法C.贪心法D.回溯法21.函数32n +10nlogn 的渐进表达式是( B ).( 2n ) B. O( 32n ) C. O( nlog n ) D. O( 10nlog n )22.二分搜索算法的时间复杂性为（ C ）。

(2n ) (n ) (n log ) D. O(n n log )23、快速排序算法的时间复杂性为（ D ）。

(2n ) (n ) (n log ) D. O(n n log )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 小元素问题中，若使用快速排序算法思想，运用分治算法对n 个元素进行划分，应如何选择划分基准下面 (D) 答案解释最合理。

A ．随机选择一个元素作为划分基准B ．取子序列的第一个元素作为划分基准C ．用中位数的中位数方法寻找划分基准D ．以上皆可行。

但不同方法，算法复杂度上界可能不同28. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。

这要求原问题和子问题 ( C ) 。

A ．问题规模相同，问题性质相同B ．问题规模相同，问题性质不同C ．问题规模不同，问题性质相同D ．问题规模不同，问题性质不同29、下面是贪心算法的基本要素的是（ C ）。

A 、重叠子问题B 、构造最优解C 、贪心选择性质D 、定义最优解30. 函数n n 1032 的渐进表达式是（ D ）。

A. O(23n ) B. O(3) C. O(n 10) (2n )二、填空题1、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。

2、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N 皇后问题 。

3.贪心算法基本要素有 最优度量标准 和 最优子结构 。

4.回溯法解旅行售货员问题时的解空间树是排列树。

5.二分搜索算法是利用分治策略实现的算法。

6.算法的复杂性有时间复杂性和空间复杂性之分。

7、程序是算法用某种程序设计语言的具体实现。

8、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。

9.矩阵连乘问题的算法可由动态规划设计实现。

10．回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。

11.任何可用计算机求解的问题所需的时间都与其规模有关。

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++) x[i]=0;float c=M;for (i=1;i<=n;i++) {if (w[i]>c) break;x[i]=1;c - =w[i];}if (i<=n) x[i]=c/w[i];}14．下面算法的基本运算是加法（或：赋值）运算，该算法中第4步执行了 2n-1 次。

算法 COUNT输入：正整数n（n=k2）。

输出：count的值。

1. count=02. while n>=13. for j=1 to n4. count =count+15. end for6. n=n/27. end whileend COUNT15.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。

16.快速排序、插入排序和选择排序算法中，快速排序算法是分治算法。

17. 下面算法的基本语句是__ S = S + i*j;____, 算法的时间复杂度是___O(2n)_____int fun(int n){int S = 0;for (int i=1; i <=n; i++ )for(int j=1; j<n – i ; j++)S = S + i*j;return S;}18. 最小生成树的prim算法应用的是贪心算法思想。

19. 分治算法的基本步骤包括分解子问题，递归求解子问题，合并解20. 归并排序和快速排序在平均情况下的时间复杂度都是O（nlogn）,但是最坏情况下两种算法有区别，其中归并排序为 O（nlogn），快速排序为_O(2n)二、算法设计1．下面是用回溯法求解图的m着色问题的算法（求出所有解）。

图的m着色问题：给定一个无向连通图G和m种颜色，给图G的所有顶点着色，使得任何两相邻顶点的颜色不同。

已有函数color(k)用于在前k-1个顶点已着色的情况下，判断第k个顶点是否可着颜色x[k]；是则返回true, 否则返回false。

输入：正整数m, n和含n个顶点的无向连通图G的邻接矩阵graph。

输出：图G的m着色问题的所有解, 若无解，则输出no solution。

flag=falsek=1; x[1]=0while k>=1while (1)x[k]=x[k]+1if color(k) thenif (2) thenflag=true; output x[1..n]elsek= (3)(4)end ifend ifend while(5)end whileif not flag then output “no solution”end m-COLORING(1) x[k]<m (2) k=n (3) k+1(4) x[k]=0 (5) k=k-12．下面是求解矩阵链乘问题的动态规划算法。

矩阵链乘问题：给出n 个矩阵M 1, M 2, …, M n , M i 为r i ⨯r i+1阶矩阵，i=1,2, …, n ，求计算M 1M 2…M n 所需的最少数量乘法次数。

记 M i, j =M i M i+1…M j , i<=j 。

设C[i, j], 1<=i<=j<=n, 表示计算M i, j 的所需的最少数量乘法次数，则⎪⎩⎪⎨⎧<++==+≤<j i , }r r r j] C[k,1]-k ,i [C {min j i , 0j] ,i [C 1j k i jk i算法 MATCHAIN输入：矩阵链长度n, n 个矩阵的阶r[1..n+1], 其中r[1..n]为n 个矩阵的行数，r[n+1]为第n 个矩阵的列数。

输出：n 个矩阵链乘所需的数量乘法的最少次数。

for i=1 to n C[i, i]= （1）for d=1 to n-1for i=1 to n-dj= (2)C[i, j]= ∞for k=i+1 to jx= (3)if x<C[i, j] then(4) =xend ifend forend forend forreturn (5)end MATCHAIN(1) 0 (2) i+d (3) C[i, k-1]+C[k, j]+r[i]*r[k]*r[j+1] (4) C[i, j] (5) C[1, n]3.下面是用回溯法解n皇后问题的算法（求出所有解）。