数据结构与算法分析习题解答(C++第二版)

SolutionsManualfor

APracticalIntroductiontoDataStructuresandAlgorithm

Analysis

SecondEdition

CliffordA.Shaffer

DepartmentofComputerScience

VirginiaTech

Blacksburg,VA24061

November30,2000

c2000byCliffordA.Shaffer.Copyright

Contents

Preface

1

2

3

4

5

6

7

8

9DataStructuresandAlgorithmsMathematicalPreliminariesAlgorithmAnalysisLists,Stacks,andQueuesBinaryTreesGeneralTreesInternalSortingFileProcessingandExternalSortingSearchingii1517233240465458

64

69

76

82

i10Indexing11Graphs12ListsandArraysRevisited13AdvancedTreeStructures

ii

14AnalysisTechniques

15LimitstoComputationContents8894

Preface

ContainedhereinarethesolutionstoallexercisesfromthetextbookAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition.

FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.InafewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresentedinthismanualhasnotactuallybeencompiledandtested.WhileIbelievethealgo-rithmstobeessentiallycorrect,theremaybeerrorsinsyntaxaswellassemantics.Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintendedanswer,ratherthanusableprograms.

iii

1

DataStructuresandAlgorithmsInstructor’snote:Unliketheotherchapters,manyofthequestionsinthischapterarenotreallysuitableforgradedwork.Thequestionsaremainlyintendedtogetstudentsthinkingaboutdatastructuresissues.

1.1Thisquestiondoesnothaveaspeci crightanswer,providedthestudentkeepstothespiritofthequestion.Studentsmayhavetroublewiththecon-ceptof“operations.”

1.2Thisexerciseasksthestudenttoexpandontheirconceptofanintegerrepre-sentation.AgoodanswerisdescribedbyProject4.5,whereasingly-linkedlistissuggested.Themoststraightforwardimplementationstoreseachdigitinitsownlistnode,withdigitsstoredinreverseorder.Additionandmulti-plicationareimplementedbywhatamountstograde-schoolarithmetic.Foraddition,simplymarchdowninparallelthroughthetwolistsrepresentingtheoperands,ateachdigitappendingtoanewlisttheappropriatepartialsumandbringingforwardacarrybitasnecessary.Formultiplication,com-binetheadditionfunctionwithanewfunctionthatmultipliesasingledigitbyaninteger.Exponentiationcanbedoneeitherbyrepeatedmultiplication(notreallypractical)orbythetraditionalΘ(logn)-timealgorithmbasedonthebinaryrepresentationoftheexponent.Discoveringthisfasteralgorithmwillbebeyondthereachofmoststudents,soshouldnotberequired.

1.3AsampleADTforcharacterstringsmightlookasfollows(withthenormalinterpretationofthefunctionnamesassumed).

1

2Chap.1DataStructuresandAlgorithms

//Concatenatetwostrings

Stringstrcat(Strings1,Strings2);

//Returnthelengthofastring

intlength(Strings1);

//Extractasubstring,startingat‘start’,

//andoflength‘length’

Stringextract(Strings1,intstart,intlength);

//Getthefirstcharacter

charfirst(Strings1);

//Comparetwostrings:thenormalC++strcmpfunc-tion.Some

//conventionshouldbeindicatedforhowtointer-pretthe

//returnvalue.InC++,thisis-

1fors1<s2;0fors1=s2;

//and1fors1>s2.

intstrcmp(Strings1,Strings2)

//Copyastring

intstrcpy(Stringsource,Stringdestination)

1.4TheanswertothisquestionisprovidedbytheADTforlistsgiveninChap-

ter4.

1.5One’scomplimentstoresthebinaryrepresentationofpositivenumbers,and

storesthebinaryrepresentationofanegativenumberwiththebitsinverted.Two’scomplimentisthesame,exceptthatanegativenumberhasitsbitsinvertedandthenoneisadded(forreasonsofef ciencyinhardwareimple-mentation).ThisrepresentationisthephysicalimplementationofanADTde nedbythenormalarithmeticoperations,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);

3

OneimplementationforthesparsematrixisdescribedinSection12.3Anotherim-plementationisahashtablewhosesearchkeyisaconcatenationofthematrixcoor-dinates.

Everyproblemcertainlydoesnothaveanalgorithm.AsdiscussedinChapter15,thereareanumberofreasonswhythismightbethecase.Someproblemsdon’thaveasuf cientlyclearde nition.Someproblems,suchasthehaltingproblem,arenon-computable.Forsomeproblems,suchasonetypicallystudiedbyarti cialintelligenceresearchers,wesimplydon’tknowasolution.

Wemustassumethatby“algorithm”wemeansomethingcomposedofstepsareofanaturethattheycanbeperformedbyacomputer.Ifso,thananyalgorithmcanbeexpressedinC++.Inparticular,ifanalgorithmcanbeexpressedinanyothercomputerprogramminglanguage,thenitcanbeexpressedinC++,sinceall(suf cientlygeneral)computerprogramminglanguagescomputethesamesetoffunctions.

Theprimitiveoperationsare(1)addingnewwordstothedictionaryand(2)search-ingthedictionaryforagivenword.Typically,dictionaryaccessinvolvessomesortofpre-processingofthewordtoarriveatthe“root”oftheword.

Atwentypagedocument(singlespaced)islikelytocontainabout20,000words.Ausermaybewillingtowaitafewsecondsbetweenindividual“hits”ofmis-spelledwords,http://www.77cn.com.cnerswilltypicallyinsertindividualwordsintothedictionaryinteractively,sothisprocesscantakeacoupleofseconds.Thus,searchmustbemuchmoreef cientthaninsertion.Theusershouldbeableto ndacitybasedonavarietyofattributes(name,location,perhapscharacteristicssuchaspopulationsize).Theusershouldalsobeabletoin-sertanddeletecities.Thesearethefundamentaloperationsofanydatabasesystem:search,insertionanddeletion.

Areasonabledatabasehasatimeconstraintthatwillsatisfythepatienceofatypicaluser.Foraninsert,delete,orexactmatchquery,afewsecondsissatisfactory.Ifthedatabaseismeanttosupportrangequeriesandmassdeletions,theentireoperationmaybeallowedtotakelonger,perhap …… 此处隐藏：13340字，全部文档内容请下载后查看。喜欢就下载吧 ……