计算机2级公共基础知识考前必看

计算机等级考试公共基础知识,第2页,计算机二级考试公共基础知识大纲,数据结构与算法程序设计基础软件工程基础数据库设计基础,这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。,第3页,算法算法的基本概念2.算法复杂度的概念和意义,一、基本数据结构与算法,数据结构数据结构的概念线性表栈和队列树与二叉树查找技术排序技术,对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。,第4页,算法的定义对解题方案准确而完整的描述称为算法。,算法是程序设计的核心,算法的基本概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。,例：n个数从大到小进行排序。有多种排序方法，常用的有冒泡排序、选择排序等。,第5页,2.算法的基本特征一个算法应该具有以下五个重要的特征：,有穷性确定性输入输出可行性,第6页,算法与计算机程序算法_是一组逻辑步骤程序用计算机语言描述的算法,3.算法的表示,INPUTrS=3.14*r*rPTINTS,问题：输入园的半径，计算园的面积,一个算法的表示需要使用一些语言形式。传统的算法-图形法，如“流程图”和N-S图目前常用的方法-使用伪码描述算法。,第7页,4.算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分,第8页,总结,对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法评价：时间复杂度：执行这个算法所需要的计算工作量空间复杂度：执行这个算法所需要的内存空间,第9页,(1)在计算机中，算法是指_。A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法(2)下列叙述中正确的是A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用,(c),(B),算法习题:,(A),第10页,(4)算法的时问复杂度是指A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对,(D)计算工作量,(A),(D),第11页,计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。,二、数据结构,程序=算法+数据结构,数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。,第12页,二.数据结构,数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。,第13页,1.逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。例：1.一年四季的数据结构B=(D,R)D=春，夏，秋，冬R=(春，夏),(夏，秋),(秋，冬)2.家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子),(父亲，女儿),春,夏,秋,冬,数据结构的图形表示,父亲,儿子,女儿,第14页,常见的逻辑结构有：线性结构、树形结构和图形结构。,线性结构结构中的每个元素之间存在一个对一个的关系；树形结构结构中的每个元素之间存在一个对多个的关系；图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。,第15页,常见的数据结构,1.线性表2.栈和队列3.树,第16页,线性表（LinearList）,线性表是由n（n0）个数据元素a1，a2，ai，an组成的一个有限序列。,简单的线性表,复杂的线性表,记录102011001张三男,记录202011003李四女,记录3,记录4,第17页,2.栈和队列,栈和队列都是特殊的线性表。栈（Stack）及其基本运算队列（Queue）及其基本运算循环队列及其基本运算,第18页,栈（Stack）是一种特殊的线性表。其特点是插入和删除运算都只能在线性表的一端进行。栈是按照“先进后出”或“后进先出”的原则组织数据的线性表。栈的物理存储结构可以用顺序结构，也可以用链表结构。下面讨论顺序存储结构中栈元素的插入和删除运算。顺序栈的进栈和出栈运算栈的基本运算有三种：入栈、退栈和读栈顶元素,在顺序栈中插入和删除运算不需要移动表中其他数据元素。,第19页,队列（Queue）是一种特殊的线性表。其特点是所有的插入都在表的一端进行，所有的删除运算都在表的另一端进行。队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。队列的物理存储结构可以用顺序结构，也可以用链式结构。顺序队列的运算,栈有三种操作：入栈出栈读栈顶元素队列有三种操作：入队出队读队首元素,例：有入栈元素序列：ABCD，求可能的出栈序列如是队列又是什么情况呢？,第20页,循环队列把队列的存储空间在逻辑上看作一个环，当R指向存储空间的末端后，就把它重新置于始端。循环队列的运算,队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。,习题：数据结构分为逻辑结构和存储结构，循环队列属于【】结构。（2005年9月）,答案：存储结构。,第21页,常见数据结构的逻辑结构,线性表线性结构栈是特殊的线性表队列也是一种操作受限的特殊的线性表树（树型结构）是一种重要的非线形数据结构,第22页,数据存储结构方面的考题,1：数据的存储结构是指A)存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示2.下列叙述中正确的是A）栈是“先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构3.数据结构分为线性结构和非线性结构，带链的队列属于。4.下列数据结构中，属于非线性结构的是A）循环队列B)带链队列C)二叉树D）带链栈,答案：D。,答案：D。,答案：线性结构。,答案：c,第23页,5。下列叙述中正确的是（）。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间,答案：A。,6。下列关于栈的叙述正确的是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,第24页,一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。有且仅有一个根结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除最后一个结点外，每一个结点最多有一个直接后继结点。,线性结构与非线性结构线性表、栈和队列都是线性结构一个数据结构不是线性结构，则称其为非线性结构。,第25页,树型结构是一种重要的非线性结构。树的概念二叉树的概念二叉树的存储二叉树的遍历,3.树与二叉树,第26页,树的概念,树的定义：n个结点的有限集。（n=0）,A,B,D,F,E,C,G,H,I,J,K,M,根：onlyone若n=0，则称为空树；否则，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归的。Question：如何辨别根？,A,只有一个结点的树,第27页,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,M,结点的度一个结点的子树的个数；Q：结点A、G的度数？树的度树中所有结点度的最大值；Q：右图中树的度？终端结点度为0的结点；Q：图中叶子结点有几个？7非终端结点度不为0的结点；Q：图中非终端结点有几个？5,孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先,第28页,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,M,结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推；Q：图中结点F的层次？树的深度树中所有结点层次的最大值；Q：图中树的深度？有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,第29页,二叉树的概念,定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是：每个结点最多有两棵子树；子树有左右之分，次序不能任意颠倒。,二叉树的5种基本形态,第30页,二叉树的性质,【性质1】在二叉树的第i层上最多有2i-1个结点（i1）,第31页,【性质2】深度为h的二叉树最多有2h-1个结点（h1）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,第32页,满二叉树,完全二叉树,12,13,8,9,10,11,4,5,6,7,1,2,3,完全二叉树是满二叉树满二叉树也是完全二叉树,第33页,12,13,8,9,10,11,4,5,6,1,2,3,非完全二叉树,深度为4的完全二叉树,8,4,5,6,7,1,2,3,第34页,【性质3】二叉树上叶子结点数比度为2的结点数多1,度为2的结点,叶子结点,第35页,1：在深度为7的满二叉树中,叶子结点的个数为A)32B)31C)64D)632：在深度为7的满二叉树中，度为2的结点个数为【】。3：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为A）219B）221C）229D）2314：某二叉树中度为2的结点有18个，则该二叉树中有【】个叶子结点。5：一棵二叉树第六层（根结点为第一层）的结点数最多为【】个。,树型结构方面的考题,1答案：C。,3答案：A。,5答案：32。,2答案：63。,4答案：19。,第36页,二叉树的遍历,遍历指不重复地访问二叉树中的所有结点。二叉树的遍历的次序与树型结构上的大多数运算有联系。遍历的方式有三种（1）先（前）序遍历（DLR）（2）中序遍历（LDR）（3）后序遍历（LRD）,第37页,二叉树的遍历,遍历指不重复地访问二叉树中的所有结点。（1）先（前）序遍历（DLR）若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。,先序遍历的结果：ABECFGHD,第38页,（2）中序遍历（LDR）若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。中序遍历的结果：EBAFHGCD（3）后序遍历（LRD）若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。后序遍历的结果：EBHGFDCA,第39页,先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA,A,B,C,F,H,D,E,G,下图所示的二叉树经过三种遍历得到的顺序分别为？,练习：,根据先序遍历序列，建立二叉树,第40页,1:设二叉树如下：（2010年3月）对该二叉树进行后序遍历的结果为【3】,树型结构方面的考题2,2:对如下二叉树（2006年4月）进行后序遍历的结果为A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA,EDBGHFCA,D,A,B,C,F,H,D,G,E,第41页,查找技术,查找是数据处理的重要内容。查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。若找到了满足条件的结点，称查找成功；否则称查找失败。衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。通常根据不同的数据结构，采用不同的查找方法：顺序查找二分查找,第42页,顺序查找,线性表中最简单的查找方法。方法：从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，则查找失败。顺序查找法的适用场合：对线性表中元素的排列次序没有要求；对线性表的存储结构没有要求，链式结构和顺序结构均可。,第43页,二分查找(折半查找),是一种效率较高的查找方法，但是只适合顺序存储的有序表。二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为0。二分查找法的适用场合：线性表中的元素按关键字值递增或递减的次序排列；线性表采用顺序存储结构。,第44页,排序技术,排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。排序方法中其排序对象一般是顺序存储的线性表。根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：交换类排序法冒泡排序快速排序插入类排序法简单插入排序希尔排序选择类排序法简单选择排序堆排序,第45页,冒泡排序,冒泡排序的方法：扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大(或最小)的元素排到表的最后(或最前)；除最后(或最前)一个元素，对剩余的元素重复上述过程，将次大(或次小)的数排到表的倒数(或正数)第二个位置；重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。,第46页,冒泡排序的方法,设待排数据元素的关键字为（18，20，15，32，4，25），第一趟冒泡排序后的序列状态如图所示：182015324251820153242518152032425181520324251815204322518152042532最大数,第二趟冒泡排序,第47|92页,Q：第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最后成为有序序列？Q：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。冒泡排序终止条件:本趟排序未发生交换，终止排序算法,第48|92页,初始第一趟第二趟第三趟第四趟第五趟序列排序后排序后排序后排序后排序后2618181818918262626915323232915185447915264791532915471554,设待排数据元素的关键字为（26,18,32,54,47,9,15),冒泡排序法，需要比较的次数为n(n-1)/2；,第49页,选择排序,选择排序的方法：扫描整个线性表，从中找出最小的元素，与第一个元素交换；除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；重复上述过程；对于长度为n的线性表，选择排序需要对表扫描n-1遍。,简单选择排序法,最坏情况需要n(n-1)/2次比较；,第50|92页,初态：15，14，22，30，37，15，11第一趟：1114，22，30，37，15，15第二趟：11，1422，30，37，15，15第三趟：11，14，1530，37，22，15第四趟：11，14，15，1537，22，30第五趟：11，14，15，15，2237，30第六趟：11，14，15，15，22，3037有序序列,例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示：,第51页,排序法小结：,简单选择排序法,最坏情况需要n(n-1)/2次比较；冒泡排序法,最坏情况需要n(n-1)/2次比较；快速排序法，最坏情况需要n(n-1)/2次比较；希尔排序法,最坏情况需要O(n1.5)次比较；堆排序法,最坏情况需要O(nlog2n)次比较；,第52页,排序查找方面的考题：,(1)对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是A)冒泡排序为n/2B)冒泡排序为nC)快速排序为nD)快速排序为n(n-1)/2(2)在长为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。A）、63B）、64C）、6D）、7(3)下列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表B）线性链表C）二叉链表D）有序线性链表(4)下列排序方法中，最坏情况下比较次数最少的是（09年3月）A）冒泡排序B）简单选择排序C）直接插入排序D）堆排序,D,B,A,D,第53页,第二章程序设计基础,内容：1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。,第54页,1结构化程序设计,结构化程序设计方法的四条原则是：1.自顶向下；2.逐步求精；3.模块化；4.限制使用goto语句。结构化程序的基本结构和特点：（1）顺序结构：简单的程序设计，最基本、最常用的结构；（2）选择结构（分支结构）：包括简单选择和多分支选择结构，（3）重复结构（循环结构）：可根据给定条件，判断是否需要重复执行某一相同程序段。,第55页,2面向对象的程序设计,对象是面向对象方法中最基本的概念。对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息操作描述了对象执行的功能，操作也称为方法或服务。,第56页,类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。消息的组成包括（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。单继承指一个类只允许有一个父类多重继承指一个类允许有多个父类。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。,第57页,程序设计基础方面的考题,1.符合结构化原则的三种基本控制结构是：选择结构、循环结构和【】.2.下列选项中不属于结构化程序设计原则的是A)可封装D)自顶向下C)模块化D)逐步求精3.以下叙述中正确的是。A）程序设计的任务就是编写程序代码并上机调试B）程序设计的任务就是确定所用数据结构C）程序设计的任务就是确定所用算法D）以上三种说法都不完整4.在面向对象方法中，类的实例称为【_】。（2005年4月）5.在面向对象方法中,【_】描述的是具有相似属性与操作的一组对象。（2006年4月）,（顺序结构）,A,D,对象,类,第58页,第三章软件工程基础,计算机软件是包括程序、数据及相关文档的完整集合。软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。,第59页,1.软件工程概念,软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期三个阶段:软件定义、软件开发、运行维护，主要活动阶段是：（1）可行性研究与计划制定；（2）需求分析；（3）软件设计；（4）软件实现；（5）软件测试；（6）运行和维护。,第60页,2结构化分析方法,结构化分析方法：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。结构化分析的常用工具（1）数据流图；（2）数据字典；（3）判定树；判定表。（4）软件需求规格说明书,第61页,3结构化设计方法,软件设计包括：总体设计与详细设计在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。常见的过程设计工具有：图形工具（程序流程图,N-S,PAD）表格工具（判定表）语言工具（PDL伪码）,第62页,4软件测试,软件测试的目的：发现错误而执行程序的过程。软件测试方法：静态测试：包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。,第63页,(1)下面叙述中错误的是A）软件测试的目的是发现错误并改正错误B）对被调试的程序进行“错误定位”是程序调试的必要步骤C）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性(2)软件测试可分为白盒测试和黑盒测试。基本路径测试属于【】测试。(2009年3月）(3)按照软件测试的一般步骤，集成测试应在_测试之后进行。(4)软件工程三要素包括方法、工具和过程，其中，_支持软件开发的各个环节的控制和管理。(2008年9月)(5)软件设计中划分模块的一个准则是A)低内聚低耦合B)高内聚低耦合C)低内聚高耦合D)高内聚高耦合,A,软件工程方面的考题：,白盒,单元,过程,B,第64页,(6)下列叙述中正确的是AA）软件交付使用后还需要进行维护B）软件一旦交付使用就不需要再进行维护C）软件交付使用后其生命周期就结束D）软件维护是指修复程序中被破坏的指令(7)程序流程图中的菱形框表示的是【2】。(8)软件开发过程主要分为需求分析、设计、编码与测试四个阶段，其中【3】阶段产生“软件需求规格说明书。(9)下列叙述中正确的是A)软件测试应该由程序开发者来完成B)程序经调试后一般不需要再测试C)软件维护只包括对程序代码的维护D)以上三种说法都不对,A,逻辑条件,需求分析,D,第65页,(3)软件按功能可以分为：应用软件、系统软件和支撑软件(或工具软件)。下面属于系统软件的是A)编辑软件B)操作系统C)教务管理系统D)浏览器(4)软件(程序)调试的任务是A)诊断和改正程序中的错误B)尽可能多地发现程序中的错误C)发现并改正程序中的所有错误D)确定程序中错误的性质(5)数据流程图(DFD图)是A)软件概要设计的工具B)软件详细设计的工具C)结构化方法的需求分析工具D)面向对象方法的需求分析工具(6)软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于A)定义阶段B)开发阶段C)维护阶段D)上述三个阶段,经典考题,B,A,C,B,第66页,第四章数据库设计基础,数据：实际上就是描述事物的符号记录。数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。数据库系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。数据库应用系统：由数据库系统、应用软件及应用界面三者组成。,第67页,数据库系统,第68页,关系数据库系统的基本特点：数据的集成性数据的高共享性与低冗余性数据独立性（物理独立性与逻辑独立性）数据统一管理与控制。数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。数据库系统的三级模式：（1）概念模式（2）外模式（3）内模式数据库系统的两级映射：（1）概念模式到内模式的映射；（2）外模式到概念模式的映射。,1.数据库系统的基本概念,69,应用,外模式(用户数据库),应用,外模式(用户数据库),应用,外模式(用户数据库),概念模式(概念数据库),内模式(物理数据库),数据库,外模式概念模式映射,概念模式内模式映射模式,70,2.数据模型,数据模型（DataModel）是对客观事物及其关系的数据描述。数据库中的数据模型可以将复杂的现实世界要求反映到计算机数据库中的物理世界。现实世界信息世界计算机世界数据模型是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件。数据模型所描述的内容包含：数据结构、数据操作和数据约束。,第71页,2.数据模型,E-R模型的基本概念（1）实体：现实世界中的事物；（2）属性：事物的特性；（3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。在一所学校，一门课程与学生之间是一对多的关系。在一所学校，多门课程与多个学生之间是多对多的关系。一个家庭，夫妻关系是一对一关系。,72,E-R模型的图示法用简单的几何图形表示实体集、属性与联系。(1)实体集表示法在E-R图中用矩形表表示实体集，在矩形内写上实体集名称。如实体集学生(student)、实体集课程(course)(2)属性表示法在E-R图中用椭圆形表示属性，在椭圆形内写上该属性名称。如学生有属性：学号(S#)、姓名(Sn)及年龄(Sa)可用如下表示。,student,course,S#,Sn,Sa,73,(3)联系表示法在E-R图中用菱形(内写上联系名)表示联系。如学生与课程的联系SC,如下图所示：(4)实体集与属性间的联系关系属性依附于实体集，它们之间有联系关系用无向线段表示。,SC,student,S#,Sn,Sa,74,属性也依附于联系，它们之间也有联系关系，因此也可用无向线段，如联系SC可与学生的课程成绩属性G建立联系并用下图表示。(5)实体集与联系间的连接关系(也可用无向线段),SC,G,student,course,SC,第75页,E-R模型之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。E-R模型的图示法：（1）实体集表示法；用长方形（2）属性表法；用椭圆形（3）联系表示法。用菱形，(m:n),76,关系模型的基本运算：1.插入集合的并运算2.删除集合的差(交)运算3.修改集合的差|并(除)运算。4.查询（投影、选择、笛卡尔积运算）,3.关系代数,集合的并运算,77,由关系R和S通过交运算得到关系T，,78,用于查询的集合运算：（1）投影对于关系R内的域指定称为投影运算。S关系就是对R关系指定A和B两个域的结果,R,S,3.关系代数,79,关系代数,（2）选择选择运算的关系是由关系R中那些满足逻辑条件的元组所组成。S关系就是R关系中满足A=a的结果,R,S,有了投影和选择运算，我们对一个关系内的任意行、列的数据都可以方便的找到。,80,笛卡尔积是对两个关系的合并操作。有三个关系R、S和TR关系n1行,m1列S关系n2行，m2列T关系行数=n1*n2列数=m1+m2,R,S,T,（3）笛卡尔积运算,81,笛卡尔积建立两个关系的连接，但得到的关系庞大且数据大量冗余。在实际应用中一般相互连接的关系往往须满足一些条件，所得到的结果也较为简单。自然连接满足两个关系中有公共域，通过公共域的相等值进行连接。有三个关系R、S和TR关系n1行,m1列S关系n2行，m2列T关系行数(n1或n2中行数多的一个)列数m1+m2,（4）自然连接运算,82,有三个关系R、S和T，由关系R和S通过运算得到关系T，则使用的运算为,笛卡尔积,R,S,T,自然连接,R,S,T,83,在三个关系R，S和T如下：由关系R和S通过自然连接运算得到关系T。,R,S,T,第84页,数据库设计与管理,数据库设计的两种方法：（1）面向数据：以信息需求为主，兼顾处理需求；（2）面向过程：以处理需求为主，兼顾信息需求。数据库的生命周期：需求分析阶段结构析方法和面向对象的方法数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流、数据存储、处理过程。概念设计阶段分析数据内在语义关系。E-R模型逻辑设计阶段物理设计阶段编码阶段测试阶段运行阶段进一步修改阶段,85,4.4数据库设计与管理,数据库应用系统(DBAS)中,核心问题是数据库设计。,需求分析,概念设计,逻辑设计,物理设计,编码,测试,运行,进一步修改,分析客户的业务和数据处理需求;,设计数据库的E-R模型图，确认需求信息的正确和完整;,将E-R图转换为多张表，进行逻辑设计,并应用数据库设计的三大范式进行审核;,数据库内模式包括存储结构和存取方法。,重点记,8个阶段,选择具体数据库进行物理实现，并编写代码实现前端应用;,第86页,数据库管理的内容,（1）数据库的建立；（2）数据库的调整；（3）数据库的重组；（4）数据库安全性与完整性控制；（5）数据库的故障恢复；（6）数据库监控。,87,06年9月全国计算机等级考试二级笔试试卷,一、单选题4)在数据库系统中,用户所见的数据模式为A)概念模式B)外模式C)内模式D)物理模式5)数据库设计的四个阶段是:需求分析、概念设计、逻辑设计和A)编码设计B)测试阶段C)运行阶段D)物理设计,D4,D5,88,6）设有如下三个表,下列操作中正确的是A)T=RSB)T=RSC)T=RSD)=R/S,R,S,T,D6,A)并B)交C)笛卡尔积D)除,89,9)数据库技术的根本目标是要解决数据的A)存储问题B)共享问题C)安全问题D)保护文题二、填空题3)一个关系表的行称为【3】,D9,T3,元组,90,07年4月全国计算机等级考试二级笔试试卷,一、单选题8）在下列关系运算中，不改变关系表中的属性个数但能减少元组个数为A）并B）交C）投影D）笛卡儿乘积9）在E-R图中，用来表示实体之间联系的图形是A）矩形B）椭圆形C）菱形D）平行四边形,D9,D8,91,10）下列叙述中错误的是A）在数据库系统中，数据的物理结构必须与逻辑结构一致B）数据库技术的根本目标是要解决数据的共享问题C）数据库设计是指在已有数据库管理系统的基础上建立数据库D）数据库系统需要操作系统的支持,D10,二、填空题3）在数据库系统中实现各种数据管理功能的核心软件称为【3】。,数据库管理系统或DBMS,T3,92,07年9月全国计算机等级考试二级笔试试卷,一、单选题9)下列叙述中正确的是A)数据库系统是一个独立的系统，不需要操作系统的支持B)数据库技术的根本目标是要解决数据的共享问题C)数据库管理系统就是数据库系统D)以上三种说法都不对,D9,93,10)下列叙述中正确的是A)为了建立一个关系，首先要构造数据的逻辑关系B)表示关系的二维表中各元组的每一个分量还可以分成若干数据项C)一个关系的属性名表称为关系模式D)一个关系可以包括多个二维表二、填空题5)在E-R图中，矩形表示5。,D10,T5,实体集,94,08年4月全国计算机等级考试二级笔试试卷,一、单选题8)在数据库设计中，将E-R图转换成关系数据模型的过程属于A)需求分析阶段B)概念设计阶段C)逻辑设计阶段D)物理设计阶段,D8,95,(9)有三个关系R、S和T如下：由关系R和S通过运算得到关系T，则所使用的运算为A并B自然连接C笛卡尔积D.交,D9,