算法分析与设计考试题目.pdfVIP

第 1 页 共 12 页 山东科技大学山东科技大学 2007 2008 学年第一学期学年第一学期 算法设计与分析 考试试卷 算法设计与分析 考试试卷 班级姓名学号 算法设计与分析 1 1 排序和查找是经常遇到的问题 按照要求完成以下各题 20 分 1 对数组 A 15 29 135 18 32 1 27 25 5 用快速排序方法将其排成递减序 2 请描述递减数组进行二分搜索的基本思想 并给出非递归算法 3 给出上述算法的递归算法 4 使用上述算法对 1 所得到的结果搜索如下元素 并给出搜索过程 18 31 135 2 对于下图使用 Dijkstra 算法求由顶点 a 到顶点 h 的最短路径 20 分 3 假设有 7 个物品 它们的重量和价值如下表所示 若这些物品均不能被分割 且背包容量 M 150 使用回溯方法求解此背包问题 请写出状态空间搜索树 20 分 物品ABCDEFG 重量35306050401025 价值10403050354030 4 已知 1 ii k kijr r Aa k 1 2 3 4 5 6 r1 5 r2 10 r3 3 r4 12 r5 5 r6 50 r7 6 求矩阵链积 A1 A2 A3 A4 A5 A6的最佳求积顺序 要求 给出计算步骤 20 分 5 回答如下问题 20 分 1 什么是算法 算法的特征有哪些 2 什么是 P 类问题 什么是 NP 类问题 请描述集合覆盖问题的近似算法的基本思想 第 2 页 共 12 页 算法设计与分析 2 1 排序和查找是常用的计算机算法 按照要求完成以下各题 20 分 1 对数组 A 15 9 115 118 3 90 27 25 5 使用合并排序方法将其排成递减序 2 若改变二分搜索法为三分搜索法 即从一个递减序列 A 中寻找元素 Z 先与元素 3 n A比较 若 3 n ZA 则在前面 3 n 个元素中寻找 Z 否则与 2 3 n A比较 总之使余下的序列为 3 n 个 元素 给出该方法的伪代码描述 3 使用上述算法对 1 所得到的结果搜索如下元素 并给出搜索过程 118 31 25 2 假设有 7 个物品 它们的重量和价值如下表所示 若这些物品均可以被分割 且背包容量 M 150 如果使用贪心方法求解此背包问题 请回答 20 分 1 对各个物品进行排序时 依据的标准都有哪些 2 使用上述标准分别对 7 个物品进行排序 并给出利用各个顺序进行贪心求解时获得解 3 上述解中哪个是最优的 物品ABCDEFG 重量35306050401025 价值10403050354030 3 多段图问题 设 G V E 是一个赋权有向图 其顶点集 V 被划分成 k 2 个不相交的子集 Vi 1ik 其中 V1和 Vk分别只有一个顶点 s 称为源 和一个顶点 t 称为汇 图中所有的边 u v i uV 1i vV 求由 s 到 t 的最小成本路径 25 分 1 给出使用动态规划算法求解多段图问题的基本思想 2 使用上述方法求解如下多段图问题 第 3 页 共 12 页 4 回答如下问题 15 分 1 什么是算法 算法的特征有哪些 2 什么是 P 类问题 什么是 NP 类问题 请描述集合覆盖问题的近似算法的基本思想 5 设 x1 x2 x3是一个三角形的三条边 而且 x1 x2 x3 14 请问有多少种不同的三角形 给出解 答过程 20 分 第 4 页 共 12 页 算法设计与分析 3 1 设数组 A 有 n 个元素 需要找出其中的最大最小值 20 分 1 请给出一个解决方法 并分析其复杂性 2 把 n 个元素等分为两组 A1 和 A2 分别求这两组的最大值和最小值 然后分别将这两组的最 大值和最小值相比较 求出全部元素的最大值和最小值 如果 A1 和 A2 中的元素多于两个 则再用上述方法各分为两个子集 直至子集中元素至多两个元素为止 这是什么方法的思想 请给出该方法的算法描述 并分析其复杂性 2 已知 1 ii k kijr r Aa k 1 2 3 4 5 6 r1 5 r2 10 r3 3 r4 12 r5 5 r6 50 r7 6 求矩阵链积 A1 A2 A3 A4 A5 A6的最佳求积顺序 20 分 3 对于下图使用 Dijkstra 算法求由顶点 a 到其他各个顶点的最短路径 并给出求各个顶点对之间 的最短路径的算法思想 20 分 4 15 谜问题 在一个 4 4 的方格的棋盘上 将数字 1 到 15 代表的 15 个棋子以任意的顺序置入 各方格中 空出一格 要求通过有限次的移动 把一个给定的初始状态变成目标状态 移动的规 则是 每次只能把空格周围的四格数字 棋子 中的任意一个移入空格 从而形成一个新的状态 为了有效的移动 设计了估值函数 C1 x 表示在结点 x 的状态下 没有到达目标状态下的正确位 置的棋子的个数 20 分 请使用该估计函数 对图示的初始状态 给出使用分支限界方法转换到 目标状态的搜索树 初始状态目标状态 5 设 x1 x2 x3是一个三角形的三条边 而且 x1 x2 x3 14 请问有多少种不同的三角形 给出解 答过程 20 分 124 5637 910128 13141115 1234 5678 9101112 131415 第 5 页 共 12 页 算法设计与分析 算法设计与分析 1 参考答案与评分标准 参考答案与评分标准 一 20 分 1 第一步 15 29 135 18 32 1 27 25 5 第二步 29 135 18 32 27 25 15 1 5 1 分 第三步 135 32 29 18 27 25 15 5 1 1 分 第四步 135 32 29 27 25 18 15 5 1 1 分 2 基本思想 首先将待搜索元素 v 与数组的中间元素 2 n A 进行比较 如果 2 n vA 则在 前半部分元素中搜索 v 若 2 n vA 则搜索成功 否则在后半部分数组中搜索 v 2 分 非递归算法 输入 递减数组 A left right 待搜索元素 v 1 分 输出 v 在 A 中的位置 pos 或者不在 A 中的消息 1 1 分 步骤 3 分 int BinarySearch intA int left int right int v int mid while leftA mid right mid 1 else left mid 1 return 1 3 递归算法 输入 递减数组 A left right 待搜索元素 v 1 分 输出 v 在 A 中的位置 pos 或者不在 A 中的消息 1 1 分 步骤 3 分 int BinarySearch intA int left int right int v int mid if leftA mid return BinarySearch A left mid 1 v else return BinarySearch A mid 1 right v else return 1 4 搜索 18 首先与 27 比较 1827 在前半部分搜索 再次 32 比较 3129 此时只有一个元素 未找到 返回 1 2 分 搜索 135 首先与 27 比较 135 27 在前半部分搜索 再次 32 比较 135 32 在前半部分 搜索 与 135 比较 相同 返回 0 2 分 二 20 分 用 V1表示已经找到最短路径的顶点 V2表示与 V1中某个顶点相邻接且不在 V1中的顶点 E1表示 加入到最短路径中的边 E2为与 V1中的顶点相邻接且距离最短的路径 1 分 步骤V1V2E1E2 1 a b ab 2 a b d ab bd 3 a b d c f ab bd dc df 4 a b d c f ab bd df 5 a b c d f e ab bd dc df fe 6 a b c d e f g ab bd dc df fe eg 7 a b c d e f g h ab bd dc df fe eg gh 8 a b c d e f g h ab bd de df fe eg gh 以上每步 2 分 结果 从 a 到 h 的最短路径为abdfegh 权值为 18 1 分 求所有顶点对之间的最短路径可以使用 Dijkstra 算法 使其起始节点从 a 循环到 h 每次求起 始节点到其他节点的最短路径 最终可以求得所有顶点对之间的最短路径 2 分 三 按照单位效益从大到小依次排列这 7 个物品为 FBGDECA 将它们的序号分别记为 1 7 则可生产如下的状态空间搜索树 其中各个节点处的限界函数值通过如下方式求得 排序 1 分 第 7 页 共 12 页 a a a b a a c Q1 1 1x 2 1x 3 1x 4 1x 5 0 x 6 0 x 7 0 x de e 4 0 x 3 0 x 4 1x e 5 1x f 6 0 x g 5 0 x h 4 0 x i 2 0 x j 1 0 x 状态空间搜索树及其计算过程 17 分 每个节点 1 分 a 150 115 4040305035190 625 40 7 1 1 1 1 0 0 8 b 150 115 4040305030177 5 60 7 1 1 1 1 0 0 12 c 40403050 10170 1 1 1 1 0 0 1 d 150 105 4040303530167 5 60 3 1 1 1 0 1 0 4 e 150 130 4040503530175 60 1 1 1 0 1 1 0 3 f 150130 4040503510170 71 35 4 1 1 0 1 1 0 7 g 40405030160 1 1 0 1 0 1 0 h 150 140 40403530 10146 85 35 2 1 1 0 0 1 1 7 i 150 125 4030503530167 5 60 5 1 0 1 1 1 0 12 j 150 145 4030503530157 5 60 1 0 1 1 1 1 0 12 在 Q1处获得该问题的最优解为 1 1 1 1 0 0 1 背包效益为 170 即在背包中装入物品 F B G D A 时达到最大效益 为 170 重量为 150 结论 2 分 四 使用动态规划算法进行求解 求解矩阵为 每个矩阵 18 分 第 8 页 共 12 页 123456 1015033040516552010 2036033024301950 301809301770 4030001860 501500 60 因此 最佳乘积序列为 A1A2 A3A4 A5A6 共执行乘法 2010 次 结论 2 分 五 1 算法是解决某类问题的一系列运算的集合 2 分 具有有穷行 可行性 确定性 0 个 或者多个输入 1 个或者多个输出 8 分 2 用确定的图灵机可以在多项式实践内可解的判定问题称为 P 类问题 2 分 用不确定的图灵 机在多项式实践内可解的判定问题称为 P 类问题 2 分 集合覆盖问题的近似算法采用贪心思想 对于问题 每次选择 F 中覆盖了尽可能多的未 被覆盖元素的子集 S 然后将 U 中被 S 覆盖的元素删除 并将 S 加入 C 中 最后得到的 C 就是近 似最优解 6 分 算法设计与分析 算法设计与分析 2 参考答案与评分标准 参考答案与评分标准 一 1 第一步 15 9 115 118 3 90 27 25 5 第二步 15 9 118 115 90 3 27 25 5 第三步 118 115 15 9 90 27 25 3 5 第四步 118 115 90 27 25 15 9 3 5 第五步 118 115 90 27 25 15 9 5 3 5 分 每步 1 分 2 输入 递减数组 A left right 待搜索元素 v 1 分 输出 v 在 A 中的位置 pos 或者不在 A 中的消息 1 1 分 步骤 8 分 int BinarySearch intA int left int right int v int mid while leftA first right first 1 else if v A second return second else if v A second left first 1 right second 1 else left second 1 return 1 3 搜索 118 118 27 所以 right 3 118 115 所以 right 1 118 118 找到 2 分 搜索 31 31 27 所以 right 3 31 90 所以 left 4 结束 未找到 2 分 搜索 25 9 25 27 所以 left 5 right 6 25 25 找到 1 分 二 1 标准 重量 价值和单位价值 3 分 每个 1 分 2 使用重量从小到大 FGBAEDC 得到贪心解为 FGBAE 全部放入 而 D 放入 20 得到价值为 165 5 分 使用价值从大到小 DFBEGCA 得到贪心解为 DFBE 全部放入 而 G 放入 80 得到价值 为 189 5 分 使用单位价值从大到小 FBGDECA 得到贪心解为 FBGD 全部放入 而 E 放入 87 5 得 到价值为 190 625 5 分 3 显然使用单位价值作为标准得到的是最优解 2 分 三 1 基本思想 设 P i j 是从 Vi 中的节点 j 到汇点 t 的最小成本路径 Cost i j 是其成本 则 i 1 Cost i j min c j h Cost i 1 h hV j h E 边界条件是 1 若 h t 则 Cost h t 0 2 Cost k 1 j c j t 10 分 2 求解过程可以表示为 6 分 每个节点 0 5 分 其中每个节点标示的序偶 p q 中 p 表示节点到 t 的成本 q 表示后继节点的编号 从而 最 优路径为 1 2 7 10 12 和 1 3 6 10 12 成本为 16 4 分 四 1 算法是解决某类问题的一系列运算的集合 2 分 具有有穷行 可行性 确定性 0 个或者多个输入 1 个或者多个输出 8 分 第 10 页 共 12 页 2 用确定的图灵机可以在多项式实践内可解的判定问题称为 P 类问题 2 分 用不确定的 图灵机在多项式实践内可解的判定问题称为 P 类问题 2 分 集合覆盖问题的近似算法采用贪心思想 对于问题 每次选择 F 中覆盖了尽可能多的未 被覆盖元素的子集 S 然后将 U 中被 S 覆盖的元素删除 并将 S 加入 C 中 最后得到的 C 就是近 似最优解 6 分 五 由于 x1 x2 x3 是三角形的三条边 从而 xi xj xk xi xj xk i j k 1 2 3 4 分 根 据 x1 x2 x3 14 可知 1 xi 7 i 1 2 3 4 分 利用回溯法求解得到 7 分 每个节点 0 5 分 即有 4 个可行解 6 6 2 6 5 3 6 4 4 5 5 4 5 分 算法设计与分析