山东科技大学算法试题-(3).docVIP

PAGE 第 PAGE 2 页 共 NUMPAGES 3 页 山东科技大学 — 学年第 学期 《算法设计与分析》考试试卷 班级 姓名 学号 题号 一 二 三 四 五 总得分 评卷人 审核人 得分 排序和查找是常用的计算机算法。按照要求完成以下各题：（20分） 对数组A={15，29，135，18，32，1，27，25，5}，使用快速排序方法将其排成递减序。 若改变二分有哪些信誉好的足球投注网站法为三分有哪些信誉好的足球投注网站法，即从一个递减序列A中寻找元素Z，先与元素比较，若，则在前面个元素中寻找Z；否则与比较，总之使余下的序列为个元素。给出该方法的描述。 使用上述算法对（1）所得到的结果有哪些信誉好的足球投注网站如下元素，并给出有哪些信誉好的足球投注网站过程：18，31，135。 数字三角形问题。如下图是一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。（20分） 使用穷举法：列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和。使用该方法求解上述问题。 使用动态规划方法：按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段……第1阶段(起始点)各决策点至第n行的最佳路径。试用该方法求解上图。并与（1）方法进行比较。（提示：哪个的复杂性更低？） 假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，请回答：（20分）。 对各个物品进行排序时，依据的标准都有哪些？ 使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。 上述解中哪个是最优的？ 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 （20分）15谜问题：在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。 请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的有哪些信誉好的足球投注网站树。 1 2 4 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 初始状态 目标状态 五、回答如下问题：（20分） 什么是算法？算法的特征有哪些？ 什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。