当前位置:主页 > 课后答案 > 数据结构习题答案
数据结构教程(第2版)

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

  • 更新:2021-04-06
  • 大小:13.7 KB
  • 类别:数据结构
  • 作者:李春葆
  • 出版:清华大学出版社
  • 格式:PDF

  • 资源介绍
  • 相关推荐

《数据结构教程(第二版)》是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

资源下载

资源下载地址1:https://pan.baidu.com/s/1-h5o7YCivRgpaB3bJA0VwQ

相关资源

网友留言