軟件學院數(shù)據(jù)結(jié)構(gòu)與算法分析期末試題(2006級B)

四川大學期末考試試題（2007-2008學年第1學期）課程號：課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法分析（B卷） 任課教師： 適用專業(yè)年級：06級軟件工程學號： 姓名： 考試須知四川大學學生參加由學校組織或由學校承辦的各級各類考試，必須嚴格執(zhí)行《四川大學考試工作管理辦法》和《四川大學考場規(guī)則》。有考試違紀作弊行為的，一律按照《四川大學學生考試違紀作弊處罰條例》進行處理。四川大學各級各類考試的監(jiān)考人員，必須嚴格執(zhí)行《四川大學考試工作管理辦法》、《四川大學考場規(guī)則》和《四川大學監(jiān)考人員職責》。有違反學校有關規(guī)定的，嚴格按照《四川大學教學事故認定及處理辦法》進行處理。題號1234567卷面成績得分20101015151515閱卷教師閱卷時間1.Single-Choicequestions（eachquestion2scores,total20scores）（1）Theprimarypurposeofmostcomputerprogramsisa)toperformamathematicalcalculation.b)tostoreandretrieveinformation.c)tosortacollectionofrecords.d)alloftheabove.（2）AssumethatPcontainsnelements.ThenumberofsetsinthepowersetofPisa)n b)n^2c)2^n d)2^n-1e)2^n+1（3）Pickthegrowthratethatcorrespondstothemostefficientalgorithmasngetslarge:a)5n b)20lognc)2n^2 d)2^n（4）Asequencehasthefollowingproperties:a)Mayhaveduplicates,elementhaveaposition.b)Mayhaveduplicates,elementsdonothaveaposition.c)Maynothaveduplicates,elementshaveaposition.d)Maynothaveduplicates,elementsdonothaveaposition.（5）ThecorrecttraversaltouseonaBSTtovisitthenodesinsortedorderis:a)Preordertraversal. b)Inordertraversal.c)Postordertraversal.（6）Whensortingnrecords,Insertionsorthasbest-casecost:a)O(logn). b)O(n).c)O(nlogn). d)O(n^2)e)O(n!) f)Noneoftheabove.（7）Foralistoflengthn,thelinked-listimplementation'sprevfunctionrequiresworst-casetime:a)O(1).b)O(logn).c)O(n).d)O(n^2).（8）Theeasiestwaytorepresentageneraltreeisto:a)converttoalist. b)converttoabinarytree.c)converttoagraph.（9）Depth-firstsearchisbestimplementedusing:a)Astackorrecursion. b)Aqueue.c)Atree.（10）ForsetP,thenotation|P|indicatesa)ThenumberofelementsinP. b)TheinverseofP.c)ThepowersetofP. d)Noneoftheabove.2．（10scores）WriteaseriesofC++statementsthatusestheListADTasfollowstocreatealistcapableofholdingtwentyelementsandwhichactuallystoresthelistwithfollowingconfiguration:<6,28|18,8,19>solution:listL1(20);L1.append(6);L1.append(28);L1.append(18);L1.append(8);L1.append(9);L1.next();L1.next();//Listabstractclasstemplate<classElem>classList{public://Reinitializethelist.Theclientisresponsiblefor//reclaimingthestorageusedbythelistelements.virtualvoidclear()=0;//Insertanelementatthefrontoftherightpartition.//Returntrueifsuccessful,falseifthelistisfull.virtualboolinsert(constElem&)=0;//Appendanelementattheendoftherightpartition.//Returntrueifsuccessful,falseifthelistisfull.virtualboolappend(constElem&)=0;//Removethefirstelementofrightpartition.Return//trueifsuccessful,falseifrightpartitionisempty.//Theelementremovedisreturnedintheparameter.virtualboolremove(Elem&)=0;//Placefenceatliststart,makingleftpartitionemptyvirtualvoidsetStart()=0;//Placefenceatlistend,makingrightpartitionemptyvirtualvoidsetEnd()=0;//Movefenceonestepleft;nochangeifalreadyatstartvirtualvoidprev()=0;//Movefenceonestepright;nochangeifalreadyatendvirtualvoidnext()=0;//ReturnlengthofleftpartitionvirtualintleftLength()const=0;//ReturnlengthofrightpartitionvirtualintrightLength()const=0;//Ifposormoreelementsareinthelist,setthesize//ofleftpartitiontoposandreturntrue.Otherwise,//donothingandreturnfalse.virtualboolsetPos(intpos)=0;//Returninfirstparameterthefirstelementofthe//rightpartition.Returntrueifsuccessful,false//iftherightpartitionisempty.virtualboolgetValue(Elem&)const=0;//Printthecontentsofthelistvirtualvoidprint()const=0;};3．（10scores）BuildtheHuffmancodingtreeanddeterminethecodesforthefollowingsetoflettersandweights:a b c d e.1 3 5 7 11solution:Huffmancodingtreeasfollows:Herearethefinalcodes.a11111b1110c110d10e04．（15scores）Whataretheminimumandmaximumnumberofelememtsinaheapofheighth?solution:Theminimumnumberofelementsiscontainedintheheapwithasinglenodeatdepthh-1,foratotalof2h-1nodes.Themaximumnumberofelementsiscontainedintheheapthathascompletelyfilleduplevelh-1,foratotalof2h-1nodes.5．（15scores）TheBubbleSortimplentationhasthefollowinginnerforloop:for(intj=n–1;j>i;j--)Considertheeffectofreplacingthiswiththefollowingstaement:for(intj=n–1;j>0;j--)Wouldthenewimplementationworkcorrectly?Wouldthechangeaffecttheasymptoticcomplexityofthealgorithm?Howwouldthechangeaffecttherunningtimeofthealgorithm?solution:Therevisedalgorithmwillworkcorrectly,anditsasymptoticcomplexitywillremainΘ(n2).However,itwilldoabouttwiceasmanycomparisons,sinceitwillcompareadjacentelementswithintheportionofthelistalreadyknowntobesorted.Theseadditionalcomparisonsareunproductive.6．（15scores）//Binarytreenodeabstractclasstemplate<classElem>classBinNode{public://Returnthenode'selementvirtualElem&val()=0;//Setthenode'selementvirtualvoidsetVal(constElem&)=0;//Returnthenode'sleftchildvirtualBinNode*left()const=0;//Setthenode'sleftchildvirtualvoidsetLeft(BinNode*)=0;//Returnthenode'srightchildvirtualBinNode*right()const=0;//Setthenode'srightchildvirtualvoidsetRight(BinN