《数据结构与算法分析：C语言描述(第二版)》课后习题答案

《数据结构与算法分析：C语言描述》曾被评为20世纪顶尖的30部计算机著作之一，作者在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评，已被世界500余所大学选作教材。

在《数据结构与算法分析：C语言描述》中，作者精炼并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。

《数据结构与算法分析：C语言描述》特色：着重讨论了算法设计技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。系统介绍了当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。详细讨论了摊还分析，考查书中介绍的一些高级数据结构。增加了高级数据结构及其实现的内容，包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平均情况分析的一些新结果。

目录

• Introduction1
•  
• 1.1.WhatstheBookAbout?1
•  
• 1.2.MathematicsReview3
•  
• 1.2.1.Exponents3
•  
• 1.2.2.Logarithms3
•  
• 1.2.3.Series4
•  
• 1.2.4.ModularArithmetic5
•  
• 1.2.5.ThePWord6
•  
• 1.3.ABriefIntroductiontoRecursion
•  
• Summary12
•  
• Exercises12
•  
• References13
• 2AlgorithmAnalysis15
•  
• 2.1.MathematicalBackground15
•  
• 2.2.Model18
•  
• 2.3.WhattoAnalyze18
•  
• 2.4.RunningTuneCalculations20
•  
• 2.4.1.ASimpleExample21
•  
• 2.4.2.GeneralRules21
•  
• 2.4.3.SolutionsfortheMaximumSubsequenceSumProblem24
•  
• 2.4.4.LogarithmsintheRunningTune28
•  
• 2.4.5.CheckingYourAnalysis33
•  
• 2.4.6.AGrainofSalt33
•  
• Summary34
•  
• Exercises35
•  
• References39
•  
• 3Lists,Stacks,andQueues41
•  
• 3.1.AbstractDataTypes(AnTs)41
•  
• 3.2.TheListADT42
•  
• 3.2.1.SimpleArrayImplementationofLists43
•  
• 3.2.2.LinkedLists43
•  
• 3.2.3.ProgrammingDetails44
•  
• 3.2.4.CommonErrors49
•  
• 3.2.5.DoublyLinkedLists51
•  
• 3.2.6.CircularlyUnkedLists52
•  
• 3.2.7.Examples52
•  
• 3.2.8.CursorImplementationofLinkedLists57
•  
• 3.3.TheStackADT62
•  
• 3.3.1.StackModel62
•  
• 3.3.2.ImplementationofStacks63
•  
• 3.3.3.Applications71
•  
• 3.4.TheQueueADT79
•  
• 3.4.1.QueueModel79
•  
• 3.4.2.ArrayImplementationofQueues79
•  
• 3.4.3.ApplicationsofQueues84
•  
• Summary85
•  
• Exercises85
•  
• 4Trees89
•  
• 4.1.Preliminaries89
•  
• 4.1.1.ImplementationofTrees90
•  
• 4.1.2.TreeTraversalswithanApplication91
•  
• 4.2.BinaryTrees95
•  
• 4.2.1.Implementation96
•  
• 4.2.2.ExpressionTrees97
•  
• 4.3.TheSearchTreeADT-BinarySearchTrees100
•  
• 4.3.1.MakeEmpty101
•  
• 4.3.2.Find101
•  
• 4.3.3.FindMinandFindMax103
•  
• 4.3.4.Insert104
•  
• 4.3.5.Delete105
•  
• 4.3.6.Average-CaseAnalysis107
•  
• 4.4.AvITrees110
•  
• 4.4.1.SingleRotation112
•  
• 4.4.2.DoubleRotation115
•  
• 4.5.SplayTrees123
•  
• 4.5.1.ASimpleIdea(ThatDoesNotWork)124
•  
• 4.5.2.Splaying126
•  
• 4.6.TreeTraversals(Revisited)132
•  
• 4.7.B-Trees133
•  
• Summary138
•  
• Exercises139
•  
• References146
•  
• 5Hashing149
•  
• 5.1.GeneralIdea149
•  
• 5.2.HashFunction150
•  
• 5.3.SeparateChaining152
•  
• 5.4.OpenAddressing157
•  
• 5.4.1.LinearProbing157
•  
• 5.4.2.QuadraticProbing160
•  
• 5.4.3.DoubleHashing164
•  
• 5.5.Rehashing165
•  
• 5.6.ExtendibleHashing168
•  
• Summary171
•  
• Exercises172
•  
• References175
•  
• 6PriorityQueues(Heaps)177
•  
• 6.1.Model177
•  
• 6.2.SimpleImplementations178
•  
• 6.3.BinaryHeap179
•  
• 6.3.1.StroctureProperty179
•  
• 6.3.2.HeapOrderProperty180
•  
• 6.3.3.BasicHeapOperations182
•  
• 6.3.4.OtherHeapOperations186
•  
• 6.4.ApplicationsofPriorityQueues189
•  
• 6.4.1.TheSelectionProblem189
•  
• 6.4.2.EventSimulation191
•  
• 6.5.d-Heaps192
•  
• 6.6.LeftistHeaps193
•  
• 6.6.1.LeftistHeapProperly193
•  
• 6.6.2.LeftistHeapOperations194
•  
• 6.7.SkewHeaps200
•  
• 6.8.BinomialQueues202
•  
• 6.8.1.BinomialQueueStructure202
•  
• 6.8.2.BinomialQueueOperations204
•  
• 6.8.3.ImplementationofBinomialQueues205
•  
• Summary212
•  
• Exercises212
•  
• References216
•  
• 7Sorting219
•  
• 7.1.Preliminaries219
•  
• 7.2.InsertionSort220
•  
• 7.2.1.TheAlgorithm220
•  
• 7.2.2.AnalysisofInsertionSort221
•  
• 7.3.ALowerBoundforSimpleSortingAlgorithms221
•  
• 7.4.SheUsort222
•  
• 7.4.1.Worst-CaseAnalysisofShellsort224
•  
• 7.5.Heapsort226
•  
• 7.5.1.AnalysisofHeapsort228
•  
• 7.6.Mergesort230
•  
• 7.6.1.AnalysisofMergesort232
•  
• 7.7.Quicksort235
•  
• 7.7.1.PickingthePivot236
•  
• 7.7.2.PartitioningStrategy237
•  
• 7.7.3.SmallArrays240
•  
• 7.7.4.ActualQuicksortRoutines240
•  
• 7.7.5.AnalysisofQuicksort241
•  
• 7.7.6.ALinear-Expected-TimeAlgorithmforSelection245
•  
• 7.8.SortingLargeStructures247
•  
• 7.9.AGeneralLowerBoundforSorting247
•  
• 7.9.1.DecisionTrees247
•  
• 7.10.BucketSort250
•  
• 7.11.ExternalSorting250
•  
• 7.11.1.WhyWeNeedNewAlgorithms251
•  
• 7.11.2.ModelforExternalSorting251
•  
• ……
•  
• 8TheDisjointSetADT
•  
• 9GraphAlgorithms
•  
• 10AlgorithmDesignTechniques
•  
• 11AmortizedAnalysis
•  
• 12AdvancedDataStructuresandImplementation