严蔚敏《数据结构》考研名校真题解析及典型题精讲精练

《严蔚敏《数据结构》考研名校真题解析及典型题精讲精练》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录第一章绪论!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（１）第二章线性表!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（６）第三章栈和队列!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（１１）第四章串!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（１５）第五章数组和广义表!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（１８）第六章树与二叉树!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（２０）第七章图!!!!!

2、!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（２５）第八章查找!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（３０）第九章内部排序!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（３３）严蔚敏《数据结构》名校真题解析及典型题精讲精练第一章绪论一、知识点概要基本概念：数据、数据对象、数据结构、数据类型；数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和

3、处理。有时，一个数据元素由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构（ＤａｔａＳｔｒｕｃｔｕｒｅ）定义：数据结构是指相互之间存在一种或多种特定关系的数据元素集合。数据元素不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Ｓｔｒｕｃｔｕｒｅ）。根据数据元素之间的不同特性，通常有下列４类基本结构：（１）集合（２）线性结构（３）树状结构（４）图状结构或网状结构数据结构的形式定义：数据结构是一个二元组Ｄａｔａ＿Ｓｔｒｕｃｔｕｒｅ＝（Ｄ，Ｓ

4、）其中：Ｄ是数据元素的有限集，Ｓ是Ｄ上关系的有限集。数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构线性结构———线性表、栈、队、字符串数组、广义表逻辑结构{图非线性结构———树、—１—考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课程电话：４００６８８５３６５数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。

5、由此得出两种不同的存储结构：顺序存储结构和链式存储结构。数据结构的三个组成部分：逻辑结构：数据元素之间逻辑关系的描述Ｄ＿Ｓ＝（Ｄ，Ｓ）存储结构：又称物理结构，是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。数据操作：对数据要进行的运算。数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。抽象数据类型（ＡｂｓｔｒａｃｔＤａｔａＴｙｐｅ，简称ＡＤＴ）：是指一个数学模型以及定义在该模型上的一组操作。ＡＤＴ的形式化定义是三元组：ＡＤＴ＝（Ｄ，Ｓ，Ｐ）其中：Ｄ是数据对象，Ｓ是Ｄ上的

6、关系集，Ｐ是对Ｄ的基本操作集。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法的特性１．有穷性：有限步骤之内正常结束，不能形成无穷循环２．确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。３．可行性：一个算法是能行的，即算法中描述的操作都是可以执行有限次来实现。４．输入：有多个或０个输入，这些输入取自于某个特定的对象的集合。５．输出：至少有一个或多个输出。算法设计的要求１．正确性（Ｃｏｒｒｅｃｔｎｅｓｓ）：算法应满足具体问题的需求。２．可读性（Ｒｅａｄａｂｉｌｉｔｙ）：算法应容

7、易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。３．健壮性（Ｒｏｂｕｓｔｎｅｓｓ）：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。４．通用性（Ｇｅｎｅｒａｌｉｔｙ）：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。５．效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。“正确”分４个层次：１．程序不含语法错误；２．程序对于几组输入数据能够得出满足规格说明要求的结果；３．程序对于精

8、心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；—２—严蔚敏《数据结构》名校真题解析及典型题精讲精练４．程序对于一切合法的输入数据都能产生满足规格说明要求的结果。通常以第３层意义的正确性作为衡量一个程序是否