本书根据计算机专业“资料库原理”课程的教学大纲编写，全书共分10章，分别介绍资料库的基础知识、

关係资料库、SQL语言、关係系统及其查询最佳化、关係数据理论、资料库设计、资料库保护、对象关係和面

向对象资料库系统、分散式资料库系统以及数据仓库概述。每章由基本知识点和例题分析组成，前者高度概

括和疏理本章应重点掌握的相关知识；后者则详尽地解析精选的典型习题。本书将使读者充分掌握“资料库

原理”课程求解问题的技巧与方法，深化对基本概念的理解，切实提高分析问题和解决问题的能力。

本书内容丰富，习题覆盖面广，不仅可以作为计算机专业本、专科资料库原理课程的学习参考书，也

是报考计算机专业硕士研究生的考生複习必读材料（複试），对资料库原理和套用课程的自学者以及计算

机等级（三级或四级）应试者也颇有助益。

李春葆，1986年7月毕业于华中工学院（现为华中科技大学）计算机软体专业，1989年7月毕业于中国科学院瀋阳自动化研究所，1989年7月分配到武汉大学计算机系工作至今，2000年评为教授。主要研究方向：数据挖掘和算法设计。先后主持和参加3S系统集成关键技术的研究（国家自然科学基金重点科技攻关项目，49631050）、城市地理信息系统标準规範的研究（国家测绘局项目）、湖北省财政厅三查管理信息系统、湖北省财政厅外汇管理信息系统、湖北省财政厅财政监督管理信息系统、武汉英华ERP系统等项目。在武汉大学学报、华中理工大学学报、计算机工程与套用、计算机套用研究等刊物上发表论文40余篇，在清华大学出版社、人民邮电出版社和机械工业出版社等出版社出版教材和论着60余本。

第1章 绪论 1
1.1 知识点1：数据结构的基本概念 1
1.1.1 要点归纳 1
1.1.2 例题解析 3
1.2 知识点2：算法和算法分析 9
1.2.1 要点归纳 9
1.2.2 例题解析 12
第2章 线性表 22
2.1 知识点1：线性表的基本概念 22
2.1.1 要点归纳 22
2.1.2 例题解析 25
2.2 知识点2：顺序表的算法 29
2.2.1 要点归纳 29
2.2.2 例题解析 32
2.3 知识点3：单鍊表的算法 42
2.3.1 要点归纳 42
2.3.2 例题解析 46
2.4 知识点4：双鍊表的算法 67
2.4.1 要点归纳 67
2.4.2 例题解析 71
2.5 知识点5：循环鍊表的算法 78
2.5.1 要点归纳 78
2.5.2 例题解析 81
第3章 栈和递归 87
3.1 知识点1：栈的基本概念 87
3.1.1 要点归纳 87
3.1.2 例题解析 88
3.2 知识点2：顺序栈的算法 94
3.2.1 要点归纳 94
3.2.2 例题解析 103
3.3 知识点3：链栈的算法 111
3.3.1 要点归纳 111
3.3.2 例题解析 112
3.4 知识点4：递归 116
3.4.1 要点归纳 116
3.4.2 例题解析 124
第4章 伫列 142
4.1 知识点1：伫列的基本概念 142
4.1.1 要点归纳 142
4.1.2 例题解析 143
4.2 知识点2：顺序队的算法 146
4.2.1 要点归纳 146
4.2.2 例题解析 150
4.3 知识点3：链队的算法 162
4.3.1 要点归纳 162
4.3.2 例题解析 164
第5章 串 171
5.1 知识点1：串的基本概念 171
5.1.1 要点归纳 171
5.1.2 例题解析 172
5.2 知识点2：顺序串的算法 174
5.2.1 要点归纳 174
5.2.2 例题解析 176
5.3 知识点3：链串的算法 179
5.3.1 要点归纳 179
5.3.2 例题解析 183
5.4 知识点4：模式匹配的算法 187
5.4.1 要点归纳 187
5.4.2 例题解析 194
第6章 数组和稀疏矩阵 201
6.1 知识点1：数组和特殊矩阵 201
6.1.1 要点归纳 201
6.1.2 例题解析 203
6.2 知识点2：稀疏矩阵 211
6.2.1 要点归纳 211
6.2.2 例题解析 214
第7章 树和二叉树 217
7.1 知识点1：树的基本概念 217
7.1.1 要点归纳 217
7.1.2 例题解析 222
7.2 知识点2：二叉树的基本概念 227
7.2.1 要点归纳 227
7.2.2 例题解析 233
7.3 知识点3：二叉树的算法 242
7.3.1 要点归纳 242
7.3.2 例题解析 253
7.4 知识点4：线索二叉树 281
7.4.1 要点归纳 281
7.4.2 例题解析 285
7.5 知识点5：哈夫曼树 287
7.5.1 要点归纳 287
7.5.2 例题解析 290
第8章 广义表 293
8.1 知识点1：广义表的基本概念 293
8.1.1 要点归纳 293
8.1.2 例题解析 295
8.2 知识点2：广义表的算法设计 298
8.2.1 要点归纳 298
8.2.2 例题解析 301
第9章 图 307
9.1 知识点1：图的基本概念 307
9.1.1 要点归纳 307
9.1.2 例题解析 312
9.2 知识点2：图的遍历算法 324
9.2.1 要点归纳 324
9.2.2 例题解析 326
9.3 知识点3：最小生成树 346
9.3.1 要点归纳 346
9.3.2 例题解析 350
9.4 知识点4：最短路径 355
9.4.1 要点归纳 355
9.4.2 例题解析 361
9.5 知识点5：AOV网和拓扑排序 366
9.5.1 要点归纳 366
9.5.2 例题解析 368
9.6 知识点6：AOE网与关键路径 370
9.6.1 要点归纳 370
9.6.2 例题解析 372
第10章 查找 377
10.1 知识点1：线性表的查找 377
10.1.1 要点归纳 377
10.1.2 例题解析 382
10.2 知识点2：树表的查找 390
10.2.1 要点归纳 390
10.2.2 例题解析 399
10.3 知识点3：哈希表的查找 419
10.3.1 要点归纳 419
10.3.2 例题解析 422
第11章 内排序 437
11.1 知识点1：插入排序算法 437
11.1.1 要点归纳 437
11.1.2 例题解析 440
11.2 知识点2：选择排序算法 446
11.2.1 要点归纳 446
11.2.2 例题解析 449
11.3 知识点3：交换排序算法 457
11.3.1 要点归纳 457
11.3.2 例题解析 459
11.4 知识点4：归併排序算法 469
11.4.1 要点归纳 469
11.4.2 例题解析 470
11.5 知识点5：基数排序算法 474
11.5.1 要点归纳 474
11.5.2 例题解析 475
第12章 外排序和档案 480
12.1 知识点1：外排序 480
12.1.1 要点归纳 480
12.1.2 例题解析 482
12.2 知识点2：档案 486
12.2.1 要点归纳 486
12.2.2 例题解析 488
附录A 两份重点大学本科“数据结构”考试试题 494
附录B 2009年～2012年全国计算机专业硕士学位研究生入学考试数据结构部分试题及参考答案 506
参考文献 528