数据结构考博复习提要

《数据结构考博复习提要》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章概论一、算法+数据结构=程序二、数据结构线性结构逻辑结构非线性结构顺序存储物理结构链式存储索引存储散列存储三、术语1、数据(Data)：数字、字符、图像、声音。.••…单元格2、数据元素(DataElement)：是数据的基本单位，又称结点(用一组连续的位串表示)或记录…••…行3、数据项(DataItem)：数据元素市若干个数据项组成，是数据的不可分割的最小单位。又称字段或域.-列4、数据对象(DataObject)：是性质相同的数据元素的集合。表5、数据结构(DataStructure)：是

2、相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性，通常有下列四类基本结构：0*00(1)集合结构：数据元素Z间除了“同属于一个集合''的关系外，别无其它关系；(2)线性结构：一对一关系；(3)树形结构：一对多关系；(4)图状结构或网状结构：多对多关系。6、数据类型：原子类型(只有一个数据项)、结构类型(由多个不同类型数据项组成)。7、抽象数据类型(AbstractDataType)：数据对象、数据关系、基本操作四、数据运算查找、插入、删除、修改、排序五、算法和算法分析1.

3、4」算法1、算法(Algorithm)：是对特定问题求解步骤的一种描述2^五个重要特性：(1)有穷性：执行有穷步之后结束，每一步在有穷时间内完成。(1)确定性：无二义性。唯一的一条执行路径，相同的输入只能得岀相同的输出。(2)可行性：基本运算执行有限次次。(3)输入：零个或多个输入。(4)输出：一个或多个输出。3、设计冃标：正确性、可读性、健壮性、效率与低存储量需求。六、算法分析1、度量一个程序的执行时间：(1)事后统计的方法(2)事前分析估算的方法(常用)高级语言编写的程序运行时间取决于下列因素：a

4、.依据的算法选用何种策略；b.问题的规模，例如求100以内还是1000以内的素数；c.书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低；d.编译程序所产生的机器代码的质量；e.机器执行指令的速度。一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的，则算法时间取决于两者的综合效果。从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。2、时间复杂度(1)算法中基本操作重复执行的次数是问题规模n

5、的某个两数f(n),算法的时间量度记作：T(n)=O(f(n))o(2)语句的频度(FrequencyCount)：该语句重复执行的次数。(3)时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O5)、线性对数阶0(nlog2n)＞平方阶O(nA2)＞立方阶O(M3)、k次方阶O(nAk)＞指数阶O(2An)«3、空间复杂©(SpaceComplexity)：算法所需辅助存储空间的量度，记作：S(n)=O(g(n))o第二章线性表一、线性表的类型定义1、线性表(Linea

6、rList)：n个数据元素的有限序列,(al,ai-1,ai,ai+1,an)(2一1),ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=l,2,ml时，ai有且仅有一个直接后继，当i=2,3,…,n时，ai有且仅有一个直接前驱。2、线性表的长度：线性表屮元素的个数n(n>0),n=0时称为空表。3、位序：al是第一个数据元素。an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表屮的位序。4、同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存

7、在着序偶关系。二、线性表的顺序表示和实现1、顺序存储或顺序映彖(顺序表)：用一组地址连续的存储单元依次存储线性表的数据元素。2、存储位置计算:LOC(aj)=LOC(ai)+(i-l)*L式屮LOC(al)是al的存储位置，称基地址。(假设每个元素占1个存储单元)3、特点：以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系，逻辑关系上相邻的两个元素在物理位置上也相邻。通常用数组来描述数据结构中的顺序存储结构。存储地址bb+L冇ftb+(i-l)L(n^l)L内存状态n空闲1二2二3二

8、4莎->5Io"6亘二78二(b)912123—>43452853063067427877(a)(b)4、优点：是一种随机存取的存储结构。5、缺点：要求占用连续的存储空间，并预先分配；插入和删除操作时需要移动大量的元素，平均移动次数为n/2。三、线性表的链式表示和实现1、特点：用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。2、结点(Node)：数据域：存储数据元素信息。指针域：存储直接后继存储位置。指针域中存储的