算法分析与设计习题集整理

《算法分析与设计习题集整理》由会员分享，可在线阅读，更多相关《算法分析与设计习题集整理（18页珍藏版）》请在金锄头文库上搜索。

1、算法分析与设计习题集整理算法分析与设计习题集整理 第一章算法引论第一章算法引论 一、填空题：一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂 度。2、多项式的上界为 O(nm)。10( )m mA na na naL3、算法的基本特征：输入、输出、确定性、有限性。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。5、计算下面算法的时间复杂度记为： O(n3) 。for(i=1;i4 时， a2 写出其相应的递归算法？Int F(int n) if(n=1) return 1;else if(n=2) return 2;elseretu

2、rn F(n-1)+ F(n-2); 2 2、设、设 a,b,ca,b,c 是是 3 3 个塔座。开始时，在塔座个塔座。开始时，在塔座 a a 上有一叠共上有一叠共 n n 个圆盘，这些圆盘自下而上，由个圆盘，这些圆盘自下而上，由 大到小地叠在一起。各圆盘从小到大编号为大到小地叠在一起。各圆盘从小到大编号为 1,2,n,1,2,n,现要求将塔座现要求将塔座 a a 上的这一叠圆盘移上的这一叠圆盘移 到塔座到塔座 b b 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则规则 1 1：每次只能移动：每次只能移动 1 1 个圆盘；

3、个圆盘； 规则规则 2 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则规则 3 3：在满足移动规则：在满足移动规则 1 1 和和 2 2 的前提下，可将圆盘移至的前提下，可将圆盘移至 a,b,ca,b,c 中任一塔座上。中任一塔座上。 写出该问题的解题步骤？写出该问题的解题步骤？ 并写出其相应的递归算法？并写出其相应的递归算法？ 解： 第一步：将 n1 个盘子看成一个整体，从 A 移到 C；第二步：将第 n 个盘子移到 B;第三步：将 n1 个盘子看成一个整体，从 C 移到 B； 写出其相应的递归算法：void hanoi(int

4、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 2）分治算法）分治算法 一、填空题：一、填空题： 1、在快速排序、插入排序和合并排序算法中， 插入排序插入排序 算法不是分治算法。 2、合并排序算法使用的是 分治分治 算法设计的思想。 3、二分搜索算法是利用 分治分治 算法思想设计的。 二、简答题：二、简答题： 1 1、适合用分治算法求解的问题具有的基本特征？、适合用分治算法求解的问题具有的基本特征？ 答：1)该问题的规模缩小到一定的程度就可以

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

6、时间复杂度？ 解：int binsearch( int an, int x ,) /x 待查数据int mid, i , j; low=1;int high=n; while(lowx) high=mid-1; /继续在左边查找else / (amid=2） ）个元素的集合中寻找极大元和极小元。用分治法（二分法）可以用较少比较次数地解决上述问题： 1）将数据等分为两组（两组数据可能差 1） ，目的是分别选取其中的最大（小）值。 2)递归分解直到每组元素的个数2,可简单地找到最大(小)值. 3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。 、 第三章动态规划算法第三章动态规划算法

7、 一、填空题：一、填空题： 1、动态规划算法中存储子问题的解是为了 避免重复求解子问题避免重复求解子问题 。 2、 （ 最优子结构最优子结构 ）是问题能用动态规划算法求解的前提。 3、矩阵连乘问题的算法可由（ 动态规划动态规划 ）算法设计实现。二、判断题：二、判断题： 1、动态规划算法基本要素的是最优子结构。 （ ）2、最优子结构性质是指原问题的最优解包含其子问题的最优解。 （ ） 3、动态规划算法求解问题时，分解出来的子问题相互独立。 （ X）三、简答题：三、简答题： 1 1、动态规划算法解题步骤？、动态规划算法解题步骤？ 答：找出最优解的性质，并刻划其结构特征; （即原问题的最优解，包含了

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

9、态规划算法的基本要素？、动态规划算法的基本要素？ 四、算法设计与计算题：四、算法设计与计算题：1 1、和的最长公共子序列为。12,mXx xxL12,nYy yyL12,kZz zzL问：若用记录序列和公共子序列长度。求： c ij12,iiXx xxL12,jjYy yyL用动态规划法求解时,计算最优值的递归公式？ 设计计算最优值的算法？以及构造最优解的算法？2 2、长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2n.游客可在这些游艇出租站 租用游艇，并在下游的任何一个游艇出租站归还游艇。 游艇出租站 i 到游艇出租站 j 之间的租金为 r(i，j)，其中 1n ) / 搜索到叶子节点

10、 sum+; /着色方案数加 1 for (int i=1; i=n; i+)system.out.print( x i ); /输出解,顶点 i 着颜色 x ielse / 搜索到中间节点 for(int i=1; i=m; i+) x t=i; /顶点 t 着颜色 i=1mif( ok( t ) ) backtrack(t+1); boolean ok( int k) /当前着色顶点与以前相邻顶点是否同色 for(int j=1; j=n; j+)if( a k jelse return true;算法分析（算法分析（m m 种颜色，种颜色，n n 个节点）个节点）计算限界函数，一重 fo

11、r 循环时间复杂度：O(n);在最坏的情况下每一个内节点都需要判断约束，内节点个数：1+m+m2+ m3+mn- 1=(mn-1)/(m-1)个； 故图的 m 着色问题的回溯算法，时间复杂度为：，时间复杂度为：O(n*mO(n*mn n) )。第六章第六章 分支限界算法分支限界算法 一、填空题一、填空题 1、按照活结点表的组织方式的不同，分支限界法包括 队列式分支限界算法队列式分支限界算法 和 优先队列式分支限界算法优先队列式分支限界算法 两种形式。 2、回溯法与分支限界法搜索方式不同，回溯法按 深度优先深度优先 搜索解空间，分支限界 法按 广度优先或最小耗费优先广度优先或最小耗费优先 搜索解

12、空间。 3、队列分支限界算法中，通常用队列队列 实现，体现先进先出原则先进先出原则 的原则。4、优先队列式分支限界算法，通常采用 堆堆 实现。 6、回溯法与分支限界算法求解问题时，需要构造对该问题的解空间结构,其解空间结构通常有 3 种形式，分别是 子集树子集树 、 排列树排列树 、 满满 m m 叉树叉树 。二、判断题二、判断题 1、分支限界法类似于回溯法，也是一种在问题的解空间树 T 上搜索问题解的算法，两者的 搜索方式是相同的。 （X）三、简答题三、简答题 1 1、简述分支限界法的基本思想与解题步骤？、简述分支限界法的基本思想与解题步骤？2 2、分支限界算法与回溯算法异同点？、分支限界算

13、法与回溯算法异同点？四、算法设计题四、算法设计题 1 1、0 01 1 背包问题背包问题： 假设有 3 个物品，它们的重量和价值如下表所示。若这些物品均不可以被分割，且背 包容量 M10，问应该如何装入使背包中物品的总价值最大？ 用分支限界算法求解该 01 背包问题： 构造求解该问题的解空间树？ 给出队列式分支限界算法的求解过程？ 如 法法1：队队列列式式队队列列式式（FIFO 先先进进先先出出）分分支支限限界界法法 从从根根结结点点1开开始始；将将活活结结点点组组织织成成一一个个队队列列活活结结点点组组织织成成一一个个队队列列； 初初始始时时活活结结点点队队列列活活结结点点队队列列为为空空，

14、结结点点加加入入队队列列，结结点点1为为当当前前 扩扩展展结结点点；92结结点点1的的孩孩子子结结点点2、9为为可可行行结结点点，故故舍舍弃弃当当前前结结点点1， 将将2、9加加入入活活结结点点队队列列队队列列；1先先进进先先出出原原则则，2作作为为当当前前扩扩展展结结点点，其其孩孩子子结结点点3、6； 由由于于结结点点3是是不不可可行行结结点点舍舍弃弃；将将结结点点6加加入入活活结结点点队队列列队队列列； 69 先先进进先先出出原原则则，9作作为为当当前前扩扩展展结结点点，其其孩孩子子结结点点10、13; 结结点点10、13是是可可行行结结点点加加入入活活结结点点队队列列队队列列； 13106设计该 01 背包问题的分支限界算法？并分析其时间复杂度？ （队列式分支限界，带上界函数）、多段图最短路径问题、多段图最短路径问题物品ABC重量655价值422530求：构造求解该问题的解空间树？ 给出队列式分支限界算法的求解过程？ 设计该问题的分支限界算法？并分析其时间复杂度？ （队列式分支限界，带上界函数） 解：2）求解过程：）算法描述：）算法描述： 法法: :队列式队列式分支限界法分支限界法double shortest( int i) while (true) /队列不空， 搜索问题的解空间 for ( int j=1; j=n; j+) /儿子结点入队 if (a i j