数据结构与算法分析习题答案(补充完整版)

《SolutionsManualforAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis(3thEdition)--CliffordA.Shaffer》习题答案与第二版对照整理注：第一个题号为第三版的题号，截图中的题号均为对应第二版的题号。chapter33.2-3.3(第二版题号3.2-3.3）3.12(第二版题号：3.10注：第三版(a)(b)(c)(g)(h)(i)对应第二版(a)(b)(c)(d)(e)(f))

在第二版无对应答案的习题补充（题号为第3版的题号）：(d)𝚯(n2(e)𝚯(nlog2(f)𝚯(nlog2Chapter44.1-4.4(第二版题号：4.1-4.4）

Chapter55.15(第二版题号：无）15152052057251725181616(b)preordertraversal:155720181625 inordertraversal:571516182025postordertraversal:7516182520155.16(第二版题号：5.11）5.17(第二版题号：5.12）5.25(第二版题号：5.17）1291074185325.26(第二版题号：5.18）

Chapter66.17(第二版题号：无）FEBACDFEBACD6.18(第二版题号：无）AACEBCEBDDGG6.19(第二版题号：6.15）Chapter7

给一个待排序数组，分别写出每种排序算法的各趟排序结果。1．①直接插入排序序号123456789101112关键字834063138435965739796115i=24083[63138435965739796115]i=3406383[138435965739796115]i=413406383[8435965739796115]i=51340638384[35965739796115]i=6133540638384[965739796115]i=713354063838496[5739796115]i=81335405763838496[39796115]i=9133539405763838496[796115]i=1013353940576379838496[6115]i=111335394057616379838496[15]i=12131535394057616379838496②直接选择排序序号123456789101112关键字834063138435965739796115i=113[4063838435965739796115]i=21315[63838435965739796140]i=3131535[838463965739796140]i=413153539[8463965783796140]i=51315353940[63965783796184]i=6131535394057[966383796184]i=713153539405761[6383799684]i=81315353940576163[83799684]i=9131535394057616379[839684]i=1013153539405761637983[9684]i=111315353940576163798384[96]③快速排序关键字834063138435965739796115第一趟排序后[154063136135795739]83[9684]第二趟排序后[13]15[63406135795739]8384[96]第三趟排序后1315[3940613557]63[79]838496第四趟排序后1315[35]39[614057]6379838496第五趟排序后13153539[5740]616379838496第六趟排序后1315353940[57]616379838496第七趟排序后131535394057616379838496④堆排序关键字：834063138435965739796115排序成功的序列：968483796361574039351513排序过程如图简答题8－1.1、8－1.2、8－1.3所示。⑤归并排序关键字834063138435965739796115第一趟排序后[4083][1363][3584][5796][3979][1561]第二趟排序后[13406383][35578496][15396179]第三趟排序后[1335405763838496][15396179]第四趟排序后131535394057616379838496

Chapter88.2(第二版题号：8.2）8.18(第二版题号：8.10）

Chapter99.18(第二