计算机等级考试计算机等级考试公共基础知识公共基础知识2021/3/101讲解：XX计算机二级考试公共基础知识计算机二级考试公共基础知识大纲大纲q数据结构与算法数据结构与算法q程序设计基础程序设计基础q软件工程基础软件工程基础q数据库设计基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。2021/3/102讲解：XX计算机二级考试公共基础知识试卷分析计算机二级考试公共基础知识试卷分析章节章节考试时间考试时间数据结构数据结构与算法与算法程序设计程序设计基础基础软件工程软件工程基础基础数据库设计数据库设计基础基础2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分2009年9月10分2分8分10分2010年3月10分0分10分10分2021/3/103讲解：XX算法算法算法的基算法的基本概念本概念2.2.算法复杂算法复杂度的概念和度的概念和意义意义一、基本数据结构与算法一、基本数据结构与算法数据结构数据结构数据结构的概念数据结构的概念线性表线性表栈和队列栈和队列树与二叉树树与二叉树查找技术查找技术排序技术排序技术对于等级考试，这个部分的考核对于等级考试，这个部分的考核重点主要重点主要在在算法和数据结构的基本概算法和数据结构的基本概念念、二叉树二叉树(遍历、结点），遍历、结点），还有还有排序和查找排序和查找考试中也经常会涉及到。考试中也经常会涉及到。2021/3/104讲解：XX算法的定义算法的定义u对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是程序设计的核心算法是程序设计的核心算法的基本概念算法的基本概念 算法是在有限步骤内求解某一问题所使用的一组定义明确的算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机规则。通俗点说，就是计算机解题的过程解题的过程( (计算的方法计算的方法) )。在。在这个过程中，无论是形成解题思路这个过程中，无论是形成解题思路( (推理实现的算法推理实现的算法) )还是编还是编写程序写程序( (操作实现的算法操作实现的算法) )，都是在实施某种算法。，都是在实施某种算法。例：例：n个数从大到小进行排序。个数从大到小进行排序。有多种排序方法有多种排序方法，常用的有冒泡排序、选择排序等。，常用的有冒泡排序、选择排序等。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。讲课讲课说课说课2021/3/105讲解：XX2.算法的基本特征算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：n有穷性有穷性n确定性确定性n输入输入n输出输出n可行性可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成拥有足够的情报拥有足够的情报2021/3/106讲解：XXu算法与计算机程序算法与计算机程序算法算法_是一组逻辑步骤是一组逻辑步骤程序程序用计算机语言描述的算法用计算机语言描述的算法3.3.算法的表示算法的表示算法的表示算法的表示INPUTrS=3.14*r*rPTINTS开始开始输入输入R RS=3.14*R*R输出输出S S结束结束问题：输入园的半径，计算园的面积一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法传统的算法-图形法，如图形法，如“流程图流程图”和和N-S图图目前常用的方法目前常用的方法-使用伪码描述算法。使用伪码描述算法。2021/3/107讲解：XX冒泡排序的方法：冒泡排序的方法：1.1.扫描整个线性表，逐次对相扫描整个线性表，逐次对相邻的两个元素进行比较，若为邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的逆序，则交换；第一趟扫描的结果使最大的元素排到表的最结果使最大的元素排到表的最后后 ；2.2.除最后一个元素，对剩余的除最后一个元素，对剩余的元素重复上述过程，将次大的元素重复上述过程，将次大的数排到表的倒数第二个位置；数排到表的倒数第二个位置；3.3.重复上述过程；重复上述过程；对于长度为对于长度为n n的线性表，冒泡排的线性表，冒泡排序需要对表扫描序需要对表扫描n-1n-1遍。遍。 算法举例：算法举例：n个数排序个数排序2021/3/108讲解：XX4.算法的两个基本要素：算法的两个基本要素：基本运算和操作基本运算和操作基本运算和操作基本运算和操作n算术运算算术运算n关系运算关系运算n逻辑运算逻辑运算n数据传输数据传输控制结构控制结构控制结构控制结构 n顺序顺序n选择选择n循环循环u一是对数据对象的运算和操作；u二是算法的控制结构。u算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法2021/3/109讲解：XX5. 算法的复杂度算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：n时间复杂度：执行这个算法所需要的时间复杂度：执行这个算法所需要的计算工作量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n空间复杂度：执行这个算法所需要的空间复杂度：执行这个算法所需要的内存空间内存空间算法在算法在执执行行过过程中程中临时临时占用的存占用的存储储空空间间时间复杂度时间复杂度它大致等于计算机它大致等于计算机执行一种简单操作所需的平均时间执行一种简单操作所需的平均时间与算法中与算法中进行进行简单操作的次数的乘积简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用存储算法本身所占用的存储空间的存储空间、算法中的输入输出数据所占用的存储空间算法中的输入输出数据所占用的存储空间和和算法在运行过程中算法在运行过程中临时占用的存储空间临时占用的存储空间这三个部分这三个部分2021/3/1010讲解：XX(1)在在计计算机中，算法是指算机中，算法是指_。A.查询查询方法方法B.加工方法加工方法C.解解题题方案的准确而完整的描述方案的准确而完整的描述D.排序方法排序方法(2)下列叙述中正确的是下列叙述中正确的是（07年年4月月）A)算法的效率只与算法的效率只与问题问题的的规规模有关，而与数据的存模有关，而与数据的存储结储结构无关构无关B)算法的算法的时间时间复复杂杂度是指度是指执执行算法所需要的行算法所需要的计计算工作量算工作量C)数据的数据的逻辑结逻辑结构与存构与存储结储结构是一一构是一一对应对应的的D)算法的算法的时间时间复复杂杂度与空度与空间间复复杂杂度一定相关度一定相关(3)算法的有算法的有穷穷性是指性是指(08年年4月月)A）算法程序的运行）算法程序的运行时间时间是有限的是有限的B）算法程序所）算法程序所处处理的数据量是有限的理的数据量是有限的C）算法程序的）算法程序的长长度是有限的度是有限的D）算法只能被有限的用）算法只能被有限的用户户使用使用(c)(B)算法习题:(A)2021/3/1011讲解：XX(4)算法的算法的时问时问复复杂杂度是指度是指(2010年年3月月)A)算法的算法的执执行行时间时间B)算法所算法所处处理的数据量理的数据量C)算法程序中的算法程序中的语语句或指令条数句或指令条数D)算法在算法在执执行行过过程中所需要的基本运算次数程中所需要的基本运算次数(5)算法的空算法的空间间复复杂杂度是指度是指(09年年9月月)A）算法在）算法在执执行行过过程中所需要的程中所需要的计计算机存算机存储储空空间间B）算法所）算法所处处理的数据量理的数据量C）算法程序中的）算法程序中的语语句或指令条数句或指令条数D）算法在）算法在执执行行过过程中所需要的程中所需要的临时临时工作工作单单元数元数(6)下列叙述中正确的是下列叙述中正确的是(06年年9月月)A）一个算法的空）一个算法的空间间复复杂杂度大，度大，则则其其时间时间复复杂杂度也必定大度也必定大B）一个算法的空）一个算法的空间间复复杂杂度大，度大，则则其其时间时间复复杂杂度必定小度必定小C）一个算法的）一个算法的时间时间复复杂杂度大，度大，则则其空其空间间复复杂杂度必定小度必定小D）上述三种）上述三种说说法都不法都不对对(D)计算工作量(A)(D)2021/3/1012讲解：XXu算法的时间复杂度是指算法的时间复杂度是指A)执行算法程序所需要的时间执行算法程序所需要的时间B)算法程序的长度算法程序的长度C)算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数D)算法程序中的指令条数算法程序中的指令条数u算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、【1】和拥有足够的情报。和拥有足够的情报。u算法的空间复杂度是指算法的空间复杂度是指A)算法程序的长度算法程序的长度B)算法程序中的指令条数算法程序中的指令条数C)算法程序所占的存储空间算法程序所占的存储空间D)执行过程中所需要的存储空间执行过程中所需要的存储空间u在计算机中，算法是指在计算机中，算法是指A)加工方法加工方法B)解题方案的准确而完整的描述解题方案的准确而完整的描述C)排序方法排序方法D)查询方法查询方法例题讲解例题讲解有穷性有穷性2021/3/1013讲解：XXu算法分析的目的是算法分析的目的是A)找出数据结构的合理性找出数据结构的合理性B)找出算法中输入和输出找出算法中输入和输出之间的关系之间的关系C)分析算法的易懂性和可靠性分析算法的易懂性和可靠性D)分析算法的效率分析算法的效率以求改进以求改进u算法的工作量大小和实现算法所需的存储单元多少算法的工作量大小和实现算法所需的存储单元多少分别称为算法的分别称为算法的【1】。时间复杂度和空间复杂度时间复杂度和空间复杂度2021/3/1014讲解：XX计算机在进行数据处理时，实际需要处理的数据元素一般有很计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，省计算机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题。二、数据结构二、数据结构程序程序=算法算法+数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。超市的物品如何超市的物品如何存放才好找且节存放才好找且节省空间呢？省空间呢？2021/3/1015讲解：XX二二.数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。2021/3/1016讲解：XXu1. 逻辑结构逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。构。数据的逻辑结构包含：数据的逻辑结构包含：（1）表示数据元素的信息；）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。例：例：1.一年四季的数据结构一年四季的数据结构B=(D,R)D=春，夏，秋，冬春，夏，秋，冬R=(春，夏春，夏),(夏，秋夏，秋),(秋，冬秋，冬)2.家庭成员的数据结构家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿父亲，儿子，女儿R=(父亲，儿子父亲，儿子),(父亲，女儿父亲，女儿)春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子女儿2021/3/1017讲解：XXu常见的常见的逻辑结构逻辑结构有：有：线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。线性结构线性结构树形结构树形结构图图形形结结构构u线性结构线性结构结构中的每个元素之间存在一个对一个的关系；结构中的每个元素之间存在一个对一个的关系；u树形结构树形结构结构中的每个元素之间存在一个对多个的关系；结构中的每个元素之间存在一个对多个的关系；u图形结构或网状结构图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。结构中的每个元素之间存在多个对多个的关系。其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。二元关系表示，也可以直观地用图形来表示。2021/3/1018讲解：XXu2.存储结构（物理结构存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。们的逻辑关系不一定是相同的，而且一般也不可能相同。如：如：一年四季家庭成员计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见的存储结构有：n顺序存储结构顺序存储结构n链式存储结构链式存储结构n索引存储结构索引存储结构只抽象地反映数据元素之间的关系的结构，只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结而不管其存储方式的数据结构称为逻辑结构。构。一种一种数据结构可以根据需要表示成一种或数据结构可以根据需要表示成一种或多种存储结构多种存储结构。2021/3/1019讲解：XXu3.数据的运算数据的运算n检索检索n插入插入n删除删除n更新更新n排序排序通常，一个数据结构中的元素结点可能是动态变化的。根据需要通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。的运算还有查找、分类、合并、分解、复制和修改。在对数据结构的处理过程中，不仅数据结构中结点的个数在动态在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表数据结构是研究数据和数据之数据结构是研究数据和数据之间关系的一门学科，研究以下三间关系的一门学科，研究以下三方面内容：方面内容：n数据的逻辑结构数据的逻辑结构n数据的存储结构数据的存储结构n数据的运算数据的运算父亲儿子女儿2021/3/1020讲解：XX常见的数据结构常见的数据结构u 数据结构分类数据结构分类 线性结构与非线性结构线性结构与非线性结构两大类型线性结构：一个非空的数据结构若满足下面的两个条件，则这种数据一个非空的数据结构若满足下面的两个条件，则这种数据结构即为结构即为线性结构线性结构线性结构线性结构。有且仅有一个根结点；有且仅有一个根结点；除第一个结点外，每一个结点最多有一个前件；除第一个结点外，每一个结点最多有一个前件；除最后一个结点外，每一个结点最多有一个后件。除最后一个结点外，每一个结点最多有一个后件。常见的线性结构有：常见的线性结构有：线性表、栈、队列、线性链表等线性表、栈、队列、线性链表等线性表、栈、队列、线性链表等线性表、栈、队列、线性链表等2021/3/10年11月21日21 21讲解：XXa1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态常见的非线性结构有树、常见的非线性结构有树、二叉树、图等二叉树、图等二叉树、图等二叉树、图等非线性结构：一个数据结构不是线性结构。一个数据结构不是线性结构。2021/3/10年11月21日2222讲解：XX 线性表（线性表（线性表（线性表（LinearListLinearList）线性表是由线性表是由n（n0）个数据元素）个数据元素a1，a2，ai，an组成的一个有限序列。组成的一个有限序列。简单的线性表简单的线性表简单的线性表简单的线性表春春夏夏秋秋冬冬复杂的线性表复杂的线性表复杂的线性表复杂的线性表记录记录102011001张三张三男男记录记录202011003李四李四女女记录记录3记录记录42021/3/1023讲解：XX线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构特点：特点：顺序存储结构把顺序存储结构把逻辑上相逻辑上相邻邻的数据元素存储在的数据元素存储在物理上相邻物理上相邻的的存储单元里，顺序存储结构存储单元里，顺序存储结构只存储只存储结点的值结点的值，不存储结点间的关系，不存储结点间的关系，结点间的关系由存储单元的邻接关结点间的关系由存储单元的邻接关系来体现。系来体现。a1a2aian存储地址存储地址200020042000+4*(i-1)2000+4*(n-1)占占4个字节个字节LoaLoa（a ai i）=Loa=Loa（a a1 1）+L*+L*（i-1i-1）第i个数的地址第一个数的地址L为该类型数所占的字节线性表的存储结构线性表的存储结构线性表的存储结构有两种：线性表的存储结构有两种：u顺序存储结构顺序存储结构u链式存储结构链式存储结构2021/3/1024讲解：XXu顺序表的插入运算顺序表的插入运算u顺序表的删除运算顺序表的删除运算顺序表的插入和删除运算顺序表的插入和删除运算顺序表的插入和删除运算顺序表的插入和删除运算在线性表顺序存储情况下，要插入或删除一个元在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。2021/3/1025讲解：XX插入运算插入运算ai-1.a2a1alengthai+1aixai-1.a2a1alengthai+1aiX 插入算法的分析插入算法的分析: : 假设线性表中含有假设线性表中含有n n个数据元素，在进行插入操作时，若假定个数据元素，在进行插入操作时，若假定在在n+1n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：个位置上插入元素的可能性均等，则平均移动元素的个数为：2021/3/1026讲解：XX删除运算删除运算ai-1.a2a1alengthai+1aiai-1.a2a1alengthai+1删除算法的分析删除算法的分析: : 在进行删除操作时，若假定删除每个元素的可能性均等，则平在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：均移动元素的个数为：总结总结: : 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。插入或删除操作时，这一点需要值得考虑。2021/3/1027讲解：XX线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构u线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。u链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。关系是由各结点的指针域指示。u链式存储结构的每一个存储结点不仅存储结点的值，而且存链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：储结点之间的关系：u链式存储结构分为单链表、双向链表、循环链表链式存储结构分为单链表、双向链表、循环链表u线性链表不能随机存取线性链表不能随机存取数据域数据域指针域指针域2021/3/1028讲解：XX设线性表为设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态线性链表线性链表的物理状态的物理状态1 a12 a23 a34 a45 a567线性表的线性表的线性表的线性表的顺顺顺顺序存储序存储序存储序存储结构结构结构结构注意:123此类编号不代表所在的地址单元的地址编码线性表的链式存储结构线性表的链式存储结构及其插入与删除操作及其插入与删除操作2021/3/1029讲解：XXzhaoqiansunlizhouwuzhengwang/H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针单链表单链表2021/3/1030讲解：XX单链表的插入运算单链表的插入运算在在P所指向的结点之后插入所指向的结点之后插入新的结点新的结点单链表单链表删除运算删除运算PbaxSbaPLaaian ai-1ai+1要求要求:删除结点删除结点ai。2021/3/1031讲解：XX循环链表循环链表:首尾相接的链表。首尾相接的链表。将将最最后后一一个个结结点点的的空空指指针针改改为为指指向向头头结结点点，从从任任一一结结点点出出发发均均可可找找到到其其它结点它结点。a1a2ana3L.带头结点的单链表带头结点的单链表a1a2ana3L.循环单链表循环单链表特点特点: 可以从任何一个结点开始访问链表的所有结点可以从任何一个结点开始访问链表的所有结点.2021/3/1032讲解：XX双向链表的存储结构双向链表的存储结构在在每每个个结结点点中中设设置置两两个个指指针针，一一个个指指向向后后继继，一一个个指指向向前前驱驱。可可直直接接确定一个结点的前驱和后继结点。可提高效率。确定一个结点的前驱和后继结点。可提高效率。HEAD31510a2a3a4a1提问：单向链表的缺点是什么？提示：如何寻找结点的直接前趋。双向链表可以克服单链表的单向性的缺点。在双向链表的结点中有两个指针域，其一指向直接后继，另一在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。指向直接前趋。双向循环链表双向循环链表2021/3/1033讲解：XXu线性表的应用：应用最广的数据结构。线性表的应用：应用最广的数据结构。u.高级语言中的数组；高级语言中的数组；u计算机的文件系统；计算机的文件系统；u计算机的目录系统；计算机的目录系统；u电话号码查询系统（可采用顺序表或单链表结构电话号码查询系统（可采用顺序表或单链表结构）；）；u各种事务处理（各种事务处理（可采用顺序表或单链表结构可采用顺序表或单链表结构）;2021/3/1034讲解：XX2.栈和队列栈和队列栈和队列栈和队列是两种特殊的线性表，它们是运算时要是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为受到某些限制的线性表，故也称为限定性的数限定性的数据结构据结构。uu 栈（栈（栈（栈（StackStack）及其基本运算）及其基本运算）及其基本运算）及其基本运算uu 队列（队列（队列（队列（QueueQueue）及其基本运算）及其基本运算）及其基本运算）及其基本运算uu 循环队列及其基本运算循环队列及其基本运算循环队列及其基本运算循环队列及其基本运算2021/3/1035讲解：XX1.栈栈栈栈是限定仅在表尾进行插入或删除操作的线性表。是限定仅在表尾进行插入或删除操作的线性表。栈顶栈顶表尾。表尾。栈底栈底表头。表头。空栈空栈不含元素的空表。不含元素的空表。a1a2an栈底栈底栈顶栈顶进栈进栈出栈出栈栈栈s=(a1,a2,an)后进先出或先后进先出或先进后出进后出（LIFO）2021/3/1036讲解：XXu栈的物理存储结构可以用顺序结构，也可以用链表结栈的物理存储结构可以用顺序结构，也可以用链表结构。构。u下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。n顺序栈的进栈和出栈运算顺序栈的进栈和出栈运算n栈的基本运算有三种：入栈、退栈和读栈顶元素栈的基本运算有三种：入栈、退栈和读栈顶元素在顺序栈中插入和删除运算不需要在顺序栈中插入和删除运算不需要移动表中其他数据元素移动表中其他数据元素。2021/3/1037讲解：XX2.栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算a2a1a1a2top用顺序存储结构表示的栈用顺序存储结构表示的栈:顺序栈用一组连续的存储单元存放自栈底到栈顶的数据顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量元素，一般用一维数组表示，设置一个简单变量top指示栈顶指示栈顶位置，位置，称为称为针栈顶指针栈顶指，它始终指向待插入元素的位置。它始终指向待插入元素的位置。基本运算：基本运算：压（进）栈：压（进）栈：PUSH出栈：出栈：POP读栈顶元素：读栈顶元素：gettop2021/3/1038讲解：XX例子：例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：空桟：topbase非空桟：非空桟：top始终在桟顶元素的后一个位置始终在桟顶元素的后一个位置桟的元素个数：桟的元素个数：top-base上溢上溢下溢下溢2021/3/1039讲解：XX2 2、队列、队列定义：一种特殊的线性结构，限定只能在表的一端进行插入，定义：一种特殊的线性结构，限定只能在表的一端进行插入，在在表的另一端进行删除的线性表表的另一端进行删除的线性表。此种结构称为先进先出。此种结构称为先进先出（FIFO）表。）表。a1,a2,a3,a4,an-1,an队队列列示示意意图图队队头头队队尾尾先进先出先进先出后进后出后进后出（LIFO）2021/3/1040讲解：XXe3e4 (c)(c)e1,e2出队，出队，e4入队入队 队队满满rear=3fronte1e2e3 (b)rearfront(b)e1,e2,e3入队入队队列的顺序存储结构及其基本运算队列的顺序存储结构及其基本运算 3210 (a)rear=front=-1(队空）队空）rearfront空队列空队列:非空队列非空队列:队列元素个数队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终指向队始终指向队尾元素的位置尾元素的位置rear-front2021/3/1041讲解：XX队列的物理存储结构可以用顺序结构，也可以用链式结队列的物理存储结构可以用顺序结构，也可以用链式结构。构。u顺序队列的运算顺序队列的运算栈有三种操作：栈有三种操作：入栈出栈读栈顶元素入栈出栈读栈顶元素队列有三种操作：入队出队读队首元素队列有三种操作：入队出队读队首元素例：有入栈元素序列：例：有入栈元素序列：ABCD，求可能的出栈序列，求可能的出栈序列如是队列又是什么情况呢？如是队列又是什么情况呢？2021/3/1042讲解：XXuu 循环队列循环队列循环队列循环队列 把队列的存储空间在逻辑上看作一个环，当把队列的存储空间在逻辑上看作一个环，当R指向存储空指向存储空间的末端后，就把它重新置于始端。间的末端后，就把它重新置于始端。u循环队列的运算循环队列的运算队列中进行插入的一端称做队尾队列中进行插入的一端称做队尾(rear),进行删除的一端进行删除的一端称做队首称做队首(front)。习题：数据结构分为逻辑结构和存储结构，循环队习题：数据结构分为逻辑结构和存储结构，循环队列属于列属于【】结构。（结构。（2005年年9月）月）答案：存储结构。答案：存储结构。2021/3/1043讲解：XXfrontrearMaxsize-101e3e4 rear=3front2021/3/1044讲解：XX0012345frontABCDEFrear上溢上溢0012345frontrear下溢下溢front=rear队满队满front=rear队空队空2021/3/1045讲解：XX数据存储结构方面的考题数据存储结构方面的考题1：数据的存：数据的存储结储结构是指构是指（2005年年4月）月）A)存存储储在外存中的数据在外存中的数据B)数据所占的存数据所占的存储储空空间间量量C)数据在数据在计计算机中的算机中的顺顺序存序存储储方式方式D)数据的数据的逻辑结逻辑结构在构在计计算机中的表示算机中的表示2.下列叙述中正确的是下列叙述中正确的是（2009年年3月）月）A）栈栈是是“先先进进先出先出”的的线线性表性表B）队队列是列是“先先进进后出后出”的的线线性表性表C）循）循环队环队列是非列是非线线性性结结构构D）有序）有序线线性表既可以采用性表既可以采用顺顺序存序存储结储结构，也可以采用构，也可以采用链链式存式存储结储结构构3.数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于。4.下列数据结构中，属于非线性结构的是下列数据结构中，属于非线性结构的是A）循环队列）循环队列B)带链队列带链队列C)二叉树二叉树D）带链栈）带链栈答案：答案：D。答案：答案：D。答案：线性结构。答案：线性结构。答案：答案：c2021/3/1046讲解：XX5。下列叙述中正确的是（下列叙述中正确的是（）。）。（2008年年9月）月）A）顺顺序序存存储储结结构构的的存存储储一一定定是是连连续续的的，链链式式存存储储结结构构的的存存储储空空间不一定是连续的间不一定是连续的B）顺顺序序存存储储结结构构只只针针对对线线性性结结构构，链链式式存存储储结结构构只只针针对对非非线线性性结构结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间）链式存储结构比顺序存储结构节省存储空间答案：答案：A。6 6。下列关于。下列关于栈栈的叙述正确的是的叙述正确的是 （2008年年4月）月） A A）栈栈按按“先先进进先出先出”组织组织数据数据 B)B)栈栈按按“先先进进后出后出”组织组织数据数据 C C）只能在）只能在栈栈底插入数据底插入数据 D 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，12021/3/1047讲解：XX9.设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向指向队头元素的前一位置队头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该循环队列中共有，则该循环队列中共有【2】个元素。个元素。（2010年年3月）月）8。假。假设设用一个用一个长长度度为为50的数的数组组（数（数组组元索的下元索的下标标从从0到到49）作）作为栈为栈的存的存储储空空间间，栈栈底指底指针针bottom指指间栈间栈底底元素，元素，栈顶栈顶指指针针top指向指向栈顶栈顶元素，如果元素，如果bottom=49，top=30（数（数组组下下标标），），则栈则栈中具有中具有【】个元素。个元素。（2009年年3月）月）答案：答案：19答案：答案：1546501102021/3/1048讲解：XXu链表不具有的特点是链表不具有的特点是A)不必事先估计存储空间不必事先估计存储空间B)可随机访问任一元素可随机访问任一元素C)插入删除不需要移动元素插入删除不需要移动元素D)所需空间与线性表长度成正比所需空间与线性表长度成正比u数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于【1】。u数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的A)存储结构存储结构B)物理结构物理结构C)逻辑结构逻辑结构D)物理和存储结构物理和存储结构u数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和【1】两大类。两大类。u数据的存储结构是指数据的存储结构是指A）数据所占的存储空间）数据所占的存储空间B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据例题讲解例题讲解存储结构存储结构 非线性结构非线性结构2021/3/1049讲解：XXu顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元的存储单元中。中。u数据处理的最小单位是数据处理的最小单位是A)数据数据B)数据元素数据元素C)数据项数据项D)数据结构数据结构u数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及据结构进行的运算，以及A)数据的存储结构数据的存储结构 B)计算方法计算方法C)数据映象数据映象D)逻辑存储逻辑存储u线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构B)随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构相邻相邻2021/3/1050讲解：XXu根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成构分成A)动态结构和静态结构动态结构和静态结构B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构C)线性结构和非线性结构线性结构和非线性结构D)内部结构和外部结构内部结构和外部结构u数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的【2】以及对数据的操作运算。以及对数据的操作运算。u数据的基本单位是数据的基本单位是【5】。u下列叙述中，错误的是下列叙述中，错误的是A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关C)数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构存储结构存储结构数据元素数据元素2021/3/1051讲解：XXu链表不具有的特点是链表不具有的特点是A)不必事先估计存储空间不必事先估计存储空间B)可随机访问任一元素可随机访问任一元素C)插入删除不需要移动元素插入删除不需要移动元素D)所需空间与线性表长度成正比所需空间与线性表长度成正比u顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元的存储单元中。中。u长度为长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为等时，插入一个元素所需移动元素的平均个数为【1】。u线性表若采用顺序存储结构时，要求内存中可用存储单元的地址线性表若采用顺序存储结构时，要求内存中可用存储单元的地址A)必须是连续的必须是连续的B)部分地址必须是连续的部分地址必须是连续的C)一定是不连续的一定是不连续的D)连续不连续都可以连续不连续都可以例题讲解例题讲解相邻相邻2021/3/1052讲解：XXu线性表线性表L=(a1,a2,a3,ai，an)，下列说法正确的是，下列说法正确的是A)每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件B)线性表中至少要有一个元素线性表中至少要有一个元素C)表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小D)除第一个元素和最后一个元素外，其余每个元素都有一个除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直且只有一个直接前件和直接后件接前件和直接后件u线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构B)随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构u下列叙述中，错误的是下列叙述中，错误的是A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关C)数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构2021/3/1053讲解：XXu根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成结构分成A)动态结构和静态结构动态结构和静态结构B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构C)线性结构和非线性结构线性结构和非线性结构D)内部结构和外部结构内部结构和外部结构u当线性表采用顺序存储结构实现存储时，其主要特点是当线性表采用顺序存储结构实现存储时，其主要特点是【1】。随机存取随机存取2021/3/1054讲解：XXu链表不具有的特点是链表不具有的特点是A)不必事先估计存储空间不必事先估计存储空间B)可随机访问任一元素可随机访问任一元素C)插入删除不需要移动元素插入删除不需要移动元素D)所需空间与线性表长度成正比所需空间与线性表长度成正比u用链表表示线性表的优点是用链表表示线性表的优点是A)便于随机存取便于随机存取B)花费的存储空间较顺序存储少花费的存储空间较顺序存储少C)便于插入和删除操作便于插入和删除操作D)数据元素的物理顺序与逻辑顺序相同数据元素的物理顺序与逻辑顺序相同u长度为长度为n的顺序存储线性表中的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为插入一个元素所需移动元素的平均个数为【1】。u在单链表中，增加头结点的目的是在单链表中，增加头结点的目的是A)方便运算的实现方便运算的实现B)使单链表至少有一个结点使单链表至少有一个结点C)标识表结点中首结点的位置标识表结点中首结点的位置D)说明单链表是线性表的链式存储实现说明单链表是线性表的链式存储实现例题讲解例题讲解2021/3/1055讲解：XXu非空的循环单链表非空的循环单链表head的尾结点的尾结点(由由p所指向所指向)，满足，满足A)p-next=NULLB)p=NULLC)p-next=headD)p=headu循环链表的主要优点是循环链表的主要优点是A)不再需要头指针了不再需要头指针了B)从表中任一结点出发都能访问到整个链表从表中任一结点出发都能访问到整个链表C)在进行插入、删除运算时，能更好的保证链表不断开在进行插入、删除运算时，能更好的保证链表不断开D)已知某个结点的位置后，能够容易的找到它的直接前件已知某个结点的位置后，能够容易的找到它的直接前件u当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为不能进行入队运算。这种情况称为【2】。u用链表表示线性表的突出优点是用链表表示线性表的突出优点是【1】。上溢上溢插入、删除灵活插入、删除灵活2021/3/1056讲解：XXu栈和队列的共同特点是栈和队列的共同特点是A)都是先进先出都是先进先出B)都是先进后出都是先进后出C)只允许在端点处插入和删除元素只允许在端点处插入和删除元素D)没有共同点没有共同点u如果进栈序列为如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是，则可能的出栈序列是A)e3,e1,e4,e2B)e2,e4,e3,e1C)e3,e4,e1,e2D)任意顺序任意顺序u一些重要的程序语言一些重要的程序语言(如如C语言和语言和Pascal语言语言)允许过程的递归调用。允许过程的递归调用。而实现递归调用中的存储分配通常用而实现递归调用中的存储分配通常用A)栈栈B)堆堆C)数组数组D)链表链表例题讲解例题讲解2021/3/1057讲解：XXu栈底至栈顶依次存放元素栈底至栈顶依次存放元素A、B、C、D，在第五个元素，在第五个元素E入栈前，栈中元素入栈前，栈中元素可以出栈，则出栈序列可能是可以出栈，则出栈序列可能是A)ABCEDB)DCBEAC)DBCEA D)CDABEu栈通常采用的两种存储结构是栈通常采用的两种存储结构是A)线性存储结构和链表存储结构线性存储结构和链表存储结构B)散列方式和索引方式散列方式和索引方式C)链表存储结构和数组链表存储结构和数组D)线性存储结构和非线性存储结构线性存储结构和非线性存储结构u栈和队列通常采用的存储结构是栈和队列通常采用的存储结构是【1】。u下列数据结构中，按先进后出原则组织数据的是下列数据结构中，按先进后出原则组织数据的是A)线性链表线性链表B)栈栈C)循环链表循环链表D)顺序表顺序表当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为入队运算。这种情况称为【2】。链表存储结构和数组链表存储结构和数组上溢上溢2021/3/1058讲解：XXu由两个栈共享一个存储空间的好处是由两个栈共享一个存储空间的好处是A)减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率B)节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率C)减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率D)节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率u下列关于栈的叙述中正确的是下列关于栈的叙述中正确的是）在栈中只能插入数据）在栈中只能插入数据B）在栈中只能删除数据）在栈中只能删除数据C）栈是先进先出的线性表）栈是先进先出的线性表D）栈是后进先出的线性表）栈是后进先出的线性表u下列关于队列的叙述中正确的是下列关于队列的叙述中正确的是）在队列中只能插入数据）在队列中只能插入数据B）在队列中只能删除数据）在队列中只能删除数据C）队列是先进先出的线性表）队列是先进先出的线性表D）队列是后进先出的线性表）队列是后进先出的线性表2021/3/1059讲解：XX树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。u树的概念树的概念u二叉树的概念二叉树的概念u二叉树的存储二叉树的存储u二叉树的遍历二叉树的遍历3.树与二叉树树与二叉树2021/3/1060讲解：XX树的概念树的概念树的概念树的概念u树的定义：是一种简单的非线性结构。树的定义：是一种简单的非线性结构。n个结点的有限集。个结点的有限集。（n=0）ABDFECGHIJKMn n结点：结点：结点：结点：n n根结点：根结点：根结点：根结点：没有前件的结点只没有前件的结点只有一个称为根结点。有一个称为根结点。简称树的简称树的根。根。n n空树：空树：空树：空树：无结点则称为空树；无结点则称为空树；n父结点：父结点：父结点：父结点：结点的前件称该结结点的前件称该结点的父结点。点的父结点。A只有一个只有一个结点的树结点的树2021/3/1061讲解：XX树型结构的常用术语树型结构的常用术语树型结构的常用术语树型结构的常用术语ABDFECGHIJKMn n子结点：子结点：子结点：子结点：结点的后件，称为该结结点的后件，称为该结点的子结点。可以有多个。点的子结点。可以有多个。n n叶子结点叶子结点叶子结点叶子结点没有后件的结点；没有后件的结点；Q：图中叶子结点有几个？图中叶子结点有几个？7n n结点的度结点的度结点的度结点的度一个结点的子树的个数；一个结点的子树的个数；(有几个分叉有几个分叉)Q：结点结点A、G的度数的度数？3 3，2. 2. Q：度数为度数为0 0、1 1、2 2、3 3的的结点分别有几个？结点分别有几个？n树的度树的度树的度树的度树中所有结点度的最大值；树中所有结点度的最大值；Q：右图中树的度？右图中树的度？3 32021/3/1062讲解：XX树型结构的常用术语树型结构的常用术语树型结构的常用术语树型结构的常用术语ABDFECGHIJKMn结点的层次结点的层次结点的层次结点的层次树中根结点的层次树中根结点的层次为为1，根结点子树的根为第，根结点子树的根为第2层，以层，以此类推；此类推；Q：图中结点图中结点F的层次？的层次？n树的深度树的深度树的深度树的深度 树中所有结点层次的最树中所有结点层次的最大值；大值；Q：图中树的深度？图中树的深度？n有序树、无序树有序树、无序树有序树、无序树有序树、无序树如果树中每棵子如果树中每棵子树从左向右的排列拥有一定的顺序，树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称不得互换，则称为有序树，否则称为无序树。为无序树。2021/3/1063讲解：XX二叉树的概念二叉树的概念二叉树的概念二叉树的概念定义：定义：定义：定义：二叉二叉树是一种有序的树形结构。它与一般树是一种有序的树形结构。它与一般树形结构的区别是：树形结构的区别是：n每个结点每个结点最多最多有两棵子树；有两棵子树；n子树有左右之分，次序不能任意颠倒。称左子树子树有左右之分，次序不能任意颠倒。称左子树和右子树和右子树二叉树的二叉树的5种基本形态种基本形态2021/3/1064讲解：XX第65页树与二叉树的区别树与二叉树的区别A树和二叉树的结点个数最少都可为树和二叉树的结点个数最少都可为0。B树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2。C树的结点无左、右之分，二叉树的树的结点无左、右之分，二叉树的结点结点子树有明确的左、右之分。子树有明确的左、右之分。3个结点的个结点的树树3个结点的个结点的二叉二叉树树2021/3/1065讲解：XX二叉树的性质二叉树的性质二叉树的性质二叉树的性质【性质1】在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点（个结点（i1）ABCDFEHG1213141589101145671232021/3/1066讲解：XX【性质2】深度为深度为h的二叉树最多有的二叉树最多有2h-1个结点（个结点（h1）ABCDFEHG1213141589101145671232021/3/1067讲解：XX【性质3】二叉树上叶子结点数比度为二叉树上叶子结点数比度为2的结点数多的结点数多1ABCDFEHG度为2的结点叶子结点2021/3/1068讲解：XX满二叉树和完全二叉树满二叉树和完全二叉树满二叉树和完全二叉树满二叉树和完全二叉树n n满二叉树满二叉树满二叉树满二叉树：除最后一层外，每一层上的所有结点都除最后一层外，每一层上的所有结点都有两个子结点。最后一层的结点均为有两个子结点。最后一层的结点均为0度。度。n n完全二叉树完全二叉树完全二叉树完全二叉树：除最后一层外，每一层上的结点数均除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少达到最大值，在最后一层上只缺少右边右边的若干结点。的若干结点。则称这棵二叉树为则称这棵二叉树为完全二叉树完全二叉树。完全二叉树中度数。完全二叉树中度数为为1的结点的个数为的结点的个数为0或或1。2021/3/1069讲解：XX121314158910114567123满二叉树满二叉树完全二叉树完全二叉树12138910114567123完全二叉树是满二叉树满二叉树也是完全二叉树2021/3/1070讲解：XX1213891011456123非完全二叉树非完全二叉树深度为深度为4的的完全二叉树完全二叉树845671232021/3/1071讲解：XX【性质4】具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2(n+1) 其中，其中， log2n 的结果是不大于的结果是不大于log2n的最大整数的最大整数121314158910114567123深度为深度为4的的满二叉树满二叉树深度为深度为4的完的完全二叉树全二叉树84567123深度为深度为3的完全二叉树具有的完全二叉树具有47个结点个结点深度为深度为4的完全二叉树具有的完全二叉树具有815深度为深度为5的完全二叉树具有的完全二叉树具有1531 log2(8+1) =ln9/In2=4 log2(15+1) =In16/In2=4深度为深度为6的完全二叉树的完全二叉树具有具有3263深度为深度为7的完全二叉树的完全二叉树具有具有64127深度为深度为8的完全二叉树的完全二叉树具有具有128255深度为深度为9的完全二叉树的完全二叉树具有具有256511深度为深度为10的完全二叉树具有的完全二叉树具有5121023深度为深度为11的完全二叉树具有的完全二叉树具有102420472021/3/1072讲解：XX性质性质5：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为112345678910121例：例：n=2k=2n=6k=3n=7k=3n=8k=4n=12k=42021/3/1073讲解：XX性质性质6：如果对一棵有：如果对一棵有n个结点的完全二叉树的结点按层个结点的完全二叉树的结点按层序编号，则对任一结点序编号，则对任一结点i(1=i=1,则双亲则双亲Parent(i)是结点是结点|i/2|。(2)如果如果2i=n,则编号则编号i的左子结点为的左子结点为2i，否则无左子结点，显，否则无左子结点，显然也就没有右子结点。然也就没有右子结点。(3)如果如果2i+11它的双亲是它的双亲是i/2取取整，左子结点是整，左子结点是2*i，右子结点，右子结点是是2*i+1.当然如果算下来超过当然如果算下来超过总数民总数民N，则为没有。，则为没有。2021/3/1074讲解：XX例：例：112345678910121i=6其双亲为其双亲为|i/2|=3；其左子结点为；其左子结点为2*i=12;i=1是树的根是树的根,无双亲无双亲;其左子结点为其左子结点为2*i=2,右子结点为右子结点为2*i+1=3.2*i=18122*i+1=1912其无左、右子结点。其无左、右子结点。2*i+1=1312其无右子结点。其无右子结点。i=9其双亲为其双亲为|i/2|=4；2021/3/1075讲解：XX1 1：在深度：在深度为为7 7的的满满二叉二叉树树中中, ,叶子叶子结结点的个数点的个数为为（20062006年年4 4月）月） A)32A)32 B)31 B)31 C)64C)64 D)63D)632 2：在深度：在深度为为7 7的的满满二叉二叉树树中，度中，度为为2 2的的结结点个数点个数为为【 】 。(07(07年年4 4月）月）3 3：一一棵棵二二叉叉树树中中共共有有7070个个叶叶子子结结点点与与8080个个度度为为1 1的的结结点点，则则该该二二叉叉树树中中的的总总结结点数点数为为 （0707年年9 9月）月） A A）219 B219 B）221 C221 C）229 D229 D）2312314 4： 某某二二叉叉树树中中度度为为2 2的的结结点点有有1818个个，则则该该二二叉叉树树中中有有 【 】个个叶叶子子结结点点。（20052005年年4 4月）月）5 5：一一棵棵二二叉叉树树第第六六层层（根根结结点点为为第第一一层层）的的结结点点数数最最多多为为【 】个个。（20052005年年9 9月）月）树型结构方面的考题树型结构方面的考题1答案：答案：C。3答案：答案：A。5答案：答案：32。2答案：答案：63。4答案：答案：19。2021/3/1076讲解：XX二叉树的存储二叉树的存储二叉树的存储二叉树的存储u在计算机中，二叉树通常采用链式存储结构。对在计算机中，二叉树通常采用链式存储结构。对于满二叉树和完全二叉树可以按层进行顺序存储。于满二叉树和完全二叉树可以按层进行顺序存储。LlinkinfoRlink二叉树的存储结点的结构二叉树的存储结点的结构ABDCFGEA G E F B C Dt2021/3/1077讲解：XX2、二叉树的存储结构、二叉树的存储结构 (2)链式存储结构链式存储结构T16若父结点在数组中若父结点在数组中i下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处。处。11ABcFED12 4 8 910563712131415(1)顺序存储结构顺序存储结构(1)顺序存储结构顺序存储结构2h-1= 24-1=15用用一一组组连连续续的的存存储储单单元元存存放放二二叉叉树树的的数数据据元元素素。结结点点在在数数组组中中的的相相对对位位置置蕴蕴含含着结点之间的关系着结点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。2021/3/1078讲解：XX(2)链式存储结构链式存储结构链式存储结构链式存储结构二叉链表二叉链表三叉链表三叉链表二叉链表：二叉链表：二叉链表的结点包含三个域：数据域、左、右指针域。二叉链表的结点包含三个域：数据域、左、右指针域。例：例：ABCDEFGABCDEFG2021/3/1079讲解：XX三叉链表：三叉链表：三叉链表的结点包含四个域：三叉链表的结点包含四个域：数据域、左、右、双亲指针域。数据域、左、右、双亲指针域。例：例：ABCDEFGABCDEFG链式存储结构的特点：链式存储结构的特点：（1）操作便于实现）操作便于实现（2）结构复杂）结构复杂2021/3/1080讲解：XX二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历u遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结点所有结点。u二叉树的遍历的次序与树型结构上的大多二叉树的遍历的次序与树型结构上的大多数运算有联系。数运算有联系。uu遍历的方式有三种遍历的方式有三种遍历的方式有三种遍历的方式有三种（1）先（前）序遍历（）先（前）序遍历（DLR）（2）中序遍历（）中序遍历（LDR）（3）后序遍历（）后序遍历（LRD）ABCDFEHG2021/3/1081讲解：XX二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历u遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结点所有结点。（1）先（前）序遍历（）先（前）序遍历（DLR）根左右根左右若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n访问根结点；访问根结点；n n先序先序先序先序遍历左子树；遍历左子树；n n先序先序先序先序遍历右子树。遍历右子树。ABCDFEHG先序遍历的结果：先序遍历的结果： A A B E C F G H D B E C F G H D2021/3/1082讲解：XX（2）中序遍历（）中序遍历（LDR）左根右左根右若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n中序遍历左子树；中序遍历左子树；n访问根结点；访问根结点；n中序遍历右子树。中序遍历右子树。中序遍历的结果：中序遍历的结果：EBAFHGCD（3）后序遍历（）后序遍历（LRD）右根左右根左若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n后序遍历左子树；后序遍历左子树；n后序遍历右子树；后序遍历右子树；n访问根结点。访问根结点。后序遍历的结果：后序遍历的结果：EBHGFDCAABCDFEHG2021/3/1083讲解：XXu先序序列：先序序列：ABDGCEFHu中序序列：中序序列：DGBAECHFu后序序列：后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？下图所示的二叉树经过三种遍历得到的顺序分别为？练习：练习：根据先序遍历序列，建立二叉树根据先序遍历序列，建立二叉树2021/3/1084讲解：XX1:1:设二叉树如下：设二叉树如下：设二叉树如下：设二叉树如下：（20102010年年年年3 3月）月）月）月）对该二叉树进行后序遍历的结果对该二叉树进行后序遍历的结果对该二叉树进行后序遍历的结果对该二叉树进行后序遍历的结果为为为为 【3 3】树型结构方面的考题树型结构方面的考题树型结构方面的考题树型结构方面的考题 2 22:2:对如下二叉树（对如下二叉树（对如下二叉树（对如下二叉树（20062006年年年年4 4月）月）月）月）进行后序遍历的结果为进行后序遍历的结果为进行后序遍历的结果为进行后序遍历的结果为A)ABCDEFA)ABCDEFB)DBEAFCB)DBEAFCC)ABDECFC)ABDECFD)DEBFCAD)DEBFCAEDBGHFCADABCFHDGE2021/3/1085讲解：XXu已知二叉树后序遍历序列是已知二叉树后序遍历序列是dabec，中序遍历序列是，中序遍历序列是debac，它的前序，它的前序遍历序列是遍历序列是A)acbedB)decabC)deabcD)cedbau已知一棵二叉树前序遍历和中序遍历分别为已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和和DBGEACHF，则该二叉树的后序遍历为，则该二叉树的后序遍历为A)GEDHFBCAB)DGEBHFCAC)ABCDEFGHD)ACBFEDHGu树是结点的集合，它的根结点数目是树是结点的集合，它的根结点数目是A)有且只有有且只有1B)1或多于或多于1C)0或或1D)至少至少2u下列叙述中正确的是下列叙述中正确的是A)线性表是线性结构线性表是线性结构B)栈与队列是非线性结构栈与队列是非线性结构C)线性链表是非线性结构线性链表是非线性结构D)二叉树是线性结构二叉树是线性结构例题讲解例题讲解2021/3/1086讲解：XXu在深度为在深度为5的满二叉树中，叶子结点的个数为的满二叉树中，叶子结点的个数为A)32B)31C)16D)15u若某二叉树的前序遍历访问顺序是若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是，则其后序遍历的结点访问顺序是A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfcau在树结构中，树根结点没有在树结构中，树根结点没有【1】。u具有具有3个结点的二叉树有个结点的二叉树有A)2种形态种形态B)4种形态种形态C)7种形态种形态D)5种形态种形态u设一棵二叉树中有设一棵二叉树中有3个叶子结点，有个叶子结点，有8个度为个度为1的结点，则该二叉树中的结点，则该二叉树中总的结点数为总的结点数为A)12B)13C)14D)15双亲结点双亲结点2021/3/1087讲解：XXu设有下列二叉树：设有下列二叉树：对此二叉树前序遍历的结果为对此二叉树前序遍历的结果为A)ZBTTCPXAB)ATBZXCTPC)ZBTACTXPD)ATBZXCPTu设有下列二叉树：设有下列二叉树：对此二叉树的中序遍历的结果为对此二叉树的中序遍历的结果为A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA2021/3/1088讲解：XXu设树设树T的度为的度为4,其中度为其中度为1、2、3、4的结点个数分别为的结点个数分别为4、2、1、1。则。则T中的叶子结点数为中的叶子结点数为A）8B）7C）6D）5u设一棵完全二叉树共有设一棵完全二叉树共有700个结点，则该二叉树中有（个结点，则该二叉树中有（）个叶子结点。）个叶子结点。u在一个容量为在一个容量为15的循环队列中，若头指针的循环队列中，若头指针front=6，尾指针，尾指针rear=9，则该循环队列中共有（，则该循环队列中共有（）个元素。）个元素。u设一棵二叉树的中序遍历结果为设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果，前序遍历结果为为ABDECF，则后序遍历结果为（，则后序遍历结果为（）。）。3503DEBFCA2021/3/1089讲解：XX查找技术查找技术查找是数据处理的重要内容。查找是数据处理的重要内容。u查找指在一个给定的数据结构中查找指定的元素，该元素也查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。称关键字。u若找到了满足条件的结点，称查找成功；否则称查找失败。若找到了满足条件的结点，称查找成功；否则称查找失败。u衡量一个查找算法的主要标准是查找过程中对关键字进行的衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。平均比较次数。u通常根据不同的数据结构，采用不同的查找方法：通常根据不同的数据结构，采用不同的查找方法：n顺序查找顺序查找n二分查找二分查找2021/3/1090讲解：XX1.7.1.1顺序查找（线性查找）顺序查找（线性查找）查找过程：查找过程：对给定的一关键字对给定的一关键字K，从线性表的一端开始，逐个进行记录的，从线性表的一端开始，逐个进行记录的关键字和关键字和K的比较，直到找到关键字等于的比较，直到找到关键字等于K的记录或到达表的另的记录或到达表的另一端。一端。可以采用从前向后查，也可采用从后向前查的方法。可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效率较低。在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。平均查找长度较大。最好情况：最好情况：1最坏情况：最坏情况：n在下面两种情况下只能采取顺序查找：在下面两种情况下只能采取顺序查找：a.线性表为无序表（元素排列是无序的）；线性表为无序表（元素排列是无序的）；b.即使是有序线性表，但采用的是链式存储结构。即使是有序线性表，但采用的是链式存储结构。2021/3/1091讲解：XX1.7.1.2折半查找（二分法查找）折半查找（二分法查找）u思想：先确定待查找记录所在的范围，然后逐步缩小范围，思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。直到找到或确认找不到该记录为止。u前提：必须在具有顺序存储结构的前提：必须在具有顺序存储结构的有序表中进行有序表中进行。u分三种情况：分三种情况：1）若中间项的值等于）若中间项的值等于x,则说明已查到。则说明已查到。2）若）若x小于中间项的值小于中间项的值,则在线性表的前半部分查找；则在线性表的前半部分查找；3）若）若x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。u特点：比顺序查找方法效率高。最坏的情况下，需要比较特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。次。2021/3/1092讲解：XX折半查找算法举例n对给定数列（有序）对给定数列（有序） 3 3，5 5，1111，1717，2121，2323，2828，3030，3232，5050，按折半查找算法，查找关键字值为，按折半查找算法，查找关键字值为3030的数据元素。的数据元素。 a a1 1 a a2 2 a a3 3 a a4 4 a a5 5 a a6 6 a a7 7 a a8 8 a a9 9 a a10 10 第第1 1次：次： 3 3，5 5，1111，1717，2121，2323，2828，3030，3232，50 50 K=30 K=30 mid1= mid1=（1+101+10）/2 = 5/2 = 5 kaka(mid1(mid1) )=a=a(5)(5)=21=21 第第2 2次：次： 23 23，2828，3030，3232，50 50 mid2 = mid2 = （6+106+10） /2 = 8/2 = 8 K=a K=a(mid2(mid2) )=a=a(8)(8)=30=30lowhighmidlowhighmid2021/3/109393讲解：XXn练习练习假设待查有序（升序）顺序表中数据元素的关键字序列假设待查有序（升序）顺序表中数据元素的关键字序列为（为（8,18,27,42,47,50,56, 68,95,1208,18,27,42,47,50,56, 68,95,120），用折半查找），用折半查找方法查找关键字值为方法查找关键字值为2727的数据元素的数据元素. .对于长度为对于长度为n n的有序线性表，最坏情况只需比较的有序线性表，最坏情况只需比较log2nlog2n次。次。2021/3/109494讲解：XX1.7.2 排序排序1.7.2.1概述概述1、排序的功能：、排序的功能：将一个数据元素（或记录）的将一个数据元素（或记录）的任意序任意序列列，重新，重新排成排成一个按关键字一个按关键字有序有序的序列。的序列。2、排序过程的组成步骤：、排序过程的组成步骤：首先首先比较比较两个关键字的大小；两个关键字的大小；然后将记录从一个位置然后将记录从一个位置移动移动到另一个位置。到另一个位置。2021/3/1095讲解：XX排序方法排序方法插入排序插入排序选择排序选择排序交换排序交换排序归并排序归并排序简单插入排序简单插入排序希尔排序希尔排序简单选择排序简单选择排序堆排序堆排序起泡排序起泡排序快速排序快速排序2021/3/1096讲解：XX1.7.2.2插入排序插入排序简单插入、希尔排序简单插入、希尔排序1 1、简单插入排序、简单插入排序: : 基本思想：基本思想：从数组的第从数组的第2 2号元素开始，顺序号元素开始，顺序从数组中取出元素，并将该元素插入到其左端从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。已排好序的数组的适当位置上。2021/3/1097讲解：XX该该算算法法适适合合于于n较较小小的的情情况况，时时间间复复杂度为杂度为O(n2).待排元素序列：待排元素序列：532736156942第一次排序：第一次排序：275336156942第二次排序：第二次排序：273653156942第三次排序：第三次排序：152736536942第四次排序：第四次排序：152736536942第五次排序：第五次排序：152736425369直接插入排序示例直接插入排序示例对于有对于有n个数个数据元素的待排据元素的待排序列，插入操序列，插入操作要进行作要进行n-1趟趟最坏情况下：最坏情况下： 需要需要n(n-1)/2次比较次比较最好：最好： n-1次比较次比较2021/3/1098讲解：XX希尔排序：希尔排序：希尔排序的基本思想希尔排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行先将整个待排记录序列分割成为若干子序列分别进行直接插入排序直接插入排序,待整个序列中的记录待整个序列中的记录“基本有序基本有序”时时,再对全再对全体记录进行一次直接插入排序体记录进行一次直接插入排序.最坏情况下：需要最坏情况下：需要O(n1.5)次比较次比较2021/3/1099讲解：XX1、简单选择排序、简单选择排序思想：首先从思想：首先从1n个元素中选出关键字个元素中选出关键字最小最小的记录交换的记录交换到到第一个第一个位置上。然后再从第位置上。然后再从第2个到第个到第n个元素中选出次个元素中选出次小的记录交换到小的记录交换到第二个第二个位置上，依次类推。位置上，依次类推。1.7.2.3选择排序选择排序简单选择排序、堆排序简单选择排序、堆排序简单选择排序法简单选择排序法, ,最坏情况需要最坏情况需要n(n-1)/2n(n-1)/2次比较；次比较；时间复杂度为时间复杂度为O(n2)， 适用于适用于待排序元素较少待排序元素较少的情况。的情况。2021/3/10100讲解：XX第第101101|92|92页页n初态：初态： 15，14，22，30，37，15，11n第一趟：第一趟： 11 14，22，30，37，15，15n第二趟：第二趟： 11，14 22，30，37，15，15n第三趟：第三趟： 11，14，15 30，37，22，15n第四趟：第四趟： 11，14，15，15 37，22，30n第五趟：第五趟： 11，14，15，15，22 37，30n第六趟：第六趟： 11，14，15，15，22，30 37 有序序列有序序列例：设待排数据元素的关键字为（例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示），每一趟排序后的序列状态如图所示：2021/3/10101讲解：XX2、堆排序、堆排序（也是一种选择排序）也是一种选择排序）堆堆是是具具有有特特定定条条件件的的顺顺序序存存储储的的完完全全二二叉叉树树，其其特特定定条条件件是是：任任何何一一个个非非叶叶子子结结点点的的关关键键字字大大于于等等于于（或或小小于于等等于于）子女的关键字的值。子女的关键字的值。897624331510112536497856(a):堆顶元素取最大值堆顶元素取最大值(b):堆顶元素取最小值堆顶元素取最小值堆排序需要比较的堆排序需要比较的次数为次数为O(nlog2n) (1) 堆的示例堆的示例 2021/3/10102讲解：XX1.7.2.4交交换换排排序序交换排序的特点在于交换排序的特点在于交换交换。有冒泡和快速排序两种。有冒泡和快速排序两种。1、冒泡排序（起泡排序）、冒泡排序（起泡排序）思想：思想：小的浮起，大的沉底。小的浮起，大的沉底。从左端开始比较。从左端开始比较。第一趟：第第一趟：第1个与第个与第2个比较，大则交换；第个比较，大则交换；第2个与第个与第3个比较，个比较，大则交换，大则交换，关键字最大的记录交换到最后一个位置上；关键字最大的记录交换到最后一个位置上；第二趟：对前第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换个记录进行同样的操作，关键字次大的记录交换到第到第n-1个个位置上；位置上；依次类推，则完成排序。依次类推，则完成排序。2021/3/10103讲解：XX冒泡排序冒泡排序冒泡排序冒泡排序u冒泡排序的方法：冒泡排序的方法：n扫描整个线性表，逐次对相邻的两个元素进行比较，若扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大为逆序，则交换；第一趟扫描的结果使最大(或最小或最小)的的元素排到表的最后元素排到表的最后(或最前或最前)；n除最后除最后(或最前或最前)一个元素，对剩余的元素重复上述过程，一个元素，对剩余的元素重复上述过程，将次大将次大(或次小或次小)的数排到表的倒数的数排到表的倒数(或正数或正数)第二个位置；第二个位置；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，冒泡排序需要对表扫描的线性表，冒泡排序需要对表扫描n-1遍。遍。2021/3/10104讲解：XX冒泡排序的方法冒泡排序的方法u设待排数据元素的关键字为（18，20，15，32，4，25），第一趟第一趟冒泡排序后的序列状态如图所示：182015324251820153242518152032425181520324251815204322518152042532最大数u第二趟冒泡排序第二趟冒泡排序2021/3/10105讲解：XXQ：第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最后成为有序序列？Q：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。u冒泡排序终止条件:本趟排序未发生交换，终止排序算法2021/3/10106讲解：XX初始初始第一趟第一趟第二趟第二趟第三趟第三趟第四趟第四趟第五趟第五趟序列序列排序后排序后排序后排序后排序后排序后排序后排序后排序后排序后2618 18181891826 26269153232 32915185447 915264791532915 471554设待排数据元素的关键字为（26,18,32,54,47,9,15)冒泡排序法，需要比较的次数为冒泡排序法，需要比较的次数为n(n-1)/2n(n-1)/2；2021/3/10107讲解：XX2、快速排序、快速排序(对冒泡排序的改进）对冒泡排序的改进）思想：通过一趟排序将待排序列思想：通过一趟排序将待排序列分成两部分分成两部分，使其中使其中一部分记录一部分记录的关键字均比的关键字均比另一部分小另一部分小，再分，再分别对这两部分排序，以达到整个序列有序。别对这两部分排序，以达到整个序列有序。时间复杂度：时间复杂度：O(log2n)当当待待排排序序列列逆逆序序时时，蜕蜕变变成成冒冒泡泡排排序序，时时间间复复杂杂度度: O(n(n-1)/2)2021/3/10108讲解：XX1.7.2.5内部排序方法的选择内部排序方法的选择各种排序方法各有优缺点，故在不同情况下可作不同的选各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有择。通常需考虑的因素有：待排序的记录个数；记录本身：待排序的记录个数；记录本身的大小；记录的键值分布情况的大小；记录的键值分布情况等。等。若待排序的记录个数若待排序的记录个数n较小时，可采用简单排序方法。较小时，可采用简单排序方法。若若n较大时，应采用快速排序或堆排序。较大时，应采用快速排序或堆排序。若待排序的记录已基本有序，可采用简单插入和起泡若待排序的记录已基本有序，可采用简单插入和起泡排序。排序。2021/3/10109讲解：XX方法方法归并排序归并排序简单插入简单插入希尔排序希尔排序简单选择简单选择堆排序堆排序起泡排序起泡排序快速排序快速排序插插入入选选择择交交换换比较次数比较次数使用建议使用建议查找查找:方法方法顺序顺序折半折半比较次数比较次数log2n最好最好:1最坏最坏:n平均平均:(n+1)/2使用条件使用条件顺序存储结构的顺序存储结构的有序表有序表任何表任何表排序排序:n-1n(n-1)/2n1.5n(n-1)/2nlog2nn-1n(n-1)/2log2nn(n-1)/2正序的表、正序的表、n小的表小的表与表的初始数据无关、与表的初始数据无关、n小的表小的表正序的表、正序的表、n小的表小的表n大的表大的表,但逆序的表会蜕变为起泡排序但逆序的表会蜕变为起泡排序借助辅助空间最多的方法借助辅助空间最多的方法n大的表大的表2021/3/10110讲解：XX第第111111|92|92页页排序法小结：排序法小结：u简单选择排序法简单选择排序法,最坏情况需要最坏情况需要n(n-1)/2次比较；次比较；u冒泡排序法冒泡排序法,最坏情况需要最坏情况需要n(n-1)/2次比较；次比较；u希尔排序法希尔排序法,最坏情况需要最坏情况需要O(n1.5)次比较；次比较；u堆排序法堆排序法,最坏情况需要最坏情况需要O(nlog2n)次比较；次比较；2021/3/10111讲解：XX第第112112|92|92页页排序查找方面的考题：排序查找方面的考题：(1)对对于于长长度度为为n的的线线性性表表，在在最最坏坏情情况况下下，下下列列各各排排序序法法所所对对应应的的比比较较次次数数中中正正确确的的是（是（2005年年4月）月）A)冒泡排序冒泡排序为为n/2B)冒泡排序冒泡排序为为nC)快速排序快速排序为为nD)快速排序快速排序为为n(n-1)/2(2)在在长长为为64的的有有序序线线性性表表中中进进行行顺顺序序查查找找，最最坏坏情情况况下下需需要要比比较较的的次次数数为为_。（06年年9月）月）A）63B）64C）6D）7(3)下列数据下列数据结结构中，能用二分法构中，能用二分法进进行行查查找的是（找的是（2005年年9月）月）A）顺顺序存序存储储的有序的有序线线性表性表B）线线性性链链表表C）二叉）二叉链链表表D）有序）有序线线性性链链表表(4)下列排序方法中，最坏情况下比下列排序方法中，最坏情况下比较较次数最少的是（次数最少的是（09年年3月）月）A）冒泡排序）冒泡排序B）简单选择简单选择排序排序C）直接插入排序）直接插入排序D）堆排序）堆排序DBAD2021/3/10112讲解：XXu在长度为在长度为n的有序线性表中进行二分查找。最坏的情况的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为下，需要的比较次数为【2】。u长度为长度为n的顺序存储线性表中，当在任何位置上插入一的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平个元素概率都相等时，插入一个元素所需移动元素的平均个数为均个数为【1】。u假设线性表的长度为假设线性表的长度为n，则在最坏情况下，冒泡排序需，则在最坏情况下，冒泡排序需要的比较次数为要的比较次数为A)log2nB)n2C)O(n1.5)D)n(n-1)/2u已知数据表已知数据表A中每个元素距其最终位置不远，为节省时中每个元素距其最终位置不远，为节省时间，应采用的算法是间，应采用的算法是A)堆排序堆排序B)直接插入排序直接插入排序C)快速排序快速排序D)直接选择排序直接选择排序例题讲解例题讲解log2nn/22021/3/10113讲解：XXu冒泡排序算法在最好的情况下的元素交换次数为冒泡排序算法在最好的情况下的元素交换次数为【1】。u在最坏情况下，堆排序需要比较的次数为在最坏情况下，堆排序需要比较的次数为【2】。u最简单的交换排序方法是最简单的交换排序方法是A)快速排序快速排序B)选择排序选择排序C)堆排序堆排序D)冒泡排序冒泡排序u排序是计算机程序设计中的一种重要操作，常见的排序排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、方法有插入排序、【1】和选择排序等。和选择排序等。0nlog2n交换排序交换排序2021/3/10114讲解：XXu在下列几种排序方法中，要求内存量最大的是在下列几种排序方法中，要求内存量最大的是A)插入排序插入排序B)选择排序选择排序C)快速排序快速排序D)归并排序归并排序u在待排序的元素序列基本有序的前提下，效率最高的排在待排序的元素序列基本有序的前提下，效率最高的排序方法是序方法是A)冒泡排序冒泡排序B)选择排序选择排序C)快速排序快速排序D)归并排序归并排序u希尔排序属于希尔排序属于A)交换排序交换排序B)归并排序归并排序C)选择排序选择排序D)插入排序插入排序u对长度为对长度为n的线性表进行顺序查找，在最坏的情况下所的线性表进行顺序查找，在最坏的情况下所需要的比较次数为需要的比较次数为)n+1B)nC)(n+1)/2D)n/22021/3/10115讲解：XX2.程序设计基础2021/3/10116讲解：XX第二章第二章程序设计基础程序设计基础内容：内容：1.程序设计方法与风格。程序设计方法与风格。2.结构化程序设计。结构化程序设计。3.面向对象的程序设计方法，对象，方面向对象的程序设计方法，对象，方法，属性及继承与多态性。法，属性及继承与多态性。2021/3/10117讲解：XX1. 1. 源程序的文档化源程序的文档化n符号的命名符号的命名: :见名知意见名知意n注释（序言性和功能性注释）注释（序言性和功能性注释）n程序的视觉组织程序的视觉组织: :空格、空行、缩进。空格、空行、缩进。2. 2. 数据说明数据说明n数据说明的次序应该规范化数据说明的次序应该规范化n变量安排有序化变量安排有序化n对复杂数据结构应注释说明对复杂数据结构应注释说明3. 3. 语句的结构语句的结构n每条语句简单明了每条语句简单明了n尽量不用或少用尽量不用或少用GOTOGOTO语句语句n尽量只采用尽量只采用3 3种基本控制结构编程种基本控制结构编程4. 4. 输入和输出输入和输出n对所有输入数据进行校验和合理性检查对所有输入数据进行校验和合理性检查n输入输出格式保持一致输入输出格式保持一致n设计良好的输出报表设计良好的输出报表清晰第一，效率第二清晰第一，效率第二2.1.2 程序设计风格程序设计风格2021/3/10118讲解：XX2021/3/10119讲解：XX2.2结构化程序设计结构化程序设计2.2.1 2.2.1 基本概念基本概念基本思想基本思想 对大型的程序设计，使用一些基本的结构来设计程序，无论多复对大型的程序设计，使用一些基本的结构来设计程序，无论多复杂的程序，都可以使用这些基本结构按一定的顺序组合起来。这些杂的程序，都可以使用这些基本结构按一定的顺序组合起来。这些基本结构的特点都是只有一个入口、一个出口。由这些基本结构组基本结构的特点都是只有一个入口、一个出口。由这些基本结构组成的程序就避免了任意转移、阅读起来需要来回寻找的问题。成的程序就避免了任意转移、阅读起来需要来回寻找的问题。u三种基本结构三种基本结构n顺序结构顺序结构n选择结构选择结构n循环结构循环结构u三种基本结构的特点三种基本结构的特点n只有一个入口只有一个入口n只有一个出口只有一个出口n每一个基本结构中的每一部分都有机会执行到每一个基本结构中的每一部分都有机会执行到n结构内不存在结构内不存在“死循环死循环”2021/3/10120讲解：XX2.2.2 2.2.2 设计原则设计原则n自顶向下（先总体，后细节）自顶向下（先总体，后细节）n逐步求精（设计子目标过渡）逐步求精（设计子目标过渡）n模块化模块化 （分解总目标）（分解总目标）n限制使用限制使用gotogoto语句语句结构化程序设计方法特点结构化程序设计方法特点n要求把程序的结构规定为顺序、选择和循环三种基本机构，并要求把程序的结构规定为顺序、选择和循环三种基本机构，并提出了提出了自顶向下、逐步求精、模块化程序设计自顶向下、逐步求精、模块化程序设计等原则。等原则。n结构化程序设计是把模块分割方法作为对大型系统进行分析的结构化程序设计是把模块分割方法作为对大型系统进行分析的手段，使其最终转化为三种基本结构，其目的是为了解决由许手段，使其最终转化为三种基本结构，其目的是为了解决由许多人共同开发大型软件时，如何高效率地完成可靠系统的问题。多人共同开发大型软件时，如何高效率地完成可靠系统的问题。n缺点：程序和数据结构松散地耦合在一起。解决此问题的方法缺点：程序和数据结构松散地耦合在一起。解决此问题的方法就是采用面向对象的程序设计方法就是采用面向对象的程序设计方法(OOP)(OOP)。2021/3/10121讲解：XX2.3.2 2.3.2 基本概念基本概念u对象对象(Object)(Object)n对象对象是系统中用来描述客观事物的一个实体，是构成系统是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，的一个基本单位，它既包括数据（属性），也包括作用于它既包括数据（属性），也包括作用于数据的操作（行为）。数据的操作（行为）。n一个对象把属性和行为封装为一个整体一个对象把属性和行为封装为一个整体n一个对象通常可由一个对象通常可由对象名、属性和操作对象名、属性和操作3 3部分组成部分组成n属性属性即对象所包含的信息即对象所包含的信息n操作操作描述了对象执行的功能，操作也称为方法或服务。描述了对象执行的功能，操作也称为方法或服务。2.3 2.3 面向对象的程序设计面向对象的程序设计2021/3/10122讲解：XXu主要优点主要优点n与人类习惯的思维方法一致与人类习惯的思维方法一致n稳定性好稳定性好n可重用性好（可重用性好（* *）n可维护性好可维护性好n易于开发大型软件产品易于开发大型软件产品n对象的基本特性：对象的基本特性： （1 1）标识唯一性）标识唯一性 （对象可区分）（对象可区分） （2 2）分类性）分类性 （对象抽象成类）（对象抽象成类） （3 3）多态性）多态性 （同一操作可以是不同对象的行为）（同一操作可以是不同对象的行为） （4 4）封装性）封装性 （只能看到对象的外部特性）（只能看到对象的外部特性）信息隐蔽性是通过对象信息隐蔽性是通过对象的封装性来实现的。的封装性来实现的。 （5 5）模块独立性好（对象内部各元素结合紧密、内聚性强）模块独立性好（对象内部各元素结合紧密、内聚性强）2021/3/10123讲解：XXu类类是指具有共同属性、共同方法的对象的集合。是指具有共同属性、共同方法的对象的集合。u所以类是对象的抽象，对象是对应类的一个实例。所以类是对象的抽象，对象是对应类的一个实例。 u消息消息是一个实例与另一个实例之间传递的信息。是一个实例与另一个实例之间传递的信息。消息的组成包括消息的组成包括 （1 1）接收消息的对象的名称；）接收消息的对象的名称； （2 2）消息标识符，也称消息名；）消息标识符，也称消息名； （3 3）零个或多个参数。）零个或多个参数。在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送消息。发送消息。u继承继承是指能够直接获得已有的性质和特征，而不必重复定义他们。是指能够直接获得已有的性质和特征，而不必重复定义他们。n 单继承指一个类只允许有一个父类单继承指一个类只允许有一个父类n 多重继承指一个类允许有多个父类。多重继承指一个类允许有多个父类。n类的继承性是类之间共享属性和操作的机制，它提高了软件的可类的继承性是类之间共享属性和操作的机制，它提高了软件的可重用性。重用性。u多态性多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。现象。2021/3/10124讲解：XXu结构化结构化程序设计的程序设计的3种结构是种结构是A)顺序结构、选择结构、转移结构顺序结构、选择结构、转移结构B)分支结构、等价结构、循环结分支结构、等价结构、循环结构构C)多分支结构、赋值结构、等价结构多分支结构、赋值结构、等价结构D)顺序结构、选择结构、循环结顺序结构、选择结构、循环结构构u在设计程序在设计程序时，应采纳的原则之一是时，应采纳的原则之一是A)不限制不限制goto语句的使用语句的使用B)减少或取消注解行减少或取消注解行C)程序越短越好程序越短越好D)程序结构应有助于读者理解程序结构应有助于读者理解u程序设计程序设计语言的基本成分是数据成分、运算成分、控制成分和语言的基本成分是数据成分、运算成分、控制成分和A)对象成分对象成分B)变量成分变量成分C)语句成分语句成分D)传输成分传输成分例题讲解例题讲解2021/3/10125讲解：XXu结构化结构化程序设计主要强调的是程序设计主要强调的是A)程序的规模程序的规模B)程序的效率程序的效率C)程序设计语言的先进性程序设计语言的先进性D)程序易读性程序易读性u以下不属于对象的基本特点的是以下不属于对象的基本特点的是A)分类性分类性B)多态性多态性C)继承性继承性D)封装性封装性u对建立对建立良好的程序设计风格，下面描述正确的是良好的程序设计风格，下面描述正确的是A)程序应简单、清晰、可读性好程序应简单、清晰、可读性好B)符号名的命名只要符合语法符号名的命名只要符合语法C)充分考虑程序的执行效率充分考虑程序的执行效率D)程序的注释可有可无程序的注释可有可无u在结构化程序在结构化程序设计思想提出之前，在程序设计中曾强调程序的设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的效率，现在，与程序的效率相比，人们更重视程序的A)安全性安全性B)一致性一致性C)可理解性可理解性D)合理性合理性2021/3/10126讲解：XXu程序的程序的3种基本控制结构是种基本控制结构是A)过程、子过程和分程序过程、子过程和分程序B)顺序、选择和重复顺序、选择和重复C)递归、堆栈和队列递归、堆栈和队列D)调用、返回和转移调用、返回和转移u下列下列叙述中，不属于结构化程序设计方法的主要原则的叙述中，不属于结构化程序设计方法的主要原则的是是A)自顶向下自顶向下 B)由底向上由底向上C)模块化模块化D)限制使用限制使用goto语句语句u对象实现了数据和操作的结合，是指对数据和数据的操对象实现了数据和操作的结合，是指对数据和数据的操作进行作进行A)结合结合B)隐藏隐藏C)封装封装D)抽象抽象类是一个支持集成的抽象数据类型，而对象是类的类是一个支持集成的抽象数据类型，而对象是类的_。实例实例2021/3/10127讲解：XXu在面向对象方法中，一个对象请求另一个对象为其服务的在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送方式是通过发送A）调用语句）调用语句B）命令）命令C）口令）口令D）消息）消息u信息屏蔽的概念与下述哪一种概念直接相关信息屏蔽的概念与下述哪一种概念直接相关A）软件结构定义）软件结构定义B）模块独立性）模块独立性C）模块类型划分）模块类型划分D）模块偶合度）模块偶合度u下列对象概念描述错误的是下列对象概念描述错误的是A）任何对象都必须有继承性）任何对象都必须有继承性B）对象是属性和方法的封装体）对象是属性和方法的封装体C）对象间的通讯靠消息传递）对象间的通讯靠消息传递D）操作是对象的动态属性）操作是对象的动态属性2021/3/10128讲解：XXu下列叙述下列叙述中，不属于结构化分析方法的是中，不属于结构化分析方法的是A)面向数据流的结构化分析方法面向数据流的结构化分析方法B)面向数据结构的面向数据结构的Jackson方法方法C)面向数据结构的结构化数据系统开发方法面向数据结构的结构化数据系统开发方法D)面向对象的分析方法面向对象的分析方法u在面向对象的程序设计中，类描述的是具有相似性在面向对象的程序设计中，类描述的是具有相似性质的一组质的一组【3】u在面向对象方法中，类之间共享属性和操作的机制在面向对象方法中，类之间共享属性和操作的机制称为称为【2】。u一个类可以从直接或间接的祖先中继承所有属性和一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的方法。采用这个方法提高了软件的【3】。对象的共同行为和属性对象的共同行为和属性继承继承可重用性可重用性2021/3/10129讲解：XXu面向对象的模型中，最基本的概念是对象和面向对象的模型中，最基本的概念是对象和【3】。u在面向对象的设计中，用来请求对象执行某一处理或回在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为答某些信息的要求称为【4】。u在程序设计在程序设计阶段应该采取阶段应该采取【2】和逐步求精的方法，把和逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，一个模块的功能逐步分解，细化为一系列具体的步骤，进而用某种程序设计语言写成程序。进而用某种程序设计语言写成程序。u在面向对象方法种，类之间共享属性和操作的机制称为在面向对象方法种，类之间共享属性和操作的机制称为_。消息消息自顶向下自顶向下属性、行为属性、行为继承继承2021/3/10130讲解：XXu【3】是是一一种种信信息息隐隐蔽蔽技技术术，目目的的在在于于将将对对象象的使用者和对象的设计者分开。的使用者和对象的设计者分开。u可可以以把把具具有有相相同同属属性性的的一一些些不不同同对对象象归归类类，称称为为【3】。u子子程程序序通通常常分分为为两两类类：【2】和和函函数数，前前者者是是命命令令的的抽抽象，后者是为了求值。象，后者是为了求值。u源源程程序序文文档档化化要要求求程程序序应应加加注注释释。注注释释一一般般分分为为序序言言性注释和性注释和_。u在在面面向向对对象象方方法法种种，信信息息屏屏蔽蔽是是通通过过对对象象的的_性性来实现的。来实现的。封装封装类类过程过程功能性注释功能性注释封装封装2021/3/10131讲解：XX程序设计基础方面的考题程序设计基础方面的考题1.符合结构化原则的三种基本控制结构是：选择结构、循环结构和符合结构化原则的三种基本控制结构是：选择结构、循环结构和【】.(2009年年3月月)2.下列选项中不属于结构化程序设计原则的是下列选项中不属于结构化程序设计原则的是（2009年年9月月）A)可封装可封装D)自顶向下自顶向下C)模块化模块化D)逐步求精逐步求精3.以下叙述中正确的是以下叙述中正确的是。（。（2010年年3月月）A）程序设计的任务就是编写程序代码并上机调试）程序设计的任务就是编写程序代码并上机调试B）程序设计的任务就是确定所用数据结构）程序设计的任务就是确定所用数据结构C）程序设计的任务就是确定所用算法）程序设计的任务就是确定所用算法D）以上三种说法都不完整）以上三种说法都不完整4.在面向对象方法中，类的实例称为在面向对象方法中，类的实例称为【_】。（。（2005年年4月月）5.在面向对象方法中在面向对象方法中,【_】描述的是具有相似属性与操作的一组对象。描述的是具有相似属性与操作的一组对象。（2006年4月）（顺序结构）（顺序结构）AD对象对象类类2021/3/10132讲解：XX3.软件工程基础2021/3/10133讲解：XX3.1基本概念基本概念u软件软件程序程序数据数据相关文档相关文档机器可执行的程序和数据机器可执行的程序和数据机器不能执行的，与软件开发、运行、维护、使用等有关的文档机器不能执行的，与软件开发、运行、维护、使用等有关的文档2021/3/10134讲解：XX软件的特点包括：软件的特点包括：（1 1）软件是一种逻辑实体；）软件是一种逻辑实体；（2 2）软件的生产与硬件不同，它没有明显的制作过程；）软件的生产与硬件不同，它没有明显的制作过程；（3 3）软件在运行、使用期间不存在磨损、老化问题；）软件在运行、使用期间不存在磨损、老化问题；（4 4）软件的开发、运行对计算机系统具有依赖性，受）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；计算机系统的限制，这导致了软件移植的问题；（5 5）软件复杂性高，成本昂贵；）软件复杂性高，成本昂贵；（6 6）软件开发涉及诸多的社会因素。）软件开发涉及诸多的社会因素。软件按功能分为：软件按功能分为： 应用软件、系统软件、支撑软件（或工具软件）。应用软件、系统软件、支撑软件（或工具软件）。2021/3/10135讲解：XXu1. 1. 软件危机软件危机n软件危机：泛指在计算机软件的开发和维护中所遇到软件危机：泛指在计算机软件的开发和维护中所遇到的一系列严重问题。的一系列严重问题。n软件危机主要表现在成本、质量、生产率等问题。软件危机主要表现在成本、质量、生产率等问题。n软件危机主要表现在：软件危机主要表现在：n1 1、软件需求增长得不到满足软件需求增长得不到满足n2 2、软件开发成本和进度无法控制软件开发成本和进度无法控制n3 3、软件不可维护和维护程度非常低软件不可维护和维护程度非常低n4 4、软件质量难以保证软件质量难以保证n5 5、软件的成本不断提高软件的成本不断提高n6 6、软件开发生主率的提高跟不上硬件的发展和应用需软件开发生主率的提高跟不上硬件的发展和应用需求的增长。求的增长。2021/3/10136讲解：XXu2.软件工程软件工程n软件工程是应用于计算机软件的定义、开发软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标和维护的一整套方法、工具、文档、实践标准和工序。准和工序。n其目的是提高软件生产率、提高软件质量、其目的是提高软件生产率、提高软件质量、降低软件成本。降低软件成本。n它所包含的内容有以下两方面：它所包含的内容有以下两方面：n 软件开发技术软件开发技术 主要有软件开发方法学、主要有软件开发方法学、软件工具、软件工程环境。软件工具、软件工程环境。n 软件工程管理软件工程管理 主要有软件管理、软件工主要有软件管理、软件工程经济学。程经济学。2021/3/10137讲解：XX. . 软件工程三要素软件工程三要素n方法：完成软件工程项目的技术手段方法：完成软件工程项目的技术手段n工具：支持软件的开发、管理、文档生成工具：支持软件的开发、管理、文档生成n过过程程：支支持持软软件件开开发发的的各各个个环环节节的的控控制制、管管理理；将将方方法法和和工工具具综综合合起起来来, ,以以达达到到合合理理、及及时时地地进进行计算机软件开发的目的。行计算机软件开发的目的。n过过程程是是把把输输入入转转化化为为输输出出的的一一组组彼彼此此相相关关的的资资源的活动。源的活动。2021/3/10138讲解：XX3.软件生命周期软件生命周期n将软件产品从提出、实现、使用、维护到将软件产品从提出、实现、使用、维护到停止使用退役的过程称为软件生命周期停止使用退役的过程称为软件生命周期n分为软件定义、软件开发及软件运行维护分为软件定义、软件开发及软件运行维护3 3个阶段。个阶段。n维护维护是持续时间最长，花费代价最大的一是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护代价软件的可维护性，降低维护代价。2021/3/10139讲解：XXn6 6个活动阶段个活动阶段n制定计划制定计划：确定系统的总体目标确定系统的总体目标。参加人员有用户、项目负责人和系统分析员，产生文档有参加人员有用户、项目负责人和系统分析员，产生文档有可行性分析报告、项目计划书等可行性分析报告、项目计划书等n需求分析需求分析：对开发软件提出的需求进行分并给出详细对开发软件提出的需求进行分并给出详细定义。定义。确定系统的逻辑模型。参加人员有用户、项目负责人和系确定系统的逻辑模型。参加人员有用户、项目负责人和系统分析员。产生文档为需求规格说明书，其作用统分析员。产生文档为需求规格说明书，其作用：（1 1）便于用户、开发人员进行理解交流；）便于用户、开发人员进行理解交流；（2 2）反映用户问题的结构，可以作为软件开发工作的基）反映用户问题的结构，可以作为软件开发工作的基础和依据；础和依据；（3 3）作为确认测试和验收的依据）作为确认测试和验收的依据2021/3/10140讲解：XXu软件设计软件设计：分为概要设计和详细设计分为概要设计和详细设计。 包括软件包括软件结构设计结构设计、数据设计数据设计、接口设计接口设计和和过程设计过程设计。 结构设计结构设计是定义软件系统各部件之间的关系；是定义软件系统各部件之间的关系； 数据设计数据设计是将分析时创建的模型转化为数据结构的定义；是将分析时创建的模型转化为数据结构的定义； 接口设计接口设计是描述软件内部、软件和操作系统之间及软件与是描述软件内部、软件和操作系统之间及软件与 人人之间如何通信；之间如何通信； 过程设计过程设计是把系统结构部件转换成软件的过程性描述。是把系统结构部件转换成软件的过程性描述。 软件设计分概要设计和详细设计。软件设计分概要设计和详细设计。 参加人员有系统分析员和高级程序员。产生的文档有参加人员有系统分析员和高级程序员。产生的文档有设计规格设计规格说明书。说明书。u软件实现：编程。高级程序员和程序员产生软件实现：编程。高级程序员和程序员产生源程序清单源程序清单u软件测试：在设计测试用例的基础上，检验软件的各个组成软件测试：在设计测试用例的基础上，检验软件的各个组成部分。产生部分。产生软件测试计划和软件测试报告软件测试计划和软件测试报告u运行与维护运行与维护2021/3/10141讲解：XX制定计划制定计划需求分析需求分析软件设计软件设计实现实现测试测试运行和维护运行和维护确定系统的总体目标确定系统的总体目标需求规格说明书需求规格说明书概要设计说明书概要设计说明书详细设计说明书详细设计说明书 测试计划初稿测试计划初稿完成程序代码完成程序代码用户手册用户手册单元测试计划单元测试计划检验软件检验软件测试分析报告测试分析报告制定计划制定计划需求分析需求分析概要设计概要设计实现实现测试测试退役退役详细设计详细设计使用使用维护维护定义阶段定义阶段开发阶段开发阶段维护阶段维护阶段2021/3/10142讲解：XX第143页3.2 3.2 需求分析与结构化分析方法需求分析与结构化分析方法u需求分析的方法需求分析的方法结构化分析方法结构化分析方法面向对象的分析方法面向对象的分析方法面向数据流的结构化方法面向数据流的结构化方法(SA)(SA)面向数据结构面向数据结构JacksonJackson方法方法(JSD)(JSD)面向数据结构的结构化数据系统开发方面向数据结构的结构化数据系统开发方法法(DSSD)(DSSD)2021/3/10143讲解：XX需求分析的任务：需求分析的任务：导出目标系统的逻辑模型，解决“做什么”的问题。需求分析一般分为：需求分析一般分为：四个步骤进行需求获取需求分析编写需求规格说明书需求评审第144页2021/3/10144讲解：XX第145页结构化分析常用工具结构化分析常用工具:(1)(1)数据流图数据流图(2)(2)数据字典数据字典(3)(3)判定树判定树(4)(4)判定表判定表结构化分析方法的实质：结构化分析方法的实质： 着眼于数据流，自顶向下，逐层分解，建立系统的处着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具理流程，以数据流图和数据字典为主要工具, ,建立系统的建立系统的逻辑模型。逻辑模型。2021/3/10145讲解：XX第146页数据流图（数据流图（DFDDFD）: :描述数据处理过程的工具，是需求理解的逻辑模型的描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。图形表示，它直接支持系统功能建模。2021/3/10146讲解：XX第147页建立数据流图的步骤：建立数据流图的步骤：（1 1）由外向里；）由外向里；（2 2）自顶向下：顶层、中间层、低层数据流图；）自顶向下：顶层、中间层、低层数据流图；（3 3）逐层分解）逐层分解；2021/3/10147讲解：XX第148页2021/3/10148讲解：XX第149页数据字典数据字典(DD(DD):对所有与系统相关的数据元素的一个有组织的列表，以及精对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。存储成分和中间计算结果有共同的理解。数据字典是各类数据描述的集合，它通常包括数据字典是各类数据描述的集合，它通常包括5 5个部分：个部分： 即即数据项、数据结构、数据流、数据存储、和处理过程。数据项、数据结构、数据流、数据存储、和处理过程。数据字典是结构化分析的核心。数据字典是结构化分析的核心。数据字典的作用是对数据流图中出现的被命名的图形元素的数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。确切解释。2021/3/10149讲解：XX第150页存储文件存储文件”存折存折”的的DD定义定义:2021/3/10150讲解：XX第151页判定树：判定树： 当数据流图中的当数据流图中的加工加工依赖于多个逻辑时，可以使用判定树来依赖于多个逻辑时，可以使用判定树来描述。从问题定义的文字描述中分清哪些是判定的条件，哪些描述。从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。从属关系、并列关系、选择关系，根据它们构造判定树。2021/3/10151讲解：XX第152页判定表：判定表： 与判定树相似，当数据流图中的加工要依赖于多个逻辑条与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。的组合而引发的，使用判定表描述比较适宜。2021/3/10152讲解：XX第153页软件需求规格说明书，其作用软件需求规格说明书，其作用：（1 1）便于用户、开发人员进行理解交流；）便于用户、开发人员进行理解交流；（2 2）反映用户问题的结构，可以作为软件开发工作的基）反映用户问题的结构，可以作为软件开发工作的基 础和依据；础和依据；（3 3）作为确认测试和验收的依据。）作为确认测试和验收的依据。需求分析结束时产生：需求分析结束时产生：（1 1）DFDDFD、DDDD、判定树、判定表、判定树、判定表（2 2）软件需求规格说明书）软件需求规格说明书2021/3/10153讲解：XX第154页软件需求规格说明书的特点：软件需求规格说明书的特点：（1 1）正确性；）正确性；（2 2）无岐义性；）无岐义性；（3 3）完整性；）完整性；（4 4）可验证性；）可验证性；（5 5）一致性；）一致性；（6 6）可理解性；）可理解性；（7 7）可追踪性。）可追踪性。2021/3/10154讲解：XX第155页3.3 3.3 结构化设计方法、概要设计和详细设计结构化设计方法、概要设计和详细设计u软件设计软件设计 软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，软件设计是确定系统的物理模型。预定的任务，软件设计是确定系统的物理模型。 软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径。件产品或系统的唯一途径。 需求分析解决做什么的问题，软件设计主要解决怎么做的问题。需求分析解决做什么的问题，软件设计主要解决怎么做的问题。u从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。过程设计。 结构设计：定义软件系统各主要部件之间的关系。结构设计：定义软件系统各主要部件之间的关系。 数据设计：将分析时创建的模型转化为数据结构的定义。数据设计：将分析时创建的模型转化为数据结构的定义。 接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。通信。 过程设计：把系统结构部件转换成软件的过程描述。过程设计：把系统结构部件转换成软件的过程描述。u从工程管理角度来看：概要设计和详细设计。从工程管理角度来看：概要设计和详细设计。2021/3/10155讲解：XX第156页软件设计的基本原理：软件设计的基本原理： （1 1）抽象）抽象 （2 2）模块化）模块化 （3 3）信息隐蔽）信息隐蔽 （4 4）模块独立化）模块独立化 内聚性：内聚性： 耦合性耦合性：在程序结构中各模块的内聚性越强，则耦合性越弱。在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。优秀软件应高内聚，低耦合。2021/3/10156讲解：XX第157页 内聚性：内聚性：是一个模块内部各元素间彼此结合的紧密是一个模块内部各元素间彼此结合的紧密程度的度量。程度的度量。 内聚由弱到强排列：内聚由弱到强排列： 偶然内聚偶然内聚 逻辑内聚逻辑内聚时间内聚时间内聚过程内聚过程内聚通通信内聚信内聚顺序内聚顺序内聚功能内聚功能内聚 耦合性耦合性：模块间互相连接的紧密程度的度量。模块间互相连接的紧密程度的度量。 耦合性从高到低排列：耦合性从高到低排列： 内容耦合内容耦合公共耦合公共耦合外部耦合外部耦合控制耦合控制耦合标标记耦合记耦合数据耦合数据耦合非直接耦合非直接耦合2021/3/10157讲解：XX第158页3.3.2 3.3.2 概要设计概要设计n设计的基本任务设计的基本任务n软件的系统结构软件的系统结构n数据结构和数据库设计数据结构和数据库设计n编写概要设计文档编写概要设计文档n概要设计文档评审概要设计文档评审2021/3/10158讲解：XX第159页结构图（结构图（SC)SC)：概要设计概要设计( (软件结构设计软件结构设计) )的工具的工具:模块用一个矩形表示，箭头表示模块间的调用关系。模块用一个矩形表示，箭头表示模块间的调用关系。 在结构图中还可以用带注释的箭头表示模块调用过程中来在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据。心表示传递的是数据。2021/3/10159讲解：XX第160页结构图的基本形式：结构图的基本形式： 基本形式、顺序形式、重复形式、选择形式。基本形式、顺序形式、重复形式、选择形式。结构图有四种模块类型：结构图有四种模块类型： 传入模块、传出模块、变换模块和协调模块。传入模块、传出模块、变换模块和协调模块。2021/3/10160讲解：XX第161页需求分析需求分析逻辑模型逻辑模型数据流图数据流图概要设计概要设计系统结构图系统结构图物理模型物理模型概要设计的方法概要设计的方法: :典型的数据流类型有两种：变换型和事务型。典型的数据流类型有两种：变换型和事务型。变换型数据流系统结构图变换型数据流系统结构图事务型数据流系统结构图事务型数据流系统结构图2021/3/10161讲解：XX第162页3.3.3 3.3.3 详细设计详细设计n根本目标根本目标n确定应用怎样具体的实现所要求的系统，不是具体的编写程序，确定应用怎样具体的实现所要求的系统，不是具体的编写程序，而是要设计程序的而是要设计程序的“蓝图蓝图”n是为软件结构图中的每一个模块确定实现算法和局部数据结构，是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。用某种选定的表达工具表示算法和数据结构的细节。n此阶段的结果基本上决定了最终的程序代码的质量此阶段的结果基本上决定了最终的程序代码的质量n包括内容：包括内容：n代码设计代码设计n输入设计输入设计n输出设计输出设计n处理过程设计处理过程设计n用户界面设计用户界面设计n安全控制设计安全控制设计2021/3/10162讲解：XX第163页过程设计工具过程设计工具: :图形工具图形工具: : 程序流程图、程序流程图、N NS S图、图、表格工具：判定表表格工具：判定表语言工具：语言工具：( (伪码伪码) ) 程序流程图程序流程图: :2021/3/10163讲解：XX第164页u程序流程图程序流程图N-S图图PAD图图2021/3/10164讲解：XX第165页2021/3/10165讲解：XX第166页NS图：图：2021/3/10166讲解：XX第167页图：图：（伪码）：（伪码）：2021/3/10167讲解：XX6 6. .软件工程的目标软件工程的目标n在给定的成本、进度的前提下，开发出具有有效性、在给定的成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可适应性、可移植可靠性、可理解性、可维护性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品性、可追踪性和可互操作性且满足用户需求的产品n软件工程鼓励研制和采用各种先进的软件开发方法、软件工程鼓励研制和采用各种先进的软件开发方法、工具和环境工具和环境n软件工程需要达到的基本目标应是：付出较低的成软件工程需要达到的基本目标应是：付出较低的成本，达到要求的软件功能，取得较好的软件性能，本，达到要求的软件功能，取得较好的软件性能，开发的软件易于移植，需要较低的维护费用，能按开发的软件易于移植，需要较低的维护费用，能按时完成开发，及时交付使用。时完成开发，及时交付使用。2021/3/10168讲解：XX8. 8.软件工程的基本原则：软件工程的基本原则： 抽象、信息隐蔽、模块化、局部化（模块间松散，抽象、信息隐蔽、模块化、局部化（模块间松散，模块内内聚性强）、确定性、一致性、完备性模块内内聚性强）、确定性、一致性、完备性和可验证性。和可验证性。9. 9. 软件工具和软件开发环境软件工具和软件开发环境n软件工具软件工具(CASE)(CASE)：用来辅助软件开发、运行、：用来辅助软件开发、运行、维护、管理、支持等过程中的活动的软件维护、管理、支持等过程中的活动的软件n 软件开发工具从单项软件开发工具从单项 集成发展集成发展 n软件开发环境：支持软件产品开发全过程的软件开发环境：支持软件产品开发全过程的软件工具的集合。软件工具的集合。 2021/3/10169讲解：XX3.4 3.4 软件测试软件测试 软件测试定义：软件测试定义： 使用人工或自动手段来运行或测定某个系统的过程使用人工或自动手段来运行或测定某个系统的过程。 意义目的：意义目的：n尽可能多的发现错误尽可能多的发现错误n希望能以最少的人力和时间发现潜在的各种错误和缺陷希望能以最少的人力和时间发现潜在的各种错误和缺陷n保证系统质量和可靠性的关键步骤保证系统质量和可靠性的关键步骤 4.4.2 4.4.2 测试方法测试方法n静态测试：包括代码检查、静态结构分析、代码质量度静态测试：包括代码检查、静态结构分析、代码质量度量。量。 不实际运行软件，主要通过人工进行。不实际运行软件，主要通过人工进行。n动态测试：是基于计算机的测试。动态测试：是基于计算机的测试。 主要包括白盒测试方法和黑盒测试方法。主要包括白盒测试方法和黑盒测试方法。测试用例：测试用例： （输入值集），（输入值集）， （输出值集）（输出值集） 2021/3/10170讲解：XX3.4.3 3.4.3 白盒测试白盒测试n结构结构测试测试n将软件看成透明的白盒，根据程序的内部结构和逻辑结构将软件看成透明的白盒，根据程序的内部结构和逻辑结构来设计测试例子，对程序的来设计测试例子，对程序的路径和过程路径和过程进行测试，检查是进行测试，检查是否满足设计的要求否满足设计的要求n主要方法：逻辑覆盖、基本路径测试主要方法：逻辑覆盖、基本路径测试3.4.4 3.4.4 黑盒测试黑盒测试n功能功能测试测试n将软件看成黑盒子，在完全不考虑软件内部结构和特性的将软件看成黑盒子，在完全不考虑软件内部结构和特性的情况下，测试软件的外部特性情况下，测试软件的外部特性n主要方法：等价类划分法、边界值分析法、错误推测法主要方法：等价类划分法、边界值分析法、错误推测法3.4.5 3.4.5 软件测试的实施软件测试的实施n单元测试（模块测试）单元测试（模块测试）n集成测试集成测试n确认测试确认测试n系统测试系统测试2021/3/10171讲解：XXn单元测试：单元测试： 是对模块进行正确性检验的测试。是对模块进行正确性检验的测试。 是软件测试的最小单位，是软件测试的最小单位， 主要采用静态和动态测试法，动态测试以主要采用静态和动态测试法，动态测试以 白盒测试法为主，白盒测试法为主， 辅助于黑盒测试辅助于黑盒测试n集成测试集成测试是测试和组装软件的过程，主要目的是发现是测试和组装软件的过程，主要目的是发现与接口有关与接口有关的错误。的错误。n确认测试确认测试验证软件的功能和性能及其他特性是否满足了需求规格说明中确定验证软件的功能和性能及其他特性是否满足了需求规格说明中确定的各种要求。的各种要求。n系统测试系统测试将通过将通过确认确认测试的软件，与计算机硬件、外设等其他元素组合在一起，测试的软件，与计算机硬件、外设等其他元素组合在一起，在实际环境下对计算机系统进行一系列的集成测试和确认测试。在实际环境下对计算机系统进行一系列的集成测试和确认测试。2021/3/10172讲解：XX3.5 3.5 程序调试程序调试1 1 任务任务n根据测试时发现的错误，根据测试时发现的错误， （）找出原因和具体的位置（）找出原因和具体的位置 （）进行改正，排除错误（）进行改正，排除错误n由程序开发人员来进行，谁开发的程序就由谁来进行调试由程序开发人员来进行，谁开发的程序就由谁来进行调试2. 2. 程序调试的基本步骤：程序调试的基本步骤：（1 1）错误定位；）错误定位；（2 2）修改设计和代码，以排除错误；）修改设计和代码，以排除错误；（3 3）进行回归测试，防止引进新的错误。）进行回归测试，防止引进新的错误。3. 3.调试方法：（静态、动态调试法）调试方法：（静态、动态调试法）强行排错法强行排错法回溯法回溯法原因排除法（演绎、归纳、二分法原因排除法（演绎、归纳、二分法) )2021/3/10173讲解：XXu为了提高测试的效率，应该为了提高测试的效率，应该A)随机选取测试数据随机选取测试数据B)取一切可能的输入数据作为测试数据取一切可能的输入数据作为测试数据C)在完成编码以后制定软件的测试计划在完成编码以后制定软件的测试计划D)集中对付那些错误群集的程序集中对付那些错误群集的程序u软件生命周期中所花费用最多的阶段是软件生命周期中所花费用最多的阶段是A)详细设计详细设计B)软件编码软件编码C)软件测试软件测试D)软件维护软件维护u下列叙述中，不属于软件需求规格说明书的作用的是下列叙述中，不属于软件需求规格说明书的作用的是A)便于用户、开发人员进行理解和交流便于用户、开发人员进行理解和交流B)反映出用户问题的结构，可以作为软件开发工作的基础和依据反映出用户问题的结构，可以作为软件开发工作的基础和依据C)作为确认测试和验收的依据作为确认测试和验收的依据D)便于开发人员进行需求分析便于开发人员进行需求分析u下列不属于软件工程的下列不属于软件工程的3个要素的是个要素的是)工具工具)过程过程)方法方法)环境环境例题讲解例题讲解2021/3/10174讲解：XXu软件设计包括软件的结构、数据、接口和过程设计，软件设计包括软件的结构、数据、接口和过程设计，其中软件的过程设计是指其中软件的过程设计是指A)模块间的关系模块间的关系B)系统结构部件转换成软件的过程描述系统结构部件转换成软件的过程描述C)软件层次结构软件层次结构D)软件开发过程软件开发过程u检查软件产品是否符合需求定义的过程称为检查软件产品是否符合需求定义的过程称为)确认测试确认测试)集成测试集成测试)验证测试验证测试)验收测试验收测试u数据流图用于抽象描述一个软件的逻辑模型，数据流数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是于数据流图合法图符的是)控制流控制流)加工加工)数据存储数据存储)源和流源和流2021/3/10175讲解：XXu开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现象称作象称作A)软件投机软件投机B)软件危机软件危机C)软件工程软件工程D)软件产生软件产生u下面不属于软件设计原则的是下面不属于软件设计原则的是)抽象抽象)模块化模块化)自底向上自底向上)信息隐蔽信息隐蔽u开发大型软件时，产生困难的根本原因是开发大型软件时，产生困难的根本原因是A)大系统的复杂性大系统的复杂性B)人员知识不足人员知识不足C)客观世界千变万化客观世界千变万化D)时间紧、任务重时间紧、任务重u软件工程的出现是由于软件工程的出现是由于A)程序设计方法学的影响程序设计方法学的影响B)软件产业化的需要软件产业化的需要C)软件危机的出现软件危机的出现D)计算机的发展计算机的发展2021/3/10176讲解：XXu软件开发离不开系统环境资源的支持，其中必要的测软件开发离不开系统环境资源的支持，其中必要的测试数据属于试数据属于A)硬件资源硬件资源B)通信资源通信资源C)支持软件支持软件D)辅助资源辅助资源u在数据流图在数据流图(DFD)中，带有名字的箭头表示中，带有名字的箭头表示A)模块之间的调用关系模块之间的调用关系B)程序的组成成分程序的组成成分C)控制程序的执行顺序控制程序的执行顺序D)数据的流向数据的流向u下列不属于结构化分析的常用工具的是下列不属于结构化分析的常用工具的是A)数据流图数据流图B)数据字典数据字典C)判定树判定树D)PAD图图u在软件生产过程中，需求信息的给出者是在软件生产过程中，需求信息的给出者是A)程序员程序员B)项目管理者项目管理者C)软件分析设计人员软件分析设计人员 D)软件用户软件用户2021/3/10177讲解：XXu下列工具不是过程设计常用工具的是下列工具不是过程设计常用工具的是)PAD)PFD)N-S)DFDu模块独立性是软件模块化所提出的要求，衡量模块独立模块独立性是软件模块化所提出的要求，衡量模块独立性的度量标准则是模块的性的度量标准则是模块的A)抽象和信息隐蔽抽象和信息隐蔽B)局部化和封装化局部化和封装化C)内聚性和耦合性内聚性和耦合性D)激活机制和控制方法激活机制和控制方法u软件开发的结构化生命周期方法将软件生命周期划分成软件开发的结构化生命周期方法将软件生命周期划分成A)定义、开发、运行维护定义、开发、运行维护B)设计阶段、编程阶段、测试阶段设计阶段、编程阶段、测试阶段C)总体设计、详细设计、编程调试总体设计、详细设计、编程调试D)需求分析、功能定义、系统设计需求分析、功能定义、系统设计2021/3/10178讲解：XXu在软件工程中，白箱测试法可用于测试程序的内部结构。在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是此方法将程序看做是A)路径的集合路径的集合B)循环的集合循环的集合C)目标的集合目标的集合D)地址的集合地址的集合u完全不考虑程序的内部结构和内部特征，而只是根据程完全不考虑程序的内部结构和内部特征，而只是根据程序功能导出测试用例的测试方法是序功能导出测试用例的测试方法是A)黑箱测试法黑箱测试法B)白箱测试法白箱测试法C)错误推测法错误推测法D)安装测试法安装测试法u在结构化设计方法中，生成的结构图在结构化设计方法中，生成的结构图(SC)中，带有箭头中，带有箭头的连线表示的连线表示A)模块之间的调用关系模块之间的调用关系B)程序的组成成分程序的组成成分C)控制程序的执行顺序控制程序的执行顺序D)数据的流向数据的流向2021/3/10179讲解：XXu下列选项中，不属于模块间耦合的是下列选项中，不属于模块间耦合的是A)数据耦合数据耦合B)同构耦合同构耦合C)异构耦合异构耦合D)公用耦合公用耦合u下列叙述中，不属于测试的特征的是下列叙述中，不属于测试的特征的是A)测试的挑剔性测试的挑剔性B)完全测试的不可能性完全测试的不可能性C)测试的可靠性测试的可靠性D)测试的经济性测试的经济性u需求分析中开发人员要从用户那里了解需求分析中开发人员要从用户那里了解A)软件做什么软件做什么B)用户使用界面用户使用界面C)输入的信息输入的信息D)软件的规模软件的规模u下列不属于软件调试技术的是下列不属于软件调试技术的是A)强行排错法强行排错法B)集成测试法集成测试法C)回溯法回溯法D)原因排除法原因排除法2021/3/10180讲解：XXu为了避免流程图在描述程序逻辑时的灵活性，提出了用为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为方框图来代替传统的程序流程图，通常也把这种图称为A)PAD图图B)N-S图图C)结构图结构图 D)数据流图数据流图u软件复杂性度量的参数包括软件复杂性度量的参数包括A)效率效率B)规模规模C)完整性完整性D)容错性容错性u下列叙述中，正确的是下列叙述中，正确的是A)软件就是程序清单软件就是程序清单B)软件就是存放在计算机中的文件软件就是存放在计算机中的文件C)软件应包括程序清单及运行结果软件应包括程序清单及运行结果D)软件包括程序和文档软件包括程序和文档u软件设计中，有利于提高模块独立性的一个准则是软件设计中，有利于提高模块独立性的一个准则是A)低内聚低耦合低内聚低耦合B)低内聚高耦合低内聚高耦合C)高内聚低耦合高内聚低耦合D)高内聚高耦合高内聚高耦合2021/3/10181讲解：XXu软件生命周期中花费时间最多的阶段是软件生命周期中花费时间最多的阶段是A)详细设计详细设计B)软件编码软件编码C)软件测试软件测试D)软件维护软件维护u下列叙述中，不属于结构化分析方法的是下列叙述中，不属于结构化分析方法的是A)面向数据流的结构化分析方法面向数据流的结构化分析方法B)面向数据结构的面向数据结构的Jackson方法方法C)面向数据结构的结构化数据系统开发方法面向数据结构的结构化数据系统开发方法D)面向对象的分析方法面向对象的分析方法u详细设计的结果基本决定了最终程序的详细设计的结果基本决定了最终程序的A)代码的规模代码的规模B)运行速度运行速度C)质量质量D)可维护性可维护性u下列不属于静态测试方法的是下列不属于静态测试方法的是A)代码检查代码检查B)白盒法白盒法C)静态结构分析静态结构分析D)代码质量度量代码质量度量2021/3/10182讲解：XXu在软件生命周期中，能准确地确定软件系统必须做什么在软件生命周期中，能准确地确定软件系统必须做什么和必须局别哪些功能的阶段是和必须局别哪些功能的阶段是A）概要设计）概要设计B）详细设计）详细设计C）可行性分析）可行性分析D）需求分析）需求分析u检查软件产品是否符合需求定义的过程称为检查软件产品是否符合需求定义的过程称为A）确认测试）确认测试B）集成测试）集成测试C）验证测试）验证测试D）验收测试）验收测试u数据流图用于抽象描述一个软件的逻辑模型，数据流图数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成，下列图符名标识的图符不属于由一些特定的图符构成，下列图符名标识的图符不属于数据流图合法图符的是数据流图合法图符的是A）控制流）控制流B）加工）加工C）数据存储）数据存储D）源和潭）源和潭2021/3/10183讲解：XXu下面不属于软件设计原则的是下面不属于软件设计原则的是A）抽象）抽象B）模块化）模块化C）自底向上）自底向上D）信息屏蔽）信息屏蔽u程序流程图（程序流程图（PFD）中的箭头代表的是）中的箭头代表的是A）数据流）数据流B）控制流）控制流C）调用关系）调用关系D）组成关系）组成关系u下列工具中为需求分析常用工具的是下列工具中为需求分析常用工具的是A）PADB）PFDC）N-SD）DFDu在结构化方法中，软件功能分解属于下列软件开发中的阶在结构化方法中，软件功能分解属于下列软件开发中的阶段是段是A）详细设计）详细设计B）需求分析）需求分析C）总体设计）总体设计D）编程调试）编程调试2021/3/10184讲解：XXu软件调试的目的是软件调试的目的是A）发现错误）发现错误B）改正错误）改正错误C）改善软件的性能）改善软件的性能D）挖掘软件的潜能）挖掘软件的潜能u软件需求分析阶段的工作，可以分为四个方面：需求软件需求分析阶段的工作，可以分为四个方面：需求获取，需求分析，编写需求规格说明书，以及获取，需求分析，编写需求规格说明书，以及A）阶段性报告）阶段性报告B）需求评审）需求评审C）总结）总结D）都不正确）都不正确u软件是程序、数据和软件是程序、数据和_的集合。的集合。uJackson方法是一种面向方法是一种面向_的结构化方法。的结构化方法。u软件工程研究的内容主要包括：软件工程研究的内容主要包括：_技术和软件工程管技术和软件工程管理。理。文档文档数据结构数据结构软件开发软件开发2021/3/10185讲解：XXu通常，将软件产品从提出、实现、使用维护到停止使通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为用退役的过程称为【4】。u耦合和内聚是评价模块独立性的两个主要标准，其中耦合和内聚是评价模块独立性的两个主要标准，其中【3】反映了模块内各成分之间的联系。反映了模块内各成分之间的联系。u软件工程研究的内容主要包括：软件工程研究的内容主要包括：【4】技术和软件工技术和软件工程管理。程管理。uJackson结构化程序设计方法是英国的结构化程序设计方法是英国的M.Jackson提出提出的，它是一种面向的，它是一种面向【2】的设计方法。的设计方法。u软件设计模块化的目的是软件设计模块化的目的是【4】。软件生命周期软件生命周期耦合耦合软件开发软件开发数据结构数据结构降低复杂性降低复杂性2021/3/10186讲解：XXu数据流图的类型有数据流图的类型有【4】和事务型。和事务型。u软件危机出现于软件危机出现于60年代末，为了解决软件危机，人们提年代末，为了解决软件危机，人们提出了出了【3】的原理来设计软件，这就是软件工程诞生的的原理来设计软件，这就是软件工程诞生的基础。基础。u软件开发环境是全面支持软件开发全过程的软件开发环境是全面支持软件开发全过程的【4】集集合。合。u测试的目的是暴露错误，评价程序的可靠性；而测试的目的是暴露错误，评价程序的可靠性；而【2】的目的是发现错误的位置并改正错误。的目的是发现错误的位置并改正错误。u软件维护活动包括以下几类：改正性维护、适应性维软件维护活动包括以下几类：改正性维护、适应性维护、护、【3】维护和预防性维护。维护和预防性维护。完善性维护完善性维护变换型变换型工程化工程化软件工具软件工具程序调试程序调试2021/3/10187讲解：XXu软件结构是以软件结构是以【3】为基础而组成的一种控制层次结构。为基础而组成的一种控制层次结构。u为了便于对照检查，测试用例应由输入数据和预期的为了便于对照检查，测试用例应由输入数据和预期的【4】两部分组成。两部分组成。u软件工程包括软件工程包括3个要素，分别为方法、工具和个要素，分别为方法、工具和【4】。u软件工程的出现是由于软件工程的出现是由于【2】。u单元测试又称模块测试，一般采用单元测试又称模块测试，一般采用【3】测试。测试。u软件的软件的【3】设计又称为总体结构设计，其主要任务是设计又称为总体结构设计，其主要任务是建立软件系统的总体结构。建立软件系统的总体结构。模块模块输出数据输出数据过程过程软件危机软件危机白盒白盒概要概要2021/3/10188讲解：XX(1)下面叙述中错误的是下面叙述中错误的是(2009年年3月）月）A）软件测试的目的是发现错误并改正错误）软件测试的目的是发现错误并改正错误B）对被调试的程序进行）对被调试的程序进行“错误定位错误定位”是程序调试的必要步骤是程序调试的必要步骤C）程序调试通常也称为）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性）软件测试应严格执行测试计划，排除测试的随意性(2)软软件件测测试试可可分分为为白白盒盒测测试试和和黑黑盒盒测测试试。基基本本路路径径测测试试属属于于【】测测试。试。(2009年年3月）月）(3)按照软件测试的一般步骤，集成测试应在按照软件测试的一般步骤，集成测试应在_测试之后进行。测试之后进行。(4)软件工程三要素包括方法、工具和过程，其中，软件工程三要素包括方法、工具和过程，其中，_支持软件支持软件开发的各个环节的控制和管理。开发的各个环节的控制和管理。(2008年年9月月)(5)软软件件设计设计中划分模中划分模块块的一个准的一个准则则是是(2009年年9月）月）A)低内聚低耦合低内聚低耦合B)高内聚低耦合高内聚低耦合C)低内聚高耦合低内聚高耦合D)高内聚高耦合高内聚高耦合A软件工程方面的考题：软件工程方面的考题：白盒白盒单元单元过程过程B2021/3/10189讲解：XX(6)下列叙述中正确的是（下列叙述中正确的是（2005年年9月）月）A）软件交付使用后还需要进行维护）软件交付使用后还需要进行维护B）软件一旦交付使用就不需要再进行维护）软件一旦交付使用就不需要再进行维护C）软件交付使用后其生命周期就结束）软件交付使用后其生命周期就结束D）软件维护是指修复程序中被破坏的指令）软件维护是指修复程序中被破坏的指令(7)程序流程图中的菱形框表示的是程序流程图中的菱形框表示的是【2】(2009年年9月月)。(8)软件开发过程主要分为需求分析、设计、编码与测试四个阶段，软件开发过程主要分为需求分析、设计、编码与测试四个阶段，其中其中【3】阶段产生阶段产生“软件需求规格说明书。软件需求规格说明书。（2009年年9月）月）(9)下列叙述中正确的是（下列叙述中正确的是（2006年年4月）月）A)软件测试应该由程序开发者来完成软件测试应该由程序开发者来完成B)程序经调试后一般不需要再测试程序经调试后一般不需要再测试C)软件维护只包括对程序代码的维护软件维护只包括对程序代码的维护D)以上三种说法都不对以上三种说法都不对A逻辑条件逻辑条件需求分析需求分析D2021/3/10190讲解：XX(3)软软件件按按功功能能可可以以分分为为：应应用用软软件件、系系统统软软件件和和支支撑撑软软件件(或或工工具具软软件件)。下面属于系统软件的是。下面属于系统软件的是A)编辑软件编辑软件B)操作系统操作系统C)教务管理系统教务管理系统D)浏览器浏览器(4)软件软件(程序程序)调试的任务是调试的任务是A)诊断和改正程序中的错误诊断和改正程序中的错误B)尽可能多地发现程序中的错误尽可能多地发现程序中的错误C)发现并改正程序中的所有错误发现并改正程序中的所有错误D)确定程序中错误的性质确定程序中错误的性质(5)数据流程图数据流程图(DFD图图)是是A)软件概要设计的工具软件概要设计的工具B)软件详细设计的工具软件详细设计的工具C)结构化方法的需求分析工具结构化方法的需求分析工具D)面向对象方法的需求分析工具面向对象方法的需求分析工具(6)软软件件生生命命周周期期可可分分为为定定义义阶阶段段，开开发发阶阶段段和和维维护护阶阶段段。详详细细设设计计属属于于A)定义阶段定义阶段B)开发阶段开发阶段C)维护阶段维护阶段D)上述三个阶段上述三个阶段2010年年3月计算机等级考试月计算机等级考试BACB2021/3/10191讲解：XX数据库设计基础知识点得分表数据库设计基础知识点得分表数据库的数据库的基本概念基本概念数据数据模型模型关系关系代数代数数据库设数据库设计与管理计与管理小计08年年4月月2分6分2分10分08年年9月月2分4分2分2分10分09年年3月月2分2分2分4分10分09年年9月月2分2分2分4分10分10年年3月月2分4分2分2分10分时间知识点2021/3/10192讲解：XX5.数据库设计基础2021/3/10193讲解：XX5.0内容u数据库的基本概念：数据库，数据库管理系统，数据库系统。u数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。u关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。u数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。2021/3/10194讲解：XX5.1基本概念1.数据(Data)n实际上就是描述事物的符号记录n软件中的数据一定是有结构的2.数据库(DB)n长期存储在计算机内的，有组织的，可共享的数据集合。n数据库中的数据按一定的数学模型组织、描述和存储，具有较小的冗(rong)余度，较高的数据独立性和易扩展性，并可为各种用户共享。2021/3/10195讲解：XX3.数据库管理系统(DBMS)n数据库系统的核心软件n要在操作系统支持下工作n解决如何科学地组织和存储数据，如何高效的获取和维护数据的系统软件n主要功能包括n数据模式定义n数据存取的物理构建n数据操纵n数据的完整性、安全性定义与检查n数据库的并发控制与故障恢复n数据的服务2021/3/10196讲解：XXn为完成上述功能，DBMS一般提供相应的数据语言：n数据定义语言（DDL）n数据操纵语言（DML）n数据控制语言（DCL）n数据语言按其使用方式具有两种结构形式n交互式命令语言n宿主型语言4.数据库管理员n主要工作包括：n数据库设计n数据库维护n改善系统性能，提高系统效率2021/3/10197讲解：XX5.数据库系统（DBS）n由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、系统平台之硬件平台（硬件）和软件平台（软件）构成。6.数据库应用系统（DBAS）n利用数据库系统进行应用开发.由数据库系统、应用软件、应用界面三者组成。7.数据库管理技术的发展n人工管理阶段n文件系统阶段n数据库系统接数据库技术的根本目标：是解决数据共享问题。数据库技术的根本目标：是解决数据共享问题。2021/3/10198讲解：XX第199页数据库系统数据库系统2021/3/10199讲解：XX8.数据库系统的基本特点n数据的集成性n采用统一的数据结构方式n按照多个应用的需要组成全局的统一的数据结构n数据模式是多个应用共同的、全局的数据结构n数据的高共享性与低冗余性（可以减少冗长但无法避免冗长）n数据独立性n物理独立性和逻辑独立性n数据统一管理与控制n数据的完整性检查n数据的安全性检查n并发控制2021/3/10200讲解：XX9.数据库系统的内部结构体系n数据库系统的三级模式（1）概念模式（2）外模式（用户模式）（3）内模式（物理模式）n内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式n概念模式处于中层，它放映了设计者的数据全局逻辑要求n外模式处于最外层，它反映了用户对数据的要求2021/3/10201讲解：XXu数据库系统的两级映射：（1）概念模式/内模式映射：实现了概念模式到内模式的转换。当存储结构发生变化时，可通过修改概念模式/内模式映射，使数据逻辑模式不变，保证了很高的物理独立性。（2）外模式/概念模式映射：实现了外模式到概念模式之间的相互转换。当逻辑模式发生变化时，能过修改外模式/概念模式映射，使得用户所使用的那部分外模式不变，从而应用程序不必修改，保证较高的逻辑独立性。2021/3/10202讲解：XX203应用外模式外模式(用户数据库用户数据库)应用外模式外模式(用户数据库用户数据库)应用外模式外模式(用户数据库用户数据库)概念模式概念模式(概念数据库概念数据库)内模式内模式(物理数据库物理数据库)数据库数据库外模式外模式概念模式映射概念模式映射概念模式概念模式内模式映射模式内模式映射模式2021/3/10203讲解：XX5.2数据模型5.2.1数据模型的基本概念n数据模型是数据特性的抽象n数据模型描述的内容n数据结构n数据操作n数据约束n数据模型按不同的应用层次分成三种类型n概念数据模型（概念模型）主要有ER模型、扩充的ER模型、面向对象的模型、谓词模型。n逻辑数据模型（数据模型）主要有层次模型、网状模型、关系模型、面向对象模型。n物理数据模型（物理模型）2021/3/10204讲解：XX第205页2.数据模型数据模型uuE-RE-R模型的基本概念模型的基本概念模型的基本概念模型的基本概念（1）实体实体：现实世界中的事物现实世界中的事物；（2）属性属性：事物的特性；事物的特性；（3）联系联系：现实世界中事物间的关系。现实世界中事物间的关系。实体集的关系有一一对一、一对多、多对多对一、一对多、多对多的联系。一个班级的学生，学生与学生之间是一个班级的学生，学生与学生之间是一对一一对一的关系。的关系。在一所学校，一门课程与学生之间是在一所学校，一门课程与学生之间是一对多一对多的关系。的关系。在一所学校，多门课程与多个学生之间是在一所学校，多门课程与多个学生之间是多对多多对多的关系。的关系。E-RE-R模型的基本成分是实体和联系。模型的基本成分是实体和联系。模型的基本成分是实体和联系。模型的基本成分是实体和联系。三个基本概念之间的联接关系三个基本概念之间的联接关系三个基本概念之间的联接关系三个基本概念之间的联接关系n实体集与属性间的联接关系实体集与属性间的联接关系n实体与联系实体与联系2021/3/10205讲解：XX206uE-R模型的图示法用简单的几何图形表示实体集、属性与联系。用简单的几何图形表示实体集、属性与联系。(1)实体集表示法实体集表示法在在E-R图中用矩形表表示实体集，在矩形内写上实体集名称。图中用矩形表表示实体集，在矩形内写上实体集名称。如实体集学生如实体集学生(student)、实体集课程、实体集课程(course)(2)属性表示法属性表示法在在E-R图中用椭圆形表示属性，在椭圆形内写上该属性名称。图中用椭圆形表示属性，在椭圆形内写上该属性名称。如学生有属性：学号如学生有属性：学号(S#)、姓名、姓名(Sn)及年龄及年龄(Sa)可用如下表示。可用如下表示。studentcourseS#SnSa2021/3/10206讲解：XX207(3)联系表示法在在E-R图中用菱形图中用菱形(内写上联系名内写上联系名)表示联系。如学生与课程表示联系。如学生与课程的联系的联系SC,如下图所示：如下图所示：(4)实体集与属性间的联系关系实体集与属性间的联系关系属性依附于实体集，它们之间有联系关系用无向线段表示。属性依附于实体集，它们之间有联系关系用无向线段表示。SCstudentS#SnSa2021/3/10207讲解：XX208属性也依附于联系，它们之间也有联系关系，因此也可用无属性也依附于联系，它们之间也有联系关系，因此也可用无向线段，如联系向线段，如联系SC可与学生的课程成绩属性可与学生的课程成绩属性G建立联系并用下图表建立联系并用下图表示。示。(5)实体集与联系间的连接关系实体集与联系间的连接关系(也可用无向线段也可用无向线段)SCGstudentcourseSC2021/3/10208讲解：XX第209页E-R模型之间的联接关系：模型之间的联接关系：实体实体是概念世界中的基本单位，是概念世界中的基本单位，属性属性有属性域，每个实体可取属性域内有属性域，每个实体可取属性域内的值。的值。一个实体的所有属性值叫元组。一个实体的所有属性值叫元组。E-R模型的图示法：模型的图示法：（1）实体集表示法；）实体集表示法；用长方形（2）属性表法；）属性表法；用椭圆形（3）联系表示法。）联系表示法。用菱形，(m:n)2021/3/10209讲解：XX5.2.3层次模型n一种树形结构n数据结构比较简单，操作简单n对于实体间联系是固定的、且预先定义好的应用系统，有较高的性能n可以提供良好的完整性支持n不适合表示非层次性的联系，对于插入和删除操作的限制比较多n特点：A、每个树有且仅有一个无双亲结点，称为根，nB、树中除根外所有结点有且仅有一个双亲。2021/3/10210讲解：XX第211页层次模型层次模型（采用树型结构）图图1-4层次模型示例层次模型示例2021/3/10211讲解：XX5.2.4网状模型n一个不加任何条件限制的无向图n优于层次模型n使用时设计系统内部的物理因素较多，用户操作不方便，其数据模式与系统实现不甚理想2021/3/10212讲解：XX第213页网络模型网络模型（采用无向图型结构）2021/3/10213讲解：XX第214页5.2.2关系数据模型关系数据模型u关系模型采用二维表来表示关系模型采用二维表来表示，简称表，由表框架及表，简称表，由表框架及表的元组组成。的元组组成。一个二维表就是一个关系。一个二维表就是一个关系。u关系数据库系统的特点之一是它建立在数据理论的基关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的数据操础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系演算。作，其中最为著名的是关系代数与关系演算。学号学号姓名姓名性别性别出生日期出生日期入学成绩入学成绩四级通过否四级通过否计算机等级考试计算机等级考试备注备注04001001尚杰尚杰男男86-11-20520.5T一一级级04001002余余习习芳芳女女86-12-26513.5F二二级级04001057张轶张轶一一男男86-01-09612.0T04002023陶陶红红莉莉女女85-02-14535.0F二二级级2021/3/10214讲解：XX第215页关系模型关系模型（采用二维表结构）2021/3/10215讲解：XX2161.关系的数据结构关系的数据结构二维表由表框架与表元组（记录）组成。二维表由表框架与表元组（记录）组成。表框架由表框架由n个命名的属性组成个命名的属性组成(n称为属性元素称为属性元素)。每个属性有一个取值范围称为值域。每个属性有一个取值范围称为值域。表框架对应了关系的模式，即类型的概念。表框架对应了关系的模式，即类型的概念。每行数据称为元组，一个元组由每行数据称为元组，一个元组由n个元组分量所组成，每个元组分量个元组分量所组成，每个元组分量是表结构中每个属性的投影值。是表结构中每个属性的投影值。学号学号姓名姓名性别性别出生日期出生日期入学成绩入学成绩四级通过否四级通过否计算机等级考试计算机等级考试备注备注04001001尚杰尚杰男男86-11-20520.5T一一级级04001002余余习习芳芳女女86-12-26513.5F二二级级04001057张轶张轶一一男男86-01-09612.0T04002023陶陶红红莉莉女女85-02-14535.0F二二级级2021/3/10216讲解：XX217一个二维表要满足下面一个二维表要满足下面7个性质就可称为一个关系。个性质就可称为一个关系。二维表中元组个数是有限的二维表中元组个数是有限的二维表中元组均不相同二维表中元组均不相同二维表中元组的次序可任意交换二维表中元组的次序可任意交换二维表中元组的分量是不可分割的基本数据项二维表中元组的分量是不可分割的基本数据项二维表中属性名各不相同二维表中属性名各不相同二维表中属性与次序无关，可任意交换二维表中属性与次序无关，可任意交换二维表属性中的分量具有与该属性相同的值域二维表属性中的分量具有与该属性相同的值域二维表二维表关系模型关系模型VFP表文件表文件二维表框架二维表框架关系模式关系模式数据表结构数据表结构行行元组元组记录记录元组分量元组分量数据项数据项列列属性属性字段字段属性值域属性值域字段值域字段值域惟一标识元组的最小属性集称为该表的键惟一标识元组的最小属性集称为该表的键(或码或码)，在，在VFP表表中称为主关键字中称为主关键字2021/3/10217讲解：XX218关系模型的基本运算：关系模型的基本运算：1.数据查询数据查询查询关系数据库中的数据，一个关系内的查询以及多个关系间的查询关系数据库中的数据，一个关系内的查询以及多个关系间的查询。查询。查询的基本单位为元组分量，先定位后操作。查询的基本单位为元组分量，先定位后操作。纵向定位（列指定）纵向定位（列指定）横向定位（行选择）横向定位（行选择）2.数据插入数据插入插入一个元组（不定位）插入一个元组（不定位）3.数据删除数据删除删除一个元组（定位、操作）删除一个元组（定位、操作）4.数据修改数据修改删除需修改的元组再插入修改后的元组删除需修改的元组再插入修改后的元组关系中的数据约束：实体完整性约束、参照实体完整性约束、参照完整性约束和用户定义的完整性约束完整性约束和用户定义的完整性约束关系操作2021/3/10218讲解：XX219关系模型的基本运算：关系模型的基本运算：1.插入插入集合的集合的并并运算运算2.删除删除集合的集合的差差(交交)运算运算3.修改修改集合的集合的差差|并并(除除)运算。运算。4.查询查询（投影、选择、笛卡尔积运算投影、选择、笛卡尔积运算）3.关系代数2021/3/10219讲解：XX集合的并运算集合的并运算R S2021/3/10220讲解：XX集合的差运算集合的差运算RS2021/3/10221讲解：XX222集合的交运算集合的交运算RS2021/3/10222讲解：XX223u笛卡尔积是对两个关系的合并操作。笛卡尔积是对两个关系的合并操作。有三个关系R、S和TR关系关系n1行行,m1列列S关系关系n2行，行，m2列列T关系关系行数行数=n1*n2列数列数=m1+m2AmnBC13ABCm13n13RST笛卡尔积运算笛卡尔积运算RS2021/3/10223讲解：XX224用于查询的集合运算用于查询的集合运算：（1）投影：从所有字段中选取一部分字段及值进）投影：从所有字段中选取一部分字段及值进行操作，它是一种纵向操作。行操作，它是一种纵向操作。对于关系对于关系R内的内的域指定域指定称为投影运算。称为投影运算。S关系就是对关系就是对R关系指定关系指定A和和B两个域的结果两个域的结果ABCa32b01c21ABa3b0c2RS3.关系代数2021/3/10224讲解：XX225关系代数关系代数（2）选择）选择选择运算的关系是由关系选择运算的关系是由关系R中那些满足逻辑条件的元组所组成。中那些满足逻辑条件的元组所组成。S关系就是关系就是R关系中满足关系中满足A=a的结果的结果ABCa32b01a69c21RSABCa32a69有了投影和选择运算，我们对一个关系内的任意有了投影和选择运算，我们对一个关系内的任意行、列的数据都可以方便的找到。行、列的数据都可以方便的找到。2021/3/10225讲解：XX226笛卡尔积建立两个关系的连接，但得到的关系庞大且数据大量冗余。在实际应用中一般相互连接的关系往往须满足一些条件，所得到的结果也较为简单。u自然连接满足两个关系中有公共域，通过公共域的相自然连接满足两个关系中有公共域，通过公共域的相等值进行连接。等值进行连接。有三个关系R、S和TR关系关系n1行行,m1列列S关系关系n2行，行，m2列列T关系关系行数(n1或n2中行数多的一个)列数m1+m2（4）自然连接运算）自然连接运算2021/3/10226讲解：XX227u有三个关系R、S和T，由关系由关系R和和S通过运算得到关系通过运算得到关系T，则使用，则使用的运算为的运算为笛卡尔积笛卡尔积ABk1f1k2r1BCf13r13ABCk1f13k2r13RST自然连接自然连接ABk1f1k2r1BCf13r13ABBCk1f1f13k1f1r13k2r1f13k2r1r13RST2021/3/10227讲解：XX228在三个关系在三个关系R，S和和T如下：如下：ABm1n2BC1335ABCm13RST由关系R和S通过自然连接运算得到关系T。2021/3/10228讲解：XX第229页数据库设计与管理u数据库设计的两种方法：数据库设计的两种方法：（1）面向数据：以信息需求为主，兼顾处理需求；（2）面向过程：以处理需求为主，兼顾信息需求。u数据库的生命周期数据库的生命周期：n需求分析阶段需求分析阶段结构析方法和面向对象的方法数据字典是各类数据描述的集合，包括数据字典是各类数据描述的集合，包括5个部分：数据项、数据个部分：数据项、数据结构、数据流、数据存储、处理过程。结构、数据流、数据存储、处理过程。n概念设计阶段概念设计阶段分析数据内在语义关系。E-R模型n逻辑设计阶段逻辑设计阶段n物理设计阶段物理设计阶段n编码阶段编码阶段n测试阶段测试阶段n运行阶段运行阶段n进一步修改阶段进一步修改阶段2021/3/10229讲解：XX2304.4数据库设计与管理数据库应用系统数据库应用系统(DBAS)中中,核心问题是数据库设计。核心问题是数据库设计。需求分析需求分析概念设计概念设计逻辑设计逻辑设计物理设计物理设计编码编码测试测试运行运行进一步修改进一步修改分析客户的业务和数据处理需求分析客户的业务和数据处理需求;设计数据库的设计数据库的E-R模型图，确认需模型图，确认需求信息的正确和完整求信息的正确和完整;将将E-R图转换为多张表，进行逻辑图转换为多张表，进行逻辑设计设计,并应用数据库设计的三大范式并应用数据库设计的三大范式进行审核进行审核;数据库内模式数据库内模式包括存储结构包括存储结构和存取方法。和存取方法。重重点点记记8个个阶阶段段选择具体数据库进行物理实现，选择具体数据库进行物理实现，并编写代码实现前端应用并编写代码实现前端应用;2021/3/10230讲解：XX第231页数据库管理的内容数据库管理的内容（1）数据库的建立；）数据库的建立；（2）数据库的调整；）数据库的调整；（3）数据库的重组；）数据库的重组；（4）数据库安全性与完整性控制；）数据库安全性与完整性控制；（5）数据库的故障恢复；）数据库的故障恢复；（6）数据库监控。）数据库监控。2021/3/10231讲解：XX23206年年9月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题4)在数据库系统中,用户所见的数据模式为A)概念模式B)外模式C)内模式D)物理模式5)数据库设计的四个阶段是:需求分析、概念设计、逻辑设计和A)编码设计B)测试阶段C)运行阶段D)物理设计D4D52021/3/10232讲解：XX2336）设有如下三个表）设有如下三个表AmnBC13ABCm13n13下列操作中正确的是下列操作中正确的是A)T=RSB)T=R SC)T=RSD)=R/SRSTD6A)并并B)交交C)笛卡尔积笛卡尔积D)除除2021/3/10233讲解：XX2349)数据库技术的根本目标是要解决数据的A)存储问题B)共享问题C)安全问题D)保护文题二、填空题二、填空题3)一个关系表的行称为【3】D9T3元组元组2021/3/10234讲解：XX23507年年4月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题8）在下列关系运算中，不改变关系表中的属性个数但能减少）在下列关系运算中，不改变关系表中的属性个数但能减少元组个数为元组个数为A）并）并B）交）交C）投影）投影D）笛卡儿乘积）笛卡儿乘积9）在）在E-R图中，用来表示实体之间联系的图形是图中，用来表示实体之间联系的图形是A）矩形）矩形B）椭圆形）椭圆形C）菱形）菱形D）平行四边形）平行四边形D9D82021/3/10235讲解：XX23610）下列叙述中错误的是）下列叙述中错误的是A）在数据库系统中，数据的物理结构必须与逻辑）在数据库系统中，数据的物理结构必须与逻辑结构一致结构一致B）数据库技术的根本目标是要解决数据的共享问）数据库技术的根本目标是要解决数据的共享问题题C）数据库设计是指在已有数据库管理系统的基础）数据库设计是指在已有数据库管理系统的基础上建立数据库上建立数据库D）数据库系统需要操作系统的支持）数据库系统需要操作系统的支持D10二、填空题二、填空题3）在数据库系统中实现各种数据管理功能的核心软数据库系统中实现各种数据管理功能的核心软件称为件称为【3】。数据库管理系统或数据库管理系统或DBMST32021/3/10236讲解：XX23707年年9月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题9)下列叙述中正确的是下列叙述中正确的是A)数据库系统是一个独立的系统，不需要操作系统的支持B)数据库技术的根本目标是要解决数据的共享问题C)数据库管理系统就是数据库系统D)以上三种说法都不对D92021/3/10237讲解：XX23810)下列叙述中正确的是下列叙述中正确的是A)为了建立一个关系，首先要构造数据的逻辑关系B)表示关系的二维表中各元组的每一个分量还可以分成若干数据项C)一个关系的属性名表称为关系模式D)一个关系可以包括多个二维表二、填空题二、填空题5)在在E-R图中，矩形表示图中，矩形表示5。D10T5实体集实体集2021/3/10238讲解：XX23908年年4月月全国计算机等级考试二级笔试试卷全国计算机等级考试二级笔试试卷一、单选题一、单选题8)在数据库设计中，将在数据库设计中，将E-R图转换成关系数据模型图转换成关系数据模型的过程属于的过程属于A)需求分析阶段B)概念设计阶段C)逻辑设计阶段D)物理设计阶段D82021/3/10239讲解：XX240(9)有三个关系有三个关系R、S和和T如下：如下：由关系由关系R和和S通过运算得到关系通过运算得到关系T，则所使用的运算为，则所使用的运算为A并并B自然连接自然连接C笛卡尔积笛卡尔积D.交交D92021/3/10240讲解：XX24110)设有表示学生选课的三张表，学生S（学号，姓名，性别，年龄，身份证号)，课程C（课号，课名)，选课SC（学号，课号，成绩)，则表SC的关键字（键或码)为A)课号，成绩B)学号，成绩C)学号，课号D)学号，姓名，成绩二、填空题二、填空题4)在关系数据库中，用来表示实体之间联系的是_。5)在数据库管理系统提供的数据定义语言、数据操纵语言和数据控制语言中，_负责数据的模式定义与数据的物理存取构建。D10T4T5关系关系数据定义语言数据定义语言2021/3/10241讲解：XX24208年年9月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题8)一间宿舍可住多个学生，则实体宿舍和学生之间的联系是A)一对一B)一对多C)多对一D)多对多9)在数据管理技术发展的三个阶段中，数据共享最好的是A)人工管理阶段B)文件系统阶段C)数据库系统阶段D)三个阶段相同D8D92021/3/10242讲解：XX24310)在三个关系在三个关系R，S和和T如下：如下：由关系R和S通过运算得到关系T,则所使用的运算为A)笛卡尔积B)交C)并D)自然连接二、填空题二、填空题4)数据库设计包括概念设计、数据库设计包括概念设计、【】、和物理设计。、和物理设计。5)在二维表中，元组的在二维表中，元组的【】不能再分成更小的数据项。不能再分成更小的数据项。ABm1n2BC1335ABCm13RSTD10T4T5逻辑设计逻辑设计分量分量2021/3/10243讲解：XX24409年年3月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题8)数据库应用系统中的核心问题是数据库应用系统中的核心问题是A)数据库设计数据库设计B)数据库系统设计数据库系统设计C)数据库维护数据库维护D)数据库管理员培训数据库管理员培训9)有两个关系有两个关系R,S如下：如下：由关系由关系R通过运算得到关系通过运算得到关系S，则所使用的运算是，则所使用的运算是A)选择选择B)投影投影C)插入插入D)连连接接ABCa32b01c21ABa3b0c2RSD8D92021/3/10244讲解：XX24510)将E-R图转换为关系模式时，实体和联系都可以表示为A)属性B)键C)关系D)域二、填空题二、填空题4)数据库系统的核心是【4】。5)在E-R图中，图形包括矩形框，菱形框，椭圆框，其中表示实体联系的是【5】框。D10T4T5数据库管理系统数据库管理系统菱形菱形2021/3/10245讲解：XX24609年年9月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题8)数据库管理系统是数据库管理系统是A）操作系统的一部分）操作系统的一部分B)在操作系统支持下的系统软件在操作系统支持下的系统软件C)一种编译系统一种编译系统D)一种操作系统一种操作系统10)有三个关系有三个关系R，S和和T如下：如下：其中关系其中关系T由关系由关系R和和S通过某种操作得到，该操作为通过某种操作得到，该操作为A)选择选择B)投影投影C)交交D)并并ABCa12b21c31RSD8D9ABCd32ABCa12b21c31d32T2021/3/10246讲解：XX2479）在E-R图中，用来表示实体联系的图形是A)椭圆图B)矩形C)菱形D)三角形二、填空题二、填空题（4）在数据库技术中，实体集之间的联系可以是一对一或一对多或多对多的，那么“学生”和“可选课程”的联系为【4】。（5）人员基本信息一般包括：身份证号，姓名，性别，年龄等。其中可以作为主关键字的是【5】。D10T4T5多对多多对多身份证号身份证号2021/3/10247讲解：XX248(7)(7)数据库管理系统中负责数据模式定义的语言是数据库管理系统中负责数据模式定义的语言是A)A)数据定义语言数据定义语言B)B)数据管理语言数据管理语言C)C)数据操纵语言数据操纵语言D)D)数据控制语言数据控制语言 (8)(8)在学生管理的关系数据库中，存取一个学生信息的数据单位是在学生管理的关系数据库中，存取一个学生信息的数据单位是A)A)文件文件B)B)数据库数据库C)C)字段字段D)D)记录记录 (9)(9)数据库设计中，用数据库设计中，用E-RE-R图来描述信息结构但不涉及信息在计算机中图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的的表示，它属于数据库设计的A)A)需求分析阶段需求分析阶段B)B)逻辑设计一阶段逻辑设计一阶段C)C)概念设计阶段概念设计阶段D)D)物理设计阶段物理设计阶段T9T7T8CAD2010年年3月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷2021/3/10248讲解：XX24910)有两个关系有两个关系R,T如下：如下：则由关系则由关系R得到关系得到关系T的操作是的操作是A)选择选择B)投影投影C)交交D)并并(5)有一个学生选课的关系，其中学生的关系模式为：学生有一个学生选课的关系，其中学生的关系模式为：学生(学号，姓名，学号，姓名，班级，年龄班级，年龄)，课程的关系模式为：课程，课程的关系模式为：课程(课号，课程名，学时课号，课程名，学时)，其中两个关，其中两个关系模式的键分别是学号和课号，则关系模式选课可定义为：选课系模式的键分别是学号和课号，则关系模式选课可定义为：选课(学号，学号，【5】，成绩，成绩)。ABCa12b22c32d32RSD10D5课号AABCc32d322021/3/10249讲解：XXu数据库管理系统DBMS中用来定义模式、内模式和外模式的语言为A)CB)BasicC)DDL D)DMLcu下列有关数据库的描述，正确的是A)数据库是一个DBF文件B)数据库是一个关系C)数据库是一个结构化的数据集合D)数据库是一组文件u下列有关数据库的描述，正确的是A)数据处理是将信息转化为数据的过程B)数据的物理独立性是指当数据的逻辑结构改变时，数据的存储结构不变C)关系中的每一列称为元组，一个元组就是一个字段D)如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键字，则称其为本关系的外关键字2021/3/10250讲解：XXu应用数据库的主要目的是应用数据库的主要目的是A)解决数据保密问题解决数据保密问题B)解决数据完整性问题解决数据完整性问题C)解决数据共享问题解决数据共享问题D)解决数据量大的问题解决数据量大的问题u在数据库设计中，将在数据库设计中，将E-R图转换成关系数据模型的过程属于图转换成关系数据模型的过程属于A)需求分析阶段需求分析阶段B)逻辑设计阶段逻辑设计阶段C)概念设计阶段概念设计阶段D)物理设计阶段物理设计阶段u在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是数据库系统阶段。其中数据独立性最高的阶段是)数据库系统数据库系统)文件系统文件系统)人工管理人工管理)数据项管理数据项管理u下述关于数据库系统的叙述中正确的是下述关于数据库系统的叙述中正确的是)数据库系统减少了数据冗余数据库系统减少了数据冗余)数据库系统避免了一切冗余数据库系统避免了一切冗余)数据库系统中数据的一致性是指数据类型一致数据库系统中数据的一致性是指数据类型一致)数据库系统比文件系统能管理更多的数据数据库系统比文件系统能管理更多的数据2021/3/10251讲解：XXu索引属于索引属于A)模式模式B)内模式内模式C)外模式外模式D)概念模式概念模式u数据库系统的核心是数据库系统的核心是A)数据库数据库B)数据库管理系统数据库管理系统C)模拟模型模拟模型D)软件工程软件工程u分布式数据库系统不具有的特点是分布式数据库系统不具有的特点是A)数据分布性和逻辑整体性数据分布性和逻辑整体性B)位置透明性和复制透明性位置透明性和复制透明性C)分布性分布性D)数据冗余数据冗余u关系表中的每一横行称为一个关系表中的每一横行称为一个)元组元组)字段字段)属性属性)码码u下列数据模型中，具有坚实理论基础的是下列数据模型中，具有坚实理论基础的是A)层次模型层次模型B)网状模型网状模型C)关系模型关系模型D)以上以上3个都是个都是2021/3/10252讲解：XXu下列下列SQL语句中，用于修改表结构的是语句中，用于修改表结构的是A)ALTERB)CREATEC)UPDATED)INSERTu数据库、数据库系统和数据库管理系统之间的关系是数据库、数据库系统和数据库管理系统之间的关系是A)数据库包括数据库系统和数据库管理系统数据库包括数据库系统和数据库管理系统B)数据库系统包括数据库和数据库管理系统数据库系统包括数据库和数据库管理系统C)数据库管理系统包括数据库和数据库系统数据库管理系统包括数据库和数据库系统D)3者没有明显的包含关系者没有明显的包含关系u关系模型允许定义关系模型允许定义3类数据约束，下列不属于数据约束的是类数据约束，下列不属于数据约束的是A)实体完整性约束实体完整性约束B)参照完整性约束参照完整性约束C)域完整性约束域完整性约束D)用户自定义的完整性约束用户自定义的完整性约束2021/3/10253讲解：XXuNULL是指是指A)0B)空格空格C)未知的值或无任何值未知的值或无任何值D)空字符串空字符串u数据库的故障恢复一般是由数据库的故障恢复一般是由A)数据流图完成的数据流图完成的B)数据字典完成的数据字典完成的C)DBA完成的完成的D)PAD图完成的图完成的u下列说法中，不属于数据模型所描述的内容的是下列说法中，不属于数据模型所描述的内容的是A)数据结构数据结构B)数据操作数据操作C)数据查询数据查询D)数据约束数据约束2021/3/10254讲解：XXu在数据管理技术发展过程中，文件系统与数据库系统的主要区别是在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有数据库系统具有A)特定的数据模型特定的数据模型B)数据无冗余数据无冗余C)数据可共享数据可共享D)专门的数据管理软件专门的数据管理软件u数据库设计包括两个方面的设计内容，它们是数据库设计包括两个方面的设计内容，它们是A)概念设计和逻辑设计概念设计和逻辑设计B)模式设计和内模式设计模式设计和内模式设计C)内模式设计和物理设计内模式设计和物理设计D)结构特性设计和行为特性设计结构特性设计和行为特性设计u实体是信息世界中广泛使用的一个术语，它用于表示实体是信息世界中广泛使用的一个术语，它用于表示A)有生命的事物有生命的事物B)无生命的事物无生命的事物C)实际存在的事物实际存在的事物D)一切事物一切事物2021/3/10255讲解：XXu一个关系中属性个数为一个关系中属性个数为1时，称此关系为时，称此关系为A)对应关系对应关系B)单一关系单一关系C)一元关系一元关系D)二元关系二元关系u为用户与数据库系统提供接口的语言是为用户与数据库系统提供接口的语言是A)高级语言高级语言B)数据描述语言数据描述语言(DDL)C)数据操纵语言数据操纵语言(DML)D)汇编语言汇编语言u相对于数据库系统，文件系统的主要缺陷有数据关联差、数据不相对于数据库系统，文件系统的主要缺陷有数据关联差、数据不一致性和一致性和A)可重用性差可重用性差B)安全性差安全性差C)非持久性非持久性D)冗余性冗余性2021/3/10256讲解：XXu下列关系模型中，能使经运算后得到的新关系中属性个数多于原下列关系模型中，能使经运算后得到的新关系中属性个数多于原来关系中属性个数的是来关系中属性个数的是A)选择选择B)连接连接C)投影投影D)并并u下列叙述中，正确的是下列叙述中，正确的是A)用用E-R图能够表示实体集间一对一的联系、一对多的联系和多对多的图能够表示实体集间一对一的联系、一对多的联系和多对多的联系联系B)用用E-R图只能表示实体集之间一对一的联系图只能表示实体集之间一对一的联系C)用用E-R图只能表示实体集之间一对多的联系图只能表示实体集之间一对多的联系D)用用E-R图表示的概念数据模型只能转换为关系数据模型图表示的概念数据模型只能转换为关系数据模型u“年龄在年龄在18-25之间之间”这种约束是属于数据库当中的这种约束是属于数据库当中的A)原子性措施原子性措施B)一致性措施一致性措施C)完整性措施完整性措施D)安全性措施安全性措施2021/3/10257讲解：XXu下列叙述中，不属于数据库系统的是下列叙述中，不属于数据库系统的是A)数据库数据库B)数据库管理系统数据库管理系统C)数据库管理员数据库管理员D)数据库应用系统数据库应用系统u数据库系统的核心是数据库系统的核心是A)数据库数据库B)数据库管理系统数据库管理系统C)数据模型数据模型 D)软件工具软件工具u视图设计一般有视图设计一般有3种设计次序，下列不属于视图设计的种设计次序，下列不属于视图设计的是是A)自顶向下自顶向下B)由外向内由外向内C)由内向外由内向外D)自底向上自底向上2021/3/10258讲解：XXu下列下列4项中说法不正确的是项中说法不正确的是A)数据库减少了数据冗余数据库减少了数据冗余B)数据库中的数据可以共享数据库中的数据可以共享C)数据库避免了一切数据的重复数据库避免了一切数据的重复D)数据库具有较高的数据独立性数据库具有较高的数据独立性u下列下列4项中，必须进行查询优化的是项中，必须进行查询优化的是A)关系数据库关系数据库B)网状数据库网状数据库C)层次数据库层次数据库D)非关系模型非关系模型u最常用的一种基本数据模型是关系数据模型，它的表示最常用的一种基本数据模型是关系数据模型，它的表示应采用应采用A)树树B)网络网络C)图图D)二维表二维表2021/3/10259讲解：XXu公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，从部门到职员的联系类型是可以有多名职员，从部门到职员的联系类型是A)多对多多对多B)一对一一对一C)多对一多对一D)一对多一对多u下列关系运算的叙述中，正确的是下列关系运算的叙述中，正确的是A)投影、选择、连接是从二维表行的方向进行的运算投影、选择、连接是从二维表行的方向进行的运算B)并、交、差是从二维表的列的方向来进行运算并、交、差是从二维表的列的方向来进行运算C)投影、选择、连接是从二维表列的方向进行的运算投影、选择、连接是从二维表列的方向进行的运算D)以上以上3种说法都不对种说法都不对u关系数据库管理系统应能实现的专门的关系运算包括关系数据库管理系统应能实现的专门的关系运算包括A)排序、索引、统计排序、索引、统计 B)选择、投影、连接选择、投影、连接C)关联、更新、排序关联、更新、排序 D)显示、打印、制表显示、打印、制表2021/3/10260讲解：XXu用树形结构来表示实体之间联系的模型称为用树形结构来表示实体之间联系的模型称为A）关系模型）关系模型B）层次模型）层次模型C）网状模型）网状模型D）关系模型）关系模型u关系表中的每一横行称为一个关系表中的每一横行称为一个A)元组元组B)字段字段C)属性属性D)码码u按条件按条件f对关系进行选择，其关系运算表示式是对关系进行选择，其关系运算表示式是A)RRB)RRC)f(R)D)f(R)f2021/3/10261讲解：XXu在关系数据库中，用来表示实体之间联系的是在关系数据库中，用来表示实体之间联系的是A)树结构树结构B)网结构网结构C)线性表线性表D)二维表二维表u数据库设计包括两个方面的设计内容，它们是数据库设计包括两个方面的设计内容，它们是A)概念设计和逻辑设计概念设计和逻辑设计B)模式设计和内模式设计模式设计和内模式设计C)内模式设计和物理设计内模式设计和物理设计D)结构特性设计和行为特性设计结构特性设计和行为特性设计u将将-R图转换到关系模式时，实体与联系都可以表示成图转换到关系模式时，实体与联系都可以表示成A)属性属性B)关系关系C)键键D)域域2021/3/10262讲解：XXu数据库管理系统常见的数据模型有层次模型、网状模型数据库管理系统常见的数据模型有层次模型、网状模型和和【5】3种。种。u一个项目具有一个项目主管，一个项目主管可管理多个一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体项目，则实体“项目主管项目主管”与实体与实体“项目项目”的联系属于的联系属于【4】的联系。的联系。u数据库设计分为以下数据库设计分为以下6个设计阶段：需求分析阶段、个设计阶段：需求分析阶段、【5】、逻辑设计阶段、物理设计阶段、实施阶段、运行和、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。维护阶段。关系模型关系模型1：n概念设计概念设计2021/3/10263讲解：XXu关系操作的特点是关系操作的特点是【5】操作。操作。u数据模型按不同应用层次分成数据模型按不同应用层次分成3种类型，它们是概念数种类型，它们是概念数据模型、据模型、【5】和物理数据模型。和物理数据模型。u当数据的物理结构当数据的物理结构(存储结构、存取方式等存储结构、存取方式等)改变时，不改变时，不影响数据库的逻辑结构，从而不致引起应用程序的变化，影响数据库的逻辑结构，从而不致引起应用程序的变化，这是指数据的这是指数据的【5】。集合集合逻辑数据模型逻辑数据模型物理独立性物理独立性2021/3/10264讲解：XXu【4】是数据库设计的核心。是数据库设计的核心。u在关系模型中，把数据看成一个二维表，每一个二维表在关系模型中，把数据看成一个二维表，每一个二维表称为一个称为一个【5】。u关系数据库的关系演算语言是以关系数据库的关系演算语言是以【5】为基础的为基础的DML语语言。言。u关键字关键字ASC和和DESC分别表示分别表示【5】的含义。的含义。数据库管理系统（数据库管理系统（DBMS）关系关系谓词演算谓词演算升序和降序升序和降序2021/3/10265讲解：XXu数据库系统阶段的数据具有较高独立性，数据独立性包数据库系统阶段的数据具有较高独立性，数据独立性包括物理独立性和括物理独立性和【4】两个含义。两个含义。u数据库保护分为：安全性控制数据库保护分为：安全性控制、【5】、并发性控制和、并发性控制和数据的恢复。数据的恢复。u【5】是从二维表列的方向进行的运算。是从二维表列的方向进行的运算。u由关系数据库系统支持的完整性约束是指由关系数据库系统支持的完整性约束是指【5】和参照和参照完整性。完整性。逻辑独立性逻辑独立性完整性控制完整性控制投影投影实体完整性实体完整性2021/3/10266讲解：XXu数据库恢复是将数据库从数据库恢复是将数据库从【4】状态恢复到某一已知的正确状态。状态恢复到某一已知的正确状态。u实体之间的联系可以归结为一对一联系、一对多实体之间的联系可以归结为一对一联系、一对多(或多对多或多对多)的联系与多对的联系与多对多联系。如果一个学校有许多教师，而一个教师只归属于一个学校，则实多联系。如果一个学校有许多教师，而一个教师只归属于一个学校，则实体集学校与实体集教师之间的联系属于体集学校与实体集教师之间的联系属于【5】的联系。的联系。错误错误1:nu数据独立性分逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑数据独立性分逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为_。u数据库系统中实现各种数据管理功能的核心软件称为数据库系统中实现各种数据管理功能的核心软件称为_。u关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、_和自定义完整性。和自定义完整性。u在关系模型中，把数据看成一个二维表，每个二维表称为一个在关系模型中，把数据看成一个二维表，每个二维表称为一个_。物理独立性物理独立性DBMS参照完整性参照完整性关系关系2021/3/10267讲解：XX谢谢大家！2021/3/10268讲解：XX感谢您的阅读收藏，谢谢！2021/3/10269