计算机二级公共基础知识课件

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

1、计算机等级考试计算机等级考试公共基础知识公共基础知识2012版（版（HNU）计算机二级公共基础知识课件计算机二级考试公共基础知识计算机二级考试公共基础知识大纲q数据结构与算法数据结构与算法q程序设计基础程序设计基础q软件工程基础软件工程基础q数据库设计基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。2计算机二级公共基础知识课件计算机二级考试公共基础知识试卷分析计算机二级考试公共基础知识试卷分析章节章节考试时间考试时间数据结构数据结构与算法与算法程序设程序设计基础计基础软件工软件工程基础程基础数据库设

2、数据库设计基础计基础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分3计算机二级公共基础知识课件算法算法算法的基算法的基本概念本概念2.2.算法复杂算法复杂度的概念和度的概念和意义意义一、基本数据结构与算法一、基本数据结构与算法数据结构数据结构数据结构的概念数据结构的概念线性表线性表栈和队列栈和队列树与二叉树树与二叉树查找技术查找技术排序技术排序技术对于等级考试，这个部分的考核对于等级考试，这个部分的考核重

3、点主要重点主要在在算法和数据结构的基本概算法和数据结构的基本概念念、二叉树二叉树(遍历、结点），遍历、结点），还有还有排序和查找排序和查找考试中也经常会涉及到。考试中也经常会涉及到。4计算机二级公共基础知识课件算法的定义算法的定义u对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是程序设计的核心算法是程序设计的核心算法的基本概念算法的基本概念 算法是在有限步骤内求解某一问题所使用的一组算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过定义明确的规则。通俗点说，就是计算机解题的过程程( (计算的方法计算的方法) )。在这个过程中，无

4、论是形成解题。在这个过程中，无论是形成解题思路思路( (推理实现的算法推理实现的算法) )还是编写程序还是编写程序( (操作实现的算操作实现的算法法) )，都是在实施某种算法。，都是在实施某种算法。例：例：n个数从大到小进行排序。个数从大到小进行排序。有多种排序方法有多种排序方法，常用的有冒泡排序、选择排序等。，常用的有冒泡排序、选择排序等。5计算机二级公共基础知识课件2.算法的基本特征算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：n有穷性有穷性n确定性确定性n输入输入n输出输出n可行性可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的

5、定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成6计算机二级公共基础知识课件u算法与计算机程序算法与计算机程序算法算法_是一组逻辑步骤是一组逻辑步骤程序程序用计算机语言描述的算法用计算机语言描述的算法3.3.算法的表示算法的表示算法的表示算法的表示INPUTrS=3.14*r*rPTINTS开始开始输入输入R RS=3.14*R*R输出输出S S结束结束问题：输入园的半径，计算园的面积一个算法的表示

6、需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法传统的算法-图形法，如图形法，如“流程图流程图”和和N-S图图目前常用的方法目前常用的方法-使用伪码描述算法。使用伪码描述算法。7计算机二级公共基础知识课件冒泡排序的方法：冒泡排序的方法：1.扫描整个线性表，逐次对扫描整个线性表，逐次对相邻的两个元素进行比较，相邻的两个元素进行比较，若为逆序，则交换；第一趟若为逆序，则交换；第一趟扫描的结果使最大的元素排扫描的结果使最大的元素排到表的最后到表的最后；2.除最后一个元素，对剩余除最后一个元素，对剩余的元素重复上述过程，将次的元素重复上述过程，将次大的数排到表的倒数第二个大的数排到

7、表的倒数第二个位置；位置；3.重复上述过程；重复上述过程；对于长度为对于长度为n的线性表，冒泡的线性表，冒泡排序需要对表扫描排序需要对表扫描n-1遍。遍。算法举例：算法举例：n个数排序个数排序8计算机二级公共基础知识课件4.算法的两个基本要素：算法的两个基本要素：基本运算和操作基本运算和操作基本运算和操作基本运算和操作n算术运算算术运算n关系运算关系运算n逻辑运算逻辑运算n数据传输数据传输控制结构控制结构控制结构控制结构 n顺序顺序n选择选择n循环循环u一是对数据对象的运算和操作；u二是算法的控制结构。u算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法9计算机二级公共基础知识

8、课件5. 算法评价算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：n时间复杂度：执行这个算法所需要的时间复杂度：执行这个算法所需要的计算工作量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n空间复杂度：执行这个算法所需要的空间复杂度：执行这个算法所需要的内存空间内存空间算法在算法在执行行过程中程中临时占用的存占用的存储空空间时间复杂度时间复杂度它大致等于计算机它大致等于计算机执行一种简单操作所需的平均时间执行一种简单操作所需的平均时间与

9、算法中与算法中进行进行简单操作的次数的乘积简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用存储算法本身所占用的存储空间的存储空间、算法中的输入输出数据所占用的存储空间算法中的输入输出数据所占用的存储空间和和算法在运行过程中算法在运行过程中临时占用的存储空间临时占用的存储空间这三个部分这三个部分10计算机二级公共基础知识课件一、算法一、算法uu对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机

10、方法，程序的编制不可算法不等于程序，也不等计算机方法，程序的编制不可算法不等于程序，也不等计算机方法，程序的编制不可算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。能优于算法的设计。能优于算法的设计。能优于算法的设计。u算法评价算法评价：n时间复杂度：执行这个算法所需要的计算工作量时间复杂度：执行这个算法所需要的计算工作量n空间复杂度：执行这个算法所需要的内存空间空间复杂度：执行这个算法所需要的内存空间11计算机二级公共基础知识课件(1)在在计算机中，算法是指算机中，算法是指_。A.查询方法方法B.加工方法加工方法C.解解题方案的准确而完整的描述方案的准确而完整的描述D.排序

11、方法排序方法(2)下列叙述中正确的是下列叙述中正确的是（07年年4月月）A)算法的效率只与算法的效率只与问题的的规模有关，而与数据的存模有关，而与数据的存储结构无关构无关B)算法的算法的时间复复杂度是指度是指执行算法所需要的行算法所需要的计算工作量算工作量C)数据的数据的逻辑结构与存构与存储结构是一一构是一一对应的的D)算法的算法的时间复复杂度与空度与空间复复杂度一定相关度一定相关(3)算法的有算法的有穷性是指性是指(08年年4月月)A）算法程序的运行）算法程序的运行时间是有限的是有限的B）算法程序所）算法程序所处理的数据量是有限的理的数据量是有限的C）算法程序的）算法程序的长度是有限的度是有

12、限的D）算法只能被有限的用）算法只能被有限的用户使用使用(c)(B)算法习题:(A)12计算机二级公共基础知识课件(4)算法的算法的时问复复杂度是指度是指(2010年年3月月)A)算法的算法的执行行时间B)算法所算法所处理的数据量理的数据量C)算法程序中的算法程序中的语句或指令条数句或指令条数D)算法在算法在执行行过程中所需要的基本运算次数程中所需要的基本运算次数(5)算法的空算法的空间复复杂度是指度是指(09年年9月月)A）算法在）算法在执行行过程中所需要的程中所需要的计算机存算机存储空空间B）算法所）算法所处理的数据量理的数据量C）算法程序中的）算法程序中的语句或指令条数句或指令条数D）算

13、法在）算法在执行行过程中所需要的程中所需要的临时工作工作单元数元数(6)下列叙述中正确的是下列叙述中正确的是(06年年9月月)A）一个算法的空）一个算法的空间复复杂度大，度大，则其其时间复复杂度也必定大度也必定大B）一个算法的空）一个算法的空间复复杂度大，度大，则其其时间复复杂度必定小度必定小C）一个算法的）一个算法的时间复复杂度大，度大，则其空其空间复复杂度必定小度必定小D）上述三种）上述三种说法都不法都不对(D)计算工作量(A)(D)13计算机二级公共基础知识课件计算机在进行数据处理时，实际需要处理的数据元素一般有很计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据

14、元素都需要存放在计算机中，因此，大量的多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，省计算机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题。二、数据结构二、数据结构程序程序=算法算法+数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据

15、元素集合中，各个数据一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。14计算机二级公共基础知识课件二二.数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。数据结构数据结构是研究数据和数据之间关系的一门是研究数据和数据之间关系的一门学科，它包括三个方面。学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；辑关系

16、，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。15计算机二级公共基础知识课件u1. 逻辑结构逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：数据的逻辑结构包含：（1）表示数据元素的信息；）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。例：例：1.一年四季的数据结构一年四季的数据结构B

17、=(D,R)D=春，夏，秋，冬春，夏，秋，冬R=(春，夏春，夏),(夏，秋夏，秋),(秋，冬秋，冬)2.家庭成员的数据结构家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿父亲，儿子，女儿R=(父亲，儿子父亲，儿子),(父亲，女儿父亲，女儿)春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子女儿16计算机二级公共基础知识课件u常见的常见的逻辑结构逻辑结构有：有：线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。线性结构线性结构树形结构树形结构图图形形结结构构u线性结构线性结构结构中的每个元素之间存在一个对一个的关系；结构中的每个元素之间存在一个对一个的关系；u树形结构树形结构结构

18、中的每个元素之间存在一个对多个的关系；结构中的每个元素之间存在一个对多个的关系；u图形结构或网状结构图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。结构中的每个元素之间存在多个对多个的关系。其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可以。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。用二元关系表示，也可以直观地用图形来表示。17计算机二级公共基础知识课件u2.存储结构（物理结构存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算计算机在实际进行数据处理时，被处理的各数据元素总是被存放在

19、计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。们的逻辑关系不一定是相同的，而且一般也不可能相同。如：如：一年四季家庭成员计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见的存储结构有：n顺序存储结构顺序存储结构n链式存储结构链式存储结构n索引存储结构存储结构只抽象地反映数据元素之间的关只抽象地反映数据元素之间的关系的结构，而不管其存储方式的系的结构，而不管其存储方式的数据结构称

20、为逻辑结构。数据结构称为逻辑结构。一种一种数据结构可以根据需要表示数据结构可以根据需要表示成一种或多种存储结构成一种或多种存储结构。18计算机二级公共基础知识课件u3.数据的运算数据的运算n检索检索n插入插入n删除删除n更新更新n排序排序通常，一个数据结构中的元素结点可能是动态变化的。根通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解

21、、复制和外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。修改。在对数据结构的处理过程中，不仅数据结构中结点的个数在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。变化。如：无序表变有序表数据结构是研究数据和数据之间数据结构是研究数据和数据之间关系的一门学科，研究以下三方面关系的一门学科，研究以下三方面内容：内容：n数据的逻辑结构数据的逻辑结构n数据的存储结构数据的存储结构n数据的运算数据的运算19计算机二级公共基础知识课件常见的数据结构1.线性表2.栈和队列3.树20计

22、算机二级公共基础知识课件 线性表（线性表（线性表（线性表（LinearListLinearList）线性表是由线性表是由n（n0）个数据元素）个数据元素a1，a2，ai，an组成的一个有限序列。组成的一个有限序列。简单的线性表简单的线性表简单的线性表简单的线性表春春夏夏秋秋冬冬复杂的线性表复杂的线性表复杂的线性表复杂的线性表记录记录102011001张三张三男男记录记录202011003李四李四女女记录记录3记录记录421计算机二级公共基础知识课件线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构顺序存储结构把顺序存储结构把逻辑上相邻逻辑上相邻的的数据元素存储在数

23、据元素存储在物理上相邻物理上相邻的存储的存储单元里，顺序存储结构单元里，顺序存储结构只存储结点只存储结点的值的值，不存储结点间的关系，结点，不存储结点间的关系，结点间的关系由存储单元的邻接关系来间的关系由存储单元的邻接关系来体现。体现。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链式

24、存储结构链式存储结构22计算机二级公共基础知识课件u顺序表的插入运算顺序表的插入运算u顺序表的删除运算顺序表的删除运算顺序表的插入和删除运算顺序表的插入和删除运算顺序表的插入和删除运算顺序表的插入和删除运算在线性表顺序存储情况下，要插入或删除一个元在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。23计算机

25、二级公共基础知识课件线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构u线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。u链式存储结构不要求逻辑上相邻的数据元素物理位链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。各数据元素的先后关系是由各结点的指针域指示。u链式存储结构的每一个存储结点不仅存储结点的值，链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：而且存储结点之间的关系：数据域数据域指针域

26、指针域24计算机二级公共基础知识课件应用举例应用举例应用举例应用举例线性链表的存储结构线性链表的存储结构线性链表的存储结构线性链表的存储结构设线性表为设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态线性链表线性链表的物理状态的物理状态1 a12 a23 a34 a45 a567线性表的线性表的线性表的线性表的顺顺顺顺序存储序存储序存储序存储结构结构结构结构注意:123此类编号不代表所在的地址单元的地址编码25计算机二级公共基础知识课件u单链表的插入运算单链表的插

27、入运算u单链表的删除运算单链表的删除运算线性链表的插入和删除运算线性链表的插入和删除运算线性链表的插入和删除运算线性链表的插入和删除运算采用链式存储结构，存储空间开销较大，但是进行插采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。入和删除运算不会造成大量元素的移动。循环链表是加一种形式的链式存储结构。它的特点是循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。表中最后一个结点的指针域指向头结点。a1a2a5a3a4HEAD31951026计算机二级公共基础知识课件双向链表的存储结构提问：单向链表的缺点是什么？提示：如何寻找结点的

28、直接前趋。双向链表可以克服单链表的单向性的缺点。在双向链表的结点中有两个指针域，其一指向在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。直接后继，另一指向直接前趋。HEAD31510a2a3a4a1双向循环链表双向循环链表27计算机二级公共基础知识课件线性表的存储结构有两种线性表的存储结构有两种线性表的存储结构有两种线性表的存储结构有两种u顺序存储结构顺序存储结构注意：注意：n数据元素在计算机数据元素在计算机存储空间中的位置关存储空间中的位置关系与它们的逻辑关系系与它们的逻辑关系不一定是相同的。不一定是相同的。n一个逻辑数据结构一个逻辑数据结构可以有多种存储结构，可以有多种

29、存储结构，且不同的存储结构影且不同的存储结构影响数据处理的效率响数据处理的效率。1a2923a1145a4106789a3510a50HEAD31 a12 a23 a34 a45 a567u链式存储结构链式存储结构线性表线性表:a1，a2，a3，a4，a528计算机二级公共基础知识课件2.栈和队列栈和队列栈和队列都是特殊的线性表。栈和队列都是特殊的线性表。 uu 栈（栈（栈（栈（StackStack）及其基本运算）及其基本运算）及其基本运算）及其基本运算uu 队列（队列（队列（队列（QueueQueue）及其基本运算）及其基本运算）及其基本运算）及其基本运算uu 循环队列及其基本运算循环队列及

30、其基本运算循环队列及其基本运算循环队列及其基本运算29计算机二级公共基础知识课件栈（栈（栈（栈（StackStack）是一种特殊的是一种特殊的线性表线性表。其特点是插入和删。其特点是插入和删除运算都只能在线性表的一端进行。除运算都只能在线性表的一端进行。u栈是按照栈是按照“先进后出先进后出先进后出先进后出”或或“后进先出后进先出后进先出后进先出”的原则组织数的原则组织数据的线性表。据的线性表。u栈的物理存储结构可以用顺序结构，也可以用链表结栈的物理存储结构可以用顺序结构，也可以用链表结构。构。u下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。n顺序栈

31、的进栈和出栈运算顺序栈的进栈和出栈运算n栈的基本运算有三种：入栈、退栈和读栈顶元素栈的基本运算有三种：入栈、退栈和读栈顶元素在顺序栈中插入和删除运算不需要在顺序栈中插入和删除运算不需要移动表中其他数据元素移动表中其他数据元素。30计算机二级公共基础知识课件队列（队列（队列（队列（QueueQueue）是一种特殊的线性表。其特点是所有的是一种特殊的线性表。其特点是所有的插入都在表的一端插入都在表的一端进行，所有的进行，所有的删除删除运算都在表的运算都在表的另另一端一端进行。进行。u队列是按照队列是按照“先进先出先进先出先进先出先进先出”或或“后进后出后进后出后进后出后进后出”的原则组织的原则组织

32、数据的线性表。数据的线性表。u队列的物理存储结构可以用顺序结构，也可以用链式队列的物理存储结构可以用顺序结构，也可以用链式结构。结构。u顺序队列的运算顺序队列的运算栈有三种操作：栈有三种操作：入栈出栈读栈顶元素入栈出栈读栈顶元素队列有三种操作：入队出队读队首元素队列有三种操作：入队出队读队首元素例：有入栈元素序列：例：有入栈元素序列：ABCD，求可能的出栈序列，求可能的出栈序列如是队列又是什么情况呢？如是队列又是什么情况呢？31计算机二级公共基础知识课件uu 循环队列循环队列循环队列循环队列 把队列的存储空间在逻辑上看作一个环，当把队列的存储空间在逻辑上看作一个环，当R指向存指向存储空间的末端

33、后，就把它重新置于始端。储空间的末端后，就把它重新置于始端。u循环队列的运算循环队列的运算队列中进行插入的一端称做队尾队列中进行插入的一端称做队尾(rear),进行删除的一进行删除的一端称做队首端称做队首(front)。习题：数据结构分为逻辑结构和存储结构，循环队习题：数据结构分为逻辑结构和存储结构，循环队列属于列属于【】结构。（结构。（2005年年9月）月）答案：存储结构。答案：存储结构。32计算机二级公共基础知识课件常见数据结构的逻辑结构常见数据结构的逻辑结构u线性表线性表线性结构u栈栈是特殊的线性表u队列队列也是一种操作受限的特殊的线性表u树树（树型结构）（树型结构）是一种重要的非线形数

34、据结构33计算机二级公共基础知识课件数据存储结构方面的考题数据存储结构方面的考题1：数据的存：数据的存储结构是指构是指（2005年年4月）月）A)存存储在外存中的数据在外存中的数据B)数据所占的存数据所占的存储空空间量量C)数据在数据在计算机中的算机中的顺序存序存储方式方式D)数据的数据的逻辑结构在构在计算机中的表示算机中的表示2.下列叙述中正确的是下列叙述中正确的是（2009年年3月）月）A）栈是是“先先进先出先出”的的线性表性表B）队列是列是“先先进后出后出”的的线性表性表C）循）循环队列是非列是非线性性结构构D）有序）有序线性表既可以采用性表既可以采用顺序存序存储结构，也可以采用构，也可

35、以采用链式存式存储结构构3.数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于。4.下列数据结构中，属于非线性结构的是下列数据结构中，属于非线性结构的是A）循环队列）循环队列B)带链队列带链队列C)二叉树二叉树D）带链栈）带链栈答案：答案：D。答案：答案：D。答案：线性结构。答案：线性结构。答案：答案：c34计算机二级公共基础知识课件5。下列叙述中正确的是（下列叙述中正确的是（）。）。（2008年年9月）月）A）顺顺序序存存储储结结构构的的存存储储一一定定是是连连续续的的，链链式式存存储储结结构构的的存存储储空空间不一定是连续的间不一定是连续的B）

36、顺顺序序存存储储结结构构只只针针对对线线性性结结构构，链链式式存存储储结结构构只只针针对对非非线线性性结构结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间）链式存储结构比顺序存储结构节省存储空间答案：答案：A。6 6。下列关于。下列关于栈的叙述正确的是的叙述正确的是 （2008年年4月）月） A A）栈按按“先先进先出先出”组织数据数据 B)B)栈按按“先先进后出后出”组织数据数据 C C）只能在）只能在栈底插入数据底插入数据 D D）不能）不能删除数据除数据答案：答案：B。7.一个队列

37、的初始状态为空。现将元素一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为依次入队，然后再依次退队，则元素退队的顺序为【1】。（2010年年3月）月）答案：答案：A，B，C，D，E，F，5，4，3，2，135计算机二级公共基础知识课件9.设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向指向队头元素的前一位置队头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该循环队列中共有，则该循环队列中共有【2】个元素。个元素。（2010年年3月）月）8。假。假设用一个

38、用一个长度度为50的数的数组（数（数组元索的下元索的下标从从0到到49）作）作为栈的存的存储空空间，栈底指底指针bottom指指间栈底底元素，元素，栈顶指指针top指向指向栈顶元素，如果元素，如果bottom=49，top=30（数（数组下下标），），则栈中具有【中具有【】个元素。】个元素。（2009年年3月）月）答案：答案：19答案：答案：1536计算机二级公共基础知识课件一个非空的数据结构若满足下面的两个条件，则这种数据结构一个非空的数据结构若满足下面的两个条件，则这种数据结构即为即为线性结构线性结构线性结构线性结构。有且仅有一个根结点；有且仅有一个根结点；除第一个结点外，每一个结点最多有

39、一个直接前驱结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除最后一个结点外，每一个结点最多有一个直接后继结点。除最后一个结点外，每一个结点最多有一个直接后继结点。u线性结构与非线性结构线性结构与非线性结构线性表、栈和队列都是线性结构线性表、栈和队列都是线性结构一个数据结构不是线性结构，则称其为一个数据结构不是线性结构，则称其为非线性结非线性结非线性结非线性结构构构构。a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态37计算机二级公共基础知识课件树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。u树的概念树的概念u二叉树的概念二叉树的概念u二叉

40、树的存储二叉树的存储u二叉树的遍历二叉树的遍历3.树与二叉树树与二叉树38计算机二级公共基础知识课件树的概念树的概念树的概念树的概念u树的定义：树的定义：n个结点的有限集。（个结点的有限集。（n=0）ABDFECGHIJKMn根：根：onlyonen若若n=0，则称为空树；，则称为空树；n否则，当否则，当n1时，其余结时，其余结点被分成点被分成m（m0）个互不）个互不相交的子集相交的子集T1，T2，.，Tm，每个子集又是一棵树。，每个子集又是一棵树。由此可以看出，树的定义是由此可以看出，树的定义是递归的。递归的。nQuestion：如何辨别根？：如何辨别根？A只有一个只有一个结点的树结点的树3

41、9计算机二级公共基础知识课件树型结构的常用术语树型结构的常用术语树型结构的常用术语树型结构的常用术语ABDFECGHIJKMn结点的度结点的度结点的度结点的度一个结点的子树的一个结点的子树的个数；个数；Q：结点结点A、G的度数？的度数？n树的度树的度树的度树的度树中所有结点度的最树中所有结点度的最大值；大值；Q：右图中树的度？右图中树的度？n终端结点终端结点终端结点终端结点度为度为0的结点；的结点；Q：图中叶子结点有几个？图中叶子结点有几个？7n n 非终端结点非终端结点非终端结点非终端结点度不为度不为0的结点；的结点；Q：图中非终端结点有几个？图中非终端结点有几个？5孩子结点、双亲结点、兄弟

42、结点、结点的子孙、结点的祖先孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先40计算机二级公共基础知识课件树型结构的常用术语树型结构的常用术语树型结构的常用术语树型结构的常用术语ABDFECGHIJKMn结点的层次结点的层次结点的层次结点的层次树中根结点的层次树中根结点的层次为为1，根结点子树的根为第，根结点子树的根为第2层，层，以此类推；以此类推；Q：图中结点图中结点F的层次？的层次？n树的深度树的深度树的深度树的深度 树中所有结点层次树中所有结点层次的最大值；的最大值；Q：图中树的深

43、度？图中树的深度？n有序树、无序树有序树、无序树有序树、无序树有序树、无序树如果树中每如果树中每棵子树从左向右的排列拥有一定棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序的顺序，不得互换，则称为有序树，否则称为无序树。树，否则称为无序树。41计算机二级公共基础知识课件二叉树的概念二叉树的概念二叉树的概念二叉树的概念定义：定义：定义：定义：二叉树是一种有序的树形结构。它与一般二叉树是一种有序的树形结构。它与一般树形结构的区别是：树形结构的区别是：n每个结点最多有两棵子树；每个结点最多有两棵子树；n子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。二叉树的二叉树的5种基

44、本形态种基本形态42计算机二级公共基础知识课件二叉树的性质二叉树的性质二叉树的性质二叉树的性质【性质1】在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点（个结点（i1）ABCDFEHG43计算机二级公共基础知识课件【性质2】深度为深度为h的二叉树最多有的二叉树最多有2h-1个结点（个结点（h1）n n满二叉树满二叉树满二叉树满二叉树：如果一个深度为如果一个深度为h的二叉树拥有的二叉树拥有2h-1个结个结点，则将它称为点，则将它称为满二叉树满二叉树。n n完全二叉树完全二叉树完全二叉树完全二叉树：有一棵深度为有一棵深度为h，具有，具有n个结点的二叉树，个结点的二叉树，若将它与一棵同深

45、度的满二叉树中的所有结点按从上若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为的每个结点分别与满二叉树中编号为1n的结点位置的结点位置一一对应，则称这棵二叉树为一一对应，则称这棵二叉树为完全二叉树完全二叉树。44计算机二级公共基础知识课件121314158910114567123满二叉树满二叉树完全二叉树完全二叉树12138910114567123完全二叉树是满二叉树满二叉树也是完全二叉树45计算机二级公共基础知识课件1213891011456123非完全二叉树非完全二叉树

46、深度为深度为4的的完全二叉树完全二叉树8456712346计算机二级公共基础知识课件【性质3】二叉树上叶子结点数比度为二叉树上叶子结点数比度为2的结点数多的结点数多1ABCDFEHG度为2的结点叶子结点47计算机二级公共基础知识课件【性质4】具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2(n+1) 其中，其中， log2n 的结果是不大于的结果是不大于log2n的最大整数的最大整数121314158910114567123深度为深度为4的的满二叉树满二叉树深度为深度为4的的完全二叉树完全二叉树84567123深度为深度为3的完全二叉树具有的完全二叉树具有47深度为深度

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的完全二叉树具有的完全二叉树具有1024204748计算机二级公共基础知识课件1 1：在深度：在深度为7 7的的

48、满二叉二叉树中中, ,叶子叶子结点的个数点的个数为（20062006年年4 4月）月） A)32 A)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的的结点点有有

49、1818个个，则该二二叉叉树中中有有 【 】个个叶叶子子结点点。（20052005年年4 4月）月）5 5：一一棵棵二二叉叉树第第六六层（根根结点点为第第一一层）的的结点点数数最最多多为【 】个个。（20052005年年9 9月）月）树型结构方面的考题树型结构方面的考题1答案：答案：C。3答案：答案：A。5答案：答案：32。2答案：答案：63。4答案：答案：19。49计算机二级公共基础知识课件二叉树的存储二叉树的存储二叉树的存储二叉树的存储u在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。LlinkinfoRlink二叉树的存储结点的结构二叉树的存储结点的结构A

50、BDCFGEAGEFBCDt50计算机二级公共基础知识课件二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历u遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结点所有结点。u二叉树的遍历的次序与树型结构上的大多二叉树的遍历的次序与树型结构上的大多数运算有联系。数运算有联系。uu遍历的方式有三种遍历的方式有三种遍历的方式有三种遍历的方式有三种（1）先（前）序遍历（）先（前）序遍历（DLR）（2）中序遍历（）中序遍历（LDR）（3）后序遍历（）后序遍历（LRD）ABCDFEHG51计算机二级公共基础知识课件二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历u遍历指遍历指不重复地不重复地访问

51、二叉树中的访问二叉树中的所有结点所有结点。（1）先（前）序遍历（）先（前）序遍历（DLR）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n访问根结点；访问根结点；n n先序先序先序先序遍历左子树；遍历左子树；n n先序先序先序先序遍历右子树。遍历右子树。ABCDFEHG先序遍历的结果：先序遍历的结果： A A B E C F G H D B E C F G H D52计算机二级公共基础知识课件（2）中序遍历（）中序遍历（LDR）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n中序遍历左子树；中序遍历左子树；n访问根结点；访问根结点；n中序遍历右子树。

52、中序遍历右子树。中序遍历的结果：中序遍历的结果：EBAFHGCD（3）后序遍历（）后序遍历（LRD）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n后序遍历左子树；后序遍历左子树；n后序遍历右子树；后序遍历右子树；n访问根结点。访问根结点。后序遍历的结果：后序遍历的结果：EBHGFDCAABCDFEHG53计算机二级公共基础知识课件u先序序列：先序序列：ABDGCEFHu中序序列：中序序列：DGBAECHFu后序序列：后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？下图所示的二叉树经过三种遍历得到的顺序分别为？练习：练习：根据先序遍

53、历序列，建立二叉树根据先序遍历序列，建立二叉树54计算机二级公共基础知识课件1:设二叉树如下：设二叉树如下：（2010年年3月）月）对该二叉树进行后序遍历的对该二叉树进行后序遍历的结果为结果为【3】树型结构方面的考题树型结构方面的考题22:对如下二叉树（对如下二叉树（2006年年4月）月）进行后序遍历的结果为进行后序遍历的结果为A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCAEDBGHFCADABCFHDGE55计算机二级公共基础知识课件查找技术查找技术查找是数据处理的重要内容。查找是数据处理的重要内容。u查找指在一个给定的数据结构中查找指定的元素，查找指在一个给定的数据结构中

54、查找指定的元素，该元素也称关键字。该元素也称关键字。u若找到了满足条件的结点，称查找成功；否则称查若找到了满足条件的结点，称查找成功；否则称查找失败。找失败。u衡量一个查找算法的主要标准是查找过程中对关键衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。字进行的平均比较次数。u通常根据不同的数据结构，采用不同的查找方法：通常根据不同的数据结构，采用不同的查找方法：n顺序查找顺序查找n二分查找二分查找56计算机二级公共基础知识课件顺序查找顺序查找u线性表中最简单的查找方法。线性表中最简单的查找方法。u方法：从线性表的第一个元素开始，依次将线性表方法：从线性表的第一个元素开始，依次

55、将线性表中的元素与关键字进行比较，若相等，则查找成功；中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，则若将所有元素都与关键字进行了比较但不相等，则查找失败。查找失败。u顺序查找法的适用场合：顺序查找法的适用场合：n对线性表中元素的排列次序没有要求；对线性表中元素的排列次序没有要求；n对线性表的存储结构没有要求，链式结构和顺对线性表的存储结构没有要求，链式结构和顺序结构均可。序结构均可。57计算机二级公共基础知识课件二分查找二分查找( (折半查找)u是一种效率较高的查找方法，但是只适合是一种效率较高的查找方法，但是只适合顺序存储顺序存储的有序表的有序表。

56、u二分查找的方法：首先将关键字与线性表中间位置的二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为直至查找成功或子表长度为0。u二分查找法的适用场合：二分查找法的适用场合：n线性表中的元素按关键字值递增或递减的次序排线性表中的元素按关键字值递增或递减的次序排列；列；n线性表采用顺序存储结构。线性表采用顺序存储结构。58计算机二级公共基础知识课件u练习假设待查有序（升序）顺序表中数据元素的关

57、键字序列为（8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找关键字值为27的数据元素.对于长度为对于长度为n n的有序线性表，最坏情况只需比较的有序线性表，最坏情况只需比较log2nlog2n次。次。59计算机二级公共基础知识课件 排序技术排序技术u排序指排序指将一个无序序列整理成按关键字值递增或递减排列的有序将一个无序序列整理成按关键字值递增或递减排列的有序序列序列。u排序方法中其排序对象一般是排序方法中其排序对象一般是顺序存储顺序存储的线性表。的线性表。u根据排序序列的规模以及数据处理的要求，可以采用不同的排序根据排序序列的规模以及数据处理的要求，可以采用

58、不同的排序方法方法：交换类排序法交换类排序法n冒泡排序冒泡排序n快速排序快速排序插入类排序法插入类排序法n简单插入排序简单插入排序n希尔排序希尔排序选择类排序法选择类排序法n简单选择排序简单选择排序n堆排序堆排序60计算机二级公共基础知识课件冒泡排序冒泡排序冒泡排序冒泡排序u冒泡排序的方法：冒泡排序的方法：n扫描整个线性表，逐次对相邻的两个元素进行比扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最较，若为逆序，则交换；第一趟扫描的结果使最大大(或最小或最小)的元素排到表的最后的元素排到表的最后(或最前或最前)；n除最后除最后(或最前或最前)一个元素，对剩余的

59、元素重复上一个元素，对剩余的元素重复上述过程，将次大述过程，将次大(或次小或次小)的数排到表的倒数的数排到表的倒数(或或正数正数)第二个位置；第二个位置；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，冒泡排序需要对表扫描的线性表，冒泡排序需要对表扫描n-1遍。遍。61计算机二级公共基础知识课件冒泡排序的方法冒泡排序的方法u设待排数据元素的关键字为（18，20，15，32，4，25），第一趟第一趟冒泡排序后的序列状态如图所示：182015324251820153242518152032425181520324251815204322518152042532最大数u第二趟冒泡排序

60、第二趟冒泡排序62计算机二级公共基础知识课件下一页上一页停止放映Q：第二趟冒泡排序后的结果是什么样的？达到第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最了最终的排序目标吗？一共需要多少次能够最后成为有序序列？后成为有序序列？Q：你觉得冒泡排序的效率如何？如果是你，你：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？会用什么方法来排序？ 冒泡排序比较简单，当初始序列基本有序时，冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。冒泡排序有较高的效率，反之效率较低。u冒泡排序终止条件冒泡排序终止条件: 本趟排序未发生交换，终止排序算

61、法本趟排序未发生交换，终止排序算法 6363计算机二级公共基础知识课件下一页上一页停止放映初始初始第一趟第一趟第二趟第二趟第三趟第三趟第四趟第四趟第五趟第五趟序列序列排序后排序后排序后排序后排序后排序后排序后排序后排序后排序后2618 18181891826 26269153232 32915185447 915264791532915 471554设待排数据元素的关键字为设待排数据元素的关键字为（26,18,32,54,47,9,15 )冒泡排序法，需要比较的次数为冒泡排序法，需要比较的次数为n(n-1)/2n(n-1)/2；6464计算机二级公共基础知识课件选择排序选择排序u选择排序的方法

62、：选择排序的方法：n扫描整个线性表，从中找出最小的元素，与第扫描整个线性表，从中找出最小的元素，与第一个元素交换；一个元素交换；n除第一个元素，对剩下的子表采用相同的方法除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；找出次小的数，与第二个数交换；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，选择排序需要对表扫的线性表，选择排序需要对表扫描描n-1遍。遍。简单选择排序法简单选择排序法, ,最坏情况需要最坏情况需要n(n-1)/2n(n-1)/2次比较；次比较；65计算机二级公共基础知识课件下一页上一页停止放映u初态：初态： 15，14，22，30，37，

63、15，11u第一趟：第一趟： 11 14，22，30，37，15，15u第二趟：第二趟： 11，14 22，30，37，15，15u第三趟：第三趟： 11，14，15 30，37，22，15u第四趟：第四趟： 11，14，15，15 37，22，30u第五趟：第五趟： 11，14，15，15，22 37，30u第六趟：第六趟： 11，14，15，15，22，30 37 有序序列有序序列例：设待排数据元素的关键字为（例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示），每一趟排序后的序列状态如图所示：6666计算机二级公共基础知识课件排序法小结：排

64、序法小结：u简单选择排序法简单选择排序法,最坏情况需要最坏情况需要n(n-1)/2次比较；次比较；u冒泡排序法冒泡排序法,最坏情况需要最坏情况需要n(n-1)/2次比较；次比较；u希尔排序法希尔排序法,最坏情况需要最坏情况需要O(n1.5)次比较；次比较；u堆排序法堆排序法,最坏情况需要最坏情况需要O(nlog2n)次比较；次比较；67计算机二级公共基础知识课件排序查找方面的考题：排序查找方面的考题：(1)对于于长度度为n的的线性性表表，在在最最坏坏情情况况下下，下下列列各各排排序序法法所所对应的的比比较次数中正确的是（次数中正确的是（2005年年4月）月）A)冒泡排序冒泡排序为n/2B)冒泡

65、排序冒泡排序为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）

66、冒泡排序）冒泡排序B）简单选择排序排序C）直接插入排序）直接插入排序D）堆排序）堆排序DBAD68计算机二级公共基础知识课件第二章第二章程序设计基础程序设计基础内容：内容：1.程序设计方法与风格。程序设计方法与风格。2.结构化程序设计。结构化程序设计。3.面向对象的程序设计方法，对象，方面向对象的程序设计方法，对象，方法，属性及继承与多态性。法，属性及继承与多态性。69计算机二级公共基础知识课件1结构化程序设计结构化程序设计u结构化程序构化程序设计方法的四条原方法的四条原则是是：1. 自顶向下；2. 逐步求精；3. 模块化；4. 限制使用goto语句。u 结构化程序的基本构化程序的基本结构和特

67、点：构和特点：（1）顺序序结构：构： 简单的程序设计，最基本、最常用的结构；（2）选择结构（分支构（分支结构）：构）： 包括简单选择和多分支选择结构，（3）重复）重复结构（循构（循环结构）：构）： 可根据给定条件，判断是否需要重复执行某一相同程序段。70计算机二级公共基础知识课件2面向对象的程序设计面向对象的程序设计对象是面向对象方法中最基本的概念。对象是面向对象方法中最基本的概念。u对象对象是系统中用来描述客观事物的一个实是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组表示其静态特征的属性和它可执行的

68、一组操作组成。操作组成。n属性属性即对象所包含的信息即对象所包含的信息n操作操作描述了对象执行的功能，操作也称为方描述了对象执行的功能，操作也称为方法或服务。法或服务。71计算机二级公共基础知识课件u类类是指具有共同属性、共同方法的对象的集合。是指具有共同属性、共同方法的对象的集合。u所以类是对象的抽象，所以类是对象的抽象，对象对象是对应类的一个实例。是对应类的一个实例。u消息消息是一个实例与另一个实例之间传递的信息。是一个实例与另一个实例之间传递的信息。消息的组成包括消息的组成包括（1）接收消息的对象的名称；）接收消息的对象的名称；（2）消息标识符，也称消息名；）消息标识符，也称消息名；（3

69、）零个或多个参数。）零个或多个参数。u继承继承是指能够直接获得已有的性质和特征，而不必重是指能够直接获得已有的性质和特征，而不必重复定义他们。复定义他们。n单继承指一个类只允许有一个父类单继承指一个类只允许有一个父类n多重继承指一个类允许有多个父类。多重继承指一个类允许有多个父类。u多态性多态性是指同样的消息被不同的对象接受时可导致完是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。全不同的行动的现象。72计算机二级公共基础知识课件程序设计基础方面的考题程序设计基础方面的考题1.符合结构化原则的三种基本控制结构是：选择结构、循环结构和【符合结构化原则的三种基本控制结构是：选择结构、循

70、环结构和【】.(2009年年3月月)2.下列选项中不属于结构化程序设计原则的是（下列选项中不属于结构化程序设计原则的是（2009年年9月月）A)可封装可封装D)自顶向下自顶向下C)模块化模块化D)逐步求精逐步求精3.以下叙述中正确的是。（以下叙述中正确的是。（2010年年3月月）A）程序设计的任务就是编写程序代码并上机调试）程序设计的任务就是编写程序代码并上机调试B）程序设计的任务就是确定所用数据结构）程序设计的任务就是确定所用数据结构C）程序设计的任务就是确定所用算法）程序设计的任务就是确定所用算法D）以上三种说法都不完整）以上三种说法都不完整4.在面向对象方法中，类的实例称为在面向对象方法

71、中，类的实例称为【_】。（。（2005年年4月月）5.在面向对象方法中在面向对象方法中,【_】描述的是具有相似属性与操作的一组对象。描述的是具有相似属性与操作的一组对象。（2006年4月）（顺序结构）（顺序结构）AD对象对象类类73计算机二级公共基础知识课件第三章第三章软件工程基础软件工程基础u计算机软件是包括程序、数据及相关文计算机软件是包括程序、数据及相关文档的完整集合。档的完整集合。u软件按功能分为应用软件、系统软件、软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。支撑软件（或工具软件）。74计算机二级公共基础知识课件1.软件工程概念软件工程概念u软件工程是应用于计算机软件的定

72、义、开发和维护的软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。一整套方法、工具、文档、实践标准和工序。软件工程包括软件工程包括3个要素：方法、工具和过程。个要素：方法、工具和过程。u软件周期：软件周期：软件产品从提出、实现、使用维护到停止软件产品从提出、实现、使用维护到停止使用退役的过程。使用退役的过程。软件生命周期三个阶段软件生命周期三个阶段:软件定义、软件开发、运行软件定义、软件开发、运行维护，主要活动阶段是：维护，主要活动阶段是：（1）可行性研究与计划制定；可行性研究与计划制定；（2）需求分析；）需求分析；（3）软件设计；）软件设计；（4）软件实现

73、；）软件实现；（5）软件测试；）软件测试；（6）运行和维护。）运行和维护。75计算机二级公共基础知识课件2结构化分析方法结构化分析方法u结构化分析方法：着眼于数据流，自顶向下，着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具和数据字典为主要工具,建立系统的逻辑模型。建立系统的逻辑模型。u结构化分析的常用工具结构化分析的常用工具（1）数据流图；）数据流图；（2）数据字典；）数据字典；（3）判定树；）判定树；判定表。判定表。（4）软件需求规格说明书）软件需求规格说明书76计算机二级公共基础知识课件3结构化设计方法结构化设计

74、方法u软件设计包括：总体设计与详细设计软件设计包括：总体设计与详细设计u在程序结构中各模块的内聚性越强，则耦合性在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。越弱。优秀软件应高内聚，低耦合。u常见的过程设计工具有：常见的过程设计工具有：图形工具（程序流程图图形工具（程序流程图,N-S,PAD）表格工具（判定表）表格工具（判定表）语言工具（语言工具（PDL伪码）伪码）77计算机二级公共基础知识课件u程序流程图程序流程图N-S图图PAD图图78计算机二级公共基础知识课件4软件测试软件测试u软件测试的目的软件测试的目的：发现错误而执行程序的过程。u软件测试方法：软件测试方法

75、：静态测试：静态测试：包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。动态测试：动态测试：是基本计算机的测试，主要包括白盒测试白盒测试方法和黑盒黑盒测试测试方法u软件测试过程测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。79计算机二级公共基础知识课件5程序的调试程序的调试u程序调试的任务是程序调试的任务是诊断和改正程序中的错误诊断和改正程序中的错误，主要在开发阶段进行。主要在开发阶段进行。u软件调试软件调试n静态调试静态调试主要是指通过人的思维来分析源程主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段。序代码和排错，是主

76、要的设计手段。n动态调试动态调试是辅助静态调试。主要调试方法有：是辅助静态调试。主要调试方法有：（1）强行排错法；）强行排错法；（2）回溯法；）回溯法；（3）原因排除法。）原因排除法。80计算机二级公共基础知识课件(1)下面叙述中错误的是下面叙述中错误的是(2009年年3月）月）A）软件测试的目的是发现错误并改正错误）软件测试的目的是发现错误并改正错误B）对被调试的程序进行）对被调试的程序进行“错误定位错误定位”是程序调试的必要步骤是程序调试的必要步骤C）程序调试通常也称为）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性）软件测试应严格执行测试计划，排除测试的随意

77、性(2)软软件件测测试试可可分分为为白白盒盒测测试试和和黑黑盒盒测测试试。基基本本路路径径测测试试属属于于【】测试。测试。(2009年年3月）月）(3)按照软件测试的一般步骤，集成测试应在按照软件测试的一般步骤，集成测试应在_测试之后进行。测试之后进行。(4)软件工程三要素包括方法、工具和过程，其中，软件工程三要素包括方法、工具和过程，其中，_支持软件支持软件开发的各个环节的控制和管理。开发的各个环节的控制和管理。(2008年年9月月)(5)软件件设计中划分模中划分模块的一个准的一个准则是是(2009年年9月）月）A)低内聚低耦合低内聚低耦合B)高内聚低耦合高内聚低耦合C)低内聚高耦合低内聚高

78、耦合D)高内聚高耦合高内聚高耦合A软件工程方面的考题：软件工程方面的考题：白盒白盒单元单元过程过程B81计算机二级公共基础知识课件(6)下列叙述中正确的是（下列叙述中正确的是（2005年年9月）月）AA）软件交付使用后还需要进行维护）软件交付使用后还需要进行维护B）软件一旦交付使用就不需要再进行维护）软件一旦交付使用就不需要再进行维护C）软件交付使用后其生命周期就结束）软件交付使用后其生命周期就结束D）软件维护是指修复程序中被破坏的指令）软件维护是指修复程序中被破坏的指令(7)程序流程图中的菱形框表示的是程序流程图中的菱形框表示的是【2】(2009年年9月月)。(8)软件开发过程主要分为需求分

79、析、设计、编码与测试四个阶段，软件开发过程主要分为需求分析、设计、编码与测试四个阶段，其中其中【3】阶段产生阶段产生“软件需求规格说明书。软件需求规格说明书。（2009年年9月）月）(9)下列叙述中正确的是（下列叙述中正确的是（2006年年4月）月）A)软件测试应该由程序开发者来完成软件测试应该由程序开发者来完成B)程序经调试后一般不需要再测试程序经调试后一般不需要再测试C)软件维护只包括对程序代码的维护软件维护只包括对程序代码的维护D)以上三种说法都不对以上三种说法都不对A逻辑条件逻辑条件需求分析需求分析D82计算机二级公共基础知识课件(3)软软件件按按功功能能可可以以分分为为：应应用用软软

80、件件、系系统统软软件件和和支支撑撑软软件件(或或工工具具软软件件)。下面属于系统软件的是。下面属于系统软件的是A)编辑软件编辑软件B)操作系统操作系统C)教务管理系统教务管理系统D)浏览器浏览器(4)软件软件(程序程序)调试的任务是调试的任务是A)诊断和改正程序中的错误诊断和改正程序中的错误B)尽可能多地发现程序中的错误尽可能多地发现程序中的错误C)发现并改正程序中的所有错误发现并改正程序中的所有错误D)确定程序中错误的性质确定程序中错误的性质(5)数据流程图数据流程图(DFD图图)是是A)软件概要设计的工具软件概要设计的工具B)软件详细设计的工具软件详细设计的工具C)结构化方法的需求分析工具

81、结构化方法的需求分析工具D)面向对象方法的需求分析工具面向对象方法的需求分析工具(6)软软件件生生命命周周期期可可分分为为定定义义阶阶段段，开开发发阶阶段段和和维维护护阶阶段段。详详细细设设计计属于属于A)定义阶段定义阶段B)开发阶段开发阶段C)维护阶段维护阶段D)上述三个阶段上述三个阶段2010年年3月计算机等级考试月计算机等级考试BACB83计算机二级公共基础知识课件数据库设计基础知识点得分表数据库设计基础知识点得分表数据库的数据库的基本概念基本概念数据数据模型模型关系关系代数代数数据库设数据库设计与管理计与管理小计08年年4月月2分6分2分10分08年年9月月2分4分2分2分10分09年

82、年3月月2分2分2分4分10分09年年9月月2分2分2分4分10分10年年3月月2分4分2分2分10分时间知识点84计算机二级公共基础知识课件第四章第四章数据库设计基础数据库设计基础uu数据：数据：数据：数据：实际上就是描述事物的符号记录。实际上就是描述事物的符号记录。uu数据库数据库数据库数据库：是数据的集合，具有统一的结构形式并存放：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。被各个应用程序共享。uu数据库管理系统数据库管理系统数据库管理系统数据库管理系统：一种系统软件，负责数据库中的

83、数：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。务等，是数据库的核心。uu数据库系统数据库系统数据库系统数据库系统：由数据库（数据）、数据库管理系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。、软件平台（软件）五个部分构成的运行实体。uu数据库应用系统数据库应用系统数据库应用系统数据库应用系统：由数据库系统、应用软件及应用界：由数据库系统、应用软件及应用界面三者组成。面

84、三者组成。85计算机二级公共基础知识课件数据库系统数据库系统86计算机二级公共基础知识课件常见的关系数据库管理系统小型数据库：Visual FoxPro （以后简称为VFP）Access (office套件中的一个)Paradox大型数据库：Oracle Informix SYBASE SQL server 等 87计算机二级公共基础知识课件u数据库管理系统提供的数据语言：数据库管理系统提供的数据语言：（1）数据定义语言数据定义语言：负责数据的模式定义与数据的物理存取构建；（2）数据操纵语言数据操纵语言：负责数据的操纵，如查询与增、删、改等；（3）数据控制语言数据控制语言：负责数据完整性、安全

85、性的定义与检查以及并发控制、故障恢复等。u数据库管理系统的发展数据库管理系统的发展(1)文件系统阶段文件系统阶段：提供了简单的数据共享与数据管理能力，但是它无法提供完整的、统一的、管理和数据共享的能力。(2)层次数据库与网状数据库系统阶段层次数据库与网状数据库系统阶段：为统一与共享数据提供了有力支撑。(3)关系数据库系统阶段关系数据库系统阶段1.数据库系统的基本概念数据库系统的基本概念88计算机二级公共基础知识课件u关系数据库系统的基本特点：关系数据库系统的基本特点：n数据的集成性数据的集成性n数据的高共享性与低冗余性数据的高共享性与低冗余性n数据独立性（物理独立性与逻辑独立性）数据独立性（物

86、理独立性与逻辑独立性）n数据统一管理与控制。数据统一管理与控制。u数据库存放数据是按数据所提供的数据模式存放的，具有集成数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。与共享的特点。u数据库系统的三级模式：数据库系统的三级模式：（1）概念模式（）概念模式（2）外模式（）外模式（3）内模式）内模式u数据库系统的两级映射：数据库系统的两级映射：（1）概念模式到内模式的映射；）概念模式到内模式的映射；（2）外模式到概念模式的映射。）外模式到概念模式的映射。1.数据库系统的基本概念数据库系统的基本概念89计算机二级公共基础知识课件应用外模式外模式(用户数据库用户数据库)应用外模式外

87、模式(用户数据库用户数据库)应用外模式外模式(用户数据库用户数据库)概念模式概念模式(概念数据库概念数据库)内模式内模式(物理数据库物理数据库)数据库数据库外模式外模式概念模式映射概念模式映射概念模式概念模式内模式映射模式内模式映射模式90计算机二级公共基础知识课件2. 数据模型数据模型数据模型数据模型（Data Model）是）是对客观事物及其对客观事物及其关系的数据描述。关系的数据描述。 数据库中的数据模型可以将复杂的现实世界要求反映到数据库中的数据模型可以将复杂的现实世界要求反映到计算机数据库中的物理世界。计算机数据库中的物理世界。现实世界现实世界信息世界信息世界计算机世界计算机世界 数

88、据模型是数据模型是数据特征的抽象，数据特征的抽象，从抽象层次上描从抽象层次上描述了系统的述了系统的静态特征、动态行为和约束条件。静态特征、动态行为和约束条件。数据模型数据模型所描述的内容包含所描述的内容包含：数据结构、数据：数据结构、数据操作和数据约束。操作和数据约束。91计算机二级公共基础知识课件2.数据模型数据模型uE-R模型的基本概念模型的基本概念（1）实体实体：现实世界中的事物现实世界中的事物；（2）属性属性：事物的特性；事物的特性；（3）联系联系：现实世界中事物间的关系。现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多一对一、一对多、多对多的联系。一个班级的学生，学生与学

89、生之间是一个班级的学生，学生与学生之间是一对一一对一的关系。的关系。在一所学校，一门课程与学生之间是在一所学校，一门课程与学生之间是一对多一对多的关系。的关系。在一所学校，多门课程与多个学生之间是在一所学校，多门课程与多个学生之间是多对多多对多的的关系。关系。92计算机二级公共基础知识课件E-R模型的图示法用简单的几何图形表示实体集、属性与联系。用简单的几何图形表示实体集、属性与联系。(1)实体集表示法实体集表示法在在E-R图中用矩形表表示实体集，在矩形内写上图中用矩形表表示实体集，在矩形内写上实体集名称。如实体集学生实体集名称。如实体集学生(student)、实体集课程、实体集课程(cour

90、se)(2)属性表示法属性表示法在在E-R图中用椭圆形表示属性，在椭圆形内写上图中用椭圆形表示属性，在椭圆形内写上该属性名称。如学生有属性：学号该属性名称。如学生有属性：学号(S#)、姓名、姓名(Sn)及及年龄年龄(Sa)可用如下表示。可用如下表示。studentcourseS#SnSa93计算机二级公共基础知识课件(3)联系表示法在在E-R图中用菱形图中用菱形(内写上联系名内写上联系名)表示联系。表示联系。如学生与课程的联系如学生与课程的联系SC,如下图所示：如下图所示：(4)实体集与属性间的联系关系实体集与属性间的联系关系属性依附于实体集，它们之间有联系关系用无属性依附于实体集，它们之间有

91、联系关系用无向线段表示。向线段表示。SCstudentS#SnSa94计算机二级公共基础知识课件属性也依附于联系，它们之间也有联系关系，因此也可属性也依附于联系，它们之间也有联系关系，因此也可用无向线段，如联系用无向线段，如联系SC可与学生的课程成绩属性可与学生的课程成绩属性G建立联系建立联系并用下图表示。并用下图表示。(5)实体集与联系间的连接关系实体集与联系间的连接关系(也可用无向线段也可用无向线段)SCGstudentcourseSC95计算机二级公共基础知识课件E-R模型之间的联接关系：模型之间的联接关系：实体实体是概念世界中的基本单位，是概念世界中的基本单位，属性属性有属性域，每个实

92、体可取属性域内有属性域，每个实体可取属性域内的值。的值。一个实体的所有属性值叫元组。一个实体的所有属性值叫元组。E-R模型的图示法：模型的图示法：（1）实体集表示法；）实体集表示法；用长方形（2）属性表法；）属性表法；用椭圆形（3）联系表示法。）联系表示法。用菱形，(m:n)96计算机二级公共基础知识课件层次模型层次模型（采用树型结构）图图1-4层次模型示例层次模型示例97计算机二级公共基础知识课件网络模型网络模型（采用无向图型结构）98计算机二级公共基础知识课件关系模型关系模型（采用二维表结构）99计算机二级公共基础知识课件关系数据模型关系数据模型u关系模型采用二维表来表示关系模型采用二维表

93、来表示，简称表，由表框架，简称表，由表框架及表的元组组成。一个二维表就是一个关系。及表的元组组成。一个二维表就是一个关系。u关系数据库系统的特点之一是它建立在数据理论关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的基础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系的数据操作，其中最为著名的是关系代数与关系演算。演算。学号学号姓名姓名性别性别出生日期出生日期入学成绩入学成绩四级通过否四级通过否计算机等级考试计算机等级考试备注备注04001001尚杰尚杰男男86-11-20520.5T一一级04001002余余习芳芳女女86-1

94、2-26513.5F二二级04001057张轶一一男男86-01-09612.0T04002023陶陶红莉莉女女85-02-14535.0F二二级100计算机二级公共基础知识课件1.关系的数据结构关系的数据结构二维表由表框架与表元组组成。二维表由表框架与表元组组成。表框架由表框架由n个命名的属性组成个命名的属性组成(n称为属性元素称为属性元素)。每个属性有一个取值范围称为值域。每个属性有一个取值范围称为值域。表框架对应了关系的模式，即类型的概念。表框架对应了关系的模式，即类型的概念。每行数据称为元组，一个元组由每行数据称为元组，一个元组由n个元组分量所组个元组分量所组成，每个元组分量是表结构中

95、每个属性的投影值。成，每个元组分量是表结构中每个属性的投影值。学号学号姓名姓名性别性别出生日期出生日期入学成绩入学成绩四级通过否四级通过否计算机等级考试计算机等级考试备注备注04001001尚杰尚杰男男86-11-20520.5T一一级04001002余余习芳芳女女86-12-26513.5F二二级04001057张轶一一男男86-01-09612.0T04002023陶陶红莉莉女女85-02-14535.0F二二级101计算机二级公共基础知识课件一个二维表要满足下面一个二维表要满足下面7个性质就可称为一个关系。个性质就可称为一个关系。二维表中元组个数是有限的二维表中元组个数是有限的二维表中元

96、组均不相同二维表中元组均不相同二维表中元组的次序可任意交换二维表中元组的次序可任意交换二维表中元组的分量是不可分割的基本数据项二维表中元组的分量是不可分割的基本数据项二维表中属性名各不相同二维表中属性名各不相同二维表中属性与次序无关，可任意交换二维表中属性与次序无关，可任意交换二维表属性中的分量具有与该属性相同的值域二维表属性中的分量具有与该属性相同的值域二维表二维表关系模型关系模型VFP表文件表文件二维表框架二维表框架关系模式关系模式数据表结构数据表结构行行元组元组记录记录元组分量元组分量数据项数据项列列属性属性字段字段属性值域属性值域字段值域字段值域惟一标识元组的最小属性集称为该表的键惟一

97、标识元组的最小属性集称为该表的键(或码或码)，在，在VFP表中称为主关键字表中称为主关键字102计算机二级公共基础知识课件关系模型的基本运算：关系模型的基本运算：1.数据查询数据查询查询关系数据库中的数据，一个关系内的查查询关系数据库中的数据，一个关系内的查询以及多个关系间的查询。询以及多个关系间的查询。查询的基本单位为元组分量，先定位后操作。查询的基本单位为元组分量，先定位后操作。纵向定位（列指定）纵向定位（列指定）横向定位（行选择）横向定位（行选择）2.数据插入数据插入插入一个元组（不定位）插入一个元组（不定位）3.数据删除数据删除删除一个元组（定位、操作）删除一个元组（定位、操作）4.数

98、据修改数据修改删除需修改的元组再插入修删除需修改的元组再插入修改后的元组改后的元组关系操作103计算机二级公共基础知识课件关系模型的基本运算：关系模型的基本运算：1.插入插入集合的集合的并并运算运算2.删除删除集合的集合的差差(交交)运算运算3.修改修改集合的集合的差差|并并(除除)运算。运算。4.查询查询（投影、选择、笛卡尔积运算投影、选择、笛卡尔积运算）3.关系代数集合的集合的并并运算运算104计算机二级公共基础知识课件由关系由关系R和和S通过通过交交运算得到关系运算得到关系T，105计算机二级公共基础知识课件用于查询的集合运算用于查询的集合运算：（1）投影）投影对于关系对于关系R内的内的

99、域指定域指定称为投影运算。称为投影运算。S关系就是对关系就是对R关系指定关系指定A和和B两个域的结果两个域的结果ABCa32b01c21ABa3b0c2RS3.关系代数106计算机二级公共基础知识课件关系代数关系代数（2）选择）选择选择运算的关系是由关系选择运算的关系是由关系R中那些满足逻辑条件的元组所组成。中那些满足逻辑条件的元组所组成。S关系就是关系就是R关系中满足关系中满足A=a的结果的结果ABCa32b01a69c21RSABCa32a69有了投影和选择运算，我们对一个关系内的任意有了投影和选择运算，我们对一个关系内的任意行、列的数据都可以方便的找到。行、列的数据都可以方便的找到。10

100、7计算机二级公共基础知识课件笛卡尔积是对两个关系的合并操作。笛卡尔积是对两个关系的合并操作。有三个关系R、S和TR关系关系n1行行,m1列列S关系关系n2行，行，m2列列T关系关系行数行数=n1*n2列数列数=m1+m2AmnBC13ABCm13n13RST（3）笛卡尔积运算）笛卡尔积运算108计算机二级公共基础知识课件笛卡尔积建立两个关系的连接，但得到的关系庞大且数据大量冗余。在实际应用中一般相互连接的关系往往须满足一些条件，所得到的结果也较为简单。自然连接满足两个关系中有公共域，通过公自然连接满足两个关系中有公共域，通过公共域的相等值进行连接。共域的相等值进行连接。有三个关系R、S和TR关

101、系关系n1行行,m1列列S关系关系n2行，行，m2列列T关系关系行数(n1或n2中行数多的一个)列数m1+m2（4）自然连接运算）自然连接运算109计算机二级公共基础知识课件有三个关系R、S和T，由关系由关系R和和S通过运算得到通过运算得到关系关系T，则使用的运算为，则使用的运算为笛卡尔积笛卡尔积ABk1f1k2r1BCf13r13ABCk1f13k2r13RST自然连接自然连接ABk1f1k2r1BCf13r13ABBCk1f1 f13k1f1 r13k2r1 f13k2r1 r13RST110计算机二级公共基础知识课件在三个关系在三个关系R，S和和T如下：如下：由关系R和S通过自然连接运算

102、得到关系T。ABm1n2BC1335ABCm13RST111计算机二级公共基础知识课件数据库设计与管理u数据库设计的两种方法：数据库设计的两种方法：（1）面向数据：以信息需求为主，兼顾处理需求；（2）面向过程：以处理需求为主，兼顾信息需求。u数据库的生命周期数据库的生命周期：n需求分析阶段需求分析阶段结构析方法和面向对象的方法数据字典是各类数据描述的集合，包括数据字典是各类数据描述的集合，包括5个部分：数据项、数据个部分：数据项、数据结构、数据流、数据存储、处理过程。结构、数据流、数据存储、处理过程。n概念设计阶段概念设计阶段分析数据内在语义关系。E-R模型n逻辑设计阶段逻辑设计阶段n物理设计

103、阶段物理设计阶段n编码阶段编码阶段n测试阶段测试阶段n运行阶段运行阶段n进一步修改阶段进一步修改阶段112计算机二级公共基础知识课件4.4数据库设计与管理数据库应用系统数据库应用系统(DBAS)中中,核心问题是数据库设核心问题是数据库设计。计。需求分析需求分析概念设计概念设计逻辑设计逻辑设计物理设计物理设计编码编码测试测试运行运行进一步修改进一步修改分析客户的业务和数据处理需求分析客户的业务和数据处理需求;设计数据库的设计数据库的E-R模型图，确认需模型图，确认需求信息的正确和完整求信息的正确和完整;将将E-R图转换为多张表，进行逻辑图转换为多张表，进行逻辑设计设计,并应用数据库设计的三大范式

104、并应用数据库设计的三大范式进行审核进行审核;数据库内模式数据库内模式包括存储结构包括存储结构和存取方法。和存取方法。重重点点记记8个个阶阶段段选择具体数据库进行物理实现，选择具体数据库进行物理实现，并编写代码实现前端应用并编写代码实现前端应用;113计算机二级公共基础知识课件数据库管理的内容数据库管理的内容（1）数据库的建立；）数据库的建立；（2）数据库的调整；）数据库的调整；（3）数据库的重组；）数据库的重组；（4）数据库安全性与完整性控制；）数据库安全性与完整性控制；（5）数据库的故障恢复；）数据库的故障恢复；（6）数据库监控。）数据库监控。114计算机二级公共基础知识课件06年年9月全国

105、计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题4)在数据库系统中,用户所见的数据模式为A)概念模式B)外模式C)内模式D)物理模式5)数据库设计的四个阶段是:需求分析、概念设计、逻辑设计和A)编码设计B)测试阶段C)运行阶段D)物理设计D4D5115计算机二级公共基础知识课件6）设有如下三个表）设有如下三个表AmnBC13ABCm13n13下列操作中正确的是下列操作中正确的是A)T=RSB)T=RSC)T=RSD)=R/SRSTD6A)并并B)交交C)笛卡尔积笛卡尔积D)除除116计算机二级公共基础知识课件9)数据库技术的根本目标是要解决数据的A)存储问题B)共

106、享问题C)安全问题D)保护文题二、填空题二、填空题3)一个关系表的行称为【3】D9T3元组元组117计算机二级公共基础知识课件07年年4月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题8）在下列关系运算中，不改变关系表中的属性）在下列关系运算中，不改变关系表中的属性个数但能减少元组个数为个数但能减少元组个数为A）并）并B）交）交C）投影）投影D）笛卡儿乘积）笛卡儿乘积9）在）在E-R图中，用来表示实体之间联系的图形是图中，用来表示实体之间联系的图形是A）矩形）矩形B）椭圆形）椭圆形C）菱形）菱形D）平行四边形）平行四边形D9D8118计算机二级公共基础知识课

107、件10）下列叙述中错误的是）下列叙述中错误的是A）在数据库系统中，数据的物理结构必）在数据库系统中，数据的物理结构必须与逻辑结构一致须与逻辑结构一致B）数据库技术的根本目标是要解决数据）数据库技术的根本目标是要解决数据的共享问题的共享问题C）数据库设计是指在已有数据库管理系）数据库设计是指在已有数据库管理系统的基础上建立数据库统的基础上建立数据库D）数据库系统需要操作系统的支持）数据库系统需要操作系统的支持D10二、填空题二、填空题3）在数据库系统中实现各种数据管理功能数据库系统中实现各种数据管理功能的核心软件称为的核心软件称为【3】。数据库管理系统或数据库管理系统或DBMST3119计算机二

108、级公共基础知识课件07年年9月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题9)下列叙述中正确的是下列叙述中正确的是A)数据库系统是一个独立的系统，不需要操作系统的支持B)数据库技术的根本目标是要解决数据的共享问题C)数据库管理系统就是数据库系统D)以上三种说法都不对D9120计算机二级公共基础知识课件10)下列叙述中正确的是下列叙述中正确的是A)为了建立一个关系，首先要构造数据的逻辑关系B)表示关系的二维表中各元组的每一个分量还可以分成若干数据项C)一个关系的属性名表称为关系模式D)一个关系可以包括多个二维表二、填空题二、填空题5)在在E-R图中，矩形表示

109、图中，矩形表示5。D10T5实体集实体集121计算机二级公共基础知识课件08年年4月月全国计算机等级考试二级笔试试卷全国计算机等级考试二级笔试试卷一、单选题一、单选题8)在数据库设计中，将在数据库设计中，将E-R图转换成关系图转换成关系数据模型的过程属于数据模型的过程属于A)需求分析阶段B)概念设计阶段C)逻辑设计阶段D)物理设计阶段D8122计算机二级公共基础知识课件(9)有三个关系有三个关系R、S和和T如下：如下：由关系由关系R和和S通过运算得到关系通过运算得到关系T，则所使用的运，则所使用的运算为算为A并并B自然连接自然连接C笛卡尔积笛卡尔积D.交交D9123计算机二级公共基础知识课件1

110、0)设有表示学生选课的三张表，学生S（学号，姓名，性别，年龄，身份证号)，课程C（课号，课名)，选课SC（学号，课号，成绩)，则表SC的关键字（键或码)为A)课号，成绩B)学号，成绩C)学号，课号D)学号，姓名，成绩二、填空题二、填空题4)在关系数据库中，用来表示实体之间联系的是_。5)在数据库管理系统提供的数据定义语言、数据操纵语言和数据控制语言中，_负责数据的模式定义与数据的物理存取构建。D10T4T5关系关系数据定义语言数据定义语言124计算机二级公共基础知识课件08年年9月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题8)一间宿舍可住多个学生，则实体

111、宿舍和学生之间的联系是A)一对一B)一对多C)多对一D)多对多9)在数据管理技术发展的三个阶段中，数据共享最好的是A)人工管理阶段B)文件系统阶段C)数据库系统阶段D)三个阶段相同D8D9125计算机二级公共基础知识课件10)在三个关系在三个关系R，S和和T如下：如下：由关系R和S通过运算得到关系T,则所使用的运算为A)笛卡尔积B)交C)并D)自然连接二、填空题二、填空题4)数据库设计包括概念设计、【数据库设计包括概念设计、【】、和物理设计。】、和物理设计。5)在二维表中，元组的在二维表中，元组的【】不能再分成更小的】不能再分成更小的数据项。数据项。ABm1n2BC1335ABCm13RSTD

112、10T4T5逻辑设计逻辑设计分量分量126计算机二级公共基础知识课件09年年3月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题8)数据库应用系统中的核心问题是数据库应用系统中的核心问题是A)数据库设计数据库设计B)数据库系统设计数据库系统设计C)数据库维护数据库维护D)数据库管理员培训数据库管理员培训9)有两个关系有两个关系R,S如下：如下：由关系由关系R通过运算得到关系通过运算得到关系S，则所使用的运算是，则所使用的运算是A)选择选择B)投影投影C)插入插入D)连连接接ABCa32b01c21ABa3b0c2RSD8D9127计算机二级公共基础知识课件10

113、)将E-R图转换为关系模式时，实体和联系都可以表示为A)属性B)键C)关系D)域二、填空题二、填空题4)数据库系统的核心是【4】。5)在E-R图中，图形包括矩形框，菱形框，椭圆框，其中表示实体联系的是【5】框。D10T4T5数据库管理系统数据库管理系统菱形菱形128计算机二级公共基础知识课件09年年9月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷一、单选题一、单选题8)数据库管理系统是数据库管理系统是A）操作系统的一部分）操作系统的一部分B)在操作系统支持下的系统软件在操作系统支持下的系统软件C)一种编译系统一种编译系统D)一种操作系统一种操作系统10)有三个关系有三个关系R

114、，S和和T如下：如下：其中关系其中关系T由关系由关系R和和S通过某种操作得到，该操作为通过某种操作得到，该操作为A)选择选择B)投影投影C)交交D)并并ABCa12b21c31RSD8D9ABCd32ABCa12b21c31d32T129计算机二级公共基础知识课件9）在E-R图中，用来表示实体联系的图形是A)椭圆图B)矩形C)菱形D)三角形二、填空题二、填空题（4）在数据库技术中，实体集之间的联系可以是一对一或一对多或多对多的，那么“学生”和“可选课程”的联系为【4】。（5）人员基本信息一般包括：身份证号，姓名，性别，年龄等。其中可以作为主关键字的是【5】。D10T4T5多对多多对多身份证号身

115、份证号130计算机二级公共基础知识课件(7)数据库管理系统中负责数据模式定义的语言是数据库管理系统中负责数据模式定义的语言是A)数据定义语言数据定义语言B)数据管理语言数据管理语言C)数据操纵语言数据操纵语言D)数据控制语言数据控制语言(8)在学生管理的关系数据库中，存取一个学生信息的数据在学生管理的关系数据库中，存取一个学生信息的数据单位是单位是A)文件文件B)数据库数据库C)字段字段D)记录记录(9)数据库设计中，用数据库设计中，用E-R图来描述信息结构但不涉及信息图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的在计算机中的表示，它属于数据库设计的A)需求分析阶段需求分析阶

116、段B)逻辑设计一阶段逻辑设计一阶段C)概念设计阶段概念设计阶段D)物理设计阶段物理设计阶段T9T7T8CAD2010年年3月全国计算机等级考试二级笔试试卷月全国计算机等级考试二级笔试试卷131计算机二级公共基础知识课件10)有两个关系有两个关系R,T如下：如下：则由关系则由关系R得到关系得到关系T的操作是的操作是A)选择选择B)投影投影C)交交D)并并(5)有一个学生选课的关系，其中学生的关系模式为：学生有一个学生选课的关系，其中学生的关系模式为：学生(学号，姓名，班级，年龄学号，姓名，班级，年龄)，课程的关系模式为：课程，课程的关系模式为：课程(课号，课号，课程名，学时课程名，学时)，其中两个关系模式的键分别是学号和课号，则，其中两个关系模式的键分别是学号和课号，则关系模式选课可定义为：选课关系模式选课可定义为：选课(学号，学号，【5】，成绩，成绩)。ABCa12b22c32d32RSD10D5课号AABCc32d32132计算机二级公共基础知识课件谢谢大家！133计算机二级公共基础知识课件