全国计算机二级公共基础知识要点

《全国计算机二级公共基础知识要点》由会员分享，可在线阅读，更多相关《全国计算机二级公共基础知识要点（135页珍藏版）》请在金锄头文库上搜索。

1、全国计算机等级考试全国计算机等级考试 二级公共基础知识二级公共基础知识基本要求基本要求 n1. 掌握算法的基本概念。掌握算法的基本概念。n2. 掌握基本掌握基本数据结构数据结构及其操作。及其操作。n3. 掌握基本排序和查找算法。掌握基本排序和查找算法。n4. 掌握逐步求精的结构化掌握逐步求精的结构化程序设计程序设计方法。方法。n5. 掌握掌握软件工程软件工程的基本方法，具有初步应的基本方法，具有初步应用相关技术进行软件开发的能力。用相关技术进行软件开发的能力。n6. 掌握掌握数据库数据库的基本知识，了解关系数据的基本知识，了解关系数据库的设计。库的设计。 一、 基本数据结构与算法 1. 算法的

2、基本概念；算法复杂度的概念和意义（时间复杂度算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。的图形表示；线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结构及其插入与删除运线性表的定义；线性表的顺序存储结构及其插入与删除运算。算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环链表的结构及其基本运算。线性单链

3、表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。序、中序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。选择类排序，插入类排序）。 二、 程序设计基础1. 程序设计方法与风格。程序设计方法与风格。2. 结构化程序设计。结构化程序设计。3. 面向对象的程序设计方法，对象，方面向对象的程序设计方法，对象，方法，属性及继承与多态性。法，属性及继承与多态性。 三、 软件工程基础1. 软

4、件工程基本概念，软件生命周期概念，软软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。件工具与软件开发环境。2. 结构化分析方法，数据流图，数据字典，软结构化分析方法，数据流图，数据字典，软件需求规格说明书。件需求规格说明书。3. 结构化设计方法，总体设计与详细设计。结构化设计方法，总体设计与详细设计。4. 软件测试的方法，白盒测试与黑盒测试，测软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、试用例设计，软件测试的实施，单元测试、集成测试和系统测试。集成测试和系统测试。5. 程序的调试，静态调试与动态调试。程序的调试，静态调试与动态调试。四、数据库设计基础

5、1. 数据库的基本概念：数据库，数据库管理系数据库的基本概念：数据库，数据库管理系统，数据库系统。统，数据库系统。2. 数据模型，实体联系模型及数据模型，实体联系模型及E-R图，从图，从E-R图导出关系数据模型。图导出关系数据模型。3. 关系代数运算，包括集合运算及选择、投影、关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。连接运算，数据库规范化理论。4. 数据库设计方法和步骤：需求分析、概念设数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。计、逻辑设计和物理设计的相关策略。考试方式1、 公共基础的考试方式为笔试，与公共基础的考试方式为笔试，与C语言

6、语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C+）的笔试部分合为一）的笔试部分合为一张试卷。公共基础部分占全卷的张试卷。公共基础部分占全卷的30分。分。2、 公共基础知识有公共基础知识有10道选择题和道选择题和5道填空题。道填空题。 学习方法n理解基本概念理解基本概念n多做练习多做练习n适当记忆一些名词适当记忆一些名词n与所学的与所学的VFPcAccess程序设计知识程序设计知识结合起来，以增加对知识的理解能力结合起来，以增加对知识的理解能力91. 基本数据结构与算法10算法的基本特征算法的基本特征:(1)可行性可行性(2)确定性确定性(3)

7、有穷性有穷性(4)输入和输出输入和输出（拥有足够的情报）（拥有足够的情报）1.1 算法111.2 算法复杂度算法复杂度1.2.1 时间复杂度时间复杂度n是指执行算法所需要的计算工作量。是指执行算法所需要的计算工作量。n通常有事后统计法和通常有事后统计法和事前分析估算法事前分析估算法。算法在执行过程中所需算法在执行过程中所需基本运算基本运算的执行次数来度量算法的执行次数来度量算法的工作量的工作量.算法所执行的基本运算次数与算法所执行的基本运算次数与问题的规模问题的规模n有关有关.执行算法所需要的计算工作量和执行算法所需要的计算工作量和f(n)同步增长，记为同步增长，记为:算法的工作量算法的工作量

8、=f(n)时间复杂度时间复杂度=O(f(n)121.2.2 算法的空间复杂度算法的空间复杂度n 一般是指执行这个算法所需要的内存空间一般是指执行这个算法所需要的内存空间n一个算法所占用的存储空间包括一个算法所占用的存储空间包括算法程序算法程序所占所占的空间、的空间、输入的初始数据输入的初始数据所占的存储空间以及所占的存储空间以及某种某种数据结构数据结构所需要的附加存储空间所需要的附加存储空间n 一个上机执行的程序除了需要存储空间来寄存一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一需

9、要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。些为实现计算所需信息的辅助空间。13n 算法的时间复杂度是指算法的时间复杂度是指A) 执行算法程序所需要的时间执行算法程序所需要的时间 B) 算法程序的长度算法程序的长度C) 算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数算法程序中的指令条数n算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。和拥有足够的情报。n算法的空间复杂度是指算法的空间复杂度是指 A) 算法程序的长度算法程序的长度 B) 算法程序中的指令条数算法程序中的指令条数

10、 C) 算法程序所占的存储空间算法程序所占的存储空间 D) 执行过程中所需要的存储空间执行过程中所需要的存储空间n在计算机中，算法是指在计算机中，算法是指 A) 加工方法加工方法B) 解题方案的准确而完整的描述解题方案的准确而完整的描述 C) 排序方法排序方法D) 查询方法查询方法例题讲解例题讲解有穷性有穷性14n算法分析的目的是算法分析的目的是 A) 找出数据结构的合理性找出数据结构的合理性 B) 找出算法中输入和输出之间的关系找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性分析算法的易懂性和可靠性 D) 分析算法的效率以求改进分析算法的效率以求改进n算法的工作量大小和实现算法

11、所需的存储单元多少分别称为算法算法的工作量大小和实现算法所需的存储单元多少分别称为算法的的 【1】 。时间复杂度和空间复杂度时间复杂度和空间复杂度151.2 数据结构数据结构n数据结构的定义数据结构的定义n数据的逻辑结构和存储结构数据的逻辑结构和存储结构n数据结构的图形表示数据结构的图形表示n线性结构与非线性结构线性结构与非线性结构161.2.1 数据结构研究的主要内容数据结构研究的主要内容(1)数据集中数据之间的逻辑关系数据集中数据之间的逻辑关系线性线性树树图图(2)数据的存储结构数据的存储结构(3)各种数据结构的运算各种数据结构的运算17（1 1）数据元素）数据元素(Data Elemen

12、t)(Data Element) 数据元素是数据的基本单位，即数据数据元素是数据的基本单位，即数据集合中的个体。集合中的个体。 有时一个数据元数可由若干有时一个数据元数可由若干数据项数据项(Data Item)(Data Item)组成。数据项是数据的最小组成。数据项是数据的最小单位。单位。数据元素亦称数据元素亦称节点节点或或记录记录。18 1数据的逻辑结构数据的逻辑结构 2、数据的存储结构、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、插入、删除、修改等。 A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储 线性表

13、线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面 19A.线性结构线性结构 (A , B , C , ，X ,Y , Z)例例:学生成绩表学生成绩表8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓98611099861109成绩成绩姓名姓名学号学号线性表线性表栈栈后进先出后进先出队列队列先进先出先进先出例例: :英文字母表英文字母表20树形结构树形结构例例:全校学生档案管理的组织方式全校学生档案管理的组织方式例例:计算机文件管理系统也是典型的树形结构计算机文件管理系统也是典型的树形结构B非线性

14、结构非线性结构211423 例例:数据结构数据结构B(D,R) D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3), (3,4) , (2,4) 213例例:数据结构数据结构C(D,R)D= 1 , 2 , 3 R= , , , 图形结构图形结构22元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(ai)=Lo+（i-1)*m1、顺序存储、顺序存储每个元素所占用每个元素所占用的存储单元个数的存储单元个数（3）存储结构）存储结构23例：线性表例：线性

15、表(zhao,qian,sun,li,zhou,wu,zheng,wang) 顺序存储结构：顺序存储结构：存储地址存储地址数据数据7891011121314zhaoqiansunlizhouwuzhengwang7基地址基地址顺序存储结构，将逻辑上相邻的顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存数据元素存储在物理上相邻的存储单元里储单元里,具有以下特点具有以下特点:1.随机存取。随机存取。2.作插入或删除操作时，需移动作插入或删除操作时，需移动大量元数。大量元数。3.长度变化较大时，需按最大空长度变化较大时，需按最大空间分配。间分配。4.表的容量难以扩充。表的容量难以扩充。24

16、2、链式存储、链式存储 每个节点都由两部分组成：每个节点都由两部分组成： 数据域数据域和和指针域指针域。数据域数据域存放元素本身的数据，存放元素本身的数据，指针域指针域存放指针。存放指针。数据元素之间逻辑上的联系由数据元素之间逻辑上的联系由指针来体现。指针来体现。例：线性表例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang)链式存储结构：链式存储结构：存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针25通常我们把链表画成用通常我们把链表画成用箭头箭

17、头相链接的结点的序列，结点相链接的结点的序列，结点之间的箭头表示链域中的指针。之间的箭头表示链域中的指针。zhaoqiansunlizhouwuzhengwang /H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针261.比顺序存储结构多用空间比顺序存储结构多用空间(存储密度小存储密度小) (每个节点都由数据域和指针每个节点都由数据域和指针域域组成组成)。2.逻辑上相邻的节点物理上不必相邻。逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活插入、删除灵活 (不必移动节点，只要改

18、变节点中的指针不必移动节点，只要改变节点中的指针)。4.非随机存取。非随机存取。链接存储结构特点：链接存储结构特点：27n链表不具有的特点是链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比n数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1】 。 n数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的 A) 存储结构存储结构B) 物理结构物理结构 C)

19、逻辑结构逻辑结构D) 物理和存储结构物理和存储结构 n数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【1】 两大类。两大类。n数据的存储结构是指数据的存储结构是指A）数据所占的存储空间）数据所占的存储空间B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据 例题讲解例题讲解存储结构存储结构 非线性结构非线性结构28n顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元中。的存储单元中。 n数据处理的最小单位是数

20、据处理的最小单位是 A) 数据数据 B) 数据元素数据元素 C) 数据项数据项 D) 数据结构数据结构n数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及 A) 数据的存储结构数据的存储结构 B) 计算方法计算方法 C) 数据映象数据映象 D) 逻辑存储逻辑存储n线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的

21、存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 相邻相邻29n根据数据结构中各数据元素之间前后件关系的复杂程度，一根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成般将数据结构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构 n数据结构包括数据的逻辑结构、数据的数据结构包括

22、数据的逻辑结构、数据的 【2】 以及对数据以及对数据的操作运算。的操作运算。n数据的基本单位是数据的基本单位是 【5】 。n下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构存储结构存储结构数据元素数据元素301.7 栈和队列栈和队列1.7.1 栈和队列的定义栈和队

23、列的定义 栈和队列栈和队列是两种特殊的线性表，它们是运算时是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为要受到某些限制的线性表，故也称为限定性的数据限定性的数据结构结构。311 .栈栈栈栈是限定仅在表尾进行插入或删除操作的线性表。是限定仅在表尾进行插入或删除操作的线性表。栈顶栈顶表尾。表尾。栈底栈底表头。表头。空栈空栈不含元素的空表。不含元素的空表。a1a2an栈底栈底栈顶栈顶进栈进栈出栈出栈栈栈s=(a1,a2,an)后进先出后进先出（LIFO）323. 队列队列定义：一种特殊的线性结构，限定只能在表的一端进行插入，在定义：一种特殊的线性结构，限定只能在表的一端进行插入，在

24、 表的另一端进行删除的线性表表的另一端进行删除的线性表 。此种结构称为。此种结构称为先进先出（先进先出（FIFO）表表。 a1 , a2 , a3 , a4 , an-1 , an 队队 列列 示示 意意 图图队队头头队队尾尾33n栈和队列的共同特点是栈和队列的共同特点是 A)都是先进先出都是先进先出 B) 都是先进后出都是先进后出 C) 只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D) 没有共同点没有共同点n如果进栈序列为如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是，则可能的出栈序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e

25、1,e2D) 任意顺序任意顺序n一些重要的程序语言一些重要的程序语言(如如C语言和语言和Pascal语言语言) 允许过允许过程的递归调用。而实现递归调用中的存储分配通常用程的递归调用。而实现递归调用中的存储分配通常用 A) 栈栈B) 堆堆 C) 数组数组 D) 链表链表例题讲解例题讲解34n栈底至栈顶依次存放元素栈底至栈顶依次存放元素A、B、C、D，在第五个元素，在第五个元素E入栈前，入栈前，栈中元素可以出栈，则出栈序列可能是栈中元素可以出栈，则出栈序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE n栈通常采用的两种存储结构是栈通常采用的两种存储结构是 A)

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

27、算。这种情况称为 【2】 。链表存储结构和数组链表存储结构和数组上溢上溢35n由两个栈共享一个存储空间的好处是由两个栈共享一个存储空间的好处是A) 减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 B) 节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率C) 减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 D) 节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率n下列关于栈的叙述中正确的是下列关于栈的叙述中正确的是）在栈中只能插入数据）在栈中只能插入数据 B）在栈中只能删除数据）在栈中只能删除数据C）栈是先进先出的线性表）栈是先进先

28、出的线性表 D）栈是后进先出的线性表）栈是后进先出的线性表n下列关于队列的叙述中正确的是下列关于队列的叙述中正确的是）在队列中只能插入数据）在队列中只能插入数据 B）在队列中只能删除数据）在队列中只能删除数据C）队列是先进先出的线性表）队列是先进先出的线性表 D）队列是后进先出的线性表）队列是后进先出的线性表361.6.1 树的定义树的定义 由一个或多个结点组成的有限集合由一个或多个结点组成的有限集合。仅有一个根结点，结仅有一个根结点，结点间有明显的层次结构关系。点间有明显的层次结构关系。 A C G T2D H I T3J M B E L KT1 F现实世界中，能用树的结构表示的例子：现实世

29、界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。学校的行政关系、书的层次结构、人类的家族血缘关系等。1.6 树37介绍几个概念：介绍几个概念：结结点点（Node）：树树中中的的元元素素，包包含含数数据据项项及及若若干干指指向向其其子树的分支。子树的分支。结点的度结点的度（Degree）：结点拥有的子树数。）：结点拥有的子树数。结点的层次：结点的层次：从根结点开始算起，根为第一层。从根结点开始算起，根为第一层。叶子叶子（Leaf）：度为零的结点，也称端结点。）：度为零的结点，也称端结点。孩子孩子（Child）：结点子树的根称为该结点的孩子结点。）：结点子树的根称

30、为该结点的孩子结点。兄弟兄弟（Sibling）：）：同一双亲的孩子。同一双亲的孩子。双双亲亲（Parent）：孩孩子子结结点点的的上上层层结结点点，称称为为这这些些结结点点的的 双亲。双亲。树的深度树的深度（Depth)： 树中结点的最大层次数。树中结点的最大层次数。树的度：树的度：结点所具有的最大的度结点所具有的最大的度.森林森林（Forest）：）：M棵互不相交的树的集合。棵互不相交的树的集合。 A C GD H I J M B E L KT1 F381.6.2 二叉树二叉树 （Binary Tree）1 、二叉树的定义及其性质、二叉树的定义及其性质 (1) 二叉树的定义二叉树的定义二叉树

31、的五种基本形态二叉树的五种基本形态 二二叉叉树树一一种种特特殊殊的的树树形形结结构构，特特点点是是树树中中每每个个结结点点最最多多只只能能有有两两棵棵子子树树(即即二二叉叉树树中中不不存存在在度度大大于于2的的结结点点)，且且子子树树有有左左右右之分，次序不能颠倒。之分，次序不能颠倒。 空二叉树空二叉树 仅有仅有根结点根结点 右子树右子树为空为空 左子树左子树为空为空左右子树左右子树均非空均非空39性质性质1:二叉树的第二叉树的第i层上至多有层上至多有2 i-1（i 1）个结点。）个结点。(2) 二叉树的基本性质二叉树的基本性质423167891011121314155第三层上第三层上(i=3

32、)(i=3)，有，有2 23-13-1=4=4个节点。个节点。第四层上第四层上(i=4)(i=4)，有，有2 24-14-1=8=8个节点。个节点。性质性质2: 深度为深度为k的二叉树中至多含有的二叉树中至多含有2k-1个结点。个结点。40性质：对任何一棵二叉树性质：对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0,度度 为为2的结点数为的结点数为n2,则则n0=n2+1。证明：证明： 设设n1为二叉树为二叉树T中度为中度为1的结点数；的结点数； 二叉树中所有结点的度均小于或等于二叉树中所有结点的度均小于或等于2 其结点总数为：其结点总数为： n=n0+n1+n2 二叉树中除了根

33、结点外，其余结点都有一个分支进入二叉树中除了根结点外，其余结点都有一个分支进入 设分支总数为设分支总数为B； 则则 n=B+1; 二叉树的分支是由度为二叉树的分支是由度为1或或2的结点射出的的结点射出的 B=n1+2*n2 n=n1+2*n2+1=n0+n1+n2 n0=n2+1ABFCJM一般树一般树41满二叉树满二叉树423167891011121314155特点：每一层上都含有最特点：每一层上都含有最大结点数。大结点数。完全二叉树完全二叉树4231678910 11125特点：特点：(1)(1)除最后一层外，每一层都取最除最后一层外，每一层都取最 大结点数，大结点数，(2)(2)最后一层

34、结点都集中在该层最左最后一层结点都集中在该层最左边的若干位置。边的若干位置。42性质：具有性质：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为112345678910121例：例：n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=443性质：如果对一棵有性质：如果对一棵有n个结点的完全二叉树的结点按层个结点的完全二叉树的结点按层 序编号，则对任一结点序编号，则对任一结点i(1=i=n,则结点则结点i无左孩子无左孩子(结点结点i为叶子结点为叶子结点); 否则其左孩子否则其左孩子Lchild(i)是结点是结点2i。 (3)如果如果2i+1n,则结点则结点i无

35、右孩子无右孩子; 否则其右孩子否则其右孩子Rchild(i)是结点是结点2i+1。(1)如果如果i=1,则结点则结点i是二叉树的根是二叉树的根,无双亲无双亲; 如果如果i1,则双亲则双亲Parent(i)是结点是结点|i/2|。 44例：例：112345678910121i=6 其双亲为其双亲为|i/2|= 3；其左孩子为；其左孩子为2*i=12;i=1 是树的根是树的根,无双亲无双亲;其左孩子为其左孩子为2*i=2,右孩子为右孩子为2*i+1=3 .2*i=1812 2*i+1=1912 其无左、右孩子。其无左、右孩子。2*i+1=1312 其无右孩子。其无右孩子。i=9 其双亲为其双亲为|

36、i/2|= 4 ；451.6.3 二叉树的遍历二叉树的遍历 查查找找某某个个结结点点，或或对对二二叉叉树树中中全全部部结结点点进进行行某某种种处处理理，就就需需要要遍历。遍历。（1）遍历定义及遍历算法）遍历定义及遍历算法 遍遍历历是是指指按按某某条条搜搜索索路路线线寻寻访访树树中中每每个个结结点点，且且每每个个结结点点只只被被访访 问一次。问一次。 按先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：先序遍历先序遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历中序遍历(L D R): 按中序遍历左

37、子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。二叉树为空时，执行空操作，即空二叉树已遍历完。46 （2）遍历算法）遍历算法先序遍历：先序遍历：D L R中序遍历：中序遍历：L D R后序遍历：后序遍历：L R DADBCD L RAD L RD L RBDCD L R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCBDAC DBCA47n已知二叉树

38、后序遍历序列是已知二叉树后序遍历序列是dabec，中序遍历序列是，中序遍历序列是debac，它的前序遍历序列是它的前序遍历序列是 A) acbed B) decab C) deabc D) cedba n已知一棵二叉树前序遍历和中序遍历分别为已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和和DBGEACHF，则该二叉树的后序遍历为，则该二叉树的后序遍历为 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHGn树是结点的集合，它的根结点数目是树是结点的集合，它的根结点数目是 A) 有且只有有且只有1B) 1或多于或多于1 C) 0或或1D) 至少

39、至少2n下列叙述中正确的是下列叙述中正确的是 A) 线性表是线性结构线性表是线性结构B) 栈与队列是非线性结构栈与队列是非线性结构 C) 线性链表是非线性结构线性链表是非线性结构D) 二叉树是线性结构二叉树是线性结构例题讲解例题讲解48n在深度为在深度为5的满二叉树中，叶子结点的个数为的满二叉树中，叶子结点的个数为 A) 32B) 31 C) 16 D) 15 n若某二叉树的前序遍历访问顺序是若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺，中序遍历访问顺序是序是dgbaechf，则其后序遍历的结点访问顺序是，则其后序遍历的结点访问顺序是 A) bdgcefha B) gdbec

40、fha C) bdgaechf D) gdbehfcan在树结构中，树根结点没有在树结构中，树根结点没有 【1】 。n具有具有3个结点的二叉树有个结点的二叉树有 A) 2种形态种形态 B) 4种形态种形态 C) 7种形态种形态 D) 5种形态种形态n设一棵二叉树中有设一棵二叉树中有3个叶子结点，有个叶子结点，有8个度为个度为1的结点，则该二的结点，则该二叉树中总的结点数为叉树中总的结点数为 A) 12 B) 13 C) 14D) 15 双亲结点双亲结点49n设有下列二叉树：设有下列二叉树： 对此二叉树前序遍历的结果为对此二叉树前序遍历的结果为A) ZBTTCPXA B) ATBZXCTP C)

41、 ZBTACTXP D) ATBZXCPTn设有下列二叉树：设有下列二叉树：对此二叉树的中序遍历的结果为对此二叉树的中序遍历的结果为A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA50n设树设树T的度为的度为4,其中度为其中度为1、2、3、4的结点的结点个数分别为个数分别为4、2、1、1。则。则T中的叶子结点中的叶子结点数为数为A）8 B）7 C）6 D）5n设一棵完全二叉树共有设一棵完全二叉树共有700个结点，则该二个结点，则该二叉树中有（叉树中有（ ）个叶子结点。）个叶子结点。 n在一个容量为在一个容量为15的循环队列中，若头指针的循环队列中，若头指针fron

42、t=6，尾指针，尾指针rear=9，则该循环队列中，则该循环队列中共有（共有（ ）个元素。）个元素。n设一棵二叉树的中序遍历结果为设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为前序遍历结果为ABDECF，则后序遍历结果，则后序遍历结果为（为（ ）。）。3503DEBFCA511.7 查找和排序n顺序查找与二分查找算法顺序查找与二分查找算法n基本排序算法（交换类排序、选择类排基本排序算法（交换类排序、选择类排序、插入类排序）序、插入类排序）521.7.1 顺序查找（线性查找）顺序查找（线性查找）查找过程：查找过程： 对给定的一关键字对给定的一关键字K，从线性表的一端开始，逐，从线性表的

43、一端开始，逐个进行记录的关键字和个进行记录的关键字和K的比较，直到找到关键字等的比较，直到找到关键字等于于K的记录或到达表的另一端。的记录或到达表的另一端。可以采用从前向后查，也可采用从后向前查的方法。可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。较，效率较低。平均查找长度较大。 最好情况：最好情况：1 最坏情况：最坏情况：n在下面两种情况下只能采取顺序查找：在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）；线性表为无序表（元素排列是无序的）； b

44、. 即使是有序线性表，但采用的是链式存储结构。即使是有序线性表，但采用的是链式存储结构。531.7.1 折半查找（二分法查找）折半查找（二分法查找）n思想：先确定待查找记录所在的范围，然后逐步缩小思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。范围，直到找到或确认找不到该记录为止。 n前提：必须在前提：必须在具有顺序存储结构的具有顺序存储结构的有序表中进行有序表中进行。n分三种情况：分三种情况： 1）若中间项的值等于）若中间项的值等于x,则说明已查到。则说明已查到。 2）若）若x小于中间项的值小于中间项的值,则在线性表的前半部分查找；则在线性表的前半部分查找

45、； 3）若）若x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。n特点：比顺序查找方法效率高。最坏的情况下，需要特点：比顺序查找方法效率高。最坏的情况下，需要比较比较 log2n次次。54排序方法排序方法插入排序插入排序选择排序选择排序交换排序交换排序归并排序归并排序简单插入排序简单插入排序希尔排序希尔排序简单选择排序简单选择排序堆排序堆排序起泡排序起泡排序快速排序快速排序1.7.2 排序排序55n在长度为在长度为n的有序线性表中进行二分查找。最的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为坏的情况下，需要的比较次数为 【2】 。n假设线性表的长

46、度为假设线性表的长度为n，则在最坏情况下，冒，则在最坏情况下，冒泡排序需要的比较次数为泡排序需要的比较次数为 A) log2n B) n2 C) O(n1.5) D) n(n-1)/2例题讲解例题讲解log2n冒泡排序算法在最好的情况下的元素交换次数为冒泡排序算法在最好的情况下的元素交换次数为 【1】 。 在最坏情况下，堆排序需要比较的次数为在最坏情况下，堆排序需要比较的次数为 【2】 。 排序是计算机程序设计中的一种重要操作，常见的排序排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、方法有插入排序、 【1】 和选择排序等。和选择排序等。0nlog2n交换排序交换排序562.程

47、序设计基础572.1 程序设计方法与风格2.1.1 程序设计方法程序设计方法n结构化设计方法结构化设计方法n面向对象程序设计方法面向对象程序设计方法582.2 结构化程序设计结构化程序设计基本概念基本概念n三种基本结构三种基本结构n顺序结构顺序结构n选择结构选择结构n循环结构循环结构n三种基本结构的特点三种基本结构的特点n只有一个入口只有一个入口n只有一个出口只有一个出口n每一个基本结构中的每一部分都有机会执行到每一个基本结构中的每一部分都有机会执行到n结构内不存在结构内不存在“死循环死循环”设计原则设计原则n自顶向下（先总体，后细节）自顶向下（先总体，后细节）n逐步求精（设计子目标过渡）逐步

48、求精（设计子目标过渡）n模块化模块化 （分解总目标）（分解总目标）n限制使用限制使用goto语句语句59n对象对象(Object)n对象是基本的运行时认得实体，它既包括数据（属性）对象是基本的运行时认得实体，它既包括数据（属性），也包括作用于数据的操作（行为）。，也包括作用于数据的操作（行为）。n一个对象把属性和行为封装为一个整体一个对象把属性和行为封装为一个整体n一个对象通常可由对象名、属性和操作一个对象通常可由对象名、属性和操作3部分组成部分组成n对象的基本特性：对象的基本特性： （1）标识唯一性）标识唯一性 （对象可区分）（对象可区分） （2）分类性）分类性 （对象抽象成类）（对象抽象成

49、类） （3）多态性）多态性 （同一操作可以是不同对象的行为）（同一操作可以是不同对象的行为） （4）封装性）封装性 （只能看到对象的外部特性）（只能看到对象的外部特性） （5）模块独立性好）模块独立性好（对象内部各元素结合紧密、内聚性强）（对象内部各元素结合紧密、内聚性强）2.3 面向对象的程序设计方法面向对象的程序设计方法60n类类(Class)和实例和实例n一个类定义了一组大体上相似的对象。一个类定义了一组大体上相似的对象。n一个类所包含的方法和数据描述一组对象的共同行为一个类所包含的方法和数据描述一组对象的共同行为和属性。和属性。n类是在对象之上的抽象，对象是类的具体化，是类的类是在对象

50、之上的抽象，对象是类的具体化，是类的实例实例n封装封装(Encapsulation)n将数据和操作数据的函数衔接在一起，构成一个具有将数据和操作数据的函数衔接在一起，构成一个具有类类型的对象的描述。类类型的对象的描述。n对象的内部实现受保护，外界不能访问对象的内部实现受保护，外界不能访问n封装简化了程序员对对象的使用封装简化了程序员对对象的使用61n继承继承(Inheritance)n继承是父类和子类之间共享数据的方法的机制继承是父类和子类之间共享数据的方法的机制n一个子类可以继承它的父类（或祖先类）中的属一个子类可以继承它的父类（或祖先类）中的属性和操作性和操作n子类中可以定义自己的属性和操

51、作子类中可以定义自己的属性和操作n单重继承、多重继承单重继承、多重继承n多态性多态性(Polymorphism)n不同的对象收到同一消息可以产生完全不同的结不同的对象收到同一消息可以产生完全不同的结构，这一现象叫做多态性构，这一现象叫做多态性n多态的实现受到继承的支持多态的实现受到继承的支持n消息消息(Message)n 对象之间进行通信的一种构造对象之间进行通信的一种构造62n结构化结构化程序设计的程序设计的3种结构是种结构是 A) 顺序结构、选择结构、转移结构顺序结构、选择结构、转移结构 B) 分支结构、等价结构、循环结构分支结构、等价结构、循环结构 C) 多分支结构、赋值结构、等价结构多

52、分支结构、赋值结构、等价结构 D) 顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构n在设计程序在设计程序时，应采纳的原则之一是时，应采纳的原则之一是 A) 不限制不限制goto语句的使用语句的使用 B) 减少或取消注解行减少或取消注解行 C) 程序越短越好程序越短越好 D) 程序结构应有助于读者理解程序结构应有助于读者理解n程序设计程序设计语言的基本成分是数据成分、运算语言的基本成分是数据成分、运算成分、控制成分和成分、控制成分和 A) 对象成分对象成分B) 变量成分变量成分 C) 语句成分语句成分D) 传输成分传输成分例题讲解例题讲解63n结构化结构化程序设计主要强调的是程序设计主

53、要强调的是 A) 程序的规模程序的规模B) 程序的效率程序的效率 C) 程序设计语言的先进性程序设计语言的先进性 D) 程序易读性程序易读性n 以下不属于对象的基本特点的是以下不属于对象的基本特点的是 A) 分类性分类性 B) 多态性多态性 C) 继承性继承性D) 封装性封装性 n 对建立对建立良好的程序设计风格，下面描述正确的是良好的程序设计风格，下面描述正确的是 A) 程序应简单、清晰、可读性好程序应简单、清晰、可读性好 B) 符号名的命名只要符合语法符号名的命名只要符合语法 C) 充分考虑程序的执行效率充分考虑程序的执行效率 D) 程序的注释可有可无程序的注释可有可无n在结构化程序在结构

54、化程序设计思想提出之前，在程序设计中曾设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们强调程序的效率，现在，与程序的效率相比，人们更重视程序的更重视程序的 A) 安全性安全性B) 一致性一致性 C) 可理解性可理解性D) 合理性合理性64n程序的程序的3种基本控制结构是种基本控制结构是 A) 过程、子过程和分程序过程、子过程和分程序B) 顺序、选择和重复顺序、选择和重复 C) 递归、堆栈和队列递归、堆栈和队列 D) 调用、返回和转移调用、返回和转移n下列下列叙述中，不属于结构化程序设计方法的主叙述中，不属于结构化程序设计方法的主要原则的是要原则的是 A) 自顶向下自

55、顶向下 B) 由底向上由底向上 C) 模块化模块化D) 限制使用限制使用goto语句语句n 对象实现了数据和操作的结合，是指对数据对象实现了数据和操作的结合，是指对数据和数据的操作进行和数据的操作进行 A) 结合结合 B) 隐藏隐藏 C) 封装封装 D) 抽象抽象类是一个支持集成的抽象数据类型，而对象是类的类是一个支持集成的抽象数据类型，而对象是类的_。实例实例65n在面向对象方法中，一个对象请求另一个对象在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送为其服务的方式是通过发送A）调用语句）调用语句 B）命令）命令 C）口令）口令 D）消息）消息n信息屏蔽的概念与下述哪一种概念

56、直接相关信息屏蔽的概念与下述哪一种概念直接相关A）软件结构定义）软件结构定义 B）模块独立性）模块独立性C）模块类型划分）模块类型划分 D）模块偶合度）模块偶合度n下列对象概念描述错误的是下列对象概念描述错误的是A）任何对象都必须有继承性）任何对象都必须有继承性B）对象是属性和方法的封装体）对象是属性和方法的封装体C）对象间的通讯靠消息传递）对象间的通讯靠消息传递D）操作是对象的动态属性）操作是对象的动态属性66n下列叙述下列叙述中，不属于结构化分析方法的是中，不属于结构化分析方法的是 A) 面向数据流的结构化分析方法面向数据流的结构化分析方法 B) 面向数据结构的面向数据结构的Jackson

57、方法方法 C) 面向数据结构的结构化数据系统开发方法面向数据结构的结构化数据系统开发方法 D) 面向对象的分析方法面向对象的分析方法 n在面向对象的程序设计中，类描述的是具在面向对象的程序设计中，类描述的是具有相似性质的一组有相似性质的一组 【3】 n在面向对象方法中，类之间共享属性和操在面向对象方法中，类之间共享属性和操作的机制称为作的机制称为 【2】 。 n一个类可以从直接或间接的祖先中继承所一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件有属性和方法。采用这个方法提高了软件的的 【3】 。 对象的共同行为和属性对象的共同行为和属性继承继承可重用性可重用性67n面向

58、对象的模型中，最基本的概念是对象和面向对象的模型中，最基本的概念是对象和 【3】 。 n在面向对象的设计中，用来请求对象执行某在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为一处理或回答某些信息的要求称为 【4】 。 n在程序设计在程序设计阶段应该采取阶段应该采取 【2】 和逐步求精和逐步求精的方法，把一个模块的功能逐步分解，细化的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，进而用某种程序设计为一系列具体的步骤，进而用某种程序设计语言写成程序。语言写成程序。n在面向对象方法种，类之间共享属性和操作在面向对象方法种，类之间共享属性和操作的机制称为的机制称为_。消息

59、消息自顶向下自顶向下属性、行为属性、行为继承继承68n 【3】 是是一一种种信信息息隐隐蔽蔽技技术术，目目的的在在于于将对象的使用者和对象的设计者分开。将对象的使用者和对象的设计者分开。n可可以以把把具具有有相相同同属属性性的的一一些些不不同同对对象象归归类类，称为称为 【3】 。 n子子程程序序通通常常分分为为两两类类： 【2】 和和函函数数，前前者者是命令的抽象，后者是为了求值。是命令的抽象，后者是为了求值。n 源源程程序序文文档档化化要要求求程程序序应应加加注注释释。注注释释一一般般分为序言性注释和分为序言性注释和_。n在在面面向向对对象象方方法法种种，信信息息屏屏蔽蔽是是通通过过对对象

60、象的的_性来实现的。性来实现的。封装封装类类过程过程功能性注释功能性注释封装封装693.软件工程基础703.1 基本概念基本概念n软件软件程序程序数据数据相关文档相关文档机器可执行的程序和数据机器可执行的程序和数据机器不能执行的，与软件开发、运行、维护、使用等有关的文档机器不能执行的，与软件开发、运行、维护、使用等有关的文档71软件的特点包括：软件的特点包括：（1）软件是一种逻辑实体；）软件是一种逻辑实体；（2）软件的生产与硬件不同，它没有明显的制作过程；）软件的生产与硬件不同，它没有明显的制作过程；（3）软件在运行、使用期间不存在磨损、老化问题；）软件在运行、使用期间不存在磨损、老化问题；（

61、4）软件的开发、运行对计算机系统具有依赖性，受计算机）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；系统的限制，这导致了软件移植的问题；（5）软件复杂性高，成本昂贵；）软件复杂性高，成本昂贵；（6）软件开发涉及诸多的社会因素。）软件开发涉及诸多的社会因素。软件按功能分为：软件按功能分为： 应用软件、系统软件、支撑软件（或工具软件）。应用软件、系统软件、支撑软件（或工具软件）。72n1. 软件危机软件危机n早期的软件主要指程序，采用个体工作方式，缺少相关文档，早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为质量低，维护困难

62、，这些问题称为“软件危机软件危机”，软件工程，软件工程概念的出现源自于软件危机。概念的出现源自于软件危机。n软件危机主要表现在成本、质量、生产率等问题。软件危机主要表现在成本、质量、生产率等问题。n2. 软件工程软件工程n软件工程是指应用计算机科学、数学及管理科学等原理，以软件工程是指应用计算机科学、数学及管理科学等原理，以工程化工程化的原则和方法来解决软件问题的工程。其目的是提高的原则和方法来解决软件问题的工程。其目的是提高软件生产率、提高软件质量、降低软件成本。软件生产率、提高软件质量、降低软件成本。n软件工程是应用于计算机软件的定义、开发和维护的软件工程是应用于计算机软件的定义、开发和维

63、护的一整套一整套方法、工具、文档、实践标准和工序。方法、工具、文档、实践标准和工序。 3. 软件工程三要素软件工程三要素n方法：完成软件工程项目的技术手段方法：完成软件工程项目的技术手段n工具：支持软件的开发、管理、文档生成工具：支持软件的开发、管理、文档生成n过程：支持软件开发的各个环节的控制、管理过程：支持软件开发的各个环节的控制、管理; 将方法和工具综合起来将方法和工具综合起来,以达到合理、及时地进行计以达到合理、及时地进行计 算机软件开发的目的。算机软件开发的目的。734. 软件生命周期软件生命周期n将软件产品从提出、实现、使用、维护到停止使用退役的过将软件产品从提出、实现、使用、维护

64、到停止使用退役的过程称为软件生命周期程称为软件生命周期n分为分为软件定义软件定义、软件开发软件开发及及软件运行维护软件运行维护3个阶段。维护是个阶段。维护是持续时间最长，花费代价最大的一个阶段，软件工程学的一持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护代价个目的就是提高软件的可维护性，降低维护代价n6个活动阶段个活动阶段n可行性研究与计划制定：确定系统的总体目标。参加人可行性研究与计划制定：确定系统的总体目标。参加人员有用户、项目负责人和系统分析员，产生文档有员有用户、项目负责人和系统分析员，产生文档有可行可行性分析报告、项目计划书等性分析报告、项

65、目计划书等n需求分析：确定系统的逻辑模型。参加人员有用户、项需求分析：确定系统的逻辑模型。参加人员有用户、项目负责人和系统分析员。产生文档为目负责人和系统分析员。产生文档为需求规格说明书需求规格说明书，其作用其作用：（：（1）便于用户、开发人员进行理解交流；）便于用户、开发人员进行理解交流；（2）反映用户问题的结构，可以作为软件开发工作的基）反映用户问题的结构，可以作为软件开发工作的基础和依据；（础和依据；（3）作为确认测试和验收的依据。）作为确认测试和验收的依据。74n软件设计：包括软件软件设计：包括软件结构设计结构设计、数据设计数据设计、接口设计接口设计和和过程设计过程设计。 结构设计结构

66、设计是定义软件系统各部件之间的关系；是定义软件系统各部件之间的关系； 数据设计数据设计是将分析时创建的模型转化为数据结构的定义；是将分析时创建的模型转化为数据结构的定义； 接口设计接口设计是描述软件内部、软件和操作系统之间及软件与是描述软件内部、软件和操作系统之间及软件与 人之人之间如何通信；间如何通信； 过程设计过程设计是把系统结构部件转换成软件的过程性描述。是把系统结构部件转换成软件的过程性描述。 软件设计分概要设计和详细设计。软件设计分概要设计和详细设计。 参加人员有系统分析员和高级程序员。产生的文档有参加人员有系统分析员和高级程序员。产生的文档有设计规格说设计规格说明书。明书。n软件实

67、现：编程。高级程序员和程序员产生软件实现：编程。高级程序员和程序员产生源程序清单源程序清单n软件测试：在设计测试用例的基础上，检验软件的各个组成部分。软件测试：在设计测试用例的基础上，检验软件的各个组成部分。产生产生软件测试计划和软件测试报告软件测试计划和软件测试报告n运行与维护运行与维护753.2 需求分析与结构化分析方法需求分析与结构化分析方法n需求分析的方法需求分析的方法结构化分析方法结构化分析方法面向对象的分析方法面向对象的分析方法面向数据流的结构化方法面向数据流的结构化方法(SA)面向数据结构面向数据结构Jackson方法方法(JSD)面向数据结构的结构化数据系统开发方面向数据结构的

68、结构化数据系统开发方法法(DSSD)76结构化分析常用工具结构化分析常用工具:(1)数据流图数据流图DFD(2)数据字典数据字典DD(3)判定树判定树(4)判定表判定表结构化分析方法的实质：结构化分析方法的实质： 着眼于数据流，自顶向下，逐层分解，建立系统的着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具处理流程，以数据流图和数据字典为主要工具,建立系统建立系统的逻辑模型。的逻辑模型。773.3 结构化设计方法、概要设计和详细设计结构化设计方法、概要设计和详细设计n软件设计软件设计 软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完软件设计的基本目标

69、是用比较抽象概括的方式确定目标系统如何完成预定的任务，软件设计是确定系统的物理模型。成预定的任务，软件设计是确定系统的物理模型。 软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径。软件产品或系统的唯一途径。n从技术观点来看，软件设计包括软件结构设计、数从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。据设计、接口设计、过程设计。 结构设计：定义软件系统各主要部件之间的关系。结构设计：定义软件系统各主要部件之间的关系。 数据设计：将分析时创建的模型转化为数据结构的定义。数据设计：将分

70、析时创建的模型转化为数据结构的定义。 接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。通信。 过程设计：把系统结构部件转换成软件的过程描述。过程设计：把系统结构部件转换成软件的过程描述。n从工程管理角度来看：概要设计和详细设计。从工程管理角度来看：概要设计和详细设计。78软件设计的基本原理：软件设计的基本原理： （1）抽象）抽象 （2）模块化）模块化 （3）信息隐蔽）信息隐蔽 （4）模块独立化）模块独立化 内聚性：内聚性： 耦合性：耦合性：在程序结构中各模块的内聚性越强，则耦合性越弱。在程序结构中各模块的内聚性越

71、强，则耦合性越弱。优秀软件应高内聚，低耦合。优秀软件应高内聚，低耦合。793.3.2 概要设计概要设计n设计的基本任务设计的基本任务n软件的系统结构软件的系统结构n数据结构和数据库设计数据结构和数据库设计n编写概要设计文档编写概要设计文档n概要设计文档评审概要设计文档评审80需求分析需求分析逻辑模型逻辑模型数据流图数据流图概要设计概要设计系统结构图系统结构图物理模型物理模型概要设计的方法概要设计的方法:结构图（结构图（SC)：概要设计概要设计(软件结构设计软件结构设计)的工具的工具:813.3.3 详细设计详细设计根本目标根本目标n确定应用怎样具体的实现所要求的系统，不是具体的编写程序，确定应

72、用怎样具体的实现所要求的系统，不是具体的编写程序，而是要设计程序的而是要设计程序的“蓝图蓝图”详细设计常用的设计工具（工程设计工具）：详细设计常用的设计工具（工程设计工具）：n图形工具：图形工具：n程序流程图：箭头表示控制流，方框表示加工步骤，菱形表示逻程序流程图：箭头表示控制流，方框表示加工步骤，菱形表示逻辑条件。辑条件。nN-S图：有五种基本图形。图：有五种基本图形。nPAD图：问题分析图，有五种基本图型。图：问题分析图，有五种基本图型。n表格工具：判定表。表格工具：判定表。n语言工具：语言工具：PDL过程设计语言（结构化的英语和伪码）。过程设计语言（结构化的英语和伪码）。823.4 软件

73、测试软件测试 软件测试定义：软件测试定义： 使用人工或自动手段来运行或测定某个系统的过程使用人工或自动手段来运行或测定某个系统的过程3.4.1 意义目的意义目的n为了发现错误为了发现错误n希望能以最少的人力和时间发现潜在的各种错误和缺陷希望能以最少的人力和时间发现潜在的各种错误和缺陷n保证系统质量和可靠性的关键步骤保证系统质量和可靠性的关键步骤 3.4.2 测试方法测试方法n静态测试：包括代码检查、静态结构分析、代码质量度量。静态测试：包括代码检查、静态结构分析、代码质量度量。 不实际运行软件，主要通过人工进行。不实际运行软件，主要通过人工进行。n动态测试：是基于计算机的测试。动态测试：是基于

74、计算机的测试。 主要包括白盒测试方法和黑盒测试方法。主要包括白盒测试方法和黑盒测试方法。833.4.3 白盒测试白盒测试n结构测试结构测试n将软件看成透明的白盒，根据程序的内部结构和逻辑结构将软件看成透明的白盒，根据程序的内部结构和逻辑结构来设计测试例子，对程序的路径和过程进行测试，检查是来设计测试例子，对程序的路径和过程进行测试，检查是否满足设计的要求否满足设计的要求n主要方法：逻辑覆盖、基本路径测试主要方法：逻辑覆盖、基本路径测试3.4.4 黑盒测试黑盒测试n功能测试功能测试n将软件看成黑盒子，在完全不考虑软件内部结构和特性的将软件看成黑盒子，在完全不考虑软件内部结构和特性的情况下，测试软

75、件的外部特性情况下，测试软件的外部特性n主要方法：等价类划分法、边界值分析法、错误推测法主要方法：等价类划分法、边界值分析法、错误推测法843.5 程序调试程序调试1 任务任务n根据测试时发现的错误，根据测试时发现的错误， （）找出原因和具体的位置（）找出原因和具体的位置 （）进行改正，排除错误（）进行改正，排除错误n由程序开发人员来进行，谁开发的程序就由谁来进由程序开发人员来进行，谁开发的程序就由谁来进行调试行调试2. 程序调试的基本步骤：程序调试的基本步骤：（1）错误定位；）错误定位；（2）修改设计和代码，以排除错误；）修改设计和代码，以排除错误；（3）进行回归测试，防止引进新的错误。）进

76、行回归测试，防止引进新的错误。3.调试方法：（静态、动态调试法）调试方法：（静态、动态调试法）强行排错法强行排错法回溯法回溯法原因排除法（演绎、归纳、二分法原因排除法（演绎、归纳、二分法)85n为了提高测试的效率，应该为了提高测试的效率，应该 A) 随机选取测试数据随机选取测试数据 B) 取一切可能的输入数据作为测试数据取一切可能的输入数据作为测试数据 C) 在完成编码以后制定软件的测试计划在完成编码以后制定软件的测试计划 D) 集中对付那些错误群集的程序集中对付那些错误群集的程序n软件生命周期中所花费用最多的阶段是软件生命周期中所花费用最多的阶段是 A) 详细设计详细设计 B) 软件编码软件

77、编码 C) 软件测试软件测试 D) 软件维护软件维护n下列叙述中，不属于软件需求规格说明书的作下列叙述中，不属于软件需求规格说明书的作用的是用的是 A) 便于用户、开发人员进行理解和交流便于用户、开发人员进行理解和交流 B) 反映出用户问题的结构，可以作为软件开发工作的基础和依据反映出用户问题的结构，可以作为软件开发工作的基础和依据 C) 作为确认测试和验收的依据作为确认测试和验收的依据 D) 便于开发人员进行需求分析便于开发人员进行需求分析n下列不属于软件工程的下列不属于软件工程的3个要素的是个要素的是 ) 工具工具) 过程过程 ) 方法方法) 环境环境例题讲解例题讲解86n 软件设计包括软

78、件的结构、数据、接口和过程设计，其中软件设计包括软件的结构、数据、接口和过程设计，其中软件的过程设计是指软件的过程设计是指 A) 模块间的关系模块间的关系 B) 系统结构部件转换成软件的过程描述系统结构部件转换成软件的过程描述 C) 软件层次结构软件层次结构 D) 软件开发过程软件开发过程n检查软件产品是否符合需求定义的过程称为检查软件产品是否符合需求定义的过程称为 ) 确认测试确认测试 ) 集成测试集成测试 ) 验证测试验证测试 ) 验收测试验收测试n 数据流图用于抽象描述一个软件的逻辑模型，数据流图由数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符

79、不属于数据流一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是图合法图符的是 ) 控制流控制流 ) 加工加工 ) 数据存储数据存储 ) 源和流源和流87n开发软件所需高成本和产品的低质量之间有着尖锐的开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现象称作矛盾，这种现象称作 A) 软件投机软件投机 B) 软件危机软件危机 C) 软件工程软件工程 D) 软件产生软件产生n下面不属于软件设计原则的是下面不属于软件设计原则的是 ) 抽象抽象) 模块化模块化 ) 自底向上自底向上 ) 信息隐蔽信息隐蔽n开发大型软件时，产生困难的根本原因是开发大型软件时，产生困难的根本原因是 A

80、) 大系统的复杂性大系统的复杂性B) 人员知识不足人员知识不足 C) 客观世界千变万化客观世界千变万化D) 时间紧、任务重时间紧、任务重n软件工程的出现是由于软件工程的出现是由于 A) 程序设计方法学的影响程序设计方法学的影响B) 软件产业化的需要软件产业化的需要 C) 软件危机的出现软件危机的出现D) 计算机的发展计算机的发展88n软件开发离不开系统环境资源的支持，其软件开发离不开系统环境资源的支持，其中必要的测试数据属于中必要的测试数据属于 A) 硬件资源硬件资源 B) 通信资源通信资源 C) 支持软件支持软件 D) 辅助资源辅助资源n在数据流图在数据流图(DFD) 中，带有名字的箭头表中

81、，带有名字的箭头表示示 A) 模块之间的调用关系模块之间的调用关系B) 程序的组成成分程序的组成成分 C) 控制程序的执行顺序控制程序的执行顺序D) 数据的流向数据的流向n下列不属于结构化分析的常用工具的是下列不属于结构化分析的常用工具的是 A) 数据流图数据流图 B) 数据字典数据字典 C) 判定树判定树 D) PAD图图n在软件生产过程中，需求信息的给出者是在软件生产过程中，需求信息的给出者是 A) 程序员程序员 B) 项目管理者项目管理者 C) 软件分析设计人员软件分析设计人员 D) 软件用户软件用户89n下列工具不是过程设计常用工具的是下列工具不是过程设计常用工具的是 ) PAD) P

82、FD ) N-S) DFDn模块独立性是软件模块化所提出的要求，衡量模块独立性是软件模块化所提出的要求，衡量模块独立性的度量标准则是模块的模块独立性的度量标准则是模块的 A) 抽象和信息隐蔽抽象和信息隐蔽 B) 局部化和封装化局部化和封装化 C) 内聚性和耦合性内聚性和耦合性 D) 激活机制和控制方法激活机制和控制方法n软件开发的结构化生命周期方法将软件生命周软件开发的结构化生命周期方法将软件生命周期划分成期划分成 A) 定义、开发、运行维护定义、开发、运行维护 B) 设计阶段、编程阶段、测试阶段设计阶段、编程阶段、测试阶段 C) 总体设计、详细设计、编程调试总体设计、详细设计、编程调试 D)

83、 需求分析、功能定义、系统设计需求分析、功能定义、系统设计90n在软件工程中，白箱测试法可用于测试程序的在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是内部结构。此方法将程序看做是 A) 路径的集合路径的集合 B) 循环的集合循环的集合 C) 目标的集合目标的集合 D) 地址的集合地址的集合n完全不考虑程序的内部结构和内部特征，而只完全不考虑程序的内部结构和内部特征，而只是根据程序功能导出测试用例的测试方法是是根据程序功能导出测试用例的测试方法是 A) 黑箱测试法黑箱测试法 B) 白箱测试法白箱测试法 C) 错误推测法错误推测法 D) 安装测试法安装测试法n在结构化设计方法

84、中，生成的结构图在结构化设计方法中，生成的结构图(SC) 中，中，带有箭头的连线表示带有箭头的连线表示 A) 模块之间的调用关系模块之间的调用关系B) 程序的组成成分程序的组成成分 C) 控制程序的执行顺序控制程序的执行顺序D) 数据的流向数据的流向91n下列选项中，不属于模块间耦合的是下列选项中，不属于模块间耦合的是 A) 数据耦合数据耦合 B) 同构耦合同构耦合 C) 异构耦合异构耦合 D) 公用耦合公用耦合n下列叙述中，不属于测试的特征的是下列叙述中，不属于测试的特征的是 A) 测试的挑剔性测试的挑剔性B) 完全测试的不可能性完全测试的不可能性 C) 测试的可靠性测试的可靠性D) 测试的

85、经济性测试的经济性n需求分析中开发人员要从用户那里了解需求分析中开发人员要从用户那里了解 A) 软件做什么软件做什么B) 用户使用界面用户使用界面 C) 输入的信息输入的信息D) 软件的规模软件的规模n下列不属于软件调试技术的是下列不属于软件调试技术的是 A) 强行排错法强行排错法B) 集成测试法集成测试法 C) 回溯法回溯法D) 原因排除法原因排除法92n为了避免流程图在描述程序逻辑时的灵活性，为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，提出了用方框图来代替传统的程序流程图，通常也把这种图称为通常也把这种图称为 A) PAD图图B) N-S图图 C) 结构图

86、结构图D) 数据流图数据流图n 软件复杂性度量的参数包括软件复杂性度量的参数包括 A) 效率效率B) 规模规模 C) 完整性完整性D) 容错性容错性n下列叙述中，正确的是下列叙述中，正确的是 A) 软件就是程序清单软件就是程序清单 B) 软件就是存放在计算机中的文件软件就是存放在计算机中的文件 C) 软件应包括程序清单及运行结果软件应包括程序清单及运行结果 D) 软件包括程序和文档软件包括程序和文档n 软件设计中，有利于提高模块独立性的一个软件设计中，有利于提高模块独立性的一个准则是准则是 A) 低内聚低耦合低内聚低耦合B) 低内聚高耦合低内聚高耦合 C) 高内聚低耦合高内聚低耦合D) 高内聚

87、高耦合高内聚高耦合93n软件生命周期中花费时间最多的阶段是软件生命周期中花费时间最多的阶段是 A) 详细设计详细设计 B) 软件编码软件编码 C) 软件测试软件测试 D) 软件维护软件维护n下列叙述中，不属于结构化分析方法的是下列叙述中，不属于结构化分析方法的是 A) 面向数据流的结构化分析方法面向数据流的结构化分析方法 B) 面向数据结构的面向数据结构的Jackson方法方法 C) 面向数据结构的结构化数据系统开发方法面向数据结构的结构化数据系统开发方法 D) 面向对象的分析方法面向对象的分析方法n详细设计的结果基本决定了最终程序的详细设计的结果基本决定了最终程序的 A) 代码的规模代码的规

88、模 B) 运行速度运行速度 C) 质量质量 D) 可维护性可维护性n下列不属于静态测试方法的是下列不属于静态测试方法的是 A) 代码检查代码检查B) 白盒法白盒法 C) 静态结构分析静态结构分析D) 代码质量度量代码质量度量94n在软件生命周期中，能准确地确定软件系统在软件生命周期中，能准确地确定软件系统必须做什么和必须局别哪些功能的阶段是必须做什么和必须局别哪些功能的阶段是A）概要设计）概要设计 B）详细设计）详细设计 C）可行性分析）可行性分析 D）需求分析）需求分析n检查软件产品是否符合需求定义的过程称为检查软件产品是否符合需求定义的过程称为A）确认测试）确认测试 B）集成测试）集成测试

89、 C）验证测试）验证测试 D）验收测试）验收测试n数据流图用于抽象描述一个软件的逻辑模型，数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成，下列图符数据流图由一些特定的图符构成，下列图符名标识的图符不属于数据流图合法图符的是名标识的图符不属于数据流图合法图符的是A）控制流）控制流 B）加工）加工 C）数据存储）数据存储 D）源和潭）源和潭95n下面不属于软件设计原则的是下面不属于软件设计原则的是A）抽象）抽象 B）模块化）模块化 C）自底向上）自底向上 D）信息屏蔽）信息屏蔽n程序流程图（程序流程图（PFD）中的箭头代表的是）中的箭头代表的是A）数据流）数据流 B）控制流）

90、控制流 C）调用关系）调用关系 D）组成关系）组成关系n下列工具中为需求分析常用工具的是下列工具中为需求分析常用工具的是A）PAD B）PFD C）N-S D）DFDn在结构化方法中，软件功能分解属于下列软件在结构化方法中，软件功能分解属于下列软件开发中的阶段是开发中的阶段是A）详细设计）详细设计 B）需求分析）需求分析C）总体设计）总体设计 D）编程调试）编程调试96n软件调试的目的是软件调试的目的是A）发现错误）发现错误 B）改正错误）改正错误C）改善软件的性能）改善软件的性能 D）挖掘软件的潜能）挖掘软件的潜能n软件需求分析阶段的工作，可以分为四个方软件需求分析阶段的工作，可以分为四个方

91、面：需求获取，需求分析，编写需求规格说面：需求获取，需求分析，编写需求规格说明书，以及明书，以及A）阶段性报告）阶段性报告 B）需求评审）需求评审C）总结）总结 D）都不正确）都不正确n软件是程序、数据和软件是程序、数据和_的集合。的集合。nJackson方法是一种面向方法是一种面向_的结构化方法。的结构化方法。n软件工程研究的内容主要包括：软件工程研究的内容主要包括：_技术和技术和软件工程管理。软件工程管理。文档文档数据结构数据结构软件开发软件开发97n 通常，将软件产品从提出、实现、使用维护通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为到停止使用退役的过程称为 【4】 。

92、n耦合和内聚是评价模块独立性的两个主要标耦合和内聚是评价模块独立性的两个主要标准，其中准，其中 【3】 反映了模块内各成分之间反映了模块内各成分之间的联系。的联系。 n 软件工程研究的内容主要包括：软件工程研究的内容主要包括： 【4】 技术技术和软件工程管理。和软件工程管理。 n软件设计模块化的目的是软件设计模块化的目的是 【4】 。软件生命周期软件生命周期耦合耦合软件开发软件开发降低复杂性降低复杂性984.数据库设计基础994.1 基本概念1. 数据数据(Data)n实际上就是描述事物的符号记录实际上就是描述事物的符号记录n软件中的数据是有一定结构的软件中的数据是有一定结构的2. 数据库数据

93、库(DB)n长期存储在计算机内的，有组织的，可共享的长期存储在计算机内的，有组织的，可共享的数据集合。数据集合。n数据库中的数据按一定的数学模型组织、描述数据库中的数据按一定的数学模型组织、描述和存储，具有较小的冗余度，较高的数据独立和存储，具有较小的冗余度，较高的数据独立性和易扩展性，并可为各种用户共享。性和易扩展性，并可为各种用户共享。1003. 数据库管理系统数据库管理系统(DBMS)n数据库系统的核心软件数据库系统的核心软件n要在操作系统支持下工作要在操作系统支持下工作n解决如何科学地组织和存储数据，如何高效的获取和维护数解决如何科学地组织和存储数据，如何高效的获取和维护数据的系统软件

94、据的系统软件n主要功能包括主要功能包括n数据模式定义数据模式定义n数据操纵数据操纵n数据的完整性、安全性定义与检查数据的完整性、安全性定义与检查n数据库的并发控制与故障恢复数据库的并发控制与故障恢复n数据的服务数据的服务n为完成上述功能，为完成上述功能，DBMS一般提供相应的数据语言：一般提供相应的数据语言：n数据定义语言（数据定义语言（DDL）n数据操纵语言（数据操纵语言（DML）n数据控制语言（数据控制语言（DCL）n数据语言按其使用方式具有两种结构形式数据语言按其使用方式具有两种结构形式n交互式命令语言交互式命令语言n宿主型语言宿主型语言1014. 数据库管理员数据库管理员n主要工作包括

95、：主要工作包括：n数据库设计数据库设计n数据库维护数据库维护n改善系统性能，提高系统效率改善系统性能，提高系统效率5. 数据库系统（数据库系统（DBS）n由数据库（数据）、数据库管理系统（软件）、数据库管理由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、系统平台之硬件平台（硬件）和软件平台（软员（人员）、系统平台之硬件平台（硬件）和软件平台（软件）构成。件）构成。6. 数据库应用系统（数据库应用系统（DBAS）n利用数据库系统进行应用开发利用数据库系统进行应用开发7. 数据库管理技术的发展数据库管理技术的发展n人工管理阶段人工管理阶段n文件系统阶段文件系统阶段n数据库系统阶段（

96、层次、网状、关系）数据库系统阶段（层次、网状、关系）1028. 数据库系统的基本特点数据库系统的基本特点n数据的集成性数据的集成性n采用统一的数据结构方式采用统一的数据结构方式n按照多个应用的需要组主全局的统一的数据结构按照多个应用的需要组主全局的统一的数据结构n数据模式是多个应用共同的、全局的数据结构数据模式是多个应用共同的、全局的数据结构n数据的高共享性与低冗余性数据的高共享性与低冗余性n数据独立性数据独立性n物理独立性和逻辑独立性物理独立性和逻辑独立性n数据统一管理与控制数据统一管理与控制n数据的完整性检查数据的完整性检查n数据的安全性检查数据的安全性检查n并发控制并发控制1039. 数

97、据库系统的内部结构体系数据库系统的内部结构体系n数据库系统的三级模式数据库系统的三级模式（1）概念模式）概念模式（2）外模式）外模式（3）内模式）内模式n内模式处于最底层，它反映了数据在计算机物理结构内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式中的实际存储形式n概念模式处于中层，它放映了设计者的数据全局逻辑概念模式处于中层，它放映了设计者的数据全局逻辑要求要求n外模式处于最外层，它反映了用户对数据的要求外模式处于最外层，它反映了用户对数据的要求104一、外模式一、外模式/模式映象模式映象数据的逻辑独立性数据的逻辑独立性：当模式改变时，由：当模式改变时，由 外模式外模式/模式映

98、象模式映象作相应的改变，可以保持外模式不变。应用程序是依据数作相应的改变，可以保持外模式不变。应用程序是依据数据的外模式编写的，从而应用程序不必修改，保证了数据据的外模式编写的，从而应用程序不必修改，保证了数据与与 程序的逻辑独立性。程序的逻辑独立性。数据的物理独立性数据的物理独立性：当内模式改变时，：当内模式改变时， 由由 模式模式/内模式映内模式映象象作相应的改变，可以保持模式不变。从而应用程序也不作相应的改变，可以保持模式不变。从而应用程序也不必改变，保证了数据与程序的物理独立性。必改变，保证了数据与程序的物理独立性。二、模式二、模式/内模式映象内模式映象1054.2 数据模型数据模型：

99、数据模型：是现实世界数据特征的抽象。是现实世界数据特征的抽象。在数据库中用数据模型这个工具来抽象、表示和处理现在数据库中用数据模型这个工具来抽象、表示和处理现实世界中的数据和信息。实世界中的数据和信息。通俗地讲数据模型就是现实世界的模拟。通俗地讲数据模型就是现实世界的模拟。数据模型应满足三方面的要求：数据模型应满足三方面的要求：（1）能比较真实地模拟现实世界。）能比较真实地模拟现实世界。（2）容易为人理解。）容易为人理解。（3）便于在计算机上实现。）便于在计算机上实现。1064.2.1 数据模型的基本概念数据模型的基本概念n数据模型是数据特性的抽象数据模型是数据特性的抽象n数据模型描述的内容数

100、据模型描述的内容n数据结构数据结构n数据操作数据操作n数据约束数据约束n数据模型按不同的应用层次分成三种类型数据模型按不同的应用层次分成三种类型n概念数据模型（概念模型）概念数据模型（概念模型）n逻辑数据模型（数据模型）逻辑数据模型（数据模型）n物理数据模型（物理模型）物理数据模型（物理模型）E-R图、扩充的图、扩充的E-R图。图。层次模型层次模型网状模型网状模型关系模型关系模型面向对象面向对象107n4.2.2 E-R模型（实体联系模型）模型（实体联系模型）n基本概念基本概念（1）实体）实体（2）属性）属性（3）联系）联系n一对一（一对一（1：1）n一对多（一对多（1：M或或M：1）n多对多

101、（多对多（M：N）班级班级拥有拥有班长班长11班级班级拥有拥有学生学生1n课程课程选修选修学生学生mn108运算符运算符集合运算集合运算:专门的关系运算专门的关系运算:比较运算比较运算: = = = 逻辑运算逻辑运算:4.3 关系代数关系代数109设设关系关系R和和关系关系S具有相同的目具有相同的目n,且相应的属性取自同一个且相应的属性取自同一个域域,则可有如下定义则可有如下定义:1.并并2.差差3.交交传统的集合运算传统的集合运算110例子例子:A B CRa1a1a2b1b2b2c1c2c1A B CSa1a1a2b2b3b2c2c2c1A B CR Sa1a1a2a1b1b2b2b3c1

102、c2c1c2111A B CRa1a1a2b1b2b2c1c2c1A B CSa1a1a2b2b3b2c2c2c1A B CR Sa1a2b2b2c2c1A B CR-Sa1b1c1112R Sa1a1a1a1a1a1a2a2a2A B C A B Cb1b1b1b2b2b2b2b2b2c1c1c1c2c2c2c1c1c1a1a1a2a1a1a2a1a1a2b2b3b2b2b3b2b2b3b2c2c2c1c2c2c1c2c2c1A B CRa1a1a2b1b2b2c1c2c1A B CSa1a1a2b2b3b2c2c2c14.笛卡儿笛卡儿113专门的关系运算：专门的关系运算：1.选择选择例子例

103、子1:查询信息系查询信息系(IS系系)的全体学生的全体学生. Sno Sname Ssex Sage Sdept刘晨刘晨张立张立9500295004ISIS女女男男1919 Sno Sname Ssex Sage Sdept李勇李勇刘晨刘晨王敏王敏张立张立95001950029500395004CSISMAIS男男女女女女男男201918191142.投影投影例子例子4:查询学生的姓名和所在系查询学生的姓名和所在系. Sno Sname Ssex Sage Sdept李勇李勇刘晨刘晨王敏王敏张立张立95001950029500395004CSISMAIS男男女女女女男男20191819Snam

104、e Sdept李勇李勇刘晨刘晨王敏王敏张立张立CSISMAIS1153.连接连接例子例子:A B CRa1a1a2a2b1b2b3b45 6 8 12B ESb1b2b3a2a13 7 102 2说明说明:（1）A和和B分别是分别是R和和S上度相等且可比的属性组。上度相等且可比的属性组。 （2） 是比较运算符。是比较运算符。116等值连接等值连接:当连接条件为当连接条件为“=”时的连接运算时的连接运算.A R.B C S.B EA B CRa1a1a2a2b1b2b3b45 6 8 12B ESb1b2b3b3b53 7 102 2a2 b3 8 b3 10 a2 b3 8 b3 2 117A

105、 R.B C Ea1a1a2a2b1b2b3b35 6 8 8 3 7 10 2自然连接自然连接:是一种特殊的等值连接是一种特殊的等值连接,它要求两个关系中进行它要求两个关系中进行 比较的分量是相同的属性组比较的分量是相同的属性组,并且在结果中把重并且在结果中把重 复的属性列去掉复的属性列去掉.A B CRa1a1a2a2b1b2b3b45 6 8 12B ESb1b2b3b3b53 7 102 21184.4 数据库设计与管理数据库设计与管理4.4.1 数据库设计概述数据库设计概述n设计一个能满足用户要求，性能良好的数据库设计一个能满足用户要求，性能良好的数据库n基本任务：根据用户对象的信息

106、需求、处理需求和数基本任务：根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式据库的支持环境设计出数据模式n两种方法：两种方法：n以信息需求为主，兼顾处理需求（面向数据的方法）以信息需求为主，兼顾处理需求（面向数据的方法）n以处理需求为主，兼顾信息需求（面向过程的方法）以处理需求为主，兼顾信息需求（面向过程的方法）n面向数据的设计方法已成为主流方法面向数据的设计方法已成为主流方法119n数据库设计目前一般采用生命周期法，分若干阶段数据库设计目前一般采用生命周期法，分若干阶段n需求分析阶段需求分析阶段n概念设计阶段概念设计阶段n逻辑设计阶段逻辑设计阶段n物理设计阶段物理设计阶段n编

107、码阶段编码阶段n测试阶段测试阶段n运行阶段运行阶段n进一步修改阶段进一步修改阶段n在数据库设计中采用前四个阶段，并且重点以数据结在数据库设计中采用前四个阶段，并且重点以数据结构与模型的设计为主线构与模型的设计为主线E-R图关系模型关系模型1204.4.3 数据库概念设计数据库概念设计n概述概述n目的：分析数据间内在语义关联，在此基础上建目的：分析数据间内在语义关联，在此基础上建立一个数据的抽象模型立一个数据的抽象模型n设计方法：集中式模式设计法和视图集成设计法设计方法：集中式模式设计法和视图集成设计法n设计的过程设计的过程 n选择局部应用选择局部应用n视图设计：视图设计：3种设计次序（自顶向下

108、、由底向上、种设计次序（自顶向下、由底向上、由内向外）由内向外）n视图集成视图集成121n数据库管理系统数据库管理系统DBMS中用来定义模式、内模式和外模式的中用来定义模式、内模式和外模式的语言为语言为 A) C B) Basic C) DDL D) DMLn下列有关数据库的描述，正确的是下列有关数据库的描述，正确的是 A) 数据库是一个数据库是一个DBF文件文件B) 数据库是一个关系数据库是一个关系 C) 数据库是一个结构化的数据集合数据库是一个结构化的数据集合D) 数据库是一组文件数据库是一组文件n下列有关数据库的描述，正确的是下列有关数据库的描述，正确的是 A) 数据处理是将信息转化为数

109、据的过程数据处理是将信息转化为数据的过程 B) 数据的物理独立性是指当数据的逻辑结构改变时，数据的数据的物理独立性是指当数据的逻辑结构改变时，数据的存储结构不变存储结构不变 C) 关系中的每一列称为元组，一个元组就是一个字段关系中的每一列称为元组，一个元组就是一个字段 D) 如果一个关系中的属性或属性组并非该关系的关键字，但如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键字，则称其为本关系的外关键字它是另一个关系的关键字，则称其为本关系的外关键字例题讲解例题讲解122n应用数据库的主要目的是应用数据库的主要目的是 A) 解决数据保密问题解决数据保密问题B) 解决数据完整性

110、问题解决数据完整性问题 C) 解决数据共享问题解决数据共享问题D) 解决数据量大的问题解决数据量大的问题n在数据库设计中，将在数据库设计中，将E-R图转换成关系数据模型的过程属于图转换成关系数据模型的过程属于 A) 需求分析阶段需求分析阶段B) 逻辑设计阶段逻辑设计阶段 C) 概念设计阶段概念设计阶段D) 物理设计阶段物理设计阶段n在数据管理技术的发展过程中，经历了人工管理阶段、文件在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是系统阶段和数据库系统阶段。其中数据独立性最高的阶段是 ) 数据库系统数据库系统 ) 文件系统文件系统 ) 人工

111、管理人工管理) 数据项管理数据项管理n下述关于数据库系统的叙述中正确的是下述关于数据库系统的叙述中正确的是 ) 数据库系统减少了数据冗余数据库系统减少了数据冗余 ) 数据库系统避免了一切冗余数据库系统避免了一切冗余 ) 数据库系统中数据的一致性是指数据类型一致数据库系统中数据的一致性是指数据类型一致 ) 数据库系统比文件系统能管理更多的数据数据库系统比文件系统能管理更多的数据123n索引属于索引属于 A) 模式模式B) 内模式内模式 C) 外模式外模式D) 概念模式概念模式n 数据库系统的核心是数据库系统的核心是 A) 数据库数据库 B) 数据库管理系统数据库管理系统 C) 模拟模型模拟模型

112、D) 软件工程软件工程n分布式数据库系统不具有的特点是分布式数据库系统不具有的特点是 A) 数据分布性和逻辑整体性数据分布性和逻辑整体性 B) 位置透明性和复制透明性位置透明性和复制透明性 C) 分布性分布性 D) 数据冗余数据冗余n关系表中的每一横行称为一个关系表中的每一横行称为一个 ) 元组元组 ) 字段字段 ) 属性属性) 码码n下列数据模型中，具有坚实理论基础的是下列数据模型中，具有坚实理论基础的是 A) 层次模型层次模型B) 网状模型网状模型 C) 关系模型关系模型D) 以上以上3个都是个都是124n下列下列SQL语句中，用于修改表结构的是语句中，用于修改表结构的是 A) ALTER

113、 B) CREATE C) UPDATE D) INSERTn数据库、数据库系统和数据库管理系统之间的关系是数据库、数据库系统和数据库管理系统之间的关系是 A) 数据库包括数据库系统和数据库管理系统数据库包括数据库系统和数据库管理系统 B) 数据库系统包括数据库和数据库管理系统数据库系统包括数据库和数据库管理系统 C) 数据库管理系统包括数据库和数据库系统数据库管理系统包括数据库和数据库系统 D) 3者没有明显的包含关系者没有明显的包含关系n关系模型允许定义关系模型允许定义3类数据约束，下列不属于数据约束类数据约束，下列不属于数据约束的是的是 A) 实体完整性约束实体完整性约束B) 参照完整性

114、约束参照完整性约束 C) 域完整性约束域完整性约束D) 用户自定义的完整性约束用户自定义的完整性约束125n NULL是指是指 A) 0B) 空格空格 C) 未知的值或无任何值未知的值或无任何值 D) 空字符串空字符串n数据库的故障恢复一般是由数据库的故障恢复一般是由 A) 数据流图完成的数据流图完成的B) 数据字典完成的数据字典完成的 C) DBA完成的完成的 D) PAD图完成的图完成的n下列说法中，不属于数据模型所描述的内容的是下列说法中，不属于数据模型所描述的内容的是 A) 数据结构数据结构B) 数据操作数据操作 C) 数据查询数据查询D) 数据约束数据约束 126n 在数据管理技术发

115、展过程中，文件系统与数据库系在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有统的主要区别是数据库系统具有 A) 特定的数据模型特定的数据模型B) 数据无冗余数据无冗余 C) 数据可共享数据可共享 D) 专门的数据管理软件专门的数据管理软件n数据库设计包括两个方面的设计内容，它们是数据库设计包括两个方面的设计内容，它们是 A) 概念设计和逻辑设计概念设计和逻辑设计 B) 模式设计和内模式设计模式设计和内模式设计 C) 内模式设计和物理设计内模式设计和物理设计 D) 结构特性设计和行为特性设计结构特性设计和行为特性设计n实体是信息世界中广泛使用的一个术语，它用于表示实体是信

116、息世界中广泛使用的一个术语，它用于表示 A) 有生命的事物有生命的事物 B) 无生命的事物无生命的事物 C) 实际存在的事物实际存在的事物 D) 一切事物一切事物127n一个关系中属性个数为一个关系中属性个数为1时，称此关系为时，称此关系为 A) 对应关系对应关系B) 单一关系单一关系 C) 一元关系一元关系D) 二元关系二元关系n为用户与数据库系统提供接口的语言是为用户与数据库系统提供接口的语言是 A) 高级语言高级语言B) 数据描述语言数据描述语言(DDL) C) 数据操纵语言数据操纵语言(DML) D) 汇编语言汇编语言n相对于数据库系统，文件系统的主要缺陷有数据关相对于数据库系统，文件

117、系统的主要缺陷有数据关联差、数据不一致性和联差、数据不一致性和 A) 可重用性差可重用性差B) 安全性差安全性差 C) 非持久性非持久性 D) 冗余性冗余性 128n下列叙述中，不属于数据库系统的是下列叙述中，不属于数据库系统的是 A) 数据库数据库B) 数据库管理系统数据库管理系统 C) 数据库管理员数据库管理员 D) 数据库应用系统数据库应用系统n数据库系统的核心是数据库系统的核心是 A) 数据库数据库B) 数据库管理系统数据库管理系统 C) 数据模型数据模型 D) 软件工具软件工具n 视图设计一般有视图设计一般有3种设计次序，下列不属于种设计次序，下列不属于视图设计的是视图设计的是 A)

118、 自顶向下自顶向下B) 由外向内由外向内 C) 由内向外由内向外D) 自底向上自底向上129n下列下列4项中说法不正确的是项中说法不正确的是 A) 数据库减少了数据冗余数据库减少了数据冗余 B) 数据库中的数据可以共享数据库中的数据可以共享 C) 数据库避免了一切数据的重复数据库避免了一切数据的重复 D) 数据库具有较高的数据独立性数据库具有较高的数据独立性n下列下列4项中，必须进行查询优化的是项中，必须进行查询优化的是 A) 关系数据库关系数据库B) 网状数据库网状数据库 C) 层次数据库层次数据库D) 非关系模型非关系模型n最常用的一种基本数据模型是关系数据模型，最常用的一种基本数据模型是

119、关系数据模型，它的表示应采用它的表示应采用 A) 树树 B) 网络网络 C) 图图 D) 二维表二维表130n公司中有多个部门和多名职员，每个职员只能属于一个部门，公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，从部门到职员的联系类型是一个部门可以有多名职员，从部门到职员的联系类型是 A) 多对多多对多 B) 一对一一对一 C) 多对一多对一 D) 一对多一对多 n下列关系运算的叙述中，正确的是下列关系运算的叙述中，正确的是 A) 投影、选择、连接是从二维表行的方向进行的运算投影、选择、连接是从二维表行的方向进行的运算 B) 并、交、差是从二维表的列的方向来进行运

120、算并、交、差是从二维表的列的方向来进行运算 C) 投影、选择、连接是从二维表列的方向进行的运算投影、选择、连接是从二维表列的方向进行的运算 D) 以上以上3种说法都不对种说法都不对n关系数据库管理系统应能实现的专门的关系运算包括关系数据库管理系统应能实现的专门的关系运算包括 A) 排序、索引、统计排序、索引、统计B) 选择、投影、连接选择、投影、连接 C) 关联、更新、排序关联、更新、排序D) 显示、打印、制表显示、打印、制表131n用树形结构来表示实体之间联系的模型称为用树形结构来表示实体之间联系的模型称为A）关系模型）关系模型 B）层次模型）层次模型C）网状模型）网状模型 D）关系模型）关

121、系模型n关系表中的每一横行称为一个关系表中的每一横行称为一个A)元组元组B)字段字段C)属性属性D)码码n按条件按条件f对关系进行选择，其关系运算表示式对关系进行选择，其关系运算表示式是是A)RR B)RR C)f(R) D)f(R) f132n在关系数据库中，用来表示实体之间联系的是在关系数据库中，用来表示实体之间联系的是A)树结构树结构B)网结构网结构C)线性表线性表D)二维表二维表n数据库设计包括两个方面的设计内容，它们是数据库设计包括两个方面的设计内容，它们是A)概念设计和逻辑设计概念设计和逻辑设计B)模式设计和内模式设计模式设计和内模式设计C)内模式设计和物理设计内模式设计和物理设计

122、D)结构特性设计和行为特性设计结构特性设计和行为特性设计n将将-R图转换到关系模式时，实体与联系都可以图转换到关系模式时，实体与联系都可以表示成表示成A)属性属性 B)关系关系 C)键键 D)域域133n数据库管理系统常见的数据模型有层次模型、数据库管理系统常见的数据模型有层次模型、网状模型和网状模型和 【5】 3种。种。 n 一个项目具有一个项目主管，一个项目主管一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体可管理多个项目，则实体“项目主管项目主管”与实体与实体“项目项目”的联系属于的联系属于 【4】 的联系。的联系。n数据库设计分为以下数据库设计分为以下6个设计阶段：需求分析

123、个设计阶段：需求分析阶段、阶段、 【5】 、逻辑设计阶段、物理设计阶、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。段、实施阶段、运行和维护阶段。关系模型关系模型1：n概念设计概念设计134n关系操作的特点是关系操作的特点是 【5】 操作。操作。n 数据模型按不同应用层次分成数据模型按不同应用层次分成3种类型，它们种类型，它们是概念数据模型、是概念数据模型、 【5】 和物理数据模型。和物理数据模型。n 当数据的物理结构当数据的物理结构(存储结构、存取方式等存储结构、存取方式等) 改变时，不影响数据库的逻辑结构，从而不致改变时，不影响数据库的逻辑结构，从而不致引起应用程序的变化，这是指数

124、据的引起应用程序的变化，这是指数据的 【5】 。集合集合逻辑数据模型逻辑数据模型物理独立性物理独立性135n 数据库恢复是将数据库从数据库恢复是将数据库从 【4】 状态恢复到某一已知的正确状态恢复到某一已知的正确状态。状态。 n实体之间的联系可以归结为一对一联系、一对多实体之间的联系可以归结为一对一联系、一对多(或多对多或多对多) 的联系与多对多联系。如果一个学校有许多教师，而一个教的联系与多对多联系。如果一个学校有许多教师，而一个教师只归属于一个学校，则实体集学校与实体集教师之间的联师只归属于一个学校，则实体集学校与实体集教师之间的联系属于系属于 【5】 的联系。的联系。错误错误1:nn数据

125、独立性分逻辑独立性与物理独立性。当数据的存储结构改变数据独立性分逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为修改，称为_。n数据库系统中实现各种数据管理功能的核心软件称为数据库系统中实现各种数据管理功能的核心软件称为_。n关系模型的完整性规则是对关系的某种约束条件，包括实体完整关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、性、_和自定义完整性。和自定义完整性。n在关系模型中，把数据看成一个二维表，每个二维表称为一个在关系模型中，把数据看成一个二维表，每个二维表称为一个_。物理独立性物理独立性DBMS参照完整性参照完整性关系关系