数据结构样卷2答案(英文)

重庆大学数据结构课程样卷2参考答案一．123456789101112131415CBBADBDACCDDABB二．1.q-next-prior=s2.prior,next,d3.thetopofstack4.t-ltag=15.Dynamiclook-uptable6.abdgcefh7.3times8.n-1次times9.O（n）10.pop(s),push(s,5)11.基数排序12.2n+1三．1.Assumethatnisthetotalnumber，n0isthenumberofleafnodes：n=n0+n1+n2+..+nm①becausen-1=ThetotalnumberofdegreesThereforen-1=1*n1+2*n2+...+m*nm②①-②:1=n0-n2-2*n3-…-(m-1)nm.n0=1+n2+2n3+…+(m-1)nm=1+nini2)1(i2．2，8，12，32，47，19，303．略4．{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}四．1．Low=high,(low+high)/2,high=m-1;low=m-1;L.r[high+1]2.p(5):135p(6):2463．Thefunctionofwhatis：calculatethenumberofnodeswhichvalueequalto0inbinarytreeT