数据结构习题与解析B级

　　本书是重点大学的资深教授根据高等学校计算机专业数据结构课程的教学大纲要求，结合丰富教学实践、经验编写而成的，通过对概念和习题的讲解和分析，帮助读者了解、掌握数据结构的原理和算法。本书按照课程的讲授顺序，阐述了线性表、栈和递归、队列、串、数组和稀疏矩阵、树和二叉树、广义表、图、查找、内排序、外排序和文件等内容。每章都以知识点为单位，剖析知识要点，并提供1～5级各种难度的例题，对相关内容作深入、透彻的分析，特别是增加了“知识创新”和“创新应用”两部分的内容，使读者充分掌握求解数据结构问题的思想和方法，深化对基本概念的理解，提高分析与解决问题的能力。本书适合作为课程考试和研究生考试辅导书，任课教师可以将其作为教学参考书使用。对于计算机专业本科学生，可以在学习时参考使用。

　　李春葆 教授，武汉大学计算机科学系副主任。长期从事软件设计与开发， 编著有《Visual FoxPro 6.0高级编程》、《Visual FoxPro 7.0程序设计教程》，合编著有《Visual Basic应用开发原理和技术》等。

第1章  绪论    1
1.1  知识点1：数据结构的基本概念    1
1.1.1  要点归纳    1
1.1.2  例题解析    3
1.2  知识点2：算法和算法分析    7
1.2.1  要点归纳    7
1.2.2  例题解析    9
第2章  线性表    16
2.1  知识点1：线性表的基本概念    16
2.1.1  要点归纳    16
2.1.2  例题解析    18
2.2  知识点2：顺序表的算法    22
2.2.1  要点归纳    22
2.2.2  例题解析    24
2.3  知识点3：单链表的算法    31
2.3.1  要点归纳    31
2.3.2  例题解析    35
2.4  知识点4：双链表的算法    51
2.4.1  要点归纳    51
2.4.2  例题解析    55
2.5  知识点5：循环链表的算法    58
2.5.1  要点归纳    58
2.5.2  例题解析    61
第3章  栈和递归    67
3.1  知识点1：栈的基本概念    67
3.1.1  要点归纳    67
3.1.2  例题解析    68
3.2  知识点2：顺序栈的算法    72
3.2.1  要点归纳    72
3.2.2  例题解析    80
3.3  知识点3：链栈的算法    86
3.3.1  要点归纳    86
3.3.2  例题解析    87
3.4  知识点4：递归    90
3.4.1  要点归纳    90
3.4.2  例题解析    99
第4章  队列    111
4.1  知识点1：队列的基本概念    111
4.1.1  要点归纳    111
4.1.2  例题解析    112
4.2  知识点2：顺序队的算法    114
4.2.1  要点归纳    114
4.2.2  例题解析    117
4.3  知识点3：链队的算法    124
4.3.1  要点归纳    124
4.3.2  例题解析    126
第5章  串    134
5.1  知识点1：串的基本概念    134
5.1.1  要点归纳    134
5.1.2  例题解析    135
5.2  知识点2：顺序串的算法    137
5.2.1  要点归纳    137
5.2.2  例题解析    139
5.3  知识点3：链串的算法    143
5.3.1  要点归纳    143
5.3.2  例题解析    146
5.4  知识点4：模式匹配的算法    149
5.4.1  要点归纳    149
5.4.2  例题解析    155
第6章  数组和稀疏矩阵    163
6.1  知识点1：数组    163
6.1.1  要点归纳    163
6.1.2  例题解析    165
6.2  知识点2：稀疏矩阵    171
6.2.1  要点归纳    171
6.2.2  例题解析    174
第7章  树和二叉树    178
7.1  知识点1：树的基本概念    178
7.1.1  要点归纳    178
7.1.2  例题解析    182
7.2  知识点2：二叉树的基本概念    185
7.2.1  要点归纳    185
7.2.2  例题解析    189
7.3  知识点3：二叉树的算法    197
7.3.1  要点归纳    197
7.3.2  例题解析    207
7.4  知识点4：线索二叉树    232
7.4.1  要点归纳    232
7.4.2  例题解析    236
7.5  知识点5：哈夫曼树    239
7.5.1  要点归纳    239
7.5.2  例题解析    241
第8章  广义表    245
8.1  知识点1：广义表的基本概念    245
8.1.1  要点归纳    245
8.1.2  例题解析    246
8.2  知识点2：广义表的第一种存储结构    248
8.2.1  要点归纳    248
8.2.2  例题解析    254
8.3  知识点3：广义表的第二种存储结构    261
8.3.1  要点归纳    261
8.3.2  例题解析    266
第9章  图    272
9.1  知识点1：图的基本概念    272
9.1.1  要点归纳    272
9.1.2  例题解析    276
9.2  知识点2：图的遍历算法    285
9.2.1  要点归纳    285
9.2.2  例题解析    287
9.3  知识点3：最小生成树    300
9.3.1  要点归纳    300
9.3.2  例题解析    304
9.4  知识点4：最短路径    311
9.4.1  要点归纳    311
9.4.2  例题解析    316
9.5  知识点5：AOV网和拓扑排序    322
9.5.1  要点归纳    322
9.5.2  例题解析    323
9.6  知识点6：AOE网与关键路径    329
9.6.1  要点归纳    329
9.6.2  例题解析    331
第10章  查找    336
10.1  知识点1：线性表的查找    336
10.1.1  要点归纳    336
10.1.2  例题解析    340
10.2  知识点2：树表的查找    346
10.2.1  要点归纳    346
10.2.2  例题解析    355
10.3  知识点3：哈希表的查找    373
10.3.1  要点归纳    373
10.3.2  例题解析    376
第11章  内排序    393
11.1  知识点1：插入排序算法    393
11.1.1  要点归纳    393
11.1.2  例题解析    395
11.2  知识点2：选择排序算法    399
11.2.1  要点归纳    399
11.2.2  例题解析    402
11.3  知识点3：交换排序算法    409
11.3.1  要点归纳    409
11.3.2  例题解析    411
11.4  知识点4：归并排序算法    419
11.4.1  要点归纳    419
11.4.2  例题解析    421
11.5  知识点5：基数排序算法    423
11.5.1  要点归纳    423
11.5.2  例题解析    424
第12章  外排序和文件    429
12.1  知识点1：外排序    429
12.1.1  要点归纳    429
12.1.2  例题解析    431
12.2  知识点2：文件    435
12.2.1  要点归纳    435
12.2.2  例题解析    438
附录A  一份重点大学本科“数据结构”课程考试试题    444
附录B  一份重点大学本科“数据结构”课程考试试题    451
附录C  一份重点大学考研“数据结构”考试试题    458
附录D  一份重点大学考研“数据结构”考试试题    463