计算机考研数据结构统考历年真题2009-2015

2009-2015201620091.A.B.C.D.2.SQabcdefgSQ7bdcfeagSA1B.2C.3D.43.NLR3175624ALRNB.NRLC.RLND.RNL4.5.618A39B.52C.111D.1196.uvuvIII.III.uvA.IIB.IIIC.IIIID.IIIIII7.III.1III.1A.IB.IIC.IIID.IIII8.mBAmB.CD.9.581219282015223A351282820152219B.351219201522828C381252015222819D.31258282015221910.1112137892345AB.C.D.41.10uuvu=vu42.15listkkdata10123CC++JAVA20101a,b,c,d,e,fAdcebfaBcbdaefCdbcaefDafedcb2AbacdeBdbaceCdbcaeDecbad3datalink44837A1348B2448C2453D249054T20410312101TA41B82C113D1226n(n2)AB1CD7G-V.E7GA6B15C16D218abcdeA4B3C2D1916LA4B5C6D710ABCD112121688510212165108821251016882510121688ABCD41.107811189140Hkey=key3MODT0.71242.13n(n,1)RRP0PnRX0X1Xn-1XpXp+1Xn-1X0X1Xp-112CC++JAVA320111.nx=2;while(xn/2)x=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2.a,b,c,d,edA.3B.4C.5D.63.A[0..n-1]frontrear1A[0]frontrearA.0,0B.0,n-1C.n-1,0D.n-1,n-14.768A.257B.258C.384D.3855.1,2,3,44,3,2,1A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,16.2011116A.115B.116C.1895D.18967.A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,348.I.II.III.A.IIB.IIIC.IIID.IIII9.(Hash)I.()II.()III.()()A.IB.IIC.IIID.IIIII10.A.B.C.D.11.25,13,10,12,918A.1B.2C.4D.541.(8)6(0~5)GA()(1)GA(2)G(3)G42.(15)L(L1)SL/2SS1=(11,13,15,17,19)S115S2=(2,4,6,8,20)S1S211ABAB:(1)(2)CC++JAVA(3)20121n(n0)()intfact(intn){if(n=1)return1;returnn*fact(n-1);}A.O(log2n)B.O(n)C.(nlog2n)D.O(n2)2+-*/()a+b-a*((c+d)/e-f)+gab+acd+e/f-**-g+()A.5B.7C.8D.113a,e,b,d,cb,c,d,e,a()A.eB.ebC.ecD.461()A.10B.20C.32D.335ne()A.O(n)B.O(e)C.O(n+e)D.O(n*e)6()A.B.C.D.7Dijkstraabc()A.d,e,fB.e,d,fC.f,d,eD.f,e,d8()PrimKruskalA.B.C.D.93B-78B-()A.60B.60,62C.62,65D.6510().....A.B.C.D.11()A.B.C.D.41106ABCDEF103540506020056112N(N2)4213loagingbeingstr1str2data,nextstr1str2ip12CC++java320131.mnm+nA.O(n)B.O(m*n)C.O(min(m,n))D.O(max(m,n))2.1,2,3,,np1,p2,p3,pnp2=3p3:A.n-3B.n-2C.n-1D.3.1234567TT0A.0B.1C.2D.34.T6234567TA.27B.46C.54D.565.XXYXA.XB.YC.XYD.Y6.T1vT2vT2T3T1T3I.vT1T1T3II.vT1T1T3III.vT1T1T3IV.vT1T1T3A.IIIIB.IIVC.IIIIID.IIIV7.AA.1212B.2211C.3423D.44228.A.hcabdegfB.eafgbhcdC.dbcahefgD.abcdhefg9AOE8AceBdeCfdDfh1025BA5B7C8D14A=(05535755)5A=(05535157)AAnA-112CC++Java342.104S={doforrepeatwhile}p1=0.35p2=0.15p3=0.15p4=0.35S42.21S2S20141.count=0;for(k=1;k=n;k*=2)for(j=1;j=n;j+1)count++;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2.abcdefgfAB.C.D.3.A[0M-1]end1end2M-1A.end1==end2end1==(end2+1)modMB.end1==end2;end2==(end1+1)mod(M-1)C.end2==(end1+1)modM;end1==end2+1modMD.end1==end2+1modM;end2==(end1+1)mod(M-1)4.xA.e,cB.e,aC.d,cD.b,a5.FTFA.TB.T1C.TD.T6.54A.01,0000,0001,001,1B.011,000,001,010,1C.000,001,010,011,100D.000,001,010,011,1007.A.3,1,2,4,5,6B.3,1,2,4,6,5C.3,1,4,2,5,6D.3,1,4,2,6,58.A.B.C.D.9.154BA.5B.6C.10D.1510.19,1,4,13,7,8,20,23,15A.2B.3C.4D.511.2A.2,3,5,4,6,7,9B.2,7,5,6,4,3,9C.3,2,5,4,7,6,9D.4,2,3,5,7,6,941.13WPLTbdxeac125463weightrootTTWPL12CC++3CC++20151ints(intn){return(n=0)?0:s(n-1)+n;}voidmain(){couts(1);}Amain()-S(1)-S(0)BS(0)-S(1)-main()Cmain()-S(0)-S(1)DS(1)-S(0)-main()2a,b,c,dA13B14C15D163A2410524107B2410524127C241010241411D24105241464AVL,A2BCD5G=(V,E)V={V0,V1,V2,V3}E={v0,v1,v0,v2,v0,v3v1,v3},V0A2B3C4D56kruskalPrimV42A(V1,V3)B(V1,V4)C(V2,V3)D(V3,V4)leftweightright7A500200450180B500450200180C180500200450D1802005004508SabaabaabacacaabaabcctabaabcKMPs[i]!=t[i])i=j=5,ijAi=1j=0Bi=5j=0Ci=5j=2Di=6j=29ABCD1081510213416128A1B2C3D411ABCD41.m(data,link)|data|n(n)headhead(1)(2)cc++(3)cc++(4)42.5G(1)GA(0)(2)A2A203(3)n(n=2)BBm(2=m=n)