严蔚敏《数据结构》（第2版）笔记和习题（含考研真题）详解
内容简介
本书特别适用于参加研究生入学考试指定考研参考书目为严蔚敏《数据结构》的考生，也可供各大院校学习严蔚敏《数据结构》的师生参考。
我国各大院校一般都把国内外通用的权威教科书作为本科生和研究生学习专业课程的参考教材，这些教材甚至被很多考试（特别是硕士和博士入学考试）和培训项目作为指定参考书。为了帮助读者更好地学习专业课，我们有针对性地编著了一套与国内外教材配套的复习资料，并提供配套的名师讲堂和题库。
严蔚敏所著的《数据结构》（第2版，清华大学出版社）是我国高校采用较多的计算机专业优秀教材，也被众多高校指定为计算机专业考研参考书目。
作为该教材的辅导书，本书具有以下几个方面的特点：
1．整理名校笔记，浓缩内容精华。在参考了国内外名校名师讲授严蔚敏《数据结构》的课堂笔记基础上，本书每章的复习笔记部分对该章的重难点进行了整理，同时对重要知识点进行点拨，因此，本书的内容几乎浓缩了配套教材的知识精华。
2．归纳典型题，强化知识考点。为了进一步巩固和强化各章知识难点的复习，特针对该教材的重难点相应整理了典型强化习题，并对相关知识点进行归纳和延伸，梳理知识点逻辑关系，以达到高效复习的目的。
3．精选考研真题，巩固重难点知识。为了强化对重要知识点的理解，本书精选了部分名校近几年的数据结构考研真题，这些高校大部分以该教材作为考研参考书目。所选考研真题基本涵盖了各个章节的考点和难点，特别注重联系实际，凸显当前热点。
要深深牢记：考研不同一般考试，概念题（名词解释）要当作简答题来回答，简答题要当作论述题来解答，而论述题的答案要像是论文，多答不扣分。有的论述题的答案简直就是一份优秀的论文（其实很多考研真题就是选自一篇专题论文），完全需要当作论文来回答！
目录
内容简介
第1章 绪 论
1.1 复习笔记
（1）数据结构的基本结构
根据数据元素之间关系的不同特性，通常有下列四类基本结构：
②线性结构。数据元素之间存在一个对一个的关系。
③树形结构。数据元素之间存在一个对多个的关系。
④图状结构或网状结构。数据元素之间存在多个对多个的关系。
如图1-1所示为上述四类基本结构的关系图。
（2）数据结构的形式定义
（3）数据结构在计算机中的表示
数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。
①元素的表示。计算机数据元素用一个由若干位组合起来形成的一个位串表示。
②关系的表示。计算机中数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象。并由这两种不同的表示方法得到两种不同的存储结构：顺序存储结构和链式存储结构。
a．顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
与数据结构密切相关的是定义在数据结构上的一组操作。操作的种类和数目不同，即使逻辑结构相同，这个数据结构的用途也会大为不同。操作的种类是没有限制的，可以根据需要而定义。基本的操作主要有以下几种（可简单记做增、删、改、查、排）：
（1）插入
在数据结构中的指定位置上增添新的数据元素。
（2）删除
删去数据结构中某个指定的数据元素。
（3）更新
改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。
（4）查找
在数据结构中寻找满足某个特定要求的数据元素（的位置和值）。
（5）排序
（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或由大到小的次序排列。
（1）有穷性
一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
（2）确定性
算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得到相同的输出。
（3）可行性
一个算法是可行的，即算法中描述的操作都是可以通过执行有限次已经实现的基本运算来实现的。
（4）输入
一个算法有零个或多个的输入。这些输入取自于特定的对象的集合。
（5）输出
一个算法有一个或多个的输出。这些输出是同输入有某个特定关系的量。
数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新的趋势，越来越被人们所重视。
算法需要用一种语言来描述，同时，算法可有各种描述方法以满足不同的需求。例如，一个需在计算机上运行的程序（程序也是算法）必须是严格按照语法规定用机器语言、汇编语言或高级程序语言编写的，而一个为了人的阅读和交流的算法可以用伪码语言或框图等其它形式来描述。
正确性是指设计或选择的算法应当能正确地反映某种需求，否则，算法正确与否的衡量准则就不存在了。“正确”一词的含义大体可分为以下四个层次：
①程序不含语法错误。
②程序对于几组输入数据能够得出满足规格说明要求的结果。
③程序对于精心选择的、典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。
④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
可读性算法首先是方便人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解，因为晦涩难懂的程序易于隐藏较多错误从而难以调试和修改。
健壮性是指当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。
（4）效率与低存储量需求
效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。
算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量，度量一个程序的执行时间通常有两种方法：
（1）事后统计
很多计算机内部都有计时功能，有的甚至可精确到毫秒级，因此采用不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。
但这种方法有两个缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。
（2）事前分析估算
①消耗时间的因素
一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
a．程序依据的算法选用的策略。
b．问题的规模。
c．书写程序的语言。
d．编译程序所产生的机器代码的质量。
e．机器执行指令的速度。
显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同，这表明使用绝对的时间单位衡量算法的效率是不合适的。
②时间复杂度
4．算法的存储空间需求
1.2 强化习题详解
1.3 考研真题与典型题详解
①事后统计。利用计算机内的计时功能，采用不同算法的程序可以用一组或多组相同的统计数据区分。其缺点，一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。
②事前分析估计。一个高级语言程序在计算机上运行所消耗的时间。其运行消耗的时间取决于：依据的算法选用何种策略、问题的规模、程序语言、编译程序产生机器代码质量、机器执行指令速度。
第2章 线性表
2.1 复习笔记
2.2 强化习题详解
2.3 考研真题与典型题详解
第3章 栈和队列
3.1 复习笔记
3.2 强化习题详解
10．试将下列递归过程改写为非递归过程。
void test（int &sum）
{
intx;
scanf（x）;
if（x==0）sum=0;
else
{
test（sum）;
sum+=x;
}
printf（sum）;
}
11．简述队列和栈这两种数据类型的相同点和差异处。
12．写出以下程序段的输出结果（队列中的元素类型QElemType为char）。
voidmain（）
{
QueueQ;
InitQueue（Q）;
charx = 'e'
EnQueue（Q
EnQueue（Q
EnQueue（Q
DeQueue（Q
EnQueue（Q
DeQueue（Q
EnQueue（Q
While（!QueueEmpty（Q））
{
DeQueue（Q
printf（y）;
}
printf（x）;
}
char（根据队列先进先出的操作特点，按照入队和出队顺序依次写出元素即可。）
13．简述以下算法的功能（栈和队列的元素类型均为int）。
void algo3（Queue&Q）
{
StackS;
intd;
InitStack（S）;
while（!QueueEmpty（Q））
{
DeQueue（Q
Push（S
}
while（!StackEmpty（S））
{
Pop（S
EnQueue（Q
}
}
14．若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。
答：（1）4132
（2）4213
（3）4231
15．假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack（tws）、入栈push（tws
答：
答：
答：
答：
答：
答：
答：
答：
答：
答：
答：
答：
答：
答：
答：设head指示循环队列中队头元素元素的位置，则有
head=（（q.rear+MAXLEN）-q.length+1）%MAXLEN
其中MAXLEN为队列可用的最大空间。
答：
答：
答：
答：
3.3 考研真题与典型题详解
第4章 串
4.1 复习笔记
4.2 强化习题详解
4.3 考研真题与典型题详解
第5章 数组和广义表
5.1 复习笔记
5.2 强化习题详解
5.3 考研真题与典型题详解
第6章 树和二叉树
6.1 复习笔记
6.2 强化习题详解
6.3 考研真题与典型题详解
第7章 图
7.1 复习笔记
7.2 强化习题详解
7.3 考研真题与典型题详解
第8章 动态存储管理
8.1 复习笔记
8.2 强化习题详解
8.3 考研真题与典型题详解
第9章 查 找
9.1 复习笔记
9.2 强化习题详解
9.3 考研真题与典型题详解
第10章 内部排序
10.1 复习笔记
10.2 强化习题详解
10.3 考研真题与典型题详解
第11章 外部排序
11.1 复习笔记
11.2 强化习题详解
11.3 考研真题与典型题详解
第12章 文 件
12.1 复习笔记
12.2 强化习题详解
12.3 考研真题与典型题详解