《全国硕士研究生入学统一考试计算机学科专业基础综合（2010年版）》是专门针对计算机专业研究生入学考试的特点和需求量身打造的，书中融合了编者多年的教学辅导经验，完全针对考研大纲的要求，知识点覆盖全面，文字通俗易懂，简洁精炼，是複习备考不可缺少的学习资料。从去年全国计算机专业课统考以来，市面上出现了一些有关专业课统考的複习用书，但并非特别适合考生使用，大部分辅导用书由于编写时间极短，覆盖知识点不全，难易程度控制不到位，不仅没能起到总结归纳的作用，反而浪费考生的複习时间，影响複习效果

本书在编写过程中，注重吸取目前市面上专业複习用书出现的一些问题，特别针对当前国内大学生学习水平和複习时间，给出考生複习计算机专业课的目标、考点精解、例题精析和习题、参考答案等。使得本书无论是在知识面的覆盖上，还是在题目的难易程度上都儘量与考试一致。使考生高效率的複习知识点，提高对知识的认识水平，总结和归纳套用技巧。因此，学生完全可以放心选择本书作为计算机专业的複习全书

第1部分数据结构

第1章线性表············································2

1.1複习提示··················································2

1.1.1複习目标和要求·································2

1.1.2命题方向提示·····································3

1.2知识点精讲···············································3

1.2.1数据结构的基本概念和线性结构······3

1.2.2顺序表的类型和定义·························3

1.2.3线性表的顺序表示和实现··················4

1.2.4线性表的链式表示和实现··················6

1.2.5递归概念及算法实现·························8

1.3例题精析··················································8

1.4习题························································15

1.5习题解答················································18

第2章栈、伫列和数组·····························21

2.1複习提示················································21

2.1.1複习目标和要求·······························21

2.1.2命题方向提示···································22

2.2知识点精讲·············································22

2.2.1栈和伫列的基本概念·······················22

2.2.2顺序栈和链栈及其套用···················23

2.2.3链队、顺序队和循环伫列················27

2.2.4对称矩阵···········································29

2.2.5特殊矩阵的压缩存储·······················29

2.3例题精析················································31

2.4习题························································37

2.5习题答案················································40

第3章树与二叉树····································45

3.1複习提示················································45

3.1.1複习目标和要求·······························45

3.1.2命题方向提示···································46

3.2知识点精讲·············································46

3.2.1树和二叉树的定义和主要特徵········46

3.2.2二叉树的顺序存储结构

和链式存储结构································48

3.2.3二叉树的遍历····································49

3.2.4线索二叉树的基本概念和构造········50

3.2.5排序二叉树和平衡二叉树················53

3.2.6树的存储结构和森林························53

3.2.7树和森林的遍历································55

3.2.8树的套用：哈夫曼树

和哈夫曼编码···································56

3.3例题精析················································58

3.4习题························································65

3.5习题答案················································69

第4章图···················································78

4.1複习提示················································78

4.1.1複习目标和要求································78

4.1.2命题方向提示····································79

4.2知识点精讲············································79

4.2.1图的概念和基本术语························79

4.2.2图的存储结构和操作························80

4.2.3图的遍历············································82

4.2.4最小生成树和生成森林····················83

4.2.5最短路径············································84

4.2.6拓扑排序············································85

4.2.7关键路径············································86

4.3例题精析················································87

4.4习题························································93

4.5习题答案················································96

第5章查找·············································100

5.1複习提示···············································100

5.1.1複习目标和要求······························100

5.1.2命题方向提示··································101

5.2知识点精讲···········································101

目录

VI

5.2.1查找的基本概念·····························101

5.2.2顺序查找法·····································102

5.2.3折半查找法·····································103

5.2.4动态查找法·····································103

5.2.5B-树和B+树···································106

5.2.6哈希表·············································107

5.3例题精析··············································110

5.4习题······················································114

5.5习题答案··············································116

第6章内部排序······································120

6.1複习提示··············································120

6.1.1複习目标和要求·····························120

6.1.2命题方向提示·································121

6.2知识点精讲···········································121

6.2.1排序的基本概念······························121

6.2.2插入排序··········································122

6.2.3交换排序··········································123

6.2.4选择排序··········································124

6.2.5归併排序··········································127

6.2.6基数排序··········································128

6.2.7对各种排序算法的比较··················129

6.3例题精析···············································130

6.4习题·······················································133

6.5习题答案···············································137