全国计算机等级考试《二级公共基础知识》【教材精讲+真题解析】讲义与视频课程【12小时高清视频】.docx

内容简介为了带助考生以利通过全国计算机等级考试.我们根据全国计算机等级考试最新公告、考试大纲以及相关考试用书,精心编写制作了全国计算机等级考试“二徼公共基础知识”辅导系列：1 .全国计算机等级考试i.:级公共堪础知识3【教材精讲+直册解析】讲义与视频课程【12小时高清视翔】2 .全国计算机等级考试二级公共基Bh知识题库【历年JX题+章节题库+模拟试题】3 .全国计算机等级考试二级公共基础知识专用教材【考纲分析+考点精讲+真题演燎+强化习题】本书主要包括以下两部分内容：1 .教材精讲【含12小时视频讲解】，遵循”:线公共基础知识考试大纲(20I8/&)"的考察要求及指定参考教材和相关法律法规，Z师而清视领深入剖析考试大纲，全面讲解教材重点难点内容，帮助学员巩固知识,梳理逻辑,轻松应考.2 .其应解析,新选历年考试真遨.每道真应均提供详尽答案解析，学员可以熟悉观阳的考试特点，巩固知识点弁测试自己的水平。圣才电子书编辑部公共基础知识网授精讲班主讲效邦：赵亮（二级）M光,毕业于中科院研究生院的计算机科学与技术专业.常年从事计算机学科的研究和教学.有较强的专业知识和教学能力，能膨根据学科特点，深入浅出的讲解课程内容，使学生快速理好掌握.达到教学目标.授课特点：亲和力强，课堂城It1.轻松，授课思路明朗，能够让枯煤的知识形象生动，M助学员轻松掌握核心知识点,深受广大学员喜姿.教材精讲部分视版讲解15第I章数据结构与算法视频讲解61.1 算法61.2 数据结构的卷本概念101.3 线性表及其顺序存储结构121.4 栈和队列151.5 线性链表191.6 树与二叉树241.7 查找技术301.8 排序技术32第2章程序设计基础视频讲解392.1 程序设计方法与风格392.2 结构化程序设计402.3 面向对象的程序设计44第3章软件工程基础视频讲解1493.1 软件工程基本概念493.2 结构化分析方法533.3 结构化设计方法583.4 软件测试683.5 程序的调试77第4章数据库设计基础视频讲解794.1 数据库系统的基本概念794.2 数据模型844.3 关系代数904.4 数据库设计与管理98立即解析部分107全国计算机等级考试二级公共加础知识-SS精选(一)107全国计算机等级考试二级公共基础知识3口即精选(二)109考试形式I.公共法础知识不单独考试，与其他二级科目组合在一起，作为：线科11考核内容的一部分,2.考试方式为上机考试,10道选择起.占10分.知识点分布1 .数据结构与算法2 .程序设计法础3 .软件工程基础4 .数据库设计法础大纲星本要求1 .掌握算法的她本概念，2 .掌旌基本数楙结构及其操作.3,掌握般本排序和杳找算法。4 .常旌逐步求精的结构化程序设计方法.5 .掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。家旌数据庠的基本知识,了解关系数据库的设计.第1章数据结构与算法1«MK讲解I1 .算法的基本概念：算法更杂度的概念和意义(时间更杂度与空间更杂度).2 .数据结构的定义；数据的定轨结构与存储结构；数据结构的图形表示：线性结构与非践性结构的概念。3 .线性表的定义：线性表的项序存储结构及其插入与捌除运算.4 .栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5 .线性单鞋表、双向性表与循环鞋表的结构及其基本运算.6 .树的范本概念；二叉树的定义及其存储结构；：乂树的前序、中序和后序遗历，7 .顺序查找与二分法查找©法：基本排序以法交换类排序,选择类排序,辅人类排序).1.1算法一、算法的基本概念1 .算法的定义豫法是指解题方案的准确而完整的描述，即除法是对特定向理求解步骤的一种描述“【注意】算法不等于程序，也不等于计算方法。2 .算法的基本特征(I)可行性(Effecdveness):算法中的特一个步骤必须能朝实现，执行的站果要能够达到预期的目的。<2)确定性(Dd1.nitencss):算法中的母个步骤都必须是有明确定义的，不允许有模棱两可的解择或多义性，<3)有穷性(FiniIenCss)：徵法必须能在有限的时间(合理的时间)内做完，即算法必须能在执行有限个步.骤之后终止.<4)拥有足够的情Hb输入是否足鹿井正确，领出是否合理.初始状态是否正确.二、算法设计基本方法I.列举法<1)基本思想根据提出的问遨，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的.<2)特点简单.方使用计尊机进行大量列举：情况较多时工作量将会很大.<3)使用将马向SS有关的知识条理化、完备化、系统化，从中找出规律，行分类,减少列举最。【例1】今有鸡母一，值钱三：鸡翁一，假钱二；鸡雏一，值钱半.凡百钱买百鸡,问鸡母、鸡翁、鸡维各几何？假设买母鸡I只、公鸡J只、小璃K只.根据SS速，林略的列举算法描述如下：FORI=OTO100STEPIDOFORJ-OTOI(K)STEPIIX)FORK=OTOI(X)STEPIDOI1R(1+J+K=1OO)AND(3*I+2*J-M).5*K=100.O)THENPRINTU.K)END共有三层砧环，降层循环各制要循环IOI次，大约为100万次。优化后的算法FORI=OTO33STEPIDOFORJ=OTO50-1.5*ISTEPIDOK=!-I-J1F(3+I+2J+O.5*K=1.(X).()THENPRINTU.KEND共有两层循环循环次数为33£(51-1.5/)894I=Q2.归纳法<1)基本思想通过列举少出的特殊情况,经过分析最后找出一般的关系.<2)特点归纳是一种抽象，即从特殊现象中找出一做关系，<3)使用由于在切纳的过程中不可能对所行的情况进行列举.因此,最后由归纳得到的结论还只是种物冽,还需要时这种猜冽加以必要的证明.实际上.通过精心观察而得到的猜测解不到证实或以后证明猜测玷错的，也是常H的事.3 .递推(1)基本思想从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果.(2)特点本质上同尸归纳法，递推关系式往往是归纳的结果。(3)使用速推算法在数值计算中是极为常见的.但是,对于数值型的递推算法必须要注意数值计算的稳定件问起.4 .递归(1)基本思想为了降低问遨的复杂程度,符问题逐层分解,最后归结为一些最简单的何麴,这种符问题逐层分解的过程,实际上并没有对问题进行求解，而只是当解决了靛后那些最简雎的问胆后，再沿着原来分解的逆过程逐步进行综合.(2)特点结构清晰.可读性强，<3)使用递归在可计算性理论和算法设计中占有很虫要的地位。(4)分类直接递归(自己调用自己)和间接递归(P陶用Q.Q乂调用P).【例2】编写一个过程，对于输入的参数n,依次打印输出自然数I到n.非递归算法:wt(in(n)FORk=1.TOnSTEPIDOPRINTkRETURNI递归算法：witHintn)(IF(n0)THENWrtKn-DPRINTnIRET1.RN5,减半递推技术所谓“减半是指将问题的序模减半,而问题的性质不变：所谓“递推是指重复“减半”的过程.【例13设方程f<x>=O在区间a,b上有实根，且f（八）与f(b>界号.利用二分法求该方程在区间同b)上的一个实根，用二分法求方程实根的减半递推过程如下：(1)首先取给定区间的中点C=<a+b)/2.<2)然后判断f(C)是否为0：如果f(c)=0,则说明C即为所求的根，求解过程结束：如果f(c)0,则根据以下原则将原区间减半：若f（八）f(c)<0,则取原区间的前半部分：若f(b)f8)<0.则取原区间的后半部分.(3)班后判断战半后的区间长度是否己羟很小：若a-bVe,则过程结束，取(a+b)/2为根的近似值：若a-b妾e,则Hi复上述的减半过程,6.回溯法(1)基本思想通过时问题的分析，找出一个解决问时的线索，然后沿希这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退,换别的路线再进行试探.这种方法称为回溯法。(2)特点在工程上，有些实际问超很难归纳出一组简单的递推公式或直观的求解步骡，并旦也不能进行无限的列举.对于这类向SS,一种有效的方法是“试”。三、算法复杂度主要包括时间坡杂度和空间更杂度.1 .以法的时间史杂度<1)定义执行算法所需要的计算工作量.(2)衡量标准通常用算法在执行过程中所需基本运算的执行次数来度量笄法的工作量，律法所执行的基本运算次数还与问题的规模有关.综上所述.算法的工作限用算法所执行的基本运算次数来度限,而算法所执行的基本运豫次数是何时规模的函数，即算法的工作录=f(1).(3)存在问题算法所执行的基本运尊次数还可能与特定的输入行关.而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来.(4)解决方法平均性态(AverageBehavior)用各种制定输入下的基本运算次数的加权平均值来度量算法的工作量：&)=PC(X)XdSt坏情况红杂性(WOrStC3$CComp1.exity>规模为n时，算法所执行的般本运獴的坡大次数：W(n)=maxr(x)wd“2 .豫法的空间更杂度【定义】执行这个算法所需要的内存空间.< 1)匏法程序所占的空间：< 2)输入的初始数据所占的存储空间；< 3)算法执行过程中所需要的额外空间。【注意】如果额外空间量相对于问区规模来说是常数，则称该算法是像地r作的.在许多实际问遨中，为了M少饵法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间,【考即1】打法的时间复杂度是指().A,执行算法程序所衙要的时间B.蚱法程序的长度1 .数据的逻帆结构<1）定义反映数据元素之间逻辑关系的数捌结构.一个数据结构应包含以下两方面的信息：表示数据元素的佶息：表示各数据元素之间的前后件关系，<2）数据的逻轼结构有两个要素：一是数据元素的集合,通常记为D：二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R：即一个数据结构可以表示成B=（D.R）,【例4】一年四季的数据结构Ur以表示成B=（D.R）D=1.夏，秋，冬R=（#,熨），（夏，秋），（秋，冬2 .数据的存储结构定义：数据的逻辑结构在计算机存储空间中的存放形式.【注意】各数据元素在计徵机存储空间中的位置关系与它们的能卷关系不一定是相同的，而且一般也不可能相同.在数据的存储结构中,不仅要存放各数据元案的信息.还需要存放各数据元素之间的前后件关系的信息.常用的存储结构书1顺序、t接、索引等存储结构.采用不同的存储结构，其数据处理的效率是不同的.二、数据结构的图形式示一个数据结构除了用二元关系我示外，还可以直观地用图形发示.<1）时于数据集合D中的绿一个数据元素用中间标有元素例的方框表示，一般称之为数据结点，并简称为结点：<2）对于关系R中的每一个二元组,用一条目向线段从前件结点指向后件结点,有时箭头可省去.*43图1-1一年四季数据结构的图形表示图（段性）图1-2家庭成员间关系数据结构的图形衣示（树型结构【考时】下列叙述中正确的是（KA,雄性衣是线性结构B.栈与队列是非线性结构C.循环链友是非线性结构D.二叉树是践性结构【答案】A【解析】选项A正确：选项B.极和队列都是线性结构，二者区别足.栈只允许在一端插入和呀除.队列只允许在一珀插入，在另一端删除：选项C.循环法表是压性表的能式存储结构：选项D,二叉树是一种典型的非线性结构。三、雄性结构与非战性结构根据数据结构中各数据元素之间前后件关系的友杂程度,一般将数据结构分为两大类型：线性结构与非线性结构.如果一个非空的数据结构满足下列两个条件：<1）有且只有一个根结点;<2）每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构,线性结构乂称线性表.【注意】在一个浅性结构中插入或删除任何一个结点后还应是规性结构.如果个数据结构不是线性结构.则称之为非雄性结构。【考即】设数据集合为D=1.,3.5.7.9）,D上的关系为R,卜列数据结构B=<D,R）中为非战性结构的是（）.A.R=(5-I),B.R=(9.7).C.R=(I.9).D.R=(1.3).【答案】D<7,9，<1.7>.(9.3>I(1.3),(7,I),(3,5)(9.7).(7,5).(5,3)<3.5),(5.9)t解析】如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点以多有一个前件，也最多有一个后件。则该数据结构为雄性结构,选项A：选项B：选项C:选项D：5是根结点,5的后件是1.9是根结点.9的后件是7,I是根结点，I的后件是9,1是根结点，1的后件是3,1的后件是7.7的后件是I.9的后件是7,3的后件是S.7的后件是9.1的后件是3.7的后件是5,S的后件是9,9的后件是3.3的后件是5,5的后件是3,7也是根结点,故选项A是线性结构：故选项B是线性结构：故选项C是线性结构；没有前件也没有后件,城性数据结构第一个条件不满足,故选项D是非线性结构,即选项D正确.1.3线性表及其序存俺结构一、线性表的基本概念线性表（1.inear1.ist）是最简单、最常用的一种数据结构.如：一个n维向麻、矩阵，学生情况登记表.性表是由n（n>0）个数据元索a,a>，a殂成的一个有限序列，表中的每一个数据元素，除了第个外，有且只有一个前件，除了最后一个外，有且只有一个后件,即成性表或是一个空表，或可以表示为（a1.a2.ai,.ao）,其中&（i=1.,2.,n>是M于数据对象的元素,通常也称其为线性表中的一个结点.非空规性表有如下一些结构特征：< 1>有且只有一个根结点a它无前件；< 2）有且只有一个终端结点a11,它无后件：< 3）除根结点与终端结点外.其他所有结点有且只有一个前件也有且只有一个后件.【说明】线性表中结点的个数n林为战性去的长度.当n=0时，林为空;表。二、线性去的蹶序存储结构1 .特点<I）级性衣中所有元素所占的存储空间班连续的：<2）设性表中各数据元素在存储空间中是按逻耕顺序依次存放的。在线性表的顷序存储结构中，其前后件两个元素在存储空间中是紫钠的，且前件元素一定存储在后件元素的前面.图1-3线性表的眼序存储结构【注意】在程序设计语方中，通常定义一个一维数组来表示或性表的顺序存储空间，在用傩数组存放战性表时，该啾数组的长度通常要定义得比雄性表的实际长度大些，以便对雄性表进行各种运算，特别是插入运算，2 .线性表的相关操作（I）插入；在践性表的指定位词处加入一个新的元素。< 2）刷除：在城性表中删除指定的元素。< 3）查找：在线性表中查找某个（或某些）特定的元素.< 4）排序：对线性表中的元素进行整序（即线性表的.< 5）分斛；按要求将一个规性表分解成多个跷性去，< 6）合并：按要求将多个线性衣合并成一个线性表，< 7）复制一个线性表.< 8）逆转：逆转一个线性表.三、顺序表的插入运算【例5】长度为8的线性表联序存储在长度为IO的存砧空间中.在第2个元索之前插入一个新元素87.然后在线性表的第9个元素之前植入一个新元素14.129129129叵-2182872873563183184634564565355635636246356357317247248478318319叵94791410101047（八）长度为8的线性表线性表的存横空间从1到m.(b)插入元索87后的线性表(C)插入元素14后的线性表图1-4践性表在IBi序存储结构下的插入线性表的长度为n(nSm),插入的位置为i(i表示在第i个元本之前插入,V(Ij1.O)V(IJO)V(IJO)线性表的插入操作如下：第一步首先处理以下三种异常情况：当存储空间已满(即n=m)时为"上溢”错i5i,不能进行插入，算法结束；当i>n时，认为在最后一个元素之后插入：当i<1.Br,认为在第1个元素之前插入.第二步从城后一个元素开始，宜到第i个元素，每一个元素往后移动一个位置.第三步将新元素插入到第i个位置，线性衣的长度加I。四、顺序表的删除运算【例6】长度为8的线性农坂序存储在长度为IO的存储空间中.现在要求捌除税性表中的第I个元素.再删除线性表中的笫6个元素。V(IrIO)V(IJO)V(I=IO)I29I18!18218256956356363363463435435535524524624631647731747784788999IO1010（八）长度为8的线性表(b)耕除元素29后的线性表(C)微除元索31后的线性及图15践性表在顺序存储结构下的删除战性表的存储空间从1到m,我性表的长度为n(nm),删除的位置为i(表示删除第i个元素线性表的删除操作如下：第一步首先处理以下两种异常情况：当线性表为空（KPn=O）时错误,不能进行删除,算法结束:当i<1.或i>n时，错误，不能进行删除，算法结束.第：步删除战性衣中的第i个元素。第三步从第i+1个元素开始，起到最后一个元泰，其中年一个元素均依次往前移动一个位置。线性表的长度减小1.1.4机和队列一、枝及其基本运算1 .什么是栈【定义】限定在一雉进行插入与删除的雄性表【说明】允许插入与删除的一端称为栈顶（指针top,而不允许插入与删除的另一端称为栈底（指针bottom.栈是按照“先进后出“（FI1.O）的原则组织数抵.栈具有记忆作用。往栈中插入一个元素称为入校运算，从枝中删除一个元素（即蒯除校顶元素）称为出栈运洋.人栈退栈栈顶top-栈底bottom图1-6栈示意图2,栈的顺序存储及其运算图1-7（八）是容畸为10的栈眼序存储空间，栈中已有6个元素；图1-7<b）与图1-7（c）分别为入栈与退栈后的状态.1010109998top-8Y877Xtop7Xtop6F6F6F5E5E5E4D4D4D3C3C3C2B2B2Bbottom1Abottom1.Abottom1.A（八）有6个元素的栈（b）插入X与丫后的栈（C）退出一个元素后的栈图1-7校在顺序存储结构下的运算S(IJO)S(IJO)S(IJO)<1.>入栈运算入栈运算是指在栈顶位置插入一个新元素。操作过程如F：首先判断栈蹊指针是否已经指向存砧空间的最后一个位置.如果是则说明栈空间已满.不可能再进行入栈悚作（这种情况称为栈“上溢”错误），究法结束.然后将栈顶指针进一（即top加1）。最后将新元竣X插入栈顶指针指向的位置.<2>退栈运算退栈运算是指取出栈顶元素并赋给一个指定的变ht.操作过程如下：首先判断栈项指针是否为0,如果是，则说明栈空，不可能迸行退栈操作（这种情况称为栈“下溢”错误），算法结束。然后将极原元素（栈顶指针指向的元素）赋给一个指定的变量.最后构枝顶指竹退一（RPtopMI）.<3>设栈顶元素读栈顶元泰是指将栈顶元素赋给一个指定的变境.操作过程如K：首先判断栈痍指针是否为0.如果是.则说明栈空,读不到栈膜元素,算法结束.然后将极顶元素献给指定的变属y【注球】这个运算不蒯除栈顶元素，只是将它的伯献给一个变最，因此，在这个运算中栈顶指针不会改变。【考即】下列关于栈的叙述中正确的是（）。A.在栈中只能插入数据B.在校中只能捌除数据C.栈是先进先出的雄性表D.栈是先进后出的戏性表E.栈是一种非线性结构【答案】D【解析】在栈中，只允许在栈顶一端进行插入和删除，所以A、B错误；队列是“先进先出”的战性表，栈是“先进后出”的线性表，所以C、Ef1.fi5J.D1E.,二、队列及其基本运算1 .什么是队列加入的元索总是插入到我性表的末尾，并且又总是从线性表的头部取出（蒯除）元素，这种线性表称为队列。【说明】允许插入的一湘称为队尾（rear）,允许删除的一蟠称为队头（front）.在队列中按照“先进先出”的原则进行操作。front图18艮有6个元Mt的队列示意图rearfrontAfrontfront-BBBCCCrearDrearDDrcarE（八）一个5(列(b)删除-图一个元素六1-9队列运号的队列以示意图(C)插入为:索E后白勺队列退队ABCDEF人队【考即】下列关于队列的叙述中正确的是().A.在队列中只能插入数据B.在队列中只能IM除数据C.队列是先进先出的线性表D.队列毡先进后出的税性表【答案】C【解析】在队列中,只允许在一端进行插入，在另一端进行刷除，所以A.B错误：队列是“先进先出”的线性表,栈足“先进后出”的线性表,所以D错误，选择C.2 .循环队列及其运算【定义】循环队列是将队列行储空间的最后一个(置绕到第一个位置，形成逻轼上的环状空间,供队列循环使用.rearfront图1-10循环队列存储空间示意图用队尾指针rear指向队列中的队尾元素，用排头指针from指向排头元素的前个位汽,在实际使用循环队列时，为了能区分队列消还是队列空，通常还需增加一个标志s,s值的定义如卜:0表示队列空I表示队列非空Ih此可以得出队列空与队列满的条件如下:队列空的条件为s=0：队列港的条件为S=I且front=rear.（八）具有6个元素的循环队列(b)加入X、Y后的循环队列(C)退出一个元求后的循环队列图1-11循环队列运算示意图<1)入队运算入队运算是指在循环队列的队星加入一个新元素.操作过程如下：首先判断第环队列是否满。当循环队列非空(S=I)且队尾指针等于排头指计时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”,此时算法结束。然后物队尾指针进一(即rear=rear+1).并当rear=m÷I时置rear=1.最后将新元素X插入认足指针指向的位置，并旦式锵环队列年空标志.<2)退队运算退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变埴.操作过程如卜：首先判断循环队列是否为空.当循环认列为空(S=O)M,不能进行退队运算.这种情况称为“下滥”.此时算法结束.后将后头指针进(即from=from+1)，井当front=m+1RtW.front=I.再将排头指针指向的元素赋给指定的变ft.最后判断退队后循环队列是否为空.当fmnmar时置循环认列空标志<Ws=0).8SJ设循环队列为QU：m),其初始状态为fmm=rear=m.羟过一套列入队与退队运算后，front=30, rear=10,现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为().A. 19B. 20C. m-9D. m20【答案】D【解析】在该循环队列中作股序查找,最坏情况下需要比较的次数,实际上就是求循环队列中元素的个数.元素的个数=(rear-front+m)modm=(1030+m)nx>dm=m-20,选项D正确CIS线性使表一、线性链表的基本概念【定义】线性交的健式存储结构称为线性能表.魏性箍龙的数据结构包括两部分，一是数据元素的值，二是数据元素之间的前后件关系。存储序号数据域指针域*1V(i)NEXT(i)图1-12践性链衣的一个存储结点为什么用雄性琏表？<1）线性表顺序存储结构存在的缺点：1而入或捌除过程中需要移动大量的数据元素.出现线性表的存储空间己满，但还需要插入新的元素时，就会发生“上滋”错误。线性表的顺序存储结构不便于存储空间的动态分配。<2）线性表链式存储结构存在的优点：在髓式存储结构中，存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的，【说明】在线性性表中.用一个专门的指针HEAD指向线性鞋表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号），线性衣中最后一个元素没有后件.因此，我性链表中最后一个结点的指针域为空（用NU1.1.或O表示），衣示链表终止。HEADII1H数据2I-IA-H数据nINU1.1.图1-13线性健表的逻辑结构在雄性表的链式存储结构中，各数据结点的存储序号是不连滨的，并旦各结戊在存储空间中的位置关系与逻辑关系也不一致。当HEAD=NU1.1.（或0）时称为空表.HEAD23456789IOV(i)NEXT(i)a29三1I&10即50（八）线性倭表的物理状态(b)战性储表的遗辑状套图1-14雄性健衣例I.双向域表对畿性链表中的姆个结点设置两个指针,一个称为左指针(Uink)，用以指向其前件结点；另一个称为右指针(R1.ink),用以指向其后件结点.HEAD图1-15双向箧衣示意图2.帝恰的栈栈也是雄性表，也可以采用Si式存储结构,图1/6带道的栈在实际应用中，带琏的栈可以用来收策计算机存储空间中所有空闱的存储结点,这种带徒的栈称为可利用栈,00(b)在从可利用栈取得一个结点P图1-17可利用栈及其运算3.帝链的队列队列也是线性表，也可以采用链式存储结构,frontrear（八）带链的队列(b)在带链的队列中插入一个新结点(C)在带徒的队列中删除一个结点图1-18带链的队列及其运算二、线性鞋表的基本运算践性链表的运算主要有以下几个：插入：在线性链表中包含指定元素的结点之前插入一个新元素捌除：在线性链表中删除包含指定元素的结点.合并：将两个税性链我按要求合弁成一个线性链友.分解：将一个战性链表按要求迸行分解。逆转复制的序查找1 .在线性链去中杳找指定元素从头指针指向的结点开始往后沿指针迸行扫描，直到后面1.I没有结点或下一个结点的数据域为X为止。因此,由这种方法找到的结点P行两种可能：当线性能衣中存在包含元素X的结点时，则找到的P为第一次遇到的包含元素X的前一个结点序号:当畿性链衣中不存在包含元素X的结点时,则找到的P为戏性链表中的以后一个站点号。2 .线性捷表的插入TOPHITTIT一UI0IHEADXIT-HIHX1.TTI0（八）原来的可利用栈与线性链表XXX_JfryTOPbITA1.IIA一HIQ(c)P插入到q之后图1-19线性桂表的插入3-找性流表的州除TOPHEAD（八）原来的可利用栈与线性fij表(O将襁删除的结怠P送回可利屈诟图1-20线性链表的删除三、循环链衣线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和时第一个结点的处理必须单独考虑.使空表与非空表的焰算不统一.I,循环链表的特点(1)增加了表头结点,其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元本的结点。结环链表的头指针指向表头结点.<2)循环箍发中最后一个结点的指忏域不是空，而是指向衣头结点,即在循环箍发中，所有结点的指针构成了一个环状链.HEAD表头结点<a)非空循环谄表HEAD_表头结点(b)至循环涟表图1-21循环链表的茂物状态2.循环链我与线性总能发相比主要布以下两个方面的优点：<1)在循环链表中，只要指出衣中任何一个站点的位应，就可以从它出发访问到表中其他所有的结点。线性单链去做不到这一点。(2)由于在循环链表中设置了一个表头结点，因此,在任何情况下循环燧表中至少有一个结点存在.从而使空衣与非空表的运算统1.6材与二叉树一、树的基本概念t定义】树(Tree)是一种简单的北线性结构，例中所有数据元素之间的关系具有明显的层次特性.图1-22学校行政层次结构树【说明】在树结构中.每一个结点只有一个前件，林为父结点,没有前件的结点只有一个.林为树的根结点,简称为树的根.在树结构中，个站点可以有.多个后件，它们都称为该结点的子结点，没有后件的站点称为叶子结点，在树结构中，一个结点所拥有的后件个数称为该结点的度.在树中,所有结点中的最大的度称为树的度.树中的结点数=树中所有结点的度之和+1”根结点在第I层。同一层上所有结点的所有子结点都在下一层。树的域大层次称为树的深收。树在计算机中的存储方式：树在计算出中通常用多重链表表示.多理琏表中的每个结点描述树中对应结点的信息.而每个结点中的最域(指针域个数将前树中该结点的度而定，va1.uc（值）degree（度）Iink1.Iink21.ink.图1-23机陡衣中的结点结构二、二叉树及其基本性质1 .什么是二叉二二叉树具有以下两个特点：非空二叉树只有一个根结点：每一个结点外多有的株子树，且分别称为该结点的左子树与右子树,t注意】在：叉树中，好一个站点的废以大为2,只有根结点的二叉树图1-24（b）深度为4的二叉树二叉树例2 .二叉树的基本性质【性短I1.在二叉树的第k层上，最多有N'（k>1.）个站点.【性麻2】度为m的二叉树球多有2n1个结点,即2叶22-叶+2"r=2nT°【性限3】在任意一棵二叉树中.度为O的结点（即叶子结点总是比度为2的结点多一个.【性质4】具有n个结点的二叉树，其深度至少为1.o&nj+1.其中Uog加表示取1.ogin的整数部分.【考SS1在深或为5的满二叉树中，叶子站点的个数为（>.A. 32B. 31C. 16D. 15【答案】C【解析】叶子结点的个数=2'ST=I6.【考胭2】设树T的度为%其中度为1,2.3,4的结点个数分别为4,2.1.I,则树T中的叶子结点数为<）。A. 8B. 7C. 6D. 5t答案】A【蚱析】结点数为所有结点的度数之和加I，同时,注意到叶子结点的度数为O,则总结点数（设叶子结点数为X1.4+2*2+31.+41+X*0+1=16.叶子结点数为X=164-2一I-1=8,3.满二叉的与完全二义四<1）满二叉树【定义】满二叉树是指这样的一种二叉树：除最后一层外，好一层上的所有结点都彳f两个子站点。【说明】在满二叉树中，每一层上的结点数都达到最大值，即在涌二叉树的第k层上有2kI个结点,且深度为m的满二叉树有2«-1个结点.（八）深度为2的满二叉树（b）深度为3的满二叉树（c）深度为4的满二叉树图125满二叉树<2>完全二又树【定义】所谓完全二叉树是指这样的二叉树：除最后一层外每一层上的结点数均达到蜃大值：在最后一层上只缺少右边的若干给点.除第一层外，集层上的结点都有两个子结点.图1-26完全二叉树完全二叉树还具有以卜两个性质：【性防5】具有n个结点的完全二叉树的深度为1.o"n+1.【性质6设完全二叉树共有n个结点.如果从根结点开始，按层序（每一层从左到右）用自然数I,2,n给站点进行编号、则对于编号为k（k=1.2,n）的结点有以下站论：若k=1.,则该结点为根结点，它没有父结点：若k>1.,则该结点的父结点端号为INT仆/2）。若2kWn,则编号为k的结点的左子结点娟号为2k：否则该结点无左子结点（显然也没有右子结点）.若2k+1n.W1.号为k的结点的右子结点编号为2k+1：否则谡结点无右子结点.SS1设一探完全：叉料共有700个站点，则该完全二叉树中的叶子站点数为（>.A.351B.350C.349D.348【答案】B【解析】完全二叉树所有结点的度数最大为2.设度为0的结点数为11o度为1的结点数为n,度为2的结点数为m,即有：n0+a+n2=700：根据二叉树性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个，知：m=n“一1.；根据完全二叉树的特点：n=0或I。联立G，易知：陶=350,所以选项B1.E确。三、二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点也由两部分组成：数据域叮指针域.1.Chi1.dVa1.ueR