全国计算机等级考试二级公共基础知识教程.pdf

《全国计算机等级考试二级公共基础知识教程.pdf》由会员分享，可在线阅读，更多相关《全国计算机等级考试二级公共基础知识教程.pdf（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国计算机等级考试二级公共基础知识全国计算机等级考试二级公共基础知识考纲考试内容一、基本数据结构与算法1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。二、程序设

2、计基础1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。三、软件工程基础1.软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。2.结构化分析方法，数据流图，数据字典.，软件需求规格说明书。第 1页全国计算机等级考试二级公共基础知识3.结构化设计方法，总体设计与详细设计。4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5.程序的调试，静态调试与动态调试。四、数据库设计基础1.数据库的基本概念：数据库，数据库管理系统，数据库系统。2.数据模型，实体联系模型及E-R图，从E-R图导出关

3、系数据模型。3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。考试方式公共基础的考试方式为笔试，与 C 语言(VisualBASIC、VisualFoxPro、Java、Access Visual C+)的笔试部分合为一张试卷。公共基础部分占全卷的30分。公共基础知识有10道选择题和5 道填空题。第 2页全国计算机等级考试二级公共基础知识第 一 章 数据结构与算法一、内容要点(-)算法1.算法的基本概念算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，

4、且是明确的，没有二义性，同时该规则将在有限次运算后可终止。1)算法的基本特征(1)可行性由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。如：计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为有效位数的影响而使小数丢失，因此，在算法设计时，应该考虑到这一点。(2)确定性算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。例如，一个实际的问题，小宝和萍萍共有12个苹果，小宝比萍萍多4个，请问小宝和萍萍各有几个苹果？这个问题，我们可以立一第3页全国计算机等级考试二级公共基础知识x+y=12

5、个方程1 来求解，要 求x和y的值，公式是正确的，但如11-y=4何让计算能够进行计算，我们的算法不能把公式直接输进去，而应该设计出解题的步骤和过程。即设计的算法是计算工具所能够正常解决问题的过程。(3)有穷性算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。例如，在数学中的无穷级数，在计算机中只能求有限项，即计算的过程是有穷的。(4)拥有足够的情报算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。2)算法的基本要素一是数据对象的运算和操作，二是算法的控制结构。(1)算法中对数据的

6、运算和操作算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列。(2)算法的控制结构算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺第 4页全国计算机等级考试二级公共基础知识序有关。在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三种：顺序结构、选择结构和循环结构。在算法描述是，有相关的工具对这三种结构进行描述，常用的描述工具有：流程图、N-S结构图和算法描述语言等。3)算法设计的基本方法为用计算机解决实际问题而设计的算法，即是计算机算法。通常的算法设计有如下几种：(1)列举法列举法的基本思想是

7、，根据提出的问题，列举出所有可能的情况,并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。列举法通常用于解决“是否存在”或“有哪些可能”等问题。例如，我国古代的趣味数学题：“百钱买百鸡”、“鸡兔同笼”等,均可采用列举法进行解决。使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律。(2)归纳法归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。(3)递推第5页全国计算机等级考试二级公

8、共基础知识递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。递推的本质也是一种归纳，递推关系式通常是归纳的结果。例如，裴波那契数列，是采用递推的方法解决问题的。(4)递归在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合,这就是递归的方法。递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另

9、一个算法B,而算法B又调用算法A,则此种递归称为间接递归调用。(5)减半递推技术减半递推即将问题的规模减半，然后，重复相同的递推操作。例如，一元二次方程的求解。(6)回溯法有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。对于这类问题，只能采用试探的方法,通过对问题的分析，找出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退，换第6页全国计算机等级考试二级公共基础知识别的路线进行试探。这种方法，即称为回溯法。如人工智能中的机器人下棋。2.算法复杂度算法的复杂度包括时间复杂度和空间复杂度。1)时间复杂度即实现该算法需要

10、的计算工作量。算法的工作量用算法所执行的基本运算次数来计算。同一个问题规模下，如果算法执行所需要的基本次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：算法工作量=f(n)(1)平均性态用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。设x是某个可能输入中的某个特定输入，p (x)是x出现的概率，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：A()=p(x)心)D.表示当规模为n时-，算法执行时所有可能输入的集合。(2)最坏情况复杂度指在规模为n时，算法所执行的基本运算的最大次数。它定义为:=max“(x)第7页全国计算机等级考试二级公共基础

11、知识例如，在具有n个元素的数列中搜索一个数X。平均性态:A(/i)=之pt.+q)n=(口 D +(1-q)n，=i，=i n 2即该数在数列中任何位置出现的数列是相同的，也有可能不存在，存在的概率为q。如果有一半的机会存在，则概率q为1/2,平均性态：(/n+八l)x1 3A()=-+(1 )/1 /12 2 4如果查找的元素一定在数列中，则每个数存在的概率即为1,则平均性态为：A(n)=最坏情况分析：即要查找的元素X在数列的最后或不在数列中，显然，它的最坏情况复杂度为：W(n)=maxtiil,则该结点的父结点编号为I N T(k/2)o 若2 k W n,则编号为k的结点的左子结点编号为

12、2 k；否则该第24页全国计算机等级考试二级公共基础知识结点无左子结点(当然也没有右子结点)若2 k+l W n,则编号为k的结点的右子结点编号为2 k+l；否则该结点无右子结点。3.二叉树的存储结构二叉树的存储常采用链式存储结构。存储二叉树中各元素的存储结点由两个部分组成：数据域和指针域。在二叉树中，由于每个结点可有两个子结点，则它的指针域有两个：一个用于存储该结点的左子结点的存储地址，即称为左指针域；一个用于存储指向该结点的右子结点的存储地址，称为右指针域。存储结构如下：L chil d V a l u e R chiI di L(i)V(i)R(i)即二叉树的存储结构中每一个存储结点都有

13、两个指针域，因此，二叉树的链式存储结构也称为二叉树的链表。在二叉树在存储中，用一个头指针指向二叉树的根结点的存储地址。如图所示的二叉树：第 25页全国计算机等级考试二级公共基础知识如果我们将该二叉树的所有结点顺序编号，顺序存放在存储空间里，则它们在内存空间中的存放方式是:第26页全国计算机等级考试二级公共基础知识1 50001 60P01 70Q01 80R0当然，对于满二叉树或完全二叉树而言，也可采用顺序存储的方式，但顺序存储的方式不适合其他的二叉树。4.二叉树的遍历二叉树的遍历即是不重复地访问二叉树的所有结点。在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，二叉树的

14、遍历又可分为三种：前序遍历、中序遍历和后序遍历。1）前序遍历前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时.，依然是先遍历根结点，然后是左子树,再是右子树。操作的具体方式：若二叉树为空，则结束返回。否则：访问根结点前序遍历左子树一前序遍历右子树如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、0第27页全国计算机等级考试二级公共基础知识2）中序遍历中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。具体的操作方式：若二叉树为空，则结束返回。否则：中序遍历左子树访问根结点一中序遍历右子树这里

15、强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、03）后序遍历后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结占O具体的操作方式：若二叉树为空，则结束返回I。否则：前序遍历左子树一前序遍历右子树一访问根结点如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、0、G、C、A（七）查找技术查找即是指在一个给定的数据结构中查找某个指定的元素。第28页全国计算机等级考试二级公共基础知识1.顺序查找顺序查找又称顺序搜索。一般是在线

16、性表中查找指定的元素。基本操作方法是：从线性表的第一个元素开始，与被查元素进行比较，相等则查找成功，否则继续向后查找。如果所有的元素均查找完毕后都不相等，则该元素在指定的线性表中不存在。顺序查找的最好情况：要查找的元素在线性表的第一个元素，则查找效率最高；如果要查找的元素在线性表的最后或根本不存在，则查找需要搜索所有的线性表元素，这种情况是最差情况。对于线性表而言，顺序查找效率很低。但对于以下的线性表，也只能采用顺序查找的方法：线性表为无序表，即表中的元素没有排列不是按大小顺序进行排列的，这类线性表不管它的存储方式是顺序存储还是链式存储，都只能按顺序查找方式进行查找 即使是有序线性表，如果采用

17、链式存储，也只能采用顺序查找方式例如，现有线性表：7、2、1、5、9、4,要在序列中查找元素6,查找的过程是：整个线性表的长度为5 查找计次n=l,将元素6与序列的第一个7元素进行比较，不等，继续查找 n=2,将6与第二个元素2进行比较，不等，继续第29页全国计算机等级考试二级公共基础知识 n=3,将6与第三个元素1进行比较，不等，继续 n=4,将6与第四个元素5进行比较，不等，继续 n=5,将6与第五个元素9进行比较，不等，继续 n=6,将6与第六个元素4进行比较，不等，继续 n=7,超出线性表的长度，查找结束，则该表中不存在要查找的元素。2.二分查找二分查找只适用于顺序存储的有序表。此处所

18、述的有序表是指线性中的元素按值非递减排列（即由小到大，但允许相邻元素值相等）。二分查找的方法如下：将要查找的元素与有序序列的中间元素进行比较：如果该元素比中间元素大，则继续在线性表的后半部分（中间项以后的部分）进行查找如果要查找的元素的值比中间元素的值小，则继续在线性表的前 半 部 分（中间项以前的部分）进行查找这个查找过程一直按相同的顺序进行下去，一直到查找成功或子表长度为0 （说明线性表中没有要查找的元素）有序线性表的二分法查找，条件是必须这个有序线性表的存储方式是顺序存储的。它的查找效率比顺序查找要高得多，它的最坏情况的查找次数是l o g 2 n次，而顺序查找的最坏情况的查找次数是n次

19、。当然，二分查找的方法也支持顺序存储的递减序列的线性表。有非递减有序线性表：1、2、4、5、7、9,要查找元素6 查找第 30页全国计算机等级考试二级公共基础知识的方法是：序列长度为n=6,中间元素的序号m=(n+l)/2 =3 查找计次k=l,将元素6与中间元素即元素4进行比较，不等,6 4 查找计次k=2,查找继续在后半部分进行，后半部分子表的长度 为3,计算中间元素的序号:m=3+(3+l)/2 =5,将元素与后半部分的中间项进行比较，即第5个元素中的7进行比较，不等，6 294176后）259 41762549 17623419 76254179 6第一遍结束后2541769第32页全

20、国计算机等级考试二级公共基础知识第 二 遍（从前往25 41769后）245 176924157 692415679第二遍结束后2415679第 三 遍（从前往24 15679后）2145679第三遍结束2145679第 四 遍（从前往2 145679后）1245679第四遍结束1245679最后结果1245679扫描的次数，最多需要扫描n T 次，如果序列已经就位，则扫描结束。测试是否已经就位，可设置一个标志，如果该次扫描没有数据交换，则说明数据排序结束。2）快速排序法冒泡排序方法每次交换只能改变相邻两个元素之间的逆序，速度相对较慢。如果将两个不相邻的元素之间进行交换，可以消除多个逆序。第3

21、3页全国计算机等级考试二级公共基础知识快速排序的方法是：从线性表中选取一个元素，设为T,将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果将线性表分成两个部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。对过对线性表的一次分割，就以T为分界线，将线性表分成前后两个子表，且前面子表中的所有元素均不大于T,而后面的所有元素均不小于T。再将前后两个子表再进行相同的快速排序，将子表再进行分割，直到所有的子表均为空，则完成快速排序操作。在快速排序过程中，随着对各子表不断的进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行分割处理，需要将暂时不用的子表记忆

22、起来，这里可用栈来实现。对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空时一，可以从栈中退出一个子表进行分割。这个过程直到栈为空为止，说明所有子表为空，没有子表再需分割，排序就完成。2.插入类排序法1）简单插入排序插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。插入排序操作的思路：在线性表中，只包含第1个元素的子表，第 34页全国计算机等级考试二级公共基础知识作为该有序表。从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有序的子表中。该方法与冒泡排序方法的效率相同

23、,最坏的情况下需要n(n-l)/2次比较。例如，有序列5、2、9、4、1、7、6,将该序列从小到大进行排列。采用简单插入排序法，具体操作步骤如下:序列长度n=75 2 9 4 1?j=22 5 9 4 1Tj=32 5 9 4 1?j=47 67 67 62 4 5 91 7 6?j=51 2 4 5 9 7 6?j=61 2 4 5 7 9 6Tj=7插 入 排 序 后 的1245679结果第 35页全国计算机等级考试二级公共基础知识2)希尔排序法希尔排序法的基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序的过程中，

24、逐次减小这个增量，最后当h减小到1时，再进行一次插入排序操作，即完成排序。增量序列一般取h,=n/2 k (k=l,2,，l o g z n ),其 中n为待排序序列的长度。3.选择类排序法1)简单选择排序法基本思路：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对后面的子表采用相同的方法，直到子表为空为止。对于长度为n的序列，需要扫描n-1次，每一次扫描均找出剩余的子表中最小的元素，然后将该最小元素与子表的第一个元素进行交换。例如，有序列5、2、9、4、1、7、6,将该序列从小到大进行排列。采用简单选择排序法，具体操作步骤如下：原序列 5 2 9 4 1 7 6第一遍扫描 1

25、294576第二遍扫描 1294576第 36页全国计算机等级考试二级公共基础知识第三遍扫描1 2 4 9 5 7 6第四遍扫描1 2 4 5 9 7 6第五遍扫描1 2 4 5 6 7 9第六遍扫描1 2 4 5 6 7 9排序结果1 2 4 5 6 7 92）堆排序法堆排序法属于选择类排序方法。堆的定义：具 有n个元素的序列（h i,h z,h Q,当且仅当满足鱼 或（I,2,，n/2）时称之为堆。本节只讨论满足前者条件的堆。由堆的定义看，堆 顶 元 素（即第一个元素）必为最大项。可以用一维数组或完全二叉树来表示堆的结构。用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左右子树的根结点

26、的值，因此堆顶（完全二叉树的根结点）元素必须为序列的n个元素中的最大项。例如，有序列5、2、9、4、1、7、6,将该序列从小到大进行排列。第 37页全国计算机等级考试二级公共基础知识无序堆 调整根结点 调整子树的根结点建堆的过程利用堆排序法将该序列进行排序。操作方式即：先将无序堆的根结点5与左右子树的根结点2、9进行比较，5!X2 XX“第83页全国计算机等级考试二级公共基础知识集合可看作是域的笛卡尔积的子集，R c DX%x D o关系模型的四种操作是：插入 删除 修改 查询可将它们分解为六种基本操作：关系的属性指定 关系的元组选择 两个关系的合并运算 关系的查询 关系元组的插入 关系元组的

27、删除2.关系模型的基本运算1）插入插入操作可看作是集合的并运算。即在原有的关系R中并入要插入的元组R,是这两个元组的并运算：RUR2）删除在关系R中删除元组R,可看作是两个关系的差运算：R-R 3）修改修改关系R中的元组的内容的操作：先将要修改的元组R 从关第84页全国计算机等级考试二级公共基础知识系R中删除，再将修改后的元组R”插入到关系R中，即操作为:(R-R)UR 4)查询插入运算无法通过传统的集合运算来表示，需要专门的关系运算来实现。(1)投影运算投影运算，是从关系中指定若干个属性组合成一个新的关系的操作。投影操作后得到一个新的关系，其关系模式中包含的属性通常比原来的关系少，或者，与原

28、来的关系具有不同的属性顺序。投影是从垂直的角度进行运算，即从列的角度进行运算，投影运算基于一个关系，是一个一元运算。姓名1 励 学 生-1!x|L普姓名1性 别 1班级 1 二 李军张红选择姓名和班级两个属性周云吉.如宿宿.031102031201李军周云青男男=i+03财管03031202刘倩倩女财管03031204王静女财管。3031301钟笑天男财政03031302李海男财政03-1!x|班级 臼会计03会计03时 管 阳时管65钟笑天李海财政03昉 疏 投影操作(2)选择选择，是从关系中查找满足条件的元组。选择的条件是通过逻辑表达式进行描述，逻辑表达式值为真的元组被选出。第 85页全国

29、计算机等级考试二级公共基础知识选择是从行的角度进行的运算，即从水平方向进行元组的抽取。腆学生-11 x|031101张红:女：会计03学号姓 名 性 别 班 级 二 031102李军男会计。3031201周云青男财管03031202刘倩倩女财首03031204王静女财管03031301钟笑天男财政03031302李海男财政03瞄查询设置选择的逻辑条件为:性别=女 学号 姓名 性 别 班级 因,031101张红女；会计03汝；财管。3技 源管而”j；031202-031204i i i zz刘信信至藤”选择操作选择基于一个关系，得到的结果可以形成一个新的关系，它的关系模式与原关系相同，但是原关系

30、的一个子集。例如，从学生表中查找女同学的信息。(3)笛卡尔积运算两个关系的合并操作可以用笛卡尔积表示。设有n元关系R及m元关系S,它们分别有p、q个元组，则关系R和关系S的笛卡尔积为R X S,新关系是一个n+m元关系，元组个数是p X q,由R和S的有序组合而成。3.关系代数中的扩充运算1)交运算关系R与关系S经交运算后所得到的关系是既在R中又在S中的元组组成，记为/?n s。第86页全国计算机等级考试二级公共基础知识2）除运算如果将笛卡尔积运算看作乘运算的话，除运算即是它的逆运算。当关系T=RXS时 一，则可将运算写成：丁 内=5或 丁 八=5S称 为T除 以R的商。T能被除的充分与必要条

31、件是：T中的域包 含R中的所有属性，T中有一些域不出现在R中。在除运算中S的域由T中那些不出现在R中的域所组成，对 于S中任一有序组，由它与关系R中每个有序组所构成的有序组均出现在关系T中。3）连接与自然连接运算联接是关系的横向运算。联接运算将两个关系横向地拼接成一个更宽的关系，生成的新关系中有满足联接条件的所有元组。联接运算通过联接条件来控制，联接条件中将出现两个关系中的公共属性，或者具有相同的域、可比的属性。第87页联接操作,1!x|学号姓名性别班级 国成琴j n l xJ全国计算机等级工031101张红女会计03学号课程号|成绩I一031102李军男会计03财管03-财管03-财管03

32、财政03 一50KO3.1031101001j 9 4.0：0312010312020312040313010313021.-周有青刘倩信王群钟笑天厚薄1男女男舅一031101031102031102031101031301rm、ni002101001103001m iI 8 7.0：|8 7.0：j 8 9.0：:87.0：|89.oj|89。查询-l a l x ii 90.cd学号a姓名性 另。班级学号上课程号成 绩Lfj031101张红女会计0303110100194.0031101031102031102031101031301031301031301张红李军李军张红钟笑天钟笑天钟笑

33、天女男男会计03会计03会计03=i+0 3财政面财政03财政03J031101031102031102031101031301031301031301002101001103obiio ii”20587878987898990.0.0联接条件是学号相.U.0.0等连接运算基于两个关系。如下图所示为联接运算的操作。在联接运算中，按字段值相等的为条件进行的联接运算，即为等值联接。上例即为等值联接的运算。自然联接，是去掉重复属性的等值联接。自然联接是最常用的联自然联接后的结果e，查询,1!x|学号姓名性别班级课程号成绩J|031101张红女会计0300194.0031101张红女会计0300287

34、.0031102李军男会计0310187.0031102李军男会计0300189.0031101张红女会计0310387.0031301钟笑天男财政。300189.0031301钟笑天男财政。310189.0031301钟笑天男财政0320590.01 1 1接方式。如果上例进行的是自然联接，则联接后的关系如下图所示。第88页全国计算机等级考试二级公共基础知识（四）数据库设计与管理1 .数据库设计概述数据库设计的基本任务是根据用户对象的信息需求、处理需求和数据库的支持环境（包括硬件、操作系统与D B M S）设计出数据模式。数据库设计的两种方法：面向数据的方法：以信息需求为主，兼顾处理需求。面

35、向过程的方法：以处理需求为主，兼顾信息需求。目前，面向数据的设计方法是数据库设计的主流方法。数据库设计一般采用生命周期法，分为如下几个阶段：需求分析阶段概 念设计阶段逻 辑设计阶段物 理设计阶段 编码阶段测 试阶段运 行阶段进 一步修改阶段前四个阶段是数据库设计的主要阶段，重点以数据结构与模型的设计为主线。2 .数据库设计的需求分析第一阶段：需求收集和分析，收集基本数据和数据流图。第89页全国计算机等级考试二级公共基础知识主要的任务是：通过详细调查现实世界要处理的对象（组织、部门、企业等），充分了解原系统的工作概况，明确用户的各种需求，在此基础上确定新系统的功能。对数据库的要求：信息要求 处理

36、要求 安全性和完整性的要求数据字典是各类数据的集合，它包括五个部分：数据项，即数据的最小单位 数据结构，是若干数据项有意义的集合 数据流，可以是数据项，也可以是数据结构，用来表示某一处理过程的输入或输出 数据存储，处理过程中存取的数据，通常是手工凭证、手工文档或计算机文件 处理过程3.数据库概念设计1）概念设计概述（1）集中式模式设计法根据需求由一个统一的机构或人员设计一个综合的全局模式。适合于小型或并不复杂的单位或部门。（2）视图集成设计法第 90页全国计算机等级考试二级公共基础知识将系统分解成若干个部分，对每个部分进行局部模式设计，建立各个部分的视图，再以各视图为基础进行集成。比较适合于大

37、型与复杂的单位，是现在使用较多的方法。2)数据库概念设计的过程(1)选择局部应用根据系统情况，在多层的数据流图中选择一个适当层次的数据流图，将这组图中每一部分对应一个局部应用，以该层数据流图为出发点，设计各自的E-R图。(2)视图设计视图设计的三种次序：自顶向下：先从抽象级别高且普遍性强的对象开始逐步细化、具体化和特殊化。由底向上：先从具体的对象开始，逐步抽象，普遍化和一般化,最后形成一个完整的视图设计 由内向外：先从最基本与最明显的对象开始，逐步扩充至非基本、不明显的对象。例：某大学由一名校长主管，学校下设多个学院，每个学院又的多个系；每个系有一名系主任，负责聘任教师；每个教师可以承担多门课

38、，同一门课又可由多个教师承担；每个系有多个班级，每个班级有一定数量的学生；学生在校期间要学习多门课程，学习结束后，每门课程对应一个成绩。要求设计该大学的教学管理系统。第91页全国计算机等级考试二级公共基础知识某大学的组织结构图需求分析阶段，得到该学校的机构组织结构图如下图所示：E-R图设计首先，设 计“院长”、“学院”和“系”之间的联系。一个学院有院长、学院、系之间的关系一个院长，一个院长主管一个学校；一个系属于一个学院，一个学院有多个系。院长与学院的关系是一对一的联系，学院和系之间是一对多的联系。在系里在，一个系会聘用多个教师，而一个教师只属于一个系，所以，系和教师之间的关系是一对多的联系；

39、一门课可由多个教师讲授，同时，一个教师可讲授多门课，课程和教师之间的关系是多对多的联系。第92页全国计算机等级考试二级公共基础知识在系里，学生和课程之间的联系有，一个系有多个班，一个班只能属于一个系，它们之间的联系是一对多的联系；一个班有多个学生,同时，一个学生只属于一个班，所以，班级和学生之间的联系是一对多的联系；系和课程之间的联系，一个系可开设多门课，同 时 一，一门课可被多个系开设，因此，课程和系之间的关系是多对多的联系；学生与课程之间，一个学生会选多门课，同时，一门课可被多个学生选取，因此，课程和学生之间的关系是多对多的联系。逻辑设计学 院（学院编号,学 院 名，学院地址，院长编号）院

40、 长（院长编号,院长姓名，联系电话，办公地址）系（系编号,系 名，联系电话，系地址，学院编号，系主任职工号）教 师（职工号,姓 名，性别，学历，职称，工资，联系电话，系编号）第 93页全国计算机等级考试二级公共基础知识班 级（班级编号,班级名称，学生人数，系名）学 生（学号,身份 证 号，姓名，性别，出生日期，民族，籍贯，班级名）课 程（课程编号,课程名称，学分）开 课（系编号，课程号）授 课（职工号，课程号）选 课（学号，课程号,成 绩）（3）视图集成视图集成是将所有局部视图统一与合并成一个完整的数据模式。视图集成的重点是解决局部设计中的冲突，常见的冲突主要有如下几种：命名冲突：有同名异义或

41、同义异名 概念冲突：同一概念在一处为实体而在另一处为属性或联系 域冲突：相同的属性在不同视图中有不同的域 约束冲突：不同的视图可能有不同的约束视图经过合并生成E-R图时-，其中还可能存在冗余的数据和冗余的实体间联系。冗余数据和冗余联系容易破坏数据库的完整性，给数据库维护带来困难。对于视图集成后所形成的整体的数据库概念结构必须进行验证，满足下列要求：第94页全国计算机等级考试二级公共基础知识整 体概念结构内部必须具有一致性，即不能存在互相矛盾的表达整 体概念结构能准确地反映原来的每个视图结构，包括属性、实体及实体间的联系 整体概念结构能满足需求分析阶段所确定的所有要求 整体概念结构还需要提交给用

42、户，征求用户和有关人员的意见，进行评审、修改和优化，最后定稿4.数据库的逻辑设计1）从 E-R 模型向关系模式转换E-R 模型向关系模式的转换包括：E-R 模型中的属性转换为关系模式中的属性 E-R 模型中的实体转换为关系模式中的元组 E-R 模型中的实体集转换为关系模式中的关系 E-R 模型中的联系转换为关系模式中的关系转换中存在的一些问题：命名与属性域的处理。名称不要重复，同时，要用关系数据库中允许的数据类型来描述类型 非原子属性处理。在 E-R 模型中允许非原子属性存在，但在关系模式中不允许出现非原子属性，因此，要将非原子属性进行转换。联系的转换。通常联系可转换为关系，但有的联系需要归并

43、到相关联的实体中第 95页全国计算机等级考试二级公共基础知识2)逻辑模式规范化及调整、实现(1)规范对关系做规范化验证。(2)R D B M S对逻辑模式进行调整以满足R D B M S的性能、存储空间等要求，包括如下内容：调 整性能以减少连接运算调 整关系大小，使每个关系数量保持在合理水平，从而可以提高存取效率 尽量采取快照，提高查询速度3)关系视图设计逻辑设计又称外模式设计。关系视图是关系模式基础上所设计的直接面向操作用户的视图。关系视图的作用：提供数据逻辑独立性 能适应用户对数据的不同需求 有一定数据保密功能5.数据库的物理设计物理设计的主要目标是对数据库内部物理结构作调整并选择合理的存

44、取路径，以提高数据库访问速度及有效利用存储空间。第96页全国计算机等级考试二级公共基础知识6.数据库管理数据库管理包括：1）数据库的建立数据库建立包括：数据模式的建立。数据模式由D B A负责建立，定义数据库名、表及相应的属性，定义主关键字、索引、集簇、完整性约束、用户访问权限、申请空间资源，定义分区等。数据加载。在数据模式定义后可加载数据，D B A可以编制加载程序将外界的数据加载到数据模式内，完成数据库的建立。2）数据库的调整在数据库库建立并运行一段时间后，对不适合的内容要进行调整，调整的内容包括：调 整关系模式与视图使之更适应用户的需求调 整索引与集簇使数据库性能与效率更佳调 整分区、数

45、据库缓冲区大小以及并发度使数据库物理性能更好3）数据库的重组数据库运行一段时间后，由于数据的大量插入、删除和修改，使性能受到很大的影响，需要重新调整存贮空间，使数据的连续性更好,即通过数据库的重组来实现。第97页全国计算机等级考试二级公共基础知识4）数据库的故障校复保证数据不受非法盗用与破坏；保证数据的正确性。5）数据安全性控制与完整性控制一旦数据被破坏，要及时恢复。6）数据库监控D B A需要随时观察数据库的动态变化，并在发生错误、故障或产生不适应情况时随时采取措施，并监控数据库的性能变化，必要时可对数据库进行调整。三、本章应考点拨本章在考试中一般出现2-4个小题。本章内容概括性强，比较抽象，难于理解，因此建议考生在复习的时候，首先熟读讲义，其次对数据库系统的基本概念及原理等知识要注意理解、加强记忆。第98页