《湖南大学复习算法分析期末答案大题》由会员分享，可在线阅读，更多相关《湖南大学复习算法分析期末答案大题（28页珍藏版）》请在金锄头文库上搜索。
1、一、 解答题1. 机器调度问题。问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi，sifi 。si，fi为处理任务i的时间范围。两个任务i，j重叠指两个任务的时间范围区间有重叠，而并非指i，j的起点或终点重合。例如：区间1，4与区间2，4重叠，而与4，7不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。问题实例：若任务占用的时间范围是1，4，2，5，4，5，2，6，4，7，则按时完成所有任务最少需要几台机器？（提
2、示：使用贪心算法）画出工作在对应的机器上的分配情况。3. 单源最短路径的求解。问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代7. 最长公共子序列问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。
3、由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列Xi和Yj的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：在程序中，bij记录Cij的值是由哪一个子问题的解得到的。三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。52863174各边的代价如下：C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4，
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,3)= minC(3，6)+ Cost(3,6) = min4+5=9 D3=5Cost(2,2)= minC(2，6)+ Cost(3,6), C(2，7)+ Co
5、st(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=414682、 写出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、 4861, 123 1932，574、 6132 3
6、55、 61 31、 快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。 A=(65,70,75,80,85,55,50,2)解：第一个分割元素为65(1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 665 2 50 55 85 80 75 70 4 655 70 75 80 85 65 50 22、 归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7)
7、解： 48,12,61,3 5,19,32,748,12 61,3 5,19 32,712,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，323,5, 7,12，19，32，48,61 3、 写出图着色问题的回溯算法的判断Xk是否合理的过程。解：i0while ik do if Gk,i=1 and Xk= Xi then return false ii+1repeat if i= k then return true4、 对于下图，写出图着色算法得出一种着色方案的过程。2314解：K1X1 1 , 返回 trueX21,返回false; X2X2+1=2,
8、 返回 trueX31 ,返回false; X3X3+1=2, 返回false;X3X3+1=3, 返回 true X41, 返回false; X4X4+1=2, 返回false;X4X4+1=3, 返回 true找到一个解 （1，2，3，3）5、 写出第7题的状态空间树。解：X1=1X2=2X3=33X4=338、写出归并排序算法对下列实例排序的过程。(6,2,9,3,5,1,8,7)解：调用第一层次 6,2,9,3 5,1,8,7 分成两个子问题 调用第二层次 6,2 9,3 5,1 8,7 分成四个子问题 调用第三层次 6 2 9 3 5 1 8 7 分成八个子问题 调用第四层次 只有一
9、个元素返回上一层第三层归并 2 ,6 3, 9 1,5 7,8 返回上一层第二层归并 2 ,3,6, 9 1,5,7,8 返回上一层第一层归并 1, 2 ,3, 5 ,6, 7, 8,9 排序结束，返回主函数9、写出用背包问题贪心算法解决下列实例的过程。 P=(18,12,4,1) W=(12,10,8,3) M=25解: 实例符合P(i)/W(i)P(i+1)/W(i+1)的顺序。 CU25,X0 W1 CU: x11; CUCU-W1=13; W2CU: x3CU/ W3=3/8;实例的解为：（1，1，3/8，0）11、有一个有序表为1，3，9，12，32，41，45，62，75，77，8
10、2，95，100，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。解：有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。一共要要执行四次才能找到值为82的数。12、使用prim算法构造出如下图G的一棵最小生成树。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6解：使用普
11、里姆算法构造出如下图G的一棵最小生成树。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=61316136412645126343313、有如下函数说明int f(int x,int y) f=x Mod y +1;已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c)后，k的值是多少并写出详细过程。解：有如下函数说明int f(int x,int y) f=x Mod y +
12、1;已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c)后，k的值是多少并写出详细过程。 K的值是5四、设计算法 1. 设有n项独立的作业1,2, n,由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。解：对于处理机j，用Sj 表示处理机j已有的作业数，用Pj,k表示处理机j的第k个作业的序号 。1）将作业按照t1t2tn排序2）S1:m清零 j0 /从第一个处理机开始安排3) for i1 to n do /安排n个作业 jj mod m +1 /选下一个处理机SjSj+1; Pj,Sji ； Repeat2. 设有n种面值为:d1
