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

第 1 页 共 12 页 山东科技大学山东科技大学 20072008 学年第一学期学年第一学期 算法设计与分析考试试卷算法设计与分析考试试卷 班级姓名学号_ 算法设计与分析（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， 求矩阵链积 A1A2A3A4A5A6的最佳求积顺序。 （要求：给出计算步骤） （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 被划分成 k2 个不相交的子集 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， 求矩阵链积 A1A2A3A4A5A6的最佳求积顺序。 （20 分） 3、对于下图使用 Dijkstra 算法求由顶点 a 到其他各个顶点的最短路径。并给出求各个顶点对之间 的最短路径的算法思想。 （20 分） 。 4、15 谜问题：在一个 44 的方格的棋盘上，将数字 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 分】 非递归算法： 输入：递减数组 Aleft:right，待搜索元素 v。 【1 分】 输出：v 在 A 中的位置 pos，或者不在 A 中的消息（-1） 。 【1 分】 步骤： 【3 分】 int BinarySearch(intA,int left,int right,int v) int mid; while (leftAmid) right=mid-1; else left=mid+1; return -1; （3）递归算法： 输入：递减数组 Aleft:right，待搜索元素 v。 【1 分】 输出：v 在 A 中的位置 pos，或者不在 A 中的消息（-1） 。 【1 分】 步骤： 【3 分】 int BinarySearch(intA,int left,int right,int v) int mid; if (leftAmid) 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 比较，13527，在前半部分搜索；再次 32 比较，13532，在前半部分 搜索；与 135 比较，相同，返回 0。 【2 分】 二、 【20 分】 用 V1表示已经找到最短路径的顶点，V2表示与 V1中某个顶点相邻接且不在 V1中的顶点；E1表示 加入到最短路径中的边，E2为与 V1中的顶点相邻接且距离最短的路径。 【1 分】 步骤V1V2E1E2 1.abab 2.a,bdabbd 3.a,b,dc,fab,bddc,df 4.a,b,d,cfab,bddf 5.a,b,c,d,feab,bd,dc,dffe 6.a,b,c,d,e,fgab,bd,dc,df,feeg 7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh 8.a,b,c,d,e,f,g,hab,bd,de,df,fe,eg,gh【以上每步 2 分】 结果：从 a 到 h 的最短路径为abdfegh，权值为 18。 【1 分】 求所有顶点对之间的最短路径可以使用 Dijkstra 算法，使其起始节点从 a 循环到 h，每次求起 始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。 【2 分】 三、按照单位效益从大到小依次排列这 7 个物品为：FBGDECA。将它们的序号分别记为 17。 则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得： 【排序 1 分】 第 7 页 共 12 页 a a a b a a c Q1 1 1x 2 1x 3 1x 4 1x 5 0x 6 0x 7 0x de e 4 0x 3 0x 4 1x e 5 1x f 6 0x g 5 0x h 4 0x i 2 0x j 1 0x 【状态空间搜索树及其计算过程 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 c40403050 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）输入：递减数组 Aleft:right，待搜索元素 v。 【1 分】 输出：v 在 A 中的位置 pos，或者不在 A 中的消息（-1） 。 【1 分】 步骤： 【8 分】 int BinarySearch(intA,int left,int right,int v) int mid; while (leftAfirst) right=first-1; else if (v=Asecond) return second; else if (vAsecond) left=first+1;right=second-1; else left=second+1; return -1; （3）搜索 118：11827，所以 right3；118115，所以 right1；118118，找到。 【2 分】 搜索 31：3127，所以 right3；31，每次选择 F 中覆盖了尽