算法考试题

1、UseInsertionSortAlgorithmtosort{49，38，65，97，76，13，27，49}.Showthesortingprocess.初试序列：（49）38659776132749第一次排序：（3849）659776132749第二次排序：（384965）9776132749第三次排序：（38496597）76132749第四次排序：（3849657697）132749第五次排序：（133849657697）2749第六次排序：（13273849657697）49第七次排序：（1327384949657697）相关算法：VoidStrightInsertSort(inta[]){inti,j;for(i=2;i=length;i++){a[0]=a[i]//a[0]用来保存待插入元素j=i-1;while(a[0]a[j]){a[j+1]=a[j];j--;}a[j+1]=a[0];}}2、WeobservedthataworstcaseforInsertionSortoccurswhenthekeysareinitiallyindecreasingorder.Describeatleasttwootherinitialarrangementsofthekeysthatarealsoworstcases.（我们观察到,一个坏的情况下,为插入排序时发生的键是首先在降序，按键依次开始。说明至少有两个其他的关键，同时也是最坏的情况初步安排。）3、UseQuicksortAlgorithmtosort{49，38，65，97，76，13，27，49}.Showthedividingprocessofthefirstpass.（使用快速排序算法进行排序,{49,38、65、97、76岁、13,27岁,49}。显示第一次排序过程）.27381349769765494、HowmanykeycomparisonsdoesQuicksort(choosingthefirstelementaspivot)doifthearrayisalreadysorted?Howmanyelementmovementsdoesitdo?（如果数组已经被排序，那么用快速排序算法要排多少次？（以第一个元素为中心），要移到多少元素？）n(n-1)/205、CarryoutDFSTraceonthedigraph,andclassifyalltheedges(tree,back,cross,forward).AssumetheverticesareindexedinalphabeticalorderintheadjVerticesarrayandthateachadjacencylistisinalphabeticalorder.（DFS追踪执行有向图,并分类所有的边缘。承担顶点索引按字母顺序排列的adjVertices数组,每个邻接列表是按字母顺序排列的。）A-B-G-F-E-I(A,B)(A,B,G)(A,F)(A,F,E)(A,F,I)C-D-H(C,D)(C,H)6、Forthefollowinggraph,indicatewhichedgeswouldbeintheminimumspanningtreeconstructedbyPrim'sMSTalgorithm,andwhichwouldinthetreeconstructedbyDijkstra'sshortest-pathalgorithmusingv1asthesource.（以下图,指出边缘可能会在最小生成树算法,构造了一本正经的MST且这种在树上所构成的最短路径算法中使用v1作为来源）PRIM:11V1V2V3V431V5V63Dijkstra:(V1，V2)1(V1,V2,V3)2(V1,V2,V3,V5)5(V1,V2,V3,V5,V6)8(V1,V2,V3,V5,V6,V4)97、1.SupposethedimensionsofthematricesA,B,C,andDare30╳1,1╳40,40╳10,and10╳25,respectively,andwewanttoknowhowbesttocomputeA╳B╳C╳D.Showthecomputationprocess,thearrayscost,last,andmultOrdercomputedbyAlgorithms10.1OptimalMatrixMultiplicationOrderand10.2ExtractingOptimalMultiplicationOrder.（Dynamicprogrammingalgorithm）（假设的维矩阵A、B、C、D是30╳1,1╳40,40╳10,and10╳25,分别,我们想知道如何更好的计算A╳B╳C╳D。显示计算过程中,数组,multOrder成本,最后计算最优矩阵乘法算法10.1秩序和10.2提取最佳乘法秩序。(动态规划算法)m[1][1]=0m[1][2]=m[1][1]+m[2][2]+p0*p1=30*1*40=1200m[1][3]=m[1][1]+m[2][3]+p0*p1*p3=0+1*40*10+30*1*10=700m[1][3]=700m[1][3]=m[1][2]+m[3][3]+p0*p2*p3=30*1*40+0+30*40*10=12200m[1][4]=m[1][1]+m[2][4]+p0*p1*p4=0+650+30*1*25=1400m[1][4]=m[1][2]+m[3][4]+p0*p2*p4=30*1*40+40*10*25+30*40*25=41200m[1][4]=1400m[1][4]=m[1][3]+m[4][4]+p0*p3*p4=700+0+30*10*25=8200m[2][2]=0m[2][3]=1*40*10=400m[2][4]=m[2][2]+m[3][4]+p1*p2*p4=0+40*10*25+1*40*25=11000m[2][4]=650m[2][4]=m[2][3]+m[4][4]+p1*p3*p4=1*40*10+0+1*10*25=650m[3][3]=0m[3][4]=40*10*25=10000m[4][4]=0给出示意图m[i][j]jis[i][j]ji8、给出用动态规划方法来解决0-1背包问题的算法。//参数m[i][j]表示的是将前n-i（n,n-1,....i）个物体放入到体积为j的背包中获得的价值。voidknapsack(int[]v,int[]w,intc,int[][]m){intn=v.length-1;intjMax=Math.min(w[n]-1,c);//取较小值/*if(w[n]-1c)jMax=w[n]-1elsejMax=c*//*初始化m[n][j]表示的意思为当第n个物体的体积大于背包体积时，就不选择；当第n个物体的体积小于背包体积时，选择。*/for(intj=0;j=jMax;j++)m[n][j]=0/*含义是将第n个物体放入体积为j的背包中，由于其体积小于物体n的体积，所以不选择*/for(intj=w[n];j=c;j++)m[n][j]=v[n];/*含义是将第n个物体放入体积为j的背包中，当叫jMax=c时，不执行；当jMax=w[n]-1时，j=w[n]...c,所以选择第n个物体*/for(inti=n-1;i1;i--)｛//第i个物体的选择jMax=Math.min(w[i]-1,c);for(intj=0;j=jMax;j++)1234101200700140020400650301000040123410111202330340m[i][j]=m[i+1][j];/*当体积小于第i个物体的体积时，不限则第i个物体*/for(intj=w[i];j=c;j++)m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);｝m[1][c]=m[2][c];if(c=w[1])m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);}9、用改进的动态规划方法解决下列0-1背包问题：n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。得出最大价值是多少？初试时：p[6]={(0,0)},(w5,v5)=(4,6)。因此，q[6]=p[6](w5,v5)={(4,6)}。p[5]=p[6]q[6]={(0,0),(4,6)}。q[5]=p[5](w4,v4)={(0,0),(4,6),(5,4),(9,10)}p[5]q[5]={(0,0),(4,6),(5,4),(9,10)}根据题意知（5，4）是受控点p[4]={(0,0),(4,6),(9,10)}q[4]=p[4](w3,v3)={(6,5),(10,11)}p[4]q[4]={(0,0),(4,6),(6,5),(9,10),(10,11)}p[3]={(0,0),(4,6),(9,10),(10,11)}q[3]=p[3](w2,v2)={(2,3),(6,9)}p[3]q[3]=｛(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)｝p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}q[2]=p[2](w1,v1)={(2,6),(4，9)，(6，12)，(8，15)}p[2]q[2]={(0,0),(2,3),(2,6),(4,6),(4，9),(6,9),(6，12),(8，15),(9,10),(10,11)}p[1]={(0,0),(2,6),(4，9),(6，12)，(8，15)}m(1,c)=1510、给定背包问题的贪心算法GREEDY－KNAPSACK,对其进行时间性能分析i.procedureGREEDY－KNAPSACK(P,W,M,X,n)1.//P(1:n)和W(1:n)分别含有按P(i)/W(i)≥P(i＋1)/W(i＋1)排序的n2.件物品的效益值和重量。M是背包的容量大小，而X(1:n)是解3.向量//4.realP(1:n),W(1:n),X(1:n),M,cu;5.integerI,n6.X←0//将解向量初始化为0//ii.cu←M//cu是背包的剩余容量//1.fori←1tondoa)ifW(i)cuthenexitendifb)X(i)←12.cu←cu-W(i)3.repeat4.ifi≤nthenX(i)←cu/W(i)endifb)endGREEDY-KNAPSACK解：11、给定在n个不同的数中找最大的数的算法FindMax,证明FindMax算法是最优算法。基本运算：比较算法：FindMax输入：数组L，项数n输出：L中的最大项MAX1）MAX←L(1);i←2;2）whilei≤ndo3）ifMAXL(i)thenMAX←L(i);4）i←i+1;5）end。证明：行3的比较进行n-1次，故W(n)=n-1定理：在n个数的数组中找最大的数，并以比较作为基本运算的算法类中的任何算法最坏情况下至少要做n-1次比较因为MAX是唯一的，其他的n-1个数必须在比较后被淘汰。一次比较最多淘汰一个数，所以至少需要n-1次比较故FindMax算法是最优算法12、给定利用分治法求取最大和最小元素算法MAXMIN,仅考虑算法中的比较运算,对其进行时间性能分析a)procedureMAXMIN(i,j,fmax,fmin)i.//A(1:n)是含有n个元素的全局数组，参数i,j是整数，1≤i,j≤n，代表当前的查找区间//ii.//该过程把A(i:j)中的最大和最小元素分别赋给fmax和fmin//iii.integeri,j;globaln,A(1:n)iv.casev.:i=j:fmax←fmin←A