数据结构常见题型解析及模拟题

1 数据结构与算法基本概念 1

1．1 重点与难点 1

1．1．1 什么是数据结构 1

1．1．2 算法的概念及特性 1

1．1．3 数据结构与算法的关系 2

1．1．4 算法的描述和分析 2

1．2 例题精选 3

1．3 习题与思考题 6

2 线性表 8

2．1 重点与难点 8

2．1．1 线性表结构的基本概念 8

2．1．2 顺序表上基本操作的描述及实现 9

2．1．3 链式表上基本操作的描述及实现 10

2．1．4 多项式相加与相乘 12

2．2 例题精选 12

2．3 习题与思考题 16

3 栈与队列结构 18

3．1 重点与难点 18

3．1．1 栈结构的基本概念 18

3．1．2 栈的应用 19

3．1．3 栈与递归 19

3．1．4 队列结构的基本概念 20

3．2 例题精选 22

3．3 习题与思考题 26

4 串与模式匹配 28

4．1 重点与难点 28

4．1．1 串的基本概念和存储结构 28

4．1．2 串的基本运算 29

4．1．3 模式匹配 29

4．2 例题精选 32

4．3 习题与思考题 35

5 数组结构与压缩存储 36

5．1 重点与难点 36

5．1．1 数组结构的基本概念 36

5．1．2 数组的存储结构 37

5．1．3 矩阵的压缩存储 37

5．1．4 三维图形信息的压缩存储 39

5．2 例题精选 41

5．3 习题与思考题 45

6 树与二叉树 46

6．1 重点与难点 46

6．1．1 树的基本概念 46

6．1．2 二叉树的基本概念及性质 47

6．1．3 二叉树的遍历 49

6．1．4 线索二叉树 50

6．1．5 二叉树的应用 52

6．1．6 计算二叉树的数目 54

6．2 例题精选 55

6．3 习题与思考题 60

7 图结构及应用算法 63

7．1 重点与难点 63

7．1．1 图结构的基本概念 63

7．1．2 图的遍历算法实现 65

7．1．3 生成树 67

7．1．4 最短路径 68

7．1．5 拓扑排序和关键路径 70

7．2 例题精选 73

7．3 习题与思考题 80

8 列表结构及遍历算法 81

8．1 重点与难点 81

8．1．1 列表结构的基本概念 81

8．1．2 列表存储结构 82

8．1．3 列表的遍历算法 84

8．2 例题精选 86

8．3 习题与思考题 90

9 查找 91

9．1 重点与难点 91

9．1．1 顺序表的查找 91

9．1．2 树表的查找 93

9．1．3 哈希表及其查找 95

9．2 例题精选 98

9．3 习题与思考题 103

10 内排序 104

10．1 重点与难点 104

10．1．1 排序的基本概念 104

10．1．2 插入排序法 105

10．1．3 选择排序法 105

10．1．4 交换排序法 107

10．1．5 归并排序法 108

10．1．6 基数排序法 109

10．1．7 内排序法的比较和选择 109

10．2 例题精选 111

10．3 习题与思考题 119

11 外部排序 120

11．1 重点与难点 120

11．1．1 外存设备 120

11．1．2 外排序的基本方法 120

11．1．3 多路平衡归并与败方树 121

11．1．4 置换选择排序——形成初始归并段 123

11．1．5 最佳归并树 123

11．2 例题精选 124

11．3 习题与思考题 126

12 文件 128

12．1 重点与难点 128

12．1．1 文件结构的基本概念 128

12．1．2 顺序文件 129

12．1．3 索引文件 129

12．1．4 索引顺序文件 129

12．1．5 散列文件 129

12．1．6 多关键字文件 130

12．2 例题精选 130

12．3 习题与思考题 133

附录 134

1 1996年西安交通大学硕士研究生入学考试试题 134

2 1996年西安电子科技大学硕士研究生入学考试试题 138

3 1997年北京某计算研究所硕士研究生入学考试试题 140

4 1998年西北工业大学硕士研究生入学考试试题 142

5 1998年西安电子科技大学硕士研究生入学考试试题 143

6 数据结构硕士研究生入学考试模拟试题Ⅰ 145

参考答案 148

7 数据结构硕士研究生入学考试模拟试题 152

参考答案 154

各章习题与思考题参考解答 158

参考文献 186