《数据结构与算法分析》(C++第3版)各章节答案

APracticalIntroductiontoDataStructuresandAlgorithmAnalysisThirdEdition(C++Version)CliffordA.ShafferDepartmentofComputerScienceVirginiaTechBlacksburg,VA24061January19,2010Copyrightc2009-2010byCliffordA.Shaffer.Thisdocumentismadefreelyavailableforeducationalandothernon-commercialuse.Youmaymakecopiesofthisfileandredistributeitwithoutcharge.Youmayextractportionsofthisdocumentprovidedthatthefrontpage,includingthetitle,author,andthisnoticeareincluded.Anycommercialuseofthisdocumentreq[e-mail]histextisavailableat˜shaffer/Book/ContentsPrefacexiiiIPreliminaries11DataStructuresandAlgorithms31.1APhilosophyofDataStructures41.1.1TheNeedforDataStructures41.1.2CostsandBenefits61.2AbstractDataTypesandDataStructures81.3DesignPatterns121.3.1Flyweight131.3.2Visitor141.3.3Composite151.3.4Strategy161.4Problems,Algorithms,andPrograms171.5FurtherReading191.6Exercises212MathematicalPreliminaries252.1SetsandRelations252.2MiscellaneousNotation292.3Logarithms312.4SummationsandRecurrences33iiiivContents2.5Recursion362.6MathematicalProofTechniques392.6.1DirectProof402.6.2ProofbyContradiction402.6.3ProofbyMathematicalInduction412.7Estimating472.8FurtherReading492.9Exercises503AlgorithmAnalysis573.1Introduction573.2Best,Worst,andAverageCases633.3AFasterComputer,oraFasterAlgorithm?653.4AsymptoticAnalysis673.4.1UpperBounds683.4.2LowerBounds703.4.3Notation713.4.4SimplifyingRules723.4.5ClassifyingFunctions733.5CalculatingtheRunningTimeforaProgram743.6AnalyzingProblems793.7CommonMisunderstandings813.8MultipleParameters833.9SpaceBounds843.10SpeedingUpYourPrograms863.11EmpiricalAnalysis893.12FurtherReading903.13Exercises913.14Projects95IIFundamentalDataStructures974Lists,Stacks,andQueues99Contentsv4.1Lists1004.1.1Array-BasedListImplementation1044.1.2LinkedLists1074.1.3ComparisonofListImplementations1184.1.4ElementImplementations1204.1.5DoublyLinkedLists1214.2Stacks1274.2.1Array-BasedStacks1274.2.2LinkedStacks1284.2.3ComparisonofArray-BasedandLinkedStacks1314.2.4ImplementingRecursion1314.3Queues1354.3.1Array-BasedQueues1364.3.2LinkedQueues1394.3.3ComparisonofArray-BasedandLinkedQueues1424.4DictionariesandComparators1424.5FurtherReading1524.6Exercises1534.7Projects1565BinaryTrees1595.1DefinitionsandProperties1595.1.1TheFullBinaryTreeTheorem1625.1.2ABinaryTreeNodeADT1635.2BinaryTreeTraversals1655.3BinaryTreeNodeImplementations1695.3.1Pointer-BasedNodeImplementations1695.3.2SpaceRequirements1755.3.3ArrayImplementationforCompleteBinaryTrees1775.4BinarySearchTrees1785.5HeapsandPriorityQueues1885.6HuffmanCodingTrees1955.6.1BuildingHuffmanCodingTrees196viContents5.6.2AssigningandUsingHuffmanCodes2025.7FurtherReading2065.8Exercises2065.9Projects2106Non-BinaryTrees2136.1GeneralTreeDefinitionsandTerminology2136.1.1AnADTforGeneralTreeNodes2146.1.2GeneralTreeTraversals2166.2TheParentPointerImplementation2176.3GeneralTreeImplementations2256.3.1ListofChildren2256.3.2TheLeft-Child/Right-SiblingImplementation2256.3.3DynamicNodeImplementations2266.3.4Dynamic“Left-Child/Right-Sibling”Implementation2296.4K-aryTrees2306.5SequentialTreeImplementations2316.6FurtherReading2356.7Exercises2356.8Projects238IIISortingandSearching2417InternalSorting2437.1SortingTerminologyandNotation2447.2Three(n2)SortingAlgorithms2457.2.1InsertionSort2467.2.2BubbleSort2487.2.3SelectionSort2497.2.4TheCostofExchangeSorting2517.3Shellsort2527.4Mergesort2547.5Quicksort257Contentsvii7.6Heapsort2647.7BinsortandRadixSort2677.8AnEmpiricalComparisonofSortingAlgorithms2737.9LowerBoundsforSorting2757.10FurtherReading2797.11Exercises2807.12Projects2838FileProcessingandExternalSorting2878.1PrimaryversusSecondaryStorage2888.2DiskDrives2908.2.1DiskDriveArchitecture2918.2.2DiskAccessCosts2948.3BuffersandBufferPools2978.4TheProgrammer’sViewofFiles3058.5ExternalSorting3068.5.1SimpleApproachestoExternalSorting3098.5.2ReplacementSelection3128.5.3MultiwayMerging3148.6FurtherReading3198.7Exercises3198.8Projects3239Searching3279.1SearchingUnsortedandSortedArrays3289.2Self-OrganizingLists3349.3BitVectorsforRepresentingSets3399.4Hashing3409.4.1HashFunctions3419.4.2OpenHashing3469.4.3ClosedHashing3479.4.4AnalysisofClosedHashing3569.4.5Deletion360viiiContents9.5FurtherReading3619.6Exercises3629.7Projects36510Indexing36710.1LinearIndexing36910.2ISAM37110.3Tree-basedIndexing37410.42-3Trees37610.5B-Trees38410.5.1B+-Trees38510.5.2B-TreeAnalysis39210.6FurtherReading39410.7Exercises39410.8Projects397IVAdvancedDataStructures39911Graphs40111.1TerminologyandRepresentations40211.2GraphImplementations40611.3GraphTraversals41011.3.1Depth-FirstSearch41411.3.2Breadth-FirstSearch41511.3.3TopologicalSort41711.4Shortest-PathsProblems42011.4.1Single-SourceShortestPaths42111.5Minimum-CostSpanningTrees42411.5.1Prim’sAlgorithm42611.5.2Kruskal’sAlgorithm42911.6FurtherReading43111.7Exercises43111.8Projects434Contentsix12ListsandArraysRevisited43712.1Multilists43712.2MatrixRepresentations44112.3MemoryManagement44412.3.1DynamicSt