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

1、全国计算机等级考试 二级公共基础知识主讲人：韩静2020年8月6日星期四,基本要求,1. 掌握算法的基本概念。 2. 掌握基本数据结构及其操作。 3. 掌握基本排序和查找算法。 4. 掌握逐步求精的结构化程序设计方法。 5. 掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。 6. 掌握数据库的基本知识，了解关系数据库的设计。,一、 基本数据结构与算法,1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算

2、。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,二、 程序设计基础,1. 程序设计方法与风格。 2. 结构化程序设计。 3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。,三、 软件工程基础,1. 软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。 2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3. 结构化设计方法，总体

3、设计与详细设计。 4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5. 程序的调试，静态调试与动态调试。,四、数据库设计基础,1. 数据库的基本概念：数据库，数据库管理系统，数据库系统。 2. 数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4. 数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。,考试方式,1、 公共基础的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、V

4、isual C+）的笔试部分合为一张试卷。公共基础部分占全卷的30分。 2、 公共基础知识有10道选择题和5道填空题。,学习方法,理解基本概念 多做练习 适当记忆一些名词 与所学的VFPcAccess程序设计知识结合起来，以增加对知识的理解能力,9,1. 基本数据结构与算法,10,算法的基本特征: (1)可行性 (2)确定性 (3)有穷性 (4)输入和输出（拥有足够的情报）,1.1 算法,11,1.2 算法复杂度,1.2.1 时间复杂度 是指执行算法所需要的计算工作量。 通常有事后统计法和事前分析估算法。 算法在执行过程中所需基本运算的执行次数来度量算法的工作量. 算法所执行的基本运算次数与问

5、题的规模n有关.,执行算法所需要的计算工作量和f(n)同步增长，记为:,算法的工作量=f(n),时间复杂度=O(f(n),12,1.2.2 算法的空间复杂度 一般是指执行这个算法所需要的内存空间 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间 一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。,13,算法的时间复杂度是指 A) 执行算法程序所需要的时间 B) 算法程序的长度 C) 算法执行过程中所需要的基本运算次数 D) 算法程

6、序中的指令条数 算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。 算法的空间复杂度是指 A) 算法程序的长度 B) 算法程序中的指令条数 C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间 在计算机中，算法是指 A) 加工方法B) 解题方案的准确而完整的描述 C) 排序方法D) 查询方法,例题讲解,有穷性,14,算法分析的目的是 A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进 算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【1】 。,时间复杂度和空间复杂度,15,1.2 数据结

7、构,数据结构的定义 数据的逻辑结构和存储结构 数据结构的图形表示 线性结构与非线性结构,16,1.2.1 数据结构研究的主要内容,(1)数据集中数据之间的逻辑关系,(2)数据的存储结构,(3)各种数据结构的运算,17,（1）数据元素(Data Element),数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元数可由若干数据项(Data Item)组成。数据项是数据的最小单位。,数据元素亦称节点或记录。,18,19,A.线性结构,(A , B , C , ，X ,Y , Z),例:学生成绩表,线性表,栈后进先出 队列先进先出,例:英文字母表,20,树形结构,例:全校学生档案管理的组

8、织方式,例:计算机文件管理系统也是典型的树形结构,B非线性结构,21,例:数据结构B(D,R) D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3), (3,4) , (2,4) ,例:数据结构C(D,R) D= 1 , 2 , 3 R= , , , ,图形结构,22,Loc(ai)=Lo+（i-1)*m,1、顺序存储,每个元素所占用 的存储单元个数,（3）存储结构,23,例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang),顺序存储结构：,顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点

9、: 1.随机存取。 2.作插入或删除操作时，需移动大量元数。 3.长度变化较大时，需按最大空间分配。 4.表的容量难以扩充。,24,2、链式存储,每个节点都由两部分组成： 数据域和指针域。 数据域存放元素本身的数据， 指针域存放指针。 数据元素之间逻辑上的联系由指针来体现。,例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang),链式存储结构：,25,通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。,26,1.比顺序存储结构多用空间(存储密度小) (每个节点都由数据域和指针域组成)。 2.逻辑上相邻的节点物理上不必相邻。 3.插入、删除

10、灵活 (不必移动节点，只要改变节点中的指针)。 4.非随机存取。,链接存储结构特点：,27,链表不具有的特点是 A) 不必事先估计存储空间 B) 可随机访问任一元素 C) 插入删除不需要移动元素 D) 所需空间与线性表长度成正比 数据结构分为逻辑结构与存储结构，线性链表属于 【1】 。 数据结构中，与所使用的计算机无关的是数据的 A) 存储结构B) 物理结构 C) 逻辑结构D) 物理和存储结构 数据的逻辑结构有线性结构和 【1】 两大类。 数据的存储结构是指 A）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示 C）数据在计算机中的顺序存储方式 D）存储在外存中的数据,例题讲解,存储结构

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

12、前后件关系的复杂程度，一般将数据结构分成 A) 动态结构和静态结构 B) 紧凑结构和非紧凑结构 C) 线性结构和非线性结构 D) 内部结构和外部结构 数据结构包括数据的逻辑结构、数据的 【2】 以及对数据的操作运算。 数据的基本单位是 【5】 。 下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构,存储结构,数据元素,30,1.7 栈和队列,1.7.1 栈和队列的定义 栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称

13、为限定性的数据结构。,31,1 .栈,栈是限定仅在表尾进行插入或删除操作的线性表。 栈顶表尾。 栈底表头。 空栈不含元素的空表。,进栈,出栈,栈s=(a1,a2,an),后进先出（LIFO）,32,3. 队列 定义：一种特殊的线性结构，限定只能在表的一端进行插入，在 表的另一端进行删除的线性表 。此种结构称为先进先出（FIFO）表。,33,栈和队列的共同特点是 A)都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e

14、2D) 任意顺序 一些重要的程序语言(如C语言和Pascal语言) 允许过程的递归调用。而实现递归调用中的存储分配通常用 A) 栈B) 堆 C) 数组 D) 链表,例题讲解,34,栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 栈通常采用的两种存储结构是 A) 线性存储结构和链表存储结构B) 散列方式和索引方式 C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构 栈和队列通常采用的存储结构是 【1】 。 下列数据结构中，按先进后出原则组织数据的是 A) 线性链表 B

15、) 栈 C) 循环链表 D) 顺序表 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为 【2】 。,链表存储结构和数组,上溢,35,由两个栈共享一个存储空间的好处是 A) 减少存取时间，降低下溢发生的机率 B) 节省存储空间，降低上溢发生的机率 C) 减少存取时间，降低上溢发生的机率 D) 节省存储空间，降低下溢发生的机率 下列关于栈的叙述中正确的是 ）在栈中只能插入数据 B）在栈中只能删除数据 C）栈是先进先出的线性表 D）栈是后进先出的线性表 下列关于队列的叙述中正确的是 ）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线性表

16、D）队列是后进先出的线性表,36,1.6.1 树的定义 由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。,现实世界中，能用树的结构表示的例子： 学校的行政关系、书的层次结构、人类的家族血缘关系等。,1.6 树,37,介绍几个概念： 结点（Node）：树中的元素，包含数据项及若干指向其子树的分支。 结点的度（Degree）：结点拥有的子树数。 结点的层次：从根结点开始算起，根为第一层。 叶子（Leaf）：度为零的结点，也称端结点。 孩子（Child）：结点子树的根称为该结点的孩子结点。 兄弟（Sibling）：同一双亲的孩子。 双亲（Parent）：孩子结点的上层结点

17、，称为这些结点的 双亲。 树的深度（Depth)： 树中结点的最大层次数。 树的度：结点所具有的最大的度. 森林（Forest）：M棵互不相交的树的集合。,38,1.6.2 二叉树 （Binary Tree）,1 、二叉树的定义及其性质 (1) 二叉树的定义,二叉树的五种基本形态,二叉树一种特殊的树形结构，特点是树中每个结点最多只能有两棵子树(即二叉树中不存在度大于2的结点)，且子树有左右之分，次序不能颠倒。,39,性质1:二叉树的第i层上至多有2 i-1（i 1）个结点。,(2) 二叉树的基本性质,第三层上(i=3)，有23-1=4个节点。 第四层上(i=4)，有24-1=8个节点。,性质2

18、: 深度为k的二叉树中至多含有2k-1个结点。,40,性质：对任何一棵二叉树T，如果其终端结点数为n0,度 为2的结点数为n2,则n0=n2+1。,证明： 设n1为二叉树T中度为1的结点数； 二叉树中所有结点的度均小于或等于2 其结点总数为： n=n0+n1+n2 二叉树中除了根结点外，其余结点都有一个分支进入 设分支总数为B； 则 n=B+1; 二叉树的分支是由度为1或2的结点射出的 B=n1+2*n2 n=n1+2*n2+1=n0+n1+n2 n0=n2+1,41,满二叉树,特点：每一层上都含有最大结点数。,完全二叉树,特点： (1)除最后一层外，每一层都取最 大结点数， (2)最后一层结

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

20、,2*i+1=1312 其无右孩子。,45,1.6.3 二叉树的遍历 查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。 （1）遍历定义及遍历算法 遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访 问一次。 按先左后右的原则，一般使用三种遍历： 先序遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。 中序遍历(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。 后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。,46,（2）遍历算法,先序遍历：D L R 中序遍历：L D

21、 R 后序遍历：L R D,A,D,B,C,D L R,以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,47,已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 A) acbed B) decab C) deabc D) cedba 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG 树是结点的集合，它的根结点数目是 A) 有且只有1B) 1或多于1 C) 0或1D) 至少2 下列叙述中正确的是 A) 线

22、性表是线性结构B) 栈与队列是非线性结构 C) 线性链表是非线性结构D) 二叉树是线性结构,例题讲解,48,在深度为5的满二叉树中，叶子结点的个数为 A) 32B) 31 C) 16 D) 15 若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca 在树结构中，树根结点没有 【1】 。 具有3个结点的二叉树有 A) 2种形态 B) 4种形态 C) 7种形态 D) 5种形态 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结

23、点数为 A) 12 B) 13 C) 14D) 15,双亲结点,49,设有下列二叉树： 对此二叉树前序遍历的结果为 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT 设有下列二叉树： 对此二叉树的中序遍历的结果为 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA,50,设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中的叶子结点数为 A）8 B）7 C）6 D）5 设一棵完全二叉树共有700个结点，则该二叉树中有（ ）个叶子结点。 在一个容量为15的循环队列中，若头指针front=6，尾指针r

24、ear=9，则该循环队列中共有（ ）个元素。 设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（ ）。,350,3,DEBFCA,51,1.7 查找和排序,顺序查找与二分查找算法 基本排序算法（交换类排序、选择类排序、插入类排序）,52,1.7.1 顺序查找（线性查找）,查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。 可以采用从前向后查，也可采用从后向前查的方法。 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。 最好情况：1 最坏情况：n 在下面

25、两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。,53,1.7.1 折半查找（二分法查找）,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值,则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。,54,排序方法,插入排序,选择排序,交换排序,归并排序,简单插入排序,希尔排

26、序,简单选择排序,堆排序,起泡排序,快速排序,1.7.2 排序,55,在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为 【2】 。 假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为 A) log2n B) n2 C) O(n1.5) D) n(n-1)/2,例题讲解,log2n,冒泡排序算法在最好的情况下的元素交换次数为 【1】 。 在最坏情况下，堆排序需要比较的次数为 【2】 。 排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、 【1】 和选择排序等。,0,nlog2n,交换排序,56,2.程序设计基础,57,2.1 程序设计方法与风格,2.

27、1.1 程序设计方法 结构化设计方法 面向对象程序设计方法,58,2.2 结构化程序设计,基本概念 三种基本结构 顺序结构 选择结构 循环结构 三种基本结构的特点 只有一个入口 只有一个出口 每一个基本结构中的每一部分都有机会执行到 结构内不存在“死循环”,设计原则 自顶向下（先总体，后细节） 逐步求精（设计子目标过渡） 模块化 （分解总目标） 限制使用goto语句,59,对象(Object) 对象是基本的运行时认得实体，它既包括数据（属性），也包括作用于数据的操作（行为）。 一个对象把属性和行为封装为一个整体 一个对象通常可由对象名、属性和操作3部分组成 对象的基本特性： （1）标识唯一性

28、（对象可区分） （2）分类性 （对象抽象成类） （3）多态性 （同一操作可以是不同对象的行为） （4）封装性 （只能看到对象的外部特性） （5）模块独立性好（对象内部各元素结合紧密、内聚性强）,2.3 面向对象的程序设计方法,60,类(Class)和实例 一个类定义了一组大体上相似的对象。 一个类所包含的方法和数据描述一组对象的共同行为和属性。 类是在对象之上的抽象，对象是类的具体化，是类的实例 封装(Encapsulation) 将数据和操作数据的函数衔接在一起，构成一个具有类类型的对象的描述。 对象的内部实现受保护，外界不能访问 封装简化了程序员对对象的使用,61,继承(Inheritan

29、ce) 继承是父类和子类之间共享数据的方法的机制 一个子类可以继承它的父类（或祖先类）中的属性和操作 子类中可以定义自己的属性和操作 单重继承、多重继承 多态性(Polymorphism) 不同的对象收到同一消息可以产生完全不同的结构，这一现象叫做多态性 多态的实现受到继承的支持,消息(Message) 对象之间进行通信的一种构造,62,结构化程序设计的3种结构是 A) 顺序结构、选择结构、转移结构 B) 分支结构、等价结构、循环结构 C) 多分支结构、赋值结构、等价结构 D) 顺序结构、选择结构、循环结构 在设计程序时，应采纳的原则之一是 A) 不限制goto语句的使用 B) 减少或取消注解

30、行 C) 程序越短越好 D) 程序结构应有助于读者理解 程序设计语言的基本成分是数据成分、运算成分、控制成分和 A) 对象成分B) 变量成分 C) 语句成分D) 传输成分,例题讲解,63,结构化程序设计主要强调的是 A) 程序的规模B) 程序的效率 C) 程序设计语言的先进性 D) 程序易读性 以下不属于对象的基本特点的是 A) 分类性 B) 多态性 C) 继承性D) 封装性 对建立良好的程序设计风格，下面描述正确的是 A) 程序应简单、清晰、可读性好 B) 符号名的命名只要符合语法 C) 充分考虑程序的执行效率 D) 程序的注释可有可无 在结构化程序设计思想提出之前，在程序设计中曾强调程序的

31、效率，现在，与程序的效率相比，人们更重视程序的 A) 安全性B) 一致性 C) 可理解性D) 合理性,64,程序的3种基本控制结构是 A) 过程、子过程和分程序B) 顺序、选择和重复 C) 递归、堆栈和队列 D) 调用、返回和转移 下列叙述中，不属于结构化程序设计方法的主要原则的是 A) 自顶向下 B) 由底向上 C) 模块化D) 限制使用goto语句 对象实现了数据和操作的结合，是指对数据和数据的操作进行 A) 结合 B) 隐藏 C) 封装 D) 抽象 类是一个支持集成的抽象数据类型，而对象是类的_。,实例,65,在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送 A）调用语句

32、 B）命令 C）口令 D）消息 信息屏蔽的概念与下述哪一种概念直接相关 A）软件结构定义 B）模块独立性 C）模块类型划分 D）模块偶合度 下列对象概念描述错误的是 A）任何对象都必须有继承性 B）对象是属性和方法的封装体 C）对象间的通讯靠消息传递 D）操作是对象的动态属性,66,下列叙述中，不属于结构化分析方法的是 A) 面向数据流的结构化分析方法 B) 面向数据结构的Jackson方法 C) 面向数据结构的结构化数据系统开发方法 D) 面向对象的分析方法 在面向对象的程序设计中，类描述的是具有相似性质的一组 【3】 在面向对象方法中，类之间共享属性和操作的机制称为 【2】 。 一个类可以

33、从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的 【3】 。,对象的共同行为和属性,继承,可重用性,67,面向对象的模型中，最基本的概念是对象和 【3】 。 在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为 【4】 。 在程序设计阶段应该采取 【2】 和逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，进而用某种程序设计语言写成程序。 在面向对象方法种，类之间共享属性和操作的机制称为_。,消息,自顶向下,属性、行为,继承,68,【3】 是一种信息隐蔽技术，目的在于将对象的使用者和对象的设计者分开。 可以把具有相同属性的一些不同对象归类，称为

34、【3】 。 子程序通常分为两类： 【2】 和函数，前者是命令的抽象，后者是为了求值。 源程序文档化要求程序应加注释。注释一般分为序言性注释和_。 在面向对象方法种，信息屏蔽是通过对象的_性来实现的。,封装,类,过程,功能性注释,封装,69,3.软件工程基础,70,3.1 基本概念,软件,程序 数据 相关文档,机器可执行的程序和数据,机器不能执行的，与软件开发、运行、维护、使用等有关的文档,71,软件的特点包括： （1）软件是一种逻辑实体； （2）软件的生产与硬件不同，它没有明显的制作过程； （3）软件在运行、使用期间不存在磨损、老化问题； （4）软件的开发、运行对计算机系统具有依赖性，受计算机

35、系统的限制，这导致了软件移植的问题； （5）软件复杂性高，成本昂贵； （6）软件开发涉及诸多的社会因素。 软件按功能分为： 应用软件、系统软件、支撑软件（或工具软件）。,72,1. 软件危机 早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为“软件危机”，软件工程概念的出现源自于软件危机。 软件危机主要表现在成本、质量、生产率等问题。 2. 软件工程 软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。其目的是提高软件生产率、提高软件质量、降低软件成本。 软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文

36、档、实践标准和工序。 3. 软件工程三要素 方法：完成软件工程项目的技术手段 工具：支持软件的开发、管理、文档生成 过程：支持软件开发的各个环节的控制、管理; 将方法和工具综合起来,以达到合理、及时地进行计 算机软件开发的目的。,73,4. 软件生命周期 将软件产品从提出、实现、使用、维护到停止使用退役的过程称为软件生命周期 分为软件定义、软件开发及软件运行维护3个阶段。维护是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护代价 6个活动阶段 可行性研究与计划制定：确定系统的总体目标。参加人员有用户、项目负责人和系统分析员，产生文档有可行性分析报告、项

37、目计划书等 需求分析：确定系统的逻辑模型。参加人员有用户、项目负责人和系统分析员。产生文档为需求规格说明书，其作用：（1）便于用户、开发人员进行理解交流；（2）反映用户问题的结构，可以作为软件开发工作的基础和依据；（3）作为确认测试和验收的依据。,74,软件设计：包括软件结构设计、数据设计、接口设计和过程设计。 结构设计是定义软件系统各部件之间的关系； 数据设计是将分析时创建的模型转化为数据结构的定义； 接口设计是描述软件内部、软件和操作系统之间及软件与 人之间如何通信； 过程设计是把系统结构部件转换成软件的过程性描述。 软件设计分概要设计和详细设计。 参加人员有系统分析员和高级程序员。产生的

38、文档有设计规格说明书。 软件实现：编程。高级程序员和程序员产生源程序清单 软件测试：在设计测试用例的基础上，检验软件的各个组成部分。产生软件测试计划和软件测试报告 运行与维护,75,3.2 需求分析与结构化分析方法,需求分析的方法,结构化分析方法 面向对象的分析方法,面向数据流的结构化方法(SA) 面向数据结构Jackson方法(JSD) 面向数据结构的结构化数据系统开发方法(DSSD),76,结构化分析常用工具:,(1)数据流图DFD (2)数据字典DD (3)判定树 (4)判定表,结构化分析方法的实质： 着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,

39、建立系统的逻辑模型。,77,3.3 结构化设计方法、概要设计和详细设计,软件设计 软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，软件设计是确定系统的物理模型。 软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径。 从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。 结构设计：定义软件系统各主要部件之间的关系。 数据设计：将分析时创建的模型转化为数据结构的定义。 接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。 过程设计：把系统结构部件转换成软件的过程描述。 从工程管理角度来看：概要设计和详细设计

40、。,78,软件设计的基本原理： （1）抽象 （2）模块化 （3）信息隐蔽 （4）模块独立化 内聚性： 耦合性：,在程序结构中各模块的内聚性越强，则耦合性越弱。 优秀软件应高内聚，低耦合。,79,3.3.2 概要设计 设计的基本任务 软件的系统结构 数据结构和数据库设计 编写概要设计文档 概要设计文档评审,80,概要设计的方法:,结构图（SC)：,概要设计(软件结构设计)的工具:,81,3.3.3 详细设计 根本目标 确定应用怎样具体的实现所要求的系统，不是具体的编写程序，而是要设计程序的“蓝图” 详细设计常用的设计工具（工程设计工具）： 图形工具： 程序流程图：箭头表示控制流，方框表示加工步骤

41、，菱形表示逻辑条件。 N-S图：有五种基本图形。 PAD图：问题分析图，有五种基本图型。 表格工具：判定表。 语言工具：PDL过程设计语言（结构化的英语和伪码）。,82,3.4 软件测试,软件测试定义： 使用人工或自动手段来运行或测定某个系统的过程3.4.1 意义目的 为了发现错误 希望能以最少的人力和时间发现潜在的各种错误和缺陷 保证系统质量和可靠性的关键步骤 3.4.2 测试方法 静态测试：包括代码检查、静态结构分析、代码质量度量。 不实际运行软件，主要通过人工进行。 动态测试：是基于计算机的测试。 主要包括白盒测试方法和黑盒测试方法。,83,3.4.3 白盒测试 结构测试 将软件看成透明

42、的白盒，根据程序的内部结构和逻辑结构来设计测试例子，对程序的路径和过程进行测试，检查是否满足设计的要求 主要方法：逻辑覆盖、基本路径测试 3.4.4 黑盒测试 功能测试 将软件看成黑盒子，在完全不考虑软件内部结构和特性的情况下，测试软件的外部特性 主要方法：等价类划分法、边界值分析法、错误推测法,84,3.5 程序调试,1 任务 根据测试时发现的错误， （）找出原因和具体的位置 （）进行改正，排除错误 由程序开发人员来进行，谁开发的程序就由谁来进行调试,2. 程序调试的基本步骤： （1）错误定位； （2）修改设计和代码，以排除错误； （3）进行回归测试，防止引进新的错误。,3.调试方法：（静态

43、、动态调试法） 强行排错法 回溯法 原因排除法（演绎、归纳、二分法),85,为了提高测试的效率，应该 A) 随机选取测试数据 B) 取一切可能的输入数据作为测试数据 C) 在完成编码以后制定软件的测试计划 D) 集中对付那些错误群集的程序 软件生命周期中所花费用最多的阶段是 A) 详细设计 B) 软件编码 C) 软件测试 D) 软件维护 下列叙述中，不属于软件需求规格说明书的作用的是 A) 便于用户、开发人员进行理解和交流 B) 反映出用户问题的结构，可以作为软件开发工作的基础和依据 C) 作为确认测试和验收的依据 D) 便于开发人员进行需求分析 下列不属于软件工程的3个要素的是 ) 工具)

44、过程 ) 方法) 环境,例题讲解,86,软件设计包括软件的结构、数据、接口和过程设计，其中软件的过程设计是指 A) 模块间的关系B) 系统结构部件转换成软件的过程描述 C) 软件层次结构D) 软件开发过程 检查软件产品是否符合需求定义的过程称为 ) 确认测试 ) 集成测试 ) 验证测试 ) 验收测试 数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是 ) 控制流 ) 加工 ) 数据存储 ) 源和流,87,开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现象称作 A) 软件投机 B) 软件危机 C) 软件工程 D) 软件产

45、生 下面不属于软件设计原则的是 ) 抽象) 模块化 ) 自底向上 ) 信息隐蔽 开发大型软件时，产生困难的根本原因是 A) 大系统的复杂性B) 人员知识不足 C) 客观世界千变万化D) 时间紧、任务重 软件工程的出现是由于 A) 程序设计方法学的影响B) 软件产业化的需要 C) 软件危机的出现D) 计算机的发展,88,软件开发离不开系统环境资源的支持，其中必要的测试数据属于 A) 硬件资源 B) 通信资源 C) 支持软件 D) 辅助资源 在数据流图(DFD) 中，带有名字的箭头表示 A) 模块之间的调用关系B) 程序的组成成分 C) 控制程序的执行顺序D) 数据的流向 下列不属于结构化分析的常

46、用工具的是 A) 数据流图 B) 数据字典 C) 判定树 D) PAD图 在软件生产过程中，需求信息的给出者是 A) 程序员 B) 项目管理者 C) 软件分析设计人员 D) 软件用户,89,下列工具不是过程设计常用工具的是 ) PAD) PFD ) N-S) DFD 模块独立性是软件模块化所提出的要求，衡量模块独立性的度量标准则是模块的 A) 抽象和信息隐蔽 B) 局部化和封装化 C) 内聚性和耦合性 D) 激活机制和控制方法 软件开发的结构化生命周期方法将软件生命周期划分成 A) 定义、开发、运行维护 B) 设计阶段、编程阶段、测试阶段 C) 总体设计、详细设计、编程调试 D) 需求分析、功

47、能定义、系统设计,90,在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是 A) 路径的集合 B) 循环的集合 C) 目标的集合 D) 地址的集合 完全不考虑程序的内部结构和内部特征，而只是根据程序功能导出测试用例的测试方法是 A) 黑箱测试法 B) 白箱测试法 C) 错误推测法 D) 安装测试法 在结构化设计方法中，生成的结构图(SC) 中，带有箭头的连线表示 A) 模块之间的调用关系B) 程序的组成成分 C) 控制程序的执行顺序D) 数据的流向,91,下列选项中，不属于模块间耦合的是 A) 数据耦合 B) 同构耦合 C) 异构耦合 D) 公用耦合 下列叙述中，不属于测试的

48、特征的是 A) 测试的挑剔性B) 完全测试的不可能性 C) 测试的可靠性D) 测试的经济性 需求分析中开发人员要从用户那里了解 A) 软件做什么B) 用户使用界面 C) 输入的信息D) 软件的规模 下列不属于软件调试技术的是 A) 强行排错法B) 集成测试法 C) 回溯法D) 原因排除法,92,为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为 A) PAD图B) N-S图 C) 结构图D) 数据流图 软件复杂性度量的参数包括 A) 效率B) 规模 C) 完整性D) 容错性 下列叙述中，正确的是 A) 软件就是程序清单 B) 软件就是存放在计算机中

49、的文件 C) 软件应包括程序清单及运行结果 D) 软件包括程序和文档 软件设计中，有利于提高模块独立性的一个准则是 A) 低内聚低耦合B) 低内聚高耦合 C) 高内聚低耦合D) 高内聚高耦合,93,软件生命周期中花费时间最多的阶段是 A) 详细设计 B) 软件编码 C) 软件测试 D) 软件维护 下列叙述中，不属于结构化分析方法的是 A) 面向数据流的结构化分析方法 B) 面向数据结构的Jackson方法 C) 面向数据结构的结构化数据系统开发方法 D) 面向对象的分析方法 详细设计的结果基本决定了最终程序的 A) 代码的规模 B) 运行速度 C) 质量 D) 可维护性 下列不属于静态测试方法

50、的是 A) 代码检查B) 白盒法 C) 静态结构分析D) 代码质量度量,94,在软件生命周期中，能准确地确定软件系统必须做什么和必须局别哪些功能的阶段是 A）概要设计 B）详细设计 C）可行性分析 D）需求分析 检查软件产品是否符合需求定义的过程称为 A）确认测试 B）集成测试 C）验证测试 D）验收测试 数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成，下列图符名标识的图符不属于数据流图合法图符的是 A）控制流 B）加工 C）数据存储 D）源和潭,95,下面不属于软件设计原则的是 A）抽象 B）模块化 C）自底向上 D）信息屏蔽 程序流程图（PFD）中的箭头代表的是 A）

51、数据流 B）控制流 C）调用关系 D）组成关系 下列工具中为需求分析常用工具的是 A）PAD B）PFD C）N-S D）DFD 在结构化方法中，软件功能分解属于下列软件开发中的阶段是 A）详细设计 B）需求分析 C）总体设计 D）编程调试,96,软件调试的目的是 A）发现错误 B）改正错误 C）改善软件的性能 D）挖掘软件的潜能 软件需求分析阶段的工作，可以分为四个方面：需求获取，需求分析，编写需求规格说明书，以及 A）阶段性报告 B）需求评审 C）总结 D）都不正确,软件是程序、数据和_的集合。 Jackson方法是一种面向_的结构化方法。 软件工程研究的内容主要包括：_技术和软件工程管理

52、。,文档,数据结构,软件开发,97,通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为 【4】 。 耦合和内聚是评价模块独立性的两个主要标准，其中 【3】 反映了模块内各成分之间的联系。 软件工程研究的内容主要包括： 【4】 技术和软件工程管理。 软件设计模块化的目的是 【4】 。,软件生命周期,耦合,软件开发,降低复杂性,98,4.数据库设计基础,99,4.1 基本概念,1. 数据(Data) 实际上就是描述事物的符号记录 软件中的数据是有一定结构的 2. 数据库(DB) 长期存储在计算机内的，有组织的，可共享的数据集合。 数据库中的数据按一定的数学模型组织、描述和存储，具有较小

53、的冗余度，较高的数据独立性和易扩展性，并可为各种用户共享。,100,3. 数据库管理系统(DBMS) 数据库系统的核心软件 要在操作系统支持下工作 解决如何科学地组织和存储数据，如何高效的获取和维护数据的系统软件 主要功能包括 数据模式定义 数据操纵 数据的完整性、安全性定义与检查 数据库的并发控制与故障恢复 数据的服务 为完成上述功能，DBMS一般提供相应的数据语言： 数据定义语言（DDL） 数据操纵语言（DML） 数据控制语言（DCL） 数据语言按其使用方式具有两种结构形式 交互式命令语言 宿主型语言,101,4. 数据库管理员 主要工作包括： 数据库设计 数据库维护 改善系统性能，提高系

54、统效率,5. 数据库系统（DBS） 由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、系统平台之硬件平台（硬件）和软件平台（软件）构成。 6. 数据库应用系统（DBAS） 利用数据库系统进行应用开发 7. 数据库管理技术的发展 人工管理阶段 文件系统阶段 数据库系统阶段（层次、网状、关系）,102,8. 数据库系统的基本特点 数据的集成性 采用统一的数据结构方式 按照多个应用的需要组主全局的统一的数据结构 数据模式是多个应用共同的、全局的数据结构 数据的高共享性与低冗余性 数据独立性 物理独立性和逻辑独立性 数据统一管理与控制 数据的完整性检查 数据的安全性检查 并发控制,103

55、,9. 数据库系统的内部结构体系 数据库系统的三级模式 （1）概念模式 （2）外模式 （3）内模式 内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式 概念模式处于中层，它放映了设计者的数据全局逻辑要求 外模式处于最外层，它反映了用户对数据的要求,104,一、外模式/模式映象,数据的逻辑独立性：当模式改变时，由 外模式/模式映象 作相应的改变，可以保持外模式不变。应用程序是依据数 据的外模式编写的，从而应用程序不必修改，保证了数据 与 程序的逻辑独立性。,数据的物理独立性：当内模式改变时， 由 模式/内模式映 象作相应的改变，可以保持模式不变。从而应用程序也不 必改变，保证了数据与

56、程序的物理独立性。,二、模式/内模式映象,105,4.2 数据模型,数据模型：,是现实世界数据特征的抽象。 在数据库中用数据模型这个工具来抽象、表示和处理现实世界中的数据和信息。 通俗地讲数据模型就是现实世界的模拟。,数据模型应满足三方面的要求：,（1）能比较真实地模拟现实世界。 （2）容易为人理解。 （3）便于在计算机上实现。,106,4.2.1 数据模型的基本概念 数据模型是数据特性的抽象 数据模型描述的内容 数据结构 数据操作 数据约束 数据模型按不同的应用层次分成三种类型 概念数据模型（概念模型） 逻辑数据模型（数据模型） 物理数据模型（物理模型）,E-R图、扩充的E-R图。,层次模型

57、 网状模型 关系模型 面向对象,107,4.2.2 E-R模型（实体联系模型） 基本概念 （1）实体 （2）属性 （3）联系 一对一（1：1） 一对多（1：M或M：1） 多对多（M：N）,108,运算符,集合运算:,专门的关系运算:,比较运算: = ,逻辑运算:,4.3 关系代数,109,设关系R和关系S具有相同的目n,且相应的属性取自同一个域,则可有如下定义:,1.并,2.差,3.交,传统的集合运算,110,例子:,111,112,RS,4.笛卡儿,113,专门的关系运算：,1.选择,例子1:查询信息系(IS系)的全体学生.,114,2.投影,例子4:查询学生的姓名和所在系.,115,3.连

58、接,例子:,说明:（1）A和B分别是R和S上度相等且可比的属性组。 （2） 是比较运算符。,116,等值连接:当连接条件为“=”时的连接运算.,a2 b3 8 b3 10,a2 b3 8 b3 2,117,自然连接:是一种特殊的等值连接,它要求两个关系中进行 比较的分量是相同的属性组,并且在结果中把重 复的属性列去掉.,118,4.4 数据库设计与管理 4.4.1 数据库设计概述 设计一个能满足用户要求，性能良好的数据库 基本任务：根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式 两种方法： 以信息需求为主，兼顾处理需求（面向数据的方法） 以处理需求为主，兼顾信息需求（面向过程的方法） 面向数据的设计方法已成为主流方法,119,数据库设计目前一般采用生命周期法，分若干阶段 需求