数据结构与算法分析 C++版答案.docx
- 文档编号:5428557
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:69
- 大小:32.83KB
数据结构与算法分析 C++版答案.docx
《数据结构与算法分析 C++版答案.docx》由会员分享,可在线阅读,更多相关《数据结构与算法分析 C++版答案.docx(69页珍藏版)》请在冰点文库上搜索。
数据结构与算法分析C++版答案
DataStructuresandAlgorithm习题答案
Prefaceii
1DataStructuresandAlgorithms1
2MathematicalPreliminaries5
3AlgorithmAnalysis17
4Lists,Stacks,andQueues23
5BinaryTrees32
6GeneralTrees40
7InternalSorting46
8FileProcessingandExternalSorting54
9Searching58
10Indexing64
11Graphs69
12ListsandArraysRevisited76
13AdvancedTreeStructures82
i
iiContents
14AnalysisTechniques88
15LimitstoComputation94
Preface
ContainedhereinarethesolutionstoallexercisesfromthetextbookAPractical
IntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition.
FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.In
afewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresented
inthismanualhasnotactuallybeencompiledandtested.WhileIbelievethealgorithms
tobeessentiallycorrect,theremaybeerrorsinsyntaxaswellassemantics.
Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintended
answer,ratherthanusableprograms.
1
DataStructuresandAlgorithms
Instructor’snote:
Unliketheotherchapters,manyofthequestionsinthischapter
arenotreallysuitableforgradedwork.Thequestionsaremainlyintendedtoget
studentsthinkingaboutdatastructuresissues.
1.1
Thisquestiondoesnothaveaspecificrightanswer,providedthestudent
keepstothespiritofthequestion.Studentsmayhavetroublewiththeconcept
of“operations.”
1.2
Thisexerciseasksthestudenttoexpandontheirconceptofanintegerrepresentation.
AgoodanswerisdescribedbyProject4.5,whereasingly-linked
listissuggested.Themoststraightforwardimplementationstoreseachdigit
initsownlistnode,withdigitsstoredinreverseorder.Additionandmultiplication
areimplementedbywhatamountstograde-schoolarithmetic.For
addition,simplymarchdowninparallelthroughthetwolistsrepresenting
theoperands,ateachdigitappendingtoanewlisttheappropriatepartial
sumandbringingforwardacarrybitasnecessary.Formultiplication,combine
theadditionfunctionwithanewfunctionthatmultipliesasingledigit
byaninteger.Exponentiationcanbedoneeitherbyrepeatedmultiplication
(notreallypractical)orbythetraditionalΘ(logn)-timealgorithmbasedon
thebinaryrepresentationoftheexponent.Discoveringthisfasteralgorithm
willbebeyondthereachofmoststudents,soshouldnotberequired.
1.3
AsampleADTforcharacterstringsmightlookasfollows(withthenormal
interpretationofthefunctionnamesassumed).
Chap.1DataStructuresandAlgorithms
//Concatenatetwostrings
Stringstrcat(Strings1,Strings2);
//Returnthelengthofastring
intlength(Strings1);
//Extractasubstring,startingat‘start’,
//andoflength‘length’
Stringextract(Strings1,intstart,intlength);
//Getthefirstcharacter
charfirst(Strings1);
//Comparetwostrings:
thenormalC++strcmpfunction.
Some
//conventionshouldbeindicatedforhowtointerpret
the
//returnvalue.InC++,thisis1
fors1 //and1fors1>s2. intstrcmp(Strings1,Strings2) //Copyastring intstrcpy(Stringsource,Stringdestination) 1.4 TheanswertothisquestionisprovidedbytheADTforlistsgiveninChapter 4. 1.5 One’scomplimentstoresthebinaryrepresentationofpositivenumbers,and storesthebinaryrepresentationofanegativenumberwiththebitsinverted. Two’scomplimentisthesame,exceptthatanegativenumberhasitsbits invertedandthenoneisadded(forreasonsofefficiencyinhardwareimplementation). ThisrepresentationisthephysicalimplementationofanADT definedbythenormalarithmeticoperations,declarations,andothersupport givenbytheprogramminglanguageforintegers. 1.6 AnADTfortwo-dimensionalarraysmightlookasfollows. Matrixadd(MatrixM1,MatrixM2); Matrixmultiply(MatrixM1,MatrixM2); Matrixtranspose(MatrixM1); voidsetvalue(MatrixM1,introw,intcol,intval); intgetvalue(MatrixM1,introw,intcol); Listgetrow(MatrixM1,introw); OneimplementationforthesparsematrixisdescribedinSection12.3Anotherimplementation isahashtablewhosesearchkeyisaconcatenationofthematrixcoordinates. 1.7 Everyproblemcertainlydoesnothaveanalgorithm.AsdiscussedinChapter15, thereareanumberofreasonswhythismightbethecase.Someproblemsdon’t haveasufficientlycleardefinition.Someproblems,suchasthehaltingproblem, arenon-computable.Forsomeproblems,suchasonetypicallystudiedbyartificial intelligenceresearchers,wesimplydon’tknowasolution. 1.8 Wemustassumethatby“algorithm”wemeansomethingcomposedofstepsare ofanaturethattheycanbeperformedbyacomputer.Ifso,thananyalgorithm canbeexpressedinC++.Inparticular,ifanalgorithmcanbeexpressedinany othercomputerprogramminglanguage,thenitcanbeexpressedinC++,sinceall (sufficientlygeneral)computerprogramminglanguagescomputethesamesetof functions. 1.9 Theprimitiveoperationsare (1)addingnewwordstothedictionaryand (2)searching thedictionaryforagivenword.Typically,dictionaryaccessinvolvessomesort ofpre-processingofthewordtoarriveatthe“root”oftheword. Atwentypagedocument(singlespaced)islikelytocontainabout20,000words.A usermaybewillingtowaitafewsecondsbetweenindividual“hits”ofmis-spelled words,orperhapsuptoaminuteforthewholedocumenttobeprocessed.This meansthatacheckforanindividualwordcantakeabout10-20ms.Userswill typicallyinsertindividualwordsintothedictionaryinteractively,sothisprocesscan takeacoupleofseconds.Thus,searchmustbemuchmoreefficientthaninsertion. 1.10 Theusershouldbeabletofindacitybasedonavarietyofattributes(name,location, perhapscharacteristicssuchaspopulationsize).Theusershouldalsobeabletoinsert anddeletecities.Thesearethefundamentaloperationsofanydatabasesystem: search,insertionanddeletion. Areasonabledatabasehasatimeconstraintthatwillsatisfythepatienceofatypical user.Foraninsert,delete,orexactmatchquery,afewsecondsissatisfactory.Ifthe databaseismeanttosupportrangequeriesandmassdeletions,theentireoperation maybeallowedtotakelonger,perhapsontheorderofaminute.However,thetime spenttoprocessindividualcitieswithintherangemustbeappropriatelyreduced.In practice,thedatarepresentationwillneedtobesuchthatitaccommodatesefficient processingtomeetthesetimeconstraints.Inparticular,itmaybenecessarytosupport operationsthatprocessrangequeriesefficientlybyprocessingallcitiesinthe rangeasabatch,ratherthanasaseriesofoperationsonindividualcities. 1.11 Studentsatthislevelarelikelyalreadyfamiliarwithbinarysearch.Thus,they shouldtypicallyrespondwithsequentialsearchandbinarysearch.Binarysearch shouldbedescribedasbettersinceittypicallyneedstomakefewercomparisons (andthusislikelytobemuchfaster). 1.12 TheanswertothisquestionisdiscussedinChapter8.Typicalmeasuresofcost willbenumberofcomparisonsandnumberofswaps.Testsshouldincluderunning timingsonsorted,reversesorted,andrandomlistsofvarioussizes. Chap.1DataStructuresandAlgorithms 1.13 Thefirstpartiseasywiththehint,butthesecondpartisratherdifficulttodowithout astack. a)boolcheckstring(stringS){ intcount=0; for(inti=0;i if(S[i]==’(’)count++; if(S[i]==’)’){ if(count==0)returnFALSE; count--; } } if(count==0)returnTRUE; elsereturnFALSE; } b)intcheckstring(StringStr){ StackS; intcount=0; for(inti=0;i if(S[i]==’(’) S.push(i); if(S[i]==’)’){ if(S.isEmpty())returni; S.pop(); } } if(S.isEmpty())return-1; elsereturnS.pop(); } 1.14 AnswerstothisquestionarediscussedinSection7.2. 1.15 Thisissomewhatdifferentfromwritingsortingalgorithmsforacomputer,since person’s“workingspace”istypicallylimited,asistheirabilitytophysicallymanipulate thepiecesofpaper.Nonetheless,manyofthecommonsortingalgorithmshave theiranalogstosolutionsforthisproblem.Mosttypicalanswerswillbeinsertion sort,variationsonmergesort,andvariationsonbinsort. 1.16 AnswerstothisquestionarediscussedinChapter8. 2 MathematicalPreliminaries 2.1 (a)Notreflexiveifthesethasanymembers.Onecouldargueitissymmetric, antisymmetric,andtransitive,sincenoelementviolateanyof therules. (b) Notreflexive(foranyfemale).Notsymmetric(considerabrotherand sister).Notantisymmetric(considertwobrothers).Transitive(forany 3brothers). (c) Notreflexive.Notsymmetric,andisantisymmetric.Nottransitive (onlygoesonelevel). (d) Notreflexive(fornearlyallnumbers).Symmetricsincea +b =b +a, sonotantisymmetric.Transitive,butvacuouslyso(therecanbeno distincta,b,andc whereaRb andbRc). (e) Reflexive.Symmetric,sonotantisymmetric.Transitive(butsortof vacuous). (f) Reflexive–checkallthecases.Sinceitisonlytruewhenx =y,it istechnicallysymmetricandantisymmetric,butrathervacuous.Likewise, itistechnicallytransitive,butvacuous. 2.2 Ingeneral,provethatsomethingisanequivalencerelationbyprovingthatit isreflexive
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法分析 C+版答案 数据结构 算法 分析 C+ 答案