二级公共基础知识

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

1、1考试需知:考试内容及安排第一章 算法与数据结构第二章 程序设计基础第三章 软件工程基础第四章 数据库设计基础234567 8 9 10 通过工作原理了解，熟悉计算机内部执行功能的基本意义。为理解程序打下基础，特别理解计算机是机器。v 指令的集合。（解释指令）v 通过硬件控制系统自动完成某一功能。v 通过一系列代码实现。11v 计算机本身仅能识别二进制代码“0”、“1”。v 编程最直接、最低级的就是机器语言。v 为解决机器语言难理解、记忆等问题。出现符号语言。v 为使编程接近自然语言，出现高级语言。如C、PASCAL、FORTRAN等。v 为配合高级语言编程，出现了开发工具，提高效率、减轻劳动

2、量。如VB、VC、PB、Delphi、VFP等。因此VFP不是编程语言。12v 不管什么形式编写代码，最终都应将代码翻译成机器语言，这就是编译程序的工作。不同的语言有不同的编译器。v 程序控制是一种逻辑控制。因此，严谨的逻辑思维是一个 程序员必备的基本素质。v 用程序实现某一功能。有许多方法。具体用哪种完全取决 于程序员个人的思维方式。因此，程序是脑力劳动的结晶，从某种意义上，编程又是一门艺术。v 程序的特殊性决定了程序的复杂性，且与实现功能的复杂 性密切相关成正比。因此为使复杂的、智力的编程工作规 范化、科学化，便出现了各种编程设计方法。如结构化编 程方法、面向对象的程序设计方法等。13v

3、不管用什么方法编程，不管编程者智力程度如何，不管 采用什么样的编程语言和方法，程序最终完成的功能稳 定、可靠、实用、易维护和安全等是程序的最终目标，也是程序员的追求。v 程序设计是一个复杂艰巨的过程。编写代码仅是程序设 计的一部分。必须先有思想，再有方法，然后才是编写 代码，且要经过许多反复，不可急功近利。14v 程序设计语言指的是用来编写程序的语言。v 人与计算机交流要使用语言，以便让计算机工作，计算 机也通过语言把结果告诉用计算机的人“人机对 话”。v 人与计算机交流的语言非平常人与人之间交流的语言，是专门的语言程序设计语言。v 程序设计语言是计算机系统软件的重要组成部分。15v 执行程序

4、设计的语言有很多，可分高级语言和低级语言，区别在于接近自然语言的程度v 高级语言一般与具体的计算机硬件无关，比较接近人类 自然语言的语法习惯及数学表达形式。v 用高级语言编写的源程序不能被机器直接执行，需通过 编译成解释程序的翻译才可被机器执行（机器语言）。16第一章 算法与数据结构二级公共基础知识二级公共基础知识返回171 1、算法的基本概念、算法的基本概念 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法具有有穷性有穷性、确定性确定性、可行性可行

5、性、输输入入和输出输出（拥有足够的情报）等个重要特性。182 2、算法的基本要素、算法的基本要素v 对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输 算法中各操作之间的执行顺序；描述算法的工具通常有传统流程图、N-S结构化流程 图、算法描述语言等；一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。v 算法的控制结构：193 3、算法设计的基本方法、算法设计的基本方法v 列举法v 归纳法v 递推v 递归（以简洁的形式设计和描述算法）v 减半递推技术v 回溯法201 1、时间复杂度、时间复杂度v 依据算法编制的程序在计算机上运行时所消耗的时间 来度量。通常有事后统计法和事前分

6、析估算法。v 一个算法是由控制结构（顺序、分支和循环）和原操 作构成的，算法时间取决于两者的综合效果。v 算法中基本操作重复执行次数n和算法执行时间同步 增长，称作算法的时间复杂度。212 2、空间复杂度、空间复杂度v 一般是指执行这个算法所需要的内存空间。v 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需 要的附加存储空间。v 一个上机执行的程序除了需要存储空间来寄存本身所用 指令、常数、变量和输入数据外，也需要一些对数据进 行操作的工作单元和存储一些为实现计算所需信息的辅 助空间。223 3、例题讲解、例题讲解v 算法的时间复杂度是指算法的

7、时间复杂度是指(C C )A A、执行算法程序所需要的时间执行算法程序所需要的时间 B B、算法程序的长度算法程序的长度 C C、算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D D、算法程序中的指令条数算法程序中的指令条数v 算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、【1 1】和拥有足够和拥有足够 的情报。的情报。【答案】【答案】:有穷性有穷性v 算法的空间复杂度是指算法的空间复杂度是指(D D )A)A)算法程序的长度算法程序的长度 B)B)算法程序中的指令条数算法程序中的指令条数 C)C)算法程序所占的存储空间算法程序所占的存储空间 D)D)

8、执行过程中所需要的存储空间执行过程中所需要的存储空间 23v 在计算机中，算法是指（B B）A)加工方法 B)B)解题方案的准确而完整的描述解题方案的准确而完整的描述 C)排序方法 D)查询方法v 算法分析的目的是(D D)A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性 D)D)分析算法的效率以求改进分析算法的效率以求改进v 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的【1 1】。【答案】【答案】:时间复杂度和空间复杂度时间复杂度和空间复杂度 24Data Structure1 1、数据结构研究的主要内容、数据结构研究的主要内容v 当

9、今计算机应用的特点：1、所处理的数据量大且具有一定的关系；2、对其操作不再是单纯的数值计算，而更多地是需 要对其进行组织、管理和检索。对数据的讨论不单是数据本身，还要包括数据与数对数据的讨论不单是数据本身，还要包括数据与数据之间的关系。据之间的关系。25 学 生 基 本 情 况 学 号 姓 名 性 别 出 生 年 月 .99070101 李 军 男 80 12.99070102 王 颜 霞 女 81 2.99070103 孙 涛 男 80 9.99070104 单 晓 宏 男 81 3.特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小

10、存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等。v 应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。26v 应用举例2家庭血缘关系图 表示家庭成员的辈分关系，使用下图1-1所示的形式描述。3 1 21 3 21 2 31 23 2 12 3 12 1 32 11家庭血缘关系图特点：在求解过程中，所处理的数据之间具有层次关系，这是我们 所说的树形结构；对它的操作有：建立树形结构，输出终结点内容等。v 应用举例3制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。

11、有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：计算机专业学生的必修课程 课课程程编编号号 课课程程名名称称 需需要要的的先先导导 课课程程编编号号 C 1 程序设计基础 无 C 2 离散数学 C 1 C 3 数据结构 C 1，C 2 C 4 汇编语言 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

12、 1 27这种数据可以用下面的图来表示：v 课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图 1-2 计算机专业必修课程开设先后关系28 1 1、数据的、数据的逻辑结构逻辑结构 2 2、数据的、数据的存储结构存储结构 3 3、数据的、数据的运算运算：检索、排序、插入、删除、修改等。：检索、排序、插入、删除、修改等。A A线性结构线性结构B B非线性结构非线性结构A A顺序存储顺序存储 B B链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面(亦称物理结构亦称物理结构)数据结构的主要研究问题：292 2、基

13、本概念和术语、基本概念和术语 数据结构是一门研究组织组织、存储存储和运算运算的一般方法的学科。例：整数整数(1,2)、实数实数(1.1,1.2)字符串字符串(Beijing)、图形图形、声音声音。计算机管理图书问题：在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如：30数据元素在计算机中的表示 数据结构是一门研究组织组织、存储存储和运算运算的一般方法的学科。如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需

14、要的目的？目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9 对数据结构中的节点进行操作处理对数据结构中的节点进行操作处理（插入、删除、修改、查找、排序）（插入、删除、修改、查找、排序）31v 数据元素数据元素(Data Element)Data Element)数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元素可由若干数据项数据项(Data ItemData Item)组成。数据项是数据的最小单位。数据元素亦称节点节点或记录记录。数据结构可描述为数据结构可描述为 Group=Group=（D D，

15、R R）有限个数据元素的集合有限个数据元素的集合有限个节点间关系的集合有限个节点间关系的集合3233数据结构可描述为数据结构可描述为 Group=（D，R）l 例例1：一年四季的数据结构可表示成：一年四季的数据结构可表示成B=（D，R）D=春，夏，秋，冬春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）l 例例2：家庭成员数据结构可表示成：家庭成员数据结构可表示成B=（D，R）D=父亲，儿子，女儿父亲，儿子，女儿 R=（父亲，儿子），（父亲，女儿）（父亲，儿子），（父亲，女儿）冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿34数据结构也可用图形表示数据结构也可用

16、图形表示l一年四季的数据结构可表示成一年四季的数据结构可表示成l家庭成员数据结构可表示成家庭成员数据结构可表示成冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿（概念：结点、前件、后件、根结点、叶子）35v 树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式计算机程序管理系统也是典型的计算机程序管理系统也是典型的树形结构树形结构。36HGFECDBA37 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

17、=(1,2),(2,3),(3,2),(1,3)R=(1,2),(2,3),(3,2),(1,3)v 图形结构图形结构节点间的连结是任意的节点间的连结是任意的1 14 42 23 3383 3、例题讲解、例题讲解v 数据处理的最小单位是数据处理的最小单位是(C C )A)A)数据数据 B)B)数据元素数据元素 C)C)数据项数据项 D)D)数据结构数据结构v 数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及(A A )A)A)数据的存储结构数据的存储结构 B)B)计算方法计算

18、方法 C)C)数据映象数据映象 D)D)逻辑存储逻辑存储v 数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【4 4】以及对数据的以及对数据的操作运算。操作运算。【答案【答案】物理结构（或存储结构）物理结构（或存储结构）39v 线性结构与非线性结构：线性结构与非线性结构：v 线性结构：有且只有一个根结点；每一个结线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。点最多有一个前件，也最多有一个后件。如：一年四季，如：一年四季，2626个英文字母个英文字母v非线性结构：线性以外的数据结构。非线性结构：线性以外的数据结构。如：反映家庭成员间辈分关系的数据

19、结构如：反映家庭成员间辈分关系的数据结构 404、线性表、线性表（Linear List）学学 生生 成成 绩绩 表表 (按成绩排列按成绩排列)86胡孝臣986110395刘忠赏9861107100张卓9861109成 绩姓 名学 号v 线性表线性表结点间是以线性关系联结：结点间是以线性关系联结：v 线性表线性表：具有线性结构的有限序列。数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。v 线性表的定义线性表的定义:线性表线性表是是n n个元素的有限序列，它们之间的关系可以排成个元素的有限序列，它们之间的关系可以排成一个线性序列：一个线性序列：a1a1，a2a2

20、，aiai，anan 其中其中n n称作表的称作表的长度长度，当，当n=0n=0时，称作时，称作空表空表。v 线性表的特点：线性表的特点：1 1、线性表中所有元素的性质相同。、线性表中所有元素的性质相同。2 2、除第一个和最后一个数据元素之外，其它数据元素有且、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱，最仅有一个前驱和一个后继。第一个数据元素无前驱，最 后一个数据元素无后继。后一个数据元素无后继。3 3、数据元素在表中的位置只取决于它自身的序号。、数据元素在表中的位置只取决于它自身的序号。v 在线性表上常用的运算有：在线性表上常用的运算有：

21、初始化、求长度、取元素、修改、前插、删除、检索、排序初始化、求长度、取元素、修改、前插、删除、检索、排序4142v 线性表的线性表的 顺序存储结构 及其及其 插入 与与 删除 操作操作 特点：特点：1 1、线性表中数据元素类型一致，只有数据域，存储空间、线性表中数据元素类型一致，只有数据域，存储空间 利用率高。利用率高。2 2、所有元素所占的存储空间是连续的。、所有元素所占的存储空间是连续的。3 3、各数据元素在存储空间中是按逻辑顺序依次存放的、各数据元素在存储空间中是按逻辑顺序依次存放的 （a a）做插入、删除时需移动大量元素。做插入、删除时需移动大量元素。（b b）空间估计不明时，按最大空

22、间分配。空间估计不明时，按最大空间分配。43顺顺序序存存储储存储地址存储地址存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素元素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 线性表的线性表的 顺序存储结构顺序存储结构：首地址首地址起始地址起始地址基地址基地址44元素元素a a1 1元素元素a a2 2.元素元素a ai+1i+1.0 0 1 1i i 线性表的顺序存储结构线性表的顺序存储结构可用可用C C

23、语言中的一维数组来描述语言中的一维数组来描述.第第i i个元素的个元素的a ai i存储地址：存储地址：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)+(i-1)*m mVV VV ViViVm-1Vm-1 intint VM;VM;其中：其中：V V是数组的名字，是数组的名字，M M是数组大小，是数组大小，假设数组中的元素是整型类型假设数组中的元素是整型类型v插入运算插入运算.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

24、 a2 2 a a1 1 X X a ai ia ai+1i+1.a alengtlength h 插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：1n1iis2n1)i(n1n1E45在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。n1idl21ni)(nn1Ev删除算法的分析删除算法的分析46q 线性表的例

25、题讲解线性表的例题讲解v 顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【1 1】的存储单元中。的存储单元中。【答案【答案】相邻相邻v 长度为长度为n n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元 素概率都相等时，插入一个元素所需移动元素的平均个数素概率都相等时，插入一个元素所需移动元素的平均个数 为为【2 2】。【答案【答案】n/2n/2v 线性表线性表L=(a1,a2,a3,L=(a1,a2,a3,aiai，an)an)，下列说法正确的是（下列说法正确的是（D D）A)A)每个元素都有一个直接前件

26、和直接后件每个元素都有一个直接前件和直接后件 B)B)线性表中至少要有一个元素线性表中至少要有一个元素 C)C)表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D)D)除第一个元素和最后一个元素外，其余每个元素都有一除第一个元素和最后一个元素外，其余每个元素都有一 个且只有一个直接前件和直接后件个且只有一个直接前件和直接后件 4748v 数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的(C C )A)A)存储结构存储结构B)B)物理结构物理结构 C)C)逻辑结构逻辑结构D)D)物理和存储结构物理和存储结构 下列叙述中

27、，错误的是（下列叙述中，错误的是（B B ）A)A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B)B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C)C)数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D)D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 数据的存储结构是指（数据的存储结构是指（B B ）A A）数据所占的存储空间数据所占的存储空间 B B）数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示 C C）数据在计算机中的顺序存储方式数

28、据在计算机中的顺序存储方式 D D）存储在外存中的数据存储在外存中的数据 根据数据结构中各数据元素之间前后件关系的复杂程度，一根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成般将数据结构分成(C C)A)A)动态结构和静态结构动态结构和静态结构 B)B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C)C)线性结构和非线性结构线性结构和非线性结构 D)D)内部结构和外部结构内部结构和外部结构 数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【2 2】两大类。两大类。非线性结构非线性结构 当线性表采用顺序存储结构实现存储时，其主要特点是当线性表采用顺序存储结构实现存储时，其

29、主要特点是【1】。【答案【答案】逻辑结构中相邻的结点在存储结构中仍相邻。逻辑结构中相邻的结点在存储结构中仍相邻。495 5、堆栈和队列、堆栈和队列q 堆栈和队列的定义堆栈和队列的定义 栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限制的线性表，故也称为限定性的数据结构。限定性的数据结构。v 堆栈的定义堆栈的定义堆栈：堆栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表,此种此种 结构称为结构称为后进先出。后进先出。设栈设栈s=s=（a a1 1，a a2 2，a ai i，

30、a an n）,其中其中a a1 1是是栈底栈底元素，元素，a an n是是栈顶栈顶元素。元素。栈顶（栈顶（top)top)：允许插入和删除的一端；允许插入和删除的一端；约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。栈底栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。a1 a2 .an进栈进栈出栈出栈栈顶栈顶栈底栈底5051 a1 a2 .an进栈进栈出栈出栈栈顶栈顶栈底栈底51v 队列的定义队列的定义队列：队列：一种特殊的线性结构，限定只能在表的一端进行插入，一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一

31、端进行删除的线性表。此种结构称为在表的另一端进行删除的线性表。此种结构称为先进先进 先出（先出（FIFO）表表。a1 ,a2 ,a3 ,an-1 ,an队队 列列 示示 意意 图图队头队头队尾队尾v 队列的主要运算队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素。52出队出队入队入队rearrearfrontfront53v 循环队列及其运算循环队列及其运算循环循环队列：队列：将队列存储空间的最后一个位置绕到第一个位置，将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。形成逻辑上的环状空间

32、，供队列循环使用。循环队列的元素：循环队列的元素：从排头指针指向的后一个位置直到队尾指针从排头指针指向的后一个位置直到队尾指针指向的位置之间所有的元素。指向的位置之间所有的元素。说明：说明：为了能够区分队列满与空，设置一个标志为了能够区分队列满与空，设置一个标志s s。s=s=0 0 表示队列空表示队列空1 1 表示队列非空表示队列非空队列空与满的条件：队列空与满的条件：队列空时，s=0；队列满时，s=1且front=rear。54循环队列的运算：循环队列的运算：入队运算和退队运算入队运算和退队运算入队运算：是指在循环队列中的队尾加入一新元素。入队运算：是指在循环队列中的队尾加入一新元素。具体

33、操作：具体操作：（1 1）将队尾指针进一，即）将队尾指针进一，即rear=rear+1rear=rear+1。注：当注：当rear=m+1rear=m+1时，重置时，重置rear=1rear=1。（2 2）将新元素插入到）将新元素插入到rearrear指向的位置。指向的位置。注：当注：当s=1s=1且且rear=frontrear=front时，循环队列满，不能再进行入队运算，称为时，循环队列满，不能再进行入队运算，称为“上上溢溢”。退队运算：是指在循环队列的排头位置退出一个元素并赋给指定的变量。退队运算：是指在循环队列的排头位置退出一个元素并赋给指定的变量。具体操作：具体操作：（1 1）将排

34、头指针进一，即）将排头指针进一，即front=front+1front=front+1。注：当注：当front=m+1front=m+1时，重置时，重置front=1front=1。（2 2）将排头指针指向位置的后一个元素赋给指定的变量。）将排头指针指向位置的后一个元素赋给指定的变量。注：当注：当s=0s=0时，循环队列为空，再不能进行退队运算，称为时，循环队列为空，再不能进行退队运算，称为“下溢下溢”。54q 堆栈和队列的例题讲解堆栈和队列的例题讲解v栈和队列的共同特点是（栈和队列的共同特点是（C C ）A)A)都是先进先出都是先进先出 B)B)都是先进后出都是先进后出 C)C)只允许在端点

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

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

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

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

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

40、素2 2元素元素1 158596 6、线性链表、线性链表v线性链表的基本概念：线性链表的基本概念：线性表的链式存储结构称为线性链表。为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。将存储空间中的每一个存储结点分为两部：v一部分称为数据域，用于存储数据元素的值；v另一部分称为指针域，用于存放下一个数据元素的存储序号（即存储结点的地址），也就是指向后件结点。线性链表中存储结点的结构如图2.20所示60611、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。2、逻辑上相邻的

41、节点物理上不必相邻。3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。4、查找结点时链式存储要比顺序存储慢。v 链式存储结构特点：链式存储结构特点：62 线性链表的物理结构线性链表的物理结构 线性链表的逻辑结构图线性链表的逻辑结构图HEAD：指向线性表中第一个结点的指针，称为头指针。当HEAD=NULL（或0）时称为空表。对于线性链表，可以从头指针开始，沿着各个结点的指针扫描到链表中的所有结点。6363 为了弥补线性单链表的这个缺点，在某些应为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，用中，对线性链表中的每个结点设置两个指针，一个称为一个称为左指针

42、（左指针（LlinkLlink），），用以指向其前件结用以指向其前件结点；另一个称为点；另一个称为右指针（右指针（RlinkRlink），），用以指向其用以指向其后件的结点。后件的结点。这样的线性链表称为这样的线性链表称为双向链表双向链表，其逻辑状态，其逻辑状态如图如图2.232.23所示。所示。64v 线性链表的基本运算：线性链表的基本运算：线性链表的运算主要有以下几个：线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前在线性链表中包含指定元素的结点之前 插入插入一个新元素。一个新元素。在线性链表中在线性链表中删除删除包含指定元素的结点。包含指定元素的结点。将两个线性链表按要求

43、将两个线性链表按要求合并合并成一个线性成一个线性 链表。链表。65 线性链表的线性链表的 插入插入 运算：运算：线性链表的插入线性链表的插入是指在链式存储结构下是指在链式存储结构下的线性表中插入一个新元素。的线性表中插入一个新元素。为了要在线性链表中插入一个新元素，为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，然后将存首先要给该元素分配一个新结点，然后将存放新元素值的结点链接到线性链表中指定的放新元素值的结点链接到线性链表中指定的位置。位置。666667 线性链表的删除线性链表的删除指在链式存储结构下的指在链式存储结构下的线性表中删除包含指定元素的结点。线性表中删除包含指定元

44、素的结点。为了在线性链表中删除包含指定元素的结为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。然后将要删除结点放回到可利用栈。线性链表的线性链表的 删除删除 运算：运算：6868 循环链表的结构与前面所讨论的线性链表相比，具有以下循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：两个特点：循环链表的头指针指向表头结点。循环链表的头指针指向表头结点。在循环链表中，所有结点的指针构成了一个环状链。在循环链表中，所有结点的指针构成了一个环状链。图图2.292.29是循环链表的示意图。是循环链表的示意

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

46、具有的特点是（B B ）A)A)不必事先估计存储空间不必事先估计存储空间 B)B)可随机访问任一元素可随机访问任一元素 C)C)插入删除不需要移动元素插入删除不需要移动元素 D)D)所需空间与线性表长度成正比所需空间与线性表长度成正比v数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1 1】。【答案【答案】存储结构存储结构v线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是(B B)A)A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B)B)随机存取的存储结构、顺序存取的

47、存储结构随机存取的存储结构、顺序存取的存储结构 C)C)随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D)D)任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构q 线性链表的例题讲解线性链表的例题讲解71727 7、树与二叉树：、树与二叉树：v 树的基本概念：树的基本概念：前面我们讨论的线性表，栈、队列和数组等都是线性结构。而树是一种非线性数据结构，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起，清晰地反映了数据元素之间的层次关系。73现实世界中，能用树的结构表示的例子现

48、实世界中，能用树的结构表示的例子：学校的行政关系（学校的行政关系（P31）、书的层次结构（）、书的层次结构（P32）、人类的家）、人类的家族血缘关系等。族血缘关系等。7474例：下图是一个有13个结点的树，其中A是根，其余结点为分三个互不相交的子集：T1B,E,F,K,LT2F,GT3D,H,I,J,MT1、T2和T3都是根A的子树。7575树结构的基本术语：结点的度：结点所拥有子树的个数，图中A的度为3，C的度为1，F的度为0。叶子结点：树中度为0的结点，图中的K、L、F、G、M、I、J均称为叶子结点（或终端结点）。子结点与父结点：把每一个结点的一个或多个后件称为该点的子结点；反之，这个结点

49、称为其子结点的父结点，同一个父结点的子结点之间互称为兄弟。树的度：树中各结点的度的最大值，度不为0的结点为非终端结点同，又叫分支结点。森林：N0或N=0棵互不相交的树的集合组成森林。图中将根结点A去掉，其中三棵子树就组成一个森林。树的深度：树中结点的最大层次称为树的深度或高度。图中树的深度为4。二叉树是一种很有用的非线性结构。二叉树具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。v 二叉树（二叉树（Binary TreeBinary Tree）：）：因为树的每个结点的度不同，存储困难，使得对树的处理算法很复杂。所以引出二叉树的

50、讨论。767777性质性质1 1：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。例子例子1 1：某二叉树中度为2的结点有18个，则该二叉树中有 19 19 个叶子结点。二叉树的性质：二叉树的性质：特别要注意：二叉树不是树的特殊情况。a aa ab bb b两棵不同的二叉树7879性质性质2 2：二叉树的第i层上至多有2 i-1（i 1）个结点二叉树的性质：二叉树的性质：423167891011121314155第一层(i=1)，有21-1=1个节点。第二层(i=2)，有22-1=2个节点。第三层(i=3)，有23-1=4个节点。第四层(i=4)，有24-1=8个节点。

51、80二叉树的性质：二叉树的性质：性质性质3 3：深度为深度为h h的二叉树中至多含有的二叉树中至多含有2 2h h-1-1个结点个结点423167891011121314155此树的深度此树的深度h=4h=4，共有共有2 24 4-1=15-1=15个节点。个节点。1+2+4+1+2+4+2+2m-1m-1=2=2m-1m-1(等比数列前等比数列前MM项和项和)81v满二叉树与完全二叉树满二叉树与完全二叉树满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。注意：满二叉树是完全二叉

52、树，完全二叉树不一定是满二叉树。82v 满二叉树的特点：满二叉树的特点：每一层上都含有最大结点数。每一层上都含有最大结点数。8283v完全二叉树的特点：完全二叉树的特点：除最后一层外，每一层都取最大除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置结点数，最后一层结点都集中在该层最左边的若干位置83848485 对于对于完全二叉树完全二叉树而言而言如果它的结点个数为如果它的结点个数为偶偶数，则该二叉树中：数，则该二叉树中：叶子结点的个数叶子结点的个数=非叶子结点的个数非叶子结点的个数如果它的结点个数为如果它的结点个数为奇奇数，则该二叉树中：数，则该二叉树中：叶子结点

53、的个数叶子结点的个数=非叶子结点的个数非叶子结点的个数+1 +1 （即叶子结点数比非叶子结点数（即叶子结点数比非叶子结点数多一个多一个）规律总结：规律总结：1234123452 2 叶子结点 3 32 2 非叶子结点 2 286v 例题讲解例题讲解1、设一棵完全二叉树共有700个结点，则在该二叉树中有 350 350 个叶子结点。2、在深度为5的满二叉树中，叶子结点的个数为（C C ）A)32 B)31 C)16 D)15v二叉树的遍历二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为三种：前序前序遍历、中序中序遍历、后序后序遍历。设访问根结点记作设访问根结点记作

54、V V；遍历根的左子树记作遍历根的左子树记作L L；遍历根的右子树记作遍历根的右子树记作R R；前序：前序：VLRVLR（即根左右）即根左右）中序：中序：LVRLVR（即左根右）即左根右）后序：后序：LRVLRV（即左右根）即左右根）8788884 10 8 9 5 2 6 7 3 1 例：结合下图所示的二叉树，写出该二叉树的前序、中序及后序遍历结果。后序遍历：中序遍历：前序遍历：1 2 4 5 8 10 9 3 6 74 2 10 8 5 9 1 6 3 7 891 1、设一棵二叉树的中序遍历结果为、设一棵二叉树的中序遍历结果为DBEAFC,DBEAFC,前序遍历结果为前序遍历结果为ABDE

55、CFABDECF，则后序遍历结果为：则后序遍历结果为：DEBFCADEBFCA v 例题讲解例题讲解2 2、已知一棵二叉树前序遍历和中序遍历分别、已知一棵二叉树前序遍历和中序遍历分别为为ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，则该二叉树的则该二叉树的后序遍历为（后序遍历为（B B ）A)GEDHFBCA A)GEDHFBCA B)DGEBHFCAB)DGEBHFCA C)ABCDEFGH D)ACBFEDHG C)ABCDEFGH D)ACBFEDHGv具有具有3 3个结点的二叉树有（个结点的二叉树有（D D ）A)2A)2种形态种形态 B)4B)4种形态种形态

56、C)7C)7种形态种形态 D)5D)5种形态种形态 v 设有下列二叉树：设有下列二叉树：对此二叉树前序遍历的结果为（对此二叉树前序遍历的结果为（B B ）A)ZBTTCPXA A)ZBTTCPXA B)ATBZXCTP B)ATBZXCTP C)ZBTACTXP D)ATBZXCPT C)ZBTACTXP D)ATBZXCPT90918 8、查找和排序：、查找和排序：v查找查找又称为又称为检索检索 查找算法的评价主要考虑算法的时间复杂查找算法的评价主要考虑算法的时间复杂性，既可以采用数量级的形式表示，也可以性，既可以采用数量级的形式表示，也可以采用平均检索（查找）长度，即在查找成功采用平均检索

57、（查找）长度，即在查找成功情况下的平均比较次数来表示。情况下的平均比较次数来表示。查找可分为查找可分为顺序查找顺序查找和和二分法查找二分法查找两种。两种。92（a a）顺序查找：顺序查找：顺序查找顺序查找又称又称线性查找线性查找。它是一种最简单、最。它是一种最简单、最基本的查找方法。基本思想是：从表中第一条基本的查找方法。基本思想是：从表中第一条记录开始，逐个进行记录的关键字和给定值的记录开始，逐个进行记录的关键字和给定值的比较。若某个记录的关键字和给定值相等，则比较。若某个记录的关键字和给定值相等，则查找成功；否则，若直至最后一个记录，其关查找成功；否则，若直至最后一个记录，其关键字和给定值

58、都不相等，则表明表中没有所查键字和给定值都不相等，则表明表中没有所查记录，查找不成功。记录，查找不成功。93 二分查找二分查找又称又称折半查找折半查找。作为二分查找对象。作为二分查找对象的表必须是顺序存储的有序表，即各记录的的表必须是顺序存储的有序表，即各记录的次序是按其关键字的大小顺序（以下假定按次序是按其关键字的大小顺序（以下假定按从小到大的顺序）排列的表。从小到大的顺序）排列的表。（b b）二分查找：二分查找：94 二分查找的二分查找的具体做法具体做法是是:先取表先取表中间中间位置的记录位置的记录关键字与给定值比较。若相等关键字与给定值比较。若相等,则查找成功；否则则查找成功；否则,若给

59、定值比该记录的关键字小，则给定值必在表的前若给定值比该记录的关键字小，则给定值必在表的前半部分。在这前半部分中再取中间位置记录的关键字半部分。在这前半部分中再取中间位置记录的关键字进行比较，就又可以排除这部分的一半。依次反复进进行比较，就又可以排除这部分的一半。依次反复进行，直到找到给定值或找完全表而找不到为止。行，直到找到给定值或找完全表而找不到为止。对于对于n n较大时，查找长度可以近似地表示为较大时，查找长度可以近似地表示为95排序排序是将一组杂乱无章的数据按一定的规律顺是将一组杂乱无章的数据按一定的规律顺次排列起来。次排列起来。通常数据对象有多个属性域，即由多个数据成通常数据对象有多个

60、属性域，即由多个数据成员组成员组成,其中有一个属性域可用来区分对象其中有一个属性域可用来区分对象,作为排序依据。该域称为作为排序依据。该域称为关键字（关键字（keykey）。排序的时间开销是衡量算法好坏的最重要的标排序的时间开销是衡量算法好坏的最重要的标志。对于长度为志。对于长度为n n的有序线性表，查找时最坏的有序线性表，查找时最坏情况只需比较情况只需比较 n n 次。次。v 排序（排序（sortsort）96（a a）交换类排序：交换类排序：交换类排序法：交换类排序法：冒泡排序法冒泡排序法：需要比较的次数为：需要比较的次数为n(n-1)/2n(n-1)/2快速排序法快速排序法：是对冒泡排序

61、的改进，是：是对冒泡排序的改进，是目目 前内部排序中速度最快的一种。前内部排序中速度最快的一种。97（b b）插入类排序：插入类排序：插入类排序的插入类排序的基本方法基本方法是：每步将一个待排是：每步将一个待排序的对象，按其关键字大小，插入到前面已序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对经排好序的一组对象的适当位置上，直到对象全部插入为止象全部插入为止。简单插入排序法：简单插入排序法：最坏情况需要最坏情况需要n(n-1)/2n(n-1)/2次比较；次比较；希尔排序法：希尔排序法：最坏情况需要最坏情况需要OO（n n1.5 1.5）次比较。次比较。98（c c

62、）选择类排序：选择类排序：选择类排序的选择类排序的思想思想是：每一趟（例如，第是：每一趟（例如，第i i趟，趟，i=0i=0，1 1，n n2 2）在后面在后面n ni i个待排序对象中选个待排序对象中选出关键字最小（升序，若为降序，选出最大关键出关键字最小（升序，若为降序，选出最大关键字）的对象，作为有序对象序列的第字）的对象，作为有序对象序列的第i i个对象。待个对象。待到第到第n n2 2趟作完，待排序对象只剩下趟作完，待排序对象只剩下1 1个，不用再个，不用再选了，结束排序。选了，结束排序。简单选择排序法简单选择排序法，最坏情况需要，最坏情况需要n(n-1)/2n(n-1)/2次比较；

63、次比较；堆排序法堆排序法，最坏情况需要，最坏情况需要OO（nlognlog2 2 n n）次比较。次比较。99第二章 程序设计基础二级公共基础知识返回100内容1、程序设计方法与风格2、结构化程序设计3、面向对象的程序设计方法，对象、方法、属性及继承与多态性。101（一）程序设计方法与风格（一）程序设计方法与风格 v 如何形成良好的程序设计风格：如何形成良好的程序设计风格：1 1、源程序内部文档化；、源程序内部文档化；选择标识符的名字选择标识符的名字 注释（注释（序言性序言性和和功能性功能性注释）注释）程序的视觉组织程序的视觉组织一般位于模块的一般位于模块的首部，用于说明首部，用于说明模块的相

64、关信息模块的相关信息位于源程序位于源程序模块内部模块内部风格：风格：清晰第一，效率第二。102 显式地说明一切变量显式地说明一切变量 数据说明的次序应该规范化数据说明的次序应该规范化 便于查找变量（按顺序排列）便于查找变量（按顺序排列）对复杂数据结构应注释说明对复杂数据结构应注释说明 2 2、数据说明、数据说明3 3、语句的结构、语句的结构 每条语句简单明了 限制GOTO语句的使用(尽量不用或少用)尽量只采用3种基本控制结构编程4 4、输入和输出、输入和输出 对所有输入数据进行校验和合理性检查对所有输入数据进行校验和合理性检查 输入输出格式保持一致输入输出格式保持一致 设计良好的输出报表设计良

65、好的输出报表 输入方式输入方式应力求简单，尽量避免给用户带来不必要的麻烦；应力求简单，尽量避免给用户带来不必要的麻烦；交互式输入数据时应有必要的提示信息交互式输入数据时应有必要的提示信息;程序应对输入数据的程序应对输入数据的合法性进行检查合法性进行检查;若用户输入某些数据后可能产生严重后果若用户输入某些数据后可能产生严重后果,应应给用户输出必要的提示并要求用户确认；应根据系统的特点和给用户输出必要的提示并要求用户确认；应根据系统的特点和用户的习惯设计出令用户满意的输入方式。用户的习惯设计出令用户满意的输入方式。输出数据的格式输出数据的格式应清晰，美观；输出数据时要加上必要的应清晰，美观；输出数

66、据时要加上必要的提示信息。提示信息。103104主要思想：主要思想：对大型的程序设计，使用一些基本的结构来设计程序，无论多复杂的程序，都可以使用这些基本结构按一定的顺序组合起来。这些基本结构的特点都是只有一个入口、一个出口。由这些基本结构组成的程序就避免了任意转移、阅读起来需要来回寻找的问题。（二）结构化程序设计（二）结构化程序设计 三种基本结构的特点三种基本结构的特点 只有一个入口 只有一个出口 基本结构中的每一部分都有机会执行到 结构内不存在“死循环”三种基本结构三种基本结构 顺序结构 选择结构 循环结构105设计原则设计原则 自顶向下 逐步求精 模块化 限制使用goto语句（二）结构化程序设计（二）结构化程序设计 结构化程序设计方法结构化程序设计方法1、要求把程序的结构规定为顺序、选择和循环三种基本机构，并提出了自顶向下、逐步求精、模块化程序设计等原则。2、结构化程序设计是把模块分割方法作为对大型系统进行分析的手段，使其最终转化为三种基本结构，其目的是为了解决由许多人共同开发大型软件时，如何高效率地完成可靠系统的问题。3、程序的可读性好、可维护性好成为评价程序质量的首要条件。4、