搜索
DataStructuresandAlgorithmAnalysisinC(secondedition)SolutionsManualMarkAllenWeissFloridaInternationalUniversityPrefaceIncludedinthismanualareanswerstomostoftheexercisesinthetextbookDataStructuresandAlgorithmAnalysisinC,secondedition,publishedbyAddison-Wesley.Theseanswersreflectthestateofthebookinthefirstprinting.Specificallyomittedarelikelyprogrammingassignmentsandanyquestionwhosesolu-tionispointedtobyareferenceattheendofthechapter.Solutionsvaryindegreeofcomplete-ness;generally,minordetailsarelefttothereader.Forclarity,programsaremeanttobepseudo-Cratherthancompletelyperfectcode.Errorscanbereportedtoweiss@fiu.edu.ThankstoGrigoriSchwarzandBrianHarveyforpointingouterrorsinpreviousincarnationsofthismanual.TableofContents1.Chapter1:Introduction......................................................................................................12.Chapter2:AlgorithmAnalysis..........................................................................................43.Chapter3:Lists,Stacks,andQueues.................................................................................74.Chapter4:Trees.................................................................................................................145.Chapter5:Hashing............................................................................................................256.Chapter6:PriorityQueues(Heaps)...................................................................................297.Chapter7:Sorting..............................................................................................................368.Chapter8:TheDisjointSetADT.......................................................................................429.Chapter9:GraphAlgorithms.............................................................................................4510.Chapter10:AlgorithmDesignTechniques......................................................................5411.Chapter11:AmortizedAnalysis......................................................................................6312.Chapter12:AdvancedDataStructuresandImplementation............................................66-iii-Chapter1:Introduction1.3Becauseofround-offerrors,itiscustomarytospecifythenumberofdecimalplacesthatshouldbeincludedintheoutputandroundupaccordingly.Otherwise,numberscomeoutlookingstrange.Weassumeerrorcheckshavealreadybeenperformed;theroutineSeparateOislefttothereader.CodeisshowninFig.1.1.1.4ThegeneralwaytodothisistowriteaprocedurewithheadingvoidProcessFile(constchar*FileName);whichopensFileName,Odoeswhateverprocessingisneeded,andthenclosesit.Ifalineoftheform#includeSomeFileisdetected,thenthecallProcessFile(SomeFile);ismaderecursively.Self-referentialincludescanbedetectedbykeepingalistoffilesforwhichacalltoProcessFileOhasnotyetterminated,andcheckingthislistbeforemakinganewcalltoProcessFile.O1.5(a)Theproofisbyinduction.Thetheoremisclearlytruefor0XO≤1,sinceitistrueforXO=1,andforXO1,logXOisnegative.Itisalsoeasytoseethatthetheoremholdsfor1XO≤2,sinceitistrueforXO=2,andforXO2,logXOisatmost1.SupposethetheoremistrueforpOXO≤2pO(wherepOisapositiveinteger),andconsiderany2pOYO≤4pO(pO≥1).ThenlogYO=1+log(YO/2)1+YO/2YO/2+YO/2≤YO,wherethefirstine-qualityfollowsbytheinductivehypothesis.(b)Let2XO=AO.ThenAOBO=(2XO)BO=2XBO.ThuslogAOBO=XBO.SinceXO=logAO,thetheoremisproved.1.6(a)Thesumis4/3andfollowsdirectlyfromtheformula.(b)SO=41__+422___+433___+....4SO=1+42__+423___+....Subtractingthefirstequationfromthesecondgives3SO=1+41__+422___+....Bypart(a),3SO=4/3soSO=4/9.(c)SO=41__+424___+439___+....4SO=1+44__+429___+4316___+....Subtractingthefirstequa-tionfromthesecondgives3SO=1+43__+425___+437___+....Rewriting,weget3SO=2iO=0Σ∞4iOi___+iO=0Σ∞4iO1___.Thus3SO=2(4/9)+4/3=20/9.ThusSO=20/27.(d)LetSNO=iO=0Σ∞4iOiONO___.Followthesamemethodasinparts(a)-(c)toobtainaformulaforSNOintermsofSNO-1,SNO-2,...,SO0andsolvetherecurrence.Solvingtherecurrenceisverydifficult.-1-______________________________________________________________________________________________________________________________________________________________doubleRoundUp(doubleN,intDecPlaces){inti;doubleAmountToAdd=0.5;for(i=0;iDecPlaces;i++)AmountToAdd/=10;returnN+AmountToAdd;}voidPrintFractionPart(doubleFractionPart,intDecPlaces){inti,Adigit;for(i=0;iDecPlaces;i++){FractionPart*=10;ADigit=IntPart(FractionPart);PrintDigit(Adigit);FractionPart=DecPart(FractionPart);}}voidPrintReal(doubleN,intDecPlaces){intIntegerPart;doubleFractionPart;if(N0){putchar(’-’);N=-N;}N=RoundUp(N,DecPlaces);IntegerPart=IntPart(N);FractionPart=DecPart(N);PrintOut(IntegerPart);/*Usingroutineintext*/if(DecPlaces0)putchar(’.’);PrintFractionPart(FractionPart,DecPlaces);}Fig.1.1.______________________________________________________________________________________________________________________________________________________________1.7iO=OINO/2OKΣNi1__=iO=1ΣNi1__-iO=1ΣOINO/2-1OKi1__~~lnNO-lnNO/2~~ln2.-2-1.824=16≡1(modO5).(24)25≡125(modO5).Thus2100≡1(modO5).1.9(a)Proofisbyinduction.Thestatem