内容发布更新时间 : 2024/11/15 7:28:45星期一 下面是文章的全部内容请认真阅读。

山东科技大学 — 学年第 学期

《算法设计与分析》考试试卷

班级 姓名 学号

题号 得分 一、

一 二 三 四 五 总得分 评卷人 审核人 设数组A有n个元素，需要找出其中的最大最小值。（20分）

（1） 请给出一个解决方法，并分析其复杂性。

（2） 把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两

组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。

二、

已知Ak?(aij(k))ri*ri?1，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分） 三、

对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对

之间的最短路径的算法思想。（20分）。

be2g2ad21cf2121433h 四、 15谜问题：在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序

置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。（20分）

第 1 页 共 2 页

请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。 1 2 4 1 2 3 4

5 6 3 7 5 6 7 8

9 10 12 8 9 10 11 12

13 14 11 15 13 14 15

初始状态 目标状态

五、设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。（20分）

第 2 页 共 2 页