本书是清华大学计算机系列教材《数据结构（用面向对象方法与C++描述）》（第2版）的配套用书。本书针对主教材各个章节精选的习题，给出了参考答案；对部分习题提供了多种可能的解答，以帮助学生以不同的思路来解决问题。

本书章节的编排与主教材的章节严格对应。每一章在开始部分提示本章的複习要点，总结主要的知识点；第二部分说明其重点和难点，以引起学习者的注意；在第三部分给出本章习题的参考答案；在第四部分进一步扩展开来，针对将来工作中可能涉及的知识，兼顾考硕、考博，补充了大批练习。

书中内容涵盖了硕士研究生入学（全国联考）考试大纲的各个知识单元，针对考试的题型，增加了大量选择题和套用题，包括算法题。所有的习题都经过精心挑选和精心解答。

本书适合本科在校学生作为学习数据结构课程的参考书使用，也可以作为考研学生的複习教材。此外，对于从事计算机软体研发的人员也有参考价值。

第1章绪论1

1.1複习要点1

1.2难点与重点2

1.3教材习题解析2

1.4补充练习题18

1.5补充练习题参考答案21

第2章线性表23

2.1複习要点23

2.2难点与重点24

2.3教材习题解析25

2.4补充练习题46

2.5补充练习题参考答案49

第3章栈和伫列53

3.1複习要点53

3.2难点和重点54

3.3教材习题解析56

3.4补充练习题88

3.5补充练习题参考答案94

第4章数组、串和广义表102

4.1複习要点102

4.2难点与重点103

4.3教材习题解析105

4.4补充练习题117

4.5补充练习题参考答案122

第5章树与森林138

5.1複习要点138

5.2难点与重点139

5.3教材习题解析142

5.4补充练习题172

5.5补充练习题参考答案181第6章集合与字典209

6.1複习要点209

6.2难点和重点211

6.3教材习题解析212

6.4补充练习题230

6.5补充练习题参考答案235

第7章搜寻结构252

7.1複习要点252

7.2难点和重点256

7.3教材习题解析257

7.4补充练习题280

7.5补充练习参考答案284

第8章图296

8.1複习要点296

8.2难点和重点297

8.3教材习题解析299

8.4补充练习题329

8.5补充练习题参考答案342

第9章排序371

9.1複习要点371

9.2难点和重点374

9.3教材习题解析376

9.4补充练习题399

9.5补充练习题参考答案404

第10章档案、外部排序与搜寻418

10.1複习要点418

10.2难点与重点421

10.3教材习题解析423

10.4补充练习题439

10.5补充练习题参考答案449

第1章引论1

1.1计算机网路的产生和发展1

1.1.1历史的回顾1

1.1.2推动计算机网路发展的两大动力3

1.1.3区域网路的产生和发展4

1.2资源共享6

1.2.1资源分配和共享6

1.2.2资源共享定理6

1.3计算机网路分类7

1.4计算机网路技术基本内容8

1.5计算机网路发展趋势9

1.6本章小结12

第2章数据通信14

2.1时域和频域概念14

2.1.1时域概念14

2.1.2频域概念16

2.1.3数据率和频带的关係17

2.1.4数据率的限制19

2.1.5几个重要的信号传输度量19

2.2数据调製与编码20

2.2.1模拟数据的模拟信号调製22

2.2.2数字数据的模拟信号调製23

2.2.3数字数据的数位讯号编码25

2.2.4模拟数据的数位讯号编码27

2.3多路复用28

2.3.1多路复用技术28

2.3.2频分多路复用29

2.3.3时分多路复用29

2.3.4统计时分多路复用32

2.3.5波分多路复用33

2.3.6码分多路复用34

2.4异步传输和同步传输37

2.5铜环接入技术38

2.5.1铜环接入类别38

2.5.2ADSL调製技术42

2.6电缆调製器43

2.6.1混合光纤同轴电缆43

2.6.2DOCSIS协定44

2.7数据交换45

2.7.1线路交换45

2.7.2分组交换45

2.7.3帧中继交换49

2.7.4信元交换50

2.8本章小结52

第3章传输介质与拓扑结构54

3.1传输介质特性54

3.2传输介质类别54

3.3传输损耗56

3.4拓扑结构的选择58

3.5拓扑结构类别58

3.6环型网63

3.7汇流排/树型网路64

3.7.1基带系统65

3.7.2宽频系统66

3.7.3基带系统和宽频系统的比较68

3.8光纤区域网路68

3.8.1无源星型结构69

3.8.2有源星型结构69

3.8.3光纤环网结构70

3.8.4光纤汇流排网结构70

3.9本章小结71

第4章区域网路协定73

4.1LAN参考模型73

4.2数据链路控制77

4.2.1流控技术77

4.2.2差错检测80

4.2.3差错控制83

4.3逻辑链路控制协定85

4.3.1网路层/LLC子层界面服务规範85

4.3.2LLC子层/MAC子层界面服务规範87

4.3.3LLC协定数据单元结构87

4.3.4LLC协定的型和类88

4.3.5LLC协定的元素88

4.4介质访问控制90

4.5争用协定92

4.5.1载波监听多路访问92

4.5.2载波监听多路访问/冲突检测93

4.5.3退避算法94

4.6标记环介质访问控制95

4.7光纤分布数据接口介质访问控制96

4.7.1FDDI原理96

4.7.2FDDI系列97

4.7.3FDDI协定98

4.8区域网路协定标準100

4.9本章小结102

第5章乙太网103

5.1传统乙太网104

5.1.1MAC子层104

5.1.2物理层105

5.1.3物理层实施105

5.1.4桥接乙太网107

5.1.5交换式乙太网107

5.1.6全双工乙太网107

5.2交换式区域网路108

5.2.1交换式区域网路的基本模组108

5.2.2LAN交换器的特点109

5.2.3两种交换方式110

5.2.4第三层交换器111

5.3快速乙太网112

5.3.1MAC子层113

5.3.2物理层113

5.3.3物理层实施114

5.4千兆位乙太网117

5.4.1乙太网的进展117

5.4.2MAC子层119

5.4.3物理层119

5.4.4物理层实施119

5.4.5千兆位乙太网的套用122

5.5虚拟区域网路工作原理127

5.6网路互连方式129

5.6.1中继器互连方式129

5.6.2网桥互连方式130

5.6.3路由器互连方式131

5.6.4网路互连方式的对比132

5.7本章小结133

第6章无线区域网路134

6.1IEEE802.11体系结构134

6.2IEEE802.11物理层134

6.3IEEE802.11MAC135

6.3.1协定结构135

6.3.2帧结构138

6.4IEEE802.11地址机制138

6.5蓝牙体系结构139

6.6蓝牙层结构139

6.6.1无线电层139

6.6.2基带层140

6.6.3L2CAP层141

6.7本章小结141

第7章Internet模型142

7.1OSI模型简述142

7.1.1分层结构142

7.1.2基本构造技术144

7.2TCP/IP体系结构144

7.2.1TCP/IP分层模型144

7.2.2TCP/IP和OSI的对应关係146

7.3Internet模型各层职责147

7.3.1物理层职责147

7.3.2数据链路层职责148

7.3.3网路层职责148

7.3.4传输层职责149

7.3.5套用层职责149

7.4Internet模型的实现机制150

7.4.1物理层151

7.4.2数据链路层152

7.4.3网路层153

7.4.4传输层154

7.4.5套用层155

7.5本章小结156

第8章网路层158

8.1网路层职责158

8.1.1网路互连要求158

8.1.2网路层职责159

8.2网间协定IP159

8.2.1InternetIP设计原则159

8.2.2Internet体系结构160

8.2.3IP数据报161

8.2.4IP数据报选项162

8.2.5IP操作163

8.2.6无连线互连网路的设计163

8.3Internet地址166

8.3.1Internet地址结构166

8.3.2Internet地址映射168

8.3.3子网划分170

8.3.4无类别域间路由选择172

8.3.5网路地址转换173

8.4Internet地址空间的扩展174

8.4.1IP的更新174

8.4.2IPv6数据报格式175

8.4.3IPv6地址空间176

8.4.4IPv4过渡到IPv6177

8.5Internet控制报文协定ICMP178

8.5.1ICMP机制178

8.5.2ICMP报文格式179

8.6路由器体系结构180

8.6.1核心路由器体系结构180

8.6.2自治系统181

8.7IP数据报的路由选择182

8.7.1IP数据报的直接传送和间接传送182

8.7.2IP路由选择表与算法182

8.7.3距离矢量路由选择184

8.7.4链路状态路由选择184

8.8内部网关协定184

8.8.1路由选择信息协定185

8.8.2开放最短路径优先协定187

8.9外部网关协定189

8.10边界网关协定192

8.11本章小结193

第9章传输层195

9.1传输层服务和协定要素195

9.1.1网路层、传输层、套用层提供服务的关係195

9.1.2传送服务原语196

9.1.3传输层协定机制197

9.2用户数据报协定203

9.2.1UDP协定功能204

9.2.2UDP报文格式204

9.2.3UDP的协定分层与封装205

9.2.4UDP的复用、分解与连线埠205

9.2.5远程过程调用206

9.2.6实时传输协定207

9.3可靠的数据流传输209

9.3.1可靠数据流传输服务特性209

9.3.2可靠数据流传输服务的实现209

9.4传输控制协定210

9.4.1TCP功能210

9.4.2TCP报文格式211

9.4.3TCP的操作212

9.4.4状态转换图213

9.5网路服务质量215

9.5.1流特性和改进QoS的技术216

9.5.2网路集成服务218

9.5.3网路资源预约协定218

9.5.4网路区分服务219

9.6本章小结220

第10章网路作业系统与网路计算模式222

10.1作业系统概述及其发展222

10.2网路作业系统概述及其特点223

10.2.1网路作业系统概述223

10.2.2网路作业系统的特点224

10.3网路作业系统的种类225

10.4网路计算模式的发展226

10.4.1以大型机为中心的计算模式226

10.4.2以伺服器为中心的计算模式226

10.4.3小型化和客户机/伺服器计算模式的出现227

10.5客户机/伺服器计算模式228

10.5.1客户机的特点228

10.5.2伺服器的特点229

10.5.3客户机/伺服器计算模式的特点229

10.6客户机/伺服器模式的优点231

10.7客户机/伺服器模式的中间件232

10.7.1中间件产生的背景232

10.7.2中间件的功能与作用232

10.8客户机/伺服器类型233

10.9云计算234

10.9.1云计算原理234

10.9.2“云”时代234

10.9.3云计算的几大形式235

10.9.4发展云计算的原因236

10.10本章小结237

第11章环球信息网238

11.1环球信息网的基本原理238

11.1.1环球信息网的特点238

11.1.2环球信息网的基本概念239

11.2超文本传输协定243

11.2.1HTTP工作过程243

11.2.2HTTP协定244

11.3超文本标记语言244

11.3.1HTML的基本框架245

11.3.2在HTML档案中建立连结248

11.3.3在HTML档案中使用图像250

11.3.4多视窗套用251

11.3.5表单的套用253

11.4通用资源访问地址255

11.5动态Web文档与CGI技术256

11.5.1Web文档的3种基本形式256

11.5.2动态文档的实现257

11.5.3通用网关接口257

11.6活动Web文档和Java技术258

11.6.1活动文档技术258

11.6.2Java技术258

11.7本章小结259

第12章网路管理260

12.1网路管理功能260

12.2网路管理的标準263

12.3简单网路管理协定264

12.3.1SNMP网路管理模型265

12.3.2抽象语法表示266

12.3.3管理信息结构266

12.3.4常用管理信息库268

12.3.5SNMP协定数据格式与工作模式269

12.4网路日常管理和维护271

12.4.1VLAN管理271

12.4.2WAN接入管理272

12.4.3网路故障诊断和排除273

12.4.4网路管理工具275

12.5本章小结276

第13章网路安全277

13.1密码学277

13.1.1密码学的基本原理277

13.1.2私钥密码技术278

13.1.3公钥密码技术279

13.2鉴别279

13.2.1鉴别的基本原理279

13.2.2Kerberos鉴别281

13.2.3公钥基础设施282

13.2.4数字签名283

13.3访问控制284

13.3.1访问控制的基本原理284

13.3.2虚拟专网285

13.4防病毒286

13.5网路安全技术287

13.5.1网路安全层次模型287

13.5.2防火墙技术289

13.5.3IP层安全性290

13.5.4传输层的安全性291

13.5.5套用层的安全性293

13.5.6WWW套用安全技术295

13.6安全服务与安全机制298

13.6.1安全服务298

13.6.2安全机制299

13.7信息系统安全体系结构框架300

13.8信息系统安全评估準则301

13.8.1可信计算机系统评估準则301

13.8.2计算机信息系统安全保护等级划分準则302

13.9评估增长的安全操作代价303

13.10本章小结304

参考文献306