数据结构习题解答与实验指导(第四版)

*篇  学习提要和习题解答

第 1 章  绪论.............1

1.1 重点难点指导.. 1

1.1.1  相关术语............................................ 1

1.1.2  算法的描述和分析 ............................. 3

1.2 典型例题解析.. 4

1.2.1  选择题.. 4

1.2.2  判断题.. 5

1.2.3  填空题.. 6

1.2.4  简答题.. 6

1.3 主教材习题解答............................................ 7

1.3.1  选择题.. 7

1.3.2  简答题.. 8

第 2 章  线性表....... 12

2.1 重点难点指导.12

2.1.1  相关术语...........................................12

2.1.2  线性表的顺序存储 ............................13

2.1.3  链表 ....15

2.1.4  线性表的基本运算 ............................17

2.2 典型例题解析.20

2.2.1  选择题.20

2.2.2  判断题.23

2.2.3  简答题.24

2.2.4  算法设计题 .......................................26

2.3 主教材习题解答...........................................29

2.3.1  选择题.29

2.3.2  判断题.30

2.3.3  算法设计题 .......................................31

第 3章  栈和队列.... 36

3.1 重点难点指导.36

3.1.1  相关术语...........................................36

3.1.2  栈........37

3.1.3  队列 ....39

3.1.4  栈的应用...........................................43

3.1.5  队列的应用 .......................................43

3.2 典型例题解析.44

3.2.1  选择题.44

3.2.2  填空题.45

3.2.3  简答题.46

3.2.4  算法设计题 .......................................47

3.3 主教材习题解答...........................................52

3.3.1  选择题.52

3.3.2  简答题.53

3.3.3  算法设计题 .......................................53

第 4 章  串..............56

4.1 重点难点指导.56

4.1.1  相关术语...........................................56

4.1.2  串的基本运算....................................57

4.1.3  串的存储结构....................................57

4.1.4  字符串匹配算法实现.........................59

4.2 典型例题解析.60

4.2.1  选择题.60

4.2.2  填空题.60

4.2.3  基本运算题 .......................................61

4.2.4  算法设计题 .......................................61

4.3 主教材习题解答...........................................64

4.3.1  选择题.64

4.3.2  算法设计题 .......................................65

第 5章  数组和广义表...........................................67

5.1 重点难点指导.67

5.1.1  相关术语...........................................67

5.1.2  多维数组...........................................68

5.1.3  特殊矩阵...........................................68

5.1.4  稀疏矩阵...........................................70

5.1.5  广义表.72

5.2 典型例题解析.74

5.2.1  选择题.74

5.2.2  填空题.75

5.2.3  简答题.76

5.2.4  算法设计题 .......................................77

5.3 主教材习题解答...........................................81

5.3.1  选择题.81

5.3.2  简答题.82

5.3.3  算法设计题 .......................................84

第 6 章  二叉树....... 87

6.1 重点难点指导.87

6.1.1  相关术语...........................................87

6.1.2  二叉树的存储结构 ............................89

6.1.3  二叉树的遍历运算 ............................90

6.1.4  二叉树的基本应用 ............................91

6.2 典型例题解析.92

6.2.1  选择题.92

6.2.2  判断题.93

6.2.3  填空题.94

6.2.4  简答题.95

6.2.5  算法设计题 .......................................97

6.3 主教材习题解答.........................................101

6.3.1  选择题.............................................101

6.3.2  简答题.............................................103

6.3.3  算法设计题 .....................................104

第 7章  树与森林.. 108

7.1 重点难点指导.............................................108

7.1.1  相关术语.........................................108

7.1.2  树的存储结构..................................109

7.1.3  树的基本运算..................................110

7.1.4  树、森林和二叉树的相互转换........ 111

7.2 典型例题解析.............................................111

7.2.1  选择题............................................. 111

7.2.2  判断题.............................................112

7.2.3  填空题.............................................113

7.2.4  简答题.............................................113

7.2.5  算法设计题 .....................................114

7.3 主教材习题解答.........................................116

7.3.1  选择题.............................................116

7.3.2  简答题.............................................116

7.3.3  算法设计题 .....................................118

第 8 章  图............120

8.1 重点难点指导.............................................120

8.1.1  相关术语.........................................120

8.1.2  图的基本操作..................................122

8.1.3  图的存储表示..................................122

8.1.4  图的遍历.........................................125

8.1.5  图的应用.........................................126

8.2 典型例题解析.............................................129

8.2.1  选择题.............................................129

8.2.2  判断题.............................................130

8.2.3  填空题.............................................132

8.2.4  简答题.............................................132

8.2.5  算法设计题 .....................................134

8.3 主教材习题解答.........................................139

8.3.1  选择题.............................................139

8.3.2  简答题.............................................141

8.3.3  算法设计.........................................144

第 9 章  查找.........151

9.1 重点难点指导.............................................151

9.1.1  相关术语.........................................151

9.1.2  线性表查找 .....................................152

9.1.3  排序树上的查找..............................153

9.1.4  哈希表.............................................156

9.2 典型例题解析.............................................157

9.2.1  选择题.............................................157

9.2.2  判断题.............................................158

9.2.3  简答题.............................................159

9.2.4  算法设计题 .....................................160

9.3 主教材习题解答.........................................165

9.3.1  选择题.............................................165

9.3.2  简答题.............................................166

9.3.3  算法设计题 .....................................169

第 10 章  排序....... 173

10.1 重点难点指导...........................................173

10.1.1  相关术语 .......................................173

10.1.2  插入排序 .......................................174

10.1.3  交换排序 .......................................175

10.1.4  选择排序 .......................................176

10.1.5  归并排序 .......................................177

10.1.6  基数排序 .......................................177

10.1.7  外部排序 .......................................178

10.2 典型例题解析...........................................178

10.2.1  选择题...........................................178

10.2.2  判断题...........................................179

10.2.3  填空题...........................................180

10.2.4  算法设计题 ...................................182

10.3 主教材习题解答 .......................................185

10.3.1  选择题...........................................185

10.3.2  简答题...........................................187

10.3.3  算法设计题 ...................................190

第二篇  课程实验与设计指导

第 11章  课程实验与设计的一般步骤..................194

11.1 概述............194

11.2 课程实验与设计步骤................................195

第 12章  课程实验与设计安排............................197

12.1 线性结构 ....197

实验 1   约瑟夫环问题...............................197

实验 2   一元多项式运算...........................199

实验 3   模拟停车场管理...........................201

12.2 树形结构 ....206

实验 1   哈夫曼编码/译码器......................206

实验 2   二叉树遍历...................................208

12.3 图形结构 ....208

实验 1   校园导游程序...............................208

实验 2   教学计划编排...............................210

12.4 查找和排序.210

实验 1   职工信息检索系统........................210

实验 2   各种内部排序的性能比较.............211

参考文献 ...........................212