二级公共基础知识部分课件

《二级公共基础知识部分课件》由会员分享，可在线阅读，更多相关《二级公共基础知识部分课件（116页珍藏版）》请在装配图网上搜索。

1、1二级公共基础知识部分2345考试内容基本数据结构与算法基本数据结构与算法程序设计基础程序设计基础软件工程基础软件工程基础数据库设计基础数据库设计基础内容内容2008/92009/42009/92010/42010/910108212846128461028101028106考试方式考试方式1、 公共基础的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C+）的笔试部分合为一张试卷。公共基础部分占全卷的30分。2、 公共基础知识有10道选择题和5道填空题。 7学习方法学习方法l理解基本概念l多做练习l适当记忆一些名词l与所学的

2、VFPcAccess程序设计知识结合起来，以增加对知识的理解能力8 9基本要求 l1. 掌握算法的基本概念。l2. 掌握基本数据结构数据结构及其操作。l3. 掌握基本排序和查找算法。l4. 掌握逐步求精的结构化程序设计程序设计方法。l5. 掌握软件工程软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。l6. 掌握数据库数据库的基本知识，了解关系数据库的设计。 10algorithm1 1、算法的基本概念、算法的基本概念 算法是指解题方案的准确而完整的描述。它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺

3、序将在有限的次数下终止。111.1 算法算法1 算法(algorithm)基本概念一级算法一级算法:S1:输入圆的半径输入圆的半径r;S2:求周长求周长2r;S3:求面积求面积 r2;S4:输出周长和面积输出周长和面积;例题例题1:已知圆的半径已知圆的半径,求周长和面积求周长和面积.程序程序12算法的基本特征算法的基本特征:(1)可行性可行性(2)确定性确定性(3)有穷性有穷性(4)输入和输出（输入和输出（拥有足够的情报拥有足够的情报）132 2、算法的基本要素、算法的基本要素v 对数据对象的运算和操作： 算术运算、逻辑运算、关系运算、数据传输 算法中各操作之间的执行顺序； 描述算法的工具通常

4、有传统流程图、N-S结构化流程 图、算法描述语言等； 一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。v 算法的控制结构： 143 3、算法设计的基本方法、算法设计的基本方法v 列举法v 归纳法v 递推v 递归（以简洁的形式设计和描述算法）v 减半递推技术v 回溯法151.2.1 时间复杂度 是指执行算法所需要的计算工作量。是指执行算法所需要的计算工作量。 通常有事后统计法和通常有事后统计法和事前分析估算法事前分析估算法。算法在执行过程中所需算法在执行过程中所需基本运算的执行次数基本运算的执行次数来度量算法来度量算法的工作量的工作量.算法所执行的基本运算次数与算法所执行的基本运算次数

5、与问题的规模问题的规模n有关有关.执行算法所需要的计算工作量和执行算法所需要的计算工作量和f(n)同步增长，记为同步增长，记为:算法的工作量算法的工作量=f(n)时间复杂度时间复杂度=O(f(n)16例子例子4：for ( i=2 ;i=n;+i) for (j=2 ;j=i-1;+j) +x ;基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：X增增1i=2 0i=3 1i=4 2i=n n-2 1+2+3+(n-2)= (n-1)(n-2)/2O（ ）2n例子例子2：+x;O（ 1 ）例子例子3： for (i=1 ;i=n;+i) +x;O（ n ）时间复杂度：时间复杂度：O(

6、n*n-3n+2)/2)基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：1X增增1基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：X增增1n171 1、时间复杂度、时间复杂度v 在同一问题规模下，如果算法执行所需要的基本运算次数取决于某一特定输入时，可以用以下方法分析工作量：平均性态和最坏情况复杂性。182 2、空间复杂度、空间复杂度v 一般是指执行这个算法所需要的内存空间。v 一个算法所占用的存储空间包括算法程序所占的空间、 输入的初始数据所占的存储空间以及某种数据结构所需 要的附加存储空间。v 一个上机执行的程序除了需

7、要存储空间来寄存本身所用 指令、常数、变量和输入数据外，也需要一些对数据进 行操作的工作单元和存储一些为实现计算所需信息的辅 助空间。19l 算法的时间复杂度是指算法的时间复杂度是指A) 执行算法程序所需要的时间执行算法程序所需要的时间 B) 算法程序的长度算法程序的长度C) 算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数算法程序中的指令条数l算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。和拥有足够的情报。l算法的空间复杂度是指算法的空间复杂度是指 A) 算法程序的长度算法程序的长度 B) 算法程序

8、中的指令条数算法程序中的指令条数 C) 算法程序所占的存储空间算法程序所占的存储空间 D) 执行过程中所需要的存储空间执行过程中所需要的存储空间l在计算机中，算法是指在计算机中，算法是指 A) 加工方法加工方法B) 解题方案的准确而完整的描述解题方案的准确而完整的描述 C) 排序方法排序方法D) 查询方法查询方法例题讲解有穷性有穷性20l法的工作量大小和实现算法所需的存储单元多少分别称为算法的法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【1】 。时间复杂度和空间复杂度时间复杂度和空间复杂度21Data Structure1 1、数据结构研究的主要内容、数据结构研究的主要内容v 当

9、今计算机应用的特点： 1、所处理的数据量大且具有一定的关系； 2、对其操作不再是单纯的数值计算，而更多地是需 要对其进行组织、管理和检索。 对数据的讨论不单单是数据本身，还要包括数据与对数据的讨论不单单是数据本身，还要包括数据与数据之间的关系。数据之间的关系。22数据结构研究的主要内容(1)数据集中数据之间的逻辑关系数据集中数据之间的逻辑关系,即数据的逻辑结构即数据的逻辑结构线性线性树树图图(2)数据的存储结构数据的存储结构(3)对各种数据结构进行的运算对各种数据结构进行的运算23 学 生 基 本 情 况 学 号 姓 名 性 别 出 生 年 月 . 99070101 李 军 男 80 12 .

10、 99070102 王 颜 霞 女 81 2 . 99070103 孙 涛 男 80 9 . 99070104 单 晓 宏 男 81 3 . . . . . . 特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。v 应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。24v 应用举例2家庭血缘关系图 表示家庭成员的辈分关系，使用下图1-1所示的形式描述。3 1

11、 21 3 21 2 31 23 2 12 3 12 1 32 11家庭血缘关系图特点： 在求解过程中，所处理的数据之间具有层次关系，这是我们 所说的树形结构； 对它的操作有：建立树形结构，输出结点内容等等。25v 应用举例3制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示： 计算机专业学生的必修课程 课课程程编编号号 课课程程名名称称 需需要要的的先先导导 课课程程编编号号 C 1 程序设计基础 无 C 2 离散数学 C 1 C 3 数据结构 C 1 ，C 2 C 4

12、 汇编语言 C 1 C 5 算法分析与设计 C 3 ，C 4 C 6 计算机组成原理 C 1 1 C 7 编译原理 C 5 ，C 3 C 8 操作系统 C 3 ，C 6 C 9 高等数学 无 C 1 0 线性代数 C 9 C 1 1 普通物理 C 9 C 1 2 数值分析 C 9 ，C 1 0 ，C 1 25这种数据可以用下面的图来表示：26v 课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图 1-2 计算机专业必修课程开设先后关系2627 1 1、数据的、数据的逻辑结构逻辑结构 2 2、数据的、数据的存储结构存储结构 3 3、数据的、数据的运算运算：检索、排

13、序、插入、删除、修改等。：检索、排序、插入、删除、修改等。 A A线性结构线性结构B B非线性结构非线性结构A A顺序存储顺序存储 B B链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面(亦称物理结构亦称物理结构)数据结构的主要研究问题：27282 2、什么是数据结构？、什么是数据结构？ 数据结构是一门研究组织组织、存储存储和运算运算的一般方法的学科。例：整数整数(1,2)、实数实数(1.1,1.2)字符串字符串(Beijing)、图形图形、声音声音。计算机管理图书问题 ： 在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类

14、编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如：2829数据元素在计算机中的表示 数据结构是一门研究组织组织、存储存储和运算运算的一般方法的学科。如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9 对数据结构中的节点进行操作处理对数据结构中的节点进行操作处理（插入、删除、修改、查找、排序）（插入、删除、修改、查找、排序）2

15、930v 数据元素数据元素( (Data Element)Data Element) 数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元素可由若干数据项数据项(Data ItemData Item)组成。数据项是数据的最小单位。数据元素亦称节点节点或记录记录。数据结构可描述为数据结构可描述为 Group=Group=（D D，R R）有限个数据元素的集合有限个数据元素的集合有限个节点间关系的集合有限个节点间关系的集合3031数据结构可描述为数据结构可描述为 Group=（D，R）l 例例1：一年四季的数据结构可表示成：一年四季的数据结构可表示成B=（D，R） D=春，夏，秋，冬春，

16、夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）l 例例2：家庭成员数据结构可表示成：家庭成员数据结构可表示成B=（D，R）D=父亲，儿子，女儿父亲，儿子，女儿 R=（父亲，儿子），（父亲，女儿）（父亲，儿子），（父亲，女儿）冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿32数据结构也可用图形表示数据结构也可用图形表示l一年四季的数据结构可表示成一年四季的数据结构可表示成l家庭成员数据结构可表示成家庭成员数据结构可表示成冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿（ 概念：结点、前件、后件、根结点、叶子 ）33v 树形结构全校学生档案管理的组织方式全校学生档案管理的组

17、织方式计算机程序管理系统也是典型的计算机程序管理系统也是典型的树形结构树形结构。34HGFECDBA351 14 42 23 3 D=1 , 2 , 3 , 4 D=1 , 2 , 3 , 4R=(1,2),(1,3), R=(1,2),(1,3), (1,4),(2,3), (1,4),(2,3), (3,4),(2,4) (3,4),(2,4) 2 21 13 3 D= 1 , 2 , 3 D= 1 , 2 , 3 R=(1,2),(2,3),(3,2),(1,3) R=(1,2),(2,3),(3,2),(1,3)v 图形结构图形结构节点间的连结是任意的节点间的连结是任意的363 3、例

18、题讲解、例题讲解v 数据处理的最小单位是数据处理的最小单位是( )( ) A)A)数据数据 B)B)数据元素数据元素 C) C) 数据项数据项 D) D) 数据结构数据结构v 数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及( )( ) A) A) 数据的存储结构数据的存储结构 B) B) 计算方法计算方法 C) C) 数据映象数据映象 D) D) 逻辑存储逻辑存储v 数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【4 4】 以及对数据的以及对数据的操

19、作运算。操作运算。C CA A【答案【答案】物理结构（或存储结构）物理结构（或存储结构）373 3、线性结构与非线性结构：、线性结构与非线性结构：v 线性结构：有且只有一个根结点；每一个线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。结点最多有一个前件，也最多有一个后件。 如：一年四季，如：一年四季，2626个英文字母个英文字母v非线性结构：线性以外的数据结构。非线性结构：线性以外的数据结构。 如：反映家庭成员间辈分关系的数据结构如：反映家庭成员间辈分关系的数据结构 384、线性表、线性表（Linear List）学学 生生 成成 绩绩 表表 ( (按成绩排列按成绩排

20、列) )86胡孝臣95刘忠赏100张卓成 绩姓 名学 号v 线性表线性表结点间是以线性关系联结：结点间是以线性关系联结：v 线性表线性表：具有线性结构的有限序列。 数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。39v 线性表的定义线性表的定义: : 线性表线性表是是n n个元素的有限序列，它们之间的关系可以排成个元素的有限序列，它们之间的关系可以排成一个线性序列：一个线性序列：a1a1，a2a2， ，aiai， ，anan 其中其中n n称作表的称作表的长度长度，当，当n=0n=0时，称作时，称作空表空表。v 线性表的特点：线性表的特点： 1 1、线性表中所

21、有元素的性质相同。、线性表中所有元素的性质相同。 2 2、除第一个和最后一个数据元素之外，其它数据元素有且、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱，最仅有一个前驱和一个后继。第一个数据元素无前驱，最 后一个数据元素无后继。后一个数据元素无后继。 3 3、数据元素在表中的位置只取决于它自身的序号。、数据元素在表中的位置只取决于它自身的序号。v 在线性表上常用的运算有：在线性表上常用的运算有： 初始化、求长度、取元素、修改、前插、删除、检索、排序初始化、求长度、取元素、修改、前插、删除、检索、排序3940v 线性表的线性表的 顺序存储结构 及

22、其及其 插入 与与 删除 操作操作 特点：特点： 1 1、线性表中数据元素类型一致，只有数据域，存储空间、线性表中数据元素类型一致，只有数据域，存储空间 利用率高。利用率高。 2 2、所有元素所占的存储空间是连续的。、所有元素所占的存储空间是连续的。 3 3、各数据元素在存储空间中是按逻辑顺序依次存放的、各数据元素在存储空间中是按逻辑顺序依次存放的 （a a）做插入、删除时需移动大量元素。做插入、删除时需移动大量元素。 （b b）空间估计不明时，按最大空间分配。空间估计不明时，按最大空间分配。41顺顺序序存存储储存储地址存储地址存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素

23、元素1 1L Lo o + + mL Lo o+(i-1)+(i-1)mLo+Lo+（n-1)n-1)mLoc(Loc(元素元素i)=Li)=Lo o+ +（i-1)i-1)m每个元素所占用每个元素所占用的存储单元个数的存储单元个数v 线性表的线性表的 顺序存储结构顺序存储结构：首地址首地址起始地址起始地址基地址基地址42元素元素a a1 1元素元素a a2 2.元素元素a ai+1i+1. 0 0 1 1i i 线性表的顺序存储结构线性表的顺序存储结构可用可用C C语言中的一维数组来描述语言中的一维数组来描述. .第第i i个元素的个元素的a ai i存储地址：存储地址：Loc(aLoc(a

24、i i)=Loc(a)=Loc(a1 1)+(i-1)+(i-1)* * m mVV VV ViViVm-1Vm-1 int VM; int VM; 其中：其中：V V是数组的名字，是数组的名字，M M是数组大小，是数组大小， 假设数组中的元素是整型类型假设数组中的元素是整型类型43v插入运算插入运算.a2a a1 1an.ai+1ai01i-1in-1a ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai i x x a ai-1i-1. a a2 2 a a1 1 X X a ai ia ai+1i+1.a alengtlength h 插入

25、算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：1n1iis2n1)i(n1n1E4344在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。n1idl21ni)(nn1Ev删除算法的分析删除算法的分析4445 顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。v 顺序存储结构的三个缺

26、点： 1.作插入或删除操作时，需移动大量元数。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素元素1 14546q 线性表的例题讲解线性表的例题讲解v 顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【1 1】 的存储单元中。的存储单元中。 长度为长度为n n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元 素概率都相等时，插入一个元素所需移动元素的平均个数素概率都相等时，插入一个元素所需移动元素的平均个数 为为【2 2】 。v

27、 线性表线性表L=(a1,a2,a3,aiL=(a1,a2,a3,ai，an)an)，下列说法正确的是（）下列说法正确的是（） A) A) 每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B) B) 线性表中至少要有一个元素线性表中至少要有一个元素 C) C) 表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D) D) 除第一个元素和最后一个元素外，其余每个元素都有一除第一个元素和最后一个元素外，其余每个元素都有一 个且只有一个直接前件和直接后件个且只有一个直接前件和直接后件 46【答案【答案】相邻相邻【答案【答案】 n/2n/2

28、D D47v 数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的( )( ) A) A) 存储结构存储结构B) B) 物理结构物理结构 C) C) 逻辑结构逻辑结构D) D) 物理和存储结构物理和存储结构 下列叙述中，错误的是下列叙述中，错误的是（ ） A) A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) D) 一种数据的逻辑结构

29、可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 数据的存储结构是指数据的存储结构是指（ ） A A）数据所占的存储空间数据所占的存储空间 B B）数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示 C C）数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D D）存储在外存中的数据存储在外存中的数据C C B BB B48 根据数据结构中各数据元素之间前后件关系的复杂程度，一般根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成将数据结构分成( ( C C ) ) A) A) 动态结构和静态结构动态结构和静态结构 B) B) 紧凑结构和非紧凑结构紧凑结

30、构和非紧凑结构 C) C) 线性结构和非线性结构线性结构和非线性结构 D) D) 内部结构和外部结构内部结构和外部结构 数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【2 2】两大类。两大类。非线性结构非线性结构 当线性表采用顺序存储结构实现存储时，其主要特点是当线性表采用顺序存储结构实现存储时，其主要特点是【1】。 【答案【答案】逻辑结构中相邻的结点在存储结构中仍相邻。逻辑结构中相邻的结点在存储结构中仍相邻。48495 栈和队列栈和队列1.7.1 栈和队列的定义栈和队列的定义 栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某是两种特殊的线性表，它们是运算时要受到某些限制的线性

31、表，故也称为些限制的线性表，故也称为限定性的数据结构限定性的数据结构。501 .栈栈栈栈是限定仅在表尾进行插入或删除操作的线性表。是限定仅在表尾进行插入或删除操作的线性表。栈顶栈顶表尾。表尾。栈底栈底表头。表头。空栈空栈不含元素的空表。不含元素的空表。a1a2an栈底栈底栈顶栈顶进栈进栈出栈出栈栈栈s=(a1,a2,an)后进先出后进先出（LIFO）512. 栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算 a2 a1 a1 a2 top 用顺序存储结构表示的栈用顺序存储结构表示的栈: 顺序栈用一组连续的存储单元存放自栈底到栈顶的数据顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素

32、，一般用一维数组表示，设置一个简单变量元素，一般用一维数组表示，设置一个简单变量top指示栈顶位指示栈顶位置，称为置，称为栈顶指针，它始终指向待插入元素的位置栈顶指针，它始终指向待插入元素的位置。基本运算：基本运算：压（进）栈：压（进）栈：PUSH出栈：出栈：POP读栈顶元素：读栈顶元素：gettop52例子：例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：空桟：topbase非空桟：非空桟：top始终在桟顶元素始终在桟顶元素上溢上溢下溢下溢53v 队列的定义队列的定义队列：队列：一种特殊的线性结构，限定只能在表的一端进行插入，一种特殊的线性结构，限定只能

33、在表的一端进行插入， 在表的另一端进行删除的线性表在表的另一端进行删除的线性表 。此种结构称为。此种结构称为先进先进 先出（先出（FIFO）表表。 a1 , a2 , a3 , a4 , an-1 , an队队 列列 示示 意意 图图队头队头队尾队尾v 队列的主要运算队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；5354 e3 e4 (c)e1,e2出队，出队，e4入队入队 队队 满满rear =3front e1 e2 e3 (b)rearfront(b)e1,e2,e3入队入队4.队列的顺序存储结构及其基本运算队

34、列的顺序存储结构及其基本运算 3 2 1 0 (a)rear=front=-1(队空）队空）rearfront空队列空队列:非空队列非空队列:队列元素个数队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终始终指向队尾元素的位置指向队尾元素的位置rear-front55q 堆栈和队列的例题讲解堆栈和队列的例题讲解v栈和队列的共同特点是（栈和队列的共同特点是（ ） A)A)都是先进先出都是先进先出 B) B) 都是先进后出都是先进后出 C) C) 只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D) D) 没有共同点

35、没有共同点v如果进栈序列为如果进栈序列为e1,e2,e3,e4e1,e2,e3,e4，则可能的出栈序列是（则可能的出栈序列是（ ） A) e3,e1,e4,e2 B) e4,e3,e2,e1 A) e3,e1,e4,e2 B) e4,e3,e2,e1 C) e3,e4,e1,e2 C) e3,e4,e1,e2 D) D) 任意顺序任意顺序v一些重要的程序语言一些重要的程序语言( (如如C C语言和语言和PascalPascal语言语言) ) 允许过程的允许过程的递归调用。而实现递归调用中的存储分配通常用（递归调用。而实现递归调用中的存储分配通常用（ ） A) A) 栈栈 B) B) 堆堆 C)

36、 C) 数组数组 D) D) 链表链表 5556v 栈底至栈顶依次存放元素栈底至栈顶依次存放元素A A、B B、C C、D D，在第五个元素在第五个元素E E 入栈前，栈中元素可以出栈，则出栈序列可能是（入栈前，栈中元素可以出栈，则出栈序列可能是（ ） A) ABCEDA) ABCED B) DCBEA B) DCBEA C) DBCEA C) DBCEA D) CDABE D) CDABE v 栈通常采用的两种存储结构是（栈通常采用的两种存储结构是（ ） A) A) 顺序存储结构和链表存储结构顺序存储结构和链表存储结构 B) B) 散列方式和索引方式散列方式和索引方式 C) C) 链表存储结

37、构和数组链表存储结构和数组 D) D) 线性存储结构和非线性存储结构线性存储结构和非线性存储结构v 栈和队列通常采用的存储结构是栈和队列通常采用的存储结构是 【1 1】。 【答案【答案】链式存储和顺序存储链式存储和顺序存储v 下列数据结构中，按先进后出原则组织数据的是（下列数据结构中，按先进后出原则组织数据的是（ ） A) A) 线性链表线性链表 B) B) 栈栈 C) C) 循环链表循环链表 D) D) 顺序表顺序表 5657v 当循环队列非空且队尾指针等于队头指针时，说明循环队列当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为已满，不能进行入队运算。

38、这种情况称为【2 2】。v 由两个栈共享一个存储空间的好处是（由两个栈共享一个存储空间的好处是（ ） A) A) 减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 B) B) 节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率 C) C) 减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 D) D) 节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率v 下列关于栈的叙述中正确的是（下列关于栈的叙述中正确的是（ ）) )在栈中只能插入数据在栈中只能插入数据 B B）在栈中只能删除数据在栈中只能删除数据C C）栈是先进先出的线性表栈是先进

39、先出的线性表 D D）栈是后进先出的线性表栈是后进先出的线性表v 下列关于队列的叙述中正确的是（下列关于队列的叙述中正确的是（ ）在队列中只能插入数据）在队列中只能插入数据 B B）在队列中只能删除数据在队列中只能删除数据C C）队列是先进先出的线性表队列是先进先出的线性表 D D）队列是后进先出的线性表队列是后进先出的线性表 57答案：答案：上溢上溢58 顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。v 顺序存储结构的三个缺点： 1.作插入或删除操作时，需移动大量元数。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。存储内容存储内容元素元

40、素n n.元素元素i i.元素元素2 2元素元素1 158596 6、线性链表、线性链表v线性链表的基本概念：线性链表的基本概念： 线性表的链式存储结构称为线性表的链式存储结构称为线性链表线性链表。 为了适应线性表的链式存储结构，计为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存一小块占若干字节，通常称这些小块为存储结点。储结点。60将存储空间中的每一个存储结点分为两部：v一部分称为数据域，用于存储数据元素的值；v另一部分称为指针域，用于存放下一个数据元素的存储序号（即存储结点的地址），也就是指向后件结

41、点. 线性链表中存储结点的结构如图2.20所示60611、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。2、逻辑上相邻的节点物理上不必相邻。3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。4、查找结点时链式存储要比顺序存储慢。v 链接存储结构特点：链接存储结构特点：62 指向线性表中第一个结点的指针指向线性表中第一个结点的指针HEADHEAD称为称为头指针头指针。 当当HEAD=NULLHEAD=NULL（或（或0 0）时称为）时称为空表空表。 对于线性链表，可以从头指针开始，沿着各对于线性链表，可以从头指针开始，沿

42、着各个结点的指针扫描到链表中的所有结点。个结点的指针扫描到链表中的所有结点。线性链表的逻辑结构图所示63v 线性链表的基本运算：线性链表的基本运算：线性链表的运算主要有以下几个：线性链表的运算主要有以下几个： 在线性链表中包含指定元素的结点之前在线性链表中包含指定元素的结点之前 插入插入一个新元素。一个新元素。 在线性链表中在线性链表中删除删除包含指定元素的结点。包含指定元素的结点。 将两个线性链表按要求将两个线性链表按要求合并合并成一个线性成一个线性 链表。链表。64 线性链表的线性链表的 插入插入 运算：运算： 线性链表的插入线性链表的插入是指在链式存储结构下是指在链式存储结构下的线性表中

43、插入一个新元素。的线性表中插入一个新元素。 为了要在线性链表中插入一个新元素，为了要在线性链表中插入一个新元素，首先首先要给该元素分配一个新结点，然后将存要给该元素分配一个新结点，然后将存放新元素值的结点放新元素值的结点链接链接到线性链表中指定的到线性链表中指定的位置。位置。65baPbaP1-1单链表的插入运算单链表的插入运算xS在在P所指向的结点之后插入新的结点所指向的结点之后插入新的结点666667 线性链表的删除线性链表的删除指在链式存储结构下的指在链式存储结构下的线性表中删除包含指定元素的结点。线性表中删除包含指定元素的结点。 为了在线性链表中删除包含指定元素的为了在线性链表中删除包

44、含指定元素的结点，首先要在线性链表中找到这个结点，结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。然后将要删除结点放回到可利用栈。 线性链表的线性链表的 删除删除 运算：运算：681-2单链表单链表删除运算删除运算Laaian ai-1ai+1要求要求:删除结点删除结点ai。696970 循环链表的结构与前面所讨论的线性链表相比，具有以下循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：两个特点： 循环链表的头指针指向表头结点。循环链表的头指针指向表头结点。 在循环链表中，所有结点的指针构成了一个在循环链表中，所有结点的指针构成了一个环状链环状链。 v循环链表：

45、循环链表：7071 在实际应用中，循环链表与线性单链表相在实际应用中，循环链表与线性单链表相比主要有以下两个方面的优点：比主要有以下两个方面的优点： 在循环链表中，只要指出表中任何一个结点在循环链表中，只要指出表中任何一个结点 的位置，就可以从它出发访问到表中其他所的位置，就可以从它出发访问到表中其他所 有的结点。有的结点。 由于在循环链表中设置了一个表头结点，因由于在循环链表中设置了一个表头结点，因 此，在任何情况下，循环链表中至少有一个此，在任何情况下，循环链表中至少有一个 结点存在，从而使空表与非空表的运算统一。结点存在，从而使空表与非空表的运算统一。727273双向链表双向链表 在每个

46、结点中设置两个指针，一个指向后继，一个在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。高效率。datanextbefore线性表的应用：应用最广的数据结构。线性表的应用：应用最广的数据结构。.高级语言中的数组；高级语言中的数组；计算机的文件系统；计算机的文件系统；计算机的目录系统；计算机的目录系统；电话号码查询系统（可采用顺序表或单链表结构电话号码查询系统（可采用顺序表或单链表结构）；）；各种事务处理（各种事务处理（可采用顺序表或单链表结构可采用顺序表或单链表结构）;74l链表不具有的特点是

47、链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比l数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1】 。 l数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的 A) 存储结构存储结构B) 物理结构物理结构 C) 逻辑结构逻辑结构D) 物理和存储结构物理和存储结构 l数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【1】 两大类两大类。l数据的存

48、储结构是指数据的存储结构是指A）数据所占的存储空间）数据所占的存储空间B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据 例题讲解存储结构存储结构 非线性结构非线性结构75l顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元中。的存储单元中。 l数据处理的最小单位是数据处理的最小单位是 A) 数据数据 B) 数据元素数据元素 C) 数据项数据项 D) 数据结构数据结构l数据结构作为计算机的一门学科，主要研究数据的逻

49、辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及 A) 数据的存储结构数据的存储结构 B) 计算方法计算方法 C) 数据映象数据映象 D) 逻辑存储逻辑存储l线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存

50、储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 相邻相邻76l根据数据结构中各数据元素之间前后件关系的复杂程度，一根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成般将数据结构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构 l数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【2】 以及对数据以及对数据的操作运算。的操作运算。l数据的基本单位是数据的基本单位是 【5】 。l下列叙述中，错误的是下列叙

51、述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构存储结构存储结构数据元素数据元素771.61.6、树与二叉树：、树与二叉树：v 树的基本概念：树的基本概念： 前面我们讨论的线性表，栈、队列和数前面我们讨论的线性表，栈、队列和数组等都是组等都是线性结构线性结构。而。而树树是一种是一种非线性数

52、据非线性数据结构结构，它的每一个结点，都可以有不止一个，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组一个直接前趋。这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次织起来，清晰地反映了数据元素之间的层次关系。关系。 781.6.1 树的定义树的定义 由一个或多个结点组成的有限集合。仅有一个根结点，结由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。点间有明显的层次结构关系。 A C G T2D H I T3J M B E LKT1 F现实世界中，能用树的结

53、构表示的例子：现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。学校的行政关系、书的层次结构、人类的家族血缘关系等。1.6 树树797980介绍几个概念：介绍几个概念：结点结点（Node）：树中的元素，包含数据项及若干指向其）：树中的元素，包含数据项及若干指向其子树的分支。子树的分支。结点的度结点的度（Degree）：结点拥有的子树数。）：结点拥有的子树数。结点的层次：结点的层次：从根结点开始算起，根为第一层。从根结点开始算起，根为第一层。叶子叶子（Leaf）：度为零的结点，也称端结点。）：度为零的结点，也称端结点。孩子孩子（Child）：结点子树的根称为

54、该结点的孩子结点。）：结点子树的根称为该结点的孩子结点。兄弟兄弟（Sibling）：）：同一双亲的孩子。同一双亲的孩子。双亲双亲（Parent）：孩子结点的上层结点，称为这些结点的）：孩子结点的上层结点，称为这些结点的 双亲。双亲。树的深度树的深度（Depth)： 树中结点的最大层次数。树中结点的最大层次数。树的度：树的度：结点所具有的最大的度结点所具有的最大的度.森林森林（Forest）：）：M棵互不相交的树的集合。棵互不相交的树的集合。 A C G T2D H I T3J M B E LKT1 F81 二叉树二叉树( (binary tree)binary tree)是一种很有用的非线是一

55、种很有用的非线性结构。性结构。 二叉树具有以下两个特点：二叉树具有以下两个特点：（1 1）非空二叉树只有一个根结点；）非空二叉树只有一个根结点；（2 2）每一个结点最多有两棵子树，且分别）每一个结点最多有两棵子树，且分别 称为该结点的左子树与右子树。称为该结点的左子树与右子树。v 二叉树（二叉树（Binary TreeBinary Tree）：）：因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论81828283性质性质1 1：二叉树的第k层上至多有2 k-1（i 1）个结点二叉树的性质：二叉树的性质：423167891011121314155第三层上(i=3)，

56、有23-1=4个节点。第四层上(i=4)，有24-1=8个节点。84二叉树的性质：二叉树的性质：性质性质2 2：深度为深度为h h的二叉树中至多含有的二叉树中至多含有2 2h h-1 -1个结点个结点423167891011121314155此树的深度此树的深度h=4h=4，共有共有2 24 4-1=15-1=15个节点。个节点。85性质性质3 3：在任意一棵二叉树中，度为0的结点 （即叶子结点）总是比度为2的结点多一个。二叉树的性质：二叉树的性质：85 性质：对任何一棵二叉树性质：对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0,度为度为2的结点数为的结点数为n2,则则n0=n

57、2+1。例例1 1：某二叉树中度为2的结点有18个，则 该二叉树中有 个叶子结点。191986v满二叉树与完全二叉树满二叉树与完全二叉树 满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。 完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 注意：满二叉树是完全二叉树，完全二叉树不一定是满二叉树。87v 满二叉树的特点：满二叉树的特点：每一层上都含有最大结点数。每一层上都含有最大结点数。8788v完全二叉树的特点：完全二叉树的特点：除最后一层外，每一层都取最大除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的

58、若干位置结点数，最后一层结点都集中在该层最左边的若干位置8889 对于对于完全二叉树完全二叉树而言而言如果它的结点个数为如果它的结点个数为偶偶数，则该二叉树中：数，则该二叉树中：叶子结点的个数叶子结点的个数=非叶子结点的个数非叶子结点的个数如果它的结点个数为如果它的结点个数为奇奇数，则该二叉树中：数，则该二叉树中：叶子结点的个数叶子结点的个数=非叶子结点的个数非叶子结点的个数+1+1（即叶子结点数比非叶子结点数（即叶子结点数比非叶子结点数多一个多一个）规律总结：规律总结：90v 例题讲解例题讲解1、设一棵完全二叉树共有700个结点，则在该二叉树中有 个叶子结点。2、在深度为5的满二叉树中，叶子

59、结点的 个数为（ ） A) 32 B) 31 C) 16 D) 15 35035091树与二叉树的区别A树和二叉树的结点个数最少都可为0。B树中结点的最大度数没有限制，二叉树结点最大度数为2。C树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。3个结点的个结点的树树3个结点的个结点的二叉二叉树树92v二叉树的存储二叉树的存储 二叉树通常采用链式存储结构。存储结点由两部分组成：数据域数据域、指针域。其中指针域有两个：左指针域、右指针域其中指针域有两个：左指针域、右指针域 因此二叉树的链式存储结构也称为二叉链表因此二叉树的链式存储结构也称为二叉链表92932、二叉树的存储结构、二叉树的存储

60、结构 (2) 链式存储结构链式存储结构T16若父结点在数组中若父结点在数组中i下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处。处。11 A B c F E D 1 2 4 8 910 5 6 3 712131415(1) 顺序存储结构顺序存储结构(1) 顺序存储结构顺序存储结构2h-1= 24-1 = 15用一组连续的存储单元存放二叉树用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。位置蕴含着结点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须

61、按完全二叉树的形式存储，将造成存储的浪费。一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。94(2)、链式存储结构、链式存储结构链式存储结构链式存储结构二叉链表二叉链表三叉链表三叉链表二叉链表：二叉链表：二叉链表的结点包含三个域：数据域、左、右指针域。二叉链表的结点包含三个域：数据域、左、右指针域。例：例：ABCDEFG A B C D E F G 95三叉链表：三叉链表：三叉链表的结点包含四个域：三叉链表的结点包含四个域： 数据域、左、右、双亲指针域。数据域、左、右、双亲指针域。例：例：ABCDEFG A B C D E F G 链式存储结构的特点：链式存储结构的特点： （1）操作便

62、于实现）操作便于实现 （2）结构复杂）结构复杂96v二叉树的遍历二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。 二叉树的遍历可以分为三种：前序前序遍历、中中序序遍历、后序后序遍历。 设访问根结点记作设访问根结点记作V V；遍历根的左子树记作遍历根的左子树记作L L；遍历根的右子树记作遍历根的右子树记作R R； 前序：前序： VLRVLR（即即根根左右）左右） 中序：中序： LVRLVR（即左即左根根右）右） 后序：后序： LRVLRV（即左右即左右根根）969797981 1、设一棵二叉树的中序遍历结果为、设一棵二叉树的中序遍历结果为DBEAFC,DBEAFC, 前序遍历结果为

63、前序遍历结果为ABDECFABDECF，则后序遍历结则后序遍历结 果为：果为：v 例题讲解例题讲解2 2、已知一棵二叉树前序遍历和中序遍历分别、已知一棵二叉树前序遍历和中序遍历分别 为为ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，则该二叉树则该二叉树 的后序遍历为（的后序遍历为（ ） A) GEDHFBCA A) GEDHFBCA B) DGEBHFCA B) DGEBHFCA C) ABCDEFGH C) ABCDEFGH D) ACBFEDHG D) ACBFEDHG DEBFCADEBFCA991 1、设一棵二叉树的中序遍历结果为、设一棵二叉树的中序遍历结果为D

64、BEAFC,DBEAFC, 前序遍历结果为前序遍历结果为ABDECFABDECF，则后序遍历结则后序遍历结 果为：果为：v 例题讲解例题讲解2 2、已知一棵二叉树前序遍历和中序遍历分别、已知一棵二叉树前序遍历和中序遍历分别 为为ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，则该二叉树则该二叉树 的后序遍历为（的后序遍历为（ ） A) GEDHFBCA A) GEDHFBCA B) DGEBHFCA B) DGEBHFCA C) ABCDEFGH C) ABCDEFGH D) ACBFEDHG D) ACBFEDHG DEBFCADEBFCA1003 3、具有、具有3 3

65、个结点的二叉树有（个结点的二叉树有（ ） A) 2A) 2种形态种形态 B) 4B) 4种形态种形态 C) 7C) 7种形态种形态 D) 5D) 5种形态种形态 4 4、 设有下列二叉树：设有下列二叉树： 对此二叉树前序遍历的结果为（对此二叉树前序遍历的结果为（ ） A) ZBTTCPXA A) ZBTTCPXA B) ATBZXCTP B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT C) ZBTACTXP D) ATBZXCPT 1001011.71.7、查找和排序：、查找和排序：v查找查找又称为又称为检索检索 查找算法的评价主要考虑算法的查找算法的评价主要考虑算法的

66、时间复杂时间复杂性性，既可以采用数量级的形式表示，也可以采，既可以采用数量级的形式表示，也可以采用平均检索（查找）长度，即在查找成功情况用平均检索（查找）长度，即在查找成功情况下的平均比较次数来表示。下的平均比较次数来表示。 查找可分为查找可分为顺序查找顺序查找和和二分法查找二分法查找两种。两种。102（a a）顺序查找：顺序查找： 顺序查找顺序查找又称又称线性查找线性查找。它是一种最简单、。它是一种最简单、最基本的查找方法。最基本的查找方法。基本思想基本思想是：从表中第一是：从表中第一条记录开始，逐个进行记录的关键字和给定值条记录开始，逐个进行记录的关键字和给定值的比较。若某个记录的关键字和给定值相等，的比较。若某个记录的关键字和给定值相等，则查找成功；否则，若直至最后一个记录，其则查找成功；否则，若直至最后一个记录，其关键字和给定值都不相等，则表明表中没有所关键字和给定值都不相等，则表明表中没有所查记录，查找不成功。查记录，查找不成功。103 二分查找二分查找又称又称折半查找折半查找。作为二分查找对。作为二分查找对象的表必须是顺序存储的象的表必须是顺序存储的有序表有序表，即各记录的