《算法分析与设计复习题及参考答案》由会员分享,可在线阅读,更多相关《算法分析与设计复习题及参考答案(19页珍藏版)》请在金锄头文库上搜索。
1、网络教育课程考试复习题及参考答案 算法分析与设计 一、名词解释: 1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题 7.最小生成树 二、简答题: 1.备忘录方法和动态规划算法相比有何异同?简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。 7.简述算法复杂性的概念,算法复杂性度量主要指哪两个方面? 8.贪心算法求解的问题主要具有哪些性质?简述之。 9.分治法的基本思想是什么?合并排
2、序的基本思想是什么?请分别简述之。 10.简述分析贪心算法与动态规划算法的异同。 三、算法编写及算法应用分析题: 1.已知有3个物品:(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20,根据0-1背包 动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。 对数组A=15,29,135,18,32,1,27,25,5,用快速排序方法将其排成递减序。 请描述递减数组进行二分搜索的基本思想,并给出非递归算法。 给出上述算法的递归算法。 使用上述算法对所得到的结果搜索如下元素,并给出搜索过程:18,31,135。 3.已知 , 1
3、 ( ) * ( ) i i k k ij r r A a k=1,2,3,4,5,6,r 1 =5,r 2 =10,r 3 =3,r 4 =12,r 5 =5,r 6 =50,r 7 =6,求矩阵链积 A 1 A 2 A 3 A 4 A 5 A 6 的最佳求积顺序(要求给出计算步骤) 。 4.根据分枝限界算法基本过程,求解0-1背包问题。 已知n=3,M=20,(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题:已知一辆汽车加满油后可行驶n公里,而旅途中有若干个加油站。 试设计一个有效算法,指出应在哪些加油站停靠加油,使加
4、油次数最少,请写出该算法。 6.试用动态规划算法实现下列问题:设A和B是两个字符串。我们要用最少的字符操作,将字符串A转 换为字符串B,这里所说的字符操作包括: 删除一个字符。 插入一个字符。 将一个字符改为另一个字符。 请写出该算法。 7.对于下图使用Dijkstra算法求由顶点a 到顶点h的最短路径。a h g f e d c b 1 2 1 2 2 8 2 3 2 2 3 8.试写出用分治法对数组An实现快速排序的算法。 9.有n个活动争用一个活动室。已知活动i占用的时间区域为s i ,f i ,活动i,j相容的条件是: sjf i ,问题的解表示为(x i | x i=1,2,n,),
5、x i 表示顺序为i的活动编号活动,求一个相容的活 动子集,且安排的活动数目最多。 10.设x 1 、x 2 、x 3 是一个三角形的三条边,而且x 1 +x 2 +x 3 =14。请问有多少种不同的三角形?给出解答过程。 11.设数组A有n个元素,需要找出其中的最大最小值。 请给出一个解决方法,并分析其复杂性。 把n个元素等分为两组A1和A2,分别求这两组的最大值和最小值,然后分别将这两组的最大值和 最小值相比较,求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个,则再用上述方法 各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想?请给出该方法的算法描 述,并分析其
6、复杂性。 12.有n个程序和长度为L的磁带,程序i的长度为a i ,已知 ,求最优解(x i ,x 2L a n i i f 1 ,.,x i , x n ),x i=0,1, x i=1,表示程序i存入磁带,x i=0,表示程序i不存入磁带,满 足 ,且存放的程序数目最多。 L a x n i i i 1 13.试用分治法实现有重复元素的排列问题:设 是要进行排列的 个元素,其中元素 ) ,., , 2 1 n r r r R n 可能相同,试设计计算 的所有不同排列的算法。 n r r r ,., , 2 1 R 14.试用动态规划算法实现0-1闭包问题,请写出该算法。 15.试用贪心算法
7、求解下列问题:将正整数n分解为若干个互不相同的自然数之和,使这些自然数的乘积 最大,请写出该算法。 16.试写出用分治法对一个有序表实现二分搜索的算法。 17.试用动态规划算法实现最长公共子序列问题,请写出该算法。 18.假设有7个物品,它们的重量和价值如下表所示。若这些物品均不能被分割,且背包容量M150,使 用回溯方法求解此背包问题,请写出状态空间搜索树。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 19.求解子集和问题:对于集合S=1,2 ,6,8,求子集,要求该子集的元素之和d=9。 画出子集和问题的
8、解空间树; 该树运用回溯算法,写出依回溯算法遍历节点的顺序; 如果S中有n个元素,指定d,用伪代码描述求解子集和问题的回溯算法。20.求解填字游戏问题:在33个方格的方阵中要填入数字1到N(N10)内的某9个数字,每个方格 填一个整数,似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一 种数字填法的算法和满足这个要求的全部数字填法的算法。 21.试用动态规划算法实现最大子矩阵和问题:求 矩阵A的一个子矩阵,使其各元素之和为最大。 n m 22.试用回溯法解决下列整数变换问题:关于整数 的变换 和 定义如下: 。对 i f g 2 / ) ( ; 3 ) ( i i g
9、 i i f 于给定的两个整数 和 ,要求用最少的变换 和 变换次数将 变为 。 n m f g n m 23.关于15谜问题。在一个44的方格的棋盘上,将数字1到15代表的15个棋子以任意的顺序置入各 方格中,空出一格。要求通过有限次的移动,把一个给定的初始状态变成目标状态。移动的规则是: 每次只能把空格周围的四格数字(棋子)中的任意一个移入空格,从而形成一个新的状态。为了有效 的移动,设计了估值函数C 1 (x),表示在结点x的状态下,没有到达目标状态下的正确位置的棋子的 个数。 请使用该估计函数,对图示的初始状态,给出使用分支限界方法转换到目标状态的搜索树。初始状态 目标状态 1 2 4
10、 5 6 3 7 9 10 12 8 13 14 11 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15参考答案 一、名词解释: 1.算法:算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列,满足性质:(1)输 入:有零个或多个外部量作为算法的输入;(2)输出:算法产生至少一个量作为输出;(3)确定性: 组成算法的每条指令清晰、无歧义;(4)有限性:算法中每条指令的执行次数有限,执行每条指令 的时间也有限。 2.程序:程序是算法用某种程序设计语言的具体实现。 3.递归函数:用函数自身给出定义的函数称为递归函数。 4.子问题的重叠性质:递归算法求解问题时,
11、每次产生的子问题并不总是新问题,有些子问题被反复计 算多次,这种性质称为子问题的重叠性质。 5.队列式分支限界法:队列式(FIFO)分支限界法是将活结点表组织成一个队列,并按照队列的先进先出 (FIFO)原则选取下一个结点为扩展结点。 6.多机调度问题:多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由 m台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理,但未完工前不允许中断 处理。作业不能拆分成更小的子作业。 7.最小生成树:G=(V,E)是无向连通带权图,G的子图称为G的生成树,生成树上各边权的总和称为该生 成树的耗费,在G的所有生成树中,耗费最小的
12、生成树称为G的最小生成树。 二、简答题: 1.备忘录方法和动态规划算法相比有何异同?简述之。 备忘录方法是动态规划算法的变形。与动态规划算法一样,备忘录方法用表格保存已解决的子问题的 答案,在下次需要解此问题时,只要简单地查看该子问题的解答,而不必重新计算。 备忘录方法与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自 底向上递归的。因此,备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法 为每个解过的子问题建立了备忘录以备需要时查看,避免了相同的子问题的重复求解,而直接递归方 法没有此功能。 2.简述回溯法解题的主要步骤。 回溯法解题的主要步骤包
13、括: 1)针对所给问题,定义问题的解空间; 2)确定易于搜索的解空间结构; 3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。 3.简述动态规划算法求解的基本要素。 动态规划算法求解的基本要素包括: 1)最优子结构是问题能用动态规划算法求解的前提; 2)动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问 题时,只是简单地用常数时间查看一下结果,即重叠子问题。 4.简述回溯法的基本思想。 回溯法的基本做法是搜索,在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算 法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定
14、不包含,则跳过对该结 点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。 5.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。 将递归算法转化为非递归算法的方法主要有: 1)采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强,但本质上还是递归,只 不过人工做了本来由编译器做的事情,优化效果不明显。 2)用递推来实现递归函数。 3)通过Cooper变换、反演变换能将一些递归转化为尾递归,从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善,但其适用范围有限。 6.简要分析分支限界法与回溯法的异同。 1)求解目标:回溯法的求解目
15、标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。 2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小 耗费优先的方式搜索解空间树。 7.简述算法复杂性的概念,算法复杂性度量主要指哪两个方面? 算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资 源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。 如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身,而且用C表示复杂性,那 么,
16、应该有C=F(N,I,A)。 算法复杂性度量主要包括算法的时间复杂性和算法的空间复杂性。 8.贪心算法求解的问题主要具有哪些性质?简述之。 贪心算法求解的问题一般具有二个重要的性质: 一是贪心选择性质,这是贪心算法可行的第一个基本要素; 另一个是最优子结构性质,问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 9.分治法的基本思想是什么?合并排序的基本思想是什么?请分别简述之。 分治法的基本思想:将n个输入分成k个不同子集合,得到k个不同的可独立求解的子问题,其中 1kn,而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。 合并排序基本思想:将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最 终将排好