数据结构英文试题(修改)

200X年试题选择题(1)Suppose1,2,3,4istheorderwhichtheseelementspushontoastack.Thesequenceobtainedis(B)A.4.1.2.3B.3.2.4.1(2)Supposethatalinearlistcontainsn=31nodes,thebinarysearchisappliedtothelist,themaximumtimesinsearchingis(B)A4B5C25-1D24(3)Inthefollowingsortingalgorithms,whichisunstable(A)ASelectionsortBMergesortCBubblesortDInsertionsort(4)Bubblesortisusedfornnodes,theminimumnumberofcomparisonsis(A)An-1BnCn(n-1/2)Dn(n+1)/2(5)Howmanybinarytreesindifferentformscanatmostbebuiltbythreenodes?(B)A4B5C填空题.(1)Thestacktakesoncharacterof___________后进先出____________________(2)Thepostfixexpressionis‘abcdef*/-*+’.Itsinfixexpressionis_a+b[c-d/(e*f)]____(3)Theadvantageofcircularqueuesis_______克服队满溢出_________.(4)Ifthedepthoffullbinarytreeisk,thenthenumberofnodesinthetreeatleast_2^k+1-1__(5)Theselectionsortisusedtosortnnodes,thenumberofitscomparisonsis__n(n-1)/2____三．(1)WriteafunctionDeletioninCforlinearlist.(5points)intsq_elete(list,p_n,i) intlist[];/*形参数组可不指定大小*/ int*p_n,i; { intj; if(i<0||i>=*p_n)return(1); for(j=i+1,j<*p_n;j++)list[j-1]=list[j]; (*p_n)--; return(0);}(2)WriteafunctionPopinCforlinkedstack.(5points)(3)WriteafunctioninCforbinarysearch.(10point)intbisect(a,n,v)inta[],v,n;{inti,j,m;i=0;j=n-1;while(i<=j){m=(i+j)/2; if(v==a[m])return(m); if(v<a[m])j=m-1; elsei=m+1; }return(-1);}(4)WritesomesentencesinCwhichdeletethenodebinthefollowingfigure.(5point)(附图)AABCP(5)WritesomesentencesinCwhichinsertthenodebinthefollowingfigure(5pont)(附图)AACPBB四．(2)WriteafunctioninCofquicksort.(10point)PositionPartition(List*list,Posotionlow,Positionhigh){ListEntrypivot;Positioni,lastsmall,pivotpos;Swap(low,(low+high)/2,list);pivot=list->entry[low];pivotpos=low;for(i=low+1;i<=high;i++) if(LT(list->entry[i].key,pivot.key)) Swap(++pivotpos,i,list);Swap(low,pivotpos,list);returnpivotpos;}(3)Supposethatahashtablecontains5entriesindexedfrom0through4andthatthefollowingkeysaretobemappedintothetable.12,19,17,14,10,24,15Hashfunctionh(k)=kmod5.(a)Determinethehashaddressesandresolutecollisionbychaining.(b)WriteafunctioninCforsearchbychaining.(10point)voidsearch2(t,k,p,q)NODE*t[];intk;NODE*p,*q;{*p=NULL;*q=t[h(k)];while(*q!=NULL)if((*q)->key==k)return;else{*p=*q;*q=(*q)->link;}}五.(1)WriteafunctioninCwhichwillinterchangeallleftandrightsubtreesinbinarytree.(10point)(2)WriteafunctioninCforlinkedqueue.(10point)voidAppend(QueueEntryx,Queue*q){ if(QueueFull(q))Error(“cannotappendanentrytoafullqueue.”);else{ q->count++; q->rear=(q->rear+1)%MAXQUEUE; q->entry[q->rear]=x;}}选择题Inasimplelinkedlistwithnnodes,thenumberofpointerfieldswithNULLTotals(D).A.nB.2C(2)Inthelinearlists,twoconceptswhicharethesameaseachotheris(AB)AnodeB.recordC.fieldD.typeofstructure(3)Inthebinarysearchtree,foranyrootofsubtree,thekeysofallnodesinitsleftsubtreeis(D)thekeysofallnodesinitsrightsubtree.AlessthanBequaltoCgreatthanDlessthanorequalto(4)Forgeneraltrees,thecorrectchoiceis(B)AitmaybeemptyBatleastonenodeCatleasttwonodesDA.BandCareincorrect(5)Thebubblesortisusedtonnodes,leastnumberofcomparisonis(A)An-1BnCn(n-1)/2Dn(n+1)/2填空题(1)Abinarytreewithnnodesstoragedbystandardform,thereare___2n__pointerswhere_n-1___pointersareusedtopointtosub-nodes,and_n+1___pointersareempty.(2)Thepostfixexpressionisabc*+de/f*-,thenitsinfixexpressionis_a+b*c-d/e*f___(3)Thebasicoperationsoflinearlistsare___插入删除访问______(4)Thecharacterofstackis__后进先出__________(5)Hashstoragefacedwithtwoproblemsof__Hash函数____and____冲突___三．(1)WriteafunctionPopforstack(5point)VoidPop(StackEntry*item,Stack*s){if(StackEmpty(s))Error;else*item=S->entry[--s->top];}Translatethequadraticformula.(a+b*c)↑d↑(e*f/g)-h*iintopostfixform.(10point)WriteafunctioninCwhichchangesthelinkedlistinFigure1toanotherlinkedlistinFigure2.(10point)(附图)(4)(1).(a)Byhand,tracethroughthestepsbubblesortwilluseonthelist.Thefollowingsevennumbertobesortedintoincreasingorder.(b)Writeafunctionofbubblesort.(10point)voidbubble_sort(a,n)inta[],n;{inti,j,t;n--;while(n>0){j=0; for(i=0;i<n;i++)if(a[i]>a[i+1]) {t=a[i]; a[i]=a[i+1]; a[i+1]=t; j=i;}n=j; }}(2)Byhand,sortthelist46.26.22.68.48.42.36.84.66usingselectionsort.Writeafunctionofselectionsort.(10point)voidinsertion_sort(a,n)inta[];intn;{inti,j;intt;for(i=1;i<n;i++){t=a[i];for(j=i-1;j>=0&&t<a[j];j--)a[j+1]=a[j];a[j+1]=t;}}(3).Supposethatahashtablecontains11entriesfrom0through10andthatthefollowingkeysaretobemappedintothetable.(32,75,63,48,94,25,36,18,70)Hashfunctionh(k)=kmod11(a)Determinethehashaddressesandresolutecollisionbylinearprobing.(b)Determinethehashaddressesandresolutecollisionbychaining.(10point)Foreachofthefollowingbinarytrees,determinetheorderinwhichthenodeswillbevisitedmixedordergivenbyinvokingf