《数据结构教程(第2版)》课后习题答案

《数据结构教程（第二版）》是2008年清华大学出版社出版的图书。

数据结构是计算机学科的必修课程。本教程是作者针对数据结构课程概念多、算法灵活和抽象性强的特点，在总结长期教学经验的基础上编写而成的。全书分为14章，内容涵盖数据结构基本概念、线性表、栈和队列、串、数组和稀疏矩阵、递归、树和二叉树、广义表、图、查找、内排序、文件和采用面向对象方法描述算法。每章后均附有练习题和上机实验题。 

本书在第1版的基础上增加了线段树、并查集等相关数据结构，全书内容丰富、层次清晰，讲解深入浅出，可作为高等院校计算机及相关专业本科及研究生数据结构课程教材，也可供从事计算机软件开发和应用的工程技术人员参考。

目录

• 第1章 绪论 1
• 1.1 什么是数据结构 1
• 1.1.1 数据结构的定义 1
• 1.1.2 逻辑结构类型 4
• 1.1.3 存储结构类型 6
• 1.1.4 数据结构和数据类型 7
• 1.2 算法及其描述 11
• 1.2.1 什么是算法 11
• 1.2.2 算法描述 12
• 1.3 算法分析 13
• 1.3.1 算法设计的目标 13
• 1.3.2 算法效率分析 14
• 1.3.3 算法存储空间分析 17
• 1.4 数据结构+算法=程序 18
• 本章小结 24
• 练习题1 25
• 上机实验题1 26
• 第2章 线性表 27
• 2.1 线性表及其逻辑结构 27
• 2.1.1 线性表的定义 27
• 2.1.2 线性表的抽象数据类型描述 28
• 2.2 线性表的顺序存储结构 29
• 2.2.1 线性表的顺序存储结构——顺序表 29
• 2.2.2 顺序表基本运算的实现 30
• 2.3 线性表的链式存储结构 36
• 2.3.1 线性表的链式存储结构——链表 37
• 2.3.2 单链表基本运算的实现 38
• 2.3.3 双链表 45
• 2.3.4 循环链表 49
• 2.3.5 静态链表 51
• 2.4 线性表的应用 56
• 2.4.1 问题描述 56
• 2.4.2 数据组织 57
• 2.4.3 设计运算算法 57
• 2.4.4 设计求解程序 59
• 2.4.5 运行结果 59
• 2.5 有序表 60
• 本章小结 64
• 练习题2 64
• 上机实验题2 64
• 第3章 栈和队列 67
• 3.1 栈 67 [1]
• 3.1.1栈的定义 67
• 3.1.2栈的顺序存储结构及其基本运算实现 69
• 3.1.3栈的链式存储结构及其基本运算的实现 72
• 3.1.4栈的应用举例 75
• 3.2队列 84
• 3.2.1队列的定义 84
• 3.2.2队列的顺序存储结构及其基本运算的实现 85
• 3.2.3队列的链式存储结构及其基本运算的实现 89
• 3.2.4队列的应用举例 92
• 本章小结 97
• 练习题3 97
• 上机实验题3 98
• 第4章串 101
• 4.1串的基本概念 101
• 4.2串的存储结构 102
• 4.2.1串的顺序存储结构——顺序串 102
• 4.2.2串的链式存储结构——链串 108
• 4.3串的模式匹配 114
• 4.3.1Brute-Force算法 115
• 4.3.2KMP算法 117
• 本章小结 123
• 练习题4 123
• 上机实验题4 124
• 第5章数组和稀疏矩阵 126
• 5.1数组 126
• 5.1.1数组的基本概念 126
• 5.1.2数组的存储结构 127
• 5.1.3特殊矩阵的压缩存储 129
• 5.2稀疏矩阵 131
• 5.2.1稀疏矩阵的三元组表示 131
• 5.2.2稀疏矩阵的十字链表表示 136
• 本章小结 140
• 练习题5 140
• 上机实验题5 140
• 第6章递归 142
• 6.1什么是递归 142
• 6.1.1递归的定义 142
• 6.1.2何时使用递归 143
• 6.1.3递归模型 144
• 6.1.4递归与数学归纳法 145
• 6.2递归调用的实现原理 146
• 6.3递归算法的设计 148
• 6.3.1递归算法设计的步骤 148
• 6.3.2递归数据结构的递归算法设计 150
• 6.3.3递归求解方法的递归算法设计 151
• 6.4递归算法到非递归算法的转换 153
• 6.4.1尾递归和单向递归的消除 153
• 6.4.2模拟系统运行时的栈消除递归 154
• 本章小结 163
• 练习题6 163
• 上机实验题6 164
• 第7章树和二叉树 165
• 7.1树的基本概念 165
• 7.1.1树的定义 165
• 7.1.2树的逻辑表示方法 166
• 7.1.3树的基本术语 166
• 7.1.4树的性质 168
• 7.1.5树的基本运算 170
• 7.1.6树的存储结构 170
• 7.2二叉树概念和性质 173
• 7.2.1二叉树概念 173
• 7.2.2二叉树性质 174
• 7.2.3二叉树与树、森林之间的转换 175
• 7.3二叉树存储结构 177
• 7.3.1二叉树的顺序存储结构 177
• 7.3.2二叉树的链式存储结构 179
• 7.4二叉树的基本运算及其实现 180
• 7.4.1二叉树的基本运算概述 180
• 7.4.2二叉树的基本运算算法实现 180 [2]
• 7.5二叉树的遍历 183
• 7.5.1二叉树遍历的概念 183
• 7.5.2二叉树遍历递归算法 184
• 7.5.3二叉树遍历非递归算法 188
• 7.5.4层次遍历算法 197
• 7.6二叉树的构造 199
• 7.7线索二叉树 205
• 7.7.1线索二叉树的概念 205
• 7.7.2线索化二叉树 206
• 7.7.3遍历线索化二叉树 208
• 7.8哈夫曼树 209
• 7.8.1哈夫曼树概述 209
• 7.8.2哈夫曼树的构造算法 210
• 7.8.3哈夫曼编码 212
• 7.9线段树 214
• 7.9.1线段树的定义 214
• 7.9.2线段树的存储结构 215
• 7.9.3线段树基本运算的实现算法 215
• 7.10并查集 220
• 7.10.1什么叫并查集 221
• 7.10.2并查集的算法实现 222
• 本章小结 225
• 练习题7 225
• 上机实验题7 226
• 第8章广义表 228
• 8.1广义表的定义 228
• 8.2广义表的存储结构 230
• 8.3广义表的运算 232
• 8.3.1求广义表的长度 232
• 8.3.2求广义表的深度 232
• 8.3.3建立广义表的链式存储结构 233
• 8.3.4输出广义表 234
• 8.3.5广义表的复制 235
• 本章小结 240
• 练习题8 240
• 上机实验题8 240
• 第9章图 242
• 9.1图的基本概念 242
• 9.1.1图的定义 242
• 9.1.2图的基本术语 243
• 9.2图的存储结构 245
• 9.2.1邻接矩阵存储方法 245
• 9.2.2邻接表存储方法 247
• 9.2.3十字邻接表存储方法 250
• 9.2.4邻接多重表存储方法 251
• 9.3图的遍历 252
• 9.3.1图的遍历的概念 252
• 9.3.2深度优先搜索遍历 252
• 9.3.3广度优先搜索遍历 253
• 9.3.4非连通图的遍历 254
• 9.3.5图遍历算法的应用 255
• 9.4生成树和最小生成树 259
• 9.4.1生成树的概念 259
• 9.4.2无向图的连通分量和生成树 260
• 9.4.3有向图的强连通分量 261
• 9.4.4普里姆算法 262
• 9.4.5克鲁斯卡尔算法 264
• 9.5最短路径 268
• 9.5.1路径的概念 268
• 9.5.2从一个顶点到其余各顶点的最短路径 268
• 9.5.3每对顶点之间的最短路径 274
• 9.6拓扑排序 278
• 9.7AOE网与关键路径 280
• 本章小结 285
• 练习题9 285
• 上机实验题9 285
• 第10章查找 288
• 10.1查找的基本概念 288
• 10.2线性表的查找 289
• 10.2.1顺序查找 289
• 10.2.2二分查找 290
• 10.2.3分块查找 292
• 10.3树表的查找 295
• 10.3.1二叉排序树 295 [2]
• 10.3.2平衡二叉树 303
• 10.3.3B-树 320
• 10.3.4B+树 331
• 10.3.52-3-4树 333
• 10.3.6红黑树 335
• 10.4哈希表查找 338
• 10.4.1哈希表的基本概念 338
• 10.4.2哈希函数构造方法 339
• 10.4.3哈希冲突解决方法 340
• 10.4.4哈希表上的运算 343
• 本章小结 347
• 练习题10 347
• 上机实验题10 347
• 第11章内排序 349
• 11.1排序的基本概念 349
• 11.2插入排序 350
• 11.2.1直接插入排序 350
• 11.2.2希尔排序 352
• 11.3交换排序 354
• 11.3.1冒泡排序 354
• 11.3.2快速排序 356
• 11.4选择排序 360
• 11.4.1直接选择排序 360
• 11.4.2堆排序 362
• 11.5归并排序 365
• 11.6基数排序 369
• 11.7各种内排序方法的比较和选择 371
• 本章小结 373
• 练习题11 373
• 上机实验题11 374
• 第12章外排序 375
• 12.1外排序概述 375
• 12.2磁盘排序 376
• 12.2.1磁盘排序过程 376
• 12.2.2多路平衡归并 377
• 12.2.3初始归并段的生成 379
• 12.2.4最佳归并树 381
• 12.3磁带排序 384
• 12.3.1多路平衡归并排序 384
• 12.3.2多阶段归并排序 385
• 本章小结 386
• 练习题12 387
• 上机实验题12 387
• 第13章文件 388
• 13.1文件的基本概念 388
• 13.1.1什么是文件 388
• 13.1.2文件的逻辑结构及操作 389
• 13.1.3文件的存储结构 389
• 13.2顺序文件 390
• 13.3索引文件 390
• 13.3.1ISAM文件 391
• 13.3.2VSAM文件 394
• 13.4哈希文件 396
• 13.5多关键字文件 397
• 13.5.1多重表文件 397
• 13.5.2倒排文件 398
• 本章小结 399
• 练习题13 399
• 上机实验题13 400
• 第14章采用面向对象的方法描述算法 401
• 14.1面向对象的概念 401
• 14.1.1重要概念 401
• 14.1.2主要优点 402
• 14.2用C++描述面向对象的程序 403
• 14.2.1类 403
• 14.2.2类对象 405
• 14.2.3构造函数和析构函数 407
• 14.2.4派生类 410
• 14.3用C++描述数据结构算法 413
• 14.3.1顺序表类 413
• 14.3.2链栈类 416
• 14.3.3二叉树类 418
• 附录A综合实验题 424
• 附录B实验报告格式 426
• 附录C书中部分算法清单 427
• 参考文献 430