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

《算法分析与设计考试题目.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、山东科技大学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个物品，它们的重

2、量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。物品ABCDEFG重量35306050401025价值10403050354030()k4、已知A(a)，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，kijrri*i1求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。（要求：给出计算步骤）（20分）5、回答如下问题：（20分）1)什么是算法？算法的特征有哪些？2)什么是P类问题？什么是NP类问题？请描述集

3、合覆盖问题的近似算法的基本思想。第1页共12页算法设计与分析（2）1、排序和查找是常用的计算机算法。按照要求完成以下各题：（20分）1)对数组A={15，9，115，118，3，90，27，25，5}，使用合并排序方法将其排成递减序。n2)若改变二分搜索法为三分搜索法，即从一个递减序列A中寻找元素Z，先与元素A[]比较，3nn2nn若ZA[]，则在前面[]个元素中寻找Z；否则与A[]比较，总之使余下的序列为[]个3333元素。给出该方法的伪代码描述。3)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：118，31，25。2、假设有7个物

4、品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，请回答：（20分）。1)对各个物品进行排序时，依据的标准都有哪些？2)使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。3)上述解中哪个是最优的？物品ABCDEFG重量35306050401025价值104030503540303、多段图问题：设G＝(V，E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi：1ik，其中，V1和Vk分别只有一个顶点s（称为源）和一个顶点（t称为汇），图中所有的边（u,v

5、），uV，vV。求由s到t的最小成本路径。（25分）ii11)给出使用动态规划算法求解多段图问题的基本思想。2)使用上述方法求解如下多段图问题。第2页共12页4、回答如下问题：（15分）1)什么是算法？算法的特征有哪些？2)什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。5、设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。（20分）第3页共12页算法设计与分析（3）1、设数组A有n个元素，需要找出其中的最大最小值。（20分）1)请给出一个解决方法，并分析其复杂性

6、。2)把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。()k2、已知A(a)，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，kijrri*i1求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。（20分）3、对于下图使用Dijkstra算法求由顶点a

7、到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。（20分）。4、15谜问题：在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。（20分）请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。初始状态目标状态12

8、41234563756789101289101112131411151314155、设x1、x