1、123二级公共基础知识考试内容分四大部分：二级公共基础知识考试内容分四大部分：基本数据结构与算法基本数据结构与算法 程序设计基础程序设计基础 软件工程基础软件工程基础 数据库设计基础数据库设计基础41 1、算法的基本概念、算法的基本概念 算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有有穷性有穷性、确定性确定性、可行性可行性、输入输入和输出输出（拥有足够的情报）等个重要特性。52 2、算法的控制结构、算法的控制结构 一个算法一般可以用一个算法一般可以用顺序、选择、循环顺序、选择、循环三种基本结构三种基本结构 组合而成。组合而成。3 3、算法的描述方式、算法
2、的描述方式 描述算法的工具通常有描述算法的工具通常有程序流程图、程序流程图、N-SN-S结构化流程结构化流程图、算法描述语言图、算法描述语言等；等；6算法描述程序流程图7算法描述N-S结构化流程图81 1、时间复杂度、时间复杂度v 依据算法编制的程序在计算机上运行时所消耗的时间 来度量。通常有事后统计法和事前分析估算法。v 算法中基本操作重复执行次数重复执行次数n n和算法执行时间同步 增长，称作算法的时间复杂度时间复杂度。92 2、空间复杂度、空间复杂度v 一般是指执行这个算法所需要的执行这个算法所需要的内存空间内存空间。v 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占
3、的存储空间以及某种数据结构所需 要的附加存储空间。10一、选择题一、选择题1 1、算法的时间复杂度是指、算法的时间复杂度是指()2010.32010.3真题真题 A A、执行算法程序所需要的时间执行算法程序所需要的时间 B B、算法所处理的数据量算法所处理的数据量 C C、算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D D、算法程序中的语句或指令条数算法程序中的语句或指令条数2 2、算法的空间复杂度是指、算法的空间复杂度是指()()全真模拟题全真模拟题 A)A)算法程序的长度算法程序的长度 B)B)算法程序中的指令条数算法程序中的指令条数 C)C)算法程序所占的存储空
4、间算法程序所占的存储空间 D)D)执行过程中所需要的存储空间执行过程中所需要的存储空间 113、在计算机中，算法是指（）全真模拟题全真模拟题 A)加工方法 B)B)解题方案的准确而完整的描述解题方案的准确而完整的描述 C)排序方法 D)查询方法4、算法分析的目的是()全真模拟题 A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性 D)D)分析算法的效率以求改进分析算法的效率以求改进 125 5、算法的有穷性是指、算法的有穷性是指()2008.42008.4真题真题 A)A)算法程序的运行时间是有限的算法程序的运行时间是有限的 B)B)算法程序所处理的数据
5、量是有限的算法程序所处理的数据量是有限的 C)C)算法程序的长度是有限的算法程序的长度是有限的 D)D)算法只能被有限的用户所使用算法只能被有限的用户所使用 13Data Structure1 1、数据结构研究的主要内容、数据结构研究的主要内容14 学 生 基 本 情 况 学 号 姓 名 性 别 出 生 年 月 .99070101 李 军 男 80 12.99070102 王 颜 霞 女 81 2.99070103 孙 涛 男 80 9.99070104 单 晓 宏 男 81 3.特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着
6、一种前后关系，这就是我们所说的线性结构；v 应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。15v 应用举例2家庭血缘关系图 表示家庭成员的辈分关系，使用下图1-1所示的形式描述。3 1 21 3 21 2 31 23 2 12 3 12 1 32 11家庭血缘关系图特点：在求解过程中，所处理的数据之间具有层次关系，这是我们 所说的树形结构树形结构；。v 应用举例3制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：计算机专业学生的必修课程 课课
7、程程编编号号 课课程程名名称称 需需要要的的先先导导 课课程程编编号号 C 1 程序设计基础 无 C 2 离散数学 C 1 C 3 数据结构 C 1，C 2 C 4 汇编语言 C 1 C 5 算法分析与设计 C 3，C 4 C 6 计算机组成原理 C 1 1 C 7 编译原理 C 5，C 3 C 8 操作系统 C 3，C 6 C 9 高等数学 无 C 1 0 线性代数 C 9 C 1 1 普通物理 C 9 C 1 2 数值分析 C 9，C 1 0，C 1 16这种数据可以用下面的图来表示：v 课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图 1-2 计算机专业
8、必修课程开设先后关系1718v 线性结构与非线性结构：线性结构与非线性结构：v 线性结构：有且只有一个根结点；每一个线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。结点最多有一个前件，也最多有一个后件。如：一年四季，如：一年四季，2626个英文字母个英文字母v非线性结构：线性以外的数据结构。非线性结构：线性以外的数据结构。如：反映家庭成员间辈分关系的数据结构如：反映家庭成员间辈分关系的数据结构 1 1、数据的、数据的逻辑结构逻辑结构 2 2、数据的、数据的存储结构存储结构 3 3、数据的、数据的运算运算：检索、排序、插入、删除、修改等。：检索、排序、插入、删除、修改等
9、。A A线性结构线性结构B B非线性结构非线性结构A A顺序存储顺序存储 B B链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面(亦称物理结构亦称物理结构)数据结构的主要研究问题：19203 3、例题讲解、例题讲解v 数据处理的最小单位是数据处理的最小单位是(C C )A)A)数据数据 B)B)数据元素数据元素 C)C)数据项数据项 D)D)数据结构数据结构v 数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 以及对数据的以及对数据的操作运算。操作运算。【答案【答案】物理结构（或存储结构）物理结构（或存储结构）21v
10、 数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的()()A)A)存储结构存储结构B)B)物理结构物理结构 C)C)逻辑结构逻辑结构D)D)物理和存储结构物理和存储结构 数据的存储结构是指（数据的存储结构是指（）A A）数据所占的存储空间数据所占的存储空间 B B）数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示 C C）数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D D）存储在外存中的数据存储在外存中的数据 22 根据数据结构中各数据元素之间前后件关系的复杂程度，一般根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构
11、分成将数据结构分成()()A)A)动态结构和静态结构动态结构和静态结构 B)B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C)C)线性结构和非线性结构线性结构和非线性结构 D)D)内部结构和外部结构内部结构和外部结构22 23v 线性表的特点：线性表的特点：1 1、线性表中所有元素的性质相同。、线性表中所有元素的性质相同。2 2、除第一个和最后一个数据元素之外，其它数据元素有且、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个仅有一个前驱前驱和一个和一个后继后继。第一个数据元素无前驱，最。第一个数据元素无前驱，最 后一个数据元素无后继。后一个数据元素无后继。3 3、数据元素在表中的位
12、置只取决于它自身的序号。、数据元素在表中的位置只取决于它自身的序号。v 在线性表上常用的运算有：在线性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、检索、排序初始化、求长度、取元素、修改、前插、删除、检索、排序24学学 生生 成成 绩绩 表表 (按成绩排列按成绩排列)86胡孝臣986110395刘忠赏9861107100张卓9861109成 绩姓 名学 号25顺顺序序存存储储存储地址存储地址存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素元素1 1位置位置n nv 线性表的线性表的 顺序存储结构顺序存储结构：各数据元素在存储各数据元素在存储空间中是空间中是按逻辑
13、顺按逻辑顺序依次存放序依次存放的的位置位置i i所有元素所占的存所有元素所占的存储空间是连续的。储空间是连续的。v插入运算插入运算.a2a a1 1an.ai+1ai01i-1in-1a ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai i x x a ai-1i-1.a a2 2 a a1 1 X X a ai ia ai+1i+1.a alengtlength h 插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：1n1iis2n1)i(n1n1E26在进行删
14、除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平做插入或删除操作时，平均需要移动大约一半的数据元素均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。n1idl21ni)(nn1Ev删除算法的分析删除算法的分析27q 线性表的例题讲解线性表的例题讲解v 长度为长度为n n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元 素概率都相等时，插入一个元素所需移动元素的平均个数素概率都相等时，插入一个元素所需移动元素的平
15、均个数 为为()()。A)n B)n/2 C A)n B)n/2 C）(n+1)/2 D)(n-1)/2(n+1)/2 D)(n-1)/2 v 线性表线性表L=(a1,a2,a3,L=(a1,a2,a3,aiai，an)an)，下列说法正确的是（下列说法正确的是（）A)A)每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B)B)线性表中至少要有一个元素线性表中至少要有一个元素 C)C)表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D)D)除第一个元素和最后一个元素外，其余每个元素都有一除第一个元素和最后一个元素外，其余每个元素都
16、有一 个且只有一个直接前件和直接后件个且只有一个直接前件和直接后件 28 29v线性链表的基本概念：线性链表的基本概念：线性表的链式存储结构称为线性链表。1、比顺序存储结构更占空间(每个节点都由数据域和指针域组成)。2、逻辑上相邻的节点物理上不必相邻。3、插入、删除灵活(不必移动节点，只要改变节点中的指针)。v 链式存储结构特点：链式存储结构特点：30head138265129676328282138212963282null110275 12961102线性链表的插入线性链表的插入表中位置表中位置31head138265129676328282138212963282null若要插入到表头若
17、要插入到表头11795111791382若要插入到表尾若要插入到表尾head138265129676328282138212963282null141199null1411线性链表的插入线性链表的插入表头或表尾表头或表尾3232 循环链表的结构与前面所讨论的线性链表相比，具有以下循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：两个特点：循环链表的头指针指向表头结点。循环链表的头指针指向表头结点。在循环链表中，所有结点的指针构成了一个环状链。在循环链表中，所有结点的指针构成了一个环状链。图图2.292.29是循环链表的示意图。是循环链表的示意图。v循环链表：循环链表：33v链表不具有
18、的特点是（链表不具有的特点是（）A)A)不必事先估计存储空间不必事先估计存储空间 B)B)可随机访问任一元素可随机访问任一元素 C)C)插入删除不需要移动元素插入删除不需要移动元素 D)D)所需空间与线性表长度成正比所需空间与线性表长度成正比v数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1 1】。【答案【答案】存储结构存储结构 2010.92010.9真题真题q 线性链表的例题讲解线性链表的例题讲解34 35 栈和队列栈和队列是两种特殊的线性表是两种特殊的线性表堆栈：堆栈：限定限定只能在表的一端进行插入和删除只能在表的一端进行插入和删除的特殊的线
19、性表的特殊的线性表,此种此种 结构称为结构称为后进先出后进先出。栈顶（栈顶（top)top)：允许插入和删除的一端；允许插入和删除的一端；约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。栈底栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。a1 a2 .an进栈进栈出栈出栈栈顶栈顶栈底栈底36队列：队列：只能在表的只能在表的一端一端进行插入，在表的进行插入，在表的另一端另一端进行删除的进行删除的线线性表性表 。此种结构称为。此种结构称为先进先出（先进先出（FIFO）表表。a1 ,a2 ,a3 ,a4 ,an-1 ,an队队
20、 列列 示示 意意 图图队头队头队尾队尾栈和队列栈和队列37q 堆栈和队列的例题讲解堆栈和队列的例题讲解v栈和队列的共同特点是（栈和队列的共同特点是（）A)A)都是先进先出都是先进先出 B)B)都是先进后出都是先进后出 C)C)只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D)D)没有共同点没有共同点v如果进栈序列为如果进栈序列为e1,e2,e3,e4e1,e2,e3,e4，则可能的出栈序列是（则可能的出栈序列是（）A)e3,e1,e4,e2 B)e4,e3,e2,e1 A)e3,e1,e4,e2 B)e4,e3,e2,e1 C)e3,e4,e1,e2 C)e3,e4,e1,e2
21、D)D)任意顺序任意顺序v支持子程序调用或递归调用的数据结构是（支持子程序调用或递归调用的数据结构是（A A ）A)A)栈栈 B)B)堆堆 C)C)数组数组 D)D)链表链表 3738v 栈底至栈顶依次存放元素栈底至栈顶依次存放元素A A、B B、C C、D D，在第五个元素在第五个元素E E 入栈前，栈中元素可以出栈，则出栈序列可能是（入栈前，栈中元素可以出栈，则出栈序列可能是（）A)ABCEDA)ABCED B)DCBEA B)DCBEA C)DBCEA C)DBCEA D)CDABE D)CDABE v 下列数据结构中，按先进后出原则组织数据的是（下列数据结构中，按先进后出原则组织数据的
22、是（）A)A)线性链表线性链表 B)B)栈栈 C)C)循环链表循环链表 D)D)顺序表顺序表 q 堆栈和队列的例题讲解堆栈和队列的例题讲解39非线性结构非线性结构深度为深度为4 4结点的度：结点的度：拥有子树的个数拥有子树的个数例如：例如：A A的度为的度为3 3，C C的度为的度为1 1 二叉树的每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。v 二叉树（二叉树（Binary TreeBinary Tree）：）：40性质性质1 1：在任意一棵二叉树中，度为0的结点 （即叶子结点）总是比度为2的结点多 一个。例子例子1 1：某二叉树中度为2的结点有18个，则 该二叉树中有 个叶子
23、结点。例子例子2:2:某二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有 个结点。2010.9真题二叉树的性质：二叉树的性质：411919252542性质性质2 2：二叉树的第i层上至多有2 i-1（i 1）个结点二叉树的性质：二叉树的性质：423167891011121314155第三层上(i=3)，有23-1=4个节点。第四层上(i=4)，有24-1=8个节点。43二叉树的性质：二叉树的性质：性质性质3 3：深度为深度为h h的二叉树中至多含有的二叉树中至多含有2 2h h-1-1个结点个结点423167891011121314155此树的深度此树的深度h=4h=4，共有共有2
24、 24 4-1=15-1=15个节点。个节点。44v 满二叉树的特点：满二叉树的特点：每一层上都含有最大结点数。每一层上都含有最大结点数。4445v 例题讲解例题讲解1、在深度为5的满二叉树中，叶子结点的 个数为（）2008.4真题 A)32 B)31 C)16 D)15 v二叉树的遍历二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为三种：前序前序遍历、中中序序遍历、后序后序遍历。前序：前序：根根左右左右 中序：中序：左左根根右右 后序：后序：左右左右根根）46474748答案：答案：C C 49几种排序算法的比较几种排序算法的比较1 1、下列排序方法中，最坏
25、情况下比较次数最少的是（、下列排序方法中，最坏情况下比较次数最少的是（）2009.32009.3真题真题A A、冒泡排序冒泡排序 B B、简单选择排序简单选择排序C C、直接插入排序、直接插入排序 D D、堆排序、堆排序 2 2、对长度为、对长度为n n的线性表进行排序，最坏情况下比较次数不是的线性表进行排序，最坏情况下比较次数不是n(n-1)/2n(n-1)/2的排序方法是（的排序方法是（）2008.42008.4真题真题A A、冒泡排序冒泡排序 B B、简单选择排序简单选择排序C C、直接插入排序、直接插入排序 D D、堆排序、堆排序 请记忆！请记忆！冒泡排序、简单选择排序、直接插入排序的
26、冒泡排序、简单选择排序、直接插入排序的时间复杂度为时间复杂度为O O（n(n-1)/2);n(n-1)/2);堆排序的时间复杂度为堆排序的时间复杂度为O O（nlognnlogn）50第二部分第二部分 程序设计基础程序设计基础l主要考点：主要考点：考点一：结构化程序设计方法考点一：结构化程序设计方法 结构化程序设计原则：结构化程序设计原则：自顶向下、逐步求精、自顶向下、逐步求精、模块化、限制使用模块化、限制使用goto语句语句 模块设计最好做到：模块设计最好做到：高内聚，低耦合。以提高高内聚，低耦合。以提高独立性。独立性。考点二：面向对象的程序设计方法考点二：面向对象的程序设计方法51v面向对
27、象程序设计方法几个基本概念：面向对象程序设计方法几个基本概念：对象对象：在现实世界中，每个实体都是对象，例如，大在现实世界中，每个实体都是对象，例如，大学生、汽车、电视机、空调等都是现实世界中的对象学生、汽车、电视机、空调等都是现实世界中的对象属性属性：对象对象所包含的信息所包含的信息方法（操作）方法（操作）：对象：对象所能完成的操作所能完成的操作类类：一组具有相同属性和相同操作的：一组具有相同属性和相同操作的对象的集合对象的集合。继承继承：新类获得老类的某些：新类获得老类的某些方法和属性方法和属性。多态性：多态性：同样的消息被同样的消息被不同的对象接受时可导致完全不同的对象接受时可导致完全不
28、同的行动不同的行动的现象。的现象。52例题讲解：例题讲解：v 结构化程序设计的结构化程序设计的3 3种结构是（种结构是（）A)A)顺序结构、选择结构、转移结构顺序结构、选择结构、转移结构 B)B)分支结构、等价结构、循环结构分支结构、等价结构、循环结构 C)C)多分支结构、赋值结构、等价结构多分支结构、赋值结构、等价结构 D)D)顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构下列叙述中，不属于结构化程序设计方法的主要原则的是（下列叙述中，不属于结构化程序设计方法的主要原则的是（）A)A)自顶向下自顶向下 B)B)由底向上由底向上 C)C)模块化模块化D)D)限制使用限制使用gotog
29、oto语句语句 53v对象实现了对象实现了数据和操作的结合数据和操作的结合，是指对数据和数据的操作，是指对数据和数据的操作 进行（进行（）A)A)结合结合 B)B)隐藏隐藏 C)C)封装封装 D)D)抽象抽象v 在面向对象方法中，在面向对象方法中，一个对象请求另一个对象为其服务一个对象请求另一个对象为其服务的的 方式是通过发送（方式是通过发送（）A A）调用语句调用语句 B B）命令命令 C C）口令口令 D D）消息消息 542009.3真题 选择题第选择题第7 7题题552008.4真题选择题第选择题第2 2题题 562010.9真题 选择题第选择题第6 6题题57（一）基本概念（一）基本
30、概念 v 软件工程：软件工程：以工程化的原则和方法来解决软件问题的以工程化的原则和方法来解决软件问题的 工程。其目的是工程。其目的是提高软件生产率、提高软件质量、降低提高软件生产率、提高软件质量、降低 软件成本软件成本。v 软件危机：软件危机：早期的软件主要指程序，采用个体工作方式，早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为缺少相关文档，质量低，维护困难，这些问题称为“软件软件 危机危机”，软件工程概念的出现源自于软件危机。，软件工程概念的出现源自于软件危机。第三部分第三部分 软件工程基础软件工程基础v软件生命周期软件生命周期将软件产品从将软件产品从提
31、出、实现、使用维护到停止使用退役提出、实现、使用维护到停止使用退役的过的过程称为程称为软件生命周期。软件生命周期。分为分为软件定义软件定义、软件开发软件开发及及软件运行维护软件运行维护3 3个时期个时期。维护维护是是持续时间最长，花费代价最大的一个时期，软件工程学的持续时间最长，花费代价最大的一个时期，软件工程学的一个目的就是一个目的就是提高软件的可维护性，降低维护代价提高软件的可维护性，降低维护代价。v 软件工程三要素软件工程三要素 方法方法：完成软件工程项目的技术手段。：完成软件工程项目的技术手段。工具工具：支持软件的开发、管理、文档生成。：支持软件的开发、管理、文档生成。过程过程：支持软
32、件开发的各个环节的控制、管理。：支持软件开发的各个环节的控制、管理。6 6个活动阶段：个活动阶段：q可行性研究与计划制定可行性研究与计划制定：确定系统的总体目标。：确定系统的总体目标。q需求分析需求分析：数据流程图：数据流程图 DFDDFD（Data Flow DiagramData Flow Diagram）、）、数据字典数据字典DDDD（Data DictionaryData Dictionary）、判定树和判定表是）、判定树和判定表是需求分析阶段的常用工具需求分析阶段的常用工具。q软件设计软件设计：包括：包括软件结构设计软件结构设计、数据设计数据设计、接口设计接口设计和和过程设计过程设计
33、。从工程管理的角度，又可分为从工程管理的角度，又可分为概要设计概要设计和和详细设计详细设计两个阶段。两个阶段。q编码编码：产生源程序清单。：产生源程序清单。q测试测试：尽可能地发现软件潜在的错误和缺陷。：尽可能地发现软件潜在的错误和缺陷。q运行维护运行维护60（二（二）软件测试软件测试 v 意义目的意义目的 为了发现错误；为了发现错误；希望能以最少的人力和时间发现潜在的各种错希望能以最少的人力和时间发现潜在的各种错 误和缺陷；误和缺陷；保证系统质量和可靠性的关键步骤。保证系统质量和可靠性的关键步骤。v 测试方法测试方法 人工测试；人工测试；机器测试。机器测试。提问：提问：测试能否发测试能否发现
34、程序中的所有错现程序中的所有错误？误？答案：答案：不能。不能。v 白盒测试白盒测试结构测试结构测试将软件看成透明的白盒，根据程序的内部结构和逻辑结构将软件看成透明的白盒，根据程序的内部结构和逻辑结构来设计测试例子，对来设计测试例子，对程序的路径和过程进行测试程序的路径和过程进行测试，检查是，检查是否满足设计的要求否满足设计的要求v 黑盒测试黑盒测试功能测试功能测试将软件看成黑盒子，在完全不考虑软件内部结构和特性的将软件看成黑盒子，在完全不考虑软件内部结构和特性的情况下，情况下，测试软件的外部特性测试软件的外部特性v 软件测试的实施软件测试的实施单元测试单元测试（模块测试）：白盒测试法（模块测试
35、）：白盒测试法组装测试组装测试（集成测试）（集成测试）确认测试确认测试：检查软件产品是否符合需求定义，黑盒测试法：检查软件产品是否符合需求定义，黑盒测试法系统测试系统测试62（三（三）程序调试程序调试 v 任务任务根据测试时发现的错误，找出原因和具体的位置，根据测试时发现的错误，找出原因和具体的位置，进行改正进行改正，通常由程序开发人员来进行，谁开发的，通常由程序开发人员来进行，谁开发的程序就由谁来进行调试程序就由谁来进行调试v 类别类别静态调试：静态调试：通过人的思维来分析源程序代码和排错通过人的思维来分析源程序代码和排错动态调试动态调试:辅助静态调试。辅助静态调试。63（四）例题讲解（四）
36、例题讲解 v 为了提高测试的效率，应该（为了提高测试的效率，应该（）A)A)随机选取测试数据随机选取测试数据 B)B)取一切可能的输入数据作为测试数据取一切可能的输入数据作为测试数据 C)C)在完成编码以后制定软件的测试计划在完成编码以后制定软件的测试计划 D)D)选择发现错误可能性大的数据作为测试数据选择发现错误可能性大的数据作为测试数据v 软件生命周期中所花费用最多的阶段是（软件生命周期中所花费用最多的阶段是（）A)A)详细设计详细设计 B)B)软件编码软件编码 C)C)软件测试软件测试 D)D)软件维护软件维护 642009.3真题选择题第选择题第5 5题题 选择题第选择题第6 6题题
37、652010.3真题选择题第选择题第3 3题题 选择题第选择题第4 4题题 662010.3真题选择题第选择题第5 5题题 答案解析：数据流图是以图形的方式表达在问题中信息的变换和传递过程。结构化分析是面向数据流开展需求分析工作的一种有效方法，需求分析常用工具有：数据流图、需求分析常用工具有：数据流图、数据字典数据字典。672010.3真题选择题第选择题第6 6题题 682010.9真题选择题第选择题第6 6题题答案解析：软件测试：尽可能地发现程序中的错误以及错误所在的位置。软件调试：诊断和改正程序中的错误。692010.9真题选择题第选择题第4 4题题选择题第选择题第5 5题题 702008
38、.9真题选择题第选择题第5 5题题选择题第选择题第6 6题题 详细设计阶段详细设计阶段所使用的工具所使用的工具712008.4真题选择题第选择题第1 1题题 选择题第选择题第4 4题题 72（一（一）基本概念基本概念 v数据库数据库(DBDB：DatabaseDatabase)：长期存储在计算机内的，有长期存储在计算机内的，有组织的，组织的，可共享的可共享的数据集合。数据集合。v数据库系统数据库系统(DBSDBS：Database SystemDatabase System)：由数据库（数据）、由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、系统平数据库管理系统（软件）、数据库
39、管理员（人员）、系统平台之硬件平台（硬件）和软件平台（软件）构成。台之硬件平台（硬件）和软件平台（软件）构成。v数据库管理系统数据库管理系统(DBMS)-Database Management SystemDBMS)-Database Management System第四部分第四部分 数据库设计基础数据库设计基础 结论结论：数据库、数据库系数据库、数据库系统和数据库管理系统的统和数据库管理系统的关系是：数据库系统包关系是：数据库系统包括数据库和数据库管理括数据库和数据库管理系统。系统。数据库管理系统是数据库管理系统是数据库系统的核心。数据库系统的核心。DBMSDBMS提供的数据语言：提供的数
40、据语言：q 数据定义语言（数据定义语言（DDLDDL）:Data Definition Language:Data Definition Languageq 数据操纵语言（数据操纵语言（DMLDML）:Data Manipulation Language:Data Manipulation Languageq 数据控制语言（数据控制语言（DCLDCL）:Data Control Language:Data Control Language 负责数据的模式定义与数据的负责数据的模式定义与数据的物理存取构建。物理存取构建。负责数据的操纵，包括查询及负责数据的操纵，包括查询及增加、删、改变等操作。增
41、加、删、改变等操作。负责数据完整性、安全性的定负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。义与检查以及并发控制、故障恢复等。742009.3真题-选择题第选择题第8 8题题 752010.3真题-选择题第选择题第7 7题题 76v数据库管理技术的发展数据库管理技术的发展人工管理阶段人工管理阶段文件系统阶段文件系统阶段数据库系统接数据库系统接其中其中数据独立性最高数据独立性最高的阶段是的阶段是数据库系统阶段数据库系统阶段。77v 数据库系统的基本特点：数据库系统的基本特点：数据的集成性；数据的集成性；数据的高共享性与低冗余性；数据的高共享性与低冗余性；数据独立性（数据独立性（数据
42、与程序间的互不依赖性数据与程序间的互不依赖性）；）；q 物理物理独立性：物理结构改变，应用程序不变独立性：物理结构改变，应用程序不变q 逻辑逻辑独立性：逻辑结构改变，应用程序不变独立性：逻辑结构改变，应用程序不变 数据统一管理与控制。数据统一管理与控制。78v 数据库系统的内部结构体系数据库系统的内部结构体系 数据库系统的三级模式数据库系统的三级模式 （1 1）内内模式：模式：处于处于最底层最底层，它反映了，它反映了数据在计算机物数据在计算机物 理结构理结构中的实际存储形式。中的实际存储形式。（2 2）概念概念模式：模式：处于处于中层中层，它放映了设计者的数据全局，它放映了设计者的数据全局 逻
43、辑要求。逻辑要求。（3 3）外外模式：模式：处于处于最外层最外层，它反映了，它反映了用户对数据用户对数据的要求。的要求。792010.9真题-选择题第选择题第9 9题题2008.9真题-选择题第选择题第9 9题题 80 数据库的设计阶段：数据库的设计阶段：q 需求分析阶段需求分析阶段q 概念设计阶段概念设计阶段q 逻辑设计阶段逻辑设计阶段q 物理设计阶段物理设计阶段81v数据库概念设计数据库概念设计任务任务：分析数据间内在语义关联分析数据间内在语义关联，在此基础上建立，在此基础上建立一个数据的抽象模型一个数据的抽象模型v 数据库设计的需求分析数据库设计的需求分析 任务任务：通过详细调查现实世界
44、要处理的对象，充：通过详细调查现实世界要处理的对象，充分了解原系统的工作概况分了解原系统的工作概况，明确用户的各种需求，明确用户的各种需求，然，然后在此基础上确定新系统的功能；后在此基础上确定新系统的功能；82v 数据库的逻辑设计数据库的逻辑设计 从从E-RE-R图向关系模式的转换图向关系模式的转换（所有的（所有的实体和联系实体和联系都都转换为转换为关系关系）v 数据库的物理设计数据库的物理设计 对数据库内部物理结构作调整并对数据库内部物理结构作调整并选择合理的存取路径选择合理的存取路径，以提高数据库访问速度及有效利用存储空间以提高数据库访问速度及有效利用存储空间 留给用户参与物理设计的余地不
45、多留给用户参与物理设计的余地不多832010.3真题-选择题第选择题第9 9题题 84v E-RE-R模型（实体联系模型）模型（实体联系模型）基本概念基本概念 （1 1）实体实体：用于表示实际存在又可相互区别的事物；：用于表示实际存在又可相互区别的事物；（2 2）属性属性：（3 3）联系联系：q 一对一一对一（1 1：1 1）q 一对多一对多（1 1：M M或或M M：1 1）q 多对多多对多（M M：N N）852008.9真题-选择题第选择题第8 8题题2010.9真题-选择题第选择题第8 8题题 86E-RE-R模型的图示法模型的图示法q 实体集实体集的表示（的表示（矩形矩形）q 联系联
46、系的的表示（表示（菱形菱形）q 属性属性的的表示（表示（椭圆形椭圆形）q 实体集与属性间实体集与属性间的联接关系（的联接关系（直线直线）q 实体集与联系间实体集与联系间的联接关系（的联接关系（直线直线）E-RE-R图的一个实例图的一个实例:学生课程联系学生课程联系的概念模型的概念模型87v 关系数据库模型关系数据库模型 采用采用二维表二维表来表示，简称来表示，简称表，表，每一个二维表称为一个每一个二维表称为一个关系关系。表中的每一行称为一条表中的每一行称为一条记录或者元组记录或者元组，记录的每一项称为它，记录的每一项称为它的的分量或者字段分量或者字段。数据库的类型v 层次模型层次模型一种一种树
47、形结构树形结构；v 网状模型网状模型 一个不加任何条件限制的一个不加任何条件限制的无向图无向图；根据数据之间的联系方式，可将数据库划分为三种模型：882009.3真题-选择题第选择题第1010题题 2010.3真题-选择题第选择题第8 8题题 892010.9真题-选择题第选择题第7 7题题2010.3真题-填空题第填空题第5 5题题答案：课程号 902008.4真题-选择题第选择题第1010题题2008.4真题-填空题第填空题第4 4题题答案：关系 或 二维表 91v 关系模型的基本运算关系模型的基本运算 投影运算 选择运算 笛卡儿积运算（连接运算）交与并922009.3真题-选择题第选择题第9 9题题 答案解析：投影操作实际上是从关系中取出取出某些属性列某些属性列，即从列的角度从列的角度进行运算932010.3真题-选择题第选择题第1010题题 答案解析：选择操作实际上是从关系R中取出取出某些记录某些记录放入放入T T中中即从行的角度从行的角度进行运算942010.9真题-选择题第选择题第1010题题 答案解析：只要关系的属性域属性域增加增加，一定是连接一定是连接操作操作。本例中是公公共域等值连接共域等值连接，也称为自然连接。952008.9真题-选择题第选择题第1010题题 962008.4真题-选择题第选择题第9 9题题
