2023年《数据结构》考研真题与考研复习

20211.1 学问要点总结一、数据构造的根本概念1．根底概念和术语数据〔Data〕：数据是客观事物的符号表示。在计算机科学中指的是全部能输入到计算机中并被计算机程序处理的符号的总称。数据元素〔DataElement〕：数据元素是数据的根本单位，在程序中通常作为一个整体来进展考虑和处理。数据项〔DataItem〕：数据项是数据的不行分割的最小单位，数据项是对客观事物的某一方面的数据描述。一个数据元素可由假设干个数据项〔DataItem〕组成。数据对象〔DataObject〕：数据对象是性质一样的数据元素的集合，是数据C={‘A’,’B’,’C’,…}数据构造〔DataStructure〕：数据构造是指相互之间存在肯定联系〔关系〕的数据元素的集合。元素之间的相互联系〔关系〕称为规律构造。2．数据构造的形式定义数据构造的形式定义是一个二元组：DataStructure=〔D,S〕其中D是数据元素的有限集，S是D上关系的有限集。数据元素之间的关系可以是元素之间本身代表的某种自然关系，也可以是为了处理问题便利而人为定义的关系，这种自然或人为定义的关系称为数据元素之间的规律关系，相应的构造称为规律构造。3．数据构造的组成数据构造的三个组成局部：规律构造数据元素之间的规律关系的描述。数据元素之间的规律构造有四种根本类型：①集合：构造中的数据除了“同属于一个集合”外，没有其它关系。②线性构造：构造中的数据元素之间存在一对一的关系。③树形构造：构造中的数据元素之间存在一对多的关系。④图形构造或网状构造：构造中的数据元素之间存在多对多的关系。存储构造数据构造在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。存储构造主要有：挨次存储、链式存储、索引存储和散列存储。①挨次存储构造：用数据元素在存储器中的相对位置来表示数据元素之间的规律构造。数据元素存放的地址是连续的。其优点是可以实现随机存取，存储空间小；缺点是只能使用相邻的一整块存储单元，简洁产生碎片。②链式存储构造：在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针来表示数据元素之间的规律构造。对数据元素存放的地址是否连续没有要求。其优点是能充分利用全部存储单元；缺点是每个结点都需要额外的存储空间，且只能实现挨次存取。③索引存储构造：在存储元素信息的同时．还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：〔关键字．地址〕，关键字唯一标识一个元素，地址作为指向元素的指针。其优点是检索速度快；缺点是需要额外的存储空间来存放索引表。④散列〔或哈希〕存储构造：依据元素的关键字通过哈希函数直接计算出该元素的存储地址。其优点是检索速度快，缺点是可能存在冲突，而解决冲突会增加时空开销。数据操作对数据要进展的运算。【例】以下有关数据存储构造的表达中，正确的选项是〔 〕。A．挨次存储方式只能用于存储线性构造B．挨次存储方式的优点是占用存储空问小，插入、删除等操作效率高C．链表的每个结点中都恰好含有一个指针D．Hash存储的根本思想是由关键词的值打算数据的存储地址【答案】D查看答案【解析】挨次存储方式除了用于存储线性构造外，还能存储数组或完全二叉树等非线性构造，但在插入、删除操作时，由于要移动大量的数据，执行效率低。链表的形式有单链表、双链表和多重链表，除了单链表外，其他链表中的结点需要两个以上的指针。二、抽象数据类型1．数据类型数据类型〔DataType〕：数据类型是一个值的集合和定义在该集合上的一组操作的总称。2．抽象数据类型抽象数据类型〔ADT〕：是指一个数学模型以及定义在该数据模型上的一组操作。ADT的定义仅是一组规律特性的描述，与其在计算机内的表示和实现无关。因此，ADT内部构造如何变化，只要其数学特性不变，都不影响其外部使用。ADT的形式化定义是三元组：ADT={D,S,P}。其中：D是数据对象，S是D上的关系集，P是对D的根本操作集。三、算法分析算法概念算法〔Algorithm〕：算法是对特定问题求解方法〔步骤〕的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性算法由五个特性：①有穷性：一个算法必需总是在执行有穷步之后完毕，且每一步都在有穷时间内完成。②确定性：算法中每一条指令必需有精准的含义，不存在二义性，且算法只有一个入口和出口。③可行性：算法描述的操作都可以通过已经实现的根本运算执行有限次来实现。④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。⑤输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。评价标准评价一个好的算法有以下几个标准：①正确性：算法应满足具体问题的需求。②可读性：算法应简洁供人阅读和沟通。可读性好的算法有助于对算法的理解和修改。③强健性：算法应具有容错处理。当输入非法或错误数据时，算法能适当地做出反响或进展处理。④通用性：算法应具有一般性，处理结果对于一般数据集合都成立。⑤效率和存储量需求：效率指的是算法执行的时间；存储量需求指的是执行过程中所需要的最大存储空间。效率的度量时间简单度算法中的根本操作重复执行的次数是问题规模n〔〕=O〔f〔n〕〕〔其中“O”是指T〔n〕的数量级〕，称作算法的渐进时间简单度，简称时间简单度。算法的时间简单度一般用最深层循环内的语句中的原操作的执行频度〔重复执行的次数〕来表示。常用的时间简单度的关系：O〔1〕<O〔log2n〕<O〔n〕<O〔nlog2n〕<O〔n2〕<O〔n3〕指数时间简单度关系为：O〔2n〕<O〔n!〕<O〔nn〕有的状况下，算法中根本操作重复执行的次数会随问题的输入数据集的不同而不同空间简单度记做：S〔n〕=O〔f〔n〕〕，n空间简单度一般包括三个方面：①指令常数变量所占用的存储空间。②输入数据所占用的存储空间。③关心存储空间。【例】有以下算法，其时间简单度为〔 〕。A．O〔1〕B．O