NCRE二级公共基础知识讲义.ppt

1、全国计算机等级考试,National Computer Rank Examination,二级 公共基础知识,全国计算机等级考试,二级公共基础知识,2,二级公共基础知识考试内容,数据结构和算法 程序设计基础 软件工程 数据库设计基础,全国计算机等级考试,二级公共基础知识,3,1、二级公共基础的考试方式为笔 试，与各科语言的笔试部分合 为一张试卷。公共基础部分占 全卷的30分。 2、公共基础知识有10道选择题和 5道填空题。,二级公共基础知识考试方式,全国计算机等级考试,二级公共基础知识,4,理解基本概念 多做练习 适当记忆一些名词 与所学程序设计语言结合起来理解,二级公共基础知识学习方法,第一

2、章 数据结构和算法,全国计算机等级考试,二级公共基础知识,6,本章知识要点,算法,算法的定义,算法的特征,算法复杂度,数据结构,数据结构的定义,逻辑结构 和 物理结构,线性结构 和 非线性结构,顺序表、链表、堆栈 队列、循环队列、树,算法的基本要素,全国计算机等级考试,二级公共基础知识,7,算法是对特定问题求解步骤的一种描述。,一、算法,算法的特性： （1）有穷性：算法必须在有限的次数内完成。 （2）确定性：算法的每一步必须是明确的。 （3）可行性：算法的每一步必须是可以实现的。 （4）拥有足够的情报：算法必须有一定的输入和输出。,全国计算机等级考试,二级公共基础知识,8,算法的基本要素： （

3、1）对数据对象的运算和操作： A .算术运算 B .逻辑运算 C .关系运算 D .数据传输 （2）算法的控制结构： A .顺序结构 B .选择结构 C .循环结构,全国计算机等级考试,二级公共基础知识,9,算法的复杂度：衡量算法优劣的量。 （1）时间复杂度：算法的时间耗费。 A .算法中基本操作重复执行次数和算法执行时间 同步增长，称作算法的时间复杂度。 B .算法中基本操作重复执行次数和问题规模有关， 是问题规模的函数。 C .算法的时间复杂度是指执行算法所需要的计算工 作量。 （2）空间复杂度：执行算法所需要的内存空间。,全国计算机等级考试,二级公共基础知识,10,二、数据结构,数据结构

4、主要研究两方面的问题： （1）数据本身。 （2）数据之间的前后件关系。,数据结构表示为：DS=D，S 例：D=春，夏，秋，冬 S=(春,夏)，(夏,秋)，(秋,冬)，(冬,春),全国计算机等级考试,二级公共基础知识,11,数据的结构分为： （1）物理结构：数据在计算机存储介质中真正存储的结构， 也被称为“存储结构” （2）逻辑结构：人们所理解的数据之间的结构，可以用图示 的方法绘画出来的数据之间的结构。,例：一个班由35名同学，他们的座位牌号就是物理结构， 一次考试的排名是逻辑结构。1,注意：逻辑结构和物理结构没有必然的联系，也不一定是 一一对应的。,全国计算机等级考试,二级公共基础知识,12

5、,数据的结构分为： （1）线性结构： 非空数据结构同时满足以下两个条件就是线性结构： A .有且仅有一个根结点； B .除头结点和尾结点外，任何结点有且仅有一个前件 和一个后件。 （2）非线性结构：除了线性结构都是非线性结构。,全国计算机等级考试,二级公共基础知识,13,全国计算机等级考试 二级公共基础知识 要求掌握的数据结构共有以下六种：,线性表 堆栈 队列 循环队列 线性链表 树和二叉树,线 性 结 构,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构不相同,物理结构和逻辑结构不相同,非线性结构,全国计算机等级考试,二级公共

6、基础知识,14,10,20,30,40,50,60,70,80,三、顺序表：顺序表就是数组,1、顺序表也叫做线性表，属于线性结构。 线性表的逻辑结构和物理结构相同。 2、特点： （1）有且仅有一个头结点（根节点）和尾结点。 （2）任意其他结点至多有一个前件，一个后件。 （3）头结点没有前件，尾结点没有后件。,全国计算机等级考试,二级公共基础知识,15,四、堆栈,1、定义：只允许在栈顶位置插 入数据和删除数据的线性结 构是堆栈，简称为“栈”。 2、堆栈属于线性结构。 3、堆栈的逻辑结构和物理结构 相同。 4、特点：先进后出，后进先出 所以堆栈也叫做先进后出表 （FILO） 5、堆栈具备存储功能：

7、函数的 递归调用和表达式求解都用 到了堆栈。,全国计算机等级考试,二级公共基础知识,16,入栈顺序：a、b、c、d、e、f,栈空,a,b,a,c,b,a,b,a,d,b,a,.,入a,入b,入c,出c,入d,模拟堆栈的数据出入过程：,全国计算机等级考试,二级公共基础知识,17,【典型题型】假设一个堆栈，入栈顺序为abcde，认为在任何时 刻均允许出栈，下列选项中不可能的出栈顺序为： A）abcde（可能） B）edcba（可能） C）cdeba（可能） D）cdeab（不可能）,如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（ ） A) e3,e1,e4,e2 B) e2,e4,e3

8、,e1 C) e3,e4,e1,e2D) 任意顺序,栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（ ） A) ABCED B) DCBEA C) DBCEA D) CDABE,全国计算机等级考试,二级公共基础知识,18,五、队列,1、队列属于线性结构。 2、队列的逻辑结构和物理结构相同。 3、定义：入队操作发生在队尾，出队操作发生在队头。 4、特点：先进先出，后进后出，所以队列也叫做先进先 出表（FIFO）。,全国计算机等级考试,二级公共基础知识,19,六、循环队列,rear,front,全国计算机等级考试,二级公共基础知识,20,入队顺序：a

9、、b、c、d、e、f,模拟循环队列的数据出入过程：,循环队列空 front=rear,rear,front,a,front,rear,数据a入队,a,front,rear,b,数据b入队,front,rear,b,数据a出队,全国计算机等级考试,二级公共基础知识,21,七、线性链表,1、链表属于线性结构。 2、链表的逻辑结构和物理结构不相同。 3、线性链表由结点组成： 每个结点有两个区域：数据域，指针域。 A .数据域，用来存储数据。 B .指针域，用来指向下一个结点的位置。 3、绘画一个由5个节点组成的线性链表，数据为1、2、3、4、5。,全国计算机等级考试,二级公共基础知识,22,链表的种

10、类：单链表、循环链表、双向链表。,1,2,3,4,5,1,2,3,4,5,循环链表,双向链表,1,2,3,4,5,全国计算机等级考试,二级公共基础知识,23,八、树与二叉树,1、树属于非线性结构。 2、树的逻辑结构和物理结构不相同。 3、树有且仅有一个根节点。,根节点,x,e,o,q,k,b,g,全国计算机等级考试,二级公共基础知识,24,二叉树：每个结点最多分两叉的有序树。,二叉树,二叉树的术语,有序树与无序树,二叉树的五种基本结构,满二叉树 和 完全二叉树,二叉树的计算,二叉树的遍历,全国计算机等级考试,二级公共基础知识,25,1、二叉树的术语：,A .结点、根节点、叶子节点： （1）构成

11、树的基本结构是结点。 （2）没有父结点的结点是根节点。 （3）没有子结点的结点是叶子节点（度为0的结点）。 B .结点的度：结点子结点的个数。 C .树的度：树中度数最大的结点的度就是树的度。 D .树的高度/层数：树有多少层。 E .父结点、子结点、双亲结点、孩子结点、 左孩子、右孩子、兄弟结点、堂兄结点。,全国计算机等级考试,二级公共基础知识,26,2、有序树与无序树：,e,A,B,e,B,A,二叉树和度为二的树的区别： A .二叉树是有序树，度为二的树是普通树，属于无序树。 B .二叉树允许为空，度为二的数至少有三个结点。 【普通树不允许为空，至少有一个结点】,全国计算机等级考试,二级公

12、共基础知识,27,3、二叉树的五种基本结构：,全国计算机等级考试,二级公共基础知识,28,4、满二叉树和完全二叉树：,A .满二叉树：二叉树的每一层均具备该层最大结点个数。 （即：不具备度为1的结点） B .完全二叉树：满二叉树是一个特殊的完全二叉树。将所有结点 自上向下、自左向右编号，结点编号连续而不缺失。,满二叉树,完全二叉树,1,2,3,4,5,6,全国计算机等级考试,二级公共基础知识,29,5、二叉树的计算：,A .二叉树第n层的最大结点个数：2n-1。 B .n层满二叉树的结点个数：2n-1。 C .n层完全二叉树的最小结点个数：2n-1。 n层完全二叉树的最大结点个数：2n-1。

13、D .度为0的结点个数表示为n0，同理，n1表示度为1的结点个数， n2表示度为2的结点个数。 则，对于任意二叉树都有：n0=n2+1。 E .结点编号：任意结点编号n，其左孩子为2n，其右孩子为2n+1。,全国计算机等级考试,二级公共基础知识,30,填空题： 设一棵完全二叉树共有700个结点，则在该二叉树中有 个叶子结点,二叉树的结点共有三种：度为0的叶子结点、度为1的结点和度为2的结点。 设度为0的叶子结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，则： n0+n1+n2=700（1） 根据二叉树性质：叶子结点个数比度为2的结点个数多1，即： n0=n2+1 （2） 将（2

14、）式带入（1）式，所以： n0+n1+n0-1=700 2n0=701-n1 完全二叉树总结点个数为偶数，则度为1的结点个数为1；完全二叉树的总结点个数为奇数，则度为1的结点个数为0。 所以：2n0=701-1，即 n0=350。,全国计算机等级考试,二级公共基础知识,31,6、二叉树的遍历：,A .前/先（根）序遍历，GLR。【根节点为序列开头】 B .中（根）序遍历，LGR。 【没有左子树，根节点为开头；没有右子树，根节点为结尾】 【左右子树均有，根节点的位置位于左子树结点个数之和+1】 C .后（根）序遍历，LRG。【根节点为序列结尾】,先序序列：xeqbog,中序序列：qebxog,后

15、序序列：qbegox,第二章 程序设计基础,全国计算机等级考试,二级公共基础知识,33,本章知识要点,面向过程的程序设计,结构化程序设计,模块化程序设计,面向对象的程序设计,对象的定义,对象的属性和方法,类和实例的派生与继承,消息与多态性,全国计算机等级考试,二级公共基础知识,34,一、程序设计方法,1、面向过程的程序设计：C语言、BASIC语言等。 （1）结构化程序设计：顺序、选择、循环。 三大结构（顺序、选择、循环）可以解决所有的问题，和 问题的规模没有关系。 （2）模块化程序设计：利用将程序分解的方法，将复杂的问题 简单化，将单一的问题分成多个模块独立解决。 C语言：模块就是函数。 VB

16、语言：模块就是模块、子例程、子程序。 VFP数据库：模块就是子程序。 Access数据库：模块就是宏、事件代码。 2、面向对象的程序设计：VB、VFP、Java、Delphi等。,全国计算机等级考试,二级公共基础知识,35,二、程序设计风格,1.源程序文档化 选择标示符的名字 注释（序言性和功能性注释） 程序的视觉组织 2.数据说明的方法 显式地说明一切变量 数据说明的次序应该规范化 说明语句中变量安排有序化 对复杂数据结构应注释说明,3.语句的结构 每条语句简单明了 尽量不用或少用GOTO语句 尽量只采用3种基本控制结构编程 4.输入和输出 对输入数据进行校验和合理性检查 输入输出格式保持一

17、致 设计良好的输出报表,全国计算机等级考试,二级公共基础知识,36,三、结构化程序设计,20世纪70年代提出了结构化程序设计（Structured Programming）,结构化程序设计的原则： （1）自顶向下。 （2）逐步求精。 （3）模块化。 （4）限制使用goto语句。,结构化程序设计的基本结构： （1）顺序结构。 （2）选择结构。 （3）重复结构。,结构化程序设计主要强调程序的易读性。,全国计算机等级考试,二级公共基础知识,37,利用图示表示顺序结构,程序流程图,N-S图,全国计算机等级考试,二级公共基础知识,38,利用图示表示选择结构,程序流程图,N-S图,全国计算机等级考试,二级

18、公共基础知识,39,利用图示表示重复结构(1),程序流程图当型循环,程序流程图直到型循环,全国计算机等级考试,二级公共基础知识,40,利用图示表示重复结构(2),S,UNTIL 条件,N-S图当型循环,N-S图直到型循环,全国计算机等级考试,二级公共基础知识,41,三、面向对象的程序设计,面向对象(Object Oriented)的程序设计方法已经发展成为主流的软件开发方法，起源于对面向对象语言的研究。20世纪60年代后期首次被提出，80年代开始走向实用。,面向对象的程序设计的术语： 对象、属性、方法、封装性、事件、类、父类、子类、实例、派生、继承、消息、多态性。,全国计算机等级考试,二级公共

19、基础知识,42,面向对象方法的主要优点： （1）与人类习惯的思维方法一致。 （2）稳定性好。 （3）可重用性好。 （4）易于开发大型软件产品。 （5）可维护性好。,全国计算机等级考试,二级公共基础知识,43,1、对象的定义,对象：现实生活中存在的可以相互区分的物体。 是属性和方法的封装。,对象的基本特点： （1）标识唯一性。 （2）分类型。 （3）多态性。 （4）封装性。 （5）模块独立型好。,全国计算机等级考试,二级公共基础知识,44,2、对象的属性和方法,属性（Property）：用来描述对象的状态，是对象的静态特性。 包括属性名和属性值两方面。 例如：“显示器”作为对象，具备“颜色”属性

20、，取值为“银白色”。 方法（Method）：用来描述对象的行为，是对象的动态特性。 方法具备方法名。 方法必须利用事件来激活。 例如:“显示器”作为对象，具备“关闭”的方法，必须用“断电”事件来激活。,属性名,属性值,方法名,事件,封装性：(Encapsulation) 对象依靠对象名将自身的属性和方法封装。,全国计算机等级考试,二级公共基础知识,45,3、类和实例的派生与继承,（1）类（Class）：具有相同属性和方法的 对象的集合，是对对象属性和方法的抽 象。 （2）实例（Instances）：类的子类派生出 的对象就是该类的一个实例。 类展现对象的共性；实例展现对象的个性。 （3）派生过

21、程中将发生属性和方法的继承 （Inheritance） 父类将自身的所有属性和方法传递 给子类，子类继承父类传递的所有属性 和方法，并产生自身特有的属性和方 法，再将这些属性和方法的总和传递给 下一级子类。,人,好人,坏人,中国人,外国人,张三,全国计算机等级考试,二级公共基础知识,46,4、消息与多态性,（1）消息（Message）：进行对象之间的信息传递。 （2）多态性（Polymorphism）：同样的消息传递给不同的对象，导致 完全不同的行动。,消息的组成： A .接收消息的对象名称。 B .消息标识符，也叫做“消息名”。 C .零个或多个参数。,全国计算机等级考试,二级公共基础知识,

22、48,本章知识要点,软件危机,软件生命周期,需求分析,概要设计,详细设计,测试,调试,软件工程,全国计算机等级考试,二级公共基础知识,49,一、软件危机,软件危机主要表现在： （1）软件需求的增长得不到满足。 （2）软件开发成本和进度无法控制。 （3）软件质量难以保证。 （4）软件不可维护或可维护度非常低。 （5）软件的成本不断提高。 （6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。,总之，可以将软件危机归结为成本、质量、生产率问题,全国计算机等级考试,二级公共基础知识,50,二、软件工程,软件工程是为了摆脱软件危机而诞生的，主要思想是在软件开发过程中应用工程化原则。,软件工程的三

23、要素：方法、工具、工程。,软件工程的主要内容：软件开发技术、软件工程管理。,软件工程的原则： （1）抽象。 （2）信息隐蔽。 （3）模块化。 （4）局部化。 （5）确定性。 （6）一致性。 （7）完备性。 （8）可验证性。,全国计算机等级考试,二级公共基础知识,51,二、软件生命周期,软件生命周期（Software Life Cycle，SLC）：将软件产品从提出、实现、使用维护到停止使用退役的过程称为“软件生命周期”。,全国计算机等级考试,二级公共基础知识,52,全国计算机等级考试,二级公共基础知识,53,三、需求分析,需求与需求分析,需求分析的方法,结构化分析方法,数据流图与数据字典,判定

24、树与判定表,软件需求规格说明书,全国计算机等级考试,二级公共基础知识,54,1、需求与需求分析,需求：用户对目标软件系统在功能、行为、性能、设计 约束等方面的期望。,需求分析：发现用户需求的过程,需求分析阶段的工作： （1）需求获取 （2）需求分析 （3）编写需求规格说明书 （4）需求评审,全国计算机等级考试,二级公共基础知识,55,2、需求分析的方法,A .面向数据流的结构化分析方法 SA。 B .面向数据结构的Jackson方法 JSD。 C .面向数据结构的结构化数据系统开发方法 DSSD。 D .面向对象的分析方法 OOA。,全国计算机等级考试,二级公共基础知识,56,3、结构化分析方

25、法：数据流图DFD,数据流图DFD中的主要图形元素：,加工/转换,数据流,存储文件/数据源,源/潭,全国计算机等级考试,二级公共基础知识,57,结构化分析方法：数据字典DD,数据字典DD是结构化分析方法的核心。,数据字典的作用：对数据流图DFD中出现的被命名图形元素进 行确切的解释。,全国计算机等级考试,二级公共基础知识,58,结构化分析方法：判定树与判定表,判定树,全国计算机等级考试,二级公共基础知识,59,判定表,全国计算机等级考试,二级公共基础知识,60,结构化分析方法：需求规格说明书,软件需求规格说明书（SRS）是需求分析阶段的最后成果，将 在软件工程的最后转换为用户手册。,软件需求规

26、格说明书的作用： （1）便于用户、开发人员进行理解和交流。 （2）反映出用户问题的结构，可作为软件开发工作的基础和 依据。 （3）作为确认测试和验收的依据。,全国计算机等级考试,二级公共基础知识,61,四、概要设计,软件设计的基本原理： （1）抽象：把事物本质的共同特性提取出来而不考虑细节。 （2）模块化：把待开发软件分解成若干个小的简单部分。 （3）信息隐蔽：在一个模块内包含的信息，对于不需要这些 信息的其他模块来说是不能访问的。 （4）模块独立性：评价设计好坏的重要度量指标。,内聚性和耦合性是模块独立性的两个定性标准： A .内聚性：一个模块内部各个元素间彼此结合的紧密程度。 B .耦合性

27、：模块间互相连接的紧密程度。 一款优秀的软件设计，应做到高内聚，低耦合。,全国计算机等级考试,二级公共基础知识,62,概要设计的任务： （1）设计软件系统结构。 （2）确定软件的每一个模块 （3）确定模块之间的调用关系 （4）评价模块结构质量。,采用的方法：结构化设计方法【SD】 使用的工具：软件结构图SC。,全国计算机等级考试,二级公共基础知识,63,认识软件结构图SC,全国计算机等级考试,二级公共基础知识,64,五、详细设计,详细设计的任务：为软件结构图中每一个模块确定实现的算法 和数据结构。表示算法和数据结构的细节。,采用的方法：结构化编程方法【SP】 使用的工具：程序流程图、N-S图、

28、问题分析图PAD 判定表 过程设计语言/伪码PDL,全国计算机等级考试,二级公共基础知识,65,程序流程图中的主要图形元素：,加工步骤,控制流,逻辑条件,全国计算机等级考试,二级公共基础知识,66,六、软件测试,软件测试的目的：尽可能多的发现错误。 （1）错误理解：软件测试为了发现错误并改正。 （2）错误理解：软件测试为了证明软件正确性。,软件测试的准则： （1）所有测试追溯到需求。 （2）严格执行测试计划，排除测试随意性。 （3）充分注意测试中的群集现象：程序中存在错误的概率与该程 序中已发现的错误数量成正比。 （4）程序员避免检测自己的程序。 （5）穷举测试不可能。 （6）妥善保存测试文档

29、，为维护提供方便。,全国计算机等级考试,二级公共基础知识,67,软件测试的方法： （1）静态测试：由人工进行，无需借助计算机。 （2）动态测试：基于计算机，实际运行软件进行测试 A .白盒测试：逻辑覆盖、基本路径测试。 B .黑盒测试：等价类划分、边界值分析、错误推测法、因果图。,软件测试的实施： 第1步：单元测试（对每一个模块进行测试） 第2步：集成测试（将模块组装起来的同时进行测试） 第3步：确认测试（验证软件的功能和性能是否满足需求） 第4步：系统测试（评估系统环境下软件的功能）,全国计算机等级考试,二级公共基础知识,68,七、软件调试（Debug）,软件调试的目的：诊断和改正程序中的错

30、误。,软件调试的基本步骤： 第1步：错误定位。【占据了调试的绝大多数工作量】 第2步：修改设计和代码，以排除错误。 第3步：进行回归测试，防止引进新的错误。,第四章 数据库设计基础,全国计算机等级考试,二级公共基础知识,70,一、理解数据库：,1、数据（Data）是描述事物的符号记录。 2、为什么引入数据库： （1）数据量大，数据多。 （2）方便查找。,全国计算机等级考试,二级公共基础知识,71,二、数据库原理术语：,1、数据（Data）是描述事物的符号记录。 2、数据库（DataBase，DB）数据的集合，是存放数据的仓库。 3、数据库管理系统（DBMS）负责数据的管理。 （1）DBMS属于

31、系统软件。 （2）DBMS是数据库系统的核心。 4、数据库应用系统（DBAS）利用DBMS开发的应用软件。 5、数据库系统（DBS）使用了数据库技术的计算机，属于硬件系统。 6、数据库管理员（DBA）是数据库系统的人的因素。负责管理、维 护、设计、监视数据库系统的运行。,全国计算机等级考试,二级公共基础知识,72,计算机硬件,操作系统,数据库管理系统,数据库应用系统,用户,Windows XP / Vista / 7 / 2003等。,Access / Visual FoxPro / SQL Server等。,全国计算机等级考试,二级公共基础知识,73,三、数据库系统的三级模式和两级映射：,数

32、据库（DB）,内模式 （物理模式）,概念模式,外模式/子模式,用户模式,外模式,应用,应用,应用,概念模式 内模式映射,外模式 - 概念模式映射,全局数据逻辑结构的描述,局部数据逻辑结构的描述,全国计算机等级考试,二级公共基础知识,74,四、数据模型：,1、数据模型的三层分类： （1）概念数据模型/概念模型 （2）逻辑数据模型/数据模型 （3）物理数据模型/物理模型 2、典型的概念数据模型：E R模型（实体 - 联系模型） （1）实体：现实生活中的事物。 （2）属性：表示实体的一些特征。 （3）联系：实体之间的关联。,全国计算机等级考试,二级公共基础知识,75,3、实体间联系： （1）一对一（1:1） 学校 - 校长 【计算机不予处理】 （2）一对多（1:m） 学生 班级 【计算机可以直接处理】 （3）多对多（m:n） 学生 课程 【转换为两个一对多联系再处理】,历史上出现过的数据模型：网状模型、层次模型、关系模型,全国计算机等级考试,二级公共基础知识,76,4、E-R模型的图示表示法：,实体,联系,实体的属性,全国计算机等级考试,二级公共基础知识,77,五、关系模型：,关系的数据结构,例：学生关系,属性,元组/记录,主键,关系就是二维表。,1、元组是有限的。 2、元组不能重复。 3、属性不能重复。 4、元素的顺序是无关的。 5、属性的顺序是无关的。,全国计算机等级