作者：圣才电子书
出版社：圣才电子书
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
2018年数据结构考研真题与典型题详解试读：
第1章 绪 论
1.1 知识要点总结
一、数据结构的基本概念
1．基础概念和术语（1）数据（Data）：数据是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。（2）数据元素（Data Element）：数据元素是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。（3）数据项（Data Item）：数据项是数据的不可分割的最小单位，数据项是对客观事物的某一方面的数据描述。一个数据元素可由若干个数据项（Data Item）组成。（4）数据对象（Data Object）：数据对象是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,’C’ ,…}（5）数据结构（Data Structure）：数据结构是指相互之间存在一定联系（关系）的数据元素的集合。元素之间的相互联系（关系）称为逻辑结构。
2．数据结构的形式定义
数据结构的形式定义是一个二元组：
Data Structure=（D, S）
其中D是数据元素的有限集，S是D上关系的有限集。
数据元素之间的关系可以是元素之间本身代表的某种自然关系，也可以是为了处理问题方便而人为定义的关系，这种自然或人为定义的关系称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。
3．数据结构的组成
数据结构的三个组成部分：（1）逻辑结构
数据元素之间的逻辑关系的描述。数据元素之间的逻辑结构有四种基本类型：
①集合：结构中的数据除了“同属于一个集合”外，没有其它关系。
②线性结构：结构中的数据元素之间存在一对一的关系。
③树形结构：结构中的数据元素之间存在一对多的关系。
④图形结构或网状结构：结构中的数据元素之间存在多对多的关系。（2）存储结构
数据结构在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
①顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构。数据元素存放的地址是连续的。其优点是可以实现随机存取，存储空间小；缺点是只能使用相邻的一整块存储单元，容易产生碎片。
②链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针来表示数据元素之间的逻辑结构。对数据元素存放的地址是否连续没有要求。其优点是能充分利用所有存储单元；缺点是每个结点都需要额外的存储空间，且只能实现顺序存取。
③索引存储结构：在存储元素信息的同时．还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字．地址），关键字唯一标识一个元素，地址作为指向元素的指针。其优点是检索速度快；缺点是需要额外的存储空间来存放索引表。
④散列（或哈希）存储结构：根据元素的关键字通过哈希函数直接计算出该元素的存储地址。其优点是检索速度快，缺点是可能存在冲突，而解决冲突会增加时空开销。（3）数据操作
对数据要进行的运算。【例】下列有关数据存储结构的叙述中，正确的是（ ）。
A．顺序存储方式只能用于存储线性结构
B．顺序存储方式的优点是占用存储空问小，插入、删除等操作效率高
C．链表的每个结点中都恰好含有一个指针
D．Hash存储的基本思想是由关键词的值决定数据的存储地址【答案】D【解析】顺序存储方式除了用于存储线性结构外，还能存储数组或完全二叉树等非线
性结构，但在插入、删除操作时，由于要移动大量的数据，执行效率低。链表的形式有单链表、双链表和多重链表，除了单链表外，其他链表中的结点需要两个以上的指针。
二、抽象数据类型
1．数据类型
数据类型（Data Type）：数据类型是一个值的集合和定义在该集合上的一组操作的总称。
2．抽象数据类型
抽象数据类型（ADT）：是指一个数学模型以及定义在该数据模型上的一组操作。
ADT的定义仅是一组逻辑特性的描述，与其在计算机内的表示和实现无关。因此，不论ADT内部结构如何变化，只要其数学特性不变，都不影响其外部使用。
ADT的形式化定义是三元组：ADT={D,S,P}。
其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。
三、算法分析
1．算法（1）概念
算法（Algorithm）：算法是对特定问题求解方法（步骤）的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。（2）特性
算法由五个特性：
①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
②确定性：算法中每一条指令必须有确切的含义，不存在二义性，且算法只有一个入口和出口。
③可行性：算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
⑤输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。（3）评价标准
评价一个好的算法有以下几个标准：
①正确性：算法应满足具体问题的需求。
②可读性：算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。
③健壮性：算法应具有容错处理。当输入非法或错误数据时，算法能适当地做出反应或进行处理。
④通用性：算法应具有一般性，处理结果对于一般数据集合都成立。
⑤效率和存储量需求：效率指的是算法执行的时间；存储量需求指的是执行过程中所需要的最大存储空间。
2．效率的度量（1）时间复杂度
算法中的基本操作重复执行的次数是问题规模n的某个函数，其时间度量记做T（n）=O（f（n））（其中“O”是指T（n）的数量级），称作算法的渐进时间复杂度，简称时间复杂度。
算法的时间复杂度一般用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。
常用的时间复杂度的关系：23
O（1） 指数时间复杂度关系为：O（2n） 有的情况下，算法中基本操作重复执行的次数会随问题的输入数据集的不同而不同（2）空间复杂度 空间复杂度指的是算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记做：S（n）=O（f（n）），其中n为问题的规模。 空间复杂度一般包括三个方面： ①指令常数变量所占用的存储空间。 ②输入数据所占用的存储空间。 ③辅助存储空间。【例】有以下算法，其时间复杂度为（ ）。 A．O（1） B．O（logn）2 C．O（n） D．（nlogn）2【答案】B。【解析】基本运算语句为d=d/2（或f=f*f），设其执行时间为T（n），则有： 则T（n）≤logn=O（logn）。22 注意算法中while循环的if条件中包含的p=p*f语句可以不考虑．因为它执行的次数不超过d=d/2语句的执行次数。 1.2 考研真题与典型题详解 一、单项选择题 1．下列程常段的时间复杂度是（ ）。[2014年联考真题] A．O（logn） 2 B．O（n） C．O（nlogn） 22 D．O（n）【答案】C【解析】外部循环的退出条件是k>n，而对于k，每次循环都执行k=k*2,所以循环次数为logn；内部循环的退出条件是j>n,对于j，每次2循环都执行j=j+1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlogn），即选C。2 2．求整数n（n≥0）阶乘的算法如下，其时间复杂度是（ ）。[2012年联考真题] A．O（logn）2 B．O（n） C．O（nlogn）22 D．O（n）【答案】B【解析】设fact（n）的运行时间函数是T（n）。 该函数中语句①的运行时间是0（1），语句②的运行时间是T（n-1）+O（1），其中O（1）为乘法运算的时间。 因此，当n≤1时，T（n）-0（1）；当n>1时，T（n）=T（n-1）+O（1）。则，T（n）=O（1）+T（n-1） =2×O（1）+T（n-2）=（n-1）×O（1）+T（1）=n× O（1） =O（n） 即fact（n）的时间复杂度为O（n）。 3．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。[2011年联考真题] A．O（logn）2 B．O（n） C．O（nlogn）2 D．O（n） 2【答案】A【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句x=2×x，设其执行时间为T（n），则T （n）有2 4．算法的计算量的大小称为计算的（ ）。[北京邮电大学2000研] A．效率 B．复杂性 C．现实性 D．难度【答案】B【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。 5．下列说法错误的是（ ）。[南京理工大学2000研]（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于n复杂度O（2）的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 A．（1） B．（1），（2） C．（1），（4） D．（3）【答案】A【解析】算法原地工作的含义不是指不需要任何额外的辅助,而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。 6．以下属于逻辑结构的是（ ）。 A．顺序表 B．哈希表 C．有序表 D．单链表【答案】C【解析】数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，与数据元素本身的形式、内容、相对位置、所含结点个数都无关。顺序表、哈希表、单链表都涉及到数据的存储结构，有序表是指表中数据有序，与逻辑结构无关。 7．在数据结构中，从逻辑上可以将其分为（ ）。[中南大学2005研] A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．内部结构和外部结构 D．线性结构和非线性结构【答案】D【解析】数据结构从逻辑上可以分为线性结构和非线性结构。常见的线性结构为栈和队列，非线性结构为树形结构和网状结构。 8．一个算法应该是（ ）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本要求 D．A和C【答案】B【解析】程序不一定满足有穷性，如死循环，操作系统等，而算法必须有穷。算法代表了对问题求解步骤的描述，而程序是算法在计算机上的特定实现。 9．数据结构中数据元素之间的逻辑关系被称为（ ）。[北京理工大学2005研] A．数据的存储结构 B．数据的基本操作 C．程序的算法 D．数据的逻辑结构【答案】D 10．下面程序段中，执行S语句的次数为（ ）。2 A．n 2 B．n/2 C．n（n+1） D．n（n+1）/2【答案】D【解析】i的变化范围是从1到n，对于每个已确定值的i，j的变化范围是从1到i，相当于求一个公差为1的等差数列1，2，...，n的前n项和，即：n（n+1）/2。 11．可以用（ ）定义一个完整的数据结构。[中山大学2004研] A．数据元素 B．数据对象 C．数据关系 D抽象数据类型【答案】D【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。 12．以下算法的时间复杂度（ ）。 A．O（n）2 B．O（n） C．O（nlogn） 2 D．O（logn）2【答案】DT（n）【解析】基本运算为i=i*2，设其执行时间为T（n），则2 <=n,即T（n）<= logn= D．O（logn）22 二、综合题 1．已知一个整数序列，其中,若存且，则称x为A的主元素。例如,则称5为主元素；又如则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。[2013年联考真题] 解：（1） 算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元素Num。然后重新计数,确认Num是否是主元素。 算法可分为以下两步： ①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。 ②判断c中元素是否是真正的主元素，再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。（2）算法实现如下： 2．阅读下面的程序，指出过程pp完成的功能及结果数据结构的名称．并估计算法的时间复杂度O（?），说明理由。设单链表长度为n。 C语言 答：（1）程序的功能是将单链表逆置；（2）结果数据结构为存入一个带头结点、用尾指针表示的单向循环链表；（3）算法时间复杂度为O（n）。理由：因为此程序通过递归方法达到单链表的逆置，递归深度与表的节点数相当，回退时处理插入，每层复杂度为O（1），故总的复杂度为O（n）。 第2章 线性表 2.1 知识要点总结
一、线性表的定义和操作
1．线性表的定义
线性表（Linear List）：是由n（n≧0）个数据元素（结点）a，a，12…a组成的有限序列。该序列中的所有结点具有相同的数据类型。其n中数据元素的个数n称为线性表的长度。
当n=0时，称为空表。
当n>0时，将非空的线性表记作：L=（a，a，…a），其中a称12n1为线性表的第一个（首）结点，an称为线性表的最后一个（尾）结点。a，a，…a都是a（2≦i≦n）的前驱，其中a是a的直接前12i-1ii-1i驱；a，a，…a都是a（1≦i ≦n-1）的后继，其中a是a的直接i+1i+2nii+1i后继。
2．线性表的基本操作
一个数据结构的基本操作是指其最核心、最基本的操作。其它较为复杂的操作可以通过调用基本操作来实现。线性表的主要操作如下：
InitList（&L）初始化线性表：构造一个空的线性表L。
DestroyList（&L）销毁线性表：释放线性表L占用的内存空间。
ListEmpty（L）判断线性表是否为空表：若L是空表，则返回真，否则返回假。
ListLength（L）求线性表长度：返回L中元素的个数。
DispList（L）输出线性表：当线性表L不为空时，顺序显示L的各结点的值域。
GetElem（L，i，&e）求线性表L中指定位置的某个元素：用e返回L中第i（1≦i≦ListLength（L））个元素的值。
LocateElem（L，e）定位查找：返回L中第1个值域与e相等的为序。不存在则返回0。
ListInsert（&L，i，e）插入数据元素：在L的第i（1≦i≦ListLength（L）+1）个元素之前插入新的元素e，L的长度增加1。
ListDelete（&L，i，&e）删除数据元素：删除L的第i（1≦i≦ListLength（L））个元素，并用e返回其值，L的长度减少1。
二、线性表的实现
1．顺序存储（1）线性表的顺序存储结构
线性表的顺序存储结构就是把线性表的结点按逻辑顺序依次存放在一块地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
顺序存储的线性表的特点：
①线性表的逻辑顺序与物理顺序一致。
②数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
假设线性表存储的起始位置是LOC（A），元素类型为ElemType，则每个元素所占用存储空间的大小（即字节数）为sizeof（ElemType），整个线性表所占用存储空间的大小为n*sizeof（ElemType），其中，n表示线性表的长度。线性表的存储如图1-1所示。
图1-1 线性表的顺序存储结构
a在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物i理位序。
在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线性表中的所有元素和定义一个整型变量来存储线性表的长度。
假定数组用data[MaxSize]表示，长度整型变量用length表示，并采用结构体类型表示，则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下：
其中，Elem_array成员存放元素，length成员存放线性表的实际长度。（2）顺序表的基本操作
由于顺序表的操作比较简单，在这里只给出建立、插入、删除和按值查找的操作的算法。
①建立顺序表
其方法是将给定的含有n个元素数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。算法如下：
②插入操作
该运算在顺序表L的第i个位置（1≤i≤ListLength（L）+1）上插入新的元素e。
思路：如果i值不正确，则显示相应错误信息；否则将顺序表原来第i个元素及其后面元素均后移一个位置，腾出一个空位置插入新元素，顺序表长度增1。
在线性表L中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中的第i个位置插入结点的概率为P，不失一般性，i设各个位置插入是等概率，则P=1/（n+1），而插入时移动结点的次i数为n-i+1。
总的平均移动次数：
即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O（n）。
③删除操作
删除顺序表L中的第i（1≤i≤ListLength（L））个元素。
思路：如果i值不正确，则显示相应错误信息；否则将线性表第i个元素及其后面元素均向前移动一个位置，这样覆盖了原来的第i个元素，达到删除该元素的目的，最后顺序表长度减1。
试读结束[说明：试读内容隐藏了图片]