山东科技大学算法试题 (2) 下载本文

内容发布更新时间 : 2024/6/16 22:02:13星期一 下面是文章的全部内容请认真阅读。

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

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

班级 姓名 学号

题号 得分 一、

一 二 三 四 五 总得分 评卷人 审核人 设数组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 页