数据结构考试重点

1、数据结构第一章绪论1、数据结构的定义：按照某种逻辑关系组织起来的数据集、数据与数据间的逻辑关系在计算机存储器中的存储形式以及定义在数据集上的一组操作与操作的实现这三个方面统称为数据结构。2、数据主要分为两大类：数值型数据和非数值类型数据。数值型数据主要包括整数、实数和复数等；非数值类型数据包括字符、字符串、文字、声音、图形、图像等。3、数据结构的逻辑结构是指数据元素的集合以及定义在该集合上的数据元素之间的一种或多种特定关系。4、数据结构的逻辑结构是根据解决问题的功能目标而建立的；数据结构的存储结构是根据解决问题的性能要求而建立的。5、数据类型是一个具体相同性质的值的集合以及定义在该集合上的一组

2、操作的总称。数据类型定义了数据的性质、取值范围以及对数据所能进行的一组操作。6、根据数据元素之间逻辑关系的不同特性，可将数据结构分为：集合、线性机构、树形结构和图状结构。7、一个非空的线性结构的逻辑特点：1.只有一个数据元素没有前驱，称其为 “第一个”元素； 2.只有一个数据元素没有后继，称其为“最后一个”元素；3.除第一个元素外，其余数据元素有且只有一个前驱；4. 除最后一个元素外，其余数据元素有且只有一个后继。8、算法是指为解决一个问题而采用的方法和步骤；9、算法的五个特性： 1.有穷性：算法必须在有限步骤及有限时间内终止，并计算出结果；2.确定性：算法的每一个操作步骤都有确切的含义，即无

3、二义性； 3. 算法的每一个操作步骤，都是有效的、可行的；4.输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合；5.输出：一个算法必须有一个或多个输出。算法的目的是为了求解， 通过算法所求得的 “解”即是算法的输出。 注意，计算机算法的输出不一定就是计算机显示或打印输出，一个算法得到的结果实际就是算法的输出。第二章 线性表10、线性表是一种最基本而且应用最广泛的数据结构，其特点是结构中的各数据元素之间存在着一对一的关系，是一种最典型的线性结构。11、线性表是具有相同特性的数据元素的一个有限序列。12、线性表中的数据元素在位置上是有序的，相邻的元素之间存在着序偶关系。13、顺序表

4、的顺序存储结构是指把线性表中所有数据元素，按照其逻辑顺序依次存储到计算机存储器中从指定位置开始的一块连续的存储空间中，数据元素间的存储（物理）位置即表示了它的逻辑位置。14、顺序表基本操作的实现： 1.初始化操作； 2.求长度操作； 3.判空操作； 4.清空操作； 5.取元素操作； 6.按值查找操作； 7.插入操作； 8.删除操作。15、算法的空间效率是指算法在计算机上运行时所需存储空间的大小。算法的空间复杂度用大O 记法表示为： S（n）=O（f（ n）随着问题规模n 的增大，算法运行时所需辅助存储空间的增长率的数量级为f （n）。若算法运行时所占的存储空间与问题规模无关，是个常量，则称这种

5、算法为原地工作，其空间复杂度用 O（1）表示。16、顺序表的优缺点：优点： a.实现方法简单，各种高级语言中都有数组，容易实现；b.访问元素的速度快，因为在顺序表中逻辑上相邻的两个元素在存储位置上也必定相邻， 所以只要知道了第一个元素的地址，其他任何一个元素的地址都可通过简单的计算求得，故可实现随机存取， 即顺序表 L 的第 i 个元素即为L.basei-1。缺点： a.需占用连续的存储区，存储要求高，不能利用小块存储区；b.由于在顺序表中逻辑上相邻的两个元素在存储位置上也必定相邻，所以在进行插入和删除操作时， 需要进行大量的元素移动操作， 影响了算法效率。17、通常把使用链式存储结构来实现的

6、线性表称为链表。18、线性表的链式存储结构是用一组任意的存储单元来存放线性表中的数据元素，这组存储单元既可以是连续的，也可以是不连续的， 甚至可以零散分布在内存中的任意位置上。19、链表的相关概念： 1.首元结点，指链表中用于存储线性表的第一各数据元素的结点； 2.头结点，在链表中为了便于进行插入和删除等操作，为链表增设一个辅助结点，称该辅助结点为链表的头结点。 头结点在链表中可有可无； 3.头指针，是指向链表中第一个结点的指针，可以唯一地表示一个链表； 4.空指针，当链表中某个结点的指针域为空时，称该结点的指针域为空指针。20、链表的表长是指链表中存放数据元素的结点数目。21、链表分为单链表

7、、双向链表和循环链表。22、单链表的建立操作：1.头插法建立单链表：在单链表的建立过程中，总是将由读入元素所生成的结点插入到链表的表首端，即插入时始终将新生成结点作为第1 个结点插入。2.尾插法建立单链表：与头插法正好相反，在单链表的建立过程中，其每次都是将所生成的新结点插入到单链表尾端，即在插入时始终是新生成结点作为最后一个结点插入。23、链表的优缺点：优点： a.能充分利用内存中的小块存储区；b.便于进行插入和删除操作， 在进行插入和删除操作时不需要进行元素的移动，只需修改相应结点的指针域即可。缺点： a.与顺序表相比，其实现方法较复杂，特别在对双链表进行操作时不仅要考虑向后指向的“链”

8、，还需考虑向前指向的“链” ；b.无法像顺序表那样实现随机存取，在链表中要找某个结点只能从表头开始向后寻找；c.在链表的每个结点需要附加存储关系信息（指针域），因此当问题规模较小且基本一定时，链表所需存储空间比顺序表多。第三章栈与队列24、栈的定义：栈是一种将插入操作与删除操作限制在同一段进行的特殊线性表。在这个特殊的线性表中， 进行插入与删除操作的一端称为栈顶（ Top），另一端则称为栈底（ Bottom）。也就是说栈的插入操作与删除操作均在栈顶端进行，其中，插入操作称为入栈操作（Push），删除操作称为出栈操作（Pop）。不含任何元素的栈称为空栈。25、栈具有后进先出或者说为先进后出的特性

9、，故栈又称为后进先出表或先进后出表。26、栈的基本操作：初始化、销毁、判空、清空、入栈、出栈、取栈顶、求栈长及遍历。27、经试探可行则行进，不可行则返回重新试探的方法称为回溯法。28、一个概念、函数等对象用自己来定义自己，则称该对象为递归定义的。在程序设计语言中，一个算法直接或间接调用自己，则称该算法为递归算法。29、递归法则： 1.基准情形法则。递归定义中的基准情形即递归出口，它本身不再使用递归定义，是递归的结束条件； 2.不断推进法则。不断推进法则是指在递归求解过程中，每一次递归调用都必须使求解状况朝接近基准情形的方向推进。30、队列是一种插入操作限制在一端进行而删除操作限制在另一端进行的

10、特殊线性表。在这个特殊的线性表中进行插入操作的一端成为队尾，进行删除操作的一端称为队头。在队列尾端进行的插入操作称为入队操作，而在队列头端进行的删除操作称为出队操作。不含任何元素的队列称为空队。31、队列具有先进先出或者说后进后出的重要特性，故队列又称为先进先出表或后进后出表。第四章 串32、串的定义：串是由零个或多个任意字符组成的有限序列，一般记作：S=“ s1s2 si sn”（ n 0）。其中 S 是串名，用双引号括起来的字符序列为串值，但引号本身并不属于串的内容，它的作用是为了避免与变量名或数的常量相混淆。 Si（1 i n）称为串的元素，它可以是任意字母、数字或者是其他字符，是构成串

11、的基本单位， i 是它在整个串中的序号。 n 为串的长度，表示串中所包含的字符个数。例如，串 S1=“abcd”，串的元素为一个字母，其长度为 5。而在串 S2=“123456”，串的元素为一个数字，其长度为 6。33、串的静态顺序存储结构利用的是数组的静态分配方式，它是为每个定义的字符串分配一个固定长度的连续存储区域，将字符串中的字符顺序地存放在存储区域的各个单元里。实质上就是将串定义成字符数组， 利用串名可以直接访问串值。用这种表示方式，串的存储空间在编译时确定，其大小不能改变。34、串的动态顺序存储结构仍是为每个定义的字符串分配一个连续存储区域， 将字符串中的字符顺序地存放在这组存储区域

12、中的各个单元里， 只是这个存储区域不是在操作前分配的固定长度的区域， 而是在操作过程中根据需要动态分配得到的，即在程序运行时为每个产生的串分配一块实际串长所需的存储空间， 若分配成功，则返回指向该存储空间起始地址的指针，作为串的基址。第五章数组和广义表35、数组是 n 个相同数据类型的数据元素 a0，a1， ，an-1 构成的占用一块地址连续的内存单元的有限序列。 数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标。36、在大多数语言中采用以行序为主序的存储方式，如 C 语言、C+语言和 Pascal语言；在 Fortran 等少数语言中采用以列序为主序的存储

13、方式。37、常见的特殊矩阵：对称矩阵、三角矩阵和带状矩阵。对称矩阵：在一个n 阶方阵 A 中，若元素满足下述兴致：aij=aji （1i ，j n），则称 A 为 n 阶对称矩阵。三角矩阵：以主对角线划分， n 阶三角矩阵有 n 阶上三角矩阵和 n 阶下三角矩阵两种。 n 阶上三角矩阵的下三角 （不包括主对角线） 中的元素均为常数 c（或0）。n 阶下三角矩阵正好相反，它的主对角线上方均为常数 c（或 0）。带状矩阵：带状矩阵是指所有非零元素均集中在以对角线为中心的带状区域中的 n 阶方阵。38、常见的稀疏矩阵存储方法：三元组顺序表和十字链表。39、三元组顺序表： 将表示稀疏矩阵非零元素的三元

14、组按行优先或列优先（一般情况下为行优先） 的顺序排列， 并以此存储在向量中， 这种稀疏矩阵的顺序存储结构称为三元组顺序表。40、在广义表中，每个结点既可以属于基本数据类型，也可以属于广义表类型。41、广义表的定义是一个递归定义，它和线性表之间的不同之处在于：数据元素之间不仅有先后关系，更有元素内部的层次关系。42、广义表的长度是指表中数据元素的个数，需要注意的是数据元素可能是原子，也可能是子表；广义表的深度是指表中层次关系的最大深度，即所含括弧的重数， 需要注意：“原子”深度为 0，“空表”的深度为1。43、广义表的特性： 1.广义表是一个多层次的结构。表中元素可以是子表，子表的元素还可以是子

15、表； 2.广义表可为其他广义表所共享。在实际应用中，利用共享特性可以节约存储空间来；3.广义表可以是一个递归的表。递归表的深度是无穷值，长度则是有限值。44、广义表的存储形式：头尾链表和扩展线性链表。第六章 树45、树形结构是一种典型的非线性结构，在形状上类似于自然界中倒立的树，所有元素之间具有明显的层次关系和分支关系。现实生活中，操作系统的文件管理、家族的族谱关系和社会机构的组成等都可以用树形象地表示。46、树是 n（n 0）个结点的有限集。若n=0，称为空树；否则，在任何一棵非空树中满足以下条件： 1.有且仅有一个特定的没有前驱的结点称为根结点；2.当n1 时，其余结点可分为m（m0）个互

16、不相交的有限集合T1，T2， ， Tm。其中每个集合本身又是一棵树，称为根结点的子树。47、树的定义具有递归性，即树的定义中还有树。它刻画了树的固有特性：一棵非空子树由一个根结点及若干子树构成， 而子树又可以由其根结点和若干棵更小的子树构成。48、树的基本术语： 1.结点的度和树的度； 2.孩子、双亲和兄弟； 3.结点的层次和树的高度； 4.路径和路径长度； 5.有序树和无序树； 6.森林。49、树的高度：空树的高度为0；在非空树中，所有结点的最大层次称为树的高度（或深度）。50、二叉树的概念： 二叉树是一种重要的树形结构， 在计算机领域有着十分广泛的应用。任何一棵树都可以转换成一个与之对应的

17、二叉树， 从而对树的表示与处理便可用二叉树的表示和相关运算来实现。二叉树或为空树， 或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。其特点是它是一棵有序树，每个结点的度最大为2。51、满二叉树：在一棵二叉树中，如果所有分支结点的度均为2，且所有叶子结点在同一层上，则这棵二叉树称为满二叉树。52、完全二叉树：对满二叉树从树根为1 开始，按照从上到下、每层从左到右的原则对其顺序编号。满二叉树是完全二叉树的特例。53、二叉树的性质： 1.在二叉树的第 i 层上至少有 2i-1 个结点（ i0）； 2.深度为 k 的二叉树上至多含 2k-1 个结点（ k1）； 3.对任何一棵非

18、空二叉树，如果它含有n0 个叶子结点， n2 个度为 2 的结点，那么： n0= n2+1；4.具有 n 个结点的完全二叉n树的深度为 log 2 +1;5.对有 n 个结点的完全二叉树编号后，则对任意一个编号为i 的结点： a.若 i=1，则该结点是二叉树的根，无双亲；否则，其双亲结点编号为i/2 结点 ;b.若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点； c.若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。54、二叉树的顺序存储结构是用一组地址连续的存储单元来存放二叉树的数据元素。55、二叉树的链式存储结构： 在链式存储结构中， 结点之间的

19、逻辑关系是通过指针实现的。由于二叉树中每个结点最多有两个孩子结点，所以每个结点结构中，除了数据域 data 外，还需要设置两个指针域LChild 和 RChild ，分别指向左孩子和右孩子，这种存储结构称为二叉链表。56、二叉树的二叉链表和三叉链表的特点：1.它们均由 root 唯一确定，如二叉树为空，则 root=NULL ； 2.具有 n 个结点的二叉链表，共有2n 个指针域，其中具有 n+1 个空链域； 3.在三叉链表中易于查找某个结点的双亲，而在二叉链表中则需要遍历整棵树才能查找某结点的双亲。57、二叉树遍历是按照一定的路径访问二叉树中的每个结点，而且每个结点仅被访问一次。58、DLR: 先序遍历； LDR: 中序遍历； LRD: 后序遍历。第七章 图59、图是一种比线性表和树更为复杂的