(完整word版)算法分析与设计习题集整理

1、算法分析与设计习题集整理 第一章算法引论 一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂 匪。2、多项式 A(n) =amnm+&n+a0 的上界为 O(nm)。3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。5、计算下面算法的时间复杂度记为：O(n 3)qfor(i=1;i<=n;i+)for(j=1;j<=n;j+)cij=0；for(k=1;k<=n;k+)cij= cij+aik*bkj；6、描述算法常用的方法：自然语言、伪代码、程序设计语言

2、、流程图、盒图、PAD图。7、算法设计的基本要求：正确性 和 可读性。8、计算下面算法的时间复杂度记为：O(n 2)qfor (i = 1; i<n; i+ )y=y+1;for (j =0; j <=2n ; j+ ) x + +;9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法 分析、算法实现、程序调试、结果整理文档编制。10、算法是指解决问题的方法或过程。11、算法由操作、控制结构、数据结构三要素组成。二、简答题：1、按照时间复杂度从低到高排列：O( 4n2)、O( logn)、O( 3n)、O( 20n)、O( 2)、O( n2/3),O(

3、n!)应该排在哪一位？答：O( 2) , O( logn) , O( n2/3), O( 20n) , O( 4n 2) , O( 3 n) , O( n!)2、什么是算法？算法的特征有哪些？答：1)算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。2)特征：1)算法有零个或多个输入；2)算法有一个或多个输出；3)确定性；4)有穷性3、给出算法的定义？何谓算法的复杂性？计算下例在最坏情况下的时间复杂性？for(j=1;j<=n;j+)for(i=1;i<=n;i+)(2)cij=0；(3)for(k=1;k<=n;

4、k+)(4)cij= cij+aik*bkj； (5)答：1)定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。2 )算法的复杂性：指的是算法在运行过程中所需要的资源(时间、空间)多少。 所需资源越多，表明算法的复杂性越高3 )该算法的主要元操作是语句5,其执行次数是n3次。故该算法的时间复杂度记为 O(n3).4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程'T(n) =1 , n =1T(n) =4T(n/2) +n , n >1算法B的时间复杂性满足递归方程3 T")=1 , n =1,若要使得算法 A时间复杂T(n) =aT(n

5、/4) +n , n >1性的阶高于算法 B时间复杂性的阶，a的最大整数值可取多少？答：分别记算法A和算法B的时间复杂性为TA(n)和TB(n),解相应的递归方程得：TA(n) =O(n2)O(n) , a < 4TB(n) = <O(n log n) ,a=4log 4a.0(n) , a >4依题意，要求最大的整数a使彳11TB (n)TA(n)。显然，当a<=4时，TB(n)TA(n)；当 a>4 时，TB(n) < TA(n) u 10g4a m2 u a<42=16。所以，所求的a的最大整数值为15。5、算法分析的目的？答：1)为了对算

6、法的某些特定输入，估算该算法所需的内存空间和运行时间；2)是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。6、算法设计常用的技术？(写5种)答：分治法；回溯法；贪心法；动态规划法分治限界法；蛮力法；倒推法三、算法设计题1、蛮力法：百鸡百钱问题？2、倒推法：穿越沙漠问题？第二章分治算法（1）-递归循环一、填空题：1、直接或间接地调用自身的算法称为递归算法 ，用函数自身给出定义的函数称为 _递归函数 。2、递归方程 和 约束函数（递归终止条件 ）是递归函数的两个要素。二、判断题：1、所有的递归函数都能找到对应的非递归定义。（V ）2、定义递归函数时可以没有初始值。（X ）三、简答题：1

7、、什么是递归算法？递归算法的特点？答：1 ）递归算法：是一个模块（函数、过程）除了可调用其它模块（函数、过程）外，还可 以直接或间接地调用自身的算法。2）递归算法特点：每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）2、比较循环与递归的异同？答：1）相同：递归与循环都是解决“重复操作”的机制。2）不同：就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。每个迭代算法原则上总可以转换成与它等

8、价的递归算法；反之不然。递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活 的重复操作的机制。3、递归算法解题通常有三个步骤？答：1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题 的规模逐渐变小。2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。3）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。四、算法设计题：1、楼梯上有n个台阶，上楼时可以上1步，也可以上2步，设计一递归算法求出共有多少种上楼方法F(n)。写出F(n)的递归表达式？并写出其相应的递归算法？解：写出F(n)的递归表达式分析：到n阶有两种走

9、法：1 ) n-1阶到n阶；2 ) n-2阶到n阶；1n=1F(n) = 2n=2F(n-1) + F(n-2)n>2写出其相应的递归算法？Int F(int n)if(n=1) return 1;else if(n=2)return 2;elsereturn F(n-1)+ F(n-2);2、设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1:每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小

10、的圆盘之上；规则3:在满足移动规则 1和2的前提下，可将圆盘移至 a,b,c中任一塔座上。写出该问题的解题步骤？并写出其相应的递归算法？解：第一步：将n1个盘子看成一个整体，从A移到C;第二步：将第n个盘子移到B;第三步：将n1个盘子看成一个整体，从C移到B;写出其相应的递归算法：void hanoi(int n, int a, int b, int c)if (n > 0)hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a);第二章分治算法(2)分治算法一、填空题：1、在快速排序、插入排序和合并排序算法中，插入排序 算法不是分治算法。2、合

11、并排序算法使用的是分治算法设计的思想。3、二分搜索算法是利用分治算法思想设计的。二、简答题：1、适合用分治算法求解的问题具有的基本特征？答：1)该问题的规模缩小到一定的程度就可以容易解决；2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3 )该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。4)利用该问题分解出子问题解可以合并为该问题解； 2、分治算法基本思想，解题步骤?三、算法设计题：1、改写二分查找算法：设a1n是一个已经排好序的数组，改写二分查找算法，使得当搜索元素 x不在数组 中时，返回小于 x的最大元素位置i,和大于x的最小元素位置j;

12、当搜索元素x在数组中 时，i和j相同，均为x在数组中的位置。并分析其时间复杂度？解：int binsearch( int an, int x ,) /x待查数据int mid, i, j; low=1;int high=n;while(low<=high)mid=(low+high)/2;if(amid=x) return i=j=mid;if(amid>x) high=mid-1; /继续在左边查找else/ (amid<x)low=mid+1; /继续在右边查找 i=right; j=left; return 0; /low 大于high查找区间为空，查找失败计算时间复杂

13、性为O(logn) 2、棋盘覆盖 在一个2kx 2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方 格为一特殊方格，且称该棋盘为一特殊棋盘。 在棋盘覆盖问题中， 要用图示的4种不同形态 的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格， 且任何2个L型骨牌不得重 叠覆盖。求：简述分治算法的基本思想？设计该棋盘覆盖问题的分治算法？计算所设计算法的时间复杂度？（要求写出递推公式）解：分解：将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，以便各个击破，分而治之。对这k个子问题分别求解：如果子问题的规模仍然 不够小,则再划分为k个子问题，如此递归的进行下去， 直到问题规 模足

14、够小，很容易求出其解为止 求小问题解、合并：将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。、3、金块问题（求最大最小兀问题）老板有一袋金块（共n块），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。求：简述分治算法的基本思想？设计该金块问题的分治算法？计算所设计算法的时间复杂度？（要求写出递推公式）答：简述分治算法的基本思想：问题可以简化为：在含 n （n是2的哥（n>=2）个元素的集合中寻找极大元和极小元。用分治法（二分法）可以用较少比较次数地解决上述问题：1）将数据等

15、分为两组（两组数据可能差1）,目的是分别选取其中的最大（小）值。2）递归分解直到每组元素的个数w 2,可简单地找到最大（小）值.3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。、第三章动态规划算法一、填空题：1、动态规划算法中存储子问题的解是为了避免重复求解子问题。2、（最优子结构 ）是问题能用动态规划算法求解的前提。3、矩阵连乘问题的算法可由（动态规划）算法设计实现。二、判断题：1、动态规划算法基本要素的是最优子结构。（V ）2、最优子结构性质是指原问题的最优解包含其子问题的最优解。（V ）3、动态规划算法求解问题时，分解出来的子问题相互独立。（X）三、简答题：1、动态规划算

16、法解题步骤？答：找出最优解的性质，并刻划其结构特征；（即原问题的最优解，包含了子问题的最优解）递归地定义最优值；（即子问题具有重叠性，由子问题定义原问题）以自底向上的方式计算出最优值 ；根据计算最优值时得到的信息，构造最优解；2、动态规划算法基本思想？答：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题；但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次；如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。3、动态规划与分治算法异同点?4、

17、动态规划算法的基本要素?四、算法设计与计算题：1、X =a,X2,L ,XmN Y =yi, y2,L , yn的最长公共子序列为Z=z1，z2,L ,zj。问：若用cij记录序列Xi =%,x2,L，x 和丫 =y1,y2,L ,力公共子序列长度。求:用动态规划法求解时，计算最优值的递归公式？设计计算最优值的算法？以及构造最优解的算法？2、长江游艇俱乐部在长江上设置了n个游艇出租站1,2n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i , j),其中1<=i<j<=n ;求：用动态规划法求解时，计算最优值

18、(最少租金)的递归公式？设计计算最优值(最少租金)的算法？并分析其时间复杂度？解：0i 二 jri, j min ri, k rk 1, j i j .i _k ：；：j计算最优值算法public static void matrixChain(int p, int m, int s) int n=p.length-1;for (int i = 1; i <= n; i+)mii = 0;/1 个站for (int r = 2; r <= n; r+)for (int i = 1; i <= n - r+1; i+) int j=i+r-1;m i j = mii + mi+

19、1 j;s i j = i;/断点位置在i处for (int k = i+1; k < j; k+)int t = m i k + mk+1 j; if (t < mij) m i j = t; s i j = k; 构造最优解算法public void traceback( int s,int I,int j) if(i=j) return;traceback( s, i, s i j);traceback( s, s i j+1, j );System.out.println("A" + i + ”, " + s i j +«A + s

20、i j+1 + j)/(m i, s i j ) (m s i j+1, j )时间复杂度：O(n3)第4章贪心算法一、填空题:1、某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱，且取款的张数最少,统计所需各种币值（100,50,20,10,5,2,1 元共七种）的张数。应发工资贪心算法如下：void greedy_zhaoling ( float GZ, int B , int S )GZ for( j=1, j<=7;j+)/ A= GZ/B j ;/AS j= S j +A ；S jGZ= GZ-A*B j ; for(i=1;i<=7;i+) print( B

21、 i , 贪心选择，依次给最大币种 表不又应j币种张数存放对应j币种总张数“-:S i );/输出币种和对应张数if ( w i<=mm )/计算当前总价值，mmF包剩余载重; /计算物品单位价值ww初始化按单位价值将物品排序，便于贪心选择贪心选择，总是选择价值最大放入背包当前物品小于背包剩余载重2、贪心算法的两个基本要素是（贪心选择性）和（ 最优子结构 ）。3、给定n种物品和一个背包。物品 i的重量是 Wi,其价值为Vi,背包的容量为 M应如何 选择装入背包的物品，使得装入背包中物品的总价值最大。贪心算法如下：float greedy_knapsack ( float M, float

22、 w , float p , float x)/ x背包问题最优解，w物品重量，P 物品价值 int n=w.length;float pp=0;float mm = M; /ppfor( int i=1;i<=n; i+ )float ww i= p i / w ix i=0;/Mergesort ( w , n );/for( int i=1; i<=n; i+ )/x i=1;mm= mm - w i ;pp= pp + p i ; elsex i=mm/w i;PP= PP + x i*p i;break; /i部分放入背包return pp;二、判断题：1、满足贪心选择性

23、质必满足最优子结构性质。（X ）三、简答题：1、贪心算法的基本思想？2、贪心算法的基本要素？3、贪心算法与动态规划算法的异同？四、算法设计题：1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容 量七150,如果使用贪心方法求解此背包问题（背包不超载的前提下，装载的物品价值达 到最大）。物品ABCDEFG35306050401025价值10403050354030利用贪心算法求解该问题时，为了进行贪心选择，首先应该做什么？ 然后进行贪心装载，给出一种正确的物品装载顺序？并给出其最优装载方案？利用贪心思想设计该普通背包问题的贪心算法？分析其时间复杂度？解：1 ）依据不

24、同的标准对这些物品进行排序，标准有重量、价值、单位价值；2）重量从小到大：FGBAEDC得到的贪心解为：FGBAE全部放入，D放入20%,得到价值为165;价值从大到小 ：DFBEGCA得到的贪心解为：DFBE全部放入,G放入80%,得到 价值为189;单位价值从大到小 ：FBGDECA得到的贪心解为：FBGD全部放入,E放入87.5% , 得到价值为190.625 ;3）显然使用单位价值得出最佳转载方案。2、设有n个活动集合，其中每个活动都要求使用同一资源，如足球场，而在同一时间只能有一个活动使用该资源。每个活动i都有一个要求使用该资源起始时间si和结束时间fi ,且si < fi ;

25、如果选择了活动i ,则它在半开区间si , fi） 占用资源。若两个活动si , fi）与sj, fj）不相交，则称活动i与活动j是相容的；活动安排问题：就是在所给的活动集合中选出最大相容活动子集合；求：利用贪心算法求解该问题的基本思想？设计该活动安排问题的贪心算法？并分析其时间复杂度？3、给定下图G=（V, E）是一个无向连通图，对每一条边（v, w）,其权彳1为c（ v, w）;求：利用prim算法构造其最小生成树，画出其选边的过程？并构造其算法？并分析其时间复杂度？利用kruskal算法构造其最小生成树，画出其选边的过程?并构造其算法？并分析其时间复杂度？4、对下图中的有向图，应用Dij

26、kstra算法计算从源（顶点1）到其它顶点间最短路径的过程要求：给出Dijkstra 算法的迭代过程，计算源到给个顶点的最短路径？（用表表示）解：见课本123页 表4-2解：迭代过程:迭代SUdist2dist 3Jdlst 4dist 5新骷(1)10ma xinI3010011,22603010021,2, 4)4509031,2,4, 3360411, 2, 4, 3, 5)510P 503060Dijkstra算法的迭代过程;= 士_丝枣二二；V-S第5章回溯算法一、填空题1、回溯法与分支限界法搜索方式不同，回溯法按深度优先 搜索解空间,分支限界法按广度优先或最小耗费优先搜索解空间。二

27、、判断题1、回溯法中限界函数的目的是剪去得不到最优解的子树。（V ）2、分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是相同的。（X ） 三、简答题1、简述回溯法和分支限界法的相同点和不同点？2、什么是子集树？什么是排列树？什么叫满 m叉树？3、回溯算法的基本思想？回溯算法的解题步骤 ？ 四、算法设计题1、n皇后问题在4X4格的棋盘上放置彼此不受攻击的 4个皇后。按照国际象棋的规则，皇后可以攻击 与之处在同一行或同一列或同一斜线上的棋子。用回溯算法解决4皇后问题：构造求解该问题的解空间树？设计该4皇后问题的回溯算法？解：解空间树2、01背包问题：假设有3个

28、物品，它们的重量和价值如下表所示。若这些物品均不可以被分割，且背包容量M= 10,问应该如何装入使背包中物品的总价值最大？用回溯算法求解该 01背包问题：构造求解该问题的解空间树？设计该01背包问题的回溯算法？解：1）解空间树；物品ABC重量655价值4225302) 3、图的着色问题：如下图给定无向连通图G和m种不同的颜色；用这m种颜色为图G的各个顶点着色，是否有一种方法使得图 G中每一条边的两个顶点 着不同颜色；求：构造求解该问题的解空间树？设计该图的着色问题回溯算法？解：1）解空间树:2 )算法：double mcoloring(int mm)int m=mm;double sum=0;

29、backtrack( 1 );return sum;/m/sum/可用颜色数当前着色方案数深度优先搜索解空间void backtrack( int t) if ( t>n ) / sum+;/搜索到叶子节点着色方案数加1for (int i=1; i<=n; i+) system.out.print( x i);"/输出解，顶点i着颜色 else / 搜索到中间节点 for(int i=1; i<=m; i+)x i x t=i;if( ok( t )/backtrack(t+1);顶点t着颜色i=1 m当前着色顶点与以前相邻顶点是否同色boolean ok( in

30、t k) / for(int j=1; j<=n; j+)if( a k j&&( x j=x k ) )/当前顶点k 到 j 有边： a k j/ 数组 a 是图的邻接矩阵x j=x kreturn false; else return true;算法分析(m种颜色，n个节点)计算限界函数，一重for 循环时间复杂度：O(n);在 最 坏 的 情 况 下 每 一 个 内 节 点 都 需 要 判 断 约 束 ， 内 节 点 个 数 ：1+m+m2+n3+mn-1=(mn-1)/(m-1) 个；故图的m着色问题的回溯算法，时间复杂度为：O(n*mn)。第六章分支限界算法一、

31、填空题1、按照活结点表的组织方式的不同，分支限界法包括 队列式分支限界算法和 优先队列式分支限界算法两种形式。2、回溯法与分支限界法搜索方式不同，回溯法按深度优先 搜索解空间,分支限界法按广度优先或最小耗费优先搜索解空间。3、队列分支限界算法中，通常用 队列 实现,体现 先进先出原则 的原则。4、优先队列式分支限界算法，通常采用堆 实现。6、回溯法与分支限界算法求解问题时，需要构造对该问题的解空间结构，其解空间结构通常有3种形式，分别是 子集树 、 排列树 、满m叉树。二、判断题1、分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是相同的。（X）三、简答题1

32、、简述分支限界法的基本思想与解题步骤？2、分支限界算法与回溯算法异同点？四、算法设计题1、01背包问题：假设有3个物品，它们的重量和价值如下表所示。若这些物品均不可以被分割，且背包 容量M= 10,问应该如何装入使背包中物品的总价值最大?物品ABC重量655价值422530用分支限界算法求解该 0-1背包问题:构造求解该问题的解空间树？给出队列式分支限界算法的求解过程？ 如法1 :队列式 （FIFO先进先出）分支限界法? 从根结点1开始；将活结点组织成一个队列；? 初始时活结点队列为空，结点1加入队列，结点1为当前扩展结点；1? 结点 1的孩子结点2、 9为可行结点，故舍弃当前结点1,将2、

33、9加入活结点队列：|2 |9 |-|? 先进先出原则，2作为当前扩展结点，其孩子2点3、 6;由于结点3是不可行结点舍弃；将结点6加入活结点队列；1 J9 |6 1|1|1| -|? 先进先出原则，9作为当前扩展结点，其孩子结点10、 13;结点 10、 13 是可行结声加入活结总队列.；.一I I 16 10 |13 | I丁 I|设计该0-1背包问题的分支限界算法？并分析其时间复杂度?（队列式分支限界，带上界函数）2、多段图最短路径问题多段豌文:有句连通酷权圉G=（VRW，质点集合划分成K个不相好集1=<i<=k.，使得其中的边S必有以三匕，） w I'i ，叱=1；称

34、为多辎。令匕. I t - h称为J <工源点，M *叽为收点”事*岸丽 君次魅渤峰点由遍H 码的求：构造求解该问题的解空间树?给出队列式分支限界算法的求解过程？设计该问题的分支限界算法？并分析其时间复杂度?（队列式分支限界，带上界函数）解：/定义并组织问题的解空间如下:2）求解过程:法心 血血4 （FIFO 先迸先出）分支 限界法从根多苦点i开好”将适结点组组或一金鼠到二初始时也生i必在为空.结点】力II入队列.结点1为当前犷结点】的孩子结点7. 3、4为可行结点，故舍弃当前结点1 , 棉N、3r 4力口入酒结点血物|n|R/| | | | | | | | | 先进先出原则.苣作为当前

35、扩展结点其筱于结点5.6均 是 E 行姑点*将结点5、G力口入活结点血叁|3|4|5|后| 先进先山原则，3作为当吊面炉展结点，共孩子结点4- 3. 6. 日均昆Rf行结点，加入活结点以尊；-肖至U抽后队列为空。3 )算法描述： 法1 :队列式分支限界法double shortest( int i) while (true) /队列不空，搜索问题的解空间 for ( int j=1; j<=n;j+)儿子结点入队 if (a i j < Float.MAX_VALUE) 顶点 i 到顶点 j 可达 dist j= dist i +a i j;/ dist i记录源到顶点 i 的距离

36、p j=enode.i; / p j记录顶点j的前驱enQueue(v j, j); /结点 j 加入队列ew = (Integer) queue.remove().intValue();/ 取队首下一扩展结点if (ew = -1)/同一层尾部标记ew = -1 :同一层结点处理结束 if (queue.isEmpty()return dist i;判断队歹U是否为空else queue.put(new Integer(-1); /同层结点尾部标志ew = (Integer) queue.remove().intValue(); 取下一扩展结点i+;/进入下一层 时间复杂度：第七章概率算法1

37、、什么叫概率算法？答：概率算法允许算法在执行的过程中随机选择下一个计算步骤。2、概率算法有一个基本特征？答：基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全 不同的效果。3、概率算法可以分为哪4类？答：1）数值概率算法2）蒙特卡罗算法3）拉斯维加斯算法4）舍伍德算法4、在概率算法中使用的 随机数都是一定程度上随机的，即伪随机数；一般随机 数通过 线性同余法方法产生。第八章NP完全性理论1、什么是易解问题？什么是难解问题？难解问题分为哪两类？答：1）易解问题：人们将存在多项式时间算法的问题称为易解问题；2）难解问题：将需要在指数时间内解决的问题称为难解问题；3）难解问题有两类：

38、1 ）不可判定问题 2 ）非决定的难处理问题 2、什么是不可判定问题？什么是非决定的难处理问题？答：1）不可判定问题：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解 它们的任何算法。2）非决定的难处理问题：这类问题是可判定的（即可解的）。但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。3、什么是P类问题？什么是NP完全问题？答：1） P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所 有易解问题都属于 P类问题。2） NP完全问题：对于某问题，很难找到其多项式时间的算法（或许根本不存在），但是如果给了该问题的一个答案，则可以在多项式时间内判

39、定或验证这个答案是否正确。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。4、列出几个典型的 NP完全问题？答：（1）图着色问题 COLORING（2）路径问题 LONG-PATH（3）顶点覆盖问题 VERTEX-COVER（4）子集和问题 SUBSET-SUM（5）哈密尔顿回路问题 HAM-CYCLE（6）旅行商问题TSP（7）装箱问题BIN-PACKING , 能否用k个箱子来装n个物品；第九章近似算法1、所有NP完全问题都还没有多项式时间的算法，然而许多NP完全问题都具有很重要的意义，对于这类问题通常可以采取以下几种解题策略？答：1 ）只对问题的特殊实例求解；2）用动态规划或

40、分支限界法求解。3）启发式方法求解4）只求近似解2、利用近似算法求解 NP完全问题时，近似算法应该满足下面两个基本的要求？答： 1）算法的时间复杂性：要求算法能在n 的多项式时间内完成。2）解的近似程度：算法的近似解应满足一定的精度。通常，用来衡量精度的标准有近似比和相对误差。1、二分搜索算法是利用（A ）实现的算法。A、分治策略B、动态规划法C 、贪心法D 、回溯法2、下列不是动态规划算法基本步骤的是（A ）。A找出最优解的性质 B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（A ）的一搜索方式。A分支界限法B、动态规划法C、贪心法D、回溯法4、最长公共子序列算法利用的算法是（

41、B ）。A 、分支界限法B、动态规划法C、贪心法D回溯法5.回溯法解TSP问题时的解空间树是（A ）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、实现最长公共子序列利用的算法是（B ）。A、分治策略B

42、、动态规划法C、贪心法D回溯法11 下面不是分支界限法搜索方式的是（D ）。A 、广度优先B、最小耗费优先C、最大效益优先D深度优先12下列算法中通常以深度优先方式系统搜索问题解的是（D ）。A、备忘录法B、动态规划法C、贪心法13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（BA 、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解14广度优先是（A ）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法15 背包问题的贪心算法所需的计算时间为（B ）。A、 O（ n2） nB、 O（ nlogn ） C、 O（ 2） nD、 O（ n）16实现最大子段和利

43、用的算法是（B ）。A 、分治策略B、动态规划法C、贪心法D回溯法17实现棋盘覆盖算法利用的算法是（A ）。A 、分治法B、动态规划法C、贪心法D回溯法18. 下面是贪心算法的基本要素的是（C ）。A 、重叠子问题B、构造最优解C、贪心选择性质D定义最优解19. 回溯法的效率不依赖于下列哪些因素（D ）A. 满足显约束的值的个数C. 计算限界函数的时间B. 计算约束函数的时间D. 确定解空间的时间20. 下面哪种函数是回溯法中为避免无效搜索采取的策略（B ）A.递归函数B.剪枝函数C。随机数函数D.搜索函数21、以深度优先方式系统搜索问题解的算法称为（ D ）。A、分支界限算法B、概率算法C、

44、贪心算法 D回溯算法22、贪心算法与动态规划算法的主要区别是（B ）。A 、最优子结构B、贪心选择性质C、构造最优解D定义最优解23. 采用最大效益优先搜索方式的算法是（A ）。A 、分支界限法B、动态规划法C、贪心法D回溯法24. （ D ）是贪心算法与动态规划算法的共同点。A 、重叠子问题B 、构造最优解C 、贪心选择性质D最优子结构性质25. 矩阵连乘问题的算法可由（B ）设计实现。A、分支界限算法B、动态规划算法 C、贪心算法D、回溯算法26. 0-1 背包问题的回溯算法所需的计算时间为（A ） A、 O（ n2n）B、 O（ nlogn ）C、 O（ 2n）D、 O（ n）27、背包问题的贪心算法所需的计算时间为（B ）A、O（n2）B、O（nlogn ）C、O（2）D、O（n）29、使用分治法求解不需要满足的条件是（A ）。A