二级公共基础知识ppt课件教案

《二级公共基础知识ppt课件教案》由会员分享，可在线阅读，更多相关《二级公共基础知识ppt课件教案（189页珍藏版）》请在金锄头文库上搜索。

1、二级公共基础知识ppt课件Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望 一、涉及面广，但难度小一、涉及面广，但难度小一、涉及面广，但难度小一、涉及面广，但难度小 公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议 计算机等级二级理论考试中有关公共知识部分计算机等级二级理论考试中有关公共知识部分计算机等级二级理论考试中有关公共知识部分计算机等级二级理论考试中有关公共知识部分的题目共有的题目共有的题目共有的题目共有

2、15151515道，涉及道，涉及道，涉及道，涉及算法及数据结构算法及数据结构算法及数据结构算法及数据结构、程序设计基础程序设计基础程序设计基础程序设计基础、软件工程基础软件工程基础软件工程基础软件工程基础和和和和数据库设计基础数据库设计基础数据库设计基础数据库设计基础等四门学科，但是从整等四门学科，但是从整等四门学科，但是从整等四门学科，但是从整体上分析，考试中的考核内容的难度不大，考点也相对体上分析，考试中的考核内容的难度不大，考点也相对体上分析，考试中的考核内容的难度不大，考点也相对体上分析，考试中的考核内容的难度不大，考点也相对集中些。集中些。集中些。集中些。2二、考核重点为基本概念、基

3、本方法二、考核重点为基本概念、基本方法二、考核重点为基本概念、基本方法二、考核重点为基本概念、基本方法 和基本运算和基本运算和基本运算和基本运算 计算机等级二级理论考试中涉及的计算机等级二级理论考试中涉及的计算机等级二级理论考试中涉及的计算机等级二级理论考试中涉及的题目都是题目都是题目都是题目都是基本概念基本概念基本概念基本概念、基本方法基本方法基本方法基本方法和和和和基本运算基本运算基本运算基本运算，考核以概念和认识性内容为主，理解性、应考核以概念和认识性内容为主，理解性、应考核以概念和认识性内容为主，理解性、应考核以概念和认识性内容为主，理解性、应用性内容极少。用性内容极少。用性内容极少。

4、用性内容极少。 3三、考核重点是数据结构和算法三、考核重点是数据结构和算法三、考核重点是数据结构和算法三、考核重点是数据结构和算法 以下是对以往二级理论考试的大概统计：以下是对以往二级理论考试的大概统计：以下是对以往二级理论考试的大概统计：以下是对以往二级理论考试的大概统计： v 算法及数据结构算法及数据结构算法及数据结构算法及数据结构： 50% 50% 50% 50% v 程序设计基础程序设计基础程序设计基础程序设计基础：12.5%12.5%12.5%12.5%v 软件工程基础软件工程基础软件工程基础软件工程基础：18.75%18.75%18.75%18.75%v 数据库设计基础数据库设计基

5、础数据库设计基础数据库设计基础：18.75%18.75%18.75%18.75%4四、六点复习及应试建议四、六点复习及应试建议四、六点复习及应试建议四、六点复习及应试建议vv 复习的关键是复习的关键是考生必须准确判断和掌握常见考点考生必须准确判断和掌握常见考点vv 公共基础知识部分的知识点多、杂，考生在学习过程中应理公共基础知识部分的知识点多、杂，考生在学习过程中应理 清其中的清其中的脉络关系（即框架提纲）脉络关系（即框架提纲），才能有效地组织和记，才能有效地组织和记住住 各知识点各知识点vv考生考生不要太追求灵活掌握该部分的内容不要太追求灵活掌握该部分的内容，最好经历一个，最好经历一个“ “

6、先先死死 后活、熟能生巧后活、熟能生巧” ”的过程，这是多数考生常犯的另一种错的过程，这是多数考生常犯的另一种错误误vv 最后给大家一个最后给大家一个答题技巧答题技巧：“ “会就会，不会就不会会就会，不会就不会” ”，不要不要拖拖 时间，要考虑成本时间，要考虑成本/ /效果的关系，为后面的题目提供时间效果的关系，为后面的题目提供时间。5 共讲授共讲授共讲授共讲授 20202020个学时，具体安排如下：个学时，具体安排如下：个学时，具体安排如下：个学时，具体安排如下：vv 第第第第 周周周周 （ 月月月月 日）：日）：日）：日）： 算法、数据结构算法、数据结构算法、数据结构算法、数据结构（上）（

7、上）（上）（上）（地点：）（地点：）（地点：）（地点：）vv 第第第第 周周周周 （ 月月月月 日）：日）：日）：日）：数据结构数据结构数据结构数据结构( ( ( (下）、软件工程、程序设计基础下）、软件工程、程序设计基础下）、软件工程、程序设计基础下）、软件工程、程序设计基础（地点：）（地点：）（地点：）（地点：）vv 第第第第 周周周周 （ 月月月月 日）：日）：日）：日）： 数据库系统、真题讲解数据库系统、真题讲解数据库系统、真题讲解数据库系统、真题讲解（地点：）（地点：）（地点：）（地点：） 本本 课课 程程 授授 课课 安安 排排61 1、了解算法的基本概念和一些、了解算法的基本概念

8、和一些常用的算法常用的算法，学会计算算法的，学会计算算法的时间复杂度时间复杂度；2 2、掌握数据结构的基本概念，并了解数据的、掌握数据结构的基本概念，并了解数据的逻辑结构逻辑结构和和存储结构存储结构，学会利，学会利 用图形的方式表示数据结构用图形的方式表示数据结构 ；学学学学习习习习目目目目标标标标与与与与要要要要求求求求 算法与数据结构：算法与数据结构：算法与数据结构：算法与数据结构：3 3、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的 线性表的基本运算；线性表的基本运算； 4 4、了解栈和队列的基本概念，并掌

9、握它们的基本运算；、了解栈和队列的基本概念，并掌握它们的基本运算； 5 5、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循 环链表的基本概念和基本操作；环链表的基本概念和基本操作； 6 6、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存 储结构和遍历技术；储结构和遍历技术； 7 7、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据； 8 8、学会利用相关的排

10、序技术实现无序数列的排序操作。、学会利用相关的排序技术实现无序数列的排序操作。 71 1、了解软件工程的基本概念；、了解软件工程的基本概念；2 2、了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；、了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；学学学学习习习习目目目目标标标标与与与与要要要要求求求求 软件工程软件工程软件工程软件工程：3 3、了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需、了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需 求分析的方法和需要完成的任务；求分析的方法和需要完成的任务； 4 4、了解数据流图的使用方法；、了解数据流

11、图的使用方法； 5 5、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些 常用工具；常用工具； 6 6、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件 测试方法的区别和各自的功能与特点；测试方法的区别和各自的功能与特点； 7 7、了解程序调试的方法和原则、了解程序调试的方法和原则 。81 1、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序 设计的基本规则；设计的基本规则；

12、 2 2、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点; ;学学学学习习习习目目目目标标标标与与与与要要要要求求求求 程序设计基础程序设计基础程序设计基础程序设计基础：3 3、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。 数据库系统数据库系统数据库系统数据库系统：1 1、了解数据库系统的基本概念，以及数据库系统的发展；、了解数据库系统的基本概念，以及数据库系统的发展； 2 2、了解数据模型的基本概念，并对、了解数据模型的基本概念

13、，并对E-RE-R模型、层次模型、网状模型和关系模型模型、层次模型、网状模型和关系模型 进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识；进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识； 3 3、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算；、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算； 4 4、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。 9第一章 算法与数据结构二二级公共基公共基础知知识返回16算算算算法法法法与与与与数数数数据据据据结结结结构构构构一、

14、算法一、算法1 1、算法的基本概念、算法的基本概念 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法具有有穷性有穷性、确定性确定性、可行性可行性、输入输入和输出输出（拥有足够的情报）等个重要特性。17学学学学习习习习目目目目标标标标与与与与要要要要求求求求2 2、算法的基本要素、算法的基本要素v 对数据对象的运算和操作： 算术运算、逻辑运算、关系运算、数据传输 算法中各操作之间的执行顺序； 描述算法的工具通常有传统流程图、N-S结构化流程 图、算法描

15、述语言等； 一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。v 算法的控制结构： 18算算算算法法法法与与与与数数数数据据据据结结结结构构构构3 3、算法设计的基本方法、算法设计的基本方法v 列举法v 归纳法v 递推v 递归（以简洁的形式设计和描述算法）v 减半递推技术v 回溯法19算算算算法法法法与与与与数数数数据据据据结结结结构构构构二、算法的复杂度二、算法的复杂度1 1、时间复杂度、时间复杂度v 依据算法编制的程序在计算机上运行时所消耗的时间 来度量。通常有事后统计法和事前分析估算法。v 一个算法是由控制结构（顺序、分支和循环）和原操 作构成的，算法时间取决于两者的综合效果。v

16、 算法中基本操作重复执行次数n和算法执行时间同步 增长，称作算法的时间复杂度。20算算算算法法法法与与与与数数数数据据据据结结结结构构构构2 2、空间复杂度、空间复杂度v 一般是指执行这个算法所需要的内存空间。v 一个算法所占用的存储空间包括算法程序所占的空间、 输入的初始数据所占的存储空间以及某种数据结构所需 要的附加存储空间。v 一个上机执行的程序除了需要存储空间来寄存本身所用 指令、常数、变量和输入数据外，也需要一些对数据进 行操作的工作单元和存储一些为实现计算所需信息的辅 助空间。21算算算算法法法法与与与与数数数数据据据据结结结结构构构构3 3、例题讲解、例题讲解v 算法的时间复杂度

17、是指算法的时间复杂度是指( ( C C ) ) A A、执行算法程序所需要的时间执行算法程序所需要的时间 B B、算法程序的长度算法程序的长度 C C、算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D D、算法程序中的指令条数算法程序中的指令条数v 算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【1 1】和拥有足够和拥有足够 的情报。的情报。 【答案】【答案】: :有穷性有穷性v 算法的空间复杂度是指算法的空间复杂度是指( ( D D ) ) A) A) 算法程序的长度算法程序的长度 B) B) 算法程序中的指令条数算法程序中的指令条数 C) C)

18、算法程序所占的存储空间算法程序所占的存储空间 D) D) 执行过程中所需要的存储空间执行过程中所需要的存储空间22算算算算法法法法与与与与数数数数据据据据结结结结构构构构v 在计算机中，算法是指（ B B ） A) 加工方法 B) B) 解题方案的准确而完整的描述解题方案的准确而完整的描述 C) 排序方法 D) 查询方法v 算法分析的目的是( D D ) A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性 D) D) 分析算法的效率以求改进分析算法的效率以求改进v 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的 【 1 1 】 。【答

19、案】【答案】: :时间复杂度和空间复杂度时间复杂度和空间复杂度23算算算算法法法法与与与与数数数数据据据据结结结结构构构构三、数据结构（三、数据结构（ Data Structure）1 1、数据结构研究的主要内容、数据结构研究的主要内容v当今计算机应用的特点： 1、所处理的数据量大且具有一定的关系； 2、对其操作不再是单纯的数值计算，而更多地是需 要对其进行组织、管理和检索。 对数据的讨论不单是数据本身，还要包括数据与数对数据的讨论不单是数据本身，还要包括数据与数据之间的关系。据之间的关系。24特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依

20、据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等。v 应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。25v 应用举例2家庭血缘关系图 表示家庭成员的辈分关系，使用下图1-1所示的形式描述。图图图图 1-1 1-1 1-1 1-1 家庭血缘关系图特点： 在求解过程中，所处理的数据之间具有层次关系，这是我们 所说的树形结构； 对它的操作有：建立树形结构，输出终结点内容等。26v 应用举例3制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需

21、要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：27这种数据可以用下面的图来表示：27v课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图 1-2 计算机专业必修课程开设先后关系2828 1 1、数据的、数据的逻辑结构逻辑结构 2 2、数据的、数据的存储结构存储结构 3 3、数据的、数据的运算运算：检索、排序、插入、删除、修改等。：检索、排序、插入、删除、修改等。 A A线性结构线性结构B B非线性结构非线性结构A A顺序存储顺序存储 B B链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图

22、形结构数数据据结结构构的的三三个个方方面面(亦称物理结构亦称物理结构)数据结构的主要研究问题：29292 2、基本概念和术语、基本概念和术语 数据结构是一门研究数据数据数据数据组织组织、存储存储和运算运算的一般方法的学科。例：整数整数(1,2)、实数实数(1.1,1.2)字符串字符串(Beijing)、图形图形、声音声音。计算机管理图书问题 ： 在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如：3030数据元素在计算机中的表示 数据结构是一门

23、研究数据数据数据数据组织组织、存储存储和运算运算的一般方法的学科。如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9 对数据结构中的节点进行操作处理对数据结构中的节点进行操作处理（插入、删除、修改、查找、排序）（插入、删除、修改、查找、排序）3131v 数据元素数据元素( (Data Element)Data Element) 数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元素可由若干数据项数据项(D

24、ata ItemData Item)组成。数据项是数据的最小单位。数据元素亦称节点节点或记录记录。数据结构可描述为数据结构可描述为 Group=Group=（D D，R R）有限个数据元素的集合有限个数据元素的集合有限个节点间关系的集合有限个节点间关系的集合3232数据结构可描述为数据结构可描述为 Group=（D，R）l 例例1：一年四季的数据结构可表示成：一年四季的数据结构可表示成B=（D，R） D=春，夏，秋，冬春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）l 例例2：家庭成员数据结构可表示成：家庭成员数据结构可表示成B=（D，R）D=父亲，儿子

25、，女儿父亲，儿子，女儿 R=（父亲，儿子），（父亲，女儿）（父亲，儿子），（父亲，女儿）冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿33数据结构也可用图形表示数据结构也可用图形表示l一年四季的数据结构可表示成一年四季的数据结构可表示成l家庭成员数据结构可表示成家庭成员数据结构可表示成冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿（ 概念：结点、前件、后件、根结点、叶子 ）34v 树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式计算机程序管理系统也是典型的计算机程序管理系统也是典型的树形结构树形结构。35HGFECDBA树形结构树形结构树形结构树形结构 结点间具有分层次的连接关系结点间具有分层

26、次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系HHB BC CD DE EF FGGA A36 D=1 , 2 , 3 , 4 D=1 , 2 , 3 , 4R=(1,2),(1,3), R=(1,2),(1,3), (1,4),(2,3), (1,4),(2,3), (3,4),(2,4) (3,4),(2,4) 2 21 13 3 D= 1 , 2 , 3 D= 1 , 2 , 3 R=(1,2),(2,3),(3,2),(1,3) R=(1,2),(2,3),(3,2),(1,3)v 图形结构图形结构节点间的连结是任意的节点间的连结是任意的1 14 42 23 3373

27、 3、例题讲解、例题讲解v数据处理的最小单位是数据处理的最小单位是( ( C C ) ) A)A)数据数据 B)B)数据元素数据元素 C) C) 数据项数据项 D) D) 数据结构数据结构v数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及( ( A A ) ) A) A) 数据的存储结构数据的存储结构 B) B) 计算方法计算方法 C) C) 数据映象数据映象 D) D) 逻辑存储逻辑存储v数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【4 4】 以及

28、对数据的以及对数据的操作运算。操作运算。 【答案【答案】物理结构（或存储结构）物理结构（或存储结构）38v 线性结构与非线性结构：线性结构与非线性结构：v 线性结构：有且只有一个根结点；每一个结线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。点最多有一个前件，也最多有一个后件。 如：一年四季，如：一年四季，2626个英文字母个英文字母v非线性结构：线性以外的数据结构。非线性结构：线性以外的数据结构。 如：反映家庭成员间辈分关系的数据结构如：反映家庭成员间辈分关系的数据结构 算算算算法法法法与与与与数数数数据据据据结结结结构构构构394、线性表、线性表（Linear L

29、ist）学学 生生 成成 绩绩 表表 ( (按成绩排列按成绩排列) )8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓98611099861109成成 绩绩姓姓 名名学学 号号v 线性表线性表结点间是以线性关系联结：结点间是以线性关系联结：v 线性表线性表：具有线性结构的有限序列。 数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。40v线性表的定义线性表的定义: : 线性表线性表是是n n个元素的有限序列，它们之间的关系可以排成个元素的有限序列，它们之间的关系可以排成一个线性序列：一个线性序列

30、：a1a1，a2a2， ，aiai， ，anan 其中其中n n称作表的称作表的长度长度，当，当n=0n=0时，称作时，称作空表空表。v线性表的特点：线性表的特点： 1 1、线性表中所有元素的性质相同。、线性表中所有元素的性质相同。 2 2、除第一个和最后一个数据元素之外，其它数据元素有且、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱，最仅有一个前驱和一个后继。第一个数据元素无前驱，最 后一个数据元素无后继。后一个数据元素无后继。 3 3、数据元素在表中的位置只取决于它自身的序号。、数据元素在表中的位置只取决于它自身的序号。v在线性表上常用的运

31、算有：在线性表上常用的运算有： 初始化、求长度、取元素、修改、前插、删除、检索、排序初始化、求长度、取元素、修改、前插、删除、检索、排序4141v 线性表的线性表的 顺序存储结构 及其及其 插入 与与 删除 操作操作特点：特点： 1 1、线性表中数据元素类型一致，只有、线性表中数据元素类型一致，只有数据域数据域，存储空间，存储空间 利用率高。利用率高。 2 2、所有元素所占的存储空间是连续的。、所有元素所占的存储空间是连续的。 3 3、各数据元素在存储空间中是按、各数据元素在存储空间中是按逻辑顺序逻辑顺序依次存放的依次存放的 （a a）做插入、删除时需移动大量元素。做插入、删除时需移动大量元素

32、。 （b b）空间估计不明时，按最大空间分配。空间估计不明时，按最大空间分配。算算算算法法法法与与与与数数数数据据据据结结结结构构构构42顺顺序序存存储储存储地址存储地址存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素元素1 1L L L Lo o o oL Lo o + + mL Lo o+(i-1)+(i-1)mLo+Lo+（n-1)n-1)mLoc(Loc(元素元素i)=Li)=Lo o+ +（i-1)i-1)m每个元素所占用每个元素所占用的存储单元个数的存储单元个数v 线性表的线性表的 顺序存储结构顺序存储结构：首地址首地址起始地址起始地址基地址基地址43元素a1元素

33、a2.元素ai+1. 0 0 1 1i i 线性表的顺序存储结构线性表的顺序存储结构可用可用C C语言中的一维数组来描述语言中的一维数组来描述. .第第i i个元素的个元素的a ai i存储地址：存储地址：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)* )+(i-1)* m mVV VV ViViVm-1Vm-1 int VM; int VM; 其中：其中：V V是数组的名字，是数组的名字，M M是数组大小，是数组大小， 假设数组中的元素是整型类型假设数组中的元素是整型类型算算算算法法法法与与与与数数数数据据据据结结结结构构构构44v插入运算插入运算.a2a a1

34、 1an.ai+1ai01i-1in-1a ai-1i-1.a a2 2a a1 1a alengthlengtha 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 alengthlength插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：4545在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据

35、元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。v删除算法的分析删除算法的分析4646q 线性表的例题讲解线性表的例题讲解v 顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【1 1】 的存储单元中。的存储单元中。 【答案【答案】相邻相邻v 长度为长度为n n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元 素概率都相等时，插入一个元素所需移动元素的平均个数素概率都相等时，插入一个元素所需移动元素的平均个数 为为【2 2】 。 【答案【答案】 n/2n/2v 线性表线性表L=(a1,a2,a

36、3,L=(a1,a2,a3,aiai，an)an)，下列说法正确的是（下列说法正确的是（D D） A) A) 每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B) B) 线性表中至少要有一个元素线性表中至少要有一个元素 C) C) 表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D) D) 除第一个元素和最后一个元素外，其余每个元素都有一除第一个元素和最后一个元素外，其余每个元素都有一 个且只有一个直接前件和直接后件个且只有一个直接前件和直接后件4747v数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的

37、是数据的( ( C C ) ) A) A) 存储结构存储结构B) B) 物理结构物理结构 C) C) 逻辑结构逻辑结构D) D) 物理和存储结构物理和存储结构 下列叙述中，错误的是（下列叙述中，错误的是（ B B ） A) A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 数据的存储结构

38、是指（数据的存储结构是指（ B B ） A A）数据所占的存储空间数据所占的存储空间 B B）数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示 C C）数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D D）存储在外存中的数据存储在外存中的数据48 根据数据结构中各数据元素之间前后件关系的复杂程度，一根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成般将数据结构分成( ( C C ) ) A) A) 动态结构和静态结构动态结构和静态结构 B) B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) C) 线性结构和非线性结构线性结构和非线性结构 D) D)

39、 内部结构和外部结构内部结构和外部结构 数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【2 2】两大类。两大类。非线性结构非线性结构 当线性表采用顺序存储结构实现存储时，其主要特点是当线性表采用顺序存储结构实现存储时，其主要特点是【1】。 【答案【答案】逻辑结构中相邻的结点在存储结构中仍相邻。逻辑结构中相邻的结点在存储结构中仍相邻。49495 5、堆栈和队列、堆栈和队列q 堆栈和队列的定义堆栈和队列的定义 栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限制的线性表，故也称为限定性的数据结构。限定性的数据结构。v

40、 堆栈的定义堆栈的定义堆栈：堆栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表, ,此种此种 结构称为结构称为后进先出。后进先出。设栈设栈s=s=（a a1 1，a a2 2，a ai i， ，a an n）, ,其中其中a a1 1是是栈底栈底元素，元素， a an n是是栈顶栈顶元素。元素。栈顶（栈顶（top)top)：允许插入和删除的一端；允许插入和删除的一端；约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。栈底栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。 a1

41、a2. an进栈进栈出栈出栈栈顶栈顶栈底栈底5050 a1 a2. an进栈进栈出栈出栈栈顶栈顶栈底栈底5151v 队列的定义队列的定义队列：队列：一种特殊的线性结构，限定只能在表的一端进行插入，一种特殊的线性结构，限定只能在表的一端进行插入， 在表的另一端进行删除的线性表。此种结构称为在表的另一端进行删除的线性表。此种结构称为先进先进 先出（先出（FIFO）表表。 a1 , a2 , a3 , an-1 , an队队 列列 示示 意意 图图队队头头队队尾尾v 队列的主要运算队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元

42、素。52出出队队入入队队rearrearfrontfront52v 循环队列及其运算循环队列及其运算循环循环队列：队列：将队列存储空间的最后一个位置绕到第一个位置，将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。形成逻辑上的环状空间，供队列循环使用。循环队列的元素：循环队列的元素：从排头指针指向的后一个位置直到队尾指针从排头指针指向的后一个位置直到队尾指针指向的位置之间所有的元素。指向的位置之间所有的元素。说明：说明：为了能够区分队列满与空，设置一个标志为了能够区分队列满与空，设置一个标志s s。53s=s=0 0 表示队列空表示队列空1 1 表示队列非空表示

43、队列非空队列空与满的条件：队列空与满的条件：队列空时，s=0；队列满时，s=1且front=rear。53循环队列的运算：循环队列的运算：入队运算和退队运算入队运算和退队运算入队运算：是指在循环队列中的队尾加入一新元素。入队运算：是指在循环队列中的队尾加入一新元素。具体操作：具体操作：（1 1）将队尾指针进一，即）将队尾指针进一，即rear=rear+1rear=rear+1。 注：当注：当rear=m+1rear=m+1时，重置时，重置rear=1rear=1。（2 2）将新元素插入到）将新元素插入到rearrear指向的位置。指向的位置。注：当注：当s=1s=1且且rear=frontre

44、ar=front时，循环队列满，不能再进行入队运算，称为时，循环队列满，不能再进行入队运算，称为“上溢上溢”。退队运算：是指在循环队列的排头位置退出一个元素并赋给指定的变量。退队运算：是指在循环队列的排头位置退出一个元素并赋给指定的变量。具体操作：具体操作：（1 1）将排头指针进一，即）将排头指针进一，即front=front+1front=front+1。 注：当注：当front=m+1front=m+1时，重置时，重置front=1front=1。（2 2）将排头指针指向位置的后一个元素赋给指定的变量。）将排头指针指向位置的后一个元素赋给指定的变量。注：当注：当s=0s=0时，循环队列为空

45、，再不能进行退队运算，称为时，循环队列为空，再不能进行退队运算，称为“下溢下溢”。5454q 堆栈和队列的例题讲解堆栈和队列的例题讲解v栈和队列的共同特点是（栈和队列的共同特点是（ C C ） A)A)都是先进先出都是先进先出 B) B) 都是先进后出都是先进后出 C) C) 只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D) D) 没有共同点没有共同点v如果进栈序列为如果进栈序列为e1,e2,e3,e4e1,e2,e3,e4，则可能的出栈序列是（则可能的出栈序列是（ B B ） A) e3,e1,e4,e2 A) e3,e1,e4,e2 B) e4,e3,e2,e1B) e4,e

46、3,e2,e1 C) e3,e4,e1,e2 C) e3,e4,e1,e2 D) D) 任意顺序任意顺序v一些重要的程序语言一些重要的程序语言( (如如C C语言和语言和PascalPascal语言语言) ) 允许过程的递归允许过程的递归调用。而实现递归调用中的存储分配通常用（调用。而实现递归调用中的存储分配通常用（ A A ） A) A) 栈栈 B) B) 堆堆 C) C) 数组数组 D) D) 链表链表 5555v 栈底至栈顶依次存放元素栈底至栈顶依次存放元素A A、B B、C C、D D，在第五个元素在第五个元素E E 入栈前，栈中元素可以出栈，则出栈序列可能是（入栈前，栈中元素可以出栈

47、，则出栈序列可能是（ B B ） A) ABCEDA) ABCED B) DCBEAB) DCBEA C) DBCEA C) DBCEA D) CDABE D) CDABE v 栈通常采用的两种存储结构是（栈通常采用的两种存储结构是（ A A ） A) A) 顺序存储结构和链表存储结构顺序存储结构和链表存储结构 B) B) 散列方式和索引方式散列方式和索引方式 C) C) 链表存储结构和数组链表存储结构和数组 D) D) 线性存储结构和非线性存储结构线性存储结构和非线性存储结构v 栈和队列通常采用的存储结构是栈和队列通常采用的存储结构是 【1 1】。 【答案【答案】链式存储和顺序存储链式存储和

48、顺序存储v 下列数据结构中，按先进后出原则组织数据的是（下列数据结构中，按先进后出原则组织数据的是（ B B ） A) A) 线性链表线性链表 B) B) 栈栈 C) C) 循环链表循环链表 D) D) 顺序表顺序表5656v当循环队列非空且队尾指针等于队头指针时，说明循环队列已当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为满，不能进行入队运算。这种情况称为【2 2】。答案：答案：上溢上溢 v由两个栈共享一个存储空间的好处是（由两个栈共享一个存储空间的好处是（ B B ） A) A) 减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 B

49、) B) 节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率 C) C) 减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 D) D) 节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率v下列关于栈的叙述中正确的是（下列关于栈的叙述中正确的是（ D D ）) )在栈中只能插入数据在栈中只能插入数据 B B）在栈中只能删除数据在栈中只能删除数据C C）栈是先进先出的线性表栈是先进先出的线性表 D D）栈是后进先出的线性表栈是后进先出的线性表v下列关于队列的叙述中正确的是（下列关于队列的叙述中正确的是（ C C ）在队列中只能插入数据）在队列中只能插入数

50、据 B B）在队列中只能删除数据在队列中只能删除数据C C）队列是先进先出的线性表队列是先进先出的线性表 D D）队列是后进先出的线性表队列是后进先出的线性表5757 顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。v 顺序存储结构的三个缺点： 1.作插入或删除操作时，需移动大量元数。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素元素1 158586 6、线性链表、线性链表v线性链表的基本概念：线性链表的基本概念： 线性表的链式存储结构称为线性链表。 为了适应线性表的链式存储

51、结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。算算算算法法法法与与与与数数数数据据据据结结结结构构构构59将存储空间中的每一个存储结点分为两部：v一部分称为数据域，用于存储数据元素的值；v另一部分称为指针域，用于存放下一个数据元素的存储序号（即存储结点的地址），也就是指向后件结点。线性链表中存储结点的结构如图2.20所示60601、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。2、逻辑上相邻的节点物理上不必相邻。3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。4、查找结点时链

52、式存储要比顺序存储慢。v 链式存储结构特点：链式存储结构特点：算算算算法法法法与与与与数数数数据据据据结结结结构构构构61 线性链表的物理结构线性链表的物理结构算算算算法法法法与与与与数数数数据据据据结结结结构构构构 线性链表的逻辑结构图线性链表的逻辑结构图HEAD：指向线性表中第一个结点的指针，称为头指针。当HEAD=NULL（或0）时称为空表。 对于线性链表，可以从头指针开始，沿着各个结点的指针扫描到链表中的所有结点。6263 为了弥补线性单链表的这个缺点，在某些应为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，用中，对线性链表中的每个结点设置两个指针，一个

53、称为一个称为左指针（左指针（LlinkLlink），），用以指向其前件结用以指向其前件结点；另一个称为点；另一个称为右指针（右指针（RlinkRlink），），用以指向其用以指向其后件的结点。后件的结点。 这样的线性链表称为这样的线性链表称为双向链表双向链表，其逻辑状，其逻辑状态如图态如图2.232.23所示。所示。63v 线性链表的基本运算：线性链表的基本运算：线性链表的运算主要有以下几个：线性链表的运算主要有以下几个： 在线性链表中包含指定元素的结点之前在线性链表中包含指定元素的结点之前 插入插入一个新元素。一个新元素。 在线性链表中在线性链表中删除删除包含指定元素的结点。包含指定元素的结

54、点。 将两个线性链表按要求将两个线性链表按要求合并合并成一个线性成一个线性 链表。链表。64 线性链表的线性链表的 插入插入 运算：运算： 线性链表的插入线性链表的插入是指在链式存储结是指在链式存储结构下构下的线性表中插入一个新元素。的线性表中插入一个新元素。 为了要在线性链表中插入一个新为了要在线性链表中插入一个新元素，元素，首先要给该元素分配一个新结点，然后将存首先要给该元素分配一个新结点，然后将存放新元素值的结点链接到线性链表中指定的放新元素值的结点链接到线性链表中指定的位置。位置。算算算算法法法法与与与与数数数数据据据据结结结结构构构构656666 线性链表的删除线性链表的删除指在链式

55、存储结构下的指在链式存储结构下的线性表中删除包含指定元素的结点。线性表中删除包含指定元素的结点。 为了在线性链表中删除包含指定元素的为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。然后将要删除结点放回到可利用栈。 线性链表的线性链表的 删除删除 运算：运算：算算算算法法法法与与与与数数数数据据据据结结结结构构构构676868 循环链表的结构与前面所讨论的线性链表相比，具有以下循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：两个特点： 循环链表的头指针指向表头结点。循环链表的头指针指向表头结

56、点。 在循环链表中，所有结点的指针构成了一个环状链。在循环链表中，所有结点的指针构成了一个环状链。 图图2.292.29是循环链表的示意图。是循环链表的示意图。v循环链表：循环链表：6969 在实际应用中，循环链表与线性单链表相比在实际应用中，循环链表与线性单链表相比主要有以下两个方面的优点：主要有以下两个方面的优点： 在循环链表中，只要指出表中任何一个结点在循环链表中，只要指出表中任何一个结点 的位置，就可以从它出发访问到表中其他所有的位置，就可以从它出发访问到表中其他所有的结点。的结点。 由于在循环链表中设置了一个表头结点，因由于在循环链表中设置了一个表头结点，因 此，在任何情况下，循环链

57、表中至少有一个结此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。点存在，从而使空表与非空表的运算统一。算算算算法法法法与与与与数数数数据据据据结结结结构构构构70v链表不具有的特点是（链表不具有的特点是（ B B ） A) A) 不必事先估计存储空间不必事先估计存储空间 B) B) 可随机访问任一元素可随机访问任一元素 C) C) 插入删除不需要移动元素插入删除不需要移动元素 D) D) 所需空间与线性表长度成正比所需空间与线性表长度成正比v数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1 1】 。 【答案【答案】存储

58、结构存储结构v线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是( ( B B ) ) A) A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构q 线性链表的例题讲解线性链表的例题讲解71717 7、树与二叉树：、树与二叉树：v 树的基本概念：树的基本

59、概念： 前面我们讨论的线性表，栈、队列和数组等都是线性结构。而树是一种非线性数据结构，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起，清晰地反映了数据元素之间的层次关系。 72算算算算法法法法与与与与数数数数据据据据结结结结构构构构现实世界中，能用树的结构表示的例子现实世界中，能用树的结构表示的例子：学学校校的的行行政政关关系系（P31）、书书的的层层次次结结构构（P32）、人人类类的的家家族血缘关系等。族血缘关系等。7374例：下图是一个有13个结点的树，其中A是根，其余结点为分三个互不相交的子集：T1B,E,F,K,LT2F

60、,GT3D,H,I,J,MT1、T2和T3都是根A的子树。7475树结构的基本术语：结点的度：结点所拥有子树的个数，图中A的度为3，C的度为1，F的度为0。叶子结点：树中度为0的结点，图中的K、L、F、G、M、I、J均称为叶子结点（或终端结点）。子结点与父结点：把每一个结点的一个或多个后件称为该点的子结点；反之，这个结点称为其子结点的父结点，同一个父结点的子结点之间互称为兄弟。树的度：树中各结点的度的最大值，度不为0的结点为非终端结点同，又叫分支结点。森林：N0或N=0棵互不相交的树的集合组成森林。图中将根结点A去掉，其中三棵子树就组成一个森林。树的深度：树中结点的最大层次称为树的深度或高度。

61、图中树的深度为4。75二叉树是一种很有用的非线性结构。二叉树具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。v 二叉树（二叉树（Binary TreeBinary Tree）：）： 因为树的每个结点的度不同，存储困难，使得对树的处理算法很复杂。所以引出二叉树的讨论。76767777性质性质1 1：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。例子例子1 1：某二叉树中度为2的结点有18个，则该二叉树中有 19 19 个叶子结点。二叉树的性质：二叉树的性质： 特别要注意：二叉树不是树的特殊情况。a aa

62、 ab bb b两棵不同的二叉树7878性性质质2 2：二叉树的第i层上至多有2 i-1（i 1）个结点二叉树的性质：二叉树的性质：423167891011121314155第一层(i=1)，有21-1=1个节点。第二层(i=2)，有22-1=2个节点。第三层(i=3)，有23-1=4个节点。第四层(i=4)，有24-1=8个节点。79二叉树的性质：二叉树的性质：性质性质3 3：深度为深度为h h的二叉树中至多含有的二叉树中至多含有2 2h h-1-1个结点个结点423167891011121314155此树的深度此树的深度h=4h=4，共有共有2 24 4-1=15-1=15个节点。个节点。

63、1+2+4+21+2+4+2m-1m-1=2=2m-1m-1( (等比数列前等比数列前M M项和项和) )80v满二叉树与完全二叉树满二叉树与完全二叉树满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。注意：满二叉树是完全二叉树，完全二叉树不一定是满二叉树。算算算算法法法法与与与与数数数数据据据据结结结结构构构构81v 满二叉树的特点：满二叉树的特点：每一层上都含有最大结点数。每一层上都含有最大结点数。8282v完全二叉树的特点：完全二叉树的特点：除最后一层外，每一层都取最大除最

64、后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置结点数，最后一层结点都集中在该层最左边的若干位置83838484 对于对于完全二叉树完全二叉树而言而言如果它的结点个数为如果它的结点个数为偶偶数，则该二叉树中：数，则该二叉树中：叶子结点的个数叶子结点的个数= =非叶子结点的个数非叶子结点的个数如果它的结点个数为如果它的结点个数为奇奇数，则该二叉树中：数，则该二叉树中：叶子结点的个数叶子结点的个数= =非叶子结点的个数非叶子结点的个数+1 +1 （即叶子结点数比非叶子结点数（即叶子结点数比非叶子结点数多一个多一个）规律总结：规律总结：算算算算法法法法与与与与数数数数据据据

65、据结结结结构构构构1234123452 2 叶子结点 3 32 2 非叶子结点 2 285v 例题讲解例题讲解1、设一棵完全二叉树共有700个结点，则在该二叉树中有 350 350 个叶子结点。2、在深度为5的满二叉树中，叶子结点的个数为（ C C ） A) 32 B) 31 C) 16 D) 15算算算算法法法法与与与与数数数数据据据据结结结结构构构构86v二叉树的遍历二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为三种：前序前序遍历、中序中序遍历、后序后序遍历。 设访问根结点记作设访问根结点记作V V；遍历根的左子树记作遍历根的左子树记作L L；遍历根的右子

66、树记作遍历根的右子树记作R R； 前序：前序： VLRVLR（即根左右）即根左右） 中序：中序： LVRLVR（即左根右）即左根右） 后序：后序： LRVLRV（即左右根）即左右根）8787884 10 8 9 5 2 6 7 3 1 例：结合下图所示的二叉树，写出该二叉树的前序、中序及后序遍历结果。后序遍历：中序遍历：前序遍历：1 2 4 5 8 10 9 3 6 74 2 10 8 5 9 1 6 3 7 881 1、设一棵二叉树的中序遍历结果为、设一棵二叉树的中序遍历结果为DBEAFC,DBEAFC,前序遍历结果为前序遍历结果为ABDECFABDECF，则后序遍历结果为：则后序遍历结果为

67、： DEBFCADEBFCA v 例题讲解例题讲解2 2、已知一棵二叉树前序遍历和中序遍历分别、已知一棵二叉树前序遍历和中序遍历分别为为ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，则该二叉树的后序遍则该二叉树的后序遍历为（历为（ B B ） A) GEDHFBCA A) GEDHFBCA B) DGEBHFCAB) DGEBHFCA C) ABCDEFGH D) ACBFEDHG C) ABCDEFGH D) ACBFEDHG89v具有具有3 3个结点的二叉树有（个结点的二叉树有（ D D ） A) 2A) 2种形态种形态 B) 4B) 4种形态种形态 C) 7C)

68、7种形态种形态 D) 5D) 5种形态种形态 v 设有下列二叉树：设有下列二叉树： 对此二叉树前序遍历的结果为（对此二叉树前序遍历的结果为（ B B ） A) ZBTTCPXA A) ZBTTCPXA B) ATBZXCTP B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT C) ZBTACTXP D) ATBZXCPT90908 8、查找和排序：、查找和排序：v查找查找又称为又称为检索检索 查找算法的评价主要考虑算法的时间复杂查找算法的评价主要考虑算法的时间复杂性，既可以采用数量级的形式表示，也可以性，既可以采用数量级的形式表示，也可以采用平均检索（查找）长度，即在查找

69、成功采用平均检索（查找）长度，即在查找成功情况下的平均比较次数来表示。情况下的平均比较次数来表示。 查找可分为查找可分为顺序查找顺序查找和和二分法查找二分法查找两种。两种。算算算算法法法法与与与与数数数数据据据据结结结结构构构构91（a a）顺序查找：顺序查找： 顺序查找顺序查找又称又称线性查找线性查找。它是一种最简单、。它是一种最简单、最基本的查找方法。基本思想是：从表中第一最基本的查找方法。基本思想是：从表中第一条记录开始，逐个进行记录的关键字和给定值条记录开始，逐个进行记录的关键字和给定值的比较。若某个记录的关键字和给定值相等，的比较。若某个记录的关键字和给定值相等，则查找成功；否则，若

70、直至最后一个记录，其则查找成功；否则，若直至最后一个记录，其关键字和给定值都不相等，则表明表中没有所关键字和给定值都不相等，则表明表中没有所查记录，查找不成功。查记录，查找不成功。算算算算法法法法与与与与数数数数据据据据结结结结构构构构92 二分查找二分查找又称又称折半查找折半查找。作为二分查找对。作为二分查找对象的表必须是顺序存储的有序表，即各记录象的表必须是顺序存储的有序表，即各记录的次序是按其关键字的大小顺序（以下假定的次序是按其关键字的大小顺序（以下假定按从小到大的顺序）排列的表。按从小到大的顺序）排列的表。（b b）二分查找：二分查找：算算算算法法法法与与与与数数数数据据据据结结结结

71、构构构构93 二分查找的二分查找的具体做法具体做法是是: : 先取表先取表中间中间位置的记录位置的记录关键字与给定值比较。若相等关键字与给定值比较。若相等, , 则查找成功；否则则查找成功；否则, , 若给定值比该记录的关键字小，则给定值必在表的前若给定值比该记录的关键字小，则给定值必在表的前半部分。在这前半部分中再取中间位置记录的关键字半部分。在这前半部分中再取中间位置记录的关键字进行比较，就又可以排除这部分的一半。依次反复进进行比较，就又可以排除这部分的一半。依次反复进行，直到找到给定值或找完全表而找不到为止。行，直到找到给定值或找完全表而找不到为止。 对于对于n n较大时，查找长度可以近

72、似地表示为较大时，查找长度可以近似地表示为算算算算法法法法与与与与数数数数据据据据结结结结构构构构94排序排序是将一组杂乱无章的数据按一定的规律顺是将一组杂乱无章的数据按一定的规律顺次排列起来。次排列起来。通常数据对象有多个属性域，即由多个数据成通常数据对象有多个属性域，即由多个数据成员组成员组成, , 其中有一个属性域可用来区分对象其中有一个属性域可用来区分对象, , 作为排序依据。该域称为作为排序依据。该域称为关键字（关键字（keykey）。排序的时间开销是衡量算法好坏的最重要的标排序的时间开销是衡量算法好坏的最重要的标志。对于长度为志。对于长度为n n的有序线性表，查找时最坏的有序线性表

73、，查找时最坏情况只需比较情况只需比较 n n 次。次。v 排序（排序（sortsort）95（a a）交换类排序：交换类排序：交换类排序法：交换类排序法：冒泡排序法冒泡排序法：需要比较的次数为：需要比较的次数为n(n-1)/2n(n-1)/2快速排序法快速排序法：是对冒泡排序的改进，是目：是对冒泡排序的改进，是目 前内部排序中速度最快的一种。前内部排序中速度最快的一种。算算算算法法法法与与与与数数数数据据据据结结结结构构构构96（b b）插入类排序：插入类排序： 插入类排序的插入类排序的基本方法基本方法是：每步将一个待是：每步将一个待排序的对象，按其关键字大小，插入到前面已排序的对象，按其关键

74、字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象经排好序的一组对象的适当位置上，直到对象全部插入为止全部插入为止。简单插入排序法：简单插入排序法：最坏情况需要最坏情况需要n(n-1)/2n(n-1)/2次比较；次比较；希尔排序法：希尔排序法：最坏情况需要最坏情况需要O O（n n1.5 1.5 ）次比较。次比较。算算算算法法法法与与与与数数数数据据据据结结结结构构构构97（c c）选择类排序：选择类排序：选择类排序的选择类排序的思想思想是：每一趟（例如，第是：每一趟（例如，第i i趟，趟，i=0i=0，1 1，n n2 2）在后面在后面n ni i个待排序对象中选个待排序对象中选出

75、关键字最小（升序，若为降序，选出最大关键出关键字最小（升序，若为降序，选出最大关键字）的对象，作为有序对象序列的第字）的对象，作为有序对象序列的第i i个对象。待个对象。待到第到第n n2 2趟作完，待排序对象只剩下趟作完，待排序对象只剩下1 1个，不用再个，不用再选了，结束排序。选了，结束排序。简单选择排序法简单选择排序法，最坏情况需要，最坏情况需要n(n-1)/2n(n-1)/2次比较；次比较；堆排序法堆排序法，最坏情况需要，最坏情况需要O O（nlognlog2 2 n n）次比较。次比较。98第二章 程序设计基础二级公共基础知识返回99内容1、程序设计方法与风格2、结构化程序设计3、面

76、向对象的程序设计方法，对象、方法、属性及继承与多态性。程程序序设设计计基基础础100程程序序设设计计基基础础（一）程序设计方法与风格（一）程序设计方法与风格 v 如何形成良好的程序设计风格：如何形成良好的程序设计风格： 1 1、源程序内部文档化；、源程序内部文档化； 选择标识符的名字选择标识符的名字 注释（注释（序言性序言性和和功能性功能性注释）注释） 程序的视觉组织程序的视觉组织一般位于模块的一般位于模块的首部，用于说明首部，用于说明模块的相关信息模块的相关信息位于源程序位于源程序模块内部模块内部风格：风格：清晰第一，效率第二。101 显式地说明一切变量显式地说明一切变量 数据说明的次序应该

77、规范化数据说明的次序应该规范化 便于查找变量（按顺序排列）便于查找变量（按顺序排列） 对复杂数据结构应注释说明对复杂数据结构应注释说明 2 2、数据说明、数据说明程程序序设设计计基基础础3 3、语句的结构、语句的结构 每条语句简单明了 限制GOTO语句的使用(尽量不用或少用) 尽量只采用3种基本控制结构编程1024 4、输入和输出、输入和输出 对所有输入数据进行校验和合理性检查对所有输入数据进行校验和合理性检查 输入输出格式保持一致输入输出格式保持一致 设计良好的输出报表设计良好的输出报表 输入方式输入方式应力求简单，尽量避免给用户带来不必要的麻烦；应力求简单，尽量避免给用户带来不必要的麻烦；

78、交互式输入数据时应有必要的提示信息交互式输入数据时应有必要的提示信息; ; 程序应对输入数据的程序应对输入数据的合法性进行检查合法性进行检查; ;若用户输入某些数据后可能产生严重后果若用户输入某些数据后可能产生严重后果, ,应应给用户输出必要的提示并要求用户确认；应根据系统的特点和给用户输出必要的提示并要求用户确认；应根据系统的特点和用户的习惯设计出令用户满意的输入方式。用户的习惯设计出令用户满意的输入方式。 输出数据的格式输出数据的格式应清晰，美观；输出数据时要加上必要的应清晰，美观；输出数据时要加上必要的提示信息。提示信息。103103主要思想：主要思想：对大型的程序设计，使用一些基本的结

79、构来设计程序，无论多复杂的程序，都可以使用这些基本结构按一定的顺序组合起来。这些基本结构的特点都是只有一个入口、一个出口。由这些基本结构组成的程序就避免了任意转移、阅读起来需要来回寻找的问题。程程序序设设计计基基础础（二）结构化程序设计（二）结构化程序设计 三种基本结构的特点三种基本结构的特点 只有一个入口 只有一个出口 基本结构中的每一部分都有机会执行到 结构内不存在“死循环”三种基本结构三种基本结构 顺序结构 选择结构 循环结构104程程序序设设计计基基础础设计原则设计原则 自顶向下 逐步求精 模块化 限制使用goto语句（二）结构化程序设计（二）结构化程序设计 结构化程序设计方法结构化程

80、序设计方法1、要求把程序的结构规定为顺序、选择和循环三种基本机构，并提出了自顶向下、逐步求精、模块化程序设计等原则。2、结构化程序设计是把模块分割方法作为对大型系统进行分析的手段，使其最终转化为三种基本结构，其目的是为了解决由许多人共同开发大型软件时，如何高效率地完成可靠系统的问题。3、程序的可读性好、可维护性好成为评价程序质量的首要条件。4、缺点：程序和数据结构松散地耦合在一起。解决此问题的方法就是采用面向对象的程序设计方法(OOP)。105（三）面向对象的程序设计方法（三）面向对象的程序设计方法 面向对象的程序设计（面向对象的程序设计（Object-Object-Oriented Orie

81、nted ProgrammingProgramming，OOPOOP）是一种把面向对象的是一种把面向对象的思想应用于软件开发过程中，指导开发活动思想应用于软件开发过程中，指导开发活动的系统方法，简称的系统方法，简称OOPOOP方法，它是建立在对方法，它是建立在对象概念（对象、类和继承）基础上的方法。象概念（对象、类和继承）基础上的方法。程程序序设设计计基基础础106v面向对象程序设计方法的优点面向对象程序设计方法的优点 1、与人类习惯的思维方法一致 2、稳定性好 3、可重用性好 4、易于开发大型软件产品 5、可维护性好程程序序设设计计基基础础107v基本概念基本概念对象(Object)l 对象

82、是基本的运行时认得实体，它既包括数据（属性），也包括作用于数据的操作（行为）。l 一个对象把属性和行为封装为一个整体。l 一个对象通常可由对象名、属性和操作3部分组成。 属性：通常是一些数据，有时它也可以是另一个对象。 事件：是由对象识别的一个动作，用户可以编写相应代码对此动作进行响应，如单击、双击、移动等。 方法：对象中的属性只能通过该对象所提供的操作来存取或修改。 面向对象面向对象(Object Oriented, OO)(Object Oriented, OO) 从该问题所涉及的对象入手来研究问题。108消息消息(Message)(Message) 对象之间进行通信的一种构造类（类（Cl

83、ass）：类是一组具有相同属性和相同操作的对象的集合。l 一个类定义了一组大体上相似的对象。l 一个类所包含的方法和数据描述一组对象的共同行为和属性。l 类是在对象之上的抽象，对象是类的具体化，是类的实例。基类基类：用来生成新类的类。派生类派生类：由已存在的类派生出来的新类，也叫子类。继承继承：是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。109 水上交通工具陆上交通工具水陆两用交通工具 多多 重重 继继 承承 图图 程程序序设设计计基基础础单继承单继承指一个类只允许有一个父类，指一个类只允许有一个父类，多重继承多重继承指一个类允许有指一个类允许有多个父类。多个

84、父类。110 程程序序设设计计基基础础封装封装(Encapsulation)(Encapsulation)l 将数据和操作数据的函数衔接在一起，构成一个具有类类型的对象的描述。l 对象的内部实现受保护，外界不能访问l 封装简化了程序员对对象的使用多态性多态性(Polymorphism)(Polymorphism)l 不同的对象收到同一消息可以产生完全不同的结构，这一现象叫做多态性l 多态的实现受到继承的支持111四、例题讲解：四、例题讲解：程程序序设设计计基基础础v 结构化程序设计的结构化程序设计的3 3种结构是（种结构是（ D D ） A) A) 顺序结构、选择结构、转移结构顺序结构、选择结

85、构、转移结构 B) B) 分支结构、等价结构、循环结构分支结构、等价结构、循环结构 C) C) 多分支结构、赋值结构、等价结构多分支结构、赋值结构、等价结构 D) D) 顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构v 在设计程序时，应采纳的原则之一是（在设计程序时，应采纳的原则之一是（ D D ） A) A) 不限制不限制gotogoto语句的使用语句的使用 B) B) 减少或取消注解行减少或取消注解行 C) C) 程序越短越好程序越短越好 D) D) 程序结构应有助于读者理解程序结构应有助于读者理解112v 程序设计语言的基本成分是数据成分、运算成分、控制成程序设计语言的基本成分

86、是数据成分、运算成分、控制成 分和（分和（ D D ） A) A) 对象成分对象成分 B) B) 变量成分变量成分 C) C) 语句成分语句成分D) D) 传输成分传输成分程程序序设设计计基基础础v 结构化程序设计主要强调的是（结构化程序设计主要强调的是（ D D ） A) A) 程序的规模程序的规模B) B) 程序的效率程序的效率 C) C) 程序设计语言的先进性程序设计语言的先进性 D) D) 程序易读性程序易读性v 以下不属于对象的基本特点的是（以下不属于对象的基本特点的是（ C C ） A) A) 分类性分类性 B) B) 多态性多态性 C) C) 继承性继承性 D) D) 封装性封装

87、性113v 对建立良好的程序设计风格，下面描述正确的是（对建立良好的程序设计风格，下面描述正确的是（ A A ） A) A) 程序应简单、清晰、可读性好程序应简单、清晰、可读性好 B) B) 符号名的命名只要符合语法符号名的命名只要符合语法 C) C) 充分考虑程序的执行效率充分考虑程序的执行效率 D) D) 程序的注释可有可无程序的注释可有可无v 在结构化程序设计思想提出之前，在程序设计中曾强调程序在结构化程序设计思想提出之前，在程序设计中曾强调程序 的效率，现在，与程序的效率相比，人们更重视程序的（的效率，现在，与程序的效率相比，人们更重视程序的（C C） A) A) 安全性安全性 B)

88、B) 一致性一致性 C) C) 可理解性可理解性D) D) 合理性合理性程程序序设设计计基基础础114v 下列叙述中，不属于结构化程序设计方法的主要原则的是下列叙述中，不属于结构化程序设计方法的主要原则的是（B B） A) A) 自顶向下自顶向下 B) B) 由底向上由底向上 C) C) 模块化模块化D) D) 限制使用限制使用gotogoto语句语句v 对象实现了数据和操作的结合，是指对数据和数据的操作进对象实现了数据和操作的结合，是指对数据和数据的操作进行（行（ C C ） A) A) 结合结合 B) B) 隐藏隐藏 C) C) 封装封装 D) D) 抽象抽象v 在面向对象方法中，一个对象

89、请求另一个对象为其服务的方在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（式是通过发送（ D D ）A A）调用语句调用语句 B B）命令命令 C C）口令口令 D D）消息消息程程序序设设计计基基础础115v 信息屏蔽的概念与下述哪一种概念直接相关（信息屏蔽的概念与下述哪一种概念直接相关（ B B ）A A）软件结构定义软件结构定义 B B）模块独立性模块独立性C C）模块类型划分模块类型划分 D D）模块耦合度模块耦合度v 下列对对象概念描述错误的是（下列对对象概念描述错误的是（ A A ）A A）任何对象都必须有继承性任何对象都必须有继承性B B）对象是属性和方法的封装

90、体对象是属性和方法的封装体C C）对象间的通讯靠消息传递对象间的通讯靠消息传递D D）操作是对象的动态属性操作是对象的动态属性程程序序设设计计基基础础116v面向对象的设计方法与传统的面向过程的方法有本质的不同面向对象的设计方法与传统的面向过程的方法有本质的不同, ,它的基本原理是（它的基本原理是（ C C ） A) A) 模拟现实世界中不同事物之间的联系模拟现实世界中不同事物之间的联系 B) B) 强调模拟现实世界中的算法而不强调概念强调模拟现实世界中的算法而不强调概念 C) C) 使用现实世界的概念抽象地思考问题从而自然地解决问题使用现实世界的概念抽象地思考问题从而自然地解决问题 D) D

91、) 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考 v在面向对象的程序设计中，类描述的是具有相似性质的一组在面向对象的程序设计中，类描述的是具有相似性质的一组 【1 1】。【答案【答案】对象对象 v在面向对象方法中，类之间共享属性和操作的机制称为在面向对象方法中，类之间共享属性和操作的机制称为 【2 2】。【答案【答案】继承继承 v一个类可以从直接或间接的祖先中继承所有属性和方法。采一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的用这个方法提高了软件的 【3 3】。【答案【答案】可重用性可重用性 117

92、v在面向对象的模型中，最基本的概念是对象和在面向对象的模型中，最基本的概念是对象和【4 4】。 【答案】：【答案】：类类 v在面向对象的设计中，用来请求对象执行某一处理或回答某在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为些信息的要求称为【5 5】。 【答案】：【答案】：消息消息v在程序设计阶段应该采取在程序设计阶段应该采取 【6 6】 和逐步求精的方法，把一和逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，进而用个模块的功能逐步分解，细化为一系列具体的步骤，进而用某种程序设计语言写成程序。某种程序设计语言写成程序。 【答案】【答案】 ：自顶向下自顶向下

93、程程序序设设计计基基础础118v【7 7】是是一一种种信信息息隐隐蔽蔽技技术术，目目的的在在于于将将对对象象的的使使用用者者和和对对象的设计者分开。象的设计者分开。【答案】【答案】：封装封装v可以把具有相同属性的一些不同对象归类，称为可以把具有相同属性的一些不同对象归类，称为 【8 8】 。 【答案】【答案】：对象类对象类v子子程程序序通通常常分分为为两两类类：【9 9】和和函函数数，前前者者是是命命令令的的抽抽象象，后者是为了求值。后者是为了求值。 【答案】【答案】：过程过程v源源程程序序文文档档化化要要求求程程序序应应加加注注释释。注注释释一一般般分分为为序序言言性性注注释释和和【1010

94、】。 【答案】【答案】：功能性注释功能性注释v在在面面向向对对象象方方法法中中，信信息息屏屏蔽蔽是是通通过过对对象象的的【1111】 性性来来实实现的。现的。 【答案】【答案】 ：封装封装v类类是是一一个个支支持持集集成成的的抽抽象象数数据据类类型型，而而对对象象是是类类的的【1212】 。 【答案】【答案】：实例实例v 在在面面向向对对象象方方法法中中，类类之之间间共共享享属属性性和和操操作作的的机机制制称称为为【1313】。 【答案】【答案】：继承继承119第三章 软件工程基础二二级公共基公共基础知知识返回120软软件件工工程程基基础础内容内容1、软件工程基本概念，软件生命周期概念，软件工

95、具与软件开发环境。2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。3、结构化设计方法，总体设计与详细设计。4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5、程序的调试，静态调试与动态调试。121软软件件工工程程基基础础（一）基本概念（一）基本概念 v 软件工程：软件工程：软件工程软件工程是指应用计算机科学、数学及管理是指应用计算机科学、数学及管理 科学等原理，以工程化的原则和方法来解决软件问题的科学等原理，以工程化的原则和方法来解决软件问题的 工程。其目的是提高软件生产率、提高软件质量、降低工程。其目的是提高软件生产率、提高软件

96、质量、降低 软件成本。软件成本。v 软件危机：软件危机：是指在计算机软件开发和维护过程中所遇到的是指在计算机软件开发和维护过程中所遇到的一系列严重的问题。一系列严重的问题。主要表现在：成本、质量、生产率等问题。主要表现在：成本、质量、生产率等问题。122v软件生命周期软件生命周期将软件产品从提出、实现、使用维护到停止使用退役的过将软件产品从提出、实现、使用维护到停止使用退役的过程称为程称为软件生命周期。软件生命周期。分为分为软件定义软件定义、软件开发软件开发及及软件运行维护软件运行维护3 3个时期个时期。维护维护是是持续时间最长，花费代价最大的一个时期，软件工程学的持续时间最长，花费代价最大的

97、一个时期，软件工程学的一个目的就是一个目的就是提高软件的可维护性，降低维护代价提高软件的可维护性，降低维护代价。6 6个活动阶段：个活动阶段：q可行性研究与计划制定可行性研究与计划制定：确定系统的总体目标。参加人：确定系统的总体目标。参加人员有用户、项目负责人和系统分析员，产生文档有可行员有用户、项目负责人和系统分析员，产生文档有可行性分析报告、项目计划书等。性分析报告、项目计划书等。q需求分析需求分析：确定系统的逻辑模型。参加人员有用户、项：确定系统的逻辑模型。参加人员有用户、项目负责人和系统分析员。产生文档为需求规格说明书，目负责人和系统分析员。产生文档为需求规格说明书，其作用其作用：（：

98、（1 1）便于用户、开发人员进行理解交流；）便于用户、开发人员进行理解交流；（2 2）反映用户问题的结构，可以作为软件开发工作的）反映用户问题的结构，可以作为软件开发工作的基础和依据；（基础和依据；（3 3）作为确认测试和验收的依据。）作为确认测试和验收的依据。123q软件设计软件设计：包括软件结构设计、数据设计、接口设计和过程：包括软件结构设计、数据设计、接口设计和过程设计。其中设计。其中结构设计结构设计是定义软件系统各部件之间的关系；是定义软件系统各部件之间的关系；数数据设计据设计是将分析时创建的模型转化为数据结构的定义；是将分析时创建的模型转化为数据结构的定义；接口接口设计设计是描述软件

99、内部、软件和操作系统之间及软件与人之间是描述软件内部、软件和操作系统之间及软件与人之间如何通信；如何通信；过程设计过程设计则是把系统结构部件转换成软件的过程则是把系统结构部件转换成软件的过程性描述。软件设计分性描述。软件设计分概要设计概要设计和和详细设计详细设计。参加人员有系统。参加人员有系统分析员和高级程序员。产生的文档有设计规格说明书。分析员和高级程序员。产生的文档有设计规格说明书。q编码编码：编程。高级程序员和程序员产生源程序清单。：编程。高级程序员和程序员产生源程序清单。q测试测试：由另一部门的高级程序员或系统分析员产生软件测试：由另一部门的高级程序员或系统分析员产生软件测试计划和软件

100、测试报告。计划和软件测试报告。q运行维护运行维护124v 软件工程三要素软件工程三要素 方法方法：完成软件工程项目的技术手段。：完成软件工程项目的技术手段。 工具工具：支持软件的开发、管理、文档生成。：支持软件的开发、管理、文档生成。 过程过程：支持软件开发的各个环节的控制、管理。：支持软件开发的各个环节的控制、管理。v 软件工程的理论和技术研究的内容软件工程的理论和技术研究的内容软件开发技术软件开发技术和和软件工程管理软件工程管理。v 软件工程的目标软件工程的目标在给定的成本、进度的前提下，开发出具有有效性、可靠在给定的成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可适应

101、性、可移植性、可追踪性、可理解性、可维护性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。性和可互操作性且满足用户需求的产品。软件工程鼓励研制和采用各种先进的软件开发方法、工具软件工程鼓励研制和采用各种先进的软件开发方法、工具和环境。和环境。125v软件工具和软件开发环境软件工具和软件开发环境软件工具软件工具( (CASE)CASE)：用来辅助软件开发、运行、维护、管理、支持等过程中的活动的软件。软件开发环境软件开发环境：支持软件产品开发的软件系统，它由软件工具集和环境集成机制构成。软软件件工工程程基基础础126（二）结构化分析方法（二）结构化分析方法 软软件件工工程程基基础础

102、v基本思想基本思想将系统分析看成工程项目，有计划、有步骤地进行工作。将系统分析看成工程项目，有计划、有步骤地进行工作。v开发策略开发策略自顶向下，逐层分解自顶向下，逐层分解v分析结果分析结果一套分层的数据流图一套分层的数据流图( (DFD)DFD)：用来描述数据流从输入到输出用来描述数据流从输入到输出的变换流程的变换流程一个数据字典一个数据字典( (DD)DD)：用来描述用来描述DFDDFD中的每个数据流、文件以中的每个数据流、文件以及组成数据流或文件的数据项及组成数据流或文件的数据项一组小说明（加工逻辑说明）：用来描述每个基本加工的一组小说明（加工逻辑说明）：用来描述每个基本加工的加工逻辑加

103、工逻辑127（三（三）结构化设计方法、总体设计和详细设计结构化设计方法、总体设计和详细设计 软软件件工工程程基基础础v结构化设计方法结构化设计方法 结构图：结构图：q 基本成分基本成分：模块、调用、输入输出数据：模块、调用、输入输出数据q 模块用矩形表示，模块间用线段连接，表示调用关系，模块用矩形表示，模块间用线段连接，表示调用关系， 输入输出数据可写在调用线段的旁边输入输出数据可写在调用线段的旁边 数据流的类型数据流的类型q 变换流变换流q 事务流事务流128v 概要设计概要设计 设计原则设计原则q 分解分解协调原则协调原则q 自顶向下的原则自顶向下的原则q 信息屏蔽、抽象的原则信息屏蔽、抽

104、象的原则q 一致性原则一致性原则q 明确性原则明确性原则q 模块间的耦合度尽可能小，模块内部组合尽可能紧模块间的耦合度尽可能小，模块内部组合尽可能紧凑（内聚性高）凑（内聚性高）q 模块的扇入和扇出系数合理模块的扇入和扇出系数合理q 模块的规模适当模块的规模适当129v 详细设计详细设计 根本目标：根本目标： 确定应用怎样具体的实现所要求的系统，不是具体的确定应用怎样具体的实现所要求的系统，不是具体的编写程序，而是要设计程序的编写程序，而是要设计程序的“蓝图蓝图” 自顶向下的原则。自顶向下的原则。此阶段的结果基本上决定了最终的程序代码的质量。此阶段的结果基本上决定了最终的程序代码的质量。包括内容

105、：包括内容：q 代码设计代码设计q 输入设计输入设计q 输出设计输出设计q 处理过程设计处理过程设计q 用户界面设计用户界面设计q 安全控制设计安全控制设计130（四（四）软件测试软件测试 软软件件工工程程基基础础v 意义目的意义目的为了发现错误；为了发现错误；希望能以最少人力和时间发现潜在各种错误和缺陷；希望能以最少人力和时间发现潜在各种错误和缺陷；保证系统质量和可靠性的关键步骤。保证系统质量和可靠性的关键步骤。v 测试方法测试方法 人工测试人工测试 机器测试机器测试提问：提问：测试能否发测试能否发现程序中的所有错现程序中的所有错误？误？答案：答案：不能。不能。131v 白盒测试白盒测试结构

106、测试结构测试将软件看成透明的白盒，根据程序的内部结构和逻辑结构来将软件看成透明的白盒，根据程序的内部结构和逻辑结构来设计测试例子，对程序的路径和过程进行测试，检查是否满设计测试例子，对程序的路径和过程进行测试，检查是否满足设计的要求足设计的要求v 黑盒测试黑盒测试功能测试功能测试将软件看成黑盒子，在完全不考虑软件内部结构和特性的情将软件看成黑盒子，在完全不考虑软件内部结构和特性的情况下，测试软件的外部特性况下，测试软件的外部特性v 软件测试的实施软件测试的实施单元测试（模块测试）：白盒测试法单元测试（模块测试）：白盒测试法组装测试（集成测试）组装测试（集成测试）确认测试：检查软件产品是否符合需

107、求定义，黑盒测试法确认测试：检查软件产品是否符合需求定义，黑盒测试法系统测试系统测试132v 适合于适合于黑盒测试黑盒测试的测试方案：的测试方案： 主要有：主要有：等价类划分、边界值分析法、错误推测法、因果等价类划分、边界值分析法、错误推测法、因果图四种。图四种。v 适合于适合于白盒测试白盒测试的测试方案：的测试方案： 主要有主要有逻辑覆盖测试、基本路径测试逻辑覆盖测试、基本路径测试法。法。 逻辑覆盖法包括：逻辑覆盖法包括： 语句覆盖、判定覆盖（也称为分支覆盖）、条件覆盖、判语句覆盖、判定覆盖（也称为分支覆盖）、条件覆盖、判定定/ /条件覆盖、条件组合覆盖。条件覆盖、条件组合覆盖。软软件件工工

108、程程基基础础133（五（五）程序调试程序调试 软软件件工工程程基基础础v 任务任务根据测试时发现的错误，找出原因和具体位置，进行改正根据测试时发现的错误，找出原因和具体位置，进行改正由程序开发人员来进行，谁开发的程序就由谁来进行调试由程序开发人员来进行，谁开发的程序就由谁来进行调试方法：方法：q 强行排错法强行排错法q 回溯法回溯法q 原因排除法原因排除法（演绎、归纳、二分法（演绎、归纳、二分法) )程序调试程序调试是根据错误的迹象确定程序中的错误的确切性质、原因和位置，对程序进行修改，排除这个错误。134v 静态调试静态调试通过人的思维来分析源程序代码和排错，是主要的调试手段。v 动态调试动

109、态调试辅助静态调试。软软件件工工程程基基础础135例题讲解例题讲解v为了提高测试的效率，应该（为了提高测试的效率，应该（ D D ） A) A) 随机选取测试数据随机选取测试数据 B) B) 取一切可能的输入数据作为测试数据取一切可能的输入数据作为测试数据 C) C) 在完成编码以后制定软件的测试计划在完成编码以后制定软件的测试计划 D) D) 选择发现错误可能性大的数据作为测试数据选择发现错误可能性大的数据作为测试数据v软件生命周期中所花费用最多的阶段是（软件生命周期中所花费用最多的阶段是（ D D ） A) A) 详细设计详细设计 B) B) 软件编码软件编码 C) C) 软件测试软件测试

110、 D) D) 软件维护软件维护软软件件工工程程基基础础136v 下列叙述中，不属于软件需求规格说明书的作用的是下列叙述中，不属于软件需求规格说明书的作用的是( ( D D ) ) A) A) 便于用户、开发人员进行理解和交流便于用户、开发人员进行理解和交流 B) B) 反映出用户问题的结构，可以作为软件开发工作的基反映出用户问题的结构，可以作为软件开发工作的基 础和依据础和依据 C) C) 作为确认测试和验收的依据作为确认测试和验收的依据 D) D) 便于开发人员进行需求分析便于开发人员进行需求分析v 下列不属于软件工程的下列不属于软件工程的3 3个要素的是（个要素的是（ D D ） ) )

111、工具工具 ) ) 过程过程 ) ) 方法方法 ) ) 环境环境v 软件设计包括软件的结构、数据接口和过程设计，其中软软件设计包括软件的结构、数据接口和过程设计，其中软 件的过程设计是指（件的过程设计是指（ B B ） A) A) 模块间的关系模块间的关系 B) B) 系统结构部件转换成软件的过程描述系统结构部件转换成软件的过程描述 C) C) 软件层次结构软件层次结构D) D) 软件开发过程软件开发过程137v 检查软件产品是否符合需求定义的过程称为检查软件产品是否符合需求定义的过程称为( ( ) ) ) ) 确认测试确认测试 ) ) 集成测试集成测试 ) ) 系统测试系统测试 ) ) 单元测

112、试单元测试v 数据流图用于抽象描述一个软件的逻辑模型，数据流图由数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列不属于数据流图合法图符一些特定的图符构成。下列不属于数据流图合法图符 的是的是( ( ) ) ) ) 控制流控制流 ) ) 加工加工 ) ) 存储文件存储文件 ) ) 源和潭源和潭v 开发软件所需高成本和产品的低质量之间有着尖锐矛盾的开发软件所需高成本和产品的低质量之间有着尖锐矛盾的这种现象称作这种现象称作( ( B B ) ) A) A) 软件投机软件投机 B) B) 软件危机软件危机 C) C) 软件工程软件工程 D) D) 软件产生软件产生138v 下

113、面不属于软件设计原则的是下面不属于软件设计原则的是( ( ) ) ) ) 抽象抽象 ) ) 模块化模块化 ) ) 自底向上自底向上 ) ) 信息隐蔽信息隐蔽v 开发大型软件时，产生困难的根本原因是开发大型软件时，产生困难的根本原因是( ( A A ) ) A A）大系统的复杂性大系统的复杂性 B B）人员知识不足人员知识不足 C C）客观世界千变万化客观世界千变万化 D D）时间紧、任务重时间紧、任务重v 软件工程的出现是由于（软件工程的出现是由于（） A) A) 程序设计方法学的影响程序设计方法学的影响 B) B) 软件产业化的需要软件产业化的需要 C) C) 软件危机的出现软件危机的出现

114、D) D) 计算机的发展计算机的发展139v在数据流图在数据流图( (DFD) DFD) 中，带有名字的箭头表示中，带有名字的箭头表示( ( D D ) ) A) A) 模块之间的调用关系模块之间的调用关系 B) B) 程序的组成成分程序的组成成分 C) C) 控制程序的执行顺序控制程序的执行顺序 D) D) 数据的流向数据的流向v 下列不属于结构化设计的常用工具的是（下列不属于结构化设计的常用工具的是（ D D ） A) A) 数据流图数据流图 B) B) 数据字典数据字典 C) C) 判定树判定树 D) PADD) PAD图图v 在软件生产过程中，需求信息的给出是（在软件生产过程中，需求信

115、息的给出是（ D D ） A) A) 程序员程序员 B) B) 项目管理者项目管理者 C) C) 软件分析设计人员软件分析设计人员 D) D) 软件用户软件用户140v模块独立性是软件模块化所提出的要求，衡量模块独立性模块独立性是软件模块化所提出的要求，衡量模块独立性 的度量标准则是模块的（的度量标准则是模块的（ C C ） A) A) 抽象和信息隐蔽抽象和信息隐蔽 B) B) 局部化和封装化局部化和封装化 C) C) 内聚性和耦合性内聚性和耦合性 D) D) 激活机制和控制方法激活机制和控制方法v 软件开发的结构化生命周期方法将软件生命周期划分成（软件开发的结构化生命周期方法将软件生命周期划

116、分成（A A） A) A) 定义阶段、开发定义阶段、开发阶段阶段、运行维护、运行维护 B) B) 设计阶段、编程阶段、测试阶段设计阶段、编程阶段、测试阶段 C) C) 总体设计、详细设计、编程调试总体设计、详细设计、编程调试 D) D) 需求分析、功能定义、系统设计需求分析、功能定义、系统设计141 下列工具是需求分析常用工具的是（下列工具是需求分析常用工具的是（ D D ） ) ) PADPAD ) ) PFD PFD ) ) N-SN-S) ) DFDDFDv 在软件工程中，白箱测试法可用于测试程序的内部结构。在软件工程中，白箱测试法可用于测试程序的内部结构。 此方法将程序看做是（此方法将

117、程序看做是（ A A ） A) A) 路径的集合路径的集合 B) B) 循环的集合循环的集合 C) C) 目标的集合目标的集合 D) D) 地址的集合地址的集合v 完全不考虑程序的内部结构和内部特征，而只是根据程序完全不考虑程序的内部结构和内部特征，而只是根据程序 功能导出测试用例的测试方法是（功能导出测试用例的测试方法是（ A A ） A) A) 黑箱测试法黑箱测试法 B) B) 白箱测试法白箱测试法 C) C) 错误推测法错误推测法 D) D) 安装测试法安装测试法142v 下列选项中，模块间耦合度最低的是（下列选项中，模块间耦合度最低的是（ C C ） A) A) 数据耦合数据耦合 B)

118、 B) 同构耦合同构耦合 C) C) 非直接耦合非直接耦合 D) D) 内容耦合内容耦合v软件工程过程通常包含软件工程过程通常包含4 4种基本活动，其中软件开发是（种基本活动，其中软件开发是（ A A ） A) DA) DB) PB) P C) C C) C D) AD) Av 下列不属于软件调试技术的是（下列不属于软件调试技术的是（ B B ） A) A) 强行排错法强行排错法 B) B) 集成测试法集成测试法 C) C) 回溯法回溯法 D) D) 原因排除法原因排除法P(Plan)-P(Plan)-软件规格说明软件规格说明D(Do)-D(Do)-软件开发软件开发C(Check)-C(Che

119、ck)-软件确认软件确认A(Action)-A(Action)-软件演进软件演进143v为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为（代替传统的程序流程图，通常也把这种图称为（ B B ） A) PADA) PAD图图 B) N-SB) N-S图图 C) C) 结构图结构图 D) D) 数据流图数据流图v 软件复杂性度量的参数包括（软件复杂性度量的参数包括（ B B ） A) A) 效率效率 B) B) 规模规模 C) C) 完整性完整性 D) D) 容错性容错性v下列叙述中，正确的是（

120、下列叙述中，正确的是（ D D ） A) A) 软件就是程序清单软件就是程序清单 B) B) 软件就是存放在计算机中的文件软件就是存放在计算机中的文件 C) C) 软件应包括程序清单及运行结果软件应包括程序清单及运行结果 D) D) 软件包括程序、数据和文档软件包括程序、数据和文档v 软件设计中，有利于提高模块独立性的一个准则是（软件设计中，有利于提高模块独立性的一个准则是（ C C ） A) A) 低内聚低耦合低内聚低耦合 B) B) 低内聚高耦合低内聚高耦合 C) C) 高内聚低耦合高内聚低耦合 D) D) 高内聚高耦合高内聚高耦合144v下列的方法中，不属于结构化分析方法的是（下列的方法

121、中，不属于结构化分析方法的是（ D D ） A) A) 面向数据流的结构化分析方法面向数据流的结构化分析方法 B) B) 面向数据结构的面向数据结构的JacksonJackson方法方法 C) C) 面向数据结构的结构化数据系统开发方法面向数据结构的结构化数据系统开发方法 D) D) 面向对象的分析方法面向对象的分析方法v 详细设计的结果基本决定了最终程序的（详细设计的结果基本决定了最终程序的（ C C ） A) A) 代码的规模代码的规模 B) B) 运行速度运行速度 C) C) 质量质量 D) D) 可维护性可维护性v下列不属于静态测试方法的是（下列不属于静态测试方法的是（ B B ） A

122、) A) 代码检查代码检查 B) B) 白盒法白盒法 C) C) 静态结构分析静态结构分析 D) D) 代码质量度量代码质量度量v在软件生命周期中，能准确地确定软件系统必须做什么和必在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是（须具备哪些功能的阶段是（ D D ） A A）概要设计概要设计 B B）详细设计详细设计 C C）可行性分析可行性分析 D D）需求分析需求分析145v程序流程图（程序流程图（PFDPFD）中的箭头代表的是（中的箭头代表的是（ B B ）A A）数据流数据流 B B）控制流控制流 C C）调用关系调用关系 D D）组成关系组成关系v在结构化

123、方法中，软件功能分解属于下列软件开发在结构化方法中，软件功能分解属于下列软件开发中的阶段是（中的阶段是（ C C ）A A）详细设计详细设计 B B）需求分析需求分析C C）概要设计概要设计 D D）编程调试编程调试v 软件调试的目的是（软件调试的目的是（ B B ） A A）发现错误发现错误 B B）改正错误改正错误 C C）改善软件的性能改善软件的性能 D D）挖掘软件的潜能挖掘软件的潜能146v软件需求分析阶段的工作，可以分为四个方面：需求获取，软件需求分析阶段的工作，可以分为四个方面：需求获取， 需求分析，编写需求规格说明书，以及（需求分析，编写需求规格说明书，以及（ B B ） A

124、A）阶段性报告阶段性报告 B B）需求评审需求评审 C C）总结总结 D D）都不正确都不正确v 通常，将软件产品从提出、实现、使用维护到停止使用退通常，将软件产品从提出、实现、使用维护到停止使用退 役的过程称为役的过程称为【1 1】。【答案】【答案】：软件生命周期软件生命周期v 耦合和内聚是评价模块独立性的两个主要标准，其中耦合和内聚是评价模块独立性的两个主要标准，其中 【2 2】 反映了模块内各成分之间的联系。反映了模块内各成分之间的联系。【答案】【答案】：内聚内聚v 软件工程研究的内容主要包括：软件工程研究的内容主要包括：【3 3】技术和软件工程管理。技术和软件工程管理。 【答案】【答案

125、】：软件开发软件开发147v Jackson Jackson结构化分析方法是英国的结构化分析方法是英国的M.JacksonM.Jackson提出的，它是提出的，它是一种面向一种面向【4 4】的分析方法。的分析方法。 【答案】【答案】：数据结构数据结构v数据流的类型有数据流的类型有【6 6】和事务型。和事务型。【答案】【答案】：变换型变换型v 软件危机出现于软件危机出现于6060年代末，为了解决软件危机，人们提出年代末，为了解决软件危机，人们提出 了了【7 7】的原理来设计软件，这就是软件工程诞生的基的原理来设计软件，这就是软件工程诞生的基 础。础。 【答案】【答案】：工程学工程学v 软件开发环

126、境是全面支持软件开发全过程的软件开发环境是全面支持软件开发全过程的【8 8】集合。集合。 【答案】【答案】：软件工具软件工具软软件件工工程程基基础础148v 测试的目的是暴露错误，评价程序的可靠性；而测试的目的是暴露错误，评价程序的可靠性；而【9 9】的的 目的是发现错误的位置并改正错误。目的是发现错误的位置并改正错误。【答案】【答案】：软件调试软件调试v 软件维护活动包括以下几类：改正性维护、适应性维护、软件维护活动包括以下几类：改正性维护、适应性维护、 【1010】维护和预防性维护。维护和预防性维护。 【答案】【答案】：完善性完善性v 软件结构是以软件结构是以【1111】为基础而组成的一种

127、控制层次结构。为基础而组成的一种控制层次结构。 【答案】【答案】：模块模块v 为了便于对照检查，测试用例应由输入数据和预期的为了便于对照检查，测试用例应由输入数据和预期的 【1212】 两部分组成。两部分组成。【答案】【答案】：输出结果输出结果v 软件工程包括软件工程包括3 3个要素，分别为方法、工具和个要素，分别为方法、工具和【1313】。 【答案】【答案】：过程过程 v 软件工程的出现是由于软件工程的出现是由于【1414】的出现提出的。的出现提出的。【答案】【答案】：软软件危机件危机149v 单元测试又称模块测试，一般采用单元测试又称模块测试，一般采用 【1515】 测试。测试。 【答案】

128、【答案】：白盒动态白盒动态v 软件的软件的【1616】设计又称为总体结构设计，其主要设计又称为总体结构设计，其主要 任务是建立软件系统的总体结构。任务是建立软件系统的总体结构。【答案】【答案】：概要概要v 软件是程序、数据和软件是程序、数据和【1717】的集合。的集合。【答案】【答案】：文档文档v 对软件是否能达到用户所期望的要求的测试称为对软件是否能达到用户所期望的要求的测试称为 【1818】 。【答案】【答案】：确认测试确认测试( (或验收测试或验收测试) )v 质量保证策略大致分为三个阶段：以检测为重、质量保证策略大致分为三个阶段：以检测为重、 【1919】和以新产品开发为重。和以新产品

129、开发为重。 【答案】【答案】：以过程管理为重以过程管理为重150第四章 数据库设计基础二二级公共基公共基础知知识返回151数数据据库库设设计计基基础础内容内容1、数据库的基本概念：数据库，数据库管理系统，数据库系统。2、数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3、关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4、数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。152数数据据库库设设计计基基础础（一（一）基本概念基本概念 v数据数据( (Data)Data)实际上就是描述事物的符号记录实际上就是描述事物的符号记录软件中的数据一定

130、是有结构的软件中的数据一定是有结构的v数据库数据库( (DBDB：Database)Database)长期存储在计算机内，有组织的，可共享的数据集合。长期存储在计算机内，有组织的，可共享的数据集合。数据库中的数据按一定的数学模型组织、描述和存储，数据库中的数据按一定的数学模型组织、描述和存储，具有较小的冗余度，较高的数据独立性和易扩展性，并具有较小的冗余度，较高的数据独立性和易扩展性，并可为各种用户共享。可为各种用户共享。153v数据库管理系统数据库管理系统( (DBMS)-Database Management SystemDBMS)-Database Management System数据

131、库系统的核心软件；数据库系统的核心软件；要在操作系统支持下工作；要在操作系统支持下工作；解决如何科学地组织和存储数据，如何高效的获取和维护解决如何科学地组织和存储数据，如何高效的获取和维护数据的系统软件。数据的系统软件。主要功能包括：主要功能包括：q数据模式定义；数据模式定义；q数据存取的物理构建；数据存取的物理构建；q数据操纵；数据操纵；q数据的完整性、安全性定义与检查；数据的完整性、安全性定义与检查；q数据库的并发控制与故障恢复；数据库的并发控制与故障恢复；q数据的服务。数据的服务。154为完成上述功能，为完成上述功能，DBMSDBMS一般提供相应的数据语言：一般提供相应的数据语言：q数据

132、定义语言（数据定义语言（DDLDDL）:Data Definition Language:Data Definition Languageq数据操纵语言（数据操纵语言（DMLDML）:Data Manipulation Language:Data Manipulation Languageq数据控制语言（数据控制语言（DCLDCL）:Data Control Language:Data Control Language数据语言按其使用方式具有两种结构形式数据语言按其使用方式具有两种结构形式q交互式命令语言交互式命令语言q宿主型语言宿主型语言v数据库管理员数据库管理员主要工作包括：主要工作包括：

133、q数据库设计数据库设计q数据库维护数据库维护q改善系统性能，提高系统效率改善系统性能，提高系统效率 DDLDDLDDLDDL：负责数据的模式定义与数据的负责数据的模式定义与数据的物理存取构建。物理存取构建。 DMLDMLDMLDML：负责数据的操纵，包括查询及负责数据的操纵，包括查询及增加、删、改变等操作。增加、删、改变等操作。 DCLDCLDCLDCL：负责数据完整性、安全性的定负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。义与检查以及并发控制、故障恢复等。155v数据库系统（数据库系统（DBSDBS）由数据库（数据）、数据库管理系统（软件）、数据由数据库（数据）、数据库管理系

134、统（软件）、数据库管理员（人员）、系统平台之硬件平台（硬件）和库管理员（人员）、系统平台之硬件平台（硬件）和软件平台（软件）构成。软件平台（软件）构成。v数据库应用系统（数据库应用系统（DBASDBAS）利用数据库系统进行应用开发利用数据库系统进行应用开发v数据库管理技术的发展数据库管理技术的发展人工管理阶段人工管理阶段文件系统阶段文件系统阶段数据库系统接数据库系统接 结论结论： 数据库、数据库系数据库、数据库系统和数据库管理系统的统和数据库管理系统的关系是：数据库系统包关系是：数据库系统包括数据库和数据库管理括数据库和数据库管理系统。系统。 数据库管理系统是数据库管理系统是数据库系统的核心。

135、数据库系统的核心。156157数数据据库库设设计计基基础础 在数据库管理技术的发展过程中，经历了在数据库管理技术的发展过程中，经历了人工人工管理管理阶段、阶段、文件系统文件系统阶段和阶段和数据库系统数据库系统阶段。其中阶段。其中数据独立性最高数据独立性最高的阶段是的阶段是数据库系统数据库系统。文件系统与。文件系统与数据库系统的数据库系统的主要区别主要区别是是数据库系统数据库系统具有具有特定的数特定的数据模型据模型。相对于数据库系统，文件系统的。相对于数据库系统，文件系统的主要缺陷主要缺陷有：有：数据关联差数据关联差、数据不一致性数据不一致性和和冗余性冗余性。158v 数据库系统的基本特点：数据

136、库系统的基本特点： 数据的集成性数据的集成性q采用统一的数据结构方式采用统一的数据结构方式q按照多个应用的需要组主全局的统一的数据结构按照多个应用的需要组主全局的统一的数据结构q数据模式是多个应用共同的、全局的数据结构数据模式是多个应用共同的、全局的数据结构 数据的高共享性与低冗余性数据的高共享性与低冗余性 数据独立性（数据独立性（数据与程序间的互不依赖性数据与程序间的互不依赖性）q 物理物理独立性和独立性和逻辑逻辑独立性独立性 数据统一管理与控制数据统一管理与控制q 数据的完整性检查数据的完整性检查q 数据的安全性检查数据的安全性检查q 并发控制并发控制159v内部结构体系内部结构体系三级模

137、式三级模式 即即（1 1）概念概念模式（模式（2 2）外外模式（模式（3 3）内内模式模式u内模式内模式又称为物理模式，数据库物理存储结构与物理存取方法，对又称为物理模式，数据库物理存储结构与物理存取方法，对一般用户是透明的，直接影响数据库的性能，一个数据库只有一个内一般用户是透明的，直接影响数据库的性能，一个数据库只有一个内模式。处于最底层，它反映了数据在计算机物理结构。模式。处于最底层，它反映了数据在计算机物理结构。u概念模式概念模式数据库中全体数据逻辑结构和特征的描述，是所有用户的数据库中全体数据逻辑结构和特征的描述，是所有用户的公共数据视图。公共数据视图。处于中层，它反映了设计者的数据

138、全局逻辑要求。处于中层，它反映了设计者的数据全局逻辑要求。一一个数据库只有一个概念模式。个数据库只有一个概念模式。u外模式外模式也称子模式或用户模式，数据库用户能够看见和使用的局部也称子模式或用户模式，数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是用户的数据视图，一个数据库可以数据的逻辑结构和特征的描述，是用户的数据视图，一个数据库可以有多个外模式。处于最外层，它反映了用户对数据的要求。有多个外模式。处于最外层，它反映了用户对数据的要求。160数据库系统的二级映射数据库系统的二级映射u概念模式概念模式/ /内模式的映射内模式的映射p 存在于概念级和内部级存在于概念级和内部级之间之

139、间p 实现了概念模式到内模实现了概念模式到内模式之间的相互转换式之间的相互转换p 保证数据具有很高的物保证数据具有很高的物理独立性理独立性u外模式外模式/ /概念模式的映射概念模式的映射p 存在于外部级和概念级存在于外部级和概念级之间之间p 实现了外模式到概念模实现了外模式到概念模式之间的相互转换式之间的相互转换p 保证数据具有较高的逻保证数据具有较高的逻辑独立性辑独立性161（二（二）数据模型数据模型 数据库设计的核心v 数据模型的基本概念数据模型的基本概念 数据模型是数据模型是对现实世界中数据的模拟和抽象。对现实世界中数据的模拟和抽象。 数据模型的组成要素数据模型的组成要素q 数据结构：数

140、据结构：所研究的对象类型的集合；所研究的对象类型的集合；q 数据操作：数据操作：对数据库的各种对象允许执行操作的集合；对数据库的各种对象允许执行操作的集合；q 数据的约束条件：数据的约束条件：一组完整性规则的集合。一组完整性规则的集合。 数据模型按不同的应用层次分成三种类型数据模型按不同的应用层次分成三种类型q 概念数据模型（概念模型）：数据模型的基础概念数据模型（概念模型）：数据模型的基础q 逻辑数据模型（数据模型）：面向数据库系统的模型逻辑数据模型（数据模型）：面向数据库系统的模型q 物理数据模型（物理模型）：物理数据模型（物理模型）：数据的存储结构数据的存储结构 162v E-RE-R模

141、型（实体联系模型）模型（实体联系模型） 基本概念基本概念 （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） 三个基本概念之间的联接关系三个基本概念之间的联接关系q 实体集与属性间的联接关系实体集与属性间的联接关系q 实体与联系实体与联系163E-RE-R模型的图示法模型的图示法q 实体集实体集表示法（表示法（矩形矩形）q 联系联系表示法（表示法（菱形菱形）q 属性属性表示法（表示法（椭圆

142、形椭圆形）q 实体集与属性间实体集与属性间的联接关系（的联接关系（直线直线）q 实体集与联系间实体集与联系间的联接关系（的联接关系（直线直线）E-RE-R图的一个实例图的一个实例: :学生课程联系学生课程联系的概念模型的概念模型164v 层次模型层次模型一种树形结构；一种树形结构；数据结构比较简单，操作简单；数据结构比较简单，操作简单；对于实体间联系是固定的、且预先定义好的应用系统，有对于实体间联系是固定的、且预先定义好的应用系统，有较高的性能；较高的性能；可以提供良好的完整性支持；可以提供良好的完整性支持；不适合表示非层次性的联系，对于插入和删除操作的限制不适合表示非层次性的联系，对于插入和

143、删除操作的限制比较多。比较多。v 网状模型网状模型 一个不加任何条件限制的列向图；一个不加任何条件限制的列向图； 优于层次模型；优于层次模型； 使用时设计系统内部的物理因素较多，用户操作不方便，使用时设计系统内部的物理因素较多，用户操作不方便，其数据模式与系统实现不甚理想。其数据模式与系统实现不甚理想。165v 关系模型（关系模型（具有坚实的理论基础具有坚实的理论基础） 采用二维表来表示，简称采用二维表来表示，简称表，表，每一个二维表称为一个每一个二维表称为一个关系关系。 二维表（或关系）的性质二维表（或关系）的性质：元素个数有限性、元组的惟一性、元素个数有限性、元组的惟一性、元组的次序无关性

144、、元组分量的原子性、属性名惟一性、属性的次序无元组的次序无关性、元组分量的原子性、属性名惟一性、属性的次序无关性、分量值域的同一性。关性、分量值域的同一性。 关系操纵关系操纵：数据查询、插入、删除和修改。数据查询、插入、删除和修改。 关系中的数据约束关系中的数据约束p 实体完整性实体完整性约束：约束：主键中属性值不能为空值主键中属性值不能为空值。p 参照完整性参照完整性约束：约束：实体及实体间的联系。实体及实体间的联系。p 用户定义的完整性用户定义的完整性约束：约束：具体应用要求来定义的约束条件。具体应用要求来定义的约束条件。数数据据库库设设计计基基础础166（三（三）关系代数关系代数v 关系

145、模型的基本操作关系模型的基本操作 插入、删除、修改、查询v 关系模型的基本运算关系模型的基本运算 插入、删除、修改、查询 查询运算q 投影运算：在关系中选择某些属性列，即消去某些列。q 选择运算：在关系中选择满足某些条件的元组，即消去某些行。q笛卡儿积运算（连接运算）分解成六种基本操作1、关系的属性指定2、关系的元组的选择3、两个关系的合并4、关系的查询5、关系元组的插入6、关系元组的删除当一个查询需要来自两个或多个关系的数据时要用连接操作。连接是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。（等值连接、自然连接）关系代数中的扩充运算关系代数中的扩充运算 交运算、除运算、连接与自然连接运

146、算167（四（四）数据库设计与管理数据库设计与管理v 数据库设计概述数据库设计概述 设计一个能满足用户要求，性能良好的数据库；设计一个能满足用户要求，性能良好的数据库； 基本任务基本任务：根据用户对象的信息需求、处理需求和数：根据用户对象的信息需求、处理需求和数 据库的支持环境设计出数据模式；据库的支持环境设计出数据模式； 两种方法两种方法：q 以信息需求为主，兼顾处理需求（面向以信息需求为主，兼顾处理需求（面向数据数据的方法）的方法）q 以处理需求为主，兼顾信息需求（面向以处理需求为主，兼顾信息需求（面向过程过程的方法）的方法）q 面向数据的设计方法已成为主流方法。面向数据的设计方法已成为主

147、流方法。数数据据库库设设计计基基础础168 数据库设计目前一般采用生命周期法，分若干阶段：数据库设计目前一般采用生命周期法，分若干阶段：q 需求分析阶段需求分析阶段q 概念设计阶段概念设计阶段q 逻辑设计阶段逻辑设计阶段q 物理设计阶段物理设计阶段q 编码阶段编码阶段q 测试阶段测试阶段q 运行阶段运行阶段q 进一步修改阶段进一步修改阶段 在数据库设计中采用前四个阶段，并且重点以数据结构与模在数据库设计中采用前四个阶段，并且重点以数据结构与模型的设计为主线。型的设计为主线。169v 数据库设计的需求分析数据库设计的需求分析任务任务：通过详细调查现实世界要处理的对象，充分了解原：通过详细调查现实

148、世界要处理的对象，充分了解原系统的工作概况，明确用户的各种需求，然后在此基础上系统的工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能；确定新系统的功能；调查的重点调查的重点是是“数据数据”和和“处理处理”；常采用常采用结构化结构化分析方法和分析方法和面向对象面向对象的方法；的方法；对数据库设计来讲，对数据库设计来讲，数据字典数据字典是进行详细的数据收集和数是进行详细的数据收集和数据分析所获得的主要结果；据分析所获得的主要结果；数据字典是在需求分析阶段建立，在数据库设计过程中不数据字典是在需求分析阶段建立，在数据库设计过程中不断修改、充实、完善的。断修改、充实、完善的。170v数据库

149、概念设计数据库概念设计概述概述q 目的目的：分析数据间内在语义关联，在此基础上建立：分析数据间内在语义关联，在此基础上建立 一个数据的抽象模型一个数据的抽象模型q 设计方法设计方法：集中式模式设计法和视图集成设计法：集中式模式设计法和视图集成设计法设计的过程设计的过程 q 选择局部应用选择局部应用q 视图设计视图设计：3 3种设计次序（自顶向下、由底向上、由种设计次序（自顶向下、由底向上、由 内向外）内向外）q 视图集成视图集成171v 数据库的逻辑设计数据库的逻辑设计 从从E-RE-R图向关系模式的转换图向关系模式的转换 逻辑模式规范化及调整、实现逻辑模式规范化及调整、实现 关系视图设计关系

150、视图设计v 数据库的物理设计数据库的物理设计 物理设计的内容：索引设计、集簇设计、分区设计。物理设计的内容：索引设计、集簇设计、分区设计。 对数据库内部物理结构作调整并选择合理的存取路径，对数据库内部物理结构作调整并选择合理的存取路径， 以提高数据库访问速度及有效利用存储空间以提高数据库访问速度及有效利用存储空间 留给用户参与物理设计的余地不多留给用户参与物理设计的余地不多数数据据库库设设计计基基础础172v 数据库管理数据库管理 数据库的建立（数据模式的建立、数据加载） 数据库的调整 数据库的重组 数据库安全性控制与完整性控制 数据库的故障恢复 数据库监控数数据据库库设设计计基基础础173（

151、五（五）例题讲解例题讲解v数据库管理系统数据库管理系统DBMSDBMS中用来定义模式、内模式和外模式的中用来定义模式、内模式和外模式的语言为（语言为（ C C ） A) C A) C B) Basic B) Basic C) DDLC) DDL D) DML D) DMLv下列有关数据库的描述，正确的是（下列有关数据库的描述，正确的是（ C C ） A) A) 数据库是一个数据库是一个DBFDBF文件文件 B) B) 数据库是一个关系数据库是一个关系 C) C) 数据库是一个结构化的数据集合数据库是一个结构化的数据集合 D) D) 数据库是一组文件数据库是一组文件数数据据库库设设计计基基础础1

152、74v 下列有关数据库的描述，正确的是（下列有关数据库的描述，正确的是（ D D ） A) A) 数据处理是将信息转化为数据的过程数据处理是将信息转化为数据的过程 B) B) 数据的物理独立性是指当数据的逻辑结构改变时，数数据的物理独立性是指当数据的逻辑结构改变时，数 据的存储结构不变据的存储结构不变 C) C) 关系中的每一列称为元组，一个元组就是一个字段关系中的每一列称为元组，一个元组就是一个字段 D) D) 如果一个关系中的属性或属性组并非该关系的关键字，如果一个关系中的属性或属性组并非该关系的关键字， 但它是另一个关系的关键字，则称其为本关系的外关但它是另一个关系的关键字，则称其为本关

153、系的外关 键字键字v 应用数据库的主要目的是（应用数据库的主要目的是（ C C ） A) A) 解决数据保密问题解决数据保密问题B) B) 解决数据完整性问题解决数据完整性问题 C) C) 解决数据共享问题解决数据共享问题D) D) 解决数据量大的问题解决数据量大的问题175v 在数据库设计中，将在数据库设计中，将E-RE-R图转换成关系数据模型的过程属图转换成关系数据模型的过程属 于（于（ B B ） A) A) 需求分析阶段需求分析阶段B) B) 逻辑设计阶段逻辑设计阶段 C) C) 概念设计阶段概念设计阶段 D) D) 物理设计阶段物理设计阶段v 在数据管理技术的发展过程中，经历了人工管

154、理阶段、文在数据管理技术的发展过程中，经历了人工管理阶段、文 件系统阶段和数据库系统三大阶段。其中数据独立性最高件系统阶段和数据库系统三大阶段。其中数据独立性最高 的阶段是（的阶段是（） ) ) 数据库系统数据库系统 ) ) 文件系统文件系统 ) ) 人工管理人工管理 ) ) 数据项管理数据项管理数数据据库库设设计计基基础础176v索引属于（索引属于（ B B ） A) A) 模式模式 B) B) 内模式内模式 C) C) 外模式外模式 D) D) 概念模式概念模式v下述关于数据库系统的叙述中正确的是（下述关于数据库系统的叙述中正确的是（） ) ) 数据库系统减少了数据冗余数据库系统减少了数据

155、冗余 ) ) 数据库系统避免了一切冗余数据库系统避免了一切冗余 ) ) 数据库系统中数据的一致性是指数据类型一致数据库系统中数据的一致性是指数据类型一致 ) ) 数据库系统比文件系统能管理更多的数据数据库系统比文件系统能管理更多的数据v数据库系统的核心是（数据库系统的核心是（ B B ） A) A) 数据库数据库 B) B) 数据库管理系统数据库管理系统 C) C) 模拟模型模拟模型 D) D) 软件工程软件工程177v下列下列SQLSQL语句中，用于修改表结构的是语句中，用于修改表结构的是( ( A A ) ) A) ALTERA) ALTER B) CREATE C) UPDATE D)

156、INSERT B) CREATE C) UPDATE D) INSERTv数据库、数据库系统和数据库管理系统之间的关系是数据库、数据库系统和数据库管理系统之间的关系是( ( B B ) ) A) A) 数据库包括数据库系统和数据库管理系统数据库包括数据库系统和数据库管理系统 B) B) 数据库系统包括数据库和数据库管理系统数据库系统包括数据库和数据库管理系统 C) C) 数据库管理系统包括数据库和数据库系统数据库管理系统包括数据库和数据库系统 D) 3D) 3者没有明显的包含关系者没有明显的包含关系v关系模型允许定义关系模型允许定义3 3类数据约束，下列不属于数据约束的类数据约束，下列不属于数

157、据约束的是是( ( C C ) ) A) A) 实体完整性约束实体完整性约束 B) B) 参照完整性约束参照完整性约束 C) C) 域完整性约束域完整性约束 D) D) 用户定义的完整性约束用户定义的完整性约束178v分布式数据库系统不具有的特点是分布式数据库系统不具有的特点是( ( D D ) ) A) A) 数据分布性和逻辑整体性数据分布性和逻辑整体性 B) B) 位置透明性和复制透明性位置透明性和复制透明性 C) C) 分布性分布性 D) D) 数据冗余数据冗余v关系表中的每一行称为一个关系表中的每一行称为一个( ( ) ) ) ) 元组元组 ) ) 字段字段 ) ) 属性属性 ) )

158、码码v下列数据模型中，具有坚实理论基础的是下列数据模型中，具有坚实理论基础的是( ( C C ) ) A) A) 层次模型层次模型 B) B) 网状模型网状模型 C) C) 关系模型关系模型 D) D) 以上以上3 3个都是个都是179v NULLNULL是指是指( ( C C ) ) A) 0A) 0B) B) 空格空格 C) C) 未知的值或无任何值未知的值或无任何值 D) D) 空字符串空字符串v数据库的故障恢复一般是由数据库的故障恢复一般是由( ( C C ) ) A) A) 数据流图完成的数据流图完成的B) B) 数据字典完成的数据字典完成的 C) DBAC) DBA完成的完成的 D

159、) PADD) PAD图完成的图完成的v下列说法中，不属于数据模型所描述的内容的是下列说法中，不属于数据模型所描述的内容的是( ( C C ) ) A) A) 数据结构数据结构B) B) 数据操作数据操作 C) C) 数据查询数据查询D) D) 数据的约束条件数据的约束条件数数据据库库设设计计基基础础180v 一个关系中属性个数为一个关系中属性个数为1 1时，称此关系为时，称此关系为( ( C C ) ) A) A) 对应关系对应关系 B) B) 单一关系单一关系 C) C) 一元关系一元关系 D) D) 二元关系二元关系v 为用户与数据库系统提供接口的语言是为用户与数据库系统提供接口的语言是

160、( ( C C ) ) A) A) 高级语言高级语言B) B) 数据描述语言数据描述语言( (DDL) DDL) C) C) 数据操纵语言数据操纵语言( (DML)DML) D) D) 汇编语言汇编语言v 相对于数据库系统，文件系统的主要缺陷有数据关联差、相对于数据库系统，文件系统的主要缺陷有数据关联差、 据不一致性和据不一致性和( ( D D ) ) A) A) 可重用性差可重用性差B) B) 安全性差安全性差 C) C) 非持久性非持久性 D) D) 冗余性冗余性 181v下列关系模型中，能使经运算后得到的新关系中属性个数多下列关系模型中，能使经运算后得到的新关系中属性个数多于原来关系中属

161、性个数的是于原来关系中属性个数的是( ( B B ) ) A) A) 选择选择 B) B) 连接连接 C) C) 投影投影 D) D) 并并v下列叙述中，正确的是下列叙述中，正确的是( ( A A ) ) A) A) 用用E-RE-R图能够表示实体集间一对一的联系、一对多的联图能够表示实体集间一对一的联系、一对多的联 系和多对多的联系系和多对多的联系 B) B) 用用E-RE-R图只能表示实体集之间一对一的联系图只能表示实体集之间一对一的联系 C) C) 用用E-RE-R图只能表示实体集之间一对多的联系图只能表示实体集之间一对多的联系 D) D) 用用E-RE-R图表示的概念数据模型只能转换为

162、关系数据模型图表示的概念数据模型只能转换为关系数据模型v“年龄在年龄在18-2518-25之间之间”这种约束是属于数据库当中的这种约束是属于数据库当中的( ( C C ) ) A) A) 原子性措施原子性措施B) B) 一致性措施一致性措施 C) C) 完整性措施完整性措施 D) D) 安全性措施安全性措施182v下列叙述中，不属于数据库系统的是下列叙述中，不属于数据库系统的是( ( D D ) ) A) A) 数据库数据库B) B) 数据库管理系统数据库管理系统 C) C) 数据库管理员数据库管理员D) D) 数据库应用系统数据库应用系统v视图设计一般有视图设计一般有3 3种设计次序，下列不

163、属于视图设计的是种设计次序，下列不属于视图设计的是( ( B B ) ) A) A) 自顶向下自顶向下B) B) 由外向内由外向内 C) C) 由内向外由内向外D) D) 自底向上自底向上v用树形结构来表示实体之间联系的模型称为用树形结构来表示实体之间联系的模型称为( ( B B ) )A A）关系模型关系模型 B B）层次模型层次模型C C）网状模型网状模型 D D）数数据据库库设设计计基基础础183v下列下列4 4项中说法不正确的是项中说法不正确的是( ( C C ) ) A) A) 数据库减少了数据冗余数据库减少了数据冗余 B) B) 数据库中的数据可以共享数据库中的数据可以共享 C)

164、C) 数据库避免了一切数据的重复数据库避免了一切数据的重复 D) D) 数据库具有较高的数据独立性数据库具有较高的数据独立性v下列下列4 4项中，必须进行查询优化的是项中，必须进行查询优化的是( ( A A ) ) A) A) 关系数据库关系数据库B) B) 网状数据库网状数据库 C) C) 层次数据库层次数据库D) D) 非关系模型非关系模型v最常用的一种基本数据模型是关系数据模型，它的表示应采最常用的一种基本数据模型是关系数据模型，它的表示应采用用( ( D D ) ) A) A) 树树 B) B) 网络网络 C) C) 图图 D) D) 二维表二维表184v公司中有多个部门和多名职员，每

165、个职员只能属于一个部门，公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，从职员到部门的联系类型是一个部门可以有多名职员，从职员到部门的联系类型是( ( C C ) ) A) A) 多对多多对多 B) B) 一对一一对一 C) C) 多对一多对一 D) D) 一对多一对多 v下列关系运算的叙述中，正确的是下列关系运算的叙述中，正确的是( ( C C ) ) A) A) 投影、选择、连接是从二维表行的方向进行的运算投影、选择、连接是从二维表行的方向进行的运算 B) B) 并、交、差是从二维表的列的方向来进行运算并、交、差是从二维表的列的方向来进行运算 C) C) 投影

166、、选择、连接是从二维表列的方向进行的运算投影、选择、连接是从二维表列的方向进行的运算 D) D) 以上以上3 3种说法都不对种说法都不对v关系数据库管理系统应能实现的专门的关系运算包括关系数据库管理系统应能实现的专门的关系运算包括( ( B B ) ) A) A) 排序、索引、统计排序、索引、统计 B) B) 选择、投影、连接选择、投影、连接 C) C) 关联、更新、排序关联、更新、排序 D) D) 显示、打印、制表显示、打印、制表185v 在关系数据库中，用来表示实体之间联系的是在关系数据库中，用来表示实体之间联系的是( ( D D ) )A)A)树结构树结构B)B)网结构网结构C)C)线性

167、表线性表D)D)二维表二维表v 将将- -R R图转换到关系模式时，实体与联系都可以表示图转换到关系模式时，实体与联系都可以表示 成成( ( B B ) )A)A)属性属性 B)B)关系关系 C)C)键键 D)D)域域v 数据库管理系统常见的数据模型有层次模型、网状模型数据库管理系统常见的数据模型有层次模型、网状模型 和和 【1 1】 种。种。 【答案【答案】关系模型关系模型v 一个项目具有一个项目主管，一个项目主管可管理多个一个项目具有一个项目主管，一个项目主管可管理多个 项目，则实体项目，则实体“项目主管项目主管”与实体与实体“项目项目”的联系属于的联系属于 【2 2】 的联系。的联系。

168、【答案【答案】一对多一对多v按条件按条件f f对关系进行选择，其关系运算表示式是对关系进行选择，其关系运算表示式是( ( C C ) )A)R|A)R|R B)R|R B)R|R |R C)C)f f(R)(R) D) D)f f(R) (R) f f 186v 数据库设计分为以下数据库设计分为以下6 6个设计阶段：需求分析阶段、个设计阶段：需求分析阶段、 【3 3】 、 逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。v关系操作的特点是关系操作的特点是 【4 4】 操作。操作。 【答案【答案】集合集合v数据模型按不同应用层次分成数据

169、模型按不同应用层次分成3 3种类型，它们是概念数据模型、种类型，它们是概念数据模型、 【5 5】 和物理数据模型。和物理数据模型。【答案【答案】逻辑数据模型逻辑数据模型v当数据的物理结构当数据的物理结构( (存储结构、存取方式等存储结构、存取方式等) )改变时，不影响数据改变时，不影响数据库的逻辑结构，从而不致引起应用程序的变化库的逻辑结构，从而不致引起应用程序的变化, , 这是指数据的这是指数据的【6 6】。 【答案【答案】物理独立性物理独立性v 【7 7】是数据库设计的核心。是数据库设计的核心。 【答案【答案】数据模型数据模型v 在关系模型中，把数据看成一个二维表，每一个二维表称为一在关系

170、模型中，把数据看成一个二维表，每一个二维表称为一个个 【8 8】 。 【答案【答案】关系关系【答案【答案】概念设计阶段概念设计阶段187v 关系数据库的关系演算语言是以关系数据库的关系演算语言是以 【9 9】 为基础的为基础的DMLDML语言。语言。 【答案【答案】数理逻辑中的谓词演算数理逻辑中的谓词演算v 关键字关键字ASCASC和和DESCDESC分别表示分别表示【1010】的含义。的含义。升序和降序升序和降序v数据库系统阶段的数据具有较高独立性，数据独立性包括物数据库系统阶段的数据具有较高独立性，数据独立性包括物理独立性和理独立性和【1111】两个含义。两个含义。 【答案【答案】逻辑独立

171、性逻辑独立性v数据库保护分为：安全性控制数据库保护分为：安全性控制 、 【1212】 、并发性控制和数、并发性控制和数据的恢复。据的恢复。 【答案【答案】完整性控制完整性控制v 【1313】是从二维表列的方向进行的运算。是从二维表列的方向进行的运算。【答案【答案】关系运算关系运算v由关系数据库系统支持的完整性约束是指由关系数据库系统支持的完整性约束是指 【1414】 和参照完和参照完整性。整性。 【答案【答案】实体完整性实体完整性v数据库恢复是将数据库从数据库恢复是将数据库从 【1515】 状态恢复到某一已知的正状态恢复到某一已知的正确状态。确状态。 【答案【答案】错误错误188v 实体之间的

172、联系可以归结为一对一联系、一对多实体之间的联系可以归结为一对一联系、一对多( (或多对或多对 多多) )的联系与多对多联系。如果一个学校有许多教师，而的联系与多对多联系。如果一个学校有许多教师，而 一个教师只归属于一个学校，则实体集学校与实体集教师一个教师只归属于一个学校，则实体集学校与实体集教师 之间的联系属于之间的联系属于 【1616】 的联系。的联系。【答案】【答案】一对多一对多v 数据库系统中实现各种数据管理功能的核心软件称为数据库系统中实现各种数据管理功能的核心软件称为 【1717】。 【答案】【答案】数据库管理系统数据库管理系统v 关系模型的完整性规则是对关系的某种约束条件，包括实关系模型的完整性规则是对关系的某种约束条件，包括实 体完整性、体完整性、 【1818】和自定义完整性。和自定义完整性。 【答案】【答案】参照完整性参照完整性数数据据库库设设计计基基础础189