计算机二级考试公共基础知识讲义.ppt

《计算机二级考试公共基础知识讲义.ppt》由会员分享，可在线阅读，更多相关《计算机二级考试公共基础知识讲义.ppt（263页珍藏版）》请在装配图网上搜索。

1、全国计算机等级考试二级考试 公共基础知识部分,主讲教师：王昆,所有的学习都是一个自学的过程。学生 学习知识时主要是靠自己勤奋刻苦。老师最 大的任务就是教他们怎样去学。,公共基础知识考题特点及复习建议,一、涉及面广，但难度小 计算机等级二级理论考试中有关公共知识部分的题目共有15道，涉及算法及数据结构、程序设计基础、软件工程基础和数据库设计基础等四门学科，但是从整体上分析，考试中的考核内容的难度不大，考点也相对集中些。,公共基础知识考题特点及复习建议,二、考核重点为基本概念、基本方法 和基本运算 计算机等级二级理论考试中涉及的题目都是基本概念、基本方法和基本运算，考核以概念和认识性内容为主，理解

2、性、应用性内容极少。,公共基础知识考题特点及复习建议,三、考核重点是数据结构和算法 以下是对以往二级理论考试的大概统计： 算法及数据结构： 50% 程序设计基础：12.5% 软件工程基础：18.75% 数据库设计基础：18.75%,主要内容,第1章 数据结构与算法 第2章 程序设计基础 第3章 软件工程 第4章 数据库设计基础,基础知识部分：30分,设有10道选择题和5道填空题,学习目标与要求算法与数据结构,1、了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度；,2、掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利 用图形的方式表示数据结构 ；,3、了解线性表的基本概

3、念，并掌握线性表的顺序存储结构以及顺序存储的 线性表的基本运算；,4、了解栈和队列的基本概念，并掌握它们的基本运算；,5、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循 环链表的基本概念和基本操作；,6、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存 储结构和遍历技术；,7、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；,8、学会利用相关的排序技术实现无序数列的排序操作。,学习目标与要求软件工程,1、了解软件工程的基本概念；,2、了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；,3、了解利用结构化分析法进行软件工程中的需求分析的方法

4、，并了解需 求分析的方法和需要完成的任务；,4、了解数据流图的使用方法；,5、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些 常用工具；,6、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件 测试方法的区别和各自的功能与特点；,7、了解程序调试的方法和原则 。,学习目标与要求程序设计基础,1、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序 设计的基本规则；,2、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点;,3、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。,学习目标与要求数据库系统,1、了解数据库系统的基本概念，以及

5、数据库系统的发展；,2、了解数据模型的基本概念，并对E-R模型、层次模型、网状模型和关系模型 进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识；,3、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算；,4、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。,第一章 数据结构与算法,1.1 算法 1.2 数据结构的基本概念 1.3 线性表及其顺序存储结构 1.4 栈和队列 1.5 线性链表 1.6 树与二叉树 1.7 查找技术 1.8 排序技术,数据结构与算法历年试题分数分布,11 算法,1.1.1 算法的基本概念 算法：是指解题方案的准确而完整的描述。 算法不

6、等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1） 可行性（effectiveness）：针对实际问题而设计的算法，执行后能够得到满意的结果。 （2） 确定性（definiteness）：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 （3） 有穷性（finiteness）：算法必须的有限时间内做完，即算法必须能在执行有限个步骤之后终止。 （4） 拥有足够的情报：要使算法有效必须为算法提供足够的情报。当算法拥有足够的情报时，此算法才是

7、有效的；当提供的情报不够时，算法可能无效。 综上所述，算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的，此顺序将在有限的次数后终止。,11 算法,2.算法的基本要素： 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。,1.1.2 算法复杂度,算法的复杂度主要包括时间复杂度和空间复杂度。 1. 时间复杂度：指执行算法所需要的计算

8、工作量 (算法在执行过程中所需基本运算的执行次数。） 2. 空间复杂度：执行这个算法所需要的内存空间,算法的历年考题,2004.9 （1）算法的复杂度主要包括_时间_复杂度和空间复杂度。 2005.4 （5）问题处理方案的正确而完整的描述称为_算法_。 2005.9 （2）算法复杂度主要包括时间复杂度和_空间_复杂度。,算法的历年考题,2006.9 （7）下列叙述中正确的是 A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对 解析：算法的复杂度主要包括时间复杂度和空间复杂

9、度。算法的时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。算法的空间复杂度是指执行这个算法所需要的内存空间。根据两个定义可看出二者并不相关。,算法的历年考题,2007.4 （1）下列叙述中正确的是 A）算法的效率只与问题的规模有关，而与数据的存储结构无关 B）算法的时间复杂度是指执行算法所需要的计算工作量 C）数据的逻辑结构与存储结构是一一对应的 D）算法的时间复杂度与空间复杂度一定相关 解析：根据上一题可知，算法的时间复杂度和空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，他是从逻辑上描述数据元素之间的关系的，是独立于计算机的；数据

10、的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示的，他们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。,简单例题：,算法的时间复杂度是指( ) A、执行算法程序所需要的时间 B、算法程序的长度 C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数 答案： C 算法的基本特征是可行性、确定性、 【1】和拥有足够 的情报。 【答案】:有穷性 算法的空间复杂度是指( ) A) 算法程序的长度 B) 算法程序中的指令条数 C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间 答案： D 在计算机中，算法是指（ ） A) 加工方法 B) 解

11、题方案的准确而完整的描述 C) 排序方法 D) 查询方法 答案： B,简单例题：,算法分析的目的是( ) A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进 答案： D 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的 【 1 】 。 【答案】:时间复杂度和空间复杂度,1.2 数据结构的基本概念,利用计算机进行数据处理是计算机应用的一个重要领域。在进行数据处理时，实现需要处理的数据元素一般很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省

12、计算机的存储空间，这是进行数据处理的关键问题。,1.2 数据结构的基本概念,数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题。 （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。,1.2.1 什么是数据结构,数据结构是指相互有关联的数据元素的集合。 更通俗地说，数据结构是指带有结构的数据元素的集合。在此，所谓结构实际上就是指数据元素之间的前后件关系。 由上所述，一个数据结构应包含以下两方面的信息： 1）表示数据元素的信息； 2）表示各数据元素之间的前后件

13、关系。,数据的逻辑结构和存储结构,数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构） 常用的存储结构有顺序、链接、索引等。 采用不同的存储结构，其数据处理的效率是不同的。,1.2.2 数据结构的图形表示,在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点），其他称为内部结点。,插入和删除是对数据结构的两种基本运算。此外对数据结构的运算还有查找、分类、合并、分解、复制和修改等。,1.2.3 线性结构与非线性结构,线性结构条件： 1）有且只有一个根结点； 2）每一个结点最多有一

14、个前件，也最多有一个后件。 3）在一个线性结构中插入或删除任何一个结点后还应该是线性结构。 非线性结构：不满足线性结构条件的数据结构。,NCRE考题,2004.9 （2）以下数据结构中不属于线性数据结构的是 A）队列 B）线性表 C）二叉树 D）栈 （2）数据的逻辑结构在计算机存储空间中的存放形式称为数据的_存储结构_。 2005.4 （1）数据的存储结构是指 A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 解析：见上题！,NCRE考题,2005.9 （4）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数

15、据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 解析：数据的存储结构是指数据的逻辑结构在计算机中的表示，一种逻辑结构可以表示成多种存储结构；而采用不同的存储结构，其数据处理效率是不同的。,NCRE考题,2007.9 （5）下列叙述中正确的是 A)程序执行的效率与数据的存储结构密切相关 B)程序执行的效率只取决于程序的控制结构 C)程序执行的效率只取决于所处理的数据量 D)以上三种说法都不对 解析：程序执行的效率与很多因素有关，如数据的存储结构、

16、程序所处理的数据量、程序所采用的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别，其中链式存储结构的效率要高一些。,NCRE考题,（6）下列叙述中正确的是 A)数据的逻辑结构与存储结构必定是一一对应的 B)由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 C)程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构 D)以上三种说法都不对 解析：数据的逻辑结构与数据在计算机中的存储方式无关，他用来抽象的反应数据元素之间的逻辑关系，所以A错。存储结构分为顺序存储和链式存储，其中顺序存储是将逻辑上相邻的数据元素存储在物理上相邻的存储单元

17、中，节点间的关系由存储单元的相邻关系决定它主要用于存储线性结构的数据，故B错。数组的存储方式连续是指其在计算机中的存储方式，他可以用来处理非线性结构，所以C错误。,简单例题：,链表不具有的特点是（ ） A) 不必事先估计存储空间 B) 可随机访问任一元素 C) 插入删除不需要移动元素 D) 所需空间与线性表长度成正比 答案： B 数据结构分为逻辑结构与存储结构，线性链表属于 【1】 。 【答案】存储结构 数据结构中，与所使用的计算机无关的是数据的( C ) A) 存储结构B) 物理结构 C) 逻辑结构D) 物理和存储结构 数据的逻辑结构有线性结构和 【2】两大类。 【答案】非线性结构,简单例题

18、：,顺序存储方法是把逻辑上相邻的结点存储在物理位置 【3】 的存储单元中。 【答案】相邻 数据处理的最小单位是( ) A)数据 B)数据元素 C) 数据项 D) 数据结构 答案： C 数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及( ) A) 数据的存储结构 B) 计算方法 C) 数据映象 D) 逻辑存储 答案： A,简单例题：,线性表的顺序存储结构和线性表的链式存储结构分别是( ) A) 顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的

19、存储结构 答案： B,简单例题：,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成( ) A) 动态结构和静态结构 B) 紧凑结构和非紧凑结构 C) 线性结构和非线性结构 D) 内部结构和外部结构 答案： C 数据结构包括数据的逻辑结构、数据的 【4】 以及对数据的操作运算。 【答案】物理结构（或存储结构） 数据的基本单位是 【5】 。 【答案】数据元素,简单例题：,下列叙述中，错误的是（ ） A) 数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储

20、结构 答案： B 数据的存储结构是指（ B ） A）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示 C）数据在计算机中的顺序存储方式 D）存储在外存中的数据 答案： B,1.3线性表及其顺序存储结构,1.3.1 线性表的基本概念 线性表是最简单、最常用的一种数据结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他

21、所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。,1.3.2 线性表的顺序存储结构,在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 线性表的顺序存储结构具有以下两个基本特点： 1）线性表中所有元素的所占的存储空间是连续的； 2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。,1.3.3 顺序表的插入运算,在i的位置上插入x,1.3.4 顺序表的删除运算,（a）删除ai前 （b）删除ai后,历年

22、考题,没有出现过,简单例题：,顺序存储方法是把逻辑上相邻的结点存储在物理位置 【1】 的存储单元中。 【答案】相邻 长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【2】 。 【答案】 n/2 线性表L=(a1,a2,a3,ai，an)，下列说法正确的是（ ） A) 每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小 D) 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件 答案： D,简单例题：,当线性表采用顺序存储结构实现存储时，其主要特点

23、是【1】。 【答案】逻辑结构中相邻的结点在存储结构中仍相邻。 线性表若采用链式存储结构时，要求内存中可用存储单 元的地址（ ） A) 必须是连续的 B) 部分地址必须是连续的 C) 一定是不连续的 D) 连续不连续都可以 答案： D 下列叙述中，错误的是（ ） A) 数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构 答案： B,1.4 栈和队列,1.4.1栈及其基本运算,1定义 栈（Stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在

24、表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈的插入操作通常称为入栈（push），而栈的删除操作则称为出栈或退栈（top）。当栈中无数据元素时，称为空栈。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。,2.栈的顺序存储及其运算,栈的基本运算： （1）插入元素称为入栈运算； （2）删除元素称为退栈运算； （3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。,1.4.2 队列及其基本运算,1.什么是队列 队列（Queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只

25、允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。 根据队列的定义可知，队头元素总是最先进队列，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO，First In First Out）的原则组织数据的，因此，队列也被称为“先进先出”表。,队列示意图,2.循环队列及其运算,在实际应用中，队列的顺序存储结构一般采用循环队列的形式。,历年考题栈,2005.4 （2）下列关于栈的描述中错误的是 A）栈是先进后出的线性

26、表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针 解析：栈是限定只在一端进行插入与删除的线性表，一端称为栈顶，另一端称为栈底，栈是按照“后进先出”或者“先进后出”的原则组织数据的，栈具有记忆功能。 2005.9 （3）下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 解析：栈是特殊的线性表。在栈顶既可以插入也可以删除，但是栈底不可以插入和删除元素。,历年考题栈,2006.4 （4）按照“后进先

27、出”原则组织数据的数据结构是 A）队列 B）栈 C）双向链表 D）二叉树 2006.9 （4）按“先进后出”原则组织数据的数据结构是_栈_。 2008.4 （7）下列关于栈的叙述正确的是 A)栈按“先进先出”组织数据 B) 栈按“先进后出”组织数据 C)只能在栈底插入数据 D)不能删除数据,历年考题队列,2005.9 （5）数据结构分为逻辑结构和存储结构，循环队列属于_存储结构_结构。 是顺序存储结构 2006.9 （5）数据结构分为线性结构和非线性结构，带链的队列属于_线性结构_。 2007.4 （5）下列对队列的叙述正确的是 A）队列属于非线性表 B）队列按“先进后出”原则组织数据 C）队

28、列在队尾删除数据 D）队列按“先进先出”原则组织数据 解析：允许插入的一端叫队尾，允许删除的一端叫对首。,历年考题队列,2007.9 (3)线形表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线形表，循环队列是队列的【3】存储结构。答案：链式,历年考题队列,2008.4 (3)设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29(指向队尾元素)，则该循环队列中共有 【3】 个元素。答案：24 解析：实现循环队列时，头指针指向第一个元素的前一个空间，尾指针指向最后一个元素。因此，此时队列中6，7，8.29这24个空间存有元素，所以29-5

29、=24个元素。,简单例题：,栈和队列的共同特点是（ ） A)都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点 答案： C 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（ ） A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意顺序 答案： B,简单例题：,一些重要的程序语言(如C语言和Pascal语言) 允许过程的递归调用。而实现递归调用中的存储分配通常用（ ） A) 栈 B) 堆 C) 数组 D) 链表 答案： A 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E 入栈前，栈中元素可以出栈，

30、则出栈序列可能是（ ） A) ABCED B) DCBEA C) DBCEA D) CDABE 答案： B,简单例题：,栈通常采用的两种存储结构是（ ） A) 线性存储结构和链表存储结构 B) 散列方式和索引方式 C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构 答案： A 栈和队列通常采用的存储结构是 【1】。 【答案】链式存储和顺序存储 下列数据结构中，按先进后出原则组织数据的是（ ） A) 线性链表 B) 栈 C) 循环链表 D) 顺序表 答案： B,简单例题：,当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为【2】。 答案：上溢 由两

31、个栈共享一个存储空间的好处是（ ） A) 减少存取时间，降低下溢发生的机率 B) 节省存储空间，降低上溢发生的机率 C) 减少存取时间，降低上溢发生的机率 D) 节省存储空间，降低下溢发生的机率 答案： B,简单例题：,下列关于栈的叙述中正确的是（ ） )在栈中只能插入数据 B）在栈中只能删除数据 C）栈是先进先出的线性表 D）栈是后进先出的线性表 答案： D 下列关于队列的叙述中正确的是（ ） ）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线性表 D）队列是后进先出的线性表 答案： C,1.5 线性链表,1.5.1 线性链表的基本概念 数据结构中的每一个结点对应于一个

32、存储单元，这种存储单元称为存储结点，简称结点。 结点由两部分组成： （1）用于存储数据元素值，称为数据域； （2）用于存放指针，称为指针域，用于指向前一个或后一个结点。 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。,线性表中存储结点的结构,1.5.2 线性链表的基本运算,线性链表的运算主要有以下几个： 在线性链表中包含指定元素的结点之前 插入一个新元素。 在线性链表中删除包含指定元素的结点。 将两个线性链表按要求合并成一个线性 链表。,插入,线性链表的插入是指在链式存储结构下 的线性表中

33、插入一个新元素。 为了要在线性链表中插入一个新元素， 首先要给该元素分配一个新结点，然后将存 放新元素值的结点链接到线性链表中指定的 位置。,删除,线性链表的删除指在链式存储结构下的 线性表中删除包含指定元素的结点。 为了在线性链表中删除包含指定元素的 结点，首先要在线性链表中找到这个结点， 然后将要删除结点放回到可利用栈。,1.5.3 循环链表及其基本运算,前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题。在运算过程中，对于空表和对一个结点的处理必须单独考虑，使空表与非空表的运算不统一。为了克服线性表的这个缺点，可以采用另外一种链接方式，即循环链表（Circular

34、Linked List）。循环链表是另一种形式的链式存储结构。它是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其他的结点。,循环链表,循环链表具有以下两个特点：（1）在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。（2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中所有结点的指针构成了一个环状链。在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这点。 由于在循环链表中设置了

35、一个表头结点，因此在任何情况下，循环链表中至少有一个结点存在，从而使空表的运算统一。,在实际应用中，循环链表与线性单链表相比主要有以下两个方面的优点： 在循环链表中，只要指出表中任何一个结点 的位置，就可以从它出发访问到表中其他所 有的结点。 由于在循环链表中设置了一个表头结点，因 此，在任何情况下，循环链表中至少有一个 结点存在，从而使空表与非空表的运算统一。,历年考题,2005.4 （5）下列对于线性链表的描述中正确的是 A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件与元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的

36、前面 D）存储空间必须连续，且各元素的存储顺序是任意的 解析：在链式存储结构中，存储数据结构的存储空间可以不连续，各数据节点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。,1.6 树与二叉树,1.6.1 树的基本概念 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树

37、的深度。,1.6.2 二叉树及其基本性质,二叉树的特点： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,二叉树的基本性质：,性质一：度为0的结点（即叶子结点）总是比度为2的结点多一个； 例子1：某二叉树中度为2的结点有18个，则该二叉树中有 19 个叶子结点。,二叉树的基本性质：,性质2：二叉树的第i层上至多有2 i-1（i 1）个 结点。,第三层上(i=3)，有23-1=4个节点。 第四层上(i=4)，有24-1=8个节点。,二叉树的基本性质：,性质3：深度为h的二叉树中至多含有2h-1个 结点。,此树的深度h=4，共有24-1=15个

38、节点。,满二叉树,满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。,满二叉树的特点： 每一层上都含有最大结点数。,完全二叉树,完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。 注意：满二叉树是完全二叉树，完全二叉树 不一定是满二叉树。,完全二叉树的特点：除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置。,规律总结：,对于完全二叉树而言，如果它的结点个数为偶数，则该二叉树中：叶子结点的个数=非叶子结点的个数；如果它的结点个数为奇数，则该二叉树中：叶子结点

39、的个数=非叶子结点的个数+1，即叶子结点数比非叶子结点数多一个。,简单例题：,1、设一棵完全二叉树共有700个结点，则 在该二叉树中有 350 个叶子结点。 2、在深度为5的满二叉树中，叶子结点的 个数为（ C ） A) 32 B) 31 C) 16 D) 15,1.6.3 二叉树的存储结构,在计算机中，二叉树存储结构采用链式存储结构。,对于满二叉树与完全二叉树可以按层序进行顺序存储。,1.6.4 二叉树的遍历,二叉树的遍历是指不重复地访问二叉树中的所有结点。 二叉树的遍历： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树； （2）中序遍历（LDR），首先遍历左子树，

40、然后访问根结点，最后遍历右子树； （3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。,1. 前序遍历（DLR）,前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。即： 若二叉树为空则结束返回，否则： （1）访问根结点 （2）前序遍历左子树 （3）前序遍历右子树 注意的是：遍历左右子树时仍然采用前序遍历方法。 例：如图二叉树， 则前序遍历结果是：A B D E C F,2. 中序遍历（LDR）,中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结

41、点，最后遍历右子树。即： 若二叉树为空则结束返回，否则： （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树。 注意的是：遍历左右子树时仍然采用中序遍历方法。 例：如图二叉树， 则中序遍历结果是：D B E A F C,3. 后序遍历（LRD）,后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。即： 若二叉树为空则结束返回，否则： （1）后序遍历左子树， （2）后序遍历右子树 （3）最后访问根结点。 注意的是：遍历左右子树时仍然采用后序遍历方法。 例：如图二叉树，,例:,A B D E C F G,D B E

42、 A F G C,D E B G F C A,前序遍历：,中序遍历：,后序遍历：,历年考题,【2005年4月填空第1题】（1）某二叉树中度为2的结点有18个，则该二叉树中有_19_个叶子结点。 在任意一棵二叉树中，度为零的节点总比度为二的节点多一 【2005年9月填空第4题】（4）一棵二叉树第六层（根结点为第一层）的结点数最多为_32_个。 对于深度为6的二叉树来说，第6层的节点数最多为二的六减一次方即32 【2007年4月选择第7题】（7）某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为 A）n+1 B）n-1 C）2n D）n/2 对于任何一颗二叉树T，如果其叶子节点数为N1，度为

43、2的节点数为N2，则N1=N2+1。,历年考题,提示：注意度和深度的区别，度是横向的子节点数，深度是纵向的辈分 【2007年4月填空第1题】（1）在深度为7的满二叉树中，度为2的结点个数为 63 。 解析：深度为七的满二叉树有27-1=127个节点，又因为在任意二叉树中，若终端节点个数为N0，度为2的节点数为N2,则N0=N2+1，即总结点数为N0+N2=2N2+1=127,N2=63 【2007年9月选择第8题】（8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 A)219 B)221 C)229 D)231 解析：任意二叉树度为0的节点数始终是比度为2的节点

44、数多一个，总结点数=度为0的节点数+度为1的节点数+度为2的节点数 【2008年4月填空第2题】（2）深度为5的满二叉树有16 个叶子结点。解析：2的五减一次方,【2006年4月选择第6题】,（6）对下列二叉树 进行后序遍历的结果为 A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA,【2007年4月选择第6题】,（6）对下列二叉树 进行前序遍历的结果为 A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ,【2007年9月填空第4题】,（4）对下列二叉树进行中序遍历的结果为 【4】 。,答案：ACBDFEHGP,二叉树的遍历 模拟

45、题,1、设一棵二叉树的中序遍历结果为DBEAFC, 前序遍历结果为ABDECF，则后序遍历结 果为： DEBFCA 2、已知一棵二叉树前序遍历和中序遍历分别 为ABDEGCFH和DBGEACHF，则该二叉树 的后序遍历为（ B ） A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG,二叉树的遍历 模拟题,具有3个结点的二叉树有（ D ） A) 2种形态 B) 4种形态 C) 7种形态 D) 5种形态 设有下列二叉树： 对此二叉树前序遍历的结果为（ B ） A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT,

46、1.7 查找技术,查找是指在一个给定的数据结构中查找某个指定的元素。 1.7.1 顺序查找 顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查找到所要的元素为止；否则就是表中没有要找的元素，查找不成功。对于表中记录的关键字是无序的表，只能采用这种方法。 顺序查找的使用情况： （1）线性表为无序表； （2）表采用链式存储结构。,1.7.2 二分法查找,二分查找又称折半查找，是针对有序表进行查找的简单、有效而又较常用的方法。所谓有序表，即要求表中的各元素按关键字的值有序（升序或降序）存放。只适用于顺序存储的有序表，

47、对于长度为n的有序线性表，最坏情况只需比较log2n次。,历年考题,2005.4 （4）对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 A）log2n B）n/2 C）n D）n+1 2005.9 （2）下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 2006.9 （8）在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为 A）63 B）64 C）6 D）7,1.8 排序技术,排序也是数据处理的重要内容。 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。,2005年4月 选择题第3题、第4题

48、,（3）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 A）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/2 2006年4月 填空题第1题 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为_。,NCRE考题,2007年9月 选择题第7题 （7）冒泡排序在最坏情况下的比较次数是 A)n(n+1)/2 B)nlog2n C)n(n-1)2 D)n/2 2008年4月 选择题第6题 对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是 A)快速排序 B) 冒泡排序 C) 直接插入排序 D) 堆排序,

49、第二章 程序设计基础,2.1 程序设计 2.2 结构化程序设计 2.3 面向对象程序设计,2.1 程序设计方法与风格,如何形成良好的程序设计风格 1、源程序文档化； 2、数据说明的方法； 3、语句的结构； 4、输入和输出。 注释分序言性注释和功能性注释。 语句结构清晰第一、效率第二。,2.2 结构化程序设计,结构化程序设计方法的四条原则是： 1.自顶向下； 2.逐步求精； 3.模块化； 4.限制使用goto语句。,结构化程序的基本结构和特点：,（1）顺序结构：一种简单的程序设计，最基本、最常用的结构； （2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分

50、支来执行相应的语句序列； （3）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。,2.3 面向对象的程序设计,面向对象的程序设计（Object-Oriented Programming，OOP）是一种把面向对象的 思想应用于软件开发过程中，指导开发活动 的系统方法，简称OO方法，它是建立在对 象概念（对象、类和继承）基础上的方法。,面向对象程序设计方法的优点：,（1）从认知学的角度来看，面向对象方法符 合人们对客观世界的认识规律。 （2）面向对象方法开发的软件系统易于维护， 其体系结构易于理解、扩充和修改。 （3）面向对象方法中的继承机制有力地支持 软件的复用。,2

51、.3.2 面向对象的基本概念,对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。 面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。,属性、操作、封装,属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。 属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。 操作描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。操作的过程对外是封闭的，即用户只能看到这一操作实施后的结果。这相当于事先已经设计好的各种过程，只需要

52、调用就可以了，用户不必去关心这一过程是如何编写的。事实上，这个过程已经封装在对象中，用户也看不到。对的这一特性即是对象的封装性。,类、消息,对象的基本特点： （1）标识惟一性； （2）分类性； （3）多态性； （4）封装性； （5）模块独立性好。 类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。 消息是一个实例与另一个实例之间传递的信息。 消息的组成包括（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。,继承,继承是指能够直接获得已有的性质和特征，而不必重复定义他们。 继承分单继承和多重继承。单继承指一个类只允许有一个父类，多

53、重继承指一个类允许有多个父类。,多态性,多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。,历年考题,2005.4 (2)在面向对象方法中，类的实例称为_对象_。 2006.4 (1)下列选项中不属于结构化程序设计方法的是 A）自顶向下B）逐步求精C）模块化D）可复用 (2)在面向对象方法中，_类_描述的是具有相似属性与操作的一组对象。2006.9 (1)下列选项中不符合良好程序设计风格的是 A）源程序要文档化 B）数据说明的次序要规范化 C）避免滥用goto语句 D）模块设计要保证高耦合、高内聚（高内聚低耦合）,历年考题,2007.4 (2)在结构化程序设计中，模块划分的原则

54、是 A）各模块应包括尽量多的功能 B）各模块的规模应尽量大 C）各模块之间的联系应尽量紧密 D）模块内具有高内聚度、模块间具有低耦合度 (4)下面选项中不属于面向对象程序设计特征的是 A）继承性 B）多态性 C）类比性 D）封装性,历年考题,2007.9 (3)在面向对象方法中，实现信息隐藏是依靠 A)对象的继承 B)对象的多态 C)对象的封装 D)对象的分类 (4)下列叙述中，不符合良好程序设计风格要求的是 A)程序的效率第一，清晰第二 B)程序的可读性好 C)程序中要有必要的注释 D)输入数据前要有提示信息 (5)下列叙述中正确的是 A)程序执行的效率与数据的存储结构密切相关 B)程序执行

55、的效率只取决于程序的控制结构 C)程序执行的效率只取决于所处理的数据量 D)以上三种说法都不对 2008.4 (2)结构化程序设计的基本原则不包括 A)多态性 B)自顶向下 C)模块化 D)逐步求精,例题讲解,结构化程序设计的3种结构是（ D ） A) 顺序结构、选择结构、转移结构 B) 分支结构、等价结构、循环结构 C) 多分支结构、赋值结构、等价结构 D) 顺序结构、选择结构、循环结构 在设计程序时，应采纳的原则之一是（ D ） A) 不限制goto语句的使用 B) 减少或取消注解行 C) 程序越短越好 D) 程序结构应有助于读者理解,程序设计语言的基本成分是数据成分、运算成分、控制成 分

56、和（ D ） A) 对象成分 B) 变量成分 C) 语句成分D) 传输成分 结构化程序设计主要强调的是（ D ） A) 程序的规模B) 程序的效率 C) 程序设计语言的先进性 D) 程序易读性 以下不属于对象的基本特点的是（ A ） A) 分类性 B) 多态性 C) 继承性D) 封装性,对建立良好的程序设计风格，下面描述正确的是（ A ） A) 程序应简单、清晰、可读性好 B) 符号名的命名只要符合语法 C) 充分考虑程序的执行效率 D) 程序的注释可有可无 在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（C） A) 安全性 B) 一致性

57、C) 可理解性D) 合理性,下列叙述中，不属于结构化程序设计方法的主要原则的是（B） A) 自顶向下 B) 由底向上 C) 模块化D) 限制使用goto语句 对象实现了数据和操作的结合，是指对数据和数据的操作 进行（ C ） A) 结合 B) 隐藏 C) 封装 D) 抽象 在面向对象方法中，一个对象请求另一个对象为其服务的 方式是通过发送（ D ） A）调用语句 B）命令 C）口令 D）消息,信息屏蔽的概念与下述哪一种概念直接相关（ B ）A）软件结构定义 B）模块独立性C）模块类型划分 D）模块偶合度 下列对对象概念描述错误的是（ A ）A）任何对象都必须有继承性B）对象是属性和方法的封装体

58、C）对象间的通讯靠消息传递D）操作是对象的动态属性,面向对象的设计方法与传统的面向过程的方法有本质的不同,它的基本原理是（ C ） A) 模拟现实世界中不同事物之间的联系 B) 强调模拟现实世界中的算法而不强调概念 C) 使用现实世界的概念抽象地思考问题从而自然地解决问题 D) 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考 在面向对象的程序设计中，类描述的是具有相似性质的一组 【1】。【答案】对象 在面向对象方法中，类之间共享属性和操作的机制称为 【2】。【答案】继承 一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的 【3】。【答案】可重用性,面向对象的模

59、型中，最基本的概念是对象和【4】。 【答案】：类 在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为【5】。 【答案】：消息在程序设计阶段应该采取 【6】 和逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，进而用某种程序设计语言写成程序。 【答案】 ：自顶向下,【7】 是一种信息隐蔽技术，目的在于将对象的使用者和对象的设计者分开。【答案】 ：封装可以把具有相同属性的一些不同对象归类，称为 【8】 。 【答案】 ：对象类子程序通常分为两类： 【9】 和函数，前者是命令的抽象，后者是为了求值。 【答案】 ：过程源程序文档化要求程序应加注释。注释一般分为序言性注释

60、和【10】 。 【答案】 ：功能性注释在面向对象方法种，信息屏蔽是通过对象的【11】 性来实现的。 【答案】 ：封装类是一个支持集成的抽象数据类型，而对象是类的【12】 。 【答案】 ：实例 在面向对象方法种，类之间共享属性和操作的机制称为【13】 。 【答案】 ：继承,第三章 软件工程,3.1 软件工程的基本概念 3.2 结构化分析方法 3.3 结构化设计方法 3.4 软件测试 3.5 软件调试 3.6 软件维护,历年考点分析,31 软件工程基本概念,计算机软件是包括程序、数据及相关文档的完整集合。 软件的特点包括： （1）软件是一种逻辑实体； （2）软件的生产与硬件不同，它没有明显的制作过

61、程； （3）软件在运行、使用期间不存在磨损、老化问题； （4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题； （5）软件复杂性高，成本昂贵； （6）软件开发涉及诸多的社会因素。,31 软件工程基本概念,软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。 软件危机主要表现在成本、质量、生产率等问题。 软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。 软件工程包括3个要素：方法、工具和过程。 方法是完成软件工程项目的技术手段； 工具支持软件的开发、管理文档生成； 过程支持软件开发的各个环节的控制、管理。 软件工程过

62、程是把输入转化为输出的一组彼此相关的资源和活动，包含4种基本活动： （1）P软件规格说明；Plan （2）D软件开发； Do （3）C软件确认； Check （4）A软件演进。 Action,软件周期,软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。 软件生命周期三个阶段:软件定义、软件开发、运行维护，主要活动阶段是： （1）可行性研究与计划制定； （2）需求分析； （3）软件设计； （4）软件实现； （5）软件测试； （6）运行和维护。,软件工程的目标和与原则：,目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性

63、和可互操作性且满足用户需求的产品。 基本目标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发软件易于移植；需要较低的费用；能按时完成开发，及时交付使用。 基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。,软件工程,软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。 软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。 软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容。 软件管理学包括人员组织、进度安排、质量保证、配置管理、项目计划等。,历届试题,2005.4 （8）下列描述中正确的是 A）程序就是软

64、件 B）软件开发不受计算机系统的限制 C）软件既是逻辑实体，又是物理实体 D）软件是程序、数据与相关文档的集合 2005.9 （5）下列描述中正确的是 A）软件工程只是解决软件项目的管理问题 B）软件工程主要解决软件产品的生产率问题 C）软件工程的主要思想是强调在软件开发过程中需要应用工程化原则 D）软件工程只是解决软件开发中的技术问题,历届试题,2006.9（3）下列选项中不属于软件生命周期开发阶段任务的是 A）软件测试B）概要设计 C）软件维护D）详细设计 2007.4 （4）软件生命周期可分为多个阶段，一般分为定义阶段、开发阶段和维护阶段。编码和测试属于 【4】 阶段。开发 2007.9

65、 （1）软件是指 A)程序 B)程序和文档 C)算法加数据结构 D)程序、数据与相关文档的完整结合,32 结构化分析方法,结构化方法的核心和基础是结构化程序设计理论。 需求分析方法有 （1）结构化需求分析方法； （2）面向对象的分析的方法。 从需求分析建立的模型的特性来分：静态分析和动态分析。,3.2.1需求分析与需求分析方法,1.需求分析 需求分析是指用户对目标系统的功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析将创建所需数据模型、功能模型和控制模型。 （1）需求分析定义 1997年IEEE软件工程标准对需求分析定义如下： 用户解决问题或达到目标所需的条件或权能 系统或系统部件要满足合同、标准、规范或其他正式规定文档所需具有的条件或权能 一种反映前面所述的条件或权能的文档说明。 （2）需求分析阶段的工作 需求分析阶段包括四个方面： 需求获取。确定对目标系统的各方面需求。 需求分析。对获取的需求进行分析和综合，最终给出系统的解决方案和目标系统的逻辑模型。 编写需求规格说明书。说明书作为需求分析的阶段成果，可为用户、分析人员和设计人员之间的交流提供方便，可以直接支持目标软件系统的确认，又可以作为