本书汇集国内外众多著名IT企业近几年的数据结构面试笔试真题并予以解析，按知识点类型对常见的数据结构难点和疑点进行了系统归纳和透彻剖析，并提供了一定数量的自测题以便于读者自我检验。 　全书逻辑清晰、通俗易懂，适合参加IT企业校园招聘和面试笔试环节的同学复习，也适合数据结构和算法设计编程爱好者以及在校学生阅读和提高。

目 录

第1章 数据结构基础 1

常见考点 1

1.1 数据结构的概念 1

1.1.1 要点归纳 1

1.1.2 面试题解析 2

1.2 算法描述和分析 5

1.2.1 要点归纳 5

1.2.2 面试题解析 6

1.3 算法设计手段——递归 8

1.3.1 要点归纳 8

1.3.2 面试题解析 16

1.4 自测题和参考答案 31

1.4.1 自测题 31

1.4.2 参考答案 33

第2章 线性表Ⅰ——数组 36

常见考点 36

2.1 线性表顺序存储结构 36

2.1.1 要点归纳 36

2.1.2 面试题解析 38

2.2 数组的基本算法设计 39

2.2.1 要点归纳 39

2.2.2 面试题解析 45

2.3 有序数组的算法设计 55

2.3.1 要点归纳 55

2.3.2 面试题解析 59

2.4 多维数组 63

2.4.1 要点归纳 63

2.4.2 面试题解析 64

2.5 自测题和参考答案 70

2.5.1 自测题 70

2.5.2 参考答案 71

第3章 线性表Ⅱ——链表 77

常见考点 77

3.1 线性表链式存储结构概述 77

3.1.1 要点归纳 77

3.1.2 面试题解析 78

3.2 单链表算法设计 79

3.2.1 要点归纳 79

3.2.2 面试题解析 82

3.3 双链表算法设计 101

3.3.1 要点归纳 101

3.3.2 面试题解析 101

3.4 循环.. [1]

3.4.1要点归纳 104

3.4.2面试题解析 104

3.5自测题和参考答案 113

3.5.1自测题 113

3.5.2参考答案 114

第4章字符串 121

常见考点 121

4.1字符串基础 121

4.1.1要点归纳 121

4.1.2面试题解析 122

4.2字符串匹配算法设计 133

4.2.1要点归纳 133

4.2.2面试题解析 135

4.3自测题和参考答案 146

4.3.1自测题 146

4.3.2参考答案 147

第5章栈 149

常见考点 149

5.1栈基本算法设计 149

5.1.1要点归纳 149

5.1.2面试题解析 151

5.2栈应用算法设计 155

5.2.1要点归纳 155

5.2.2面试题解析 156

5.3自测题和参考答案 179

5.3.1自测题 179

5.3.2参考答案 180

第6章队列 184

常见考点 184

6.1队列基本算法设计 184

6.1.1要点归纳 184

6.1.2面试题解析 186

6.2队列应用算法设计 189

6.2.1要点归纳 189

6.2.2面试题解析 191

6.3自测题和参考答案 201

6.3.1自测题 201

6.3.2参考答案 202

第7章树和二叉树 205

常见考点 205

7.1树 205

7.1.1要点归纳 205

7.1.2面试题解析 208

7.2二叉树概念 210

7.2.1要点归纳 210

7.2.2面试题解析 212

7.3二叉树遍历及算法设计 216

7.3.1要点归纳 216

7.3.2面试题解析 223

7.4哈夫曼树 262

7.4.1要点归纳 262

7.4.2面试题解析 263

7.5自测题和参考答案 265

7.5.1自测题 265

7.5.2参考答案 267

第8章图 274

常见考点 274

8.1图的概念和存储结构 274

8.1.1要点归纳 274

8.1.2面试题解析 277

8.2图的遍历算法及其应用 280

8.2.1要点归纳 280

8.2.2面试题解析 286

8.3图的应用 302

8.3.1要点归纳 302

8.3.2面试题解析 304

8.4自测题和参考答案 340

8.4.1自测题 340

8.4.2参考答案 344

第9章查找 352

常见考点 352

9.1顺序表的查找 352

9.1.1要点归纳 352

9.1.2面试题解析 354

9.2二叉排序树和平衡二叉树 366

9.2.1要点归纳 366

9.2.2面试题解析 367

9.3B树和B+树 381

9.3.1要点归纳 381

9.3.2面试题解析 382

9.4哈希表查找 382

9.4.1要点归纳 382

9.4.2面试题解析 386

9.5自测题和参考答案 393

9.5.1自测题 393

9.5.2参考答案 395

第10章排序 399

常见考点 399

10.1插入排序 399

10.1.1要点归纳 399

10.1.2面试题解析 402

10.2交换排序 404

10.2.1要点归纳 404

10.2.2面试题解析 406

10.3选择排序 416

10.3.1要点归纳 416

10.3.2面试题解析 418

10.4归并排序 423

10.4.1要点归纳 423

10.4.2面试题解析 424

10.5基数排序和桶排序 429

10.5.1要点归纳 429

10.5.2面试题解析 431

10.6外排序 435

10.6.1要点归纳 435

10.6.2面试题解析 436

10.7自测题和参考答案 437

10.7.1自测题 437

10.7.2参考答案 438

10.8.1详细解析

附录A算法索引 443