第一部分数据结构与算法

《第一部分数据结构与算法》由会员分享，可在线阅读，更多相关《第一部分数据结构与算法（62页珍藏版）》请在装配图网上搜索。

1、数据结构与算法数据结构与算法公共基础知识公共基础知识考试方式考试方式1笔试：笔试：90分钟，满分分钟，满分100分，其中含公共基础知识部分分，其中含公共基础知识部分的的30分。分。公共基础知识的考试方式为笔试，所有语言程序设计公共基础知识的考试方式为笔试，所有语言程序设计的笔试部分合为一张试卷，公共基础知识部分占全的笔试部分合为一张试卷，公共基础知识部分占全卷的卷的30分。分。公共基础知识有公共基础知识有l0道选择题和道选择题和5道填空题。道填空题。2上机操作：上机操作：90分钟上，满分分钟上，满分100分。分。上机题目类型要求：上机题目类型要求：（1）基本操作。）基本操作。（2）简单应用。）

2、简单应用。（3）综合应用。）综合应用。基本要求 新大纲的二级基础知识分为四部分数据结构与算法程序设计基础软件工程基础数据库设计基础 数据结构与算法 本章的知识用于提高程序的效率以及对较复杂的问题进行求解。本章内容在计算机专业基础课中也属于比较难的一门，学习本章的内容必须进行理解，死记硬背是无效的。本章重点的考核点主要在二叉树，同时这也是本章的难点，考核形式主要为二叉树的遍历问题（如给图求遍历序列、给前序、中序遍历求后序遍历等）、二叉树的结点问题（如给出一些条件然后求叶子结点个数）；还有排序和查找考试中也经常会涉及到，排序主要以计算时间复杂度的形式考核，查找主要以计算最佳/最坏比较次数的方式考核

3、。其余的知识点主要以概念的形式考察，考生需要仔细看书并理解。程序设计基础与软件工程基础 这两章以概述的形式简介了规范化开发软件的方法。与数据结构不同，这两章内容主要是记忆性的知识点。程序设计基础的内容与大纲改革前添加了面向对象程序设计的内容，考生可以对本章进行几次细读后了解即可；软件工程基础这章主要考核内容为结构化分析及结构化设计方法（即SA及SD，约占50%），信息量较大，其次是软件测试（约占20%），考生需要将相关的概念及规则背诵，在以后有机会进行程序开发时这些知识可以得到深刻理解。数据库设计基础 数据库是当前软件处理的信息核心，目前大部分软件都是基于数据库的，因此学习一下数据库知识对程序

4、开发也是很有帮助的。本章主要的考核点是关系模型、关系代数及数据库系统的基本概念，其余的知识点了解即可，其中数据库的设计和管理可以结合着软件工程来看，考生会发现这两者有很多相似之处。除了关系代数会考一些简单的计算问题外，其余的都是以概念题的形式考核，考生需要仔细的阅读。v05年年4月月:10/2(选择选择/填空填空)v05年年9月月:6/6v06年年4月月:8/2v06年年9月月:6/4v07年年4月月:6/4v07年年9月月:8/4v08年年4月月:6/4v08年年9月月:6/4v09年年3月月:6/4v09年年9月月:6/4v10年年3月月:8/2v10年年9月月:8/2数据结构与算法数据结

5、构与算法近几年出题情况v考点考点1：算法：算法v考点考点2：数据结构：数据结构v考点考点3：线性表及其顺序存储结构：线性表及其顺序存储结构v考点考点4：栈和队列：栈和队列v考点考点5：线性链表：线性链表v考点考点6：树与二叉树：树与二叉树v考点考点7：查找技术：查找技术v考点考点8：排序技术：排序技术数据结构与算法数据结构与算法1算法的基本概念算法的基本概念算法是指对解题方案的准确而完整的描述。算法是指对解题方案的准确而完整的描述。2、算法的基本特征算法的基本特征可行性可行性确定性确定性有穷性（即算法必须能在执行有限个步骤之后终止）有穷性（即算法必须能在执行有限个步骤之后终止）拥有足够的情报拥

6、有足够的情报算法是一组严谨地定义运算顺序的规则算法是一组严谨地定义运算顺序的规则,并且每一个规并且每一个规则都是有效的则都是有效的,而且是明确的而且是明确的,此顺序将在有限的次数下终止。此顺序将在有限的次数下终止。数据结构与算法数据结构与算法考点考点1：算法：算法3、算法设计基本方法算法设计基本方法一个算法一般都可以用一个算法一般都可以用顺序、选择、循环顺序、选择、循环三种基本三种基本控制结构组合而成控制结构组合而成列举法：解决列举法：解决“是否存在是否存在”或或“有多少种可能有多少种可能”等类型问等类型问题题归纳法归纳法递推递推递归：分为直接递归和间接递归递归：分为直接递归和间接递归减半递推

7、技术减半递推技术回溯法回溯法数据结构与算法数据结构与算法考点考点1：算法：算法4算法复杂度算法复杂度算法的复杂度主要包括算法的复杂度主要包括时间复杂度时间复杂度和和空间复杂度空间复杂度两种。两种。算法时间复杂度：指算法在执行过程中所需基本运算的执行算法时间复杂度：指算法在执行过程中所需基本运算的执行次数，即指执行算法所需要的计算工作量。次数，即指执行算法所需要的计算工作量。v度量一个算法的工作量，与计算机、程序设计语言以及程序度量一个算法的工作量，与计算机、程序设计语言以及程序编制者无关、与算法实现过程中的许多细节无关，只编制者无关、与算法实现过程中的许多细节无关，只与问与问题的规模有关。题的

8、规模有关。)算法的空间复杂度：指执行这个算法所需要的内存空间。算法的空间复杂度：指执行这个算法所需要的内存空间。数据结构与算法数据结构与算法考点考点1：算法：算法v填空题填空题1、问题处理方案的正确而完整的描述称为、问题处理方案的正确而完整的描述称为_2、算法的复杂度主要包括、算法的复杂度主要包括_复杂度和空间复杂度复杂度和空间复杂度v选择题选择题1、下面叙述正确的是、下面叙述正确的是A.算法的执行效率与数据的存储结构无关算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令（或语句）的条数算法的空间复杂度是指算法程序中指令（或语句）的条数C.算法的有穷性是指算法必须能在执行

9、有限个步骤之后终止算法的有穷性是指算法必须能在执行有限个步骤之后终止D.以上三种描述都不对。以上三种描述都不对。数据结构与算法数据结构与算法考点考点1：算法：算法1、研究内容、研究内容：主要研究数据的逻辑结构、数据的存主要研究数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算储结构、对各种数据结构进行的运算(1)数据集合中各数据元素之间所固有的逻辑关系数据集合中各数据元素之间所固有的逻辑关系,即即数据的逻辑结构；数据的逻辑结构；(2)在对数据进行处理时在对数据进行处理时,各数据元素在计算机中的存各数据元素在计算机中的存储关系，即数据的存储结构储关系，即数据的存储结构;数据结构与算法数据结

10、构与算法考点考点2：数据结构：数据结构2、数据结构概念：数据结构是指相互有关联的数据、数据结构概念：数据结构是指相互有关联的数据元素的集合。理解元素的集合。理解（前件、后件）前件、后件）数据元素具有广泛的含义，一般来说数据元素具有广泛的含义，一般来说,现实世界现实世界中客观存在的一切个体都可以是数据元素。中客观存在的一切个体都可以是数据元素。例如例如,描述一年四季的季节名春、夏、秋、冬可描述一年四季的季节名春、夏、秋、冬可以作为季节的数据元素以作为季节的数据元素;表示家庭成员的各成员名父表示家庭成员的各成员名父亲、亲、儿子、女儿可以作为家庭成员的数据元素。儿子、女儿可以作为家庭成员的数据元素。

11、数据结构与算法数据结构与算法考点考点2：数据结构：数据结构具有相同特征的数据元素集合中具有相同特征的数据元素集合中,各个数各个数据元素之间存在有某种关系，这种关系反映据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。了该集合中的数据元素所固有的一种结构。在数据处理领域中通常把数据元素之间这种在数据处理领域中通常把数据元素之间这种固有的关系简单地用前后件关系来描述。固有的关系简单地用前后件关系来描述。例如，在考虑一年例如，在考虑一年4个季节的顺序关系时，个季节的顺序关系时，“春春”是是“夏夏”的前件的前件,而而“夏夏”是是“春春”的的后件等。后件等。数据结构与算法数据结

12、构与算法考点考点2：数据结构：数据结构3、数据的逻辑结构、数据的逻辑结构数据的逻辑结构数据的逻辑结构,是指反映数据元素之间逻辑是指反映数据元素之间逻辑关系的数据结构。关系的数据结构。数据结构与算法数据结构与算法考点考点2：数据结构：数据结构数据的逻辑结构有两个要素数据的逻辑结构有两个要素:一是数据元素的一是数据元素的集合集合,通常记为通常记为D;二是二是D上的关系上的关系,它反映了它反映了D中中各数据元素之间的前后件关系各数据元素之间的前后件关系,通常记为通常记为R,即一个即一个数据结构可以表示成：数据结构可以表示成：B=(D,R)其中其中B表示数据结构。为了反映表示数据结构。为了反映D中各数

13、据中各数据元素之间的前后件关系元素之间的前后件关系,一般用二元组来表示。例一般用二元组来表示。例如如,一年四季的数据结构可以表示成一年四季的数据结构可以表示成:B=(D,R)D=春，夏，秋，冬春，夏，秋，冬R=(春，夏春，夏),(夏，秋夏，秋),(秋，冬秋，冬)数据结构与算法数据结构与算法考点考点2：数据结构：数据结构4数据的存储结构数据的存储结构数据的逻辑结构在计算机存储空间的存放形式数据的逻辑结构在计算机存储空间的存放形式称为数据的存储结构。称为数据的存储结构。（也称数据的物理结构）（也称数据的物理结构）数据元素在计算机存储空间中的位置关系可能数据元素在计算机存储空间中的位置关系可能与逻辑

14、关系不同，与逻辑关系不同，一种数据的逻辑结构根据需要可一种数据的逻辑结构根据需要可以表示成多种存储结构以表示成多种存储结构。常用的存储结构有顺序、。常用的存储结构有顺序、链接、索引等存储结构。而采取不同的存储结构数链接、索引等存储结构。而采取不同的存储结构数据处理时效率不同，选择合适的存储结构是很重要据处理时效率不同，选择合适的存储结构是很重要的。的。数据结构与算法数据结构与算法考点考点2：数据结构：数据结构数据结构的图形表示数据结构的图形表示一个数据结构除了用二元关系表示外一个数据结构除了用二元关系表示外,还可以直观地用图形表示。在数据结构的图还可以直观地用图形表示。在数据结构的图形表示中形

15、表示中,对于数据集合对于数据集合D中的每一个数据中的每一个数据元素用中间标有元素值的方框表示元素用中间标有元素值的方框表示,称为结点。称为结点。对于关系对于关系R中的每一个二元组中的每一个二元组,用一条有向线用一条有向线段从前件结点指向后件结点。段从前件结点指向后件结点。数据结构与算法数据结构与算法考点考点2：数据结构：数据结构例如例如,一年四季的数据结构可以用如下图所示的图形来表一年四季的数据结构可以用如下图所示的图形来表示。示。反映家庭成员间辈分关系的数据结构可以用如下图所反映家庭成员间辈分关系的数据结构可以用如下图所示的图形表示示的图形表示:在数据结构中在数据结构中,没有前件的结点称为根

16、结点没有前件的结点称为根结点;没有后件的结点称没有后件的结点称为叶子结点为叶子结点.春春 夏夏秋秋冬冬父亲父亲女儿女儿儿子儿子数据结构与算法数据结构与算法考点考点2：数据结构：数据结构5线性结构与非线性结构线性结构与非线性结构数据结构分为两大类型数据结构分为两大类型:线性结构与非线性结构线性结构与非线性结构。如果一个非空的数据结构满足两个条件如果一个非空的数据结构满足两个条件:有且只有一个根结点有且只有一个根结点.每一个结点最多有一个前件每一个结点最多有一个前件,也最多有一个后件也最多有一个后件.则称该数据结构为线性结构。也称为则称该数据结构为线性结构。也称为线性表线性表。注意注意：在一个线性

17、结构中插入或删除任何一个结点后在一个线性结构中插入或删除任何一个结点后还应是线性结构。如数据结构不是线性结构还应是线性结构。如数据结构不是线性结构,则称为非线性则称为非线性结构。结构。数据结构与算法数据结构与算法考点考点2：数据结构：数据结构填空题：填空题：数据的逻辑结构在计算机存储空间中的存放形式称为数据数据的逻辑结构在计算机存储空间中的存放形式称为数据的的_。选择题选择题1、以下关于数据的逻辑结构的叙述中，哪一条是不正确的？、以下关于数据的逻辑结构的叙述中，哪一条是不正确的？数据的逻辑结构是数据间关系的描述数据的逻辑结构是数据间关系的描述数据的逻辑结构抽象地反映数据元素间的逻辑关系数据的逻

18、辑结构抽象地反映数据元素间的逻辑关系数据逻辑结构具体的反映数据在计算机中的存储方式数据逻辑结构具体的反映数据在计算机中的存储方式数据的逻辑分为线性结构和非线性结构数据的逻辑分为线性结构和非线性结构数据结构与算法数据结构与算法考点考点2：数据结构：数据结构2、数据的存储结构是指、数据的存储结构是指_.A、存储在外存中的数据、存储在外存中的数据B、数据所占的存储空间、数据所占的存储空间C、数据在计算机中的顺序存储方式、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示、数据的逻辑结构在计算机中的表示数据结构与算法数据结构与算法考点考点2：数据结构：数据结构1线性表的基本概念：线性表的基

19、本概念：线性表是一种线性结构。线性表是一种线性结构。非空线性表有如下一些结构特征非空线性表有如下一些结构特征:有且只有一个根结点有且只有一个根结点a1,它无前件它无前件;有且只有一个终端结点有且只有一个终端结点an,它无后件它无后件;除根结点与终端结点外，其他所有结点有且只有一除根结点与终端结点外，其他所有结点有且只有一个前件个前件,也有且只有一个后件。也有且只有一个后件。数据结构与算法数据结构与算法考点考点3：线性表及其顺序存储结构：线性表及其顺序存储结构v线性表由一组数据元素构成。线性表由一组数据元素构成。v例如例如,一维数组一维数组inta10=1,2,3,4,5,6,7,8,9,10是

20、一个长度为是一个长度为10的线性表，其中的每一个元素就是一个数据元素。又如一的线性表，其中的每一个元素就是一个数据元素。又如一年中的年中的4个季节个季节(春春,夏夏,秋秋,冬冬)是一个长度为是一个长度为4的线性表，其中的线性表，其中的每一个季节名就是一个数据元素。的每一个季节名就是一个数据元素。v线性表是由线性表是由n(n=O)个数据元素个数据元素a1,a2,an组成的一个有组成的一个有限序列限序列,表中的每一个数据元素表中的每一个数据元素,除了第一个外除了第一个外,有且只有一有且只有一个前件个前件,除了最后一个外除了最后一个外,有且只有一个后件。有且只有一个后件。v线性表中的元素线性表中的元

21、素ai(i=1,2,n)通常称其为线性表中的一个通常称其为线性表中的一个结点。结点。数据结构与算法数据结构与算法考点考点3：线性表及其顺序存储结构：线性表及其顺序存储结构v2线性表的顺序存储结构线性表的顺序存储结构v线性表的顺序存储结构具有以下两个基本特点线性表的顺序存储结构具有以下两个基本特点:v线性表中所有元素所占的存储空间是连续的线性表中所有元素所占的存储空间是连续的;v线性表中各数据元素在存储空间中是按逻辑顺序依次存线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。放的。v在线性表的顺序存储结构中在线性表的顺序存储结构中,如果线性表中各数据元素所占如果线性表中各数据元素所占的存储空

22、间的存储空间(字节数字节数)相等相等,第第1个数据元素的存储地址为个数据元素的存储地址为ADR(a1),每一个数据元素占每一个数据元素占k个字节个字节,则线性表中第则线性表中第i个元个元素素ai存储地址为存储地址为:vADR(ai)=ADR(a1)+(i-1)*k数据结构与算法数据结构与算法考点考点3：线性表及其顺序存储结构：线性表及其顺序存储结构1栈及其基本运算栈及其基本运算1）什么是栈）什么是栈栈实际上也是线性表，只栈实际上也是线性表，只不过是一种特殊的线性表。在不过是一种特殊的线性表。在这种特殊的线性表中，其插入这种特殊的线性表中，其插入与删除运算都只在线性表的一与删除运算都只在线性表的

23、一端进行，即这种线性表的一端端进行，即这种线性表的一端是封闭的，不允许进行插入与是封闭的，不允许进行插入与删除元素；另一端是开口的，删除元素；另一端是开口的，允许进行插入与删除元素。例允许进行插入与删除元素。例如，子弹夹就是一种栈的结构。如，子弹夹就是一种栈的结构。进进栈栈出出栈栈A A n nA A2 2A A1 1数据结构与算法数据结构与算法考点考点4：栈和队列：栈和队列v栈是一种特殊的线性表，一端是封闭的，不允许进栈是一种特殊的线性表，一端是封闭的，不允许进行插入和删除，另一端是开口的，允许插入与删除行插入和删除，另一端是开口的，允许插入与删除元素。按照元素。按照“先进后出先进后出“或或

24、”后进先出后进先出“的原则结的原则结构数据，栈具有记忆功能。构数据，栈具有记忆功能。v往栈中插入一个元素称为入栈运算，从栈中删除一往栈中插入一个元素称为入栈运算，从栈中删除一个元素称为退栈运算。个元素称为退栈运算。数据结构与算法数据结构与算法考点考点4：栈和队列：栈和队列栈是限定在一端进行插入与删除的线性表，允栈是限定在一端进行插入与删除的线性表，允许进行插入与删除的一端成为栈顶（许进行插入与删除的一端成为栈顶（top）,而不允而不允许进行插入与删除的一端成为栈底（许进行插入与删除的一端成为栈底（bottom）。栈）。栈顶的元素总是最后被插入的元素，也是最先被删除顶的元素总是最后被插入的元素，

25、也是最先被删除的元素；栈底的元素总是最先被插入的元素，也是的元素；栈底的元素总是最先被插入的元素，也是最后被删除的元素。即栈是按照最后被删除的元素。即栈是按照“先进后出先进后出”或或“后进先出后进先出”的原则组织数据的。栈具有记忆功能的原则组织数据的。栈具有记忆功能.v2）栈运算）栈运算v往栈中插入一个元素称为入栈运算，从栈中删往栈中插入一个元素称为入栈运算，从栈中删除一个元素称为退栈运算。除一个元素称为退栈运算。数据结构与算法数据结构与算法考点考点4：栈和队列：栈和队列v2队列及其基本运算队列及其基本运算v队列是指允许在一端进行插入队列是指允许在一端进行插入,而在另一端进行删除的而在另一端进

26、行删除的线性表。线性表。是是“先进先出先进先出”或或“后进后出后进后出”的原则。的原则。v允许插入的一端称为队尾允许插入的一端称为队尾,允许删除的一端称为排头允许删除的一端称为排头(也称为也称为队头队头).v在队列这种数据结构中在队列这种数据结构中,最先插入的元素将最先能够被删除最先插入的元素将最先能够被删除,反之反之,最后插入的元素将最后才能被删除。因此最后插入的元素将最后才能被删除。因此,队列又称为队列又称为先进先出先进先出或或后进后出后进后出的线性表的线性表,它体现了它体现了先来先服务先来先服务的原则。往队列的队尾插入一个元素称为入队运算，从队列的原则。往队列的队尾插入一个元素称为入队运

27、算，从队列的排头删除一个元素称为退队运算。的排头删除一个元素称为退队运算。a1，a2，an入队入队出队出队队头队头队尾队尾数据结构与算法数据结构与算法考点考点4：栈和队列：栈和队列3.循环队列及其运算循环队列及其运算循环队列就是将队列存储空间的最后一个位循环队列就是将队列存储空间的最后一个位置绕到第置绕到第1个位置个位置,形成逻辑上的环状空间，供队列形成逻辑上的环状空间，供队列循环使用。循环使用。数据结构与算法数据结构与算法考点考点4：栈和队列：栈和队列1线性链表的基本概念线性链表的基本概念线性表的链式存储结构称为线性表的链式存储结构称为线性链表线性链表。在线性。在线性表的链式存储结构中，各数

28、据结点的存储序号是不表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。辑关系也不一致。数据结构与算法数据结构与算法考点考点5：线性链表：线性链表线性链表：线性链表：为了适应线性表的链式存储结构为了适应线性表的链式存储结构,计算机存储空间计算机存储空间被划分为一个一个的小块，每一小块占若干字节被划分为一个一个的小块，每一小块占若干字节,通通常称这些小块为存储结点。为了存储线性表中的每常称这些小块为存储结点。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面一个元素，一方面要存储数据元素

29、的值，另一方面要存储各数据元素之间的前后件关系。为此目的，要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分：将存储空间中的每一个存储结点分为两部分：一部一部分用于存储数据元素的值，称为分用于存储数据元素的值，称为数据域数据域;另一部分另一部分用于存放下一个数据元素的存储序号用于存放下一个数据元素的存储序号(即存储结点的即存储结点的地址地址),即指向后件结点，称为即指向后件结点，称为指针域指针域数据结构与算法数据结构与算法考点考点5：线性链表：线性链表在线性链表中，用一个专门的指针在线性链表中，用一个专门的指针HEAD指向线性链表中指向线性链表中第第1个数据元素

30、的结点个数据元素的结点(即存放线性表中第即存放线性表中第1个数据元素的个数据元素的存储结点的序号存储结点的序号)。线性表中最后一个元素没有后件，因此，。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空线性链表中最后一个结点的指针域为空(用用NULL或或O表表示示),表示链表终止。表示链表终止。线性链表的逻辑结构如下图所示。线性链表的逻辑结构如下图所示。HEAD数据1数据2数据nNNnnnnnnnn1 NULL数据结构与算法数据结构与算法考点考点5：线性链表：线性链表v2线性链表及其基本运算线性链表及其基本运算v（1）线性链表的插入）线性链表的插入（2）线性链表的删除）线性

31、链表的删除v（3）线性链表的查找）线性链表的查找v线性链表的插入是指在链式存储结构下的线线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。性表中插入一个新元素。为了要在线性链表为了要在线性链表中插入一个新元素，首先要给该元素分配一中插入一个新元素，首先要给该元素分配一个新结点个新结点p，并赋值。然后找到待插入位置的，并赋值。然后找到待插入位置的前一个结点的指针前一个结点的指针q。先将。先将p指向指向q的后件，的后件，然后将然后将p挂接在挂接在q结点后面。结点后面。数据结构与算法数据结构与算法考点考点5：线性链表：线性链表v线性链表的删除线性链表的删除是指在链式存储结构下的线性表中删除

32、包含是指在链式存储结构下的线性表中删除包含指定元素的结点。指定元素的结点。为了在线性链表中删除包含指定元素的为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到待删除元素的前一个结点结点，首先要在线性链表中找到待删除元素的前一个结点p，用另一个指针用另一个指针q保存保存p的后续结点，然后把的后续结点，然后把q结点的后续链挂结点的后续链挂接在接在p的后面。最后归还的后面。最后归还q结点所分配的栈空间。结点所分配的栈空间。v线性链表的查找线性链表的查找过程是从头指针指向的结点开始向后沿指针过程是从头指针指向的结点开始向后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为搜进行扫描，

33、直到后面已没有结点或下一个结点的数据域为搜索值索值x为止。为止。数据结构与算法数据结构与算法考点考点5：线性链表：线性链表1树的基本概念树的基本概念MFGLCHXYSWZABENOTRKPQD数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树树是一种简单的非线性树是一种简单的非线性结构，在树结构中，每结构，在树结构中，每一个结点只有一个前件，一个结点只有一个前件，称为父结点，没有前件称为父结点，没有前件的结点只有一个，称为的结点只有一个，称为树的根结点。没有后件树的根结点。没有后件的结点称为叶子结点。的结点称为叶子结点。2、树的一些常用术语。、树的一些常用术语。v结点结点：结点由数

34、据元素和构造数据元素之间关系的结点由数据元素和构造数据元素之间关系的指针组成。例如，图中有指针组成。例如，图中有22个结点。个结点。v结点的度结点的度：结点所拥有的子树的个数称为该结点的结点所拥有的子树的个数称为该结点的度。例如，在上图中，结点度。例如，在上图中，结点R的度为的度为4，结点，结点K的度的度为为2，结点，结点M的度为的度为0。v树的度树的度：树中所有结点中的最大度称为该树的度。树中所有结点中的最大度称为该树的度。例如，上图例如，上图R的度等于的度等于4是该树中所有结点的度的最是该树中所有结点的度的最大值，所以该树的度为大值，所以该树的度为4。数据结构与算法数据结构与算法考点考点6

35、：树与二叉树：树与二叉树v叶子结点叶子结点：没有后件的结点称为叶子结点，叶子结点也没有后件的结点称为叶子结点，叶子结点也称做终端结点。结点称做终端结点。结点C、E、M、F、G等均为叶子结点。等均为叶子结点。v结点的层次结点的层次：从根结点到树中某结点所经路径上的分从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为支数称为该结点的层次。根结点的层次规定为1，这样其他，这样其他结点的层次就是它的前件的层次加结点的层次就是它的前件的层次加1。v树的深度树的深度：树中所有结点的层次的最大值称为该树的深树中所有结点的层次的最大值称为该树的深度。上图中树的深度等于度。上图中树的深度

36、等于5。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树子树子树：在树中，以某结点的一个子结点为根构成的树在树中，以某结点的一个子结点为根构成的树称为该点的一棵子树。如结点称为该点的一棵子树。如结点R有有4棵子树。叶子结棵子树。叶子结点没有子树。点没有子树。v森林森林:m(m0)棵树的集合称为森林。自然界中树和棵树的集合称为森林。自然界中树和森林的概念差别很大，但在数据结构中树和森林的森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树由根结点和概念差别很小。从定义可知，一棵树由根结点和m个子树组成，若把树中的根结点删除，则树就变成个子树组成，若把树中的根

37、结点删除，则树就变成了包含了包含m棵树的森林。当然，根据定义，一棵树也棵树的森林。当然，根据定义，一棵树也可以称做森林。可以称做森林。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v3二叉树特点二叉树特点v1）什么是二叉树什么是二叉树v二叉树是一种很有用的非线性结构。二二叉树是一种很有用的非线性结构。二叉树不同于前面介绍的树结构，但它与树结叉树不同于前面介绍的树结构，但它与树结构很相似，并且，树结构的所有术语都可以构很相似，并且，树结构的所有术语都可以用到二叉树这种数据结构上。用到二叉树这种数据结构上。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v二叉树两个特

38、点二叉树两个特点:v(1)非空二叉树只有一个根结点非空二叉树只有一个根结点;v(2)每一个结点最多有两棵子树，且分别称为该结每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。点的左子树与右子树。v由以上特点可以看出，在二叉树中，每一个结由以上特点可以看出，在二叉树中，每一个结点的度最大为点的度最大为2,即所有子树即所有子树(左子树或右子树左子树或右子树)也均也均为二叉树。而树结构中的每一个结点的度可以是任为二叉树。而树结构中的每一个结点的度可以是任意的。在二叉树中，一个结点可以只有左子树而没意的。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一有右子

39、树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是个结点既没有左子树也没有右子树时，该结点即是叶子结点。叶子结点。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v4、二叉树的基本性质、二叉树的基本性质v二叉树具有以下几个性质。二叉树具有以下几个性质。v性质性质1:在二叉树的第在二叉树的第k层上，最多有层上，最多有2k-1(k=1)个结点。个结点。v性质性质2:深度为深度为m的二叉树最多有的二叉树最多有2m-1个结点。个结点。v深度为深度为m的二叉树是指二叉树共有的二叉树是指二叉树共有m层。根据性层。根据性质质1,只要将第只要将第1层到第层到第m层

40、上的最大的结点数相层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，即加，就可以得到整个二叉树中结点数的最大值，即:v20+21+2m-l=2m-1数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v性质性质3:在任意一棵二叉树中，度为在任意一棵二叉树中，度为O的结点的结点(即叶子结点即叶子结点)总是比度为总是比度为2的的结点多结点多1个。个。v性质性质4：具有：具有n个结点的二叉树，其深个结点的二叉树，其深度至少为度至少为log2n+1,其中其中log2n表示表示取取log2n的整数部分。的整数部分。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v5、

41、满二叉树与完全二叉树、满二叉树与完全二叉树v满二叉树与完全二叉树是两种特殊形态的二叉树。满二叉树与完全二叉树是两种特殊形态的二叉树。1)满二叉树满二叉树v所谓满二叉树是指除最后一层外，每一层上的所有所谓满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。这就是说结点都有两个子结点。这就是说,在满二叉树中，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的每一层上的结点数都达到最大值，即在满二叉树的第第k层上有层上有2k-1个结个结点，且深度为点，且深度为m的满二叉树有的满二叉树有2m-1个结点。个结点。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v2)完全二叉

42、树完全二叉树v所谓完全二叉树是指除最后一层外，每一层上的结点所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值数均达到最大值;在最后一层上只缺少右边的若干结点。更在最后一层上只缺少右边的若干结点。更确切地说，如果从根结点起，对二叉树的结点自上而下、自确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为左至右用自然数进行连续编号，则深度为m,且有且有n个结点个结点的二叉树，当且仅当其每一个结点都与深度为的二叉树，当且仅当其每一个结点都与深度为m的满二叉的满二叉树中编号从树中编号从1到到n的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全

43、二叉树。v由满二叉树与完全二叉树的特点可以看出，满二叉树也是完由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。全二叉树，而完全二叉树一般不是满二叉树。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v完全二叉树两个性质：完全二叉树两个性质：v性质性质5：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n+1。v性质性质6：设完全二叉树共有：设完全二叉树共有n个结点。如果从根结点开始，个结点。如果从根结点开始，按层序按层序(每一层从左到右每一层从左到右)用自然用自然1,2,n给结点进行编号，给结点进行编号，则对于编

44、号为则对于编号为k（k=1,2,，n)的结点有以下的结点有以下结论结论:v若是若是k=1,则该结点为根结点，它没有父结点则该结点为根结点，它没有父结点;若若k1,则则该结点的父结点编号为该结点的父结点编号为INT(k/2)v若若2k=n,则编号为则编号为k的结点的左子结点编号为的结点的左子结点编号为2k,否则否则该结点无左子结点该结点无左子结点v若若2k+1=n,则编号为则编号为k的结点的右子结点编号为的结点的右子结点编号为2k+1;否则该结点无右子结点。否则该结点无右子结点。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v4二叉树的遍历二叉树的遍历v二叉树的遍历是指不重复地访

45、问二叉树中的所有结点。二叉树的遍历是指不重复地访问二叉树中的所有结点。由于二叉树是一种非线性结构，因此，对二叉树的遍历要比由于二叉树是一种非线性结构，因此，对二叉树的遍历要比遍历线性表复杂得多。在遍历二叉树的过程中，当访问到某遍历线性表复杂得多。在遍历二叉树的过程中，当访问到某个结点时，再往下访问可能有两个分支，那么先访问哪一个个结点时，再往下访问可能有两个分支，那么先访问哪一个分支呢分支呢?对于二叉树来说，需要访问根结点、左子树上的所对于二叉树来说，需要访问根结点、左子树上的所有结点、右子树上的所有结点，在这三者中，究竟先访问哪有结点、右子树上的所有结点，在这三者中，究竟先访问哪一个一个?也

46、就是说，遍历二叉树的方法实际上是要确定访问各也就是说，遍历二叉树的方法实际上是要确定访问各结点的顺序，以便不重不漏地访问到二叉树中的所有结点。结点的顺序，以便不重不漏地访问到二叉树中的所有结点。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为树的遍历可以分为3种种:前序遍历、中序遍历、后序遍历前序遍历、中序遍历、后序遍历。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v（1）前序遍历前序遍历(根左右根左右

47、)v所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树子树;并且，在遍历左右子树时，仍然先访问根结点，然后，并且，在遍历左右子树时，仍然先访问根结点，然后，遍历左子树，最后遍历右子树。遍历左子树，最后遍历右子树。v（2）中序遍历中序遍历(左根右左根右)v中序遍历是指在访问根结点、遍历左子树与遍历右子树这三中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树者中，首先遍历左子树，然后访

48、问根结点，最后遍历右子树;并且，在遍历左右子树时，仍然先遍历左子树，然后访问根并且，在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树结点，最后遍历右子树;v（3）后序遍历后序遍历(左右根左右根)v首先遍历左子树，然后遍历右子树，最后访问根结点。首先遍历左子树，然后遍历右子树，最后访问根结点。数据结构与算法数据结构与算法考点考点6：树与二叉树：树与二叉树v查找是数据处理领域中的一个重要内容，查找的效率将直接查找是数据处理领域中的一个重要内容，查找的效率将直接影响到数据处理的效率。所谓查找是指在一个给定的数据结影响到数据处理的效率。所谓查找是指在一个给定的数据结构中查找某个指定的

49、元素。通常，根据不同的数据结构，应构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。采用不同的查找方法。v1顺序查找顺序查找v顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下指定的元素，其基本方法如下:v从线性表的第从线性表的第1个元素开始，依次将线性表中的元素与被查个元素开始，依次将线性表中的元素与被查元素进行比较，若相等，则表示找到元素进行比较，若相等，则表示找到(即查找成功即查找成功);若线性若线性表中所有的元素都与被查元素进行了比较但都不相等，则表表中所有的元素都与被查元素进行了比较

50、但都不相等，则表示线性表中没有要找的元素示线性表中没有要找的元素(即查找失败即查找失败)。数据结构与算法数据结构与算法考点考点7：查找技术：查找技术v2二分查找二分查找v二分查找只适用于顺序存储的有序表二分查找只适用于顺序存储的有序表。在此所说的有序表是在此所说的有序表是指线性表中的元素按值非递减排列指线性表中的元素按值非递减排列(即从小到大，但允许相即从小到大，但允许相邻元素值相等邻元素值相等)。设有序线性表的长度为。设有序线性表的长度为n,被查元素为被查元素为z,则二查找的方法如下。将则二查找的方法如下。将Z与线性表的中间项进行比较与线性表的中间项进行比较:若若中间项的值等于中间项的值等于

51、z，则说明查到，查找结束，则说明查到，查找结束;若若Z小于中间小于中间项的值，则在线性表的前半部分项的值，则在线性表的前半部分(即中间项以前的部分即中间项以前的部分)以以相同的方法进行查找相同的方法进行查找;若若Z大于中间项的值，则在线性表大于中间项的值，则在线性表的后半部分的后半部分(即中间项以后的部分即中间项以后的部分)以相同的方法以相同的方法进行查进行查找。找。在最坏情况下，二分查找只需要比较在最坏情况下，二分查找只需要比较log2n次，而顺序次，而顺序查找需要比较查找需要比较n次。次。数据结构与算法数据结构与算法考点考点7：查找技术：查找技术v排序也是数据处理的重要内容。所谓排序是指将

52、一个排序也是数据处理的重要内容。所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，根据待排序序列的规模以及对数据处理的要求，法有很多，根据待排序序列的规模以及对数据处理的要求，可以采用不同的排序方法可以采用不同的排序方法v冒泡排序：最坏情况下需要比较冒泡排序：最坏情况下需要比较n(n-1)/2v快速排序：在数据基本有序的情况下，不利于发挥其长处。快速排序：在数据基本有序的情况下，不利于发挥其长处。最坏情况下需要比较最坏情况下需要比较n(n-1)/2v简单插入排序法：最坏情况下需要比较简单插入排序法：最坏情况下需要

53、比较n(n-1)/2v希尔排序法：最坏情况下需要比较希尔排序法：最坏情况下需要比较O（n1.5）v简单选择排序法：最坏情况下需要比较简单选择排序法：最坏情况下需要比较n(n-1)/2v堆排序：可以用完全二叉权表示堆的结构，最坏情况下需要堆排序：可以用完全二叉权表示堆的结构，最坏情况下需要比较比较O（nlog2n）数据结构与算法数据结构与算法考点考点8：排序技术：排序技术v练习题练习题v一、选择题一、选择题v1算法的时间复杂度是指算法的时间复杂度是指vA)执行算法程序所需要的时间执行算法程序所需要的时间B)算法程序的长度算法程序的长度vC算法执行所需要的基本运算次数算法执行所需要的基本运算次数D

54、)算法程序中的指令算法程序中的指令条数条数v2算法的空间复杂度是指算法的空间复杂度是指vA)算法程序的长度算法程序的长度B)算法程序中的指令条数算法程序中的指令条数vC)算法程序所占的存储空间算法程序所占的存储空间D)算法执行过程中所需要算法执行过程中所需要的存储空间的存储空间v3下列叙述中正确的是下列叙述中正确的是vA)线性表是线性结构线性表是线性结构B)栈和队列是非线性结构栈和队列是非线性结构vC)线性链表是非线性结构线性链表是非线性结构D)二叉树是线性结构二叉树是线性结构CDAv4数据的存储结构是指数据的存储结构是指vA)数据所占的存储空间量数据所占的存储空间量B)数据在计算机中的存数据

55、在计算机中的存放形式放形式vC)数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式D)存储在外存中的存储在外存中的数据数据v5长度为长度为10的顺序表的首地址是从的顺序表的首地址是从1023开始的开始的,顺序表中每顺序表中每个元素的长度为个元素的长度为2，在第，在第4个元素前面插入一个元素和删除个元素前面插入一个元素和删除第第7个元素后个元素后,顺序表的总长度还是不变。问在执行插入和删顺序表的总长度还是不变。问在执行插入和删除操作前除操作前,顺序表中第顺序表中第5个元素在执行插入和删除操作后的顺个元素在执行插入和删除操作后的顺序表中的存储地址是序表中的存储地址是vA)1028B)1029

56、C)1031D)1033BDv6下列关于线性表的两种存储结构叙述正确的是下列关于线性表的两种存储结构叙述正确的是:vA)存储相同数目的元素线性链表比顺序表要节省存储空间存储相同数目的元素线性链表比顺序表要节省存储空间vB)对无序表的查找对无序表的查找,顺序表和线性链表的效率是一样的顺序表和线性链表的效率是一样的vC)顺序表适用于插入、删除等更新操作频繁的场合顺序表适用于插入、删除等更新操作频繁的场合vD)线性链表适用于查询操作比较频繁的场合线性链表适用于查询操作比较频繁的场合v7下列关于栈的叙述中不正确的是下列关于栈的叙述中不正确的是vA)在栈中只能在同一端插入、删除数据在栈中只能在同一端插入

57、、删除数据B)在栈中只能在一端插入数据，在另一端删除数据在栈中只能在一端插入数据，在另一端删除数据vC)栈是先进后出的线性表栈是先进后出的线性表vD)栈是后进先出的线性表栈是后进先出的线性表BBv8在线性链表的插入算法中在线性链表的插入算法中,若要把结点若要把结点q插在结点插在结点p后面后面,下列操作正确的是下列操作正确的是vA)使结点使结点p指向结点指向结点q,再使结点再使结点q指向结点指向结点p的后件结点的后件结点vB)使结点使结点q指向指向p的后件结点的后件结点,再使结点再使结点p指向结点指向结点qvC)使结点使结点q指向结点指向结点p,再使结点再使结点p指向结点指向结点q的后进结点的后

58、进结点vD)使结点使结点p指向指向q的后件结点的后件结点,再使结点再使结点q指向结点指向结点pv9下列叙述中错误的是下列叙述中错误的是:vA)循环链表中循环链表中,通过表中的任何一个结点可以访问到表中其通过表中的任何一个结点可以访问到表中其他所有的结点他所有的结点vB)对线性链表插入和删除效率比顺序表的效率高对线性链表插入和删除效率比顺序表的效率高vC)线性链表与顺序表相比线性链表与顺序表相比,它容易实现动态增长它容易实现动态增长vD)在线性链表中查找一个元素要比在顺序表中查找一个元在线性链表中查找一个元素要比在顺序表中查找一个元素快素快BD10.下面排序算法中下面排序算法中,平均排序速度最快

59、的是平均排序速度最快的是A)冒泡排序法冒泡排序法B)选择排序法选择排序法C)交换排序法交换排序法D)堆排序法堆排序法O（n2）O（n2）O（n2）O(nlog2n)11.设栈和队列设栈和队列Q的初始状态为空，元素的初始状态为空，元素a,b,c,d,e,f依依次通过栈次通过栈S，并且一个元素出栈后即进入队列，并且一个元素出栈后即进入队列Q，若出队的顺序为若出队的顺序为b,d,c,f,e,a，则栈，则栈S的容量至少应该的容量至少应该为：为：A)3B)4C)5D)613在下列数据结构中，不是线性结构的是：在下列数据结构中，不是线性结构的是：A)线性链表线性链表B)带链的栈带链的栈C)循环链表循环链表

60、D)二叉树二叉树DAD14在下列数据结构中按先进后出原则组织数在下列数据结构中按先进后出原则组织数据的是据的是A)循环队列循环队列B)栈栈C)循环链表循环链表D)顺序表顺序表15下列数据结构中具有记忆功能的是下列数据结构中具有记忆功能的是A)队列队列B)循环队列循环队列C)栈栈D)顺序表顺序表BC16设有下列二叉树：对此二叉树前序遍历的结果是：设有下列二叉树：对此二叉树前序遍历的结果是：ATXBCPZYA)ZBTYCPXAB)ATBZXCYPC)ZBTACYXPD)ATBZXCPYBv二、填空题二、填空题v1假如刚开始时栈为空假如刚开始时栈为空,依次有依次有A,B,C,D四个元素入四个元素入栈

61、栈,此时找底指针指向元素此时找底指针指向元素,栈顶指针值为栈顶指针值为(假设每个假设每个元素的长度为元素的长度为1)。执行四次出栈操作后把。执行四次出栈操作后把E,F,G压入栈压入栈,问此时栈底指针指向元素问此时栈底指针指向元素,此时栈的长度为此时栈的长度为。1)A2)43)E4)3v2一个容量为一个容量为8的循环队列的循环队列,当它的队首和队尾指针当它的队首和队尾指针相等时相等时(front=rear)时队列中有时队列中有()个有效数据。个有效数据。v3.请写出用二分查找法在有序顺序表请写出用二分查找法在有序顺序表(1,2,3,4,6,8,9,11)中查找中查找3的比较序列的比较序列()。4

62、请写出用冒泡排序法对序列请写出用冒泡排序法对序列(5,1,7,3,1,6,9,3,2,7,6)从前往后进行第一遍扫描后从前往后进行第一遍扫描后的中间结果的中间结果()。1)082)4.2.33)1531672769v5.数据结构分为逻辑结构与存储结构，线性数据结构分为逻辑结构与存储结构，线性链表属于链表属于()。v6在一个容量为在一个容量为25的循环队列中，若头指的循环队列中，若头指针针front=16，尾指针，尾指针rear=9，则该循环队列，则该循环队列中共有中共有()个元素。个元素。v7在长度为在长度为n的线性表中查找一个表中不存的线性表中查找一个表中不存在的元素，需要的比较次数为在的元素，需要的比较次数为()。1)存储存储2)183)n