数据结构与算法分析C++版答案.docx
- 文档编号:14577393
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:49
- 大小:39.10KB
数据结构与算法分析C++版答案.docx
《数据结构与算法分析C++版答案.docx》由会员分享,可在线阅读,更多相关《数据结构与算法分析C++版答案.docx(49页珍藏版)》请在冰点文库上搜索。
数据结构与算法分析C++版答案
DataStructuresandAlgorithm习题答案
Prefaceii
1DataStructuresandAlgorithms1
2MathematicalPreliminaries5
3AlgorithmAnalysis17
4Lists,Stacks,andQueues23
5BimrvTrees32
J
6(ycncni)Trees40
7InternalSorting46
8FileProcessingandExternalSorting54
9Searching58
10Indexing64
11Graphs69
12ListsandArraysRc\nsited76
13AdviinccdTreeStmeturcs82
iiContents
14AnalysisTechniques88
15LimitstoComputation94
Preface
ContainedhereinarcthesolutionstoallexercisesfromthetextbookAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition・
Formostoftheproblemsrequiringanalgorithm1havegivenactualcode.Inafewcases1havepresentedpseudocode.Pleasebeawarethatthecodepresentedillthismanualhasnotactuallybeencompiledandtested.WhileIbelievethealgorithmstobeessentiallycorrect,theremaybeerrorsillsyntaxaswellassemantics・Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintendedanswer,ratherthanusableprograms.
1
DataStructuresandAlgorithms
Instructor?
snote:
Unliketheotherchapters,manyofthequestionsinthischapterarcnotreallysuitablef()rgradedwork.Thequestionsarcmainlyintendedtogetstudentsthinkingaboutdatastructuresissues・
1.1
Thisquestiondocsnothaveaspecificri曲tanswer,providedthestudentkeepstothespiritofthequestion・StudentsmayhavetroublewiththeconceptofHpemtions.”
1.2
Thisexerciseasksthestudenttoexpandontheirconceptofailintegerrepresentation.AgoodanswerisdescribedbyProject4.5,whereasin^y-liiikcdlistissuggested・Thumoststraightf()nxTardimplementationstoreseachdigitillitsownlistnode,withdigitsstoredinreverseorder.Additionandmultiplicationarcimplementedbywhatamountstograde-schoolarithmetic.Foraddition,simplymarchdowninparallelthroughthetwolistsrepresentingtheoperands,ateachdigitappendingtoanewlisttheappropriatepartialsumandbringingfi)r^*ardacarrybitasnecessary・Formultiplication,combinetheadditionfunctionwithanewfunctionthatmultipliesasingledigitbyaninteger.Exponentiarioncanbedoneeitherbyrepeatedmultiplication(notreallypractical)orbythetraditionalO(logn)-timcalgorithmbasedonthebinaryrepresentationoftheexponentDiscoveringthisfasteralgorithmwillbebeyondthereachofmoststudents,soshouldnotberequired.
1.3
AsampleADTf()rcharacterstringsmightlookasfollows(withthenormalinterpretationofthefunctionnamesassumed).
Chap・1DataStructuresandAlgorithms//Concatenatetwostrings
Stringstrcat(Siringsi,Strings2);
//Returnthelengthofastring
intlength(Siringsi);
//Extractasubstring,startingat4start",
//andoflength4length'
Stringcxtract(Siringshintstart,intlength);
//Getthefirstcharacter
charfirst(Stringsi);
//Compare:
twostrings:
thenormalC++strempfunction・
Some
//conventionshouldbeindicatedforhowtointerpret
the
//returnvalue.InC++,thisis1
forsl //and1forsl>s2. intstrcmp(Stringsi,Strings2) //Copyastring intstrcpy(Stringsource,Stringdestination) 1.4 TheanswertothisquestionisprovidedbytheAPTforlistsgiveninChapter 4. 1.5 One"scomplimentstoresthebinary-representationofpositivenumbers,andstoresthebinaryrepresentationofanegative: numberwiththebitsinverted・Two'scomplimentisthesame,exceptthatanegativenumberhasitsbitsinvertedandthenoneisadded(forreasonsofefficiencyinhardwareimplementation)・ThisrepresentationisthephysicalimplementationofanAPT definedbythenormalarithmeticoperations,declarations,andothersupport givenbytheprogramminglanguagef()rintegers・ 1.6 AnADTfor^o-dimcnsionalarraysmi曲tlookasfollows. Matrixadd(MatrixMl,MatrixM2); Matrixmultiply(MatrixMl,MatrixM2); Matrixtranspe)sc(MatrixMl); voidsctvaluc(MatrixMl,introw,intcol,intval); intge^aluc(MatrixMl,introw,intcol); ListgetrowfMatrixMl,introw); OneimplementationforthesparsematrixisdescribedinSection12.3Anotherimplementationisahashublcwhosesearchkevisaconcatenationofthematrixcoordinates. J 1.7 Evcnrproblemcertainlydocsnothaveanalgorithm・AsdiscussedinChapter15,therearcanumberofreasonswhythismightbetheease・Someproblemsdon"thaveasufficientlycleardefinition.Someproblems,suchasthehaltingproblem,arcn()n-computablc.Forsomeproblems,suchasonelypicallystudiedbyartificialintelligenceresearchers,wesimplydon'tknowasolution. 1.8 Wemustassumethatby"algorithm'wemeansomethingcomposedofstepsarcofanaturethattheycanbeperformedbyacomputer.IfsqthananyalgorithmcanbeexpressedillC++・Inparticular,ifanalgorithmcanbeexpressedinanyothercomputerprogramminglanguage,thenitcanbeexpressedinC++,sinceall(sufficientlygeneral)computerprogrammingkinguagescomputethesamesetoffunctions. 1.9 Theprimitiveoperationsarc (1)addingwordstothedictionaryand (2)searchingthedictionaryforagivenwnrd.Typically,dictionaryaccessinvolvessomesortofprc-proccssillgofthewordtoarriveatthe“rool: ”ofthe Atwentypagedocument(singlespaced)islikelytocontainabout20,000words.Ausermaybewillingtowaitafewsecondsbct\xrccnindividual"hits"ofmis-spelledwords,orperhapsuptoaminuteforthewholedocumenttobeprocessed.Thismc;insthatacheckforanindividualwordcalltakeabout10-20ms.Userswillapicallyinsertindividualwordsintothedictionaryinteractively,sothisprocesscantakeacoupleofseconds.Thus,searchmustbemuchmoreefficientthaninsertion. 1.10 Theusershouldbeabletofindacitybasedonavarict\-ofattributes(name,location,perhapscharacteristicssuchaspopulationsize)・Thuusershouldalsobeabletoinsertanddeletecities・Thesearcthefundamentaloperationsofallydatabasesystem: search,insertionanddeletion. Areasonabledatabasehasatimeconstraintthatwillsatisfythepatienceofatypicaluser.Foraninsert,delete,orexactmatchquery,afewsecondsissatisfactory・IFthedatabaseismc;uittosupportrangequeriesandmassdeletions,theentire(屮crationmaybeallowedtotakelonger,perhapsontheorderofaminute・thetime spenttoprocessindividualcitieswithintherangemustbeappropriatelyreduced・Inpractice,thedatarepresentationwillneedtobesuchthatitaccommodatesefficientprocessingtomeetthesetimeconstraints・Inparticular,itmaybencccssarx'tosupportoperationsthatprocessrangequeriesefficientlybyprocessingallcitiesintherangeasabatch,ratherthanasaseriesofoperationsonindividualcities. 1.11Studentsatthislev』arclikelyalreadyfamiliarwthbinarysearch.Thus,theyshouldtypicallyrespondwithsequentialsearchandbinary-search.Binarysearchshouldbedescribedasbettersinceittopicallyneedstomakefcx^^crcomparisons(andthusislikelytobemuchfoster). 1.12 TheanswertothisquestionisdiscussedinChapter8.Typicalmeasuresofcostwillbenumberofcomparisonsandnumberofswaps.Testsshouldincluderunningrimingsonsorted,reversesorted,andrandomlistsofvarioussizes. Chap・1DataStructuresandAlgorithms1.13 Thefirstpartiseasywiththehint,butthesecondpartisratherdifficulttodowithoutastack. a)boolchcckstring(stringS){ intcount=0; for(inti=0;i if(S[i]=='C)count++; *f(sH==,y){ if(count==0)returnFALSE; count—; if(count==0)returnTRUE;elsereturnFALSE; b)intcheckstring(StringStr){StackS; intcount=0; for(inti=0;i S.push(i); iF(S[i]=')'){if(S.isEmptyO)returni;S.popO; if(S.isEmptyO)return-1;elsereturnS.popQ; 1.14 AnswerstothisquestionarcdiscussedinSection7.2. 1.15 Thisissomewhatdifferentfromwritingsortingalgorithmsf<)racomputer,sinceperson'suworkingspaceistypicallylimiwd,asistheirability-tophysicallymanipulatethepiecesofpaper.Nonetheless,manyofthecommonsortingalgorithmshavetheiranalogstosolutionsforthisproblcm.Mosttypicalanswerswillbeinsertionsort,variationsonmergesort,andvariationsonbinsort. 1.16 AnswerstothisquestionarcdiscussedinChapter& 2 MathematicalPreliminaries 2.1 (a)Notreflexiveifthesethasanymembers.Onecouldargueitissymmetric,jintisymmetric,andtransitive,sincenoelementxHolatcanyof themlcs. (b) Notreflexive(foranyfemale).Notsymmetric(considerabrotherandsister).Not^uitisymmctric(considertwobrothers).Transitive(f(>rally3brothers)・ Notreflexive・Notsymmetric,andisantisymmetric・Nottransitive (onlygoesonelevel). (d) Notreflexive(fornearlyallnumbers).Symmetricsincea +b =b +a, sonotiiiirisymmctric・Transitive,butvacuouslyso(therecanbenodistincta,b,andc whereriRb andbRc). (e) Reflexive・Symmetric,sonotiuitisymmctric.Transitive(butsortofvacuous)・ (0 Reflexive一checkallthecases.Sinceitisonlytruewhenx =y,it istechnicallysymmetricandantisymmetric,butrathervacuous.Likewise, itistechnicallytransitive,butvacuous. 2.2 Ingeneral,provethatsomethingisailequivalencerelationbypnnnngthatitisreflexive,symmetric,andtransitive. Thisisailequivalencethateffectivelysplitstheintegersintooddandevensets・Itisreflexive(x +x isevenforanyintc^rrx)»symmetric (sincex +y=y+x)andtransitive(sinceyouarcalwaysaddingtwooddorevennumbersforallysatisfactorya,b,andc)・ (b) Thisisnotanequivalence.Tobeginwith,itisnotreflexiveforallyinteger. Thisisanequivalencethatd
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 分析 C+ 答案