DataStructuresandAlgorithm习
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
Prefaceii1DataStructuresandAlgorithms12MathematicalPreliminaries53AlgorithmAnalysis174Lists,Stacks,andQueues235BinaryTrees326GeneralTrees407InternalSorting468FileProcessingandExternalSorting549Searching5810Indexing6411Graphs6912ListsandArraysRevisited7613AdvancedTreeStructures82iiiContents14AnalysisTechniques8815LimitstoComputation94PrefaceContainedhereinarethesolutionstoallexercisesfromthetextbookAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition.FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.InafewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresentedinthismanualhasnotactuallybeencompiledandtested.WhileIbelievethealgorithmstobeessentiallycorrect,theremaybeerrorsinsyntaxaswellassemantics.Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintendedanswer,ratherthanusableprograms.1DataStructuresandAlgorithmsInstructor’snote:Unliketheotherchapters,manyofthequestionsinthischapterarenotreallysuitableforgradedwork.Thequestionsaremainlyintendedtogetstudentsthinkingaboutdatastructuresissues.1.1Thisquestiondoesnothaveaspecificrightanswer,providedthestudentkeepstothespiritofthequestion.Studentsmayhavetroublewiththeconceptof“operations.”1.2Thisexerciseasksthestudenttoexpandontheirconceptofanintegerrepresentation.AgoodanswerisdescribedbyProject4.5,whereasingly-linkedlistissuggested.Themoststraightforwardimplementationstoreseachdigitinitsownlistnode,withdigitsstoredinreverseorder.Additionandmultiplicationareimplementedbywhatamountstograde-schoolarithmetic.Foraddition,simplymarchdowninparallelthroughthetwolistsrepresentingtheoperands,ateachdigitappendingtoanewlisttheappropriatepartialsumandbringingforwardacarrybitasnecessary.Formultiplication,combinetheadditionfunctionwithanewfunctionthatmultipliesasingledigitbyaninteger.Exponentiationcanbedoneeitherbyrepeatedmultiplication(notreallypractical)orbythetraditionalΘ(logn)-timealgorithmbasedonthebinaryrepresentationoftheexponent.Discoveringthisfasteralgorithmwillbebeyondthereachofmoststudents,soshouldnotberequired.1.3AsampleADTforcharacterstringsmightlookasfollows(withthenormalinterpretationofthefunctionnamesassumed).Chap.1DataStructuresandAlgorithms//ConcatenatetwostringsStringstrcat(Strings1,Strings2);//Returnthelengthofastringintlength(Strings1);//Extractasubstring,startingat‘start’,//andoflength‘length’Stringextract(Strings1,intstart,intlength);//Getthefirstcharactercharfirst(Strings1);//Comparetwostrings:thenormalC++strcmpfunction.Some//conventionshouldbeindicatedforhowtointerpretthe//returnvalue.InC++,thisis1fors1
s2.intstrcmp(Strings1,Strings2)//Copyastringintstrcpy(Stringsource,Stringdestination)1.4TheanswertothisquestionisprovidedbytheADTforlistsgiveninChapter4.1.5One’scomplimentstoresthebinaryrepresentationofpositivenumbers,andstoresthebinaryrepresentationofanegativenumberwiththebitsinverted.Two’scomplimentisthesame,exceptthatanegativenumberhasitsbitsinvertedandthenoneisadded(forreasonsofefficiencyinhardwareimplementation).ThisrepresentationisthephysicalimplementationofanADTdefinedbythenormalarithmeticoperations,declarations,andothersupportgivenbytheprogramminglanguageforintegers.1.6AnADTfortwo-dimensionalarraysmightlookasfollows.Matrixadd(MatrixM1,MatrixM2);Matrixmultiply(MatrixM1,MatrixM2);Matrixtranspose(MatrixM1);voidsetvalue(MatrixM1,introw,intcol,intval);intgetvalue(MatrixM1,introw,intcol);Listgetrow(MatrixM1,introw);OneimplementationforthesparsematrixisdescribedinSection12.3Anotherimplementationisahashtablewhosesearchkeyisaconcatenationofthematrixcoordinates.1.7Everyproblemcertainlydoesnothaveanalgorithm.AsdiscussedinChapter15,thereareanumberofreasonswhythismightbethecase.Someproblemsdon’thaveasufficientlycleardefinition.Someproblems,suchasthehaltingproblem,arenon-computable.Forsomeproblems,suchasonetypicallystudiedbyartificialintelligenceresearchers,wesimplydon’tknowasolution.1.8Wemustassumethatby“algorithm”wemeansomethingcomposedofstepsareofanaturethattheycanbeperformedbyacomputer.Ifso,thananyalgorithmcanbeexpressedinC++.Inparticular,ifanalgorithmcanbeexpressedinanyothercomputerprogramminglanguage,thenitcanbeexpressedinC++,sinceall(sufficientlygeneral)computerprogramminglanguagescomputethesamesetoffunctions.1.9Theprimitiveoperationsare(1)addingnewwordstothedictionaryand(2)searchingthedictionaryforagivenword.Typically,dictionaryaccessinvolvessomesortofpre-processingofthewordtoarriveatthe“root”oftheword.Atwentypagedocument(singlespaced)islikelytocontainabout20,000words.Ausermaybewillingtowaitafewsecondsbetweenindividual“hits”ofmis-spelledwords,orperhapsuptoaminuteforthewholedocumenttobeprocessed.Thismeansthatacheckforanindividualwordcantakeabout10-20ms.Userswilltypicallyinsertindividualwordsintothedictionaryinteractively,sothisprocesscantakeacoupleofseconds.Thus,searchmustbemuchmoreefficientthaninsertion.1.10Theusershouldbeabletofindacitybasedonavarietyofattributes(name,location,perhapscharacteristicssuchaspopulationsize).Theusershouldalsobeabletoinsertanddeletecities.Thesearethefundamentaloperationsofanydatabasesystem:search,insertionanddeletion.Areasonabledatabasehasatimeconstraintthatwillsatisfythepatienceofatypicaluser.Foraninsert,delete,orexactmatchquery,afewsecondsissatisfactory.Ifthedatabaseismeanttosupportrangequeriesandmassdeletions,theentireoperationmaybeallowedtotakelonger,perhapsontheorderofaminute.However,thetimespenttoprocessindividualcitieswithintherangemustbeappropriatelyreduced.Inpractice,thedatarepresentationwillneedtobesuchthatitaccommodatesefficientprocessingtomeetthesetimeconstraints.Inparticular,itmaybenecessarytosupportoperationsthatprocessrangequeriesefficientlybyprocessingallcitiesintherangeasabatch,ratherthanasaseriesofoperationsonindividualcities.1.11Studentsatthislevelarelikelyalreadyfamiliarwithbinarysearch.Thus,theyshouldtypicallyrespondwithsequentialsearchandbinarysearch.Binarysearchshouldbedescribedasbettersinceittypicallyneedstomakefewercomparisons(andthusislikelytobemuchfaster).1.12TheanswertothisquestionisdiscussedinChapter8.Typicalmeasuresofcostwillbenumberofcomparisonsandnumberofswaps.Testsshouldincluderunningtimingsonsorted,reversesorted,andrandomlistsofvarioussizes.Chap.1DataStructuresandAlgorithms1.13Thefirstpartiseasywiththehint,butthesecondpartisratherdifficulttodowithoutastack.a)boolcheckstring(stringS){intcount=0;for(inti=0;i0.Itissymmetricsincexy˙=yx˙.Itistransitivesinceanytwomembersofthegivenclasssatisfytherelationship.5Chap.2MathematicalPreliminaries(d)Thisisnotanequivalancerelationsinceitisnotsymmetric.Forexample,a=1andb=2.(e)Thisisaneqivalancerelationthatdividestherationalsbasedontheirfractionalvalues.Itisreflexivesinceforalla,a.a=0.Itissymmetricsinceifa.b=xthenb.a=.x.Itistransitivesinceanytworationalswiththesamefractionalvaluewillyeildaninteger.(f)Thisisnotanequivalancerelationsinceitisnottransitive.Forexample,4.2=2and2.0=2,but4.0=4.2.3Arelationisapartialorderingifitisantisymmetricandtransitive.(a)Notapartialorderingbecauseitisnottransitive.(b)Isapartialorderingbacauseitisantisymmetric(ifaisanancestorofb,thenbcannotbeanancestorofa)andtransitive(sincetheancestorofanancestorisanancestor).(c)Isapartialorderingbacauseitisantisymmetric(ifaisolderthanb,thenbcannotbeolderthana)andtransitive(sinceifaisolderthanbandbisolderthanc,aisolderthanc).(d)Notapartialordering,sinceitisnotantisymmetricforanypairofsisters.(e)Notapartialorderingbecauseitisnotantisymmetric.(f)Thisisapartialordering.Itisantisymmetric(noviolationsexist)andtransitive(noviolationsexist).2.4Atotalorderingcanbeviewedasapermuationoftheelements.Sincetherearen!permuationsofnelements,theremustben!totalorderings.2.5ThisproposedADTisinspiredbythelistADTofChapter4.voidclear();voidinsert(int);voidremove(int);voidsizeof();boolisEmpty();boolisInSet(int);2.6ThisproposedADTisinspiredbythelistADTofChapter4.NotethatwhileitissimiliartotheoperationsproposedforQuestion2.5,thebehaviourissomewhatdifferent.voidclear();voidinsert(int);voidremove(int);voidsizeof();7boolisEmpty();//ReturnthenumberofelementswithagivenvalueintcountInBag(int);2.7ThelistclassADTfromChapter4isasequence.2.8longifact(intn){//maken<=12son!forlongintlongfact=1;Assert((n>=0)&&(n<=12),"Inputoutofrange");for(inti=1;i<=n;i++)fact=fact*i;returnfact;}2.9voidrpermute(int*array,intn){swap(array,n-1,Random(n));rpermute(array,n-1);}2.10(a)Mostpeoplewillfindtherecursiveformnaturalandeasytounderstand.Theiterativeversionrequirescarefulexaminationtounderstandwhatitdoes,ortohaveconfidencethatitworksasclaimed.(b)FibrissomuchslowerthanFibibecauseFibrre-computesthebulkoftheseriestwicetogetthetwovaluestoadd.Whatismuchworse,therecursivecallstocomputethesubexpressionsalsore-computethebulkoftheseries,anddosorecursively.Theresultisanexponentialexplosion.Incontrast,Fibicomputeseachvalueintheseriesexactlyonce,andsoitsrunningtimeisproportionalton.2.11//Arraycurr[i]indicatescurrentpositionofringi.voidGenTOH(intn,POLEgoal,POLEt1,POLEt2,POLE*curr){if(curr[n]==goal)//Gettopn-1ringssetupGenTOH(n-1,goal,t1,t2,curr);else{if(curr[n]==t1)swap(t1,t2);//Getnamesright//Now,ringnisonpolet2.Putothersont1.GenTOH(n-1,t1,goal,t2,curr);move(t2,goal);GenTOH(n-1,goal,t1,t2,curr);//Moven-1back}}2.12Ateachstepoftheway,thereductiontowardthebasecaseisonlyhalfasfarastheprevioustime.Intheory,thisseriesapproaches,butneverreaches,0,soitwillgoonforever.Inpractice,thevalueshouldbecomecomputationallyindistinguishablefromzero,andterminate.However,thisisterribleprogrammingpractice.Chap.2MathematicalPreliminaries2.13voidallpermute(intarray[],intn,intcurrpos){if(currpos==(n-1)}{printout(array);return;}for(inti=currpos;i
本文档为【数据结构与算法分析 C++版答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483