目  录 

 第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  循环链表算法设计 104

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.3  B树和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

 附录A   算法索引 443