算法设计与分析试题

1、算法设计与分析试题对于下图使用 Dijkstra算法求由顶点 a到顶点 h 的最短路径解： 用 V1表示已经找到最短路径的顶点，V2 表示与 V1中某个顶点相邻接且不在步骤V 1 V2E1E21.a bab2.a,bdabbd3.a,b,dc,f ab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,f eab,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,gh ab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 【以上每步 2 分】V1中的顶点；

2、E1 表示加入到最短路径中的边， 短的路径。【 1分】E2为与 V1 中的顶点相邻接且距离最结果：从 a 到 h 的最短路径为 a b d f e g h ，权值为 18。【 1 分】求所有顶点对之间的最短路径可以使用 Dijkstra 算法，使其起始节点从 a 循环到 h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点 对之间的最短路径。【2 分】二、 假设有 7 个物品，它们的重量和价值如下表所示。 若这些物品 均不能被分割，且背包容量 M150，使用回溯方法求解此背包问题。 请写出状态空间搜索树。物品ABCDEFG重3365412量5000005价1435343值0000500

3、解：按照单位效益从大到小依次排列这 7个物品为： FBGDEC。A将它们的序号分别记为 17。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值 通过如下方式求得：【排序 1 分】状态空间搜索树及其计算过程 17 分，每个节点1 分】ab.c40 40 30 50 10 170(1,1,1,1,0,0,1)40 40 30 50 35 115740 40 30 50 30 177.5 (1,1,1,1,0, 7 ,0)6012 115 190.625 (1,1,1,1,7,0,0)40 8d.40 40 30 35 30 150 105 167.5 (1,1,1,0,1, 3 ,0)60

4、 4e. 40 40 50 35 30 150 130 175 (1,1,0,1,1,1,0)f.60 3(1,1,0,1,1,0,47)150 13040 40 50 35 10 170.7135g. 40 40 50 30 160(1,1,0,1,0,1,0)(1,1,0,0,1,1, 27)h. 40 40 35 30 10 150 140 146.8535i. 40 30 50 35 30 150 125 167.5 (1,0,1,1,1, 5 ,0)60 12j. 40 30 50 35 30 150 145 157.5 (0,1,1,1,1,1 ,0)60 12在 Q1 处获得该问

5、题的最优解为 （1,1,1,1,0,0,1），背包效益为 170。即在背包中装入 物品 F、B、G、D、A时达到最大效益，为 170，重量为 150。【结论 2 分】三、 已知 Ak （aij（k）ri*ri 1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3， r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积 A1× A2× A3×A4× A5× A6的最佳 求积顺序。（要求：给出计算步骤）解：使用动态规划算法进行求解 求解矩阵为：【每个矩阵 18 分】12345610150330405165520102036033

6、024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘积序列为（ A1A2）（A3A4）（A5A6），共执行乘法 2010 次。【结论 2 分】四、回答如下问题：1）什么是算法？算法的特征有哪些？2）什么是 P 类问题？什么是 NP类问题？请描述集合覆盖问题 的近似算法的基本思想。解：（1）算法是解决某类问题的一系列运算的集合【 2 分】。具有有穷行、可行性、确定性、 0个或者多个输入、 1 个或者多个输出【 8分】。 （2）用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题【2 分】

7、。用不确定的图灵机在多项式实践内可解的判定问题称为 P类问题。【2 分】 集合覆盖问题的近似算法采用贪心思想：对于问题 <X,F>，每次选择 F 中覆 盖了尽可能多的未被覆盖元素的子集 S，然后将 U中被 S 覆盖的元素删除，并将 S加入 C中，最后得到的 C就是近似最优解。【6 分】五、排序和查找是常用的计算机算法。按照要求完成以下各题：1）对数组 A=15，9，115，118，3，90，27，25，5 ，使用合 并排序方法将其排成递减序。2） 若改变二分搜索法为三分搜索法，即从一个递减序列A 中寻找元素 Z，先与元素 An比较，若Z A n ，则在前面 n 个 3 3 3 元素

8、中寻找 Z；否则与 A 2n 比较，总之使余下的序列为 n 个 33 元素。给出该方法的伪代码描述。3）使用上述算法对（ 1）所得到的结果搜索如下元素，并给出 搜索过程： 118， 31，25。解：（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 分

9、】 输出： v 在 A中的位置 pos，或者不在 A中的消息（ -1 ）。【 1 分】 步骤：【8 分】int BinarySearch(int A,int left,int right,int v)int mid;while (left<=right) first=left+(right-left+1)/3; second=left+(right-left+1)/3*2; if (v=Afirst) return first; else if (v>Afirst) right=first-1; else if (v=Asecond) return second; else if

10、(v>Asecond) left=first+1;right=second-1; else left=second+1;return -1;（ 3）搜索 118：118>27，所以 right 3；118>115，所以 right 1； 118118， 找到。【2 分】搜索 31：31>27，所以 right 3；31<90，所以 left=4 ，结束，未找到。【2 分】 搜索 25：9<25<27，所以 left=5 ，right=6 ；2525，找到。【1 分】六、假设有 7 个物品，它们的重量和价值如下表所示。 若这些物品 均可以被分割，且背包容

11、量 M150，如果使用贪心方法求解此背 包问题，请回答：（ 20 分）。（4）对各个物品进行排序时，依据的标准都有哪些？（5）使用上述标准分别对 7 个物品进行排序，并给出利用各个 顺序进行贪心求解时获得解。（6）上述解中哪个是最优的？物品ABCDEFG重336541220%，得到价值为 165。【5 分】使用价值从大到小： DFBEGC，A得到贪心解为： DFBE全部放入，而 G放入 80%， 得到价值为： 189。【5 分】使用单位价值从大到小： FBGDEC，A得到贪心解为：FBGD全部放入，而E放入 87.5%， 得到价值为 190.625 。【 5 分】（3）显然使用单位价值作为标准

12、得到的是最优解。 【2 分】七、多段图问题：设 G（V ，E）是一个赋权有向图，其顶点集 V 被 划分成 k>2个不相交的子集 Vi：1 i k ，其中， V1和 Vk分别只有一 个顶点 s（称为源）和一个顶点 t（称为汇），图中所有的边 （u,v ），u Vi ， v Vi 1。求由 s 到 t 的最小成本路径。（ 25 分）（7）给出使用动态规划算法求解多段图问题的基本思想V18）使用上述方法求解如下多段图问题。V5V2V3V4241s1解：（1）基本思想：设 P（i,j） 是从 Vi 中的节点 j 到汇点 t 的最小成本路径，Cost（i,j） 是其成本。则 Cost（i,j）=m

13、inc（j,h）+Cost（i+1,h）|h Vi+1,（j,h） E 。边界条件是（2）V19 16,2/3 1s6,21/3 71)若 h=t，则 Cost(h,t) 0；(2)Cost(k-1,j) c(j,t) 。【10 分】 求解过程可以表示为： 【6分，每个节点 0.5 分】V5V2V3V47,7 27,104,129,6 2 4 2 6 6 99,6 237 7 73 148,8 11 57,104 1115,851,128 8 6 117,10/11其中每个节点标示的序偶 （p,q） 中，p表示节点到 t 的成本，q 表示后继 节 点 的 编 号 。 从 而 ， 最 优 路 径

14、 为 ： 1 2 7 10 12 和1 3 6 10 12，成本为 16。【4 分】八、设 x1、x2、x3 是一个三角形的三条边，而且 x1+x2+x3=14。请问有 多少种不同的三角形？给出解答过程。解：由于 x1、x2、x3是三角形的三条边， 从而 xi +xj >xk，|x i -x j|<x k，（i,j,k=1,2,3 ）， 【4分】根据 x1+x2+x3=14 可知 1<xi<7（i=1,2,3 ）【4分】。利用回溯法求解得到：7分，每个节点 0.5 分】即有 4 个可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。【5 分】九、15

15、 谜问题：在一个 4×4 的方格的棋盘上，将数字 1 到 15 代表的 15 个棋子以任意的顺序置入各方格中，空出一格。要求通过有限 次的移动， 把一个给定的初始状态变成目标状态。 移动的规则是： 每次只能把空格周围的四格数字 (棋子) 中的任意一个移入空格， 从而 形成一个新的状态。为了有效的移动，设计了估值函数C1(x) ，表示在结点 x 的状态下，没有到达目标状态下的正确位置的棋子的个数。解：【每个节点 1 分，注意限界值1245637910128131411157123456791012813141115612456379101281314111512345679101281

16、31411151234561279108131411151235674910128131411151234568910712131411512345678910111213141总共20 分】124563791012813141115712345679101281314111541234567891012131411151234567891011121314152112345678910121314111533123456789101213141115123456789101112131415123456789101215131411十、设数组 A有 n 个元素，需要找出其中的最大最小值。 (

17、20 分)(1)请给出一个解决方法，并分析其复杂性。(2) 把 n 个元素等分为两组 A1和 A2，分别求这两组的最大值和 最小值，然后分别将这两组的最大值和最小值相比较， 求出全部元素 的最大值和最小值。 如果 A1和 A2 中的元素多于两个， 则再用上述方 法各分为两个子集。 直至子集中元素至多两个元素为止。 这是什么方 法的思想？请给出该方法的算法描述，并分析其复杂性。 解：(1)基本思想：从头到尾逐个扫描，纪录最大和最小元素。 【2 分】 输入：具有 n 个元素的数组【 1分】 输出：最大值和最小值【 1 分】 步骤：【4 分】void FindMaxMin(int A, int n,

18、 int max, int min)max=min=A0;for (i=1;i<n;i+)if (Ai>max) max=Ai;if (Ai<min) min=Ai;复杂性分析：由于是从头到尾扫描各个元素， 而每个元素都要与 max和 min比较 一遍，从而时间复杂性为： O(n) 。【 2 分】( 2)【10分】 void FindMaxMin(int left,int right, int max, int min) if (left=right) max=min=Aleft;else if (left=right-1) max=(Aleft<Aright?Arig

19、ht:Aleft);min=( Aleft<Aright?Aleft:Aright);elsemid=(left+right)/2;FindMaxMin(left,mid,gmax,gmin); FindMaxMin(mid+1,right,hmax,hmin); max=(gmax<hmax?hmax:gmax); min=(gmin<hmin?gmin:hmin);十一、用分支限界法解装载问题时， 对算法进行了一些改进， 下面的 程序段给出了改进部分； 试说明斜线部分完成什么功能， 以及这样做 的原因，即采用这样的方式，算法在执行上有什么不同。/ 检查左儿子结点Type

20、wt = Ew + wi; /左儿子结点的重量if (wt <= c) / 可行结点 if (wt > bestw) bestw = wt;/ 加入活结点队列if (i < n) Q.Add(wt);/ 检查右儿子结点if (Ew + r > bestw && i < n) Q.Add(Ew); / 可能含最优解 Q.Delete(Ew); / 取下一扩展结点解：斜线标识的部分完成的功能为：提前更新 bestw 值； 这样做可以尽早的进行对右子树的剪枝。具体为：算法 Maxloading 初始 时将 bestw 设置为 0，直到搜索到第一个叶结点时

21、才更新 bestw 。因此在算法搜 索到第一个叶子结点之前，总有 bestw=0，r>0 故 Ew+r>bestw 总是成立。也就 是说，此时右子树测试不起作用。为了使上述右子树测试尽早生效，应提早更新 bestw 。又知算法最终找到的 最优值是所求问题的子集树中所有可行结点相应重量的最大值。 而结点所相应得 重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新 bestw 的值。十二、简要回答下列问题：1. 算法重要特性是什么？ 算法分析的目的是什么？算法的时间复杂 性与问题的什么因素相关？2. 什么是哈密顿环问题？用回溯法求解哈密顿环，如何定义判定函 数？ 答：

22、1. （1）确定性、可实现性、输入、输出、有穷性， （2）分析算法占用计算 机资源的情况，对算法做出比较和评价，设计出额更好的算法， （3）算法的时间 复杂性与问题的规模相关，是问题大小 n 的函数；2. （1）哈密顿环是指一条沿着图 G的 N 条边环行的路径，它的访问每 个节点一次并且返回它的开始位置， （2）当前选择的节点 Xk 是从未到过的节 点,即 Xk Xi（i=1,2, ,k-1） ，且 C（Xk-1, Xk） ，如果 k=-1 ，则 C（Xk, X1） 。十三、简要回答下列问题：1. 快速排序的基本思想是什么。2. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？答：1

23、. 快速排序的基本思想是在待排序的 N个记录中任意取一个记录，把 该记录放在最终位置后， 数据序列被此记录分成两部分。 所有关键字比该记录关 键字小的放在前一部分， 所有比它大的放置在后一部分， 并把该记录排在这两部 分的中间， 这个过程称作一次快速排序。 之后重复上述过程， 直到每一部分内只 有一个记录为止。2. 在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既 调用它自己本身，这称为直接递归。如果过程或者函数 P 调用过程或者函数 Q，Q又调用 P，这个称为间接递归。消除递归一般要用到栈这种数据结构十四、写出多段图最短路经动态规划算法求解下列实例的过程， 并求出最优值。各边

24、的代价如下：C(1,2)=3 ， C(1,3)=5 ，C(1,4)=2C(2,6)=8 ， C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4 ， C(4,5)=2 ，C(4,6)=1C(5,8)=4 ， C(6,8)=5 ，C(7,8)=6解： Cost(4,8)=0Cost(3,7)= C(7,8)+0=6 ，D5=8Cost(3,6)= C(6 ，8)+0=5, D6=8Cost(3,5)= C(5 ， 8)+0=4 D7=8Cost(2,4)= minC(4 ，6)+ Cost(3,6), C(4 ，5)+ Cost(3,5)= min1+ 5, 2+4=6 D4=6Cost(2

25、,3)= minC(3 ，6)+ Cost(3,6) = min4+5=9 D3=5Cost(2,2)= minC(2 ，6)+ Cost(3,6), C(2 ，7)+ Cost(3,7)= min8+5, 4+6=10 D2=7Cost(1,1)= minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+Cost(2,4)= min3+10, 5+9,2+6= 8D1=41468十五、写出 maxmin算法对下列实例中找最大数和最小数的过程。数组 A=(48,12,61,3,5,19,32,7)解： 写出 maxmin算法对下列实例中找最大数和最小数的过程。数组 A=()1、 48,12,61,3, 5,19,32,72、48,12 61,3 5,19 32,73、48 61, 12 3 19 32，574、61 32 3 55、61 3十六、快速排序算法对下列实例排序，算法执行过程中，写出数 组 A 第一次被分割的过程。A=(65,70,75,80,85,55,50,2)解： 第一个分割元素为 65(1) (2) (3)