1、1全国计算机等级考试二级公共基础知识2第一章数据结构与算法 考点 算法的特征1 1算法的基本概念算法的基本概念 算法：解决问题的步骤。算法：解决问题的步骤。计算机解题的过程实际上是在实施计算机解题的过程实际上是在实施某种算法。某种算法。算法的基本特征：算法的基本特征：可行性可行性、确定性确定性、有穷性有穷性、拥有足够的情报拥有足够的情报1.1 1.1 算法及复杂度算法及复杂度精品资料 你怎么称呼老师？如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？你所经历的课堂，是讲座式还是讨论式？教师的教鞭“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘”“太阳当
2、空照，花儿对我笑，小鸟说早早早”52 2算法复杂度算法复杂度算法复杂度包括算法复杂度包括时间复杂度时间复杂度和空间复杂度。和空间复杂度。考点 算法的复杂度61.1.逻辑结构逻辑结构 数据的逻辑结构：对数据元素之间的数据的逻辑结构：对数据元素之间的逻辑逻辑关系关系的描述。的描述。线性结构线性结构和和非线性结构非线性结构。2.2.存储结构存储结构 数据的逻辑结构在计算机数据的逻辑结构在计算机存储空间中的存存储空间中的存放形式放形式称为数据的存储结构（也称数据的称为数据的存储结构（也称数据的物理物理结构结构）常用的有常用的有顺序、链式顺序、链式等存储结构。等存储结构。考点 逻辑结构和存储结构 1.2
3、 1.2 数据结构数据结构7 顺序存储方式主要用于顺序存储方式主要用于线性线性的数据结的数据结构，构，逻辑相邻逻辑相邻的数据元素存储在的数据元素存储在物理相邻物理相邻的存储单元里。的存储单元里。链式存储结构就是在每个结点中至少链式存储结构就是在每个结点中至少包含一个包含一个指针域指针域，用，用指针指针来体现数据元素来体现数据元素之间逻辑上的联系。之间逻辑上的联系。8考点 线性结构和非线性结构 一个一个非空非空的数据结构满足下列两个条件：的数据结构满足下列两个条件：（1 1）有且只有一个）有且只有一个根结点根结点；（2 2）每一个结点最多有一个前件，也最）每一个结点最多有一个前件，也最多有一个后
4、件。多有一个后件。则称该数据结构为则称该数据结构为线性结构线性结构。又称。又称线性线性表表。如果一个数据结构不是线性结构，则为。如果一个数据结构不是线性结构，则为非线性结构。非线性结构。数据逻辑结构（也称：数据结构）分：数据逻辑结构（也称：数据结构）分：线性结构与非线性结构线性结构与非线性结构。3 3 线性结构和非线性结构线性结构和非线性结构9 在一个线性结构中插入或删除任何一个在一个线性结构中插入或删除任何一个结点后还应是线性结构。结点后还应是线性结构。栈、队列、字符串等都是线性结构。栈、队列、字符串等都是线性结构。数组、广义表、树和图数组、广义表、树和图等数据结构都是等数据结构都是非线性结
5、构。非线性结构。P15310 栈的基本运算有三种：栈的基本运算有三种：入栈入栈、退栈退栈与与读读栈顶栈顶元素。元素。考点 栈 栈栈限定只在一端进行插入与删除的限定只在一端进行插入与删除的线性线性结构（表）结构（表）。在栈中，一端是封闭的，既不。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常一端是开口的，允许插入和删除元素。通常称称插入、删除插入、删除的这一端为的这一端为栈顶栈顶，另一端为，另一端为栈栈底底。当表中没有元素时称为。当表中没有元素时称为空栈空栈。栈栈:“先进后出先进后出”或或“后进先出后进
6、先出”1.3 1.3 栈栈11 队列是只允许队列是只允许在一端在一端进行进行删除删除，在，在另一另一端端进行进行插入插入的的顺序表。顺序表。通常将允许删除的这通常将允许删除的这一端称为一端称为队头队头，允许插入的这一端称为，允许插入的这一端称为队尾队尾。当表中没有元素时称为当表中没有元素时称为空队列空队列。队列的修改按照队列的修改按照先进先出先进先出(简称简称FIFOFIFO)或或“后进后出后进后出”(简称简称LILOLILO)的原则进行。的原则进行。考点 队列1.4 1.4 队列队列 入队运算入队运算为往队列队尾插入一个数据元为往队列队尾插入一个数据元素，素，退队运算退队运算为从队列的队头删
7、除一个数据为从队列的队头删除一个数据元素。元素。12 链式存储方式中每个结点由两部分组成：链式存储方式中每个结点由两部分组成：(数据元素数据元素)数据域和数据域和(指针指针)指针域。其中指针用指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或于指向该结点的前一个或后一个结点（即前件或后件）。后件）。链式存储方式链式存储方式既可用于表示线性结构，也既可用于表示线性结构，也可用于表示非线性结构可用于表示非线性结构。（1 1）线性链表）线性链表 线性结构（线性表）的链式存储结构称为线性结构（线性表）的链式存储结构称为线性链表。线性链表。考点 链表1.5 1.5 链表链表13 在线性链表中，
8、各数据元素结点的在线性链表中，各数据元素结点的存储存储空间可以是不连续的空间可以是不连续的，且各数据元素的，且各数据元素的存储存储顺序与逻辑顺序可以不一致顺序与逻辑顺序可以不一致。在线性链表中。在线性链表中进行进行插入与删除，不需要移动链表中的元素插入与删除，不需要移动链表中的元素。（2 2）带链的栈）带链的栈 栈也是线性表栈也是线性表，也可以采用链式存储结，也可以采用链式存储结构。构。某些应用中，对线性链表中的每个结点某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向设置两个指针，一个称为左指针，用以指向其前件结点；另一个称为右指针，用以指向其前件结点；另一个称为右指针
9、，用以指向其后件结点。这样的表称为其后件结点。这样的表称为双向链表双向链表。141 1、下列关于线性链表的描述中，正确的是、下列关于线性链表的描述中，正确的是(C C)。I I只含有一个指针域来存放下一个元素地址只含有一个指针域来存放下一个元素地址 IIII指针域中的指针用于指向该结点的前一个指针域中的指针用于指向该结点的前一个或后一个结点（即前件或后件）或后一个结点（即前件或后件）IIIIII结点由两部分组成，数据域和指针域结点由两部分组成，数据域和指针域 A)IA)I、II B)III B)I、III III C)IIC)II、III III D)D)全部全部2 2、算法的时间复杂度是（、
10、算法的时间复杂度是（D D）。）。A)A)算法的长度算法的长度 B)B)执行算法所需要的时间执行算法所需要的时间 C)C)算法中的指令条数算法中的指令条数 D)D)算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数153 3、算法的空间复杂度是的指（、算法的空间复杂度是的指（D D ）。）。A)A)算法程序的长度算法程序的长度 B)B)算法程序中的指令条数算法程序中的指令条数 C)C)算法程序所汇款单的存储空间算法程序所汇款单的存储空间 D)D)算法执行过程中所需要的存储空间算法执行过程中所需要的存储空间4 4、下列描述中，正确的是（、下列描述中，正确的是（A A）。）。A)
11、A)线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构 B)B)栈与队列是非线性结构栈与队列是非线性结构 C)C)双向链表是非线性结构双向链表是非线性结构 D)D)只有根结点的二叉数是线性结构只有根结点的二叉数是线性结构165.5.按照按照“后进先出后进先出”原则组织数据的数据结构是（原则组织数据的数据结构是（B B）。）。A.A.队列队列 B.B.栈栈 C.C.双向链表双向链表 D.D.二叉树二叉树6.6.下列对队列的叙述正确的是（下列对队列的叙述正确的是（B B）。）。A.A.队列属于非线性表队列属于非线性表 B.B.队列按队列按“先进先出先进先出”原则组织数据原则组织数据 C.
12、C.队列按队列按“先进后出先进后出”原则组织数据原则组织数据 D.D.队列在队尾删除数据队列在队尾删除数据17考点 二叉树及其基本性质 在二叉树中，每一个结点的在二叉树中，每一个结点的度最大为度最大为2 2，即，即所有子树也均为二叉树。所有子树也均为二叉树。一个结点既没有左子树也没有右子树时一个结点既没有左子树也没有右子树时,该该结点即为结点即为叶子结点叶子结点。1.6 1.6 二叉树二叉树1 1、二叉树及其基本概念、二叉树及其基本概念 二叉树二叉树非线性结构非线性结构，具有以下两个特点：，具有以下两个特点：非空二叉树只有非空二叉树只有一个根结点一个根结点；每一个结点每一个结点最多有两棵子树最
13、多有两棵子树，且分别称为，且分别称为该结点的左子树和右子树。该结点的左子树和右子树。18树的基本概念树的基本概念 考点 树及其基本性质192 2、二叉树基本性质、二叉树基本性质 性质性质1 1：在二叉树的：在二叉树的第第k k层层上，最多有上，最多有2 2(k-1)(k-1)（k1k1）个结点；）个结点；性质性质2 2：深度为：深度为m m的二叉树最多有的二叉树最多有2 2m m-1-1个结个结点；点；性质性质3 3：在任意一棵二叉树中，：在任意一棵二叉树中，度为度为0 0的结的结点（即叶子结点）总是比点（即叶子结点）总是比度为度为2 2的结点的结点多一个多一个。性质性质4 4：具有：具有n
14、n个结点的二叉树，其深度至个结点的二叉树，其深度至少为少为loglog2 2n n+1+1。考点 二叉树及其基本性质203 3、满二叉树与完全二叉树、满二叉树与完全二叉树 满二叉树满二叉树:除最后一层外，每一层上的除最后一层外，每一层上的所有结点都有两个子结点所有结点都有两个子结点。一棵深度为一棵深度为k k 且有且有2 2k k-1-1个结点的二叉树。个结点的二叉树。（特点：每层都特点：每层都“充满充满”了结点了结点）AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树21完全二叉树完全二叉树:除最后一层外，每一层上的除最后一层外，每一层上的结点结点数均达到最大值数均达到最大
15、值；在；在最后一层上只缺少右边最后一层上只缺少右边的的若干结点。若干结点。深度为深度为k 的的，有有n个结点的二叉树，当且仅当其个结点的二叉树，当且仅当其每一个结点都与深度为每一个结点都与深度为k 的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应。的结点一一对应。完全二叉树的特点就是，只有最后一层叶子不完全二叉树的特点就是，只有最后一层叶子不满，叶子且全部集中在左边。满，叶子且全部集中在左边。这其实是这其实是的含义。的含义。深度为深度为4 4的的完全二叉树完全二叉树ABCGEIDHFJ22 二叉树的遍历分为三类：前序遍历、中序二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。遍历和
16、后序遍历。（1 1）前序遍历：先访问）前序遍历：先访问根根结点、然后遍历结点、然后遍历左左子树，最后遍历子树，最后遍历右右子树。子树。（2 2）中序遍历：先遍历）中序遍历：先遍历左左子树、然后访问子树、然后访问根根结点，最后遍历结点，最后遍历右右子树。子树。（3 3）后序遍历：先遍历）后序遍历：先遍历左左子树、然后遍历子树、然后遍历右右子树，最后访问子树，最后访问根根结点。结点。考点8 二叉树的遍历前序遍历：前序遍历：ABDECFABDECF中序遍历：中序遍历：DBEACFDBEACF后序遍历：后序遍历：DEBFCADEBFCA23 1.1.已知二叉树后序遍历序列是已知二叉树后序遍历序列是CD
17、ABECDABE，中序，中序遍历序列是遍历序列是CADEBCADEB。它的前序遍历序列是。它的前序遍历序列是(C C)。A A）ABCDE BABCDE B）ECABD ECABD C C）EACDB EACDB D D）CDEABCDEAB24 2 2、某二叉树中，度为、某二叉树中，度为2 2的结点有的结点有1010个，则个，则该二叉树中有（该二叉树中有（1111）个叶子结点，一棵满）个叶子结点，一棵满二叉树共有二叉树共有1515个结点，则在该满二叉树中的叶个结点，则在该满二叉树中的叶子结点数是（子结点数是（8 8 ）。）。3 3、在一棵二叉树上第、在一棵二叉树上第5 5层的结点数最多是层的
18、结点数最多是(B B)。A)8 A)8 B)16B)16 C)32 D)15 C)32 D)1525考点 顺序查找1.7 1.7 查找查找 查找是指在一个查找是指在一个给定的数据结构中查找给定的数据结构中查找某某个指定的元素。个指定的元素。1.1.顺序查找顺序查找 从线性结构（线性表）的第一个元素开始，从线性结构（线性表）的第一个元素开始，依次将线性表中的元素与被查找的元素相比较，依次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中所有的元若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了比较但都不相等，则素都与被查找元素进行了比较但都不相等，则表示查找失败。
19、表示查找失败。26在下列两种情况下也在下列两种情况下也只能只能采用顺序查找：采用顺序查找：(1)(1)如果线性表为如果线性表为无序表无序表，则不管是顺，则不管是顺序存储结构还是链式存储结构，只能用顺序存储结构还是链式存储结构，只能用顺序查找。序查找。(2)(2)即使是即使是有序线性表有序线性表，如果采用，如果采用链式链式存储结构存储结构，也只能用顺序查找。，也只能用顺序查找。27 2.2.二分法查找，也称二分法查找，也称拆半查找拆半查找，是一种，是一种高高效效的查找方法。的查找方法。能使用二分法查找的线性表必须满足两个能使用二分法查找的线性表必须满足两个条件：条件：用用顺序存储结构顺序存储结构
20、和和线性表是有序表线性表是有序表。对于长度为对于长度为n n的有序线性表，利用二分法的有序线性表，利用二分法查找元素查找元素X X的过程如下。的过程如下。步骤步骤1 1：将：将X X与线性表的中间项比较：与线性表的中间项比较：步骤步骤2 2：如果：如果X X的值与中间项的值相等，则的值与中间项的值相等，则查找成功，结束查找；查找成功，结束查找；步骤步骤3 3：如果：如果X X小于中间项的值，则在线性小于中间项的值，则在线性表的前半部分以二分法继续查找；如果表的前半部分以二分法继续查找；如果X X大于大于中间项的值，则在线性表的后半部分以二分法中间项的值，则在线性表的后半部分以二分法继续查找。继
21、续查找。考点 二分法查找28 顺序查找法每一次比较，只将查找范顺序查找法每一次比较，只将查找范围减少围减少1 1，而二分法查找，而二分法查找，每比较一次，可每比较一次，可将查找范围减少为原来的一半将查找范围减少为原来的一半，效率大大，效率大大提高。提高。对于长度为对于长度为n n的有序线性表，在的有序线性表，在最坏情最坏情况下，二分法查找只需比较况下，二分法查找只需比较loglog2 2n n次次，而，而顺顺序查找需要比较序查找需要比较n n次次。29考点 排序1.8 排序冒泡排序法和快速排序法都属于交换类排序法。冒泡排序法和快速排序法都属于交换类排序法。（1 1）冒泡排序法）冒泡排序法 依次
22、比较相邻的两个数，将小数放在前面，依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第大数放在后面。即在第一趟：首先比较第1 1个和个和第第2 2个数，将小数放前，大数放后。然后比较第个数，将小数放前，大数放后。然后比较第2 2个数和第个数和第3 3个数，将小数放前，大数放后个数，将小数放前，大数放后第一第一趟结束，将最大的数放到了最后。在第二趟：仍趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较从第一对数开始比较,一直比较到倒数第二个数一直比较到倒数第二个数,第二趟结束，在倒数第二的位置上得到一个新的第二趟结束，在倒数第二的位置上得到一个新的最大数。如此下去
23、，重复以上过程，直至最终完最大数。如此下去，重复以上过程，直至最终完成排序。成排序。30第一轮的比较过程：第一轮的比较过程：For j=1 to 5 For j=1 to 5 if a(j)a(j+1)Then if a(j)a(j+1)Then t=a(j):a(j)=a(j+1):a(j+1)=t t=a(j):a(j)=a(j+1):a(j+1)=t End if End if Next j Next j31 第第1 1轮：轮：For j=1 to 4 For j=1 to 4 If a(j)a(j+1)Then If a(j)a(j+1)Then t=a(j):a(j)=a(j+1):
24、a(j+1)=t t=a(j):a(j)=a(j+1):a(j+1)=t End if End if Next j Next j 第第2 2轮：轮：For j=1 to 3 For j=1 to 3 If a(j)a(j+1)Then If a(j)a(j+1)Then t=a(j):a(j)=a(j+1):a(j+1)=t t=a(j):a(j)=a(j+1):a(j+1)=t End if End if Next j Next j 第第3 3轮：轮：For j=1 to 2For j=1 to 2 If a(j)a(j+1)Then If a(j)a(j+1)Then t=a(j):a(j
25、)=a(j+1):a(j+1)=t t=a(j):a(j)=a(j+1):a(j+1)=t End if End if Next j Next j32第第i i轮：轮：for j=1 to for j=1 to 5-i5-i if a(j)a(j+1)Then if a(j)a(j+1)Then t=a(j)t=a(j)a(j)=a(j+1)a(j)=a(j+1)a(j+1)=t a(j+1)=t End if End ifNext jNext j33冒泡法程序清单：冒泡法程序清单：Dim a(1 To 5)As IntegerDim a(1 To 5)As IntegerFor i=1 To
26、 5For i=1 To 5 a(i)=Val(InputBox(a(i)=Val(InputBox(输入一个数输入一个数)Next iNext iFor i=1 to 4For i=1 to 4 For j=1 To 5-i For j=1 To 5-i if a(j)a(j+1)Then if a(j)a(j+1)Then t=a(j):a(j)=a(j+1):a(j+1)=t t=a(j):a(j)=a(j+1):a(j+1)=t End if End if Next j Next jNext i Next i For i=1 To 5For i=1 To 5 Print a(i);Pr
27、int a(i);Next iNext i冒泡排序冒泡排序34 1 1、对于长度为、对于长度为 n n 的线性表，在最坏情况的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的下，下列各排序法所对应的比较次数中正确的是（是（D D ）。）。A A）冒泡排序）冒泡排序 n/2 n/2 B B）冒泡排序为）冒泡排序为 n(n-1)/2 n(n-1)/2 C C）快速排序为）快速排序为 n n D D）选择排序为）选择排序为 n 2 2、对于长度为、对于长度为 n n 的线性表进行顺序查找，的线性表进行顺序查找，在最坏情况下所需要的比较次数为（在最坏情况下所需要的比较次数为（C C）。）。A
28、 A）loglog2 2n n B B）n/2 n/2 C C）n n D D）n+1 n+1 35第二章数据库设计基础 数据库技术的根本目标是数据库技术的根本目标是解决数据共享问题。解决数据共享问题。数据库管理系统（数据库管理系统（DBMSDBMS）是一种系统软件，）是一种系统软件，负责数据库中的数据组织、数据操作、数据维护、负责数据库中的数据组织、数据操作、数据维护、控制及保护和数据服务等。控制及保护和数据服务等。数据库管理系统是数数据库管理系统是数据系统的核心据系统的核心。为完成数据库管理系统的功能，数据库管理为完成数据库管理系统的功能，数据库管理系统提供相应的数据语言：系统提供相应的数
29、据语言：数据定义语言、数据数据定义语言、数据操纵语言、数据控制语言操纵语言、数据控制语言。考点 数据库的基本概念36 1.1.数据库系统的发展数据库系统的发展 数据管理技术的发展经历了三个阶段：数据管理技术的发展经历了三个阶段：人工人工管理阶段、文件系统阶段和数据库系统阶段管理阶段、文件系统阶段和数据库系统阶段。考点 数据库系统的发展和基本特点 2 2数据库系统的特点数据库系统的特点 数据独立性数据独立性：数据与程序间的互不依赖性，：数据与程序间的互不依赖性，即数据库中的数据独立于应用程序而不依赖于即数据库中的数据独立于应用程序而不依赖于应用程序。应用程序。4.1 数据库的基本概念37 数据的
30、独立性分为数据的独立性分为物理独立性与逻辑独立物理独立性与逻辑独立性性。（1 1）物理独立性：当数据的物理结构改变）物理独立性：当数据的物理结构改变时，如存储设备的更换、存储方式改变等，应时，如存储设备的更换、存储方式改变等，应用程序都不用改变。用程序都不用改变。（2 2）逻辑独立性：数据的逻辑结构改变了，）逻辑独立性：数据的逻辑结构改变了，如修改数据模式、增加新的数据类型、改变数如修改数据模式、增加新的数据类型、改变数据间联系等，用户程序都可以不变。据间联系等，用户程序都可以不变。38 1.1.数据统系统的数据统系统的3 3级模式级模式 （1 1）外模式，外模式也称子模式，是数据外模式，外模
31、式也称子模式，是数据库用户的数据视图，是与某一应用有关的数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。的逻辑表示。一个概念模式可以有若干个外模一个概念模式可以有若干个外模式。式。（2 2）概念模式，也称逻辑模式、模式，是概念模式，也称逻辑模式、模式，是全体用户（应用）全体用户（应用）公共数据视图。一个数据库公共数据视图。一个数据库只有一个概念模式只有一个概念模式。（3 3）内模式，内模式又称物理模式，它给）内模式，内模式又称物理模式，它给出了数据库物理存储结构与物理存取方法。出了数据库物理存储结构与物理存取方法。考点 数据库系统的内部体系结构4.2 4.2 数据库系统的内部体系结构数
32、据库系统的内部体系结构39 内模式处于最底层，它反映了数据在计内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式，概念模式算机物理结构中的实际存储形式，概念模式处于中间层，它反映了设计者的数据全局逻处于中间层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用辑要求，而外模式处于最外层，它反映了用户对数据的要求。户对数据的要求。4041 2.2.数据库系统的两级映射数据库系统的两级映射 两级映射保证了数据库系统中数据的独立两级映射保证了数据库系统中数据的独立性。性。（1 1）外模式到概念模式的映射。概念模式）外模式到概念模式的映射。概念模式是一个全局模式而外模式是用户
33、的局部模式。是一个全局模式而外模式是用户的局部模式。一个概念模式中可以定义多个外模式，而每个一个概念模式中可以定义多个外模式，而每个外模式是概念模式的一个基本视图。外模式是概念模式的一个基本视图。（2 2）概念模式到内模式的映射。该映射给）概念模式到内模式的映射。该映射给出了概念模式中数据的全局逻辑结构到数据的出了概念模式中数据的全局逻辑结构到数据的物理存储结构间的对应关系。物理存储结构间的对应关系。考点 数据库系统的内部体系结构42 数据模型通常由数据模型通常由数据结构、数据操作及数据结构、数据操作及数据约束数据约束三部分组成。三部分组成。数据库管理系统所支持的数据模型分为数据库管理系统所支
34、持的数据模型分为3 3种：种：层次模型、网状模型和关系模型层次模型、网状模型和关系模型。考点 数据模型的基本概念4.4 4.4 数据模型的基本概念数据模型的基本概念43 1.E-R1.E-R模型的基本概念模型的基本概念（1 1）实体：现实世界中的事物可以抽象成为实）实体：现实世界中的事物可以抽象成为实体，实体是概念世界中的基本单位。体，实体是概念世界中的基本单位。（2 2）属性：现实世界中事物的一些特性。）属性：现实世界中事物的一些特性。（3 3）码：唯一标识实体的属性集称为码。）码：唯一标识实体的属性集称为码。（4 4）域：属性的取值范围称为该属性的域。）域：属性的取值范围称为该属性的域。（
35、5 5）联系：在现实世界中事物间的关联称为联）联系：在现实世界中事物间的关联称为联系。系。两个实体集间的联系有：两个实体集间的联系有：一对一、一对多（多一对一、一对多（多对一）、多对多的联系。对一）、多对多的联系。考点 E-R模型4.5 E-R4.5 E-R模型模型44 关系模式采用二维表来表示，一个关系对应一张二关系模式采用二维表来表示，一个关系对应一张二维表。（一个关系就是一个二维表，但是一个二维表不维表。（一个关系就是一个二维表，但是一个二维表不一定是一个关系。）一定是一个关系。）元组：元组：在一个二维表中，水平方向的行称为元组。在一个二维表中，水平方向的行称为元组。元组对应存储文件中的
36、一个具体元组对应存储文件中的一个具体记录记录。属性属性：二维表中垂直方向的列称为属性，每一列有：二维表中垂直方向的列称为属性，每一列有一个属性名。一个属性名。域域：属性的取值范围，也就是不同元组对同一属性：属性的取值范围，也就是不同元组对同一属性的取值所限定的范围。的取值所限定的范围。考点 关系模型4.6 4.6 关系模型关系模型45 在二维表中惟一标识元组的最小属性值在二维表中惟一标识元组的最小属性值称为该表的称为该表的键或码键或码。二维表中可能有。二维表中可能有若干个若干个健健，它们称为表的，它们称为表的侯选码或侯选健侯选码或侯选健。从二维。从二维表的所有侯选键选取一个作为用户使用的键表的
37、所有侯选键选取一个作为用户使用的键称为称为主键或主码主键或主码。表。表A A中的某属性集是某表中的某属性集是某表B B的键，则称该属性值为的键，则称该属性值为A A的外键或外码。的外键或外码。46课程号课程名授课学时授课学期J001数据库726J003C 程序设计542Z004操作系统725Z006编译原理726X001数值分析543X002面向对象364四个属性四个属性六个元组六个元组候选码候选码键键或一个关系的例子：课程表关系名关系名主键主键47 关系模型采用二维表来表示，一般满足下面关系模型采用二维表来表示，一般满足下面7 7个个性质：性质：（1 1）二维表中元组个数是有限的）二维表中元
38、组个数是有限的元组个数有元组个数有限性；限性；（2 2）二维表中元组均不相同）二维表中元组均不相同元组的唯一性；元组的唯一性；（3 3）二维表中元组的次序可以任意交换）二维表中元组的次序可以任意交换元组元组的次序无关性；的次序无关性；（4 4）二维表中元组的分量是不可分割的基本数据）二维表中元组的分量是不可分割的基本数据项项元组分量的原子性；元组分量的原子性；（5 5）二维表中属性名各不相同）二维表中属性名各不相同属性名唯一性；属性名唯一性；考点 关系模型48 （6 6）二维表中属性与次序无关，可任意交换）二维表中属性与次序无关，可任意交换属性的次序无关性；属性的次序无关性；（7 7）二维表属
39、性的分量具有与该属性相同的值）二维表属性的分量具有与该属性相同的值域域分量值域的统一性。分量值域的统一性。关系操纵：关系操纵：数据查询、数据的删除、数据插入、数据查询、数据的删除、数据插入、数据修改数据修改。关系模型允许定义三类数据约束，它们是关系模型允许定义三类数据约束，它们是实体实体完整性约束、参照完整性约束以及用户定义的完整完整性约束、参照完整性约束以及用户定义的完整性约束性约束。49 1 1、传统的集合运算、传统的集合运算 （1 1）投影运算）投影运算 从关系模式中从关系模式中指定若干个属性指定若干个属性组成新的关系称为投组成新的关系称为投影。经过投影运算得到一个新的关系，其关系模式所
40、包影。经过投影运算得到一个新的关系，其关系模式所包含的含的属性个数往往比原关系少或属性的排列顺序不同属性个数往往比原关系少或属性的排列顺序不同。（2 2）选择运算）选择运算 从关系中从关系中找出满足给定条件的元组找出满足给定条件的元组的操作称为选择。的操作称为选择。经过选择运算得到新的关系，其关系模式不变，但其中经过选择运算得到新的关系，其关系模式不变，但其中的元组是的元组是原关系的一个子集原关系的一个子集。（3 3）迪卡尔积）迪卡尔积 设有设有n n元关系元关系R R和和m m元关系元关系S S，它们分别有，它们分别有p p和和q q个元组，个元组，则则R R与与S S的笛卡儿积记为：的笛卡
41、儿积记为：R RS S。它是一个。它是一个m+nm+n元关系，元关系，元组个数是元组个数是p pq q。考点 关系代数4.7 4.7 关系代数关系代数50 2 2、关系代数的扩充运算、关系代数的扩充运算 （1 1）交）交 假设有假设有n n元关系元关系R R和和n n元关系元关系S S，它们的，它们的交仍然是一个交仍然是一个n n元关系，它由属于关系元关系，它由属于关系R R且且由属于关系由属于关系S S的元组组成，并记为的元组组成，并记为RSRS，它，它可由基本运算推导而得：可由基本运算推导而得：RSRSR-(R-S)R-(R-S)51 1.1.不改变关系表中的属性个数但能减少元组个数的是不
42、改变关系表中的属性个数但能减少元组个数的是_选择选择_。2.2.用树形结构表示实体之间联系的模型是用树形结构表示实体之间联系的模型是_ _层次模型层次模型_。3.3.与二维表中的与二维表中的“行行”的概念最接近的概念是的概念最接近的概念是_ _元组元组_。4.4.数据独立性是数据库技术的重要特点之一，所谓数据数据独立性是数据库技术的重要特点之一，所谓数据独立性是指（独立性是指（D D）。）。A A）数据与程序独立存放）数据与程序独立存放 B B）不同的数据被存放在不同的文件中）不同的数据被存放在不同的文件中 C C）不同的数据只能被对应的应用程序所使用）不同的数据只能被对应的应用程序所使用 D
43、 D）以上三种说法都不对）以上三种说法都不对 5.5.在学校中，在学校中，“班级班级”与与“学生学生”两个实体集之间的联两个实体集之间的联系属于（系属于（B B）。）。A A）一对一）一对一 B B）一对多）一对多 C C）多对一）多对一 D D）多对多）多对多52 6.6.关系数据库管理系统能实现的专门关系运算包括关系数据库管理系统能实现的专门关系运算包括（B B）。）。A)A)排序、索引、统计排序、索引、统计 B)B)选择、投影、连接选择、投影、连接 C)C)关联、更新、排序关联、更新、排序 D)D)显示、打印、制表显示、打印、制表 7.7.数据管理技术发展的三个阶段中，（数据管理技术发展
44、的三个阶段中，（A A）没有）没有专门的软件对数据进行管理专门的软件对数据进行管理 I I、人工管理阶段、人工管理阶段 IIII、文件系统阶段、文件系统阶段 IIIIII、数据库阶段、数据库阶段 A A）仅）仅I I B B）仅）仅II CII C）I I和和II DII D）IIII和和IIIIII53 8 8.下面关于数据库三级模式结构的叙述中，正确的下面关于数据库三级模式结构的叙述中，正确的是（是（B B ）。）。A A）内模式可以有多个，外模式和模式只有一个）内模式可以有多个，外模式和模式只有一个 B B）外模式可以有多个，内模式和模式只有一个）外模式可以有多个，内模式和模式只有一个
45、C C）内模式只有一个，模式和外模式可以有多个）内模式只有一个，模式和外模式可以有多个 D D）模式只有一个，外模式和内模式可以有多个）模式只有一个，外模式和内模式可以有多个 54 9 9.在数据库系统的组织结构中，下列在数据库系统的组织结构中，下列(A A)映映射把用户数据库与概念数据库联系了起来。射把用户数据库与概念数据库联系了起来。A A）外模式）外模式/模式模式 B B）内模式内模式/外模式外模式 C C）模式）模式/内模式内模式 D D）内模式）内模式/模式模式 10 10.对关系对关系S S和和R R进行集合运算，结果中既包进行集合运算，结果中既包含含S S中所有元组也包含中所有元
46、组也包含R R中所有元组，这样的集合中所有元组，这样的集合运算称为（运算称为（D D ）A)A)并运算并运算 B)B)交运算交运算 C)C)差运算差运算 D)D)积运算积运算55 1 11.1.数据库系统的内部结构体系中，索引属数据库系统的内部结构体系中，索引属于于(B B)。A)A)模式模式 B)B)内模式内模式 C)C)外模式外模式D)D)概念模式概念模式 说明：内模式又称物理模式，它给出了数据说明：内模式又称物理模式，它给出了数据库物理存储结构与物理存取方法。库物理存储结构与物理存取方法。1 12.2.在三级模式之间引入两层映像，其主要在三级模式之间引入两层映像，其主要功能之一是（功能之
47、一是（A A）。）。A)A)使数据与程序具有较高的独立性使数据与程序具有较高的独立性 B)B)使系统具有较高的通道能力使系统具有较高的通道能力 C)C)保持数据与程序的一致性保持数据与程序的一致性D)D)提高存储空间的利用率提高存储空间的利用率56 1 13.3.下列模式中，能够给出数据库物理存下列模式中，能够给出数据库物理存储结构与物理存取方法的是（储结构与物理存取方法的是（A A）。）。A)A)内模式内模式 B)B)外模式外模式 C)C)概念模式概念模式 D)D)逻辑模式逻辑模式数据库三种模式的概念理解数据库三种模式的概念理解 4.4.数据库系统的核心是（数据库系统的核心是（D D）。）。
48、A)A)数据模型数据模型 B)B)软件开发软件开发 C)C)数据库设计数据库设计D)D)数据库管理系统数据库管理系统57 1 15.5.将将E-RE-R图转换到关系模式时，实体与联系图转换到关系模式时，实体与联系都可以表示成（都可以表示成（B B）。）。A)A)属性属性B)B)关系关系C)C)记录记录D)D)码码 1 16.6.在关系中凡能唯一标识元组的最小属性集在关系中凡能唯一标识元组的最小属性集称为该表的键或码，二维表中可能有若干个键，称为该表的键或码，二维表中可能有若干个键，它们称为该表的（它们称为该表的（D D）。）。A)A)连接码连接码 B)B)关系码关系码 C)C)外码外码 D)D
49、)候选码候选码 1 17.7.关系模型允许定义关系模型允许定义3 3类数据约束，下列不类数据约束，下列不属于数据约束的是（属于数据约束的是（C C）。）。A)A)实体完整性约束实体完整性约束B)B)参照完整性约束参照完整性约束 C)C)属性完整性约束属性完整性约束 D)D)用户自定义用户自定义 58第三章软件工程基础 考点 软件工程基本概念1.1.软件定义与软件特点软件定义与软件特点 软件是软件是程序、数据和相关文档程序、数据和相关文档的完整集合。的完整集合。程序是软件开发人员根据用户需求开发的、用程程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的序设计语言描述的、
50、适合计算机执行的指令序列指令序列。根据应用目标的不同，软件可分根据应用目标的不同，软件可分应用软件、系统应用软件、系统软件和支撑软件软件和支撑软件（或工具软件）。（或工具软件）。3.1 3.1 软件工程基本概念软件工程基本概念592 2软件工程软件工程 为了为了摆脱软件危机摆脱软件危机，提出了软件工程的概，提出了软件工程的概念。念。软件工程学软件工程学是是研究软件开发和维护的普遍研究软件开发和维护的普遍原理与技术原理与技术的一门工程学科。的一门工程学科。所谓软件工程是指，所谓软件工程是指，采用工程的概念、原采用工程的概念、原理、技术和方法指导软件的开发与维护理、技术和方法指导软件的开发与维护。
