数据结构期末复习资料

1、izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！计算机科学与技术专升本数据结构期htkvvivCMtnrmHEvmhwerihamvBszuA数据结构期末考试复习资料iz

2、TTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！考试时间：12月27日周一下午14:00-15:30考试地点：创新楼110复习范围：算法与数据结构第一至第八章考试题型：选择题

3、（每小题分，共分）判断题（每小题分，共分）填空题（每空2分，共20分）应用题（每小题，分，共20分）设计题（每小题，分，共10分）知识概要：第1章算法与程序1概念和术语数据：是能输入到计算机中并能被计算机程序处理的符号的总称。数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称

4、物理结构。数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。2逻辑结构的四种基本形态根据数据元素之间关系的不同特征，通常有下列四类基本结构：（1）集合：结构中的数据元素间除了“同属于一个集合”的关系外，别无其它关系。（2）线性结构：结构中的数据元素之间存在一个对一个的关系。（3）树型结构：结构中的数据元素之间存在一个对多个的关系。（4）图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。3数据存储结构的基本组织方式数据存储结构有顺序

5、和链式两种方式。（1）顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。（2）链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系，通常用链表来实现。在顺序存储结构的基础上，又可延伸变化出另外两种存储结构，即索引存储和散列存储。（1）索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。（2）散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一

6、一对应的目的。这样，查找时同样可大大提高效率。4数据结构的研究内容数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。5算法的五个重要特征（1）有穷性：一个算法必须保证在执行有限步骤之后结束，而不是无限的。（2）确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。（3）可行性：每一个操作步骤都必须在有限的时间内完成。（4）输入：一个算法可以有一个或多个输入，也可以没有输入。（5）输出：一个算法可以有一个或多个输出。没有输出的算法是没有实际意义的。6算法的评价标准（1）正确性。（2）易读性。（3）高效性。（4）可维护性。7算法分析的目的算法分

7、析主要是指分析算法的效率。算法效率的度量主要从两个方面：算法的运行时间和算法所需的存储空间。分析的目的是通过考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度分析作为重点。8算法的时间复杂度分析（1）算法运算时间的度量的两种方法：事后统计的方法和事前分析估算的方法。（2）算法运行时间的分析规则通常把一个程序的运行时间定义为一个（），其中是该程序输入数据的规模，而不是某一个具体的输入。的单位是不确定的，一般把它看成在一个特定计算机上执行的指令条数。通常记作：，其中表示数据输入规模。常见的算法时间复杂度的形式按性能降序的排

8、列如下：9算法空间复杂度的含义空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。算法在计算机存储器内占用的存储空间主要分为三部分：算法源代码本身占用的存储空间；算法输入输出数据所占用的存储空间；算法运行过程中临时占用的存储空间。考虑一个算法的空间复杂度时，要综合分析这三个方面的因素。通常记作,其中为问题的规模（或大小）。第2、3章线性表、栈、队列1线性表的定义线性表是个数据元素的有限序列，其中（）为线性表的长度。izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自

9、己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！线性表中各个元素的类型相同。对于线性表（，,，）而言，数据元素没有直接前趋,没有直接后继，表中的其它元素（顺序表没有直接后继，表中的其它元素（顺序表）有且仅一个直接前趋和直接后继izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesi

10、ha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！顺序表是指线性表的顺序存储结构，即用一组连续的存储单元依次存放线性表的数据元素。在语言中可用一维数组来表示。在顺序表中，以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。顺序表是一种随机存储结构，只要确定了存储顺序表的起

11、始位置，则表中任一元素都可以随机存取。所以在顺序表中可以方便的进行数据元素的查找及存取。但是在进行插入和删除操作时，将会引起元素的大量移动，因而效率比较低，并且易产生空间浪费或“上溢”现象。顺序表的操作还应注意元素的存储位置，即数组下标（语言中下标从开始）。3链表链表是线性表的链式存储结构。链表是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放线性表的数据元素。在链表中，通过指针来表示元素之间的逻辑关系的，不再有逻辑顺序与物理存储顺序一致的特点，是非顺序存储结构。在单链表中，每个结点由数据域和指针域组成。数据域保存数据元素的信息，指针域存放其直接后继的存储位置。其类型可描述为：单链表

12、由头指针唯一确定。为了便于操作，可在链表的第一个结点之前添加一个表头结点。在链表中进行插入和删除操作只需要修改有关的指针内容，不需要移动元素。因此，链表较顺序表的插入和删除操作更加方便、高效。为了便于实现各种运算，若无特殊说明，均采用带头结点的链表。4栈栈（）是限定仅在表的一端进行插入或删除操作的线性表。通常把允许插入和删除操作的一端称为栈顶（），而另一端称为栈底（t表为空时称为空栈。在栈上的主要运算是入栈和出栈。栈中元素如果按，的顺序进栈，则出栈顺序为，。因此，栈又称为“后进先出”（）的线性表，简称表。同线性表相似，栈也有顺序栈和链栈两种存储结构。顺序栈易产生“上溢”现象，而链栈不容易产生。

13、另外，注意对栈的操作只能在栈顶进行。5队列队列（）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。通常把允许插入的一端称为队尾（），允许删除的一端称为队头（）。队列中元素如果按，的顺序进队，则出队的顺序仍为，。因此，队列又称为“先进先出”（）的线性表，简称表。队列也有顺序队列和链队列两种存储结构。在顺序队列中，为避免“假满”现象，一般采用循环队列（即首尾相接）。链队列会因为队满而产生“上溢”现象。由第4章串祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出

14、自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwoizTTTfvwvewcnrintfEvwolohesiha祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！计算机科学与技术（专升本1计算机科学与技术（专升本1概念和术语数据结构期串（）（或字符串）：是由零个或多个字符组成的有限序列。一般记为其中，是串的名，用双引号括起来的字符序列是串的值。串的长度：串中字符的个数n。子串和主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串空串：不包含任何字符的串，表示为“”。空格串：由一个

15、或多个空格字符组成的串。例如：“”。2串的基本操作（）用串变量赋值和用串常量赋值（2）判等函数equat）l（s,（3）求长函数length（s）（4）连接函数concat（s,t）（5）求子串函数substproi,snlge（ns）,（6）定位函数index（s,t）（7）置换函数replace（s,t,v）（8）插入子串insert（s,pos,t）（9）删除子串delete（s,pos,k）（10）串的复制copy（s,t）3串的顺序存储结构（顺序串）串的顺序存储方式类似于线性表的顺序存储方式，其存储结构用语言描述为：定义顺序串类型第5章数组和广义表1多维数组的顺序存储结构对于多维数组

16、，有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如、等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如语言中，用的是以列为主序的分配顺序，即一列一列地分配。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的计算机科学与技术(专升本)数据结构期

17、末考试复习资料古月编辑整理存储地址表示为其下标的线性函数。设有二维数组，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。设数组的基址为(a,每个数组元素占据个地址单元，计算a的物理地址的函数为：(aO(a,)-同理，对于三维数组，即数组，对于数组元素a其物理地址为：(a)(a)()注意：在语言中，数组中每一维的下界定义为，贝y：(aO(a()2特殊矩阵压缩存储的意义在很多科学计算与工程应用中，经常要使用矩阵的概念。矩阵具有与数组相似的性质，如元素数目固定、元素按下标关系有序地排列，所以在编程时可以利用二维数组来存储矩阵，也可以利用程序设计语言中的各种矩阵运算。在某些情况下，

18、特别是在数值分析中，经常会出现一些阶数很高的矩阵，其中含有许多值相同的元素或零元素，如三角矩阵、对称矩阵、稀疏矩阵等，从节约存储空间的角度考虑，此时若用二维数组存储会造成空间的极大浪费。为了节省存储空间，可以对这类矩阵进行压缩存储。即为对多个相同值的元素只分配一个存储空间，而对零元素可以不分配空间。3对称矩阵压缩存储的方法对称矩阵的特点是：在一个阶方阵中，有a,其中WW，对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。TOC o 1-5 h z对于对称矩阵中的任意元素a,若令a,(),则将上面两个式子综合起来得到：(。)给出对称矩阵中任意元素a,依据它的下标和就可由上述对应关系式

19、确定其在数组中的位置，因此a的地址可由下式计算。(a)()()()()其中：为每个数据元素所占的存储单元长度。a()。()(+)4三角矩阵压缩存储的方法形如图的矩阵称为三角矩阵，其中为某个常数。其中下面图(a为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。(a)下三角矩阵(b)上三角矩阵图三角矩阵计算机科学与技术专升本数据结构期末考试复习资料古月编辑整理三角矩阵中的重复元素可以共享一个存储空间，其余的元素有个，因此可压缩存储到向量中，存放在向量的最后一个分量中，排列时以行序为主。和的对应关系是：下三角矩阵：上三角矩阵:5稀疏

20、矩阵及其压缩存储的特点设矩阵中有个非零元素且，这样的矩阵称为稀疏矩阵。稀疏矩阵的压缩存储采取如下方法：将非零元素所在的行、列以及它的值构成一个三元组（），然后再按某种规律存储这些三元组，这种方法可以节约存储空间。6稀疏矩阵压缩存储的顺序存储方式以顺序方式组织存储时常用的方法是三元组顺序表，方法是：将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，采用顺序存储方法存储该表。7稀疏矩阵压缩存储的链式存储方式稀疏矩阵压缩存储的链式存储方式，即十字链表。当矩阵中非零元素的个数和位置在使用中经常发生变化时，不宜采用顺序存储结构，可采用十字链表进行存储。其结点结构如图所示。8广义表（列表

21、）的定义、术语及它与线性表的关系广义表（当是（2）个数据元素的有序序列，一般记作：=（IO图十字链表的结点结构其中：是广义表的名称，是它的长度，每个（ww）是的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表的单元素和子表。当广义表非空时，称第一个元素为的表头（），称其余元素组成的表（，）为的表尾（）。表的深度：表中元素的最深嵌套层数。广义表与线性表的关系：当广义表中的元素全部是原子时，广义表即为线性表。因此，可认为线性表是广义表的特例，广义表是线性表的推广。9广义表的三个重要性质C）广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，。C

22、）广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表就是一个递归的表。C）广义表可以为其他表所共享。例如，表、表、表是表的共享子表。在中可以不必列出子表的值，而用子表的名称来引用。O广义表的存储结构祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本

23、数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！按结点形式的不同，广义表的链式存储结构可分为两种不同的存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。11广义表的基本运算广义表有两个重要的基本操作，即取头操作（）和取尾操作（）i此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。第6章树从对线性结构的研究过渡到对树形结构的研究，是数据结构课程学习的一次跃变。1理解树的递归定义树（）是零个或多个结点的有限集合。结点数为的树称为空树，结点数大于的树称为非空树。在一棵非空树中：（）

24、有且仅有一个特定的称为根（）的结点；（）当结点数大于时，除根结点外，其它结点被分成（）个互不相交的子集：，其中每个子集本身又是一棵树（称之为子树），每一棵子树的根（WW）都是根结点的后继，树1，称为根的子树。，掌握树的基本概念结点的度（）:是指结点拥有的子树的数目。叶子或终端结点：是指度为0的结点。非终端结点或分支结点：是指度不为0的结点。树的度：是指树内各结点的度的最大值。孩子（）和双亲（）：某个结点的子树的根称为该结点的孩子，相应的，该结点称为其孩子的双亲。兄弟：同一个双亲的孩子结点互为兄弟。结点的层次：规定根所在的层次为第1层，根的孩子在第二层，依次类推。树的深度或高度：树中结点最大的层

25、数。有序树：是指树中结点的各子树从左至右是有次序的，否则称为无序树。森林：是指（三）棵互不相交的树的集合。3理解二叉树的递归定义及其与树的区别二叉树（）是结点的有限集合，这个集合或者为空，或者是由一个根结点和两棵互不相交的分别称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树，且子树有左右之分，次序不能颠倒。二叉树是一种重要的树型结构，但二叉树不是树的特例。二叉树的5种形态分别为：空二叉树，只有根结点的二叉树，根结点和左子树，根结点和右子树，根结点和左右子树。二叉树与树的区别：二叉树中每个结点的孩子至多不超过两个，而树对结点的孩子数无限制；另外，二叉树中结点的子树有左右之分，而树

26、的子树没有次序。4掌握满二叉树和完全二叉树的概念满二叉树（）和完全二叉树（），是两种特殊形态的二叉树。计算机科学与技术专升本数据结构期htkvvivCMtnrmHE计算机科学与技术专升本数据结构期htkvvivCMtnrmHEvmhwerihamvBszuA一棵深度为且有个结点的二叉树称为满二叉树。深度为，有个结点的二叉树，当且仅当其每一个结点都与深度为的满二叉树中编号从至的结点一一对应时，称之为完全二叉树。完全二叉树的特点是：1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；（）对任一结点，如果其右子树的深度为，则其左子树的深度必为或理解二叉树的性质已知二叉树的

27、深度可求出该二叉树拥有的最多结点数，已知结点数可求出对应树或二叉树的最大和最小高度。性质在二叉树的第层上最多有个结点（三）。性质深度为的二叉树最多有个结点（三）。性质对任何一棵二叉树，如果其终端结点数为，度为的结点数为，则2性质性质在二叉树的第层上最多有个结点（三）。性质深度为的二叉树最多有个结点（三）。性质对任何一棵二叉树，如果其终端结点数为，度为的结点数为，则2性质具有个结点的完全二叉树的深度为性质如果对一棵有个结点的完全二叉树（其深度为1，其中，为不大于的最大整数）祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出

28、自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnri

29、ntfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！的结点按层序编号（编号方法为从第层到最后一层，每一层从左到右），则对任一结点（1）如果，则结点是二叉树的根，无双亲；如果则其双亲是第个结点。2）如果1）如果，则结点是二叉树的根，无双亲；如果则其双亲是第个结点。2）如果，则结点无左孩子（即结点为叶子结点）;否则其左孩子是第个结点。3）如果，则结点无右孩子；否则其右孩子是第+个1结点。二叉树中结点的编号规则和对应的顺序

30、存储结构顺序存储二叉树的具体方法是：在一棵具有个结点的完全二叉树中，从根结点开始编号为，自上到下，二叉树中结点的编号规则和对应的顺序存储结构顺序存储二叉树的具体方法是：在一棵具有个结点的完全二叉树中，从根结点开始编号为，自上到下，每层自左至右地给所有结点编号，这样可以得到一个反映整个二叉树结构的线性序列；然后将完全二叉树上编号为的结点依次存储在一维数组中下标为的元素中。上编号为的结点依次存储在一维数组中下标为的元素中。祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出

31、自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewc

32、nrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！二叉树的链接存储结构及存储结点的类型定义链式存储是使用链表来存储二叉树中的数据元素，链表中的一个结点相应地存储二叉树中的一个结点。常见的二叉树的链式存储结构有两种：二叉链表和三叉链表。二叉链表是指链表中的每个结点包含两个指针域和一个数据域，分别用来存储指向二叉树中结点的左右孩子的指针及结点信息。三叉链表是指链表中的每个结点包含三个指针域和一个数据域，相比二叉链表多出的一个指针域则用来指向该结点的双亲结点。不论哪种链表，

33、头指针都指向二叉树的根结点。），在含有个结点的二叉链表中，共有个指针域，但实际有效的指针数等于二叉树中的分支数（即），所以共存在个空的指针域。掌握二叉树的先序、中序、后序遍历的递归算法和非递归算法。能够根据先序+中序、后序+中序的遍历序列确定一棵二叉树，并理解为什么先序+后序不能唯一确定一棵二叉树。o掌握线索二叉树的定义及存储结构，会画出先序、中序和后序线索二叉树或相应的线索链表。2掌握遍历中序线索二叉树的规则及算法。计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整

34、理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！3掌握树的三种存储结构：双亲表示法、孩子表示法、孩子兄弟表示

35、法，掌握这三种存储方法的特点，并且能够画出指定树的存储结构图。4理解二叉树与树或森林转换的目的，掌握树和二叉树之间的相互转换，掌握森林和二叉树之间的相互转换。5掌握树的先根、后根和按层遍历的过程。6掌握森林的先根、后根遍历。7掌握路径、路径长度、结点的权、结点的带权路径长度、树的带权路径长度的概念。路径：若在树中存在着一个结点序列，使得是的双亲（WW）,则此结点序列称为从到的路径。路径长度：从到所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1结点的权：在许多应用中，常常将树中的某个结点赋上一个具有某种意义的数值，这个和某个结点相关的数值称为该结点的权或权值。结点的带权路径长度：

36、是指从树根到该结点之间的路径长度与结点的权值的乘积。树的带权路径长度：是指树中所有叶子结点的带权路径长度之和，通常记为。其中表示叶子结点的个数，表示叶子结点的权值，表示根结点到的路径长度。8掌握哈夫曼树的概念。哈夫曼树（）又称为最优二叉树，它是个带权的叶子结点构成的所有二叉树中带权路径长度最小的二叉树。9掌握哈夫曼树的构造方法，即根据一组给定的权值构造相应的哈夫曼树。O理解哈夫曼编码的含义，能够根据实际问题构造哈夫曼编码。第章图，基本概念及术语图：由两个集合和所组成，记作=V，其中是图中顶点的非空有限集合，是图中边的有限集合。有向图：如果图中每条边都是有向的即每条边在图示时都用箭头表示方向，则

37、称此图为有向图。有向图的边也称为弧，如图中是有向图，它由和组成。，E图图示例无向图：如果图中每条边都是顶点无序对，则称为无向图。无向边用圆括号括起的两个相关顶点来表示。在无向图中，和是表示同一条边。如图所示，和都是无向图。其中，无向完全图和有向完全图：若一个无向图有个顶点，而每一个顶点与其他个顶点之间都有边，这样的图称之为无向完全图。即共有一/条边。类似地，在有个顶点的有向图中，若有一条弧，即任意两顶点之间都有双向相反的两条弧连接，则称此图为有向完全图。子图：设有两个图和且满足条件：WV且B则称是的子图。路径：在图G中，从顶点V到V的一条路径是顶点序列且是中的边，路径上边的数目称之为该路径长度

38、。对于有向图，其路径也是有向的，路径由弧组成。简单路径：如果一条路径上所有顶点除其起始点和终止点外彼此都是不同的，则称该路径是简单路径。回路和简单回路：在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路。简单路径相应的回路称为简单回路。连通图和强连通图：在无向图中，若从到有路径，则称和是连通的。若中任意两顶点都是连通的，则称是连通图。对于有向图而言，若中每一对不同顶点和之间都有到和到的路径，则称为强连通图。度、入度和出度：若是中的一条边，则称顶点和是邻接的.并称边依附于顶点和。所谓顶点的度，就是依附于该顶点的边数。在有向图中，以某顶点为头，即终止于该顶点的弧的数目称为该顶点的入度；以某

39、顶点为尾，即起始于该顶点的弧的数目称为该顶点的出度。该顶点的入度和出度之和称为该顶点的度。若图中每一条边都有一个对应的数，则称为网。这些边上的数字称为权，它可以表示两顶点之间的距离或所花费的代价。类似地，边上带权的有向图称为有向网。如在图中是一个网，而图则是一个有向网。个有向网。计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的

40、成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升

41、本数据结构期末考试复习资料古月编辑整理祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！2图的存储结构常用的存储结构有邻接矩阵和邻接表。C）邻接矩阵表示法的邻接矩阵是按如下

42、定义的阶方阵:）W的邻接矩阵是按如下定义的阶方阵:）W或V丘时转。选取和关键字较小的存入辅助数组。和组成,两个子表长度分别为如果y转。否则如果y转。否则,将尚未处理完的子表中兀素存入。如果,存,入+;转。如果，将存入izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术(专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfv

43、wvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术(专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资

44、料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！合并结束。（2）两路归并的迭代算法一个元素的表总是有序的。所以对个元素的待排序列，每个元素可看成一个有序子表。对子表两两合并一个元素的表总是有序的。所以对生成个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2，再进行两两合并，直到生成，个元素按关键字有序的表。（3）算法分析归并排序是稳定排序，若用单链表作

45、为存储结构，可以实现就地排序。这种排序方法可用于内部排序，也可用于外部排序中。时间复杂度为。需进行趟归并，每一趟归并中，比较次数最多为次,移动次数等为次。空间复杂度为。6基数排序基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。计算机科学与技术（专升本（1）计算机科学与技术（专升本（1）多关键字排序数据结构期uimvivtiHCmriHFwoloheeihamvBsziiA料古月编辑整理多关键字排序按照从最主位关键字到最次位关键字或从最次位关键字到最主位关键字的顺序逐次排序，分两种方法：最咼位优先法（简称法）最低位优先法（简称法）（2）链式基数排序算法思想基数排序：从最低位关键

46、字起，按关键字的不同值将序列中的记录“分配”到个队列中，然后再“收集”之。如此重复次即可。链式基数排序是用个链队列作为分配队列，关键字相同的记录存入同一个链队列中，收集则是将各链队列按关键字大小顺序连接起来。算法分析基数排序是稳定排序，如果记录序列初始不是顺序存储，而是单链表形式，那么各辅助链队列无须分配结点空间，利用原链表的结点空间即可，而且分配和收集时都不必移动记录，只要修改指针，这样可以节省一定的时间和空间。7各种内部排序方法的比较与讨论（1）内部排序方法的共同点基本操作相同大多数排序算法都有两个基本的操作：（i）比较两个关键字的大小。（）改变指向记录的指针或移动记录本身，这种基本操作的

47、实现依赖于待排序记录的存储方式。待排文件的常用存储方式相同尽管排序可以采用不同方法，但所有待排序文件的存储方式都可以采用以下形式：（）顺序表（或直接用向量）作为存储结构（）以链表作为存储结构。（）用顺序的方式存储待排序的记录，但同时建立一个辅助表。（2）内部排序方法的不同点排序方法平均时间复杂度最坏时间复杂度辅助存储空间稳定性插入排序稳定希尔排序不确定不确定不稳定冒泡排序稳定简单选择排序稳定基数排序稳定快速排序不稳定堆排序不稳定归并排序稳定（3）排序方法的选择若较小（如W0可采用直接插入或简单选择排序。若文件初始状态基本有序（指正序），则应选用直接插入、冒泡或随机的快速排序为宜。若较大，则应采

48、用时间复杂度为（）的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。模拟试卷：数据结构模拟试卷、选择题（每小题1.分5，共30分）、有一个含头结点的单链表，头指针为则判断其是否为空的条件为（）。、非空的循环单链表的尾指针满足（）。3链表不具有的特点是（）。可随机访问任一个元素插入删除不需要移动元素不必事先估计存储空间所需空间与线性表的长度成正比4、若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后

49、一个结点，则采用（C）存储方式最节省运算时间。A单链表B双链表C单循环链表D带头结点的双循环链表5若线性表最常用的操作是存取第个元素及其前驱的值，则采用（）存储方式节省时间。A单链表B双链表C单循环链表D顺序表、设循环队列中数组的下标范围是，其头尾指针分别为，若队列中元素个数为（）。、设循环队列中数组的下标范围是，其头尾指针分别为，若队列中元素个数为（）。6设一个栈的输入序列为，则借助一个栈所得到的输出序列不可能的是（）。AA，B，C，DBD，C，B，A7、一个队列的入队序列是1，2，3，CA，C，D，BDD，A，B，C4，则队列的输出序列是（B）。Ar-fBr-f+C1（r-f）+m1odn

50、D（r-f）+mnodn9串是（）。A不少于一个字母的序列B任意个字母的序列C不少于一个字符的序列D有限个字符的序列、数组的每个元素占个单元，将其按行优先次序存储在起始地址为的连续内存单元中,则的地址是（）。1、1将一棵有1、个、结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（A）。izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术(专升本数据结构期izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrin

51、tfEvwolohesiha计算机科学与技术(专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！2对二叉树从开始编号，要求每个结点的编号大于其左右孩子的编号

52、，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用()实现编号。先序遍历中序遍历后序遍历从根开始进行层次遍历3、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是()的二叉树。空或只有一个结点高度等于其结点数任一结点无左孩子任一结点无右孩子4在有个叶子结点的哈夫曼树中，其结点总数为()。不确定5一个有个顶点的无向图最多有()边。(-(-16、任何一个无向连通图的最小生成树(B)。只有一棵有一棵或多棵一定有多棵可能不存在17、一组记录的关键字为(46，79，56，38，40，84)，利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。8已知数据表中每个元素距其最

53、终位置不远，则采用()排序算法最节省时间。堆排序插入排序快速排序直接选择排序19、下列排序算法中，()算法可能会出现下面情况：初始数据有序时，花费时间反而最多。堆排序冒泡排序快速排序排序20、对于键值序列(12，13，1，118，60，15，7，18，25，10)0，用筛选法建堆，必须从键值为(B)的结点开始。二、判断题(每小题分，共分。正确的在括号内打V”错误的打X)1、在单链表中，头结点是必不可少的。()2、如果一个二叉树中没有度为1的结点，则必为满二叉树。()3、循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。()4、顺序存储结构只能用来存放线性结构；链式存储结构

54、只能用来存放非线性结构。()5、在一个大根堆中，最小元素不一定在最后。()6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。()7、在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。()8、内部排序是指排序过程在内存中进行的排序。()9、拓扑排序是指结点的值是有序排列。()10、线性表采用链式存储，它比采用顺序存储方式，使得插入、删除、查找等运算的时间性能都更好。()三、填空题(每个填空2分，共20分)1、在顺序表(即顺序存储结构的线性表)中插入一个元素，需要平均移动个_元_素_。_2、快速排序的最坏情况，其待排序的初始排列是。izTTTfvwvewcnrintfEvwol

55、ohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术(专升本数据结构期izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术(专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计

56、算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！编辑整理、单循环链表中指针所指结点为尾结点的条件是、一个栈的输入序列为12，3写出不可能是栈的输出序列个结点的二叉树，采用二叉链表存放，空链域的个数为、队列的特性是、在求最小生成树的两种算法中，_算法_适_编辑整理、单循环链表中指针所指结点为尾结点的条件是、一个栈的输入序列为12，3写出不可能是栈的输出序列个结点的二叉树，采用二叉链表存放，空链域的个数为、队列的特性是、在求最小生成树的两种算法中，_算法_适_合_于_稀疏图。、已知一棵二叉树的前序序列为，中

57、序序列为，后序序列为、对二叉排序树进行遍_历_，_可得到结点的有序排列。0设一哈希表表长为，用除留余数法构造哈希函数，即（）为使函数具有较好性能，应选四、应用题（每小题5分，共20分）、已知关键字序列为：（7）哈希表长为10，哈希函数为：，解决冲突用线性探测再散列法，构造哈希表，求等概率下查找成功的平均查找长度。、给定叶结点权值：（1，3，5，6，7，8），构造哈夫曼树，并计算其带权路径长度。、从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树24，88，42，97，22，15，7，13）。祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参

58、考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！计算机科学与技术（专升本）计算机科学与技术（专升本）4、已知无向图如图1所示给出图的邻接表。从开始，给出一棵广度优先生成树。五、设计题（每小题5分，共10分）1有一个带头结点的单链表，已知指向头结点的指针，试写出在元素值

59、为的结点（假设该结点存在）之后插入元素值为的结点（该结点未建立）的算法过程。、以二叉链表为存储结构，写出求二叉树中叶子结点数的算法的递归函数。计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理计算机科学与技术（专升本数据结构期末考试复习资料古月编辑整理祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！i

60、zTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha计算机科学与技术（专升本数据结构期祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！祝愿大家考试考出自己理想的成绩，本资料仅供参考，谢谢！tfrwmvtiHCmriHEwdtoHEeiHAmvssziiA一、选择题（每小题，.分5，共30分）、若线性表最常用的操作是存取第个元素及其前驱元素的值，则采用（）存储方式最节省时间。单链表双向链表单循环链表顺序表、串的长度是（D）。串中不同字母的个数串中不同字符的个数串中所含字符的个数，且大于串中所含字符的个数、数组，的每个元素占个