National Computer Rank Examination

Presentation on theme: "National Computer Rank Examination"— Presentation transcript:

1 National Computer Rank Examination
全国计算机等级考试 National Computer Rank Examination +

2 National Computer Rank Examination
全国计算机等级考试 National Computer Rank Examination 第一部分 公共基础知识

3 二级公共基础知识考试内容 数据结构和算法 程序设计基础 软件工程 数据库设计基础 全国计算机等级考试 二级公共基础知识

4 1、二级公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。公共基础部分占全卷的10分。
二级公共基础知识考试方式 1、二级公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。公共基础部分占全卷的10分。 2、公共基础知识考查方式为选择题共10道。 全国计算机等级考试 二级公共基础知识

5 二级公共基础知识学习方法 理解基本概念 多做练习 适当记忆一些名词 与所学程序设计语言结合起来理解 全国计算机等级考试 二级公共基础知识

6 第一章 数据结构和算法

7 本章知识要点 算法的定义 算法的特征 算法 算法的基本要素 算法复杂度 数据结构的定义 逻辑结构 和 物理结构 数据结构
线性结构 和 非线性结构 顺序表、链表、堆栈 队列、循环队列、树 全国计算机等级考试 二级公共基础知识

8 （1）有穷性：算法必须在有限的次数内完成。 （2）确定性：算法的每一步必须是明确的。 （3）可行性：算法的每一步必须是可以实现的。
一、算法 算法是解决方案的准确而完整性描述。 算法不等于程序，也不等于计算方法。 算法的特性： （1）有穷性：算法必须在有限的次数内完成。 （2）确定性：算法的每一步必须是明确的。 （3）可行性：算法的每一步必须是可以实现的。 （4）拥有足够的情报：算法必须有一定的输入和输出。 全国计算机等级考试 二级公共基础知识

9 一、算法 算法的基本要素： （1）对数据对象的运算和操作： A .算术运算 B .逻辑运算 C .关系运算 D .数据传输
（2）算法的控制结构： A .顺序结构 B .选择结构 C .循环结构 全国计算机等级考试 二级公共基础知识

10 A .算法中基本操作重复执行次数和算法执行时间 同步增长，称作算法的时间复杂度。 B .算法中基本操作重复执行次数和问题规模有关，
一、算法 算法的复杂度：衡量算法优劣的量。 （1）时间复杂度：算法的时间耗费。 A .算法中基本操作重复执行次数和算法执行时间 同步增长，称作算法的时间复杂度。 B .算法中基本操作重复执行次数和问题规模有关， 是问题规模的函数。 C .算法的时间复杂度是指执行算法所需要的计算工 作量。 （2）空间复杂度：执行算法所需要的内存空间。 全国计算机等级考试 二级公共基础知识

11 一、算法 例题 1、算法的基本特征是可行性、确定性、 和拥有足够的情报。
1、算法的基本特征是可行性、确定性、 和拥有足够的情报。 2、算法具有4个特性，以下选项中不属于算法特性的是（    ）      A) 有穷性   B) 简洁性   C) 可行性   D) 确定性 3、算法的时间复杂度是指（ ） A) 执行算法程序所需要的时间 B) 算法程序的长度 C) 算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数 4、算法的空间复杂度是指（ ） A) 算法程序的长度 B) 算法程序中的指令条数 C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间 有穷性 B C D 全国计算机等级考试 二级公共基础知识

12 一、算法 5、在计算机中，算法是指（ ） B A) 加工方法 B) 解题方案的准确而完整的描述 C) 排序方法 D) 查询方法
5、在计算机中，算法是指（ ） A) 加工方法 B) 解题方案的准确而完整的描述 C) 排序方法 D) 查询方法 6、下列叙述中正确的是（ ） A) 算法的效率只与问题的规模有关，而与数据的存储结构无关。 B) 算法的时间复杂度是指执行算法所需要的计算工作量。 C) 数据的逻辑结构与存储结构是一一对应的。 D) 算法的时间复杂度与空间复杂度一定相关。 B B 全国计算机等级考试 二级公共基础知识

13 数据 结构 二、数据结构 数据结构主要研究两方面的问题： （1）数据本身。 （2）数据之间的前后件关系。 数据本身 数据之间的 前后件关系
数据 结构 数据本身 数据之间的 前后件关系 数据结构表示为：DS={D，S} 例：D={春，夏，秋，冬} S={(春,夏)，(夏,秋)，(秋,冬)，(冬,春)} 全国计算机等级考试 二级公共基础知识

14 （1）物理结构：数据在计算机存储介质中真正存储的结构， 也被称为“存储结构” （2）逻辑结构：人们所理解的数据之间的结构，可以用图示
二、数据结构 数据的结构分为： （1）物理结构：数据在计算机存储介质中真正存储的结构， 也被称为“存储结构” （2）逻辑结构：人们所理解的数据之间的结构，可以用图示 的方法绘画出来的数据之间的结构。 例：一个班由35名同学，他们的座位牌号就是物理结构， 一次考试的排名是逻辑结构。 注意：逻辑结构和物理结构没有必然的联系，也不一定是 一一对应的。 全国计算机等级考试 二级公共基础知识

15 非空数据结构同时满足以下两个条件就是线性结构： A .有且仅有一个根结点； B .除头结点和尾结点外，任何结点有且仅有一个前件 和一个后件。
二、数据结构 数据的结构分为： （1）线性结构： 非空数据结构同时满足以下两个条件就是线性结构： A .有且仅有一个根结点； B .除头结点和尾结点外，任何结点有且仅有一个前件 和一个后件。 （2）非线性结构：除了线性结构都是非线性结构。 全国计算机等级考试 二级公共基础知识

16 二、数据结构 线性表 堆栈 队列 循环队列 线性链表 树和二叉树 物理结构和逻辑结构相同 线 性 结 构 物理结构和逻辑结构相同
全国计算机等级考试二级公共基础知识要求掌握的数据结构共有以下六种： 线性表 堆栈 队列 循环队列 线性链表 树和二叉树 物理结构和逻辑结构相同 线 性 结 构 物理结构和逻辑结构相同 物理结构和逻辑结构相同 物理结构和逻辑结构相同 物理结构和逻辑结构不相同 非线性结构 物理结构和逻辑结构不相同 全国计算机等级考试 二级公共基础知识

17 （1）有且仅有一个头结点（根节点）和尾结点。 （2）任意其他结点至多有一个前件，一个后件。 （3）头结点没有前件，尾结点没有后件。
三、顺序表：顺序表就是数组 10 20 30 40 50 60 70 80 1、顺序表也叫做线性表，属于线性结构。 线性表的逻辑结构和物理结构相同。 2、特点： （1）有且仅有一个头结点（根节点）和尾结点。 （2）任意其他结点至多有一个前件，一个后件。 （3）头结点没有前件，尾结点没有后件。 全国计算机等级考试 二级公共基础知识

18 四、堆栈 1、定义：只允许在栈顶位置插 入数据和删除数据的线性结 构是堆栈，简称为“栈”。 2、堆栈属于线性结构。
3、堆栈的逻辑结构和物理结构 相同。 4、特点：先进后出，后进先出 所以堆栈也叫做先进后出表 （FILO） 5、堆栈具备存储功能：函数的 递归调用和表达式求解都用 到了堆栈。 栈顶 top 栈底 入栈 / 压入 出栈 / 弹出 全国计算机等级考试 二级公共基础知识

19 四、堆栈 模拟堆栈的数据出入过程： 入栈顺序：a、b、c、d、e、f ………….. c d b b b b a a a a a 栈空 入a
全国计算机等级考试 二级公共基础知识

20 四、堆栈 【典型题型】 假设一个堆栈，入栈顺序为abcde，认为在任何时刻均允许出栈，下列选项中不可能的出栈顺序为（ ）
A）abcde（可能） B）edcba（可能） C）cdeba（可能） D）cdeab（不可能） D 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（ ） A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意顺序 B 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（ ） A) ABCED B) DCBEA C) DBCEA D) CDABE B 全国计算机等级考试 二级公共基础知识

21 五、队列 1、队列属于线性结构。 2、队列的逻辑结构和物理结构相同。 3、定义：入队操作发生在队尾，出队操作发生在队头。
队头front 队尾rear 入队 出队 1、队列属于线性结构。 2、队列的逻辑结构和物理结构相同。 3、定义：入队操作发生在队尾，出队操作发生在队头。 4、特点：先进先出，后进后出，所以队列也叫做先进先 出表（FIFO）。 全国计算机等级考试 二级公共基础知识

22 五、队列 1、栈和队列的共同特点是（ ） C A)都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点
1、栈和队列的共同特点是（ ） A)都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点 2、一些重要的程序语言(如C语言和Pascal语言) 允许过程的递归调用。而 实现递归调用中的存储分配通常用（ ） A) 栈 B) 堆 C) 数组 D) 链表 3、下列关于栈的叙述中正确的是（ ） A)在栈中只能插入数据 B)在栈中只能删除数据 C)栈是先进先出的线性表 D)栈是后进先出的线性表 4、下列关于队列的叙述中正确的是（ ） A)在队列中只能插入数据 B)在队列中只能删除数据 C)队列是先进先出的线性表 D)队列是后进先出的线性表 C A D C 全国计算机等级考试 二级公共基础知识

23 六、循环队列 rear front 全国计算机等级考试 二级公共基础知识

24 六、循环队列 模拟循环队列的数据出入过程： 入队顺序：a、b、c、d、e、f
入队运算是往队列队尾插入一个数据元素；退队运算是从队列的队头删除一个数据元素。 入队顺序：a、b、c、d、e、f b b a a rear rear rear front rear front front front 循环队列空 front=rear 数据a入队 数据b入队 数据a出队 全国计算机等级考试 二级公共基础知识

25 3、绘画一个由5个节点组成的线性链表，数据为1、2、3、4、5。
七、线性链表 1、链表属于线性结构。 2、链表的逻辑结构和物理结构不相同。 3、线性链表由结点组成： 每个结点有两个区域：数据域，指针域。 A .数据域，用来存储数据。 B .指针域，用来指向下一个结点的位置。 3、绘画一个由5个节点组成的线性链表，数据为1、2、3、4、5。 链表的结点 数据域 指针域 1 2 3 4 5 ^ 单链表 全国计算机等级考试 二级公共基础知识

26 链表的种类：单链表、循环链表、双向链表。
七、线性链表 链表的种类：单链表、循环链表、双向链表。 1 1 2 2 3 3 4 4 5 5 循环链表 ^ 1 2 3 4 5 ^ 双向链表 全国计算机等级考试 二级公共基础知识

27 七、线性链表 1、链表不具有的特点是（ ） B A) 不必事先估计存储空间 B) 可随机访问任一元素 C) 插入删除不需要移动元素
1、链表不具有的特点是（ ） A) 不必事先估计存储空间 B) 可随机访问任一元素 C) 插入删除不需要移动元素 D) 所需空间与线性表长度成正比 2、数据结构分为逻辑结构与存储结构，线性链表属于 。 3、数据结构中，与所使用的计算机无关的是数据的（ ） A) 存储结构 B) 物理结构 C) 逻辑结构 D) 物理和存储结构 4、数据的逻辑结构有线性结构和 两大类。 B 存储结构 A 非线性结构 全国计算机等级考试 二级公共基础知识

28 八、树与二叉树 1、树的基本概念 树是一种简单的非线性结构，是n个结点的有限集合。
R K P Q D B E N O T C H X S W Z A Y M F G L 根节点 从逻辑结构看： 1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅有一个前趋； 3）树的结点，可以有零个或多个后继； 4）除根外的其他结点，都存在唯一一条从根到该结点的路径； 5）树是一种分支结构 一般的树 全国计算机等级考试 二级公共基础知识

29 八、树与二叉树 书 第一章 第二章 第三章 第四章 书的层次结构 注意:
1.1节 书的层次结构 注意: (1)树结构具有明显的层次关系，即树是一种层次结构。因此具有层次关系的数据都可以用树这种数据结构来描述。 (2)在树结构中分层的原则是：根节点在第1层，同一层上所有结点的所有子结点都在下一层。 (3)在树中，叶子结点没有子树。 全国计算机等级考试 二级公共基础知识

30 （1）根节点：在数据结构中，没有前件的结点只有一个，称为树的根结点。
八、树与二叉树 2、树的基本术语 （1）根节点：在数据结构中，没有前件的结点只有一个，称为树的根结点。 （2）子节点：在数据结构中，每一个结点可以有多个后件，它们都称为该节点的子节点。没有后件的结点称为叶子结点。 （3）度：在数据结构中，一个结点所拥有的后件的个数称为该结点的度。在树中，所有结点中的最大的度称为该树的度。 （4）树的深度：树的最大层次称为树的深度。 全国计算机等级考试 二级公共基础知识

31 八、树与二叉树 (1)非空二叉树只有一个根结点； 3、二叉树 二叉树也是一种非线性结构，每个结点最多分两叉的有序树。
二叉树具有以下两个特点： (1)非空二叉树只有一个根结点； (2)每一个结点最多有两颗子树，且分别称为该结点的左子树与右子树。 D D D D D D D D D (a)只有根结点的二叉树 (b)深度为4的二叉树 全国计算机等级考试 二级公共基础知识

32 八、树与二叉树 e A B 4、有序树与无序树： 二叉树和度为二的树的区别： A .二叉树是有序树，度为二的树是普通树，属于无序树。
【普通树不允许为空，至少有一个结点】 全国计算机等级考试 二级公共基础知识

33 八、树与二叉树 a b c 5、二叉树的五种基本结构 空二叉树 只有一个结 点的二叉树 有两个结点的二叉树 有三个结点的二叉树
全国计算机等级考试 二级公共基础知识

34 八、树与二叉树 6、二叉树的基本性质 ★性质1 在二叉树的第k层上，最多有 𝟐 𝒌−𝟏 (k≥1) 个结点。
根据二叉树的特点，这个性质是显然的。 ★性质2 深度为 m 的二叉树最多有个 𝟐 𝒎−𝟏 个结点。 根据性质1，只要将第1层到 m 层上的最大树的结点相加就可以得到整个二叉树中结点的最大值，即 𝟐 𝟏−𝟏 + 𝟐 𝟐−𝟏 +…+ 𝟐 𝒎−𝟏 = 𝟐 𝒎−𝟏 ★性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。 𝒏 𝟎 = 𝒏 𝟐 +1 ★性质4 具有n个结点的二叉树，其深度至少为[ 𝐋𝐨𝐠 𝟐 n]+1 ，其中[ 𝐋𝐨𝐠 𝟐 n]表示取 𝐋𝐨𝐠 𝟐 n 的整数部分。 ★性质5 具有n个结点的完全二叉树的深度为[ 𝐋𝐨𝐠 𝟐 n]+1。 全国计算机等级考试 二级公共基础知识

35 八、树与二叉树 x e o q k b g x e o q k b 7、满二叉树和完全二叉树：
(1)满二叉树：二叉树的每一层均具备该层最大结点个数。 （即：不具备度为1的结点） (2)完全二叉树：满二叉树是一个特殊的完全二叉树。将所有结点 自上向下、自左向右编号，结点编号连续而不缺失。 x e o q k b g x e o q k b 1 2 3 4 5 6 满二叉树 完全二叉树 全国计算机等级考试 二级公共基础知识

36 经典例题 填空题： 设一棵完全二叉树共有700个结点，则在该二叉树中有 个叶子结点
设一棵完全二叉树共有700个结点，则在该二叉树中有 个叶子结点 二叉树的结点共有三种：度为0的叶子结点、度为1的结点和度为2的结点。 设度为0的叶子结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，则： n0+n1+n2=700 （1） 根据二叉树性质：叶子结点个数比度为2的结点个数多1，即： n0=n2+1 （2） 将（2）式带入（1）式，所以： n0+n1+n0-1=700 2n0=701-n1 完全二叉树总结点个数为偶数，则度为1的结点个数为1；完全二叉树的总结点个数为奇数，则度为1的结点个数为0。 所以：2n0=701-1，即 n0=350。 全国计算机等级考试 二级公共基础知识

37 B F D G 八、树与二叉树 A C E 6、二叉树的遍历： 二叉树的遍历是指不重复地访问二叉树中的所有结点。
二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树 A F G E D C B 令：L：遍历左子树 D：访问根结点 R：遍历右子树 有六种遍历方法： DLR，LDR，LRD， DRL，RDL，RLD 约定先左后右,有三种遍历方法： DLR，LDR，LRD，分别称为先序遍历（先根遍历）、中序遍历（中根遍历）、后序遍历（后根遍历） 全国计算机等级考试 二级公共基础知识

38 B F D G 八、树与二叉树 (1)先序遍历（ DLR ） 若二叉树非空 ①访问根结点； A ②先序遍历左子树； ③先序遍历右子树； C
若二叉树非空 ①访问根结点； ②先序遍历左子树； ③先序遍历右子树； A F G E D C B 先序遍历序列结果：A,B,D,E,G,C,F 全国计算机等级考试 二级公共基础知识

39 B F D G 八、树与二叉树 (2)中序遍历（LDR ） A 若二叉树非空 ①中序遍历左子树; ②访问根结点; C ③中序遍历右子树; E
中序遍历序列： D,B,G,E,A,C,F 全国计算机等级考试 二级公共基础知识

40 B F D G 八、树与二叉树 (3)后序遍历（ LRD ） A 若二叉树非空 ①后序遍历左子树 ②后序遍历右子树 C ③访问根结点 E
后序遍历序列： D,G,E,B,F,C,A 全国计算机等级考试 二级公共基础知识

41 经典例题讲解 1、下列二叉树进行前序遍历的结果为（ ） C A）DYBEAFCZX B）YDEBFZXCA
1、下列二叉树进行前序遍历的结果为（ ） A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ 2、某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（ ） A）n B）n C）2n D）n/2 3、一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（ ） A） B） C）229 D）231 C A B C Z D E X Y F A A 全国计算机等级考试 二级公共基础知识

42 ABDEGCFH DBGEACHF BDEG DBGE EG GE CFH CHF FH HF 经典例题讲解 左子树： 右子树： A B D
DGEBHFCA ABCDEFGH ABDEGCFH DBGEACHF BDEG DBGE EG GE CFH CHF FH HF 左子树： 右子树： A B D E F C G H 全国计算机等级考试 二级公共基础知识

43 经典例题讲解 解答：若二叉树的任意两个节点的值都不相同，则二叉树的前序序列和中序序列可唯一确定一棵二叉树，确定方法如下：
（1）根据前序遍历的定义：前序序列的第一个元素必为二叉树的根节点； 根据中序遍历的定义：中序序列的根节点恰为左右子树的中序序列的分界点；根节点前的子序列为左子树的中序序列；根节点后的子序列为右子树的中序序列； （2）根据左子树的中序序列的节点个数，在前序序列中找出左子树的前序序列，剩下的即为右子树的前序序列； （3）然后用相同的办法分别找出左、右子树的根及其左右子树的前序序列和中序序列； （4）依此类推，直至待构造的二叉树的前序序列仅剩一个字母为止。 全国计算机等级考试 二级公共基础知识

44 第二章 程序设计基础

45 本章知识要点 面向过程的程序设计 结构化程序设计 模块化程序设计 面向对象的程序设计 对象的定义 对象的属性和方法 类和实例的派生与继承
消息与多态性 全国计算机等级考试 二级公共基础知识

46 1、面向过程的程序设计：C语言、BASIC语言等。 （1）结构化程序设计：顺序、选择、循环。
一、程序设计方法 1、面向过程的程序设计：C语言、BASIC语言等。 （1）结构化程序设计：顺序、选择、循环。 三大结构（顺序、选择、循环）可以解决所有的问题，和 问题的规模没有关系。 （2）模块化程序设计：利用将程序分解的方法，将复杂的问题 简单化，将单一的问题分成多个模块独立解决。 C语言：模块就是函数。 VB语言：模块就是模块、子例程、子程序。 VFP数据库：模块就是子程序。 Access数据库：模块就是宏、事件代码。 2、面向对象的程序设计：VB、VFP、Java、Delphi等。 全国计算机等级考试 二级公共基础知识

47 二、程序设计风格 1.源程序文档化 选择标示符的名字 注释（序言性和功能性注释） 程序的视觉组织 2.数据说明的方法 显示地说明一切变量
数据说明的次序应该规范化 说明语句中变量安排有序化 对复杂数据结构应注释说明 3.语句的结构 每条语句简单明了 尽量不用或少用GOTO语句 尽量只采用3种基本控制结构编程 4.输入和输出 对输入数据进行校验和合理性检查 输入输出格式保持一致 设计良好的输出报表 全国计算机等级考试 二级公共基础知识

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

49 利用图示表示顺序结构 A B A B 程序流程图 N-S图 全国计算机等级考试 二级公共基础知识

50 利用图示表示选择结构 A B 条件 满足 不满足 条件 满足 不满足 A B 程序流程图 N-S图 全国计算机等级考试 二级公共基础知识

51 利用图示表示重复结构(1) 程序流程图直到型循环 程序流程图当型循环 S S 不满足 条件 满足 不满足 条件 满足 全国计算机等级考试
二级公共基础知识

52 S S WHILE 条件 UNTIL 条件 利用图示表示重复结构(2) N-S图直到型循环 N-S图当型循环 全国计算机等级考试
二级公共基础知识

53 三、面向对象的程序设计 面向对象(Object Oriented)的程序设计方法已经发展成为主流的软件开发方法，起源于对面向对象语言的研究。20世纪60年代后期首次被提出，80年代开始走向实用。 面向对象的程序设计的术语： 对象、属性、方法、封装性、事件、类、父类、子类、实例、派生、继承、消息、多态性。 全国计算机等级考试 二级公共基础知识

54 面向对象方法的主要优点： （1）与人类习惯的思维方法一致。 （2）稳定性好。 （3）可重用性好。 （4）易于开发大型软件产品。
三、面向对象的程序设计 面向对象方法的主要优点： （1）与人类习惯的思维方法一致。 （2）稳定性好。 （3）可重用性好。 （4）易于开发大型软件产品。 （5）可维护性好。 全国计算机等级考试 二级公共基础知识

55 对象：现实生活中存在的可以相互区分的物体。 是属性和方法的封装。
1、对象的定义 对象：现实生活中存在的可以相互区分的物体。 是属性和方法的封装。 对象的基本特点： （1）标识唯一性。 （2）分类型。 （3）多态性。 （4）封装性。 （5）模块独立型好。 全国计算机等级考试 二级公共基础知识

56 2、对象的属性和方法 属性（Property）：用来描述对象的状态，是对象的静态特性。 包括属性名和属性值两方面。
例如：“显示器”作为对象，具备“颜色”属性，取值为“银白色”。 方法（Method）：用来描述对象的行为，是对象的动态特性。 方法具备方法名。 方法必须利用事件来激活。 例如:“显示器”作为对象，具备“关闭”的方法，必须用“断电”事件来激活。 属性名 属性值 方法名 事件 封装性：(Encapsulation) 对象依靠对象名将自身的属性和方法封装。 全国计算机等级考试 二级公共基础知识

57 3、类和实例的派生与继承 （1）类（Class）：具有相同属性和方法的 对象的集合，是对对象属性和方法的抽 象。
（2）实例（Instances）：类的子类派生出 的对象就是该类的一个实例。 类展现对象的共性；实例展现对象的个性。 （3）派生过程中将发生属性和方法的继承 （Inheritance） 父类将自身的所有属性和方法传递 给子类，子类继承父类传递的所有属性 和方法，并产生自身特有的属性和方 法，再将这些属性和方法的总和传递给 下一级子类。 人 好人 坏人 中国人 外国人 张三 全国计算机等级考试 二级公共基础知识

58 4、消息与多态性 （1）消息（Message）：进行对象之间的信息传递。 消息的组成： A .接收消息的对象名称。
（2）多态性（Polymorphism）：同样的消息传递给不同的对象，导致 完全不同的行动。 消息的组成： A .接收消息的对象名称。 B .消息标识符，也叫做“消息名”。 C .零个或多个参数。 全国计算机等级考试 二级公共基础知识

59 练习题 1、结构化程序设计的三种结构是（ ） D A) 顺序结构、选择结构、转移结构 B) 分支结构、等价结构、循环结构
1、结构化程序设计的三种结构是（ ） A) 顺序结构、选择结构、转移结构 B) 分支结构、等价结构、循环结构 C) 多分支结构、赋值结构、等价结构 D) 顺序结构、选择结构、循环结构 2、在设计程序时，应采纳的原则之一是（ ） A) 不限制goto语句的使用 B) 减少或取消注解行 C) 程序越短越好 D) 程序结构应有助于读者理解 3、程序设计语言的基本成分是数据成分、运算成分、控制成分和（ ） A) 对象成分 B) 变量成分 C) 语句成分 D) 传输成分 4、结构化程序设计主要强调的是（ ） A) 程序的规模 B) 程序的效率 C) 程序设计语言的先进性 D) 程序易读性 D D D D 全国计算机等级考试 二级公共基础知识

60 练习题 5、以下不属于对象的基本特点的是（ ） A A) 分类性 B) 多态性 C) 继承性 D) 封装性
5、以下不属于对象的基本特点的是（ ） A) 分类性 B) 多态性 C) 继承性 D) 封装性 6、对建立良好的程序设计风格，下面描述正确的是（ ） A) 程序应简单、清晰、可读性好 B) 符号名的命名只要符合语法 C) 充分考虑程序的执行效率 D) 程序的注释可有可无 7、在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（ ） A) 安全性 B) 一致性 C) 可理解性 D) 合理性 8、程序的3种基本控制结构是（ ） A) 过程、子过程和分程序 B) 顺序、选择和重复 C) 递归、堆栈和队列 D) 调用、返回和转移 9、下列叙述中，不属于结构化程序设计方法的主要原则的是（ ） A) 自顶向下 B) 由底向上 C) 模块化 D) 限制使用goto语句 A A C B B 全国计算机等级考试 二级公共基础知识

61 练习题 10、对象实现了数据和操作的结合，是指对数据和数据的操作进行（ ） C A) 结合 B) 隐藏 C) 封装 D) 抽象
10、对象实现了数据和操作的结合，是指对数据和数据的操作进行（ ） A) 结合 B) 隐藏 C) 封装 D) 抽象 11、在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发 送（ ） A）调用语句 B）命令 C）口令 D）消息 12、下列对象概念描述错误的是（ ） A）任何对象都必须有继承性 B）对象是属性和方法的封装体 C）对象间的通讯靠消息传递 D）操作是对象的动态属性 C D A 全国计算机等级考试 二级公共基础知识

62 第三章 软件工程基础 软件（Software）= 程序 + 文档

63 本章知识要点 软件危机 软件工程 软件生命周期 需求分析 概要设计 详细设计 测试 调试 全国计算机等级考试 二级公共基础知识

64 一、软件危机 软件危机主要表现在： （1）软件需求的增长得不到满足。 （2）软件开发成本和进度无法控制。 （3）软件质量难以保证。
（4）软件不可维护或可维护度非常低。 （5）软件的成本不断提高。 （6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。 总之，可以将软件危机归结为成本、质量、生产率问题 全国计算机等级考试 二级公共基础知识

65 二、软件工程 软件工程是为了摆脱软件危机而诞生的，主要思想是在软件开发过程中应用工程化原则。 软件工程的三要素：方法、工具、工程。
软件工程的主要内容：软件开发技术、软件工程管理。 软件工程的原则： （1）抽象。 （2）信息隐蔽。 （3）模块化。 （4）局部化。 （5）确定性。 （6）一致性。 （7）完备性。 （8）可验证性。 全国计算机等级考试 二级公共基础知识

66 二、软件生命周期 软件生命周期（Software Life Cycle，SLC）：将软件产品从提出、实现、使用维护到停止使用退役的过程称为“软件生命周期”。 可行性研究 需求分析 概要设计 详细设计 实现 测试 使用 退役 维护 定义阶段 开发阶段 维护阶段 全国计算机等级考试 二级公共基础知识

67 二、软件生命周期 软件工程步骤 用到的方法 用到的工具 生成的文档 需求分析 结构化分析SA 数据流图DFD 数据字典DD 判定表 判定树
《软件需求规格说明书》 SRS 概要设计 结构化设计SD 软件结构图SC 《概要设计说明书》 《数据库设计说明书》 《集成测试计划》 详细设计 结构化编程SP 程序流程图 N-S图 问题分析图PAD 伪码PDL - 全国计算机等级考试 二级公共基础知识

68 三、需求分析 需求与需求分析 需求分析的方法 结构化分析方法 数据流图与数据字典 判定树与判定表 软件需求规格说明书 全国计算机等级考试
二级公共基础知识

69 需求：用户对目标软件系统在功能、行为、性能、设计 约束等方面的期望。
1、需求与需求分析 需求：用户对目标软件系统在功能、行为、性能、设计 约束等方面的期望。 需求分析：发现用户需求的过程 需求分析阶段的工作： （1）需求获取 （2）需求分析 （3）编写需求规格说明书 （4）需求评审 全国计算机等级考试 二级公共基础知识

70 B .面向数据结构的Jackson方法 JSD。 C .面向数据结构的结构化数据系统开发方法 DSSD。 D .面向对象的分析方法 OOA。
2、需求分析的方法 A .面向数据流的结构化分析方法 SA。 B .面向数据结构的Jackson方法 JSD。 C .面向数据结构的结构化数据系统开发方法 DSSD。 D .面向对象的分析方法 OOA。 全国计算机等级考试 二级公共基础知识

71 3、结构化分析方法：数据流图DFD 数据流图DFD中的主要图形元素： 加工/转换 数据流 存储文件/数据源 源 全国计算机等级考试
二级公共基础知识

72 数据字典的作用：对数据流图DFD中出现的被命名图形元素进 行确切的解释。
结构化分析方法：数据字典DD 数据字典DD是结构化分析方法的核心。 数据字典的作用：对数据流图DFD中出现的被命名图形元素进 行确切的解释。 全国计算机等级考试 二级公共基础知识

73 判定树 条件1 条件2 结果 计 7月－9月 订票量>20: 15% 算 12月 订票量<=20: 5% 折
结构化分析方法：判定树与判定表 判定树 条件 条件 结果 计 7月－9月 订票量>20: 15% 算 12月 订票量<=20: 5% 折 扣 1月－6月 订票量>20: 30% 量 10月 11月 订票量<=20: 5% 全国计算机等级考试 二级公共基础知识

74 判定表 结构化分析方法：判定树与判定表 旅游时间 7月—9月，12月 1月—6月，10月，11月 订票量 >20% <=20%
折扣率 15% 5% 30% 20% 全国计算机等级考试 二级公共基础知识

75 软件需求规格说明书（SRS）是需求分析阶段的最后成果，将 在软件工程的最后转换为用户手册。
结构化分析方法：需求规格说明书 软件需求规格说明书（SRS）是需求分析阶段的最后成果，将 在软件工程的最后转换为用户手册。 软件需求规格说明书的作用： （1）便于用户、开发人员进行理解和交流。 （2）反映出用户问题的结构，可作为软件开发工作的基础和 依据。 （3）作为确认测试和验收的依据。 全国计算机等级考试 二级公共基础知识

76 （1）抽象：把事物本质的共同特性提取出来而不考虑细节。 （2）模块化：把待开发软件分解成若干个小的简单部分。
四、概要设计 软件设计的基本原理： （1）抽象：把事物本质的共同特性提取出来而不考虑细节。 （2）模块化：把待开发软件分解成若干个小的简单部分。 （3）信息隐蔽：在一个模块内包含的信息，对于不需要这些 信息的其他模块来说是不能访问的。 （4）模块独立性：评价设计好坏的重要度量指标。 内聚性和耦合性是模块独立性的两个定性标准： A .内聚性：一个模块内部各个元素间彼此结合的紧密程度。 B .耦合性：模块间互相连接的紧密程度。 一款优秀的软件设计，应做到高内聚，低耦合。 全国计算机等级考试 二级公共基础知识

77 四、概要设计 概要设计的任务： （1）设计软件系统结构。 （2）确定软件的每一个模块 （3）确定模块之间的调用关系 （4）评价模块结构质量。
软件结构图SC中 的主要图形元素 模块 模块间的调用关系 采用的方法：结构化设计方法【SD】 使用的工具：软件结构图SC。 全国计算机等级考试 二级公共基础知识

78 详细设计的任务：为软件结构图中每一个模块确定实现的算法 和数据结构。表示算法和数据结构的细节。
五、详细设计 详细设计的任务：为软件结构图中每一个模块确定实现的算法 和数据结构。表示算法和数据结构的细节。 采用的方法：结构化编程方法【SP】 使用的工具：程序流程图、N-S图、问题分析图PAD 判定表 过程设计语言/伪码PDL 全国计算机等级考试 二级公共基础知识

79 五、详细设计 程序流程图中的主要图形元素： 加工步骤 控制流 逻辑条件 全国计算机等级考试 二级公共基础知识

80 （1）×错误理解：软件测试为了发现错误并改正。 （2）×错误理解：软件测试为了证明软件正确性。
六、软件测试 软件测试的目的：尽可能多的发现错误。 （1）×错误理解：软件测试为了发现错误并改正。 （2）×错误理解：软件测试为了证明软件正确性。 软件测试的准则： （1）所有测试追溯到需求。 （2）严格执行测试计划，排除测试随意性。 （3）充分注意测试中的群集现象：程序中存在错误的概率与该程 序中已发现的错误数量成正比。 （4）程序员避免检测自己的程序。 （5）穷举测试不可能。 （6）妥善保存测试文档，为维护提供方便。 全国计算机等级考试 二级公共基础知识

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

82 七、软件调试（Debug） 软件调试的目的：诊断和改正程序中的错误。 软件调试的基本步骤： 第1步：错误定位。【占据了调试的绝大多数工作量】
第2步：修改设计和代码，以排除错误。 第3步：进行回归测试，防止引进新的错误。 全国计算机等级考试 二级公共基础知识

83 练习题 1、为了提高测试的效率，应该（ ） D A) 随机选取测试数据 B) 取一切可能的输入数据作为测试数据
1、为了提高测试的效率，应该（ ） A) 随机选取测试数据 B) 取一切可能的输入数据作为测试数据 C) 在完成编码以后制定软件的测试计划 D) 集中对付那些错误群集的程序 2、软件生命周期中所花费用最多的阶段是（ ） A) 详细设计 B) 软件编码 C) 软件测试 D) 软件维护 3、下列叙述中，不属于软件需求规格说明书的作用的是（ ） A) 便于用户、开发人员进行理解和交流 B) 反映出用户问题的结构，可以作为软件开发工作的基础和依据 C) 作为确认测试和验收的依据 D) 便于开发人员进行需求分析 4、下列不属于软件工程的3个要素的是（ ） Ａ) 工具 Ｂ) 过程 Ｃ) 方法 Ｄ) 环境 D D D D 全国计算机等级考试 二级公共基础知识

84 练习题 5、软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计 是指（ ）
是指（ ） A) 模块间的关系 B) 系统结构部件转换成软件的过程描述 C) 软件层次结构 D) 软件开发过程 6、检查软件产品是否符合需求定义的过程称为（ ） Ａ) 确认测试 Ｂ) 集成测试 Ｃ) 验证测试 Ｄ) 验收测试 7、数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图 符构成。下列图符名标识的图符不属于数据流图合法图符的是（ ） Ａ) 控制流 Ｂ) 加工 Ｃ) 数据存储 Ｄ) 源和流 8、开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现象称 作（ ） A) 软件投机 B) 软件危机 C) 软件工程 D) 软件产生 9、下面不属于软件设计原则的是（ ） Ａ) 抽象 B) 模块化 Ｃ) 自底向上 Ｄ) 信息隐蔽 B B B B B 全国计算机等级考试 二级公共基础知识

85 练习题 10、开发大型软件时，产生困难的根本原因是（ ） A A) 大系统的复杂性 B 人员知识不足
10、开发大型软件时，产生困难的根本原因是（ ） A) 大系统的复杂性 B 人员知识不足 C) 客观世界千变万化 D) 时间紧、任务重 11、软件工程的出现是由于（ ） A) 程序设计方法学的影响 B) 软件产业化的需要 C) 软件危机的出现 D) 计算机的发展 12、在数据流图(DFD) 中，带有名字的箭头表示（ ） A) 模块之间的调用关系 B) 程序的组成成分 C) 控制程序的执行顺序 D) 数据的流向 13、下列不属于结构化分析的常用工具的是（ ） A) 数据流图 B) 数据字典 C) 判定树 D) PAD图 14、在软件生产过程中，需求信息的给出是（ ） A) 程序员 B) 项目管理者 C) 软件分析设计人员 D) 软件用户 A C D D D 全国计算机等级考试 二级公共基础知识

86 第四章 数据库设计基础

87 1、数据（Data）是描述事物的符号记录。 2、为什么引入数据库： （1）数据量大，数据多。 （2）方便查找。
一、理解数据库： 1、数据（Data）是描述事物的符号记录。 2、为什么引入数据库： （1）数据量大，数据多。 （2）方便查找。 全国计算机等级考试 二级公共基础知识

88 1、数据（Data）是描述事物的符号记录。 2、数据库（DataBase，DB）数据的集合，是存放数据的仓库。
二、数据库原理术语： 1、数据（Data）是描述事物的符号记录。 2、数据库（DataBase，DB）数据的集合，是存放数据的仓库。 3、数据库管理系统（DBMS）负责数据的管理。 （1）DBMS属于系统软件。 （2）DBMS是数据库系统的核心。 4、数据库应用系统（DBAS）利用DBMS开发的应用软件。 5、数据库系统（DBS）使用了数据库技术的计算机，属于硬件系统。 6、数据库管理员（DBA）是数据库系统的人的因素。负责管理、维 护、设计、监视数据库系统的运行。 全国计算机等级考试 二级公共基础知识

89 二、数据库原理术语： 用户 数据库应用系统 数据库管理系统 Access / Visual FoxPro / SQL Server等。
操作系统 Windows XP / Vista / 7 / 2003等。 计算机硬件 全国计算机等级考试 二级公共基础知识

90 三、数据库系统的三级模式和两级映射： 应用 应用 应用 外模式 外模式/子模式 用户模式 外模式 - 概念模式映射 概念模式
局部数据逻辑结构的描述 外模式 外模式/子模式 用户模式 外模式 - 概念模式映射 概念模式 全局数据逻辑结构的描述 概念模式 – 内模式映射 内模式 （物理模式） 数据库（DB） 全国计算机等级考试 二级公共基础知识

91 2、典型的概念数据模型：E – R模型（实体 - 联系模型） （1）实体：现实生活中的事物。 （2）属性：表示实体的一些特征。
四、数据模型： 1、数据模型的三层分类： （1）概念数据模型/概念模型 （2）逻辑数据模型/数据模型 （3）物理数据模型/物理模型 2、典型的概念数据模型：E – R模型（实体 - 联系模型） （1）实体：现实生活中的事物。 （2）属性：表示实体的一些特征。 （3）联系：实体之间的关联。 全国计算机等级考试 二级公共基础知识

92 历史上出现过的数据模型：网状模型、层次模型、关系模型
四、数据模型： 3、实体间联系： （1）一对一（1:1） 学校 -- 校长 【计算机不予处理】 （2）一对多（1:m） 学生 – 班级 【计算机可以直接处理】 （3）多对多（m:n） 学生 – 课程 【转换为两个一对多联系再处理】 历史上出现过的数据模型：网状模型、层次模型、关系模型 全国计算机等级考试 二级公共基础知识

93 四、数据模型： 4、E-R模型的图示表示法： 实体 实体的属性 联系 全国计算机等级考试 二级公共基础知识

94 关系的数据结构 五、关系模型： 关系就是二维表。 1、元组是有限的。 2、元组不能重复。 3、属性不能重复。 4、元素的顺序是无关的。
5、属性的顺序是无关的。 例：学生关系 主键 属性 学号 姓名 性别 年龄 籍贯 01 张三 男 21 河北 02 李四 女 24 山东 03 王武 28 陕西 元组/记录 全国计算机等级考试 二级公共基础知识

95 关系的数据约束 A .实体完整性约束 主键取值不能为空，不能取重复值。 主键取值不同，就是两个不同的元组。 B .参照完整性约束
不允许引用不存在的元组。 约束了关系之间相关联的情况。 C .用户自定义完整性约束 全国计算机等级考试 二级公共基础知识

96 （1）交：R∩S=｛t|t∈R且t∈S｝ （2）并：R∪S=｛t|t∈R或t∈S｝ （3）差：R-S=｛t|t∈R且t∈S｝ 六、关系代数：
参与运算的数据都是关系（二维表）。 1、基本关系代数 （1）交：R∩S=｛t|t∈R且t∈S｝ （2）并：R∪S=｛t|t∈R或t∈S｝ （3）差：R-S=｛t|t∈R且t∈S｝ 全国计算机等级考试 二级公共基础知识

97 结论：并交差三个操作都不能更改关系的属性个数。
六、关系代数： R A B C S A B C R∩S A B C 结论：并交差三个操作都不能更改关系的属性个数。 全国计算机等级考试 二级公共基础知识

98 2、关系积（笛卡尔积） R S A B C A B C 1 2 5 1 2 5 1 4 9 3 4 9 5 6 0 R×S
R×S R.A R.B R.C S.A S.B S.C 全国计算机等级考试 二级公共基础知识

99 （1）选择：σA>C(R) 【对关系的横向分解】 （2）投影：πA,C(R) 【对关系的纵向分解】
3、扩展关系代数： （1）选择：σA>C(R) 【对关系的横向分解】 （2）投影：πA,C(R) 【对关系的纵向分解】 R σA>C(R) A B C A B C πA,C(R) A C 全国计算机等级考试 二级公共基础知识

100 七、数据库设计与管理： 1、数据库设计的四个阶段： 需求分析 概念设计 建立概念数据模型：E-R模型 逻辑设计
运行与维护 概念设计 逻辑设计 物理设计 编码 测试 建立概念数据模型：E-R模型 将E-R图转换为关系模式：实体和联系均转换为关系。 对数据库内部物理结构作出调整并选择合理的存储路径 全国计算机等级考试 二级公共基础知识

101 七、数据库设计与管理： 2、数据库管理： 实施人：数据库管理员（DBA） 数据库管理的特点：实现数据共享 管理内容：（1）数据库的建立
（2）数据库的调整 （3）数据库的重组 （4）数据安全控制与完整性控制 （5）数据库的故障校复 （6）数据库监控 全国计算机等级考试 二级公共基础知识

102 练习题 1、在数据库管理技术发展的过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是（ ）
1、在数据库管理技术发展的过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是（ ） A）数据库系统 B）文件系统 C）人工管理 D）数据项管理 2、下述关于数据库系统的叙述中正确的是（ ） A）数据库系统减少了数据冗余 B）数据库系统避免了一切冗余 C）数据库系统中数据的一致性是指数据类型一致 D）数据库系统比文件系统能管理更多的数据 3、数据库系统的核心是（ ） A）数据库 B）数据库管理系统 C）数据模型 D）软件工具 4、用树形结构来表示实体之间练习的模型称为（ ） A）关系模型 B）层次模型 C）网状模型 D）数据模型 A A B B 全国计算机等级考试 二级公共基础知识

103 练习题 5、关系表中的每一横行称为一个（ ） A A）元组 B）字段 C）属性 D）码
5、关系表中的每一横行称为一个（ ） A）元组 B）字段 C）属性 D）码 6、按条件f对关系R进行选择，其关系代数表达式是（ ） R |x| R B) R |x| R C) 𝝈 𝒇 (R) D) 𝝅 𝒇 (R) 7、关系数据库管理系统能实现的专门关系运算包括（ ） A）排序、索引、统计 B）选择、投影、连接 C）关联、更新、排序 D）显示、打印、制表 8、在关系数据库中，用来表示实体之间联系的是（ ） A）树结构 B）网结构 C）线性表 D）二维表 9、数据库设计包括两个方面的设计内容，它们是（ ） A）概念设计和逻辑设计 B）模式设计和内模式设计 C）内模式设计和物理设计 D）结构特性设计和行为特性设计 A C f B D A 全国计算机等级考试 二级公共基础知识

104 练习题 10、将E—R图转换到关系模式时，实体与联系都可以表示成（ ） A）属性 B）关系 C）键 D）域 11、设有如下关系表：
R S T 则下列操作中正确的是（ ） A）T=R∩S B）T=R∪S C）T=R×S D）T=R/S A A B C 1 2 3 A B C 3 1 A B C 1 2 3 B 全国计算机等级考试 二级公共基础知识

105 练习题 12、有三个关系R、S和T如下： R S T 由关系R和S通过运算得到关系T，则所使用的运算为（ ）
A）笛卡尔积 B）交 C）并 D）自然连接 A B m 1 n 2 A B 1 3 5 A B C m 1 3 D 全国计算机等级考试 二级公共基础知识

106 National Computer Rank Examination
全国计算机等级考试 National Computer Rank Examination 第二部分 MSOffice高级应用

107 MS Office套装系列应用软件的运行平台是 Windows。
课程简介 MS Office，是Microsoft公司推出的办公套装软件，主要版本有MS Office 97/ 2000/ 2003/ XP/ 2007/ 2010等，它包括Word、Excel、Access、PowerPoint等应用软件。 MS Office套装系列应用软件的运行平台是 Windows。 全国计算机等级考试 二级公共基础知识

108 计算机软、硬件系统的组成及性能和主要技术指标 多媒体技术、网络的的基本知识 计算机病毒的概念和防治
第一章学习内容 计算机发展简史、特点、分类及其应用 计算机中数据、字符和汉字的编码 计算机软、硬件系统的组成及性能和主要技术指标 多媒体技术、网络的的基本知识 计算机病毒的概念和防治 全国计算机等级考试 二级公共基础知识

109 第1章 计算机基础知识 计算机的发展 世界上第一台计算机问世：电子数字积分计算机（Electronic Numerical Integrator And Calculator） 于1946年，在美国宾夕法尼亚大学研制成功。 使科学家从奴隶般的计算中解放出来。 ENIAC的问世标志着计算机时代的到来。 全国计算机等级考试 二级公共基础知识