计算机二级考试公共基础知识

本文由hbxshero贡献

ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。

计算机等级考试 公共基础知识 数计学院 卫春芳

计算机二级考试公共基础知识大纲 数据结构与算法

程序设计基础 软件工程基础 数据库设计基础

这四个方面在试卷中出现的情况是：选择题10个 （20分），填空题5个（10分），总分值占到了试 卷卷面分的30％，是一个不小的比例。 第2页

计算机二级考试公共基础知识试卷分析 章节 考试时间

数据结构 程序设 软件工 数据库设 计基础 程基础 计基础 与算法

2007年4月 2007年9月 2008年4月 2008年9月 2009年3月 2009年9月 2010年3月

10分 12分 10分 10分 10分 10分 10分 2分 4分 2分 2分 2分 2分 0分 10分 8分 8分 8分 8分 8分 10分 8分 6分 10分 10分 10分 10分 10分 第3页

一、基本数据结构与算法 算法

⒈ 算法的基 本概念 2.算法复杂 2.算法复杂 度的概念和 意义 数据结构

⒈ 数据结构的概念 ⒉ 线性表 ⒊ 栈和队列 ⒋ 树与二叉树 ⒌ 查找技术 ⒍ 排序技术 对于等级考试，这个部分的考核重点主要在 对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概 重点主要 遍历、 ），还有排序和查找考试中也经常会涉及到 二叉树 遍历 结点），还有排序和查找考试中也经常会涉及到。 念、二叉树(遍历、结点），还

1

有排序和查找考试中也经常会涉及到。 第4页

⒈ 算法的基本概念 算法的定义

算法是程序设计的核心

对解题方案准确而完整的描述称为算法。 对解题方案准确而完整的描述称为算法。 算法是在有限步骤内求解某一问题所使用的一组 定义明确的规则。通俗点说， 定义明确的规则。通俗点说，就是计算机解题的过 计算的方法) 在这个过程中， 程(计算的方法)。在这个过程中，无论是形成解题 思路(推理实现的算法)还是编写程序( 思路(推理实现的算法)还是编写程序(操作实现的算 都是在实施某种算法。 法)，都是在实施某种算法。 个数从大到小进行排序。 例： n个数从大到小进行排序。 个数从大到小进行排序

常用的有冒泡排序、选择排序等。 有多种排序方法 ，常用的有冒泡排序、选择排序等。 第5页

2 . 算法的基本特征

一个算法应该具有以下五个重要的特征： 一个算法应该具有以下五个重要的特征： 有穷性 确定性 输入 输出 可行性

一个算法必须保证执行有限步之后结束； 算法的每一步骤必须有确切的定义； 一个算法有0个或多个输入，以刻画运算对象的初始 情况，所谓0个输入是指算法本身定除了初始条件； 一个算法有一个或多个输出，以反映对输入数据加 工后的结果。没有输出的算法是毫无意义的；

算法原则上能够精确地运行，而且人们用笔和 纸做有限次运算后即可完成 第6页 3. 算法的表示

一个算法的表示需要使用一些语言形式。 一个算法的表示需要使用一些语言形式。 传统的算法图形法，如“流程图”和N-S图 图形法， 传统的算法 图形法 流程图” 图 目前常用的方法使用伪码描述算法。 使用伪码描述算法。 目前常用的方法 使用伪码描述算法 算法与计算机程序 算法是一组逻辑步骤 算法 是一组逻辑步骤 程序——用计算机语言描述的算法 程序 用计算机语言描述的算法

问题： 输入园的半径， 计算园的面积 INPUT r S=3.14 * r*r PTINT S 开始 输入R 输入R S=3.14 * R*R

2

输出S 输出S 结束 第7页

算法举例： 个数排序 算法举例：n个数排序 冒泡排序的方法： 冒泡排序的方法：

1.扫描整个线性表，逐次对 扫描整个线性表， 扫描整个线性表 相邻的两个元素进行比较， 相邻的两个元素进行比较， 若为逆序，则交换； 若为逆序，则交换；第一趟 扫描的结果使最大的元素排 到表的最后 ； 2.除最后一个元素，对剩余 除最后一个元素， 除最后一个元素 的元素重复上述过程， 的元素重复上述过程，将次 大的数排到表的倒数第二个 位置； 位置； 3.重复上述过程； 重复上述过程； 重复上述过程 对于长度为n的线性表， 对于长度为 的线性表，冒泡 的线性表 排序需要对表扫描n-1遍。 排序需要对表扫描 遍 第8页

4. 算法的两个基本要素： 算法的两个基本要素： 一是对数据对象的运算和操作； 二是算法的控制结构。 基本运算和操作

算术运算 关系运算 逻辑运算 数据传输 控制结构 顺序 选择 循环

算法基本设计方法：列举法、归纳法、递推、递归、 减斗递推技术、回溯法 第9页 5. 算法评价

评价一个算法优劣的主要标准是算法的执行效率和存储需求： 评价一个算法优劣的主要标准是算法的执行效率和存储需求： 时间复杂度：执行这个算法所需要的计算工作量 时间复杂度：执行这个算法所需要的计算工作量

一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量

空间复杂度：执行这个算法所需要的内存空间 空间复杂度：执行这个算法所需要的内存空间

算法在执行过程中临时占用的存储空间 时间复杂度它大致等于计算机执行一种简单操作所需的平均时间 时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法 它大致等于计算机执行一种简单操作所需的平均时间与算法 中进行简单操作的次数的乘积 简单操作的次数的乘积。 中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占

3

用的存储空间，包括存储算法本身所占用 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用 的存储空间、算法中的输入输出数据所占用的存储空间和 的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中 临时占用的存储空间这三个部分 临时占用的存储空间这三个部分 第10页 一、算法

对解题方案准确而完整的描述称为算法。 对解题方案准确而完整的描述称为算法。 算法不等于程序，也不等计算机方法，程序的编制不 算法不等于程序，也不等计算机方法， 可能优于算法的设计。 可能优于算法的设计。 算法评价：

时间复杂度： 时间复杂度：执行这个算法所需要的计算工作量 空间复杂度： 空间复杂度：执行这个算法所需要的内存空间 第11页 算法习题:

(1) 在计算机中，算法是指 在计算机中，算法是指。 。 A. 查询方法 B. 加工方法 (c) C. 解题方案的准确而完整的描述 D. 排序方法 (2)下列叙述中正确的是 （07年4月） 下列叙述中正确的是 年 月 A)算法的效率只与问题的规模有关，而与数据的存储结构无关 算法的效率只与问题的规模有关， 算法的效率只与问题的规模有关 B)算法的时间复杂度是指执行算法所需要的计算工作量 算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 数据的逻辑结构与存储结构是一一对应的 (B) D)算法的时间复杂度与空间复杂度一定相关 算法的时间复杂度与空间复杂度一定相关 (3)算法的有穷性是指 (08年4月) 算法的有穷性是指 年 月 A）算法程序的运行时间是有限的 ） (A) B）算法程序所处理的数据量是有限的 ） C）算法程序的长度是有限的 ） D）算法只能被有限的用户使用 ） 第12页

(4) 算法的时问复杂度是指 (2010年3月) 年 月 A)算法的执行时间 算法的执行时间 B)算法所处理的数据量 算法所处理的数据量 C)算法程序中的语句或指令条数 算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数 算法在执行过程中所需要的基本运算次数 (5) 算法的空间复杂度是指 (09年9月) 年 月 A）算法在执行过程中所需要的计算机存储空间 ） B）算法所处理的数据量 ） C）算法程序中的语句或指令条数 ）

4

D）算法在执行过程中所需要的临时工作单元数 ） (6) 下列叙述中正确的是 (06年9月) 年 月 (D) 计算工作量 (A) (D)

A）一个算法的空间复杂度大，则其时间复杂度也必定大 ）一个算法的空间复杂度大， B）一个算法的空间复杂度大，则其时间复杂度必定小 ）一个算法的空间复杂度大， C）一个算法的时间复杂度大，则其空间复杂度必定小 ）一个算法的时间复杂度大， D）上述三种说法都不对 ） 第13页 二、数据结构

程序=算法 数据结构 程序 算法+数据结构 算法

计算机在进行数据处理时， 计算机在进行数据处理时，实际需要处理的数据元素一般有 很多，而这些大量的数据元素都需要存放在计算机中，因此，大量 很多，而这些大量的数据元素都需要存放在计算机中，因此， 数据元素在计算机中如何组织，以便提高数据处理的效率， 的数据元素在计算机中如何组织，以便提高数据处理的效率，并且 节省计算机的存储空间，这是进行数据处理的关键问题。 节省计算机的存储空间，这是进行数据处理的关键问题。

数据结构是指相互有关联的数据元素的集合。 数据结构是指相互有关联的数据元素的集合。

一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系 的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。

一般情况下，在具有相同特征的数据元素集合中， 一般情况下，在具有相同特征的数据元素集合中，各个数据 元素之间存在有某种关系（即联系）， ），这种关系反映了该集 元素之间存在有某种关系（即联系），这种关系反映了该集 合中的数据元素所固有的一种结构。 合中的数据元素所固有的一种结构。 第14页 二. 数据结构

数据结构是指相互有关联的数据元素的集合。 数据结构是指相互有关联的数据元素的

5

集合。

数据结构是研究数据和数据之间关系的一门

学科，它包括三个方面。 学科，它包括三个方面。 （1）数据集合中各数据元素之间所固有的逻 ） 辑关系，即数据的逻辑结构； 辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计 ）在对数据进行处理时， 算机中的存储关系，即数据的存储结构； 算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 ）对各种数据结构进行的运算。 第15页 1. 逻辑结构

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构包含： 数据的逻辑结构包含： （1）表示数据元素的信息； ）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 ）表示各数据元素之间的前后件关系。 例：

1. 一年四季的数据结构 B=(D,R) D={春，夏，秋，冬} 春 R={(春，夏) ,(夏，秋),(秋，冬)} 春 夏 秋 2. 家庭成员的数据结构 B=(D,R) D={父亲，儿子，女儿 父亲， 父亲 儿子，女儿} R={(父亲，儿子 ,(父亲，女儿 父亲， 父亲， 父亲 儿子) 父亲 女儿)} 春 数据结构的图形表示 夏 父亲 秋 冬 儿子 女儿 第16页

常见的逻辑结构有： 线性结构、树形结构和图形结构。 线性结构、树形结构和图形结构。

图 形 结 线性结构 树形结构 构 线性结构 结构 的 的 的 树形结构 结构 的 图形结构

6

结构

的 线形结构。 线形结构。 图形 。 的 。 结构 第17页

结构 的 树形结构和图形结构 2. 存储结构（物理结构） 存储结构（

计算机在实际进行数据处理时， 计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计 算机的存储空间中，并且， 算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与 它们的逻辑关系不一定是相同的，而且一般也不可能相同。 它们的逻辑关系不一定是相同的，而且一般也不可能相同。 如：一年四季 家庭成员 计算机存储空间怎样存放？

存储结构指数据结构在计算机存储空间中的具体实现。 存储结构指数据结构在计算机存储空间中的具体实现。

常见的存储结构有： 常见的存储结构有： 顺序存储结构 链式存储结构 索引存储结构 存储结构

只抽象地反映数据元素之间的关 系的结构， 系的结构，而不管其存储方式的 数据结构称为逻辑结构。 数据结构称为逻辑结构。 ? 一种数据结构可以根据需要表示 一种数据结构可以根据需要表示 成一种或多种存储结构。 成一种或多种存储结构。 第18页

通常，一个数据结构中的元素结点可能是动态变化的。 通常，一个数据结构中的元素结点可能是动态变化的。根 据需要或在处理过程中， 据需要或在处理过程中，可以在一个数据结构中增加一个新结 插入运算），也可以删除某个结点（删除运算）， ），也可以删除某个结点 ），除此之 点（插入运算），也可以删除某个结点（删除运算），除此之 对数据结构的运算还有查找、分类、合并、分解、 外，对数据结构的运算还有查找、分类、合并、分解、复制和 修改。 修改。 在对数据结构的处理过程中， 在对数据结构的处理过程中，不仅数据结构中结点的个数 在动态变化，而且， 在动态变化，而且，各数据元素之间的关系也有可能在动态地 变化。 变化。如：无序表变有序表 3. 数据的运算 检索 插入 删除 更新 排序

数据结构是研究数据和数据之间 关系的一门学科， 关系的一门学科，研究以下三方面 内容： 内容：

7

数据的逻辑结构 数据的存储结构 数据的运算 第19页 常见的数据结构

1.线性表 线性表 2.栈和队列 栈和队列 3.树 树 上一页 下一页 停止放映 第20|92页 20|92页 |92

１． 线性表（Linear List） 线性表（ List） 线性表是由n（ 线性表是由 （n≥0）个数据元素

a1，a2，…，ai，…，an组成的一个有限序列。 ， ， 组成的一个有限序列。 简单的线性表 春 夏 秋 冬 复杂的线性表

记录1 记录 记录2 记录 记录3 记录 记录4 记录 第21页 02011001 张三 男 李四 女 … … 02011003

线性表的存储结构

线性表的存储结构有两种： 线性表的存储结构有两种： 顺序存储结构 链式存储结构 存储地址 2000 2004 …

a1 a2 … ai … an … 占4个字节 个字节 线性表的顺序存储结构

顺序存储结构把逻辑上相邻的 顺序存储结构把逻辑上相邻的 逻辑上相邻 数据元素存储在物理上相邻 物理上相邻的存 数据元素存储在物理上相邻的存 储单元里，顺序存储结构只存储 储单元里，顺序存储结构只存储 结点的值，不存储结点间的关系， 结点的值，不存储结点间的关系， 结点间的关系由存储单元的邻接 关系来体现。 关系来体现。 …

8

2000+4*(i-1) …

2000+4*(n-1)

Loa（ Loa（ai）=Loa（a1）+L*（i-1） =Loa（ +L*（

第i个数的地址 第一个数的地址 L为该类型数所占的字节 第22页 顺序表的插入和删除运算

线性表的顺序存储结构称为顺序表。 线性表的顺序存储结构称为顺序表。 顺序表的插入运算 顺序表的删除运算 在线性表顺序存储情况下， 在线性表顺序存储情况下，要插入或删除一个元 素，都会由于数据元素的移动而消耗大量的处理时间， 都会由于数据元素的移动而消耗大量的处理时间， 所以这种存储方式对于小线性表或其中数据元素不经 常变动的线性表是合适的。 常变动的线性表是合适的。 第23页

线性表的链式存储结构

线性表的链式存储结构称为线性链表。 线性表的链式存储结构称为线性链表。 链式存储结构不要求逻辑上相邻的数据元素物理位 置也相邻，而且各数据元素的存储顺序也是任意的。 置也相邻，而且各数据元素的存储顺序也是任意的。 各数据元素的先后关系是由各结点的指针域指示。 各数据元素的先后关系是由各结点的指针域指示。 链式存储结构的每一个存储结点不仅存储结点的值， 链式存储结构的每一个存储结点不仅存储结点的值， 而且存储结点之间的关系： 而且存储结点之间的关系： 数据域 指针域 第24页

线性链表的物理状态 线性链表的物理状态

应用举例—— 应用举例——线性链表的存储结构 ——线性链表的存储结构 设线性表为（a1，a2，a3，a4，a5） 1 a1

线性表的顺 线性表的顺 序存储结构 序存储结构 HEAD

1 2 3 4 5 6 7 8 9 10 3 a2 a1 a4

9

9 1 10

2 a2 3 a3 4 a4 5 a5 6 7 3 1

注意:1 2 3 此类编号不 代表所在的 地址单元的 地址编码 a3 a5 10 5 0 9 5 HEAD a1 a2 a3 a4 a5 第25页

线性链表的逻辑状态 线性链表的插入和删除运算

单链表的插入运算 单链表的删除运算 采用链式存储结构，存储空间开销较大， 采用链式存储结构，存储空间开销较大，但是进行插 入和删除运算不会造成大量元素的移动。 入和删除运算不会造成大量元素的移动。 循环链表是加一种形式的链式存储结构。 循环链表是加一种形式的链式存储结构。它的特点是 表中最后一个结点的指针域指向头结点。 表中最后一个结点的指针域指向头结点。 3 HEAD 1 9 5 10 a1 a2 a3 a4 a5 第26页

10

双向链表的存储结构

提问：单向链表的缺点是什么？ 提示：如何寻找结点的直接前趋。 双向链表可以克服单链表的单向性的缺点。 在双向链表的结点中有两个指针域， 在双向链表的结点中有两个指针域，其一指向 直接后继，另一指向直接前趋。 直接后继，另一指向直接前趋。 3 HEAD 1 5 10 a1 a2 a3 a4

双向循环链表 第27页

线性表 : {a1，a2，a3，a4，a5 } ， ， ， ，

注意： 注意： 数据元素在计算机 存储空间中的位置关 系与它们的逻辑关系 不一定是相同的。 不一定是相同的。 一个逻辑数据结构 可以有多种存储结构， 可以有多种存储结构， 且不同的存储结构影 响数据处理的效率 。 线性表的存储结构有两种 顺序存储结构

1 a1 2 a2 3 a3 4 a4 5 a5 6 7 HEAD 3 链式存储结构

1 2 3 4 5 6 7 8 9 10 a3 a5 5 0 a4 10 a1 1 a2 9 第28页 2. 栈和队列

栈和队列都是特殊的线性表。 栈和队列都是特殊的线性表。 栈（Stack）及其基本运算 Stack） 队列（Queue）及其基本运算 队列（Queue） 循环队列及其基本运算 第29页

栈（Stack）是一种特殊的线性表。其特点是插入和删 Stack）是一种特殊的线性表 线性表。 除运算都只能在线性表的一端进行。 除运算都只能在线性表的一端进行。 栈是按照“先进后出” 后进先出” 栈是按照“先进后出”或“后进先出”的原则组织数 据的线性表。 据的线性表。 栈的物理存储结构可以用顺序结构， 栈的物理存储结构可以用顺序结构，也

11

可以用链表结 构。 下面讨论顺序存储结构中栈元素的插入和删除运算。 下面讨论顺序存储结构中栈元素的插入和删除运算。 顺序栈的进栈和出栈运算

栈的基本运算有三种：入栈、 栈的基本运算有三种：入栈、退栈和读栈顶元素 在顺序栈中插入和删除运算不需要 移动表中其他数据元素。 移动表中其他数据元素。 第30页

队列（Queue）是一种特殊的线性表。其特点是所有的 队列（Queue）是一种特殊的线性表。 插入都在表的一端进行 所有的删除运算都在表的另 进行， 删除运算都在表的 插入都在表的一端进行，所有的删除运算都在表的另 一端进行 进行。 一端进行。 队列是按照“先进先出” 后进后出” 队列是按照“先进先出”或“后进后出”的原则组织 数据的线性表。 数据的线性表。 队列的物理存储结构可以用顺序结构，也可以用链式 队列的物理存储结构可以用顺序结构， 结构。 结构。 顺序队列的运算

栈有三种操作： 入栈＼出栈＼ 栈有三种操作： 入栈＼出栈＼读栈顶元素 队列有三种操作：入队＼出队＼ 队列有三种操作：入队＼出队＼读队首元素 例：有入栈元素序列：ABCD，求可能的出栈序列． 有入栈元素序列： ，求可能的出栈序列． 如是队列又是什么情况呢？ 如是队列又是什么情况呢？ 第31页

循环队列 把队列的存储空间在逻辑上看作一个环， 把队列的存储空间在逻辑上看作一个环，当R指向存 指向存 储空间的末端后，就把它重新置于始端。 储空间的末端后，就把它重新置于始端。 循环队列的运算

队列中进行插入的一端称做队尾(rear),进行删除的一端 进行删除的一端 队列中进行插入的一端称做队尾 称做队首(front)。 称做队首 。

习题：数据结构分为逻辑结构和存储结构， 习题：数据结构分为逻辑结构和存储结构，循环队 列属于【 结构。（ 。（2005年9月） 列属于【 】结构。（ 年 月 答案：存储结构。 答案：存储结构。 第32页

常见数据结构的逻辑结构 线性表 栈 队列

也是一种操作受限的特殊的线性表 线性结构 是特殊的线性表 树型结构） 树 （树型结构） 是一种重要的非线形数据结构

12

第33页

数据存储结构方面的考题

1：数据的存储结构是指 （2005年4月） ： 年 月 A) 存储在外存中的数据 C) 数据在计算机中的顺序存储方式 2. 下列叙述中正确的是 （2009年3月） 年 月 A）栈是“先进先出”的线性表 ）栈是“先进先出” B）队列是“先进后出”的线性表 ）队列是“先进后出” C）循环队列是非线性结构 ） D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 ）有序线性表既可以采用顺序存储结构， B) 数据所占的存储空间量 D) 数据的逻辑结构在计算机中的表示 答案：D。 答案： 。 答案：D。 答案： 。

3. 数据结构分为线性结构和非线性结构，带链的队列属于 数据结构分为线性结构和非线性结构，带链的队列属于[ 4. 下列数据结构中，属于非线性结构的是 下列数据结构中， A）循环队列 ） C) 二叉树 B) 带链队列 D）带链栈 ）

]。 。 答案：线性结构。 答案：线性结构。 答案： 答案：c 第34页

5。下列叙述中正确的是（ ）。 （2008年9月） 。下列叙述中正确的是（ 年 月 答案： 。 答案：A。

A）顺序存储结构的存储一定是连续的，链式存储结构的存储空 ）顺序存储结构的存储一定是连续的， 间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性 ）顺序存储结构只针对线性结构， 结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 ）顺序存储结构能存储有序表， D）链式存储结构比顺序存储结构节省存储空间 ）

答案： 。 6。下列关于栈的叙述正确的是 （2008年4月） 年 月 栈按“先进先出” B)栈按 先进后出” 栈按“ A）栈按“先进先出”组织数据 B)栈按“先进后出”组织数据 C）只能在栈底插入数据 D）不能删除数据 答案：B。 答案： 。

7. 一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3， 一个队列的初始状态为空。现将元素 ， ， ， ， ， ， ， ， ， 2，1依次入队，然后再依次退队，则元素退队的顺序为 【1】 。（2010 ， 依次入队，然后再依次退队， 】 。（ 依次入队 年3月） 月 答案： ， ， ， ， ， ， ， ， ， ， 答案：A，B，C，D，E，F，5，4，3，2，1 第35页

8。假设用一个长度为50的数组（数组元索的下标从 。假设用一个长度为 的数组 数

13

组元索的下标从0 的数组（ 到49）作为栈的存储空间，栈底指针 ）作为栈的存储空间，栈底指针bottom指间栈底 指间栈底 元素，栈顶指针top指向栈顶元素，如果bottom=49， 元素，栈顶指针 指向栈顶元素，如果 ， 指向栈顶元素 top=30（数组下标），则栈中具有【 】个元素。 ），则栈中具有 个元素。 （数组下标），则栈中具有【 （2009年3月） 年 月 答案： 答案：19

9. 设某循环队列的容量为 ，如果头指针 设某循环队列的容量为50，如果头指针front=45(指向 指向 队头元素的前一位置)，尾指针rear=10(指向队尾元素 ， 指向队尾元素)， 队头元素的前一位置 ，尾指针 指向队尾元素 则该循环队列中共有 【2】 个元素。 （2010年3月） 】 个元素。 年 月 答案： 答案：15 第36页 线性结构与非线性结构

线性表、 线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为非线性结 一个数据结构不是线性结构，则称其为非线性结 构。

一个非空的数据结构若满足下面的两个条件， 一个非空的数据结构若满足下面的两个条件，则这种数据结 构即为线性结构 线性结构。 构即为线性结构。 有且仅有一个根结点； ① 有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个直接前驱结点； ② 除第一个结点外，每一个结点最多有一个直接前驱结点； 除最后一个结点外，每一个结点最多有一个直接后继结点。 ③ 除最后一个结点外，每一个结点最多有一个直接后继结点。 3 HEAD 1 9 5 10 a1 a2 a3 a4 a5 第37页

线性链表的逻辑状态 3. 树与二叉树

树型结构是一种重要的非线性结构。 树型结构是一种重要的非线性结构。 树的概念 二叉树的概念 二叉树的存储 二叉树的遍历

14

第38页 树的概念

树的定义： 个结点的有限集。（n>=0） 个结点的有限集。（ 树的定义：n个结点的有限集。（ ） 根：only one 若n=0，则称为空树； ，则称为空树； 否则， 否则，当n>1时，其余结 时 点被分成m（ 点被分成 （m>0）个互不 ） 相交的子集T1， ， ， 相交的子集 ，T2，……， Tm，每个子集又是一棵树。 ，每个子集又是一棵树。 由此可以看出， 由此可以看出，树的定义是 递归的。 递归的。 Question：如何辨别根？ ：如何辨别根？ 第39页 E B F J A C G K D H M I 只有一个 结点的树 A

树型结构的常用术语

结点的度 一个结点的子树的 个数； ：结点A、 的度数 的度数？ 个数； Q：结点 、G的度数？ 树的度 树中所有结点度的最 大值； ：右图中树的度？ 大值；Q：右图中树的度？ 终端结点 度为 的结点； 度为0的结点 的结点； Q：图中叶子结点有几个？7 ：图中叶子结点有几个？ 非终端结点 度不为 的结点； 度不为0的结点 的结点； Q：图中非终端结点有几个？ 5 ：图中非终端结点有几个？

孩子结点、双亲结点、兄弟结点、结点的子孙、 孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先

第40页 B E F J A C G K D H M I 树型结构的常用术语

结点的层次 树中根结点的层 ① 次为1，根结点子树的根为第2层 次为 ，根结点子树的根为第 层， ② 以此类推； 以此类推； Q：图中结点F的层次？ ：图中结点 的层次 的层次？ ③

E A B F J C G K D H M I

树的深度 树中所有结点层次 的最大值； ：图中树的深度？ 的最大值； Q：图中树的深度？ 有序树、无序树 如果树中每 有序树、 棵子树从左向右的排列拥有一定 的顺序，不得互换， 的顺序，不得互换，则称为有序 否则称为无序树。 树，否则称为无序树。 ④ 第41页

15

二叉树的概念

定义：二叉树是一种有序的树形结构。 定义：二叉树是一种有序的树形结构。它与一般 树形结构的区别是： 树形结构的区别是：

每个结点最多有两棵子树； 每个结点最多有两棵子树； 子树有左右之分，次序不能任意颠倒。 子树有左右之分，次序不能任意颠倒。 二叉树的5种基本形态 二叉树的 种基本形态 第42页 二叉树的性质

【性质1】 在二叉树的第 层上最多有 i-1个结点（i≥1） 在二叉树的第i层上最多有 个结点（ ≥ ） 层上最多有2 A B E F G H 第43页 C D

【性质2】深度为 的二叉树最多有2h -1个结点（h ≥1） 深度为h的二叉树最多有 个结点（ ） 深度为 的二叉树最多有 个结点 满二叉树：如果一个深度为 的二叉树拥有 满二叉树：如果一个深度为h的二叉树拥有 h-1个结 的二叉树拥有2 个结 点，则将它称为满二叉树。 则将它称为满二叉树。 满二叉树 完全二叉树：有一棵深度为 ，具有 个结点的二叉树， 完全二叉树：有一棵深度为h，具有n个结点的二叉树， 个结点的二叉树 若将它与一棵同深度的满二叉树中的所有结点按从上 到下，从左到右的顺序分别进行编号， 到下，从左到右的顺序分别进行编号，且该二叉树中 的每个结点分别与满二叉树中编号为1~n的结点位置 的结点位置 的每个结点分别与满二叉树中编号为 一一对应，则称这棵二叉树为完全二叉树。 一一对应，则称这棵二叉树为完全二叉树。 完全二叉树 第44页

满二叉树 满 二 叉 树 也 是 完 满 全 二 二 叉 树 完全二叉树 第45页

完 全 二 叉 树 是 叉 树 非完全二叉树

深度为4的 深度为 的 完全二叉树 第46页

【性质3】二叉树上叶子结点数比度为 的结点数多 二叉树上叶子结点数比度为2的结

16

点数多 二叉树上叶子结点数比度为 的结点数多1 A B E F G H C D 叶子结点 度为2的结点 第47页

【性质4】具有 个结点的完全二叉树的深度为 ?log2 (n+1) ? 具有n个结点的完全二叉树的深度为 具有 其中， 其中，?log2n? 的结果是不大于 ? 的结果是不大于log2n的最大整数 的最大整数

深度为4的 深度为 的 满二叉树 深度为4的 深度为 的 完全二叉树

log2(8+1) ? = ln9/In2=4 ?log2 (15+ 1)? =In16/In2=4 ? 深度为3的完全二叉树 具有4～ 深度为 的完全二叉树 具有 ～7 深度为4的完全二叉树 具有8～ 深度为 的完全二叉树 具有 ～15 深度为5的完全二叉树 具有15～ 深度为 的完全二叉树 具有 ～31

深度为6的完全二叉树 深度为 的完全二叉树 深度为7的完全二叉树 深度为 的完全二叉树 深度为8的完全二叉树 深度为 的完全二叉树 深度为9的完全二叉树 深度为 的完全二叉树 深度为10的完全二叉树 深度为 的完全二叉树 深度为11的完全二叉树 深度为 的完全二叉树

具有32～ 具有 ～63 具有64～ 具有 ～127 具有128～255 具有 ～ 具有256～511 具有 ～ 具有512～1023 具有 ～ 具有1024～2047 具有 ～ 第48页 树型结构方面的考题

1：在深度为7的满二叉树中,叶子结点的个数为（2006年4月） 在深度为7的满二叉树中,叶子结点的个数为（2006年 A)32 A)32 B)31 B)31 C)64 C)64 D)63 D)63 1答案：C。 答案： 。 答案

2：在深度为7的满二叉树中，度为2的结点个数为【 在深度为7的满二叉树中，度为2的结点个数为【

07年 】 。(07年4月） 2答案：63。 答案： 。 答案

一棵二叉树中共有70个叶子结点与80个度为1的结点， 70个叶子结点与80个度为 3：一棵二叉树中共有 70个叶子结点与80 个度为1的结点，则该二叉树中的总 07年 结点数为 （07年9月） A）219 B）221 C）229 3答案：A。 答案： 。 答案

D）231 个叶子结点。 】个叶子结点。 】个。（2005 4答案：19。 答案： 。 答案

17

某二叉树中度为2的结点有18 18个 4： 某二叉树中度为2的结点有18个，则该二叉树中有 【 （2005年4月） 2005年 年9月）

一棵二叉树第六层（根结点为第一层）的结点数最多为【 5：一棵二叉树第六层（根结点为第一层）的结点数最多为【

5答案：32。 答案： 。 答案 第49页 二叉树的存储

在计算机中，二叉树通常采用链式存储结构。 在计算机中，二叉树通常采用链式存储结构。

Llink info Rlink t

二叉树的存储结点的结构 A B D G ∧ A C B F ∧ ∧ C ∧ E D G ∧ E ∧ ∧ F ∧ 第50页 二叉树的遍历

遍历指不重复地访问二叉树中的所有结点。 遍历指不重复地访问二叉树中的所有结点。 不重复地访问二叉树中的所有结点 二叉树的遍历的次序与树型结构上的大多 数运算有联系。 数运算有联系。 遍历的方式有三种 序遍历（ （1）先（前）序遍历（DLR） ） ） （2）

18

中序遍历（LDR） ）中序遍历（ ） （3）后序遍历（LRD） ）后序遍历（ ） H 第51页 A C F G D B E

二叉树的遍历

遍历指不重复地访问二叉树中的所有结点。 遍历指不重复地访问二叉树中的所有结点。 不重复地访问二叉树中的所有结点 序遍历（ （1）先（前）序遍历（DLR） ） ） 若二叉树为空，则结束遍历操作； 若二叉树为空，则结束遍历操作；否则 访问根结点； 访问根结点； 先序遍历左子树； 先序遍历左子树； 遍历左子树 先序遍历右子树。 先序遍历右子树。 遍历右子树 G E B F A C D

先序遍历的结果： 先序遍历的结果： A B E C F G H D H 第52页

（2）中序遍历（LDR） ）中序遍历（ ） 若二叉树为空，则结束遍历操作； 若二叉树为空，则结束遍历操作；否则 中序遍历左子树； 中序遍历左子树； 访问根结点； 访问根结点； 中序遍历右子树。 中序遍历右子树。 中序遍历的结果： 中序遍历的结果： E B A F H G C D （3）后序遍历（LRD） ）后序遍历（ ） 若二叉树为空，则结束遍历操作； 若二叉树为空，则结束遍历操作；否则 后序遍历左子树； 后序遍历左子树； 后序遍历右子树； 后序遍历右子树； 访问根结点。 访问根结点。 后序遍历的结果： 后序遍历的结果： E B H G F D C A 第53页 A B E F G H C D 练习： 练习：

下图所示的二叉树经过三种遍历得到的顺序分别为？ 下图所示的二叉树经过三种遍历得到的顺序分别为？ A B D G E H C F

先序序列： 先序序列： ABDGCEFH 中序序列： 中序序列： DGBAECHF 后序序列： 后序序列： GDBEHFCA

19

根据先序遍历序列， 根据先序遍历序列，建立二叉树 第54页

树型结构方面的考题 2

1:设二叉树如下： 设二叉树如下： 设二叉树如下 （2010年3月） 年 月 对该二叉树进行后序遍历的 结果为 【3】 】 EDBGHFCA A B C F E G H D

2: 对如下二叉树（2006年4月） 对如下二叉树（ 年 月 进行后序遍历的结果为 A) ABCDEF B) DBEAFC D C) ABDECF D) DEBFCA 第55页 ⒌ 查找技术

查找是数据处理的重要内容。 查找是数据处理的重要内容。 查找指在一个给定的数据结构中查找指定的元素， 查找指在一个给定的数据结构中查找指定的元素， 该元素也称关键字。 该元素也称关键字。 若找到了满足条件的结点，称查找成功； 若找到了满足条件的结点，称查找成功；否则称查 找失败。 找失败。 衡量一个查找算法的主要标准是查找过程中对关键 字进行的平均比较次数。 字进行的平均比较次数。 通常根据不同的数据结构，采用不同的查找方法： 通常根据不同的数据结构，采用不同的查找方法： 顺序查找 二分查找 第56页 顺序查找

线性表中最简单的查找方法。 线性表中最简单的查找方法。 方法：从线性表的第一个元素开始， 方法：从线性表的第一个元素开始，依次将线性表 中的元素与关键字进行比较，若相等，则查找成功； 中的元素与关键字进行比较，若相等，则查找成功； 若将所有元素都与关键字进行了比较但不相等，则 若将所有元素都与关键字进行了比较但不相等， 查找失败。 查找失败。 顺序查找法的适用场合： 顺序查找法的适用场合： 对线性表中元素的排列次序没有要求； 对线性表中元素的排列次序没有要求； 对线性表的存储结构没有要求， 对线性表的存储结构没有要求，链式结构和顺 序结构均可。 序结构均可。 第57页

二分查找(折半查找)

20

是一种效率较高的查找方法，但是只适合顺序存储 是一种效率较高的查找方法，但是只适合顺序存储 的有序表。 的有序表。 二分查找的方法： 二分查找的方法：首先将关键字与线性表中间位置 的结点比较，相等则查找成功；不相等则根据比较 的结点比较，相等则查找成功； 结果确定下一步查找应在哪个子表中进行； 结果确定下一步查找应在哪个子表中进行；重复上 述过程，直至查找成功或子表长度为0。 述过程，直至查找成功或子表长度为 。 二分查找法的适用场合： 二分查找法的适用场合： 线性表中的元素按关键字值递增或递减的次序排 列； 线性表采用顺序存储结构。 线性表采用顺序存储结构。 第58页

折半查找算法举例

对给定数列（有序） 3， 11，17，21，23，28， 对给定数列（有序）{ 3，5，11，17，21，23，28， 30，32，50}，按折半查找算法，查找关键字值为30 30，32，50}，按折半查找算法，查找关键字值为30 的数据元素。 的数据元素。

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 3， 11，17，21，23，28，30，32， 第1次： { 3，5，11，17，21，23，28，30，32，50 } K=30 mid1=（1+10） mid1=（1+10）/2 = 5 low mid high

k>a(mid1)=a(5)=21

23，28，30，32， 第2次： { 23，28，30，32，50 low

上一页 下一页 停止放映 } high mid

mid2 = （6+10） /2 = 8 6+10） K=a(mid2)=a(8)=30 第59|92页 59|92页 |92 练习

假设待查有序（升序）顺序表中数据元素的关键字序列 为（8,18,27,42,47,50,56,

21

68,95,120），用折半查找 方法查找关键字值为27的数据元素.

对于长度为n的有序线性表，最坏情况只需比较log2n次 对于长度为n的有序线性表，最坏情况只需比较log2n次。 log2n 第60页 ⒍ 排序技术

排序指将一个无序序列整理成按关键字值递增或递减排列的有序 排序指将一个无序序列整理成按关键字值递增或递减排列的有序 序列。 序列。 顺序存储的线性表 排序方法中其排序对象一般是顺序存储的线性表。 排序方法中其排序对象一般是顺序存储的线性表。 根据排序序列的规模以及数据处理的要求， 根据排序序列的规模以及数据处理的要求，可以采用不同的排序 方法： 交换类排序法 冒泡排序 快速排序 插入类排序法

简单插入排序 希尔排序 选择类排序法 简单选择排序 堆排序 第61页 冒泡排序

冒泡排序的方法： 冒泡排序的方法： 扫描整个线性表， 扫描整个线性表，逐次对相邻的两个元素进行比 若为逆序，则交换； 较，若为逆序，则交换；第一趟扫描的结果使最 或最小)的元素排到表的最后 或最前) 大(或最小 的元素排到表的最后 或最前 ； 或最小 的元素排到表的最后(或最前 除最后(或最前)一个元素 除最后(或最前)一个元素，对剩余的元素重复上 或最前 一个元素， 述过程，将次大(或次小 的数排到表的倒数(或正 或次小)的数排到表的倒数 述过程，将次大 或次小 的数排到表的倒数 或正 第二个位置； 数)第二个位置； 第二个位置 重复上述过程； 重复上述过程； 对于长度为n的线性表， 对于长度为 的线性表，冒泡排序需要对表扫描 的线性表 n-1遍。 遍 第62页 冒泡排序的方法

设待排数据元素的关键字为（ ， ， ， 设待排数据元素的关键字为（18，20，15， 32，4，25），第一趟冒泡排序后的序列状 ），第一趟 ， ， ），第一趟冒泡排序后的序列状 态

22

如图所示：

18 18 18 18 18 18 上一页 下一页 停止放映

20 15 32 4 20 15 32 4 15 20 32 4 15 20 32 4 15 20 4 32 15 20 4 25 25 25 25 25 25 32 最大数 第63|92页 63|92页 |92 第二趟冒泡排序

Q：第二趟冒泡排序后的结果是什么样的？达到 ：第二趟冒泡排序后的结果是什么样的？

了最终的排序目标吗？ 了最终的排序目标吗？一共需要多少次能够最 后成为有序序列？ 后成为有序序列？ Q：你觉得冒泡排序的效率如何？如果是你，你 ：你觉得冒泡排序的效率如何？如果是你， 会用什么方法来排序？ 会用什么方法来排序？ 冒泡排序比较简单，当初始序列基本有序时， 冒泡排序比较简单，当初始序列基本有序时， 冒泡排序有较高的效率，反之效率较低。 冒泡排序有较高的效率，反之效率较低。 冒泡排序终止条件: 冒泡排序终止条件

本趟排序未发生交换， 本趟排序未发生交换，终止排序算法 上一页 下一页 停止放映 第64|92页 64|92页 |92

设待排数据元素的关键字为 （26,18,32,54,47,9,15 )

初始 序列 第一趟 排序后 第二趟 排序后 第三趟 排序后 第四趟 排序后 第五趟 排序后

26 18 32 54 47 9 15 上一页 下一页 停止放映 18 26 32 47 9 15 54 18 26 32 9 15 47 18 26 9 15 32 18 9 15 26 9 15 18

冒泡排序法，需要比较的次数为n(n-1)/2； 冒泡排序法，需要比较的次数为n(n-1)/2； n(n

23

第65|92页 65|92页 |92 选择排序

选择排序的方法： 选择排序的方法： 扫描整个线性表，从中找出最小的元素， 扫描整个线性表，从中找出最小的元素，与第 一个元素交换； 一个元素交换； 除第一个元素，对剩下的子表采用相同的方法 除第一个元素， 找出次小的数，与第二个数交换； 找出次小的数，与第二个数交换； 重复上述过程； 重复上述过程； 对于长度为n的线性表， 对于长度为 的线性表，选择排序需要对表扫 的线性表 描n-1遍。 遍

简单选择排序法, 最坏情况需要n(n 1)/2次比较 n(n次比较； 简单选择排序法, 最坏情况需要n(n-1)/2次比较； 第66页

例：设待排数据元素的关键字为（15，14，22，30， 设待排数据元素的关键字为（ ， ， ， ， 37，11），每一趟排序后的序列状态如图所示： ），每一趟排序后的序列状态如图所示 ， ），每一趟排序后的序列状态如图所示： 初态： 初态：

[15，14，22，30，37，15，11] ， ， ， ， ， ，

第一趟： 第一趟： [11] [14，22，30，37，15，15] ， ， ， ， ， 第二趟： 第二趟： [11，14] [22，30，37，15，15] ， ， ， ， ， 第三趟： [11，14， [30，37，22， 第三趟： [11，14，15] [30，37，22，15] 第四趟： [11，14，15，15] [37，22，30] 第四趟： ， ， ， ， ， 第五趟： 第五趟： [11，14，15，15，22] [37，30] ， ， ， ， ， 上一页 下一页 停止放映

第六趟： 第六趟： [11，14，15，15，22，30] [37] ， ， ， ， ， 有序序列 第67|92页 67|92页 |92 排序法小结： 排序法小结：

简单选择排序法, 最坏情况需要n(n-1)/2次比较； 次比较； 简单选择排序法 最坏情况需要 次比较 冒泡排序法, 冒泡排序法 希尔排序法, 希尔排序法 堆排序法, 堆排序法 最坏情况需要n(n-1)/2次比较； 次比较； 最坏情况需要 次比较 最坏情况需要O(n1.5)次比较； 次比较； 最坏情况需要 次比较 最坏情况需要O(nlog2n)次比较； 次比较； 最坏情况需要 次比较 第68页

排序查找方面的考题： 排序查找方面的考题：

24

(1) 对于长度为 的线性表，在最坏情况下，下列各排序法所对应的比较 对于长度为n的线性表，在最坏情况下， 的线性表 次数中正确的是（ 次数中正确的是（2005年4月） 年 月 D A) 冒泡排序为 冒泡排序为n/2 B) 冒泡排序为 冒泡排序为n C) 快速排序为 快速排序为n D) 快速排序为 快速排序为n(n-1)/2 (2)在长为 的有序线性表中进行顺序查找，最坏情况下需要比较的次数 在长为64的有序线性表中进行顺序查找 在长为 的有序线性表中进行顺序查找， 为。（06年9月） 。 年 月 A）、 ）、63 ）、 B）、 ）、64 ）、 C）、 ）、6 ）、 D）、 ）、7 ）、 B

(3) 下列数据结构中，能用二分法进行查找的是（2005年9月） 下列数据结构中，能用二分法进行查找的是（ 年 月 A）顺序存储的有序线性表 B）线性链表 ） ） A C）二叉链表 D）有序线性链表 ） ） (4) 下列排序方法中，最坏情况下比较次数最少的是（09年3月） 下列排序方法中，最坏情况下比较次数最少的是（ 年 月 A）冒泡排序 B）简单选择排序 ） ） D C）直接插入排序 ） D）堆排序 ） 第69页

第二章 程序设计基础

内容： 内容： 1. 程序设计方法与风格。 程序设计方法与风格。 结构化程序设计。 2. 结构化程序设计。 面向对象的程序设计方法，对象， 3. 面向对象的程序设计方法，对象，方 属性及继承与多态性。 法，属性及继承与多态性。 第70页

1．结构化程序设计

结构化程序设计方法的四条原则是：

1. 2. 3. 4. 自顶向下； 逐步求精； 模块化； 限制使用goto语句。 结构化程序的基本结构和特点： 结构化程序的基本结构和特点：

（1）顺序结构： ）顺序结构： 简单的程序设计，最基本、最常用的结构； （2）选择结构（分支结构）： ）选择结构（分支结构）： 包括简单选择和多分支选择结构， （3）重复结构（循环结构）： ）重复结构（循环结构）： 可根据给定条件，判断是否需要重复执行某一相同程序段。 第71页

2．面向对象的程序设计

对象是面向对象方法中最基本的概念。 对象是面向对象方法中最基本的概念。

25

对象是系统中用来描述客观事物的一个实 对象是系统中用来描述客观事物的一个实 是构成系统的一个基本单位， 体，是构成系统的一个基本单位，由一组 表示其静态特征的属性和它可执行的一组 操作组成。 操作组成。

属性即对象所包含的信息 属性即对象所包含的信息 操作描述了对象执行的功能，操作也称为方 操作描述了对象执行的功能， 描述了对象执行的功能 法或服务。 法或服务。 第72页

类是指具有共同属性、共同方法的对象的集合。 是指具有共同属性、共同方法的对象的集合。 所以类是对象的抽象，对象是对应类的一个实例 是对应类的一个实例。 所以类是对象的抽象，对象是对应类的一个实例。 消息是一个实例与另一个实例之间传递的信息 是一个实例与另一个实例之间传递的信息。 消息是一个实例与另一个实例之间传递的信息。 消息的组成包括 （1）接收消息的对象的名称； ）接收消息的对象的名称； （2）消息标识符，也称消息名； ）消息标识符，也称消息名； （3）零个或多个参数。 ）零个或多个参数。 继承是指能够直接获得已有的性质和特征 是指能够直接获得已有的性质和特征， 继承是指能够直接获得已有的性质和特征，而不必重 复定义他们。 复定义他们。 单继承指一个类只允许有一个父类 多重继承指一个类允许有多个父类。 多重继承指一个类允许有多个父类。 多态性是指同样的消息被不同的对象接受时可导致完 多态性是指同样的消息被不同的对象接受时可导致完 全不同的行动的现象。 全不同的行动的现象。 第73页

程序设计基础方面的考题

1.符合结构化原则的三种基本控制结构是：选择结构、循环结构和【 】 . 符合结构化原则的三种基本控制结构是：选择结构、循环结构和【

(2009年3月) 年 月 2. 下列选项中不属于结构化程序设计原则的是（2009年9月） 下列选项中不属于结构化程序设计原则的是（ 年 月 A) 可封装 D) 自顶向下 （顺序结构） 顺序结构） A

C) 模块化 D) 逐步求精 3. 以下叙述中正确的是。（ 以下叙述中正确的是。（ 。（2010年3月） 年 月 A）程序设计的任务就是编写程序代码并上机调试 ） B）程序设计的任务就是确定所用数据结构 ） C）程序设计的任务就是确定所用算法 ） D）以上三种说法都不完整 ） D

26

对象

4.在面向对象方法中，类的实例称为 【】 。（ 在面向对象方法中， 在面向对象方法中 】 。（2005年4月） 年 月 5.在面向对象方法中 【】 描述的是具有相似属性与操作的一组对象。 在面向对象方法中, 在面向对象方法中 】 描述的是具有相似属性与操作的一组对象。 类 （2006年4月） 第74页

第三章 软件工程基础

计算机软件是包括程序、 计算机软件是包括程序、数据及相关文 档的完整集合。 档的完整集合。 软件按功能分为应用软件、系统软件、 软件按功能分为应用软件、系统软件、 支撑软件（或工具软件）。 支撑软件（或工具软件）。 第75页

1.软件工程概念 软件工程概念

软件工程是应用于计算机软件的定义、 软件工程是应用于计算机软件的定义、开发和维护的 一整套方法、工具、文档、实践标准和工序。 一整套方法、工具、文档、实践标准和工序。 软件工程包括3个要素 方法、工具和过程。 个要素： 软件工程包括 个要素：方法、工具和过程。 软件周期：软件产品从提出、实现、 软件周期：软件产品从提出、实现、使用维护到停止 使用退役的过程。 使用退役的过程。 软件生命周期三个阶段:软件定义 软件开发、 软件定义、 软件生命周期三个阶段 软件定义、软件开发、运行 维护，主要活动阶段是： 维护，主要活动阶段是：

（1）可行性研究与计划制定； 可行性研究与计划制定； 可行性研究与计划制定 （2）需求分析； ）需求分析； （3）软件设计； ）软件设计； （4）软件实现； ）软件实现； （5）软件测试； ）软件测试； （6）运行和维护。 ）运行和维护。 第76页

2．结构化分析方法

结构化分析方法：着眼于数据流，自顶向下， 结构化分析方法 着眼于数据流，自顶向下， 着眼于数据流 逐层分解，建立系统的处理流程， 逐层分解，建立系统的处理流程，以数据流图 和数据字典为主要工具,建立系统的逻辑模型。 和数据字典为主要工具 建立系统的逻辑模型。 建立系统的逻辑模型 结构化分析的常用工具 （1）数据流图； ）数据流图； （2）数据字典； ）数据字典； （3）判定树； 判定表。 ）判定树； 判定表。 （4）软件需求规格说明书 ）

27

第77页

3．结构化设计方法

软件设计包括： 软件设计包括：总体设计与详细设计 在程序结构中各模块的内聚性越强， 在程序结构中各模块的内聚性越强，则耦合性 越弱。优秀软件应高内聚，低耦合。 越弱。优秀软件应高内聚，低耦合。 常见的过程设计工具有： 常见的过程设计工具有： 图形工具（程序流程图,N-S,PAD） 图形工具（程序流程图 ） 表格工具（判定表） 表格工具（判定表） 语言工具（ 伪码） 语言工具（PDL伪码） 伪码 第78页 程序流程图 N-S图 图 PAD图 图 第79页 4．软件测试

软件测试的目的：发现错误而执行程序的过程。 软件测试方法： 软件测试方法： 静态测试： 静态测试： 包括代码检查、静态结构分析、代码质量度量。不实际 运行软件，主要通过人工进行。 动态测试： 动态测试： 是基本计算机的测试，主要包括白盒测试方法和黑盒 测试方法 软件测试过程一般按4个步骤进行：单元测试、集成测 试、验收测试（确认测试）和系统测试。 第80页 5 ．程序的调试

程序调试的任务是诊断和改正程序中的错误， 程序调试的任务是诊断和改正程序中的错误， 诊断和改正程序中的错误 主要在开发阶段进行。 主要在开发阶段进行。 软件调试 静态调试主要是指通过人的思维来分析源程 静态调试主要是指通过人的思维来分析源程 序代码和排错，是主要的设计手段。 序代码和排错，是主要的设计手段。 动态调试是辅助静态调试 主要调试方法有： 是辅助静态调试。 动态调试是辅助静态调试。主要调试方法有： （1）强行排错法； ）强行排错法； （2）回溯法； ）回溯法； （3）原因排除法。 ）原因排除法。 第81页

软件工程方面的考题： 软件工程方面的考题： (1) 下面叙述中错误的是 (2009年3月） 年 月

28

A）软件测试的目的是发现错误并改正错误 ） B）对被调试的程序进行“错误定位”是程序调试的必要步骤 ）对被调试的程序进行“错误定位” C）程序调试通常也称为 ）程序调试通常也称为Debug D）软件测试应严格执行测试计划，排除测试的随意性 ）软件测试应严格执行测试计划， 白盒 (2) 软件测试可分为白盒测试和黑盒测试。基本路径测试属于【 】 软件测试可分为白盒测试和黑盒测试。基本路径测试属于【 测试。 测试。(2009年3月） 年 月 单元 (3) 按照软件测试的一般步骤，集成测试应在 按照软件测试的一般步骤，集成测试应在测试之后进行。 测试之后进行。 测试之后进行 (4) 软件工程三要素包括方法、工具和过程，其中，支持软件 软件工程三要素包括方法、工具和过程，其中， 支持软件 开发的各个环节的控制和管理。 开发的各个环节的控制和管理。(2008年9月) 年 月 过程 (5)软件设计中划分模块的一个准则是 软件设计中划分模块的一个准则是(2009年9月） 软件设计中划分模块的一个准则是 年 月 A) 低内聚低耦合 B) 高内聚低耦合 B C) 低内聚高耦合 D) 高内聚高耦合 A 第82页

(6) 下列叙述中正确的是（2005年9月）A 下列叙述中正确的是（ 年 月 A）软件交付使用后还需要进行维护 ） A B）软件一旦交付使用就不需要再进行维护 ） C）软件交付使用后其生命周期就结束 ） D）软件维护是指修复程序中被破坏的指令 ） 逻辑条件 (7) 程序流程图中的菱形框表示的是 【2】(2009年9月) 。 】 年 月 (8)软件开发过程主要分为需求分析、设计、编码与测试四个阶段， 软件开发过程主要分为需求分析、 软件开发过程主要分为需求分析 设计、编码与测试四个阶段， 其中 【3】 阶段产生“软件需求规格说明书。 】 阶段产生“软件需求规格说明书。 需求分析 （2009年9月） 年 月 (9)下列叙述中正确的是（2006年4月） 下列叙述中正确的是（ 下列叙述中正确的是 年 月 A)软件测试应该由程序开发者来完成 软件测试应该由程序开发者来完成 B)程序经调试后一般不需要再测试 程序经调试后一般不需要再测试 D C)软件维护只包括对程序代码的维护 软件维护只包括对程序代码的维护 D)以上三种说法都不对 以上三种说法都不对 第83页

2010年3月计算机等级考试 年 月计算机等级考试

(3)软件按功能可以分为：应用软件 、系统软件和支撑软件 或工具软 软件按功能可以分为：应用软件、系统软件和支撑软件(或工具软 软件按功能可以分为 件)。下面属于系统软件的是 。 B A)编辑软件 编辑软件 C)教务管理系统 教务管理系统 B)操作系统 操作系

29

统 D)浏览器 浏览器 A

(4)软件 程序 调试的任务是 软件(程序 软件 程序)调试的任务是 A)诊断和改正程序中的错误 诊断和改正程序中的错误 (5)数据流程图 数据流程图(DFD图)是 数据流程图 图是 A)软件概要设计的工具 软件概要设计的工具 C)结构化方法的需求分析工具 结构化方法的需求分析工具 C)发现并改正程序中的所有错误 发现并改正程序中的所有错误 B)尽可能多地发现程序中的错误 尽可能多地发现程序中的错误 D)确定程序中错误的性质 确定程序中错误的性质 C

B)软件详细设计的工具 软件详细设计的工具 D)面向对象方法的需求分析工具 面向对象方法的需求分析工具

(6)软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属 软件生命周期可分为定义阶段，开发阶段和维护阶段。 软件生命周期可分为定义阶段 于 B A)定义阶段 定义阶段 C)维护阶段 维护阶段 B)开发阶段 开发阶段 D)上述三个阶段 上述三个阶段 第84页

数据库设计基础知识点得分表 知识点 时间

数据库的 基本概念 2分 2分 2分 2分 2分 数据 模型 6分 4分 2分 2分 4分 关系 代数 2分 2分 2分 2分 2分 数据库设 计与管理 小计 10分

08年4月 年 月 08年9月 年 月 09年3月 年 月 09年9月 年 月 10年3月 年 月 2分 4分 4分 2分 10分 10分 10分 10分 第85页

第四章 数据库设计基础

数据：实际上就是描述事物的符号记录。 数据：实际上就是描述事物的符号记录。 数据库：是数据的集合， 数据库：是数据的集合，具有统一的结构形式并存放 于统一的存储介质内，是多种应用数据的集成， 于统一的存储介质内，是多种应用数据的集成，并可 被

30

各个应用程序共享。 被各个应用程序共享。 数据库管理系统：一种系统软件， 数据库管理系统：一种系统软件，负责数据库中的数 据组织、数据操纵、数据维护、 据组织、数据操纵、数据维护、控制及保护和数据服 务等，是数据库的核心。 务等，是数据库的核心。 数据库系统：由数据库（数据）、数据库管理系统 数据库系统：由数据库（数据）、数据库管理系统 ）、 软件）、数据库管理员（人员）、硬件平台（ ）、数据库管理员 ）、硬件平台 （软件）、数据库管理员（人员）、硬件平台（硬 ）、软件平台 软件）五个部分构成的运行实体。 软件平台（ 件）、软件平台（软件）五个部分构成的运行实体。 数据库应用系统：由数据库系统、 数据库应用系统：由数据库系统、应用软件及应用界 面三者组成。 面三者组成。 第86页 数据库系统 第87页

常见的关系数据库管理系统 小型数据库：

Visual FoxPro （以后简称为VFP） Access (office套件中的一个) Paradox 大型数据库：

Oracle Informix SYBASE SQL server 等 88

1.数据库系统的基本概念 数据库系统的基本概念

数据库管理系统提供的数据语言： 数据库管理系统提供的数据语言： （1）数据定义语言 数据定义语言： 数据定义语言 负责数据的模式定义与数据的物理存取构建； （2）数据操纵语言 数据操纵语言： 数据操纵语言

负责数据的操纵，如查询与增、删、改等； （3）数据控制语言 负责数据完整性、安全性的定义与检查 3 数据控制语言 数据控制语言： 以及并发控制、故障恢复等。 数据库管理系统的发展

(1)文件系统阶段 提供了简单的数据共享与数据管理能力，但 文件系统阶段： 文件系统阶段

是它无法提供完整的、统一的、管理和数据共享的能力。

(2)层次数据库与网状数据库系统阶段 ：为统一与共享数据 层次数据库与网状数据库系统阶段

31

提供了有力支撑。

(3)关系数据库系统阶段 关系数据库系统阶段 第89页

1.数据库系统的基本概念 数据库系统的基本概念

关系数据库系统的基本特点： 关系数据库系统的基本特点： 数据的集成性 数据的高共享性与低冗余性 数据独立性（物理独立性与逻辑独立性） 数据独立性（物理独立性与逻辑独立性） 数据统一管理与控制。 数据统一管理与控制。 数据库存放数据是按数据所提供的数据模式存放的， 数据库存放数据是按数据所提供的数据模式存放的，具有集成 与共享的特点。 与共享的特点。 数据库系统的三级模式： 数据库系统的三级模式： （1）概念模式（2）外模式（3）内模式 ）概念模式（ ）外模式（ ） 数据库系统的两级映射： 数据库系统的两级映射： （1）概念模式到内模式的映射； ）概念模式到内模式的映射； （2）外模式到概念模式的映射。 ）外模式到概念模式的映射。 第90页

应用 外模式 (用户数据库 用户数据库) 用户数据库 应用 外模式 (用户数据库 用户数据库) 用户数据库 应用 外模式 (用户数据库 用户数据库) 用户数据库 外模式→概念模式映射 外模式 概念模式映射 概念模式 (概念数据库 概念数据库) 概念数据库 概念模式→内模式映射模式 概念模式 内模式映射模式 内模式 (物理数据库 物理数据库) 物理数据库 数据库 91

2. 数据模型

数据模型（ 数据模型（Data Model）是对客观事物及其 ） 关系的数据描述。 关系的数据描述。

数据库中的数据模型可以将复杂的现实世界要求反映 到计算机数据库中的物理世界。 到计算机数据库中的物理世界。 现实世界 信息世界 计算机世界

数据模型是数据特征的抽象， 数据模型是数据特征的抽象，从抽象层次上 数据特征的抽象 静态特征、 描述了系统的静态特征 动态行为和约束条件。 描述了系统的静态特征、动态行为和约束条件。 数据模型所描述的内容包含：数据结构、 数据模型所描述的内容包含：数据结构、数据 所描述的内容包含 操作和数据约束。 操作和数据约束。

32

92

2. 数据模型

E-R模型的基本概念 （1）实体 现实世界中的事物 实体：现实世界中的事物 实体 现实世界中的事物； （2）属性 事物的特性； 属性：事物的特性 属性 事物的特性； （3）联系 现实世界中事物间的关系。实体 联系：现实世界中事物间的关系 联系 现实世界中事物间的关系。 集的关系有一对一、一对多、多对多 一对一、 一对一 一对多、多对多的联系。

一个班级的学生，学生与学生之间是一对一的关系。 一个班级的学生，学生与学生之间是一对一的关系。 一对一的关系 在一所学校，一门课程与学生之间是一对多的关系。 在一所学校，一门课程与学生之间是一对多的关系。 一对多的关系 在一所学校，多门课程与多个学生之间是多对多 多对多的 在一所学校，多门课程与多个学生之间是多对多的 关系。 关系。 第93页

E-R模型的图示法

用简单的几何图形表示实体集、属性与联系。 用简单的几何图形表示实体集、属性与联系。 (1)实体集表示法 实体集表示法 图中用矩形表表示实体集， 在E-R图中用矩形表表示实体集，在矩形内写上 图中用矩形表表示实体集 实体集名称。如实体集学生(student)、实体集课程 实体集名称。如实体集学生 、 (course) student course (2)属性表示法 属性表示法 图中用椭圆形表示属性， 在E-R图中用椭圆形表示属性，在椭圆形内写上 图中用椭圆形表示属性 该属性名称。如学生有属性：学号(S#)、姓名 该属性名称。如学生有属性：学号 、姓名(Sn)及 及 年龄(Sa)可用如下表示。 可用如下表示。 年龄 可用如下表示 S# Sn Sa 94

(3)联系表示法

图中用菱形(内写上联系名 表示联系。 在E-R图中用菱形 内写上联系名 表示联系。如 图中用菱形 内写上联系名)表示联系 学生与课程的联系SC,如下图所示： 如下图所示： 学生与课程的联系 如下图所示 SC

(4)实体集与属性间的联系关系 实体集与属性间的联系关系 属性依附于实体集，它们之间有联系关系用无 属性依附于实体集， 向线段表示。 向线段表示。 student S# Sn Sa 95

33

属性也依附于联系，它们之间也有联系关系， 属性也依附于联系，它们之间也有联系关系，因此也可 用无向线段，如联系SC可与学生的课程成绩属性 可与学生的课程成绩属性G建立联系 用无向线段，如联系 可与学生的课程成绩属性 建立联系 并用下图表示。 并用下图表示。 SC G (5)实体集与联系间的连接关系 也可用无向线段 实体集与联系间的连接关系(也可用无向线段 实体集与联系间的连接关系 也可用无向线段) student SC course 96

E-R模型之间的联接关系： 模型之间的联接关系： 模型之间的联接关系

实体是概念世界中的基本单位， 实体是概念世界中的基本单位， 是概念世界中的基本单位 属性有属性域， 属性有属性域，每个实体可取属性域内 有属性域 的值。 的值。 一个实体的所有属性值叫元组。 一个实体的所有属性值叫元组。 E-R模型的图示法： 模型的图示法： 模型的图示法 （1）实体集表示法；用长方形 ）实体集表示法； （2）属性表法；用椭圆形 ）属性表法； （3）联系表示法。用菱形，(m:n) ）联系表示法。 第97页

层次模型（采用树型结构） 层次模型 图1-4 层次模型示例 第98页

网络模型（采用无向图型结构） 第99页

关系模型（采用二维表结构） 关系模型 第100页 关系数据模型

关系模型采用二维表来表示，简称表， 关系模型采用二维表来表示，简称表，由表框架 及表的元组组成。一个二维表就是一个关系。 及表的元组组成。一个二维表就是一个关系。 关系数据库系统的特点之一是它建立在数据理论 的基础之上， 的基础之上，有很多数据理论可以表示关系模型 的数据操作， 的数据操作，其中最为著名的是关系代数与关系 演算。 演算。

学号 04001001 04001002 04001057 04002023 姓名 尚杰 余习芳 张轶一 陶红莉 性别

34

男 女 男 女 出生日期 86-11-20 86-12-26 86-01-09 85-02-14 入学成绩 520.5 513.5 612.0 535.0 四级通过否 T F T F 二级 计算机等级考试 一级 二级 备注 第101页

1.关系的数据结构 关系的数据结构

二维表由表框架与表元组组成。 二维表由表框架与表元组组成。 表框架由n个命名的属性组成 称为属性元素)。 个命名的属性组成(n称为属性元素 表框架由 个命名的属性组成 称为属性元素 。 每个属性有一个取值范围称为值域。 每个属性有一个取值范围称为值域。 表框架对应了关系的模式，即类型的概念。 表框架对应了关系的模式，即类型的概念。 每行数据称为元组，一个元组由n个元组分量所组 每行数据称为元组，一个元组由 个元组分量所组 每个元组分量是表结构中每个属性的投影值。 成，每个元组分量是表结构中每个属性的投影值。

学号 姓名 性别 男 女 男 女 出生日期 86-11-20 86-12-26 86-01-09 85-02-14 入学成绩 520.5 513.5 612.0 535.0 四级通过否 T F T F 二级 102

计算机等级考试 一级 二级 备注

04001001 尚杰 04001002 余习芳 04001057 张轶一 04002023 陶红莉

一个二维表要满足下面7个性质就可称为一个关系。 一个二维表要满足下面 个性质就可称为一个关系。 个性质就可称为一个关系

①二维表中元组个数是有限的 ②二维表中元组均不相同 ③二维表中元组的次序可任意交换 ④二维表中元组的分量是不可分割的基本数据项 ⑤二维表中属性名各不相同 二维表中属性与次序无关， ⑥二维表中属性与次序无关，可任意交换 ⑦二维表属性中的分量具有与该属性相同的值域 二维表 二维表框架 行 列 关系模型 关系模式 元组 元组分量 属性 属性值域 VFP表文件 VFP表文件 数据表结构 记录 数据项 字段 字段值域

惟一标识元组的最小属性集称为该表的键(或码 ， 惟一标识元组的最小属性集称为该表的键 或码)，在VFP 或码 表中称为主关键字 103 关系操作

关系模型的基本运算： 关系模型的基本运算： 1. 数据查询

35

查询关系数据库中的数据， 查询关系数据库中的数据，一个关系内的查 询以及多个关系间的查询。 询以及多个关系间的查询。

查询的基本单位为元组分量，先定位后操作。 查询的基本单位为元组分量，先定位后操作。 纵向定位（列指定） 横向定位（行选择） 纵向定位（列指定） 横向定位（行选择） 2. 数据插入 3. 数据删除 4. 数据修改 改后的元组

插入一个元组（不定位） 插入一个元组（不定位） 删除一个元组（定位、操作） 删除一个元组（定位、操作） 删除需修改的元组再插入修 104 3.关系代数

关系模型的基本运算： 关系模型的基本运算： 1. 插入 2. 删除 3. 修改 4. 查询

集合的并 集合的并运算 集合的差 交 集合的差(交) 运算 集合的差 并 除 运算 运算。 集合的差|并(除)运算。

投影、选择、 （投影、选择、笛卡尔积运算） 集合的并 集合的并运算 105

由关系R和 通过 运算得到关系T， 由关系 和S通过交运算得到关系 ， 106 3.关系代数

用于查询的集合运算： （1）投影 ）

对于关系R内的域指定称为投影运算。 对于关系 内的域指定称为投影运算。 内的域指定称为投影运算 S关系就是对 关系指定 和B两个域的结果 关系就是对R关系指定 关系就是对 关系指定A和 两个域的结果 R A a b c B 3 0 2 C 2 1 1 S

A a b c B 3 0 2 107 关系代数

36

（2）选择 ）

选择运算的关系是由关系R中那些满足逻辑条件的元组所组成。 选择运算的关系是由关系 中那些满足逻辑条件的元组所组成。 中那些满足逻辑条件的元组所组成 S关系就是 关系中满足 关系就是R关系中满足 关系就是 关系中满足A=?a?的结果 的结果 R

A a b a c B 3 0 6 2 C 2 1 9 1 A a a S B 3 6 C 2 9

有了投影和选择运算， 有了投影和选择运算，我们对一个关系内的任意 列的数据都可以方便的找到。 行、列的数据都可以方便的找到。 108 （3）笛卡尔积运算 ）

笛卡尔积是对两个关系的合并操作。 笛卡尔积是对两个关系的合并操作。 有三个关系R、S和T

R关系 关系 S关系 关系 T关系 关系 n1行, m1列 行 列 n2行， m2列 行 列 行数= 行数 n1*n2 列数= m1+m2 列数 R A m n S B C 1 3 A m n T B 1 1 C 3 3 109

（4）自然连接运算 ）

笛卡尔积建立两个关系的连接，但得到的关系庞大且数据 大量冗余。在实际应用中一般相互连接的关系往往须满足一 些条件，所得到的结果也较为简单。

自然连接满足两个关系中有公共域 ?自然连接满足两个关系中有公共域，通过公 自然连接满足两个关系中有公共域， 共域的相等值进行连接。 共域的相等值进行连接。 有三个关系R、S和T

R关系 n1行, m1列 关系 行 列 S关系 n2行， m2列 关系 行 列 T关系 行数≤(n1或n2中行数多的一个) 关系 列数≤m1+m2 110

有三个关系R、S和T，由关系 和S通过运算得到 由关系R和 通过运算得到 由关系 关系T， 关系 ，则使用的运算为 T R A B k1 f1 k2 r1 S B C f1 3 r1 3 笛卡尔积 A k1 k1 k2 k2

37

自然连接 B f1 f1 r1 r1 T A B C k1 f1 3 k2 r1 3 B f1 r1 f1 r1 C 3 3 3 3 R A B k1 f1 k2 r1 S B C f1 3 r1 3 111

在三个关系R 如下： 在三个关系 ， S和T如下： 和 如下 R A B m 1 n 2 S B C 1 3 3 5 A m T B 1 C 3

由关系R和S通过自然连接运算得到关系T。 112

数据库设计与管理

数据库设计的两种方法： 数据库设计的两种方法： （1）面向数据：以信息需求为主，兼顾处理需求； （2）面向过程：以处理需求为主，兼顾信息需求。 数据库的生命周期： 数据库的生命周期 需求分析阶段 结构析方法和面向对象的方法

数据字典是各类数据描述的集合，包括5个部分：数据项、数 个部分： 数据字典是各类数据描述的集合，包括 个部分 数据项、 据结构、数据流、数据存储、处理过程。 据结构、数据流、数据存储、处理过程。 概念设计阶段 分析数据内在语义关系。E-R模型 逻辑设计阶段 物理设计阶段 编码阶段 测试阶段 运行阶段 进一步修改阶段 第113页 4.4 数据库设计与管理

数据库应用系统(DBAS)中,核心问题是数据库 中 核心问题是数据库 数据库应用系统 设计。 设计。 分析客户的业务和数据处理需求; 分析客户的业务和数据处理需求 需求分析 重 设计数据库的E-R模型图，确认需 模型图， 设计数据库的 模型图 求信息的正确和完整; 求信息的正确和完整 概念设计 点 记 图转换为多张表， 将E-R图转换为多张表，进行逻辑 图转换为多张表 个 逻辑设计 设计,并应用数据库设计的三大范式 设计 并应用数据库设计的三大范式 阶 核; 进行 核 段 数据库 模式 理设计 8 和 。 并

数据库进行 理 应用; 应用 ， 行 进 114

38

数据库管理的内容

（1）数据库的建立； ）数据库的建立； （2）数据库的调整； ）数据库的调整； （3）数据库的重组； ）数据库的重组； （4）数据库安全性与完整性控制； ）数据库安全性与完整性控制； （5）数据库的故障恢复； ）数据库的故障恢复； （6）数据库监控。 ）数据库监控。 第115页

06年9月全国计算机等级考试二级笔试试卷 年 月全国计算机等级考试二级笔试试卷 一、单选题 4)在数据库系统中,用户所见的数据模式为 A)概念模式 √B)外模式 C)内模式 D)物理模式 5)数据库设计的四个阶段是:需求分析、概 念设计、逻辑设计和 A)编码设计 B)测试阶段 C)运行阶段 D)物理设计 √ D4 D5 116

6）设有如下三个表 ） R A m n S B C 1 3 A m n B) T=R∪S ∪ B)交 交 T B 1 1 C 3 3 下列操作中正确的是 A) T=R∩S A) 并 C)T=R×S × √ C) 笛卡尔积 D)=R/S D)除 除 D6 117

9)数据库技术的根本目标是要解决数据的 A)存储问题 √B)共享问题 C)安全问题 D)保护文题 二、填空题 3)一个关系表的行称为 【3】 元组 D9 T3 118

07年4月全国计算机等级考试二级笔试试卷 年 月全国计算机等级考试二级笔试试卷 一、单选题 8）在下列关系运算中，不改变关系表中的属性 ）在下列关系运算中， 个数但能减少元组个数为 A）并 B）交 √ ） ） C）投影 D）笛卡儿乘积 ） ） 9）在E-R图中，用来表示实体之间联系的图形是 ） 图中， 图中 A）矩形 B）椭圆形 ） ） C）菱形 √ D）平行四边形 ） ） D8 D9 119

39

10）下列叙述中错误的是 ） √ A）在数据库系统中，数据的物理结构必 ）在数据库系统中， 须与逻辑结构一致 B）数据库技术的根本目标是要解决数据 ） 的共享问题 C）数据库设计是指在已有数据库管理系 ） 统的基础上建立数据库 D10 D）数据库系统需要操作系统的支持 ） 二、填空题 T3

3）在数据库系统中实现各种数据管理功能 的核心软件称为 【3】 。 】 120 数据库管理系统或DBMS 数据库管理系统或

07年9月全国计算机等级考试二级笔试试卷 年 月全国计算机等级考试二级笔试试卷 一、单选题 9)下列叙述中正确的是 下列叙述中正确的是

A)数据库系统是一个独立的系统，不需要操作 系统的支持 √B)数据库技术的根本目标是要解决数据的共享 问题 C)数据库管理系统就是数据库系统 D)以上三种说法都不对 D9 121

10)下列叙述中正确的是 下列叙述中正确的是

A)为了建立一个关系，首先要构造数据的逻辑 关系 B)表示关系的二维表中各元组的每一个分量还 可以分成若干数据项 √C)一个关系的属性名表称为关系模式 D)一个关系可以包括多个二维表 D)

二、填空题 5)在E-R图中，矩形表示 实体集 图中， [5] 在 图中 D10 。 T5 122

08年4月 全国计算机等级考试二级笔试试卷 年 月

一、单选题 8)在数据库设计中，将E-R图转换成关系 在数据库设计中， 在数据库设计中 图转换成关系 数据模型的过程属于 A)需求分析阶段 B)概念设计阶段 C)逻辑设计阶段 √ D)物理设计阶段 D8 123

(9)有三个关系 、S和T如下： 有三个关系R、 和 如下 如下： 有三个关系 由关系R和 通过运算得到关系 通过运算得到关系T， 由关系 和S通过运算得到关

40

本文来源：https://www.bwwdw.com/article/u99g.html