数据结构与算法分析C++版答案

《数据结构与算法分析C++版答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、....DataStructuresandAlgorithm习题答案Prefaceii1DataStructuresandAlgorithms12MathematicalPreliminaries53AlgorithmAnalysis174Lists,Stacks,andQueues235BinaryTrees326GeneralTrees407InternalSorting468FileProcessingandExternalSorting549Searching5810Indexing6411Graphs6

2、912ListsandArraysRevisited7613AdvancedTreeStructures82i专业资料精心整理....iiContents14AnalysisTechniques8815LimitstoComputation94专业资料精心整理....PrefaceContainedhereinarethesolutionstoallexercisesfromthetextbookAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis,

3、2ndedition.FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.InafewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresentedinthismanualhasnotactuallybeencompiledandtested.WhileIbelievethealgorithmstobeessentiallycorrect,theremaybeerrorsinsyn

4、taxaswellassemantics.Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintendedanswer,ratherthanusableprograms.专业资料精心整理....1DataStructuresandAlgorithmsInstructor’snote:Unliketheotherchapters,manyofthequestionsinthischapterarenotreallysuitablefo

5、rgradedwork.Thequestionsaremainlyintendedtogetstudentsthinkingaboutdatastructuresissues.1.1Thisquestiondoesnothaveaspecificrightanswer,providedthestudentkeepstothespiritofthequestion.Studentsmayhavetroublewiththeconceptof“operations.”1.2Thisexerciseasksthestu

6、denttoexpandontheirconceptofanintegerrepresentation.AgoodanswerisdescribedbyProject4.5,whereasingly-linkedlistissuggested.Themoststraightforwardimplementationstoreseachdigitinitsownlistnode,withdigitsstoredinreverseorder.Additionandmultiplicationareimplemente

7、dbywhatamountstograde-schoolarithmetic.Foraddition,simplymarchdowninparallelthroughthetwolistsrepresentingtheoperands,ateachdigitappendingtoanewlisttheappropriatepartialsumandbringingforwardacarrybitasnecessary.Formultiplication,combinetheadditionfunctionwith

8、anewfunctionthatmultipliesasingledigitbyaninteger.Exponentiationcanbedoneeitherbyrepeatedmultiplication(notreallypractical)orbythetraditionalΘ(logn)-timealgorithmbasedonthebinaryrepresent