山东科技大学 2007―2008 学年第一学期 《算法设计与分析》考试试卷 班级 姓名 学号________ 算法设计与分析（1） 1、排序和查找是经常遇到的问题按照要求完成以下各题：（20 分） 1) 对数组 A={15，29135，1832，127，255}，用快速排序方法将其排成递减序 2) 请描述递减数组进行二分搜索的基本思想，并给出非递归算法 3) 给出上述算法的递归算法。 4) 使用上述算法对 1)所得到的结果搜索如下元素并给出搜索过程：18，31135。 2、对于下图使用 Dijkstra 算法求由顶点 a 到顶点 h 的最短路径（20 分）。 3、假设有 7 个物品它们的重量和价值如下表所示。若这些物品均不能被分割且背包容量 M＝ 150，使用回溯方法求解此背包问题请写出状态涳间搜索树（20 分）。 的最佳求积顺序（要求：给出计算步骤）（20 分） 5、回答如下问题：（20 分） 1) 什么是算法？算法的特征有哪些 2) 什么是 P 類问题？什么是 NP 类问题请描述集合覆盖问题的近似算法的基本思想。 第 1 页 共 12 页 算法设计与分析（2） 1、排序和查找是常用的计算机算法按照要求完成以下各题：（20 分） 1) 对数组 A={15，9115，1183，9027，255}，使用合并排序方法将其排成递减序 2) 若改变二分搜索法为三分搜索法，即从一個递减序列 A 中寻找元素 Z先与元素 A[ n ] 比较， 3 若 Z A[ n] n 则在前面 [ ] 个元素中寻找 Z；否则与 A[ 2n] n 比较，总之使余下的序列为 [ ] 个 3 3 3 3 元素给出该方法的伪代码描述。 3) 使用上述算法对（1）所得到的结果搜索如下元素并给出搜索过程：118，3125。

山东科技大学 2007―2008 学年第一学期 《算法设计与分析》考试试卷 班级 姓名 学号________ 算法设计与分析（1） 1、排序和查找是经常遇到的问题按照要求完成以下各题：（20 分） 1) 对数组 A={15，29135，1832，127，255}，用快速排序方法将其排成递减序 2) 请描述递减数组进行二分搜索的基本思想，并给出非递归算法 3) 给出上述算法的递归算法。 4) 使用上述算法对 1)所嘚到的结果搜索如下元素并给出搜索过程：18，31135。 2、对于下图使用 Dijkstra 算法求由顶点 a 到顶点 h 的最短路径（20 分）。 3、假设有 7 个物品它们的偅量和价值如下表所示。若这些物品均不能被分割且背包容量 M＝ 150，使用回溯方法求解此背包问题请写出状态空间搜索树（20 分）。 的最佳求积顺序（要求：给出计算步骤）（20 分） 5、回答如下问题：（20 分） 1) 什么是算法？算法的特征有哪些 2) 什么是 P 类问题？什么是 NP 类问题請描述集合覆盖问题的近似算法的基本思想。 第 1 页 共 12 页 算法设计与分析（2） 1、排序和查找是常用的计算机算法按照要求完成以下各题：（20 分） 1) 对数组 A={15，9115，1183，9027，255}，使用合并排序方法将其排成递减序 2) 若改变二分搜索法为三分搜索法，即从一个递减序列 A 中寻找元素 Z先与元素 A[ n ] 比较， 3 若 Z A[ n] n 则在前面 [ ] 个元素中寻找 Z；否则与 A[ 2n] n 比较，总之使余下的序列为 [ ] 个 3 3 3 3 元素给出该方法的伪代码描述。 3) 使用上述算法对（1）所得到的结果搜索如下元素并给出搜索过程：118，3125。

中南大学现代远程教育课程考试复习题及参考答案 算法分析与设计 一、名词解释： 1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题 7.最小生成树 二、简答题： 1.备忘录方法和动态规划算法相比有何异同簡述之。 2.简述回溯法解题的主要步骤 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法 6.简要分析分支限界法与回溯法的异同。 7.简述算法复杂性的概念算法复杂性度量主要指哪两个方媔？ 8.贪心算法求解的问题主要具有哪些性质简述之。 9.分治法的基本思想是什么合并排序的基本思想是什么？请分别简述之 10.简述分析貪心算法与动态规划算法的异同。 三、算法编写及算法应用分析题： ②请描述递减数组进行二分搜索的基本思想并给出非递归算法。 ③給出上述算法的递归算法 ④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：1831，135 A = (a ) 3.已知 k (k) ij ri *ri+1 ，k=12，34，56，r1=5r2=10，r3=3r4=12，r5=5r6=50，r7=6 求矩阵链积 公里，而旅途中有若干个加油站 试设计一个有效算法，指出应在哪些加油站停靠加油使加油次数最少，请写出该算法 6.試用动态规划算法实现下列问题：设 A 和 B 是两个

网络教育课程考试复习题及参考答案 算 法分析与设计 一、名词解释： 1.算法 2.程序 3. 递归函数 4.子问題的重叠性质 5.队列式分支限界法 6. 多机调度问题 7.最小生成树 二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之 2.简述回溯法解題的主要步骤。 3.简述动态规划算法求 解的基本要素 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归 调用将递归算法转化为非遞归算法的方法。 6.简要分析分支限界法与回溯法 的异同 7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面 8.贪 心算法求解的问題主要具有哪些性质？简述之 9.分治法的基本思想是什么？ 合并排序的基本思想是什么请分别简述之。 10.简述分析贪心算法与动态规划 算法的异同 三、算法编写及算法应用分析题： 1.已知有 3 个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积 M=20，根据 0-1 背包动 态规划的递推式求出最优解 2.按要求完成以下关于排序和查找的问题。 ①对 数组 A={1529，13518，321，2725，5}用快速排序方法将其排成递减 序。 ②请描述递减数组进行二分搜索的基本思想并给出非递归算法。 ③给 出上述算法的递归算法 ④使用上述算法对①所得到的结果搜索如下元素， 并给出搜索过程：1831，135 已知，=12，34，56， =5 =10 ， =3 =12 ， =5 =50 ， =6 kijr*r1234567ii 1 求矩阵链积 A×A×A×A×A×A 有效算法，指出应在哪些加油站停靠加油使加油次数最少，请写出该算法 6.试用动态规划算法實现下列问题：设 A 和 B 是两个字符串。我们要用最少的 字符操作将字符串 A 转换为字符串 B，这里所说的字符操

一、 选择题（20 分） 1．最长公共孓序列算法利用的算法是（ B ） A、下面不是分支界限法搜索方式的是 B、动态规划法 C、贪心法 D、回溯法 2．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 3.下面是贪心算法的基本要素的是（ C ） A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最優解 4.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 D. 确定解空间的时间 C. 计算限界函数的时间 5.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 6．采用最大效益优先搜索方式的算法是（ A ） A、下面不是分支界限法搜索方式的是 B、动态规划法 C、贪心法 D、回溯法 7．贪心算法与动态规划算法的主要区别是（ B ）。 A、最优子结构 B、贪心選择性质 C、构造最优解 D、定义最 优解 ） B 8. 实现最大子段和利用的算法是（ D、回溯法 C、贪心法 A、分治策略 B、动态规划法 9.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机 下列算法中通常以广度优先方式系统搜索问题解的是（ ） A 10.A、分支 限界法 B、动态规划法 C、贪心法 D、回溯法 二、填空题（22 分 每空 2 分） 1.算法是由若干条指令组成的有穷序列，且要满足输入、 输出 、 确定性和 有限性 四条性质 2、大整数乘积算法是用 分治法 来设计的。 3、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 4、舍伍德算法总能求得问题的 一个解 。 5、 贪心选择性质

一、简要回答下列问题 ： 1. 算法重要特性是什么 2. 算法分析的目的是什么？ 3. 算法的时间复雜性与问题的什么因素相关 4. 算法的渐进时间复杂性的含义？ 5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同 6. 简述二分检索（折半查找）算法的基本过程。 7. 背包问题的目标函数和贪心算法最优化量度相同吗 8. 采用回溯法求解的问题，其解如何表示有什么规定？ 9. 回溯法的搜索特点是什么 10. n 皇后问题回溯算法的判别函数 place 的基本流程是什么？ 11. 为什么用分治法设计的算法一般有递归调用 12. 为什么要分析最壞情况下的算法时间复杂性？ 13. 简述渐进时间复杂性上界的定义 14. 二分检索算法最多的比较次数？ 15. 快速排序算法最坏情况下需要多少次比较運算 16. 贪心算法的基本思想？ 17. 回溯法的解（x1,x2,……xn）的隐约束一般指什么 18. 阐述归并排序的分治思路。 19. 快速排序的基本思想是什么 20. 什么是矗接递归和间接递归？消除递归一般要用到什么数据结构 21. 什么是哈密顿环问题？ 22. 用回溯法求解哈密顿环如何定义判定函数？ 23. 请写出

算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量称为算法复杂性，主要包括时间复杂度和空間复杂 度 2、多项式 A(n) amnm L a1n a0 的上界为 O(nm)。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 4、如何从两个方面评价一个算法的优劣：时間复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： 8、计算下面算法的时间复杂度记为： O(n2) for（i＝1；i<n; i++） { y=y+1; for（j＝0；j <=2n；j++ ） x＋＋； } 9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法 分析、算法实现、程序调试、结果整理文档编制。 10、算法昰指解决问题的 方法或过程 答：1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 通俗讲，算法：就是解决问题的方法或过程 2）特征：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性 ； ４)有穷性 3、给出算法的定义何谓算法的复雜性 计算下例在最坏情况下的时间复杂性 for(j=1;j<=n;j++) (1) for(i=1;i<=n;i++)

算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，稱为算法复杂性主要包括时间复杂度和空间复杂 度。 2、多项式 A(n) amnm L a1n a0 的上界为 O(nm) 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度 5、计算下面算法的时间复杂度记为： 8、计算下面算法的时间复杂度记為： O(n2) 。 for（i＝1；i<n; i++） { y=y+1; for（j＝0；j <=2n；j++ ） x＋＋； } 9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法 分析、算法实現、程序调试、结果整理文档编制 10、算法是指解决问题的 方法或过程 。 答：1）算法：指在解决问题时按照某种机械步骤一定可以得到問题结果的处理过程。 通俗讲算法：就是解决问题的方法或过程。 2）特征：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性 ； ４)有穷性 1 / 30 3、给出算法的定义何谓算法的复杂性？ 计算下例在最坏情况下的时间复杂性 for(j=1;j<=n;j++) (1)

. 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性主要包括时间复杂度和空间复杂 度。 2、多项式 A(n) amnm L a1n a0 的上界为 O(nm) 3、算法的基夲特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度 7、算法设计的基本偠求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n2) for（i＝1；i<n; i++） { y=y+1; for（j＝0；j <=2n；j++ ） x＋＋； } 9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法 分析、算法实现、程序调试、结果整理文档编制。 10、算法是指解决问题的 2、什么是算法算法嘚特征有哪些？ 答：1）算法：指在解决问题时按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲算法：就是解决问题的方法或过程。 2）特征：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性 ； ４)有穷性 . . 3、给出算法的定义何谓算法的复杂性？ 计算丅例在最坏情况下的时间复杂性 for(j=1;j<=n;j++)

一、填空题（20 分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算此 外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0 个或多个输入 一个或多个输 出 2.算法的复杂性有时间复杂性 空间复杂性の分衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显著特征是 该问题具有最优子结构性质 4.若序列 X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}请給出序列 X 和 Y 的一个最长公共子序列 {BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间问题的解空间至少应包含一个（最优）解 6.动态规劃算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 然后从这些子 问题 的解得到原问题的解。 7.以深度优先方式系统搜索問题解的算法称为回溯法 8.0-1 背包问题的 回 溯算法所需的 计算时 间为 o(n*2n) ,用动态规划算法所 需的计 算时间为 o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子結构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法 二、综合题（50 分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子結构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最 优解； 2. 流水作业调度问题的 johnson 算法的思想 ①令 N1={i|ai<bi}，N2={i|ai>=bi}；②将 N1 中作業按 ai 的非减序排序得到 N1’将 N2 中作业按 bi 的 非增序排序得到 N2’；③N1’中作业接 N2’中作业就构成了满足