华师大数据结构期中考试试卷(含答案)

华东师范大学期中试卷2007—2008学年第二学期课程名称：______数据结构_____姓名：___________________学号：__________________专业：___________________年级/班级：__________________课程性质：专业必修一二三四五六七八总分阅卷人签名一、单项选择题(共18分，每题3分)1.Stackhasthepropertycalledlastinandfirstout,thenwhichofthefollowingdescribesthepropertyofQueue?a)Lastinandfirstoutb)Firstinandlastoutc)Firstinandfirstout2.Alistofitemsfromwhichonlytheitemmostrecentlyaddedcanberemovedisknownasa()a)stackb)queuec)circularlinkedlistd)list3.Ifthefollowingfunctioniscalledwithavalueof2forn,whatistheresultingoutput?voidQuiz(intn){if(n0){cout0;Quiz(n-1);cout1;Quiz(n-1);}}a)00011011b)11100100c)10011100d)01100011e)0011014.Aheapisalistinwhicheachentrycontainsakey,and,forallpositionsiinthelist,thekeyatpositioniisatleaseaslargeasthekeysinpositions2i+2and(),providedthesepositionsexistinthelist.a)2ib)2i-1c)2i-2d)2i+15.GiventherecursivefunctionintFunc(/*in*/inti,/*in*/intj){if(i11)if(j11)returni+j;elsereturnj+Func(i,j-2);elsereturni+Func(i-1,j);}whatisthevalueoftheexpressionFunc(12,15)?a)81b)62c)19d)72e)noneoftheabove6.Shellsortfinallyperformanordinary()?a)Heapsortb)Insertionsortc)Selectionsortd)Quicksort二、填空题（共22分，每空2分）1.Ifthefollowingfunctioniscalledwithavalueof75forn,theresultingoutputis_______【1】_________.voidFunc(/*in*/intn){if(n0){Func(n/8);coutn%8;}}2.Givetheoutputofthefollowingprogram.________【2】__________.templateclassList_entryvoidprint(List_entry&x){coutx;}voidmain(){Listintmylist;for(inti=0;i5;i++)mylist.insert(i,i);coutYourlisthavemylist.size()elements:endl;mylist.remove(0,i);mylist.remove(2,i);mylist.insert(i,i);mylist.traverse(print);mylist.clear();for(i=1;i3;i++)mylist.insert(i,i);mylist.traverse(print);}3.Readthefollowingprogramandfilltheblanktocompletethemethod.templateclassNode_entrystructNode{//datamembersNode_entryentry;NodeNode_entry*next;NodeNode_entry*back;//constructorsNode();Node(Node_entryitem,NodeNode_entry*link_back=NULL,NodeNode_entry*link_next=NULL);};templateclassList_entryvoidListList_entry::set_position(intposition)const/*Pre:positionisavalidpositionintheList:0=positioncount.Post:ThecurrentNodepointerreferencestheNodeatposition.*/{if(current_position=position)for(;current_position!=position;current_position++)【3】;elsefor(;current_position!=position;【4】)current=current-back;}4.Readthefollowingprogramandfilltheblanktocompletethemethod.Error_coderecursive_binary_2(constOrdered_list&the_list,constKey&target,intbottom,inttop,int&position)/*Pre:Theindicesbottomtotopdefinetherangeinthelisttosearchforthetarget.Post:IfaRecordintherangefrombottomtotopinthelisthaskeyequaltotarget,thenpositionlocatesonesuchentry,andacodeofsuccessisreturned.Otherwise,not_presentisreturned,andpositionisundefined.Uses:recursive_binary_2,togetherwithmethodsfromtheclassesOrdered_listandRecord.*/{Recorddata;if(bottom=top){intmid=【5】;the_list.retrieve(mid,data);if(data==target){【6】;returnsuccess;}elseif(datatarget)returnrecursive_binary_2(the_list,target,【7】,top,position);elsereturnrecursive_binary_2(the_list,target,bottom,【8】,position);}elsereturnnot_present;}5.Thefollowingprogramisthedivide_fromfunctionofMergeSort.Pleasefilltheblanktocompletethefunction.NodeRecord*divide_from(NodeRecord*sub_list)/*Post:Thelistofnodesreferencedbysub_listhasbeenreducedtoitsfirsthalf,andapointertothefirstnodeinthesecondhalfofthesublistisreturned.Ifthesublisthasanoddnumberofentries,thenitsfirsthalfwillbeoneentrylargerthanitssecond.*/{NodeRecord*position,//traversestheentirelist*midpoint,//movesathalfspeedofpositiontomidpoint*second_half;if((midpoint=sub_list)==NULL)returnNULL;//Listisempty.position=midpoint-next;while(【9】){//Movepositiontwiceformidpoint'sonemove.position=position-next;if(position!=NULL){【10】;position=position-next;}}second_half=【11】;midpoint-next=NULL;returnsecond_half;}三、编程题（共60分）1.（16分）Applyquicksorttothefollowinglistof14names,wherethepivotineachsublistischosentobe(a)thefirstkeyinthesublistand(b)thelastkeyinthesublist.Ineachcase,drawthetreeofrecursivecall.TimDotEvaRoyTomKimGuyAmyJonAnnJimKayRonJan2.（16分）Writethefollowingoverloadoperatorforstacks:1)boolStack::operator==(constStack&s);2)boolStack::operator+=(constStack&s);//pushesthecontentsofthegivenstackontothisstack;3.（10分）Writethefollowingfunctiontemple:TemplateclassTvoidreverse(QueueT&q);//reversesthecontentsofthegivenqueue;4.（18分）structNode{//datamembersintentry;Node*next;//constructorsNode();Node(intitem,Node*link=NULL);};fistheheadpointerofalinklistofnodes.Usingrecursion,implementthefollowingfunctions:1)intMax(Node*f);//returnthemaxvalueinthelinklist.2)intNum(Node*f);//returnthenumberofthenodesinthelinklist3)Node*Search(Node*f,intx);//Searchthefirstoccurrenceofthexinthelinklist.Ifsuccessreturnsthe//pointertothenode,elsereturnsNULL.数据结构期中考卷参考答案一、单项选择题(3×6＝18)1．c2．a3．e4．d5．a6．b二、填空题(2×11＝22)【1】113【2】Yourlisthave5elements:1243【3】current=current-next【4】current_position--【5】(bottom+top)/2【6】position=mid【7】mid+1【8】mid–1【9】position!=NULL【10】midpoint=midpoint-next;【11】midpoint-next三、编程题(16×2＋10＋18＝60)1，a)P3