2012公共基础知识(lrw)PPT参考幻灯片.ppt

计算机二级考试计算机二级考试公共基础知识公共基础知识计算机系计算机系C_罗罗12课时安排课时安排C程序设计（程序设计（24节）节）-1公共基础知识（公共基础知识（26节）节）+1上机（上机（30节）节）3计算机二级考试公共基础知识计算机二级考试公共基础知识大纲大纲q数据结构与算法数据结构与算法q程序设计基础程序设计基础q软件工程基础软件工程基础q数据库设计基础数据库设计基础1.掌握算法的基本概念。掌握算法的基本概念。2.掌握基本掌握基本数据结构数据结构及其操作及其操作3.掌握基本掌握基本排序排序和和查找查找算法。算法。4.掌握逐步求精的掌握逐步求精的结构化结构化程序程序设计设计方法。方法。5.掌握掌握软件工程软件工程的基本方法，的基本方法，具有初步应用相关技术进行软具有初步应用相关技术进行软件开发的能力。件开发的能力。6.掌握掌握数据库数据库的基本知识，了的基本知识，了解关系数据库的设计。解关系数据库的设计。4计算机二级考试公共基础知识试卷分析计算机二级考试公共基础知识试卷分析章节章节考试时间考试时间数据结构数据结构与算法与算法程序设程序设计基础计基础软件工软件工程基础程基础数据库设数据库设计基础计基础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分2010年9月10分4分6分10分2011年3月10分2分6分10分2011年9月12分2分6分10分选择题选择题10个（个（20分）分）填空填空题题5个（个（10分）分）总总分的分的30%5一、一、基本数据结构与算法基本数据结构与算法1.算法的基本概念；算法的基本概念；时间复杂度时间复杂度与与空间复杂度空间复杂度。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；数据结构的图形表示；线性结构线性结构与与非线性结构非线性结构的概的概念。念。3.线性表线性表的定义；线性表的顺序存储结构及其插入的定义；线性表的顺序存储结构及其插入与删除运算。与删除运算。4.栈栈和和队列队列的定义；栈和队列的顺序存储结构及其的定义；栈和队列的顺序存储结构及其基本运算。基本运算。5.线性单线性单链表链表、双向链表与循环链表的结构及其基、双向链表与循环链表的结构及其基本运算。本运算。6.树的基本概念；树的基本概念；二叉树二叉树的定义及其存储结构；二的定义及其存储结构；二叉树的前序、中序和后序叉树的前序、中序和后序遍历遍历。7.顺序顺序查找查找与二分法查找算法；基本与二分法查找算法；基本排序排序算法（交算法（交换类排序，选择类排序，插入类排序）。换类排序，选择类排序，插入类排序）。6二、二、程序设计基础程序设计基础1.程序设计方法与风格。程序设计方法与风格。2.结构化程序设计。结构化程序设计。3.面向对象的程序设计方法，对象，面向对象的程序设计方法，对象，方法，属性及类、继承与多态性。方法，属性及类、继承与多态性。7三、三、软件工程基础软件工程基础1.软件工程基本概念，软件工程基本概念，软件生命周期软件生命周期概念，软件概念，软件工具与软件开发环境。工具与软件开发环境。2.结构化分析方法结构化分析方法，数据流图，数据字典，软件，数据流图，数据字典，软件需求规格说明书。需求规格说明书。3.结构化设计方法，总体设计与详细设计。结构化设计方法，总体设计与详细设计。4.软件测试软件测试的方法，白盒测试与黑盒测试，测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成用例设计，软件测试的实施，单元测试、集成测试和系统测试。测试和系统测试。5.程序的程序的调试调试，静态调试与动态调试。，静态调试与动态调试。8四、数据库设计基础四、数据库设计基础1.数据库数据库的基本概念：数据库，数据库管理系统，的基本概念：数据库，数据库管理系统，数据库系统。数据库系统。2.数据模型：实体联系模型及数据模型：实体联系模型及E-R图图，从，从E-R图导图导出关系数据模型。出关系数据模型。3.关系代数运算关系代数运算：包括集合运算及选择、投影、：包括集合运算及选择、投影、连接运算，数据库规范化理论。连接运算，数据库规范化理论。4.数据库设计数据库设计方法和步骤：需求分析、概念设计、方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。逻辑设计和物理设计的相关策略。9算法算法算法的基本概念算法的基本概念2.2.算法复杂度的概念算法复杂度的概念和意义和意义一、基本数据结构与算法一、基本数据结构与算法数据结构数据结构数据结构的概念数据结构的概念线性表线性表栈和队列栈和队列树与树与二叉树二叉树查找查找技术技术排序排序技术技术对于等级考试，这个部分的考核重点主要在对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概算法和数据结构的基本概念念、二叉树二叉树(遍历、结点），遍历、结点），还有还有排序和查找排序和查找考试中也经常会涉及到。考试中也经常会涉及到。10算法的定义算法的定义u对解题方案准确而完整的描述对解题方案准确而完整的描述算法。算法。算法是程序设计的核心算法是程序设计的核心算法的基本概念算法的基本概念 算法是在算法是在有限步骤有限步骤内求解某一问题所使用的一组内求解某一问题所使用的一组定义明确定义明确的的规则规则。通俗点说，就是计算机解题的过。通俗点说，就是计算机解题的过程程(计算的方法计算的方法)。在这个过程中，无论是形成解题。在这个过程中，无论是形成解题思路思路(推理实现的算法推理实现的算法)还是编写程序还是编写程序(操作实现的算操作实现的算法法)，都是在实施某种算法。，都是在实施某种算法。112.算法的基本特征算法的基本特征n可行性可行性n有穷性有穷性n确定性确定性n输入输入n输出输出算法原则上能够精确地运行一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；拥有足拥有足够的情够的情报报123.算法的表示算法的表示开始开始输入输入R RS=3.14*R*R输出输出S S结束结束传统的算法传统的算法-图形法，如图形法，如“流流程图程图”和和N-S图图目前常用的方法目前常用的方法-使用伪码描使用伪码描述算法。述算法。134.算法的两个基本要素：算法的两个基本要素：基本运算和操作基本运算和操作基本运算和操作基本运算和操作n算术运算算术运算n关系运算关系运算n逻辑运算逻辑运算n数据传输数据传输控制结构控制结构控制结构控制结构 n顺序顺序n选择选择n循环循环u一是一是对数据数据对象的运算和操作；象的运算和操作；u二是算法的控制二是算法的控制结构。构。14算法设计基本方法算法设计基本方法n列举法列举法n归纳法归纳法n递推递推n递归递归n减半递推技术减半递推技术n回溯法回溯法根据提出的问题，列举出所有可能的情况根据提出的问题，列举出所有可能的情况通过列举少量的特殊情况，经过分析，最后找出一般的关系通过列举少量的特殊情况，经过分析，最后找出一般的关系从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果将复杂问题逐层分解，最后归结为一些最简单的问题。将复杂问题逐层分解，最后归结为一些最简单的问题。将问题的规模减半，然后，重复相同的递推操作将问题的规模减半，然后，重复相同的递推操作采用试探的方法，通过对问题的分析，找出解决问题的线索采用试探的方法，通过对问题的分析，找出解决问题的线索155算法复杂度算法复杂度时间复杂度时间复杂度n是指执行算法所需要的是指执行算法所需要的计算工作量计算工作量。算法在执行过程中所需算法在执行过程中所需基本运算基本运算的的执行次数执行次数来来度量算法的工作量度量算法的工作量.算法所执行的算法所执行的基本运算次数基本运算次数与与问题的规模问题的规模n有有关关.16例子例子3：for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：X增增1i=20i=31i=42i=nn-21+2+3+(n-2)=(n-1)(n-2)/2O（）例子例子1：+x;O（1）例子例子2：for(i=1;i=n;+i)+x;O（n）时间复杂度：时间复杂度：O(n*n-3n+2)/2)基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：1X增增1基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：X增增1n17空间复杂度空间复杂度n一般是指执行这个算法所需要的一般是指执行这个算法所需要的内存空间内存空间n一个算法所占用的存储空间包括一个算法所占用的存储空间包括:1.算法程序算法程序所占的空间所占的空间2.输入的初始数据输入的初始数据所占的存储空间所占的存储空间3.某种某种数据结构数据结构所需要的附加存储空间所需要的附加存储空间n18(1)在在计计算机中，算法是指算机中，算法是指_。A.查询查询方法方法B.加工方法加工方法C.解解题题方案的准确而完整的描述方案的准确而完整的描述D.排序方法排序方法(2)下列叙述中正确的是下列叙述中正确的是（07年年4月月）A)算法的效率只与算法的效率只与问题问题的的规规模有关，而与数据的存模有关，而与数据的存储结储结构无关构无关B)算法的算法的时间时间复复杂杂度是指度是指执执行算法所需要的行算法所需要的计计算工作量算工作量C)数据的数据的逻辑结逻辑结构与存构与存储结储结构是一一构是一一对应对应的的D)算法的算法的时间时间复复杂杂度与空度与空间间复复杂杂度一定相关度一定相关(3)算法的有算法的有穷穷性是指性是指(08年年4月月)A）算法程序的运行）算法程序的运行时间时间是有限的是有限的B）算法程序所）算法程序所处处理的数据量是有限的理的数据量是有限的C）算法程序的）算法程序的长长度是有限的度是有限的D）算法只能被有限的用）算法只能被有限的用户户使用使用(c)(B)算法习题:(A)19(4)算法的算法的时间时间复复杂杂度是指度是指(2010年年3月月)A)算法的算法的执执行行时间时间B)算法所算法所处处理的数据量理的数据量C)算法程序中的算法程序中的语语句或指令条数句或指令条数D)算法在算法在执执行行过过程中所需要的基本运算次数程中所需要的基本运算次数(5)算法的空算法的空间间复复杂杂度是指度是指(09年年9月月)A）算法在）算法在执执行行过过程中所需要的程中所需要的计计算机存算机存储储空空间间B）算法所）算法所处处理的数据量理的数据量C）算法程序中的）算法程序中的语语句或指令条数句或指令条数D）算法在）算法在执执行行过过程中所需要的程中所需要的临时临时工作工作单单元数元数(6)下列叙述中正确的是下列叙述中正确的是(06年年9月月)A）一个算法的空）一个算法的空间间复复杂杂度大，度大，则则其其时间时间复复杂杂度也必定大度也必定大B）一个算法的空）一个算法的空间间复复杂杂度大，度大，则则其其时间时间复复杂杂度必定小度必定小C）一个算法的）一个算法的时间时间复复杂杂度大，度大，则则其空其空间间复复杂杂度必定小度必定小D）上述三种）上述三种说说法都不法都不对对(D)计算工作量(A)(D)20计算机在进行数据处理时，实际需要处理的数据元计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的算机中，因此，大量的数据元素在计算机中如何组织，数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题。二、数据结构二、数据结构程序程序=算法算法+数据结构数据结构21二二.数据结构数据结构数据结构是指数据结构是指相互有关联的数据元素的集合相互有关联的数据元素的集合。数据结构数据结构是研究数据和数据之间关系的一门是研究数据和数据之间关系的一门学科，它包括三个方面。学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻）数据集合中各数据元素之间所固有的逻辑关系，即数据的辑关系，即数据的逻辑结构逻辑结构；（2）在对数据进行处理时，各数据元素在计）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的算机中的存储关系，即数据的存储结构存储结构；（3）对各种数据结构进行的）对各种数据结构进行的运算运算。221数据的逻辑结构数据的逻辑结构2、数据的存储结构、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、插入、删除、修改等。A线性结构线性结构B非线性结构非线性结构A.顺序存储顺序存储B.链式存储链式存储线性表线性表栈栈队队树树图图数数据据结结构构的的三三个个方方面面23u1.逻辑结构逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：数据的逻辑结构包含：（1）数据元素的集合）数据元素的集合D（2）各数据元素之间的前后件关系）各数据元素之间的前后件关系R数据结构数据结构B=（D，R）例：例：1.一年四季的数据结构一年四季的数据结构B=(D,R)D=春，夏，秋，冬春，夏，秋，冬R=(春，夏春，夏),(夏，秋夏，秋),(秋，冬秋，冬)2.家庭成员的数据结构家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿父亲，儿子，女儿R=(父亲，儿子父亲，儿子),(父亲，女儿父亲，女儿)春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子女儿24u常见的常见的逻辑结构逻辑结构有：有：u线性结构线性结构结构中的每个元素之间存在结构中的每个元素之间存在一一个对个对一一个的关系；个的关系；u树形结构树形结构结构中的每个元素之间存在结构中的每个元素之间存在一一个对个对多多个的关系；个的关系；u图形结构或网状结构图形结构或网状结构结构中的每个元素之间存在结构中的每个元素之间存在多多个对个对多多个的关系。个的关系。线性线性树树图图非非线线性性结结构构A.线性结构线性结构(A,B,C,，X,Y,Z)例例:学生成绩表学生成绩表8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓98611099861109成绩成绩姓名姓名学号学号线性表线性表例例:英文字母表英文字母表如果一个非空的数据结构满足如下条件，则该数据结构为线性结构：如果一个非空的数据结构满足如下条件，则该数据结构为线性结构：有且只有一个根结点有且只有一个根结点每一个结点最多只有一个前件，也最多只有一个后件每一个结点最多只有一个前件，也最多只有一个后件湖北大学公共计算机课部2006年11月21日A.线性结构线性结构线性表线性表栈栈后进先出后进先出LIFOa1a2an栈底栈底栈顶栈顶湖北大学公共计算机课部2006年11月21日A.线性结构线性结构线性表线性表栈栈后进先出后进先出LIFO队列队列先进先出先进先出FIFOa1,a2,a3,a4,an-1,an队队列列示示意意图图队队头头队队尾尾湖北大学公共计算机课部2006年11月21日树形结构树形结构例例:全校学生档案管理的组织方式全校学生档案管理的组织方式B非线性结构非线性结构湖北大学公共计算机课部2006年11月21日1423例例:数据结构数据结构B(D,R)D=1,2,3,4R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)213例例:数据结构数据结构C(D,R)D=1,2,3R=,图形结构图形结构湖北大学公共计算机课部2006年11月21日30u2.存储结构（物理结构存储结构（物理结构）存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见的存储结构有：n顺序存储结构顺序存储结构n链式存储结构链式存储结构n索引存储结构存储结构注意：注意：n数据元素在计算机数据元素在计算机存储存储空间中的位空间中的位置关系与它们的置关系与它们的逻辑逻辑关系关系不一定是相不一定是相同同的。的。n一个逻辑数据结构可以有多种存储一个逻辑数据结构可以有多种存储结构，且不同的存储结构影响数据处结构，且不同的存储结构影响数据处理的效率理的效率。31u3.数据的运算数据的运算n检索检索n插入插入n删除删除n更新更新n排序排序常见的数据结构常见的数据结构 1.线性表线性表 2.栈和队列栈和队列 3.树树湖北大学公共计算机课部2006年11月21日33 线性表（线性表（线性表（线性表（LinearListLinearList）线性表是由线性表是由n（n0）个数据元素）个数据元素a1，a2，ai，an组成的一个有限序列。组成的一个有限序列。其中其中n称作表的称作表的长度长度，当，当n=0时，称作时，称作空表空表。线性表的特点：线性表的特点：1.线性表中所有元素的性质相同。线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继有且仅有一个前驱和一个后继.第一个数据元素无前驱第一个数据元素无前驱,最后一个数据元素无后继。最后一个数据元素无后继。3.数据元素在表中的位置只取决于它自身的序号。数据元素在表中的位置只取决于它自身的序号。34设线性表为设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态2、链式存储结构、链式存储结构1 a12 a23 a34 a45 a5671、顺序存储结构、顺序存储结构线性表的存储结构有两种：线性表的存储结构有两种：35线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表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为该类型数所占的字节顺序存储结构，将顺序存储结构，将逻辑上相邻逻辑上相邻的数的数据元素存储在据元素存储在物理上相邻物理上相邻的存储单的存储单元里元里,具有以下特点具有以下特点:1.随机存取。随机存取。2.作插入或删除操作时，需移动大作插入或删除操作时，需移动大量元数。量元数。3.长度变化较大时，需按最大空间长度变化较大时，需按最大空间分配。分配。4.表的容量难以扩充。表的容量难以扩充。36顺序表的插入运算顺序表的插入运算顺序表的插入运算顺序表的插入运算在线性表顺序存储情况下，要插入或删除一个元素，在线性表顺序存储情况下，要插入或删除一个元素，都会由于都会由于数据元素的移动而消耗大量的处理时间数据元素的移动而消耗大量的处理时间，所以，所以这种存储方式对于小线性表或其中数据元素不经常变动这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。的线性表是合适的。ai-1.a2a1alengthai+1aixai-1.a2a1alengthai+1ai顺序表的删除运算顺序表的删除运算顺序表的删除运算顺序表的删除运算37线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针1.比顺序存储结构多用空比顺序存储结构多用空间间(存储密度小存储密度小)(每个节点都由数据域每个节点都由数据域和指针和指针域域组成组成)。2.逻辑上相邻逻辑上相邻的节点的节点物理物理上不必相邻上不必相邻。3.插入、删除灵活插入、删除灵活(不必移动节点，只不必移动节点，只要改变节点中的指针要改变节点中的指针)。4.非随机存取。非随机存取。38线性链表的删除运算线性链表的删除运算线性链表的删除运算线性链表的删除运算线性链表的插入运算线性链表的插入运算线性链表的插入运算线性链表的插入运算采用链式存储结构，采用链式存储结构，存储空存储空间开销较大间开销较大，但是进行插入，但是进行插入和删除运算和删除运算不会不会造成大量元造成大量元素的移动。素的移动。39循环链表循环链表是另一种形式的链式存储结构。是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头它的特点是表中最后一个结点的指针域指向头结点。结点。可以从任何一个结点开始访问链表的所有结点可以从任何一个结点开始访问链表的所有结点.a1a2a5a3a4HEAD31951040双向链表双向链表在在每每个个结结点点中中设设置置两两个个指指针针，一一个个指指向向后后继继，一一个个指指向向前前驱驱。可可直直接接确确定定一一个个结结点点的的前前驱驱和和后后继继结结点点。可可提提高效率。高效率。datanextbeforeHEADHEAD412.栈和队列栈和队列栈和队列都是特殊的线性表。栈和队列都是特殊的线性表。u栈（栈（Stack）及其基本运算）及其基本运算u队列（队列（Queue）及其基本运算）及其基本运算u循环队列及其基本运算循环队列及其基本运算421.栈栈栈栈是限定仅在是限定仅在表尾表尾进行插入或删除操作的线性表。进行插入或删除操作的线性表。栈顶栈顶表尾。表尾。栈底栈底表头。表头。空栈空栈不含元素的空表。不含元素的空表。a1a2an栈底栈底栈顶栈顶入栈入栈出栈出栈栈栈s=(a1,a2,an)后进先出（后进先出（LIFO）先进后出（先进后出（FILO）432.栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算a1a2top顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量一般用一维数组表示，设置一个简单变量top指示栈顶位置，指示栈顶位置，称称为为栈顶指针栈顶指针，它始终指向待插入元素的位置。它始终指向待插入元素的位置。基本运算：基本运算：入栈：入栈：PUSH出栈：出栈：POP读栈顶元素：读栈顶元素：gettop在顺序栈中插入在顺序栈中插入和删除运算不需和删除运算不需要移动表中其他要移动表中其他数据元素数据元素。44例子：例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空栈：空栈：topbase非空栈：非空栈：top始终在栈顶元素的后一个位置始终在栈顶元素的后一个位置栈的元素个数：栈的元素个数：top-base上溢上溢下溢下溢3.队列队列定义：一种特殊的线性结构，限定只能在表的一端进行定义：一种特殊的线性结构，限定只能在表的一端进行插入，在插入，在表的另一端进行删除的线性表表的另一端进行删除的线性表。此种结构称。此种结构称为为先进先出（先进先出（FIFO）表）表。a1,a2,a3,a4,an-1,an队队列列示示意意图图队队头头队队尾尾 e3 e4 (c)(c)e1,e2出队，出队，e4入队入队 队队满满rear=3front e1 e2 e3 (b)rearfront(b)e1,e2,e3入队入队4.队列的顺序存储结构及其基本运算队列的顺序存储结构及其基本运算 3210 (a)rear=front=-1(队空）队空）rearfront空队列空队列:非空队列非空队列:队列元素个数队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终始终指向队尾元素的位置指向队尾元素的位置rear-front循环队列循环队列将队列存储空间的最后一个位置绕到第一个将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。位置，形成逻辑上的环状空间。e3 e4 rear=3front队队列的列的顺顺序存序存储结储结构一般采用构一般采用队队列循列循环环的形式。的形式。计计算循算循环队环队列的元素个数：列的元素个数：“尾指尾指针针减减头头指指针针”，若，若为负为负数，再加数，再加其容量即可。其容量即可。48数据存储结构方面的考题数据存储结构方面的考题1：数据的存：数据的存储结储结构是指构是指（2005年年4月）月）A)存存储储在外存中的数据在外存中的数据B)数据所占的存数据所占的存储储空空间间量量C)数据在数据在计计算机中的算机中的顺顺序存序存储储方式方式D)数据的数据的逻辑结逻辑结构在构在计计算机中的表示算机中的表示2：下列叙述中正确的是下列叙述中正确的是（2009年年3月）月）A）栈栈是是“先先进进先出先出”的的线线性表性表B）队队列是列是“先先进进后出后出”的的线线性表性表C）循）循环队环队列是非列是非线线性性结结构构D）有序）有序线线性表既可以采用性表既可以采用顺顺序存序存储结储结构，也可以采用构，也可以采用链链式存式存储结储结构构3.数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于。4.下列数据结构中，属于非线性结构的是下列数据结构中，属于非线性结构的是A）循环队列）循环队列B)带链队列带链队列C)二叉树二叉树D）带链栈）带链栈答案：答案：D。答案：答案：D。答案：线性结构。答案：线性结构。答案：答案：c495。下列叙述中正确的是（下列叙述中正确的是（）。）。（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，150一个栈的入栈序列是一个栈的入栈序列是a,b,c,d,e则栈的不可能的输出序列是：（）则栈的不可能的输出序列是：（）A、edcbaB、decbaC、dceabD、abcdeu栈之根本栈之根本先进后出（先进后出（firstin，lastout）选项选项1是是abcde先入栈，然后依次出栈，正好是先入栈，然后依次出栈，正好是edcba选项选项2是是abcd先依次入栈，然后先依次入栈，然后d出栈，出栈，e再入栈，再入栈，e出栈出栈选项选项3是错误的，是错误的，d出栈了，出栈了，abc一定已经入栈，那么一定已经入栈，那么abc只能只能以以cba的顺序出栈，的顺序出栈，选项选项4是是a入栈，然后入栈，然后a出栈；出栈；b再入栈，再入栈，b出栈。依此类推出栈。依此类推519.设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向指向队头元素的前一位置队头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该循环队列中共有，则该循环队列中共有【2】个元素。个元素。（2010年年3月）月）8。假。假设设用一个用一个长长度度为为50的数的数组组（数（数组组元索的下元索的下标标从从0到到49）作）作为栈为栈的存的存储储空空间间，栈栈底指底指针针bottom指指间栈间栈底底元素，元素，栈顶栈顶指指针针top指向指向栈顶栈顶元素，如果元素，如果bottom=49，top=30（数（数组组下下标标），），则栈则栈中具有中具有【】个元素。个元素。（2009年年3月）月）答案：答案：19答案：答案：1552树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。u树的概念树的概念u二叉树的概念二叉树的概念u二叉树的存储二叉树的存储u二叉树的遍历二叉树的遍历3.树与二叉树树与二叉树53T3T2T1树的概念树的概念树的概念树的概念un个结点的有限集。（个结点的有限集。（n=0）仅有一个根结点，结点间仅有一个根结点，结点间有明显的层次结构关系。有明显的层次结构关系。n若若n=0，则称为空树；，则称为空树；否则，当否则，当n1时，其余结点被时，其余结点被分成分成m（m0）个互不相交的子集）个互不相交的子集T1，T2，.，Tm，每个，每个子集又是一棵树。子集又是一棵树。ACGDHIJMBELKF结点结点（Node）：树中的）：树中的元素元素父结点（根）:在在树结树结构中，每一个构中，每一个结结点只有一个点只有一个前件前件子结点:每一个每一个结结点可以有多个点可以有多个后件后件结点的度结点的度（Degree）：结点拥有的子树数）：结点拥有的子树数(后件后件)。叶子叶子（Leaf）：度为）：度为0的结点。的结点。树的度：树的度：结点所具有的最大的度结点所具有的最大的度.结点的层次：结点的层次：从根结点开始算起，根为第一层。从根结点开始算起，根为第一层。树的深度树的深度（Depth)：树中结点的树中结点的最大层次数最大层次数。ABDFECGHIJKM二叉树二叉树（Binary Tree）的定义）的定义二叉树的五种基本形态二叉树的五种基本形态二叉树是一种很有用的非线性结构，具有以下两特点：二叉树是一种很有用的非线性结构，具有以下两特点：非空二叉树非空二叉树只有一个根结点只有一个根结点；每每一一个个结结点点最最多多有有两两棵棵子子树树（左左子子树树、右右子子树树），且且子树有左右之分，次序不能颠倒。子树有左右之分，次序不能颠倒。空二叉树空二叉树仅有仅有根结点根结点右子树右子树为空为空左子树左子树为空为空左右子树左右子树均非空均非空性质性质1:二叉树的第二叉树的第i层上至多有层上至多有2i-1（i 1）个结点。）个结点。二叉树的基本性质二叉树的基本性质423167891011121314155性质性质2:深度为深度为k的二叉树中至多含有的二叉树中至多含有2k-1个结点。个结点。性质：性质：对任何一棵二叉树对任何一棵二叉树T，如果其叶子结点数为，如果其叶子结点数为n0,度度为为2的结点数为的结点数为n2,则则n0=n2+1,n2=n0-1。其结点总数为：其结点总数为：n=n0+n1+n2=2n0+n1-1性质性质4：具有具有n个结点的二叉树，其深度至少为个结点的二叉树，其深度至少为log2n+1,其中其中log2n表示取表示取log2n的整数部分。的整数部分。n n满二叉树满二叉树满二叉树满二叉树：如果一个深度为如果一个深度为h的二叉树拥有的二叉树拥有2h-1个个结点，则将它称为结点，则将它称为满二叉树满二叉树。n n完全二叉树完全二叉树完全二叉树完全二叉树：有一棵深度为有一棵深度为h，具有，具有n个结点的二个结点的二叉树，若将它与一棵同深度的满二叉树中的所有叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号且该二叉树中的每个结点分别与满二叉树中编号为为1n的结点位置一一对应，则称这棵二叉树为的结点位置一一对应，则称这棵二叉树为完全二叉树完全二叉树。满二叉树满二叉树423167891011121314155特点：每一层上都含有最特点：每一层上都含有最大结点数大结点数2i-1深度为深度为k的满二叉树拥有的满二叉树拥有2k-1个结点个结点完全二叉树完全二叉树4231678910 11125特点：特点：(1)(1)除最后一层除最后一层外，每一层都外，每一层都取最取最 大结点数大结点数(2)(2)最后一层最后一层结点都集中在该结点都集中在该层层最左边最左边的若干位置。的若干位置。12131415891011456712312138910114567123已知总结点数，求各已知总结点数，求各类型结点数类型结点数n0,n1,n21213891011456123非完全二叉树非完全二叉树深度为深度为4的的完全二叉树完全二叉树84567123性质性质1：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为112345678910121结点数结点数n=2n=6n=7n=8n=12深度深度k=2k=3k=3k=4k=4性质性质2：如果对一棵有：如果对一棵有n个结点的完全二叉树的结点按层个结点的完全二叉树的结点按层序编号，则对任一结点序编号，则对任一结点i(1=i=n,则结点则结点i无左孩子无左孩子(结点结点i为叶子结点为叶子结点);否则其左孩子否则其左孩子Lchild(i)是结点是结点2i。(3)如果如果2i+1n,则结点则结点i无右孩子无右孩子;否则其右孩子否则其右孩子Rchild(i)是结点是结点2i+1。(1)如果如果i=1,则结点则结点i是二叉树的根是二叉树的根,无双亲无双亲(父结点父结点);如果如果i1,则双亲则双亲Parent(i)是结点是结点i/2。112345678910121例：例：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；641 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。65二叉树的存储二叉树的存储二叉树的存储二叉树的存储u在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。LlinkinfoRlink二叉树的存储结点的结构二叉树的存储结点的结构ABDCFGEA G E F B C Dt先序遍历：先序遍历：DLR中序遍历：中序遍历：LDR后序遍历：后序遍历：LRDADBCDL