1、200X年試題選擇題Suppose1,2,3,4istheorderwhichtheseelementspushontoastack.Thesequenceobtainedis(B)A.4.1.2.3B.3.2.4.1C.3.4.1.2D.4.3.1.2Supposethatalinearlistcontainsn=31nodes,thebinarysearchisappliedtothelist,themaximumtimesinsearchingis(B)A4B5C25-1D24-1Inthefollowingsortingalgorithms,whichisunstable(A)ASel

2、ectionsortBMergesortCBubblesortDInsertionsortBubblesortisusedfornnodes,theminimumnumberofcomparisonsis(A)An-1BnCn(n-1/2)Dn(n+1)/2Howmanybinarytreesindifferentformscanatmostbebuiltbythreenodes?(B)A4B5C6D7填空題.(1)Thestacktakesoncharacterof后進(jìn)先出Thepostfixexpressionisabcdef*/-*+.Itsinfixexpressionis_a+bc-

3、d/(e*f)Theadvantageofcircularqueuesis克服隊滿溢出.(4)Ifthedepthoffullbinarytreeisk,thenthenumberofnodesinthetreeatleast_2Ak+1-1(5)Theselectionsortisusedtosortnnodes,thenumberofitscomparisonsis_n(n-1)/2三(1)WriteafunctionDeletioninCforlinearlist.(5points)intsq_elete(list,p_n,i)intIist;/*形參數(shù)組可不指定大小*/int*p_n,

4、i;intj;if(i=*p_n)return(1);for(j=i+1,j*p_n;j+)listj-1=listj;(*p_n)-;return(0);WriteafunctionPopinCforlinkedstack.(5points)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=am)return(m);if(ventrylow;pivotpos=low;for(i=low+1;ientryi.key,pivo

5、t.key)Swap(+pivotpos,i,list);Swap(low,pivotpos,list);returnpivotpos;Supposethatahashtablecontains5entriesindexedfrom0through4andthatthefollowingkeysaretobemappedintothetable.12,19,17,14,10,24,15Hashfunctionh(k)=kmod5.(a)Determinethehashaddressesandresolutecollisionbychaining.(b)WriteafunctioninCfors

6、earchbychaining.(10point)voidsearch2(t,k,p,q)NODE*t;intk;NODE*p,*q;*p=NULL;*q=th(k);while(*q!=NULL)if(*q)-key=k)return;else*p=*q;*q=(*q)-link;五.WriteafunctioninCwhichwillinterchangeallleftandrightsubtreesinbinarytree.(10point)WriteafunctioninCforlinkedqueue.(10point)voidAppend(QueueEntryx,Queue*q)if

7、(QueueFull(q)Error(“cannotappendanentrytoafullqueue.”);elseq-count+;q-rear=(q-rear+1)%MAXQUEUE;q-entryq-rear=x;選擇題Inasimplelinkedlistwithnnodes,thenumberofpointerfieldswithNULLTotals(D).A.nB.2C.n/2D.1Inthelinearlists,twoconceptswhicharethesameaseachotheris(AB)AnodeB.recordC.fieldD.typeofstructureInt

8、hebinarysearchtree,foranyrootofsubtree,thekeysofallnodesinitsleftsubtreeis(D)thekeysofallnodesinitsrightsubtree.AlessthanBequaltoCgreatthanDlessthanorequaltoForgeneraltrees,thecorrectchoiceis(B)AitmaybeemptyBatleastonenodeCatleasttwonodesDA.BandCareincorrectThebubblesortisusedtonnodes,leastnumberofc

9、omparisonis(A)An-1BnCn(n-1)/2Dn(n+1)/2填空題Abinarytreewithnnodesstoragedbystandardform,thereare_2n_pointerswhere_n-1_pointersareusedtopointtosub-nodes,and_n+1_pointersareempty.Thepostfixexpressionisabc*+de/f*-,thenitsinfixexpressionis_a+b*c-d/e*f_Thebasicoperationsoflinearlistsare_插入刪除訪問Thecharacterof

10、stackis_后進(jìn)先出Hashstoragefacedwithtwoproblemsof_Hash函數(shù)and沖突_WriteafunctionPopforstack(5point)VoidPop(StackEntry*item,Stack*s)if(StackEmpty(s)Error;else*item=S-entry-s-top;Translatethequadraticformula.(a+b*c)fdf(e*f/g)-h*iintopostfixform.(10point)WriteafunctioninCwhichchangesthelinkedlistinFigure1toano

11、therlinkedlistinFigure2.(10point)(附圖)(4).(a)Byhand,tracethroughthestepsbubblesortwilluseonthelist.Thefollowingsevennumbertobesortedintoincreasingorder.(b)Writeafunctionofbubblesort.(10point)voidbubble_sort(a,n)inta,n;inti,j,t;n;while(n0)j=0;for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;j=i;n=j;Byhand,sortthelis

12、t46.26.22.68.48.42.36.84.66usingselectionsort.Writeafunctionofselectionsort.(10point)voidinsertion_sort(a,n)inta;intn;inti,j;intt;for(i=1;i=0&tentry)B(root-left,Visit);B(root-right,Visit);voidB(TreeNode*root,void(*Visit)(TreeEbtryx)If(root)A(root-left,Visit);Visit(root-entry);A(root-right,Visit);五.(2)Insertanewnodertakenastherightchildofnodesanddrawathreaded-tree.(a)Byhand(b)Bysomese