2025年全国计算机等级考试二级数据结构与算法解析攻略

考点算法的复杂度1【考点精讲】算法的基本概念

1.计算机算法为计算机解题的过程实际上是在实行某种算法算法的基本特性可行性、确定性、有穷性、拥有足够的情报算法复杂度

2.算法复杂度包括时间复杂度和空间复杂度名称描述时间复杂度是指执行算法所需要的计算工作量空间复杂度是指执行这个算法所需要的内存空间考点逻辑构造和存储构造2【考点精讲】逻辑构造

1.数据的逻辑构造是对数据元素之间的逻辑关系的描述，它可以用一种数据元素的集合和定义在此集合中的若干关系来表达数据的逻辑构造有两个要素一是数据元素的集合，一般记为；D二是上的关系，它反应了数据元素之间的前后件关系，一般记为一种数据构造可以表到D R达（）B=D,R其中表达数据构造为了反应中各数据元素之间的前后件关系，一般用二元组来表达B D例如，假如把一年四季看作一种数据构造，则可表到达（）B=D,R｛春季，夏季，秋季，冬季｝D=二｛（春季，夏季），（夏季，秋季），（秋季，冬季）｝R存储构造

2.数据的逻辑构造在计算机存储空间中的寄存形式称为数据的存储构造（也称数据的物理构造）由于数据元素在计算机存储空间中的位置关系也许与逻辑关系不一样，因此，为了表达寄存在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储构造中，不仅要寄存各数据元素的信息，还需要寄存各数据元素之间的前后件关系的信息一种数据的逻辑构造根据需要可以表到达多种存储构造，常用的存储构造有次序、链接等存储构造次序存储方式重要用于线性的数据构造，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现链式存储构造就是在每个结点中至少包括一种指针域，用指针来体现数据元素之间逻辑上的联络考点线性构造和非线性构造3【考点精讲】根据数据构造中各数据元素之间前后件关系的复杂程度，一般将数据构造分为两大类型线性构造与非线性构造假如一种非空的数据构造满足下列两个条件（）有且只有一种根结点；1（）每一种结点最多有一种前件，也最多有一种后件2则称该数据构造为线性构造线性构造又称线性表在一种线性构造中插入或删除任何一种结点后还应是线性构造栈、队列、串等都线性构造假如一种数据构造不是线性构造，则称之为非线性构造数组、广义表、树和图等数据构造都是非线性构造考点栈4【考点精讲】栈的基本概念

1.栈（）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表在栈中，一端是stack封闭的，既不容许进行插入元素，也不容许删除元素；另一端是开口的，容许插入和删除元素一般称插入、删除的这一端为栈顶，另一端为栈底当表中没有元素时称为空栈栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最终才能被删除的元素栈是按照“先进后出”或“后进先出”的原则组织数据的例如，枪械的子弹匣就可以用来形象的表达栈构造子弹匣的一端是完全封闭的，最终被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最终才能被弹出栈的次序存储及其运算

2.栈的基本运算有三种入栈、退栈与读栈顶元素（）入栈运算入栈运算是指在栈顶位置插入一种新元素1（）退栈运算退栈是指取出栈顶元素并赋给一种指定的变量2（）读栈顶元素读栈顶元素是指将栈顶元素赋给一种指定的变量3考点队列5【考点精讲】队列的基本概念

1.队列是只容许在一端进行删除，在另一端进行插入的次序表，一般将容许删除的这一端称为队头，容许插入的这一端称为队尾当表中没有元素时称为空队列队列的修改是根据先进先出的原则进行的，因此队列也称为先进先出的线性表，或者后进后出的线性表例如火车进遂道，最先进遂道的是火车头，最终是火车尾，而火车出遂道的时候也是火车头先出，最终出的是火车尾若有队列二（，）Q ql,q2,…qn那么，为队头元素（排头元素），为队尾元素队列中的元素是按照…，的次序ql qnql,q2,qn进入的，退出队列也只能按照这个次序依次退出，即只有在，都退队之后，才ql,q2,…qn-1qn能退出队列因最先进入队列的元素将最先出队，因此队列具有先进先出的特性，体现“先来先服务”的原则队头元素是最先被插入的元素，也是最先被删除的元素队尾元素是最终被插入的元素，ql qn也是最终被删除的元素因此，与栈相反，队列又称为“先进先出（简称）First InFirst Out,FIFO或“后进后出（简称）的线性表Last InLast Out,LILO入队运算为往队列队尾插入一种数据元素，退队运算为从队列的队头删除一种数据元素考点链表6【考点精讲】在链式存储方式中，规定每个结点由两部分构成:一部分用于寄存数据元素值,称为数据域，另一部分用于寄存指针，称为指针域其中指针用于指向该结点的前一种或后一种结点（即前件或后件）链式存储方式既可用于表达线性构造，也可用于表达非线性构造（）线性链表1线性表的链式存储构造称为线性链表在某些应用中，对线性链表中的每个结点设置两个指针，一种称为左指针，用以指向其前件结点；另一种称为右指针，用以指向其后件结点这样的表称为双向链表在线性链表中，各数据元素结点的存储空间可以是不持续的，且各数据元素的存储次序与逻辑次序可以不一致在线性链表中进行插入与删除，不需要移动链表中的元素（）带链的栈2栈也是线性表，也可以采用链式存储构造带链的栈可以用来搜集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可运用栈考点二叉树及其基本性质7【考点精讲】、二叉树及其基本概念1二叉树是一种很有用的非线性构造，具有如下两个特点

①非空二叉树只有一种根结点；

②每一种结点最多有两棵子树，且分别称为该结点的左子树和右子树在二叉树中，每一种结点的度最大为即所有子树（左子树或右子树）也均为二叉树此外，2,二叉树中的每个结点的子树被明显地分为左子树和右子树在二叉树中，一种结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树当一种结点既没有左子树也没有右子树时，该结点即为叶子结点例如，一种家族中的族谱关系如图所示有后裔；A B,C行后裔；有后裔；B D,E CF经典的二叉树如图所示1-1下面就图详细讲解二叉树的某些基本概念图族谱二叉树1-11-1父结点（根）在树构造中，每一种结点只有一种前件，称为父结点，没有前件的结点只有一种，称为树的根结点，简称树的根例如，在图中，结点是树的根结点A子结点和叶子结点在树构造中，每一种结点可以有多种后件，称为该结点的子结点没有后件的结点称为叶子结点例如，在图中，结点均为叶子结点1-1D,E,F度在树构造中，一种结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度例如，在图中，根结点和结点的度为结点的度为叶子结点的度为因1-1A B2,C1,D,E,F0此，该树的度为2深度定义一棵树的根结点所在的层次为其他结点所在的层次等于它的父结点所在的层次加树的1,lo最大层次称为树的深度例如，在图中，根结点在第层，结点在第层，结点A1B,C2D,E,F在第层该树的深度为33子树在树中，以某结点的一种子结点为根构成的树称为该结点的一棵子树、二叉树基本性质2二叉树具有如下几种性质性质在二叉树的第层上，最多有个结点；1k2k-l kl性质深度为的二叉树最多有个结点；2m2m-l性质在任意一棵二叉树中，度为的结点即叶子结点总是比度为的结点多一种性质3024具有个结点的二叉树，其深度至少为［］其中［］表达取的整数部分n Iog2n+1,log2n Iog2n、满二叉树与完全二叉树3满二叉树是指这样的一种二叉树除最终一层外，每一层上的所有结点均有两个子结点在满二叉树中，每一层上的结点数都到达最大值，即在满二叉树的第层上有个结点，且深度k2k-l为的满二叉树有个结点m2m—1完全二叉树是指这样的二叉树除最终一层外，每一层上的结点数均到达最大值；在最终一层上只缺乏右边的若干结点对于完全二叉树来说，叶子结点只也许在层次最大的两层上出现对于任何一种结点，若其右分支下的子孙结点的最大层次为，则其左分支下的子孙结点的最大层次或为，或为完全P Pp+lo二叉树具有如下两个性质性质具有个结点的完全二叉树的深度为［］5n Iog2n+1性质设完全二叉树共有个结点假如从根结点开始，按层次每一层从左到右用自然数6n，给结点进行编号，则对于编号为的结点有如下结论1,2,……n kk=l,2,……,n

①若则该结点为根结点，它没有父结点；若则该结点的父结点编号为k=l,kl,INTk/2

②若则编号为的结点的左子结点编号为；否则该结点无左子结点（显然也没有右子2kWn,k2k结点）

③若则编号为的结点的右子结点编号为；否则该结点无右子结点2k+lWn,k2k+l考点二叉树的遍历8【考点精讲】在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树在先左后右的原则下，根据访问根结点的次序，二叉树的遍历分为三类前序遍历、中序遍历和后序遍历（）前序遍历先访问根结点、然后遍历左子树，最终遍历右子树；并且，在遍历左、右子1树时，仍然先访问根结点，然后遍历左子树，最终遍历右子树例如，对图中的二叉树进行前序遍历的成果（或称为该二叉树的前序序列）为1-1A,B,D,E,C,Fo（）中序遍历先遍历左子树、然后访问根结点，最终遍历右子树；并且，在遍历左、右子2树时，仍然先遍历左子树，然后访问根结点，最终遍历右子树例如，对图中的二叉树进行中序遍历的成果（或称为该二叉树的中序序列）为1-1D,B,E,A,C,Fo（）后序遍历先遍历左子树、然后遍历右子树，最终访问根结点；并且，在遍历左、右子3树时，仍然先遍历左子树，然后遍历右子树，最终访问根结点例如，对图中的二叉树进行后序遍历的成果（或称为该二叉树的后序序列）为1-1D,E,B,F,C,Ao考点次序查找9【考点精讲】查找是指在一种给定的数据构造中查找某个指定的元素从线性表的第一种元素开始，依次将线性表中的元素与被查找的元素相比较，若相等则表达查找成功；若线性表中所有的元素都与被查找元素进行了比较但都不相等，则表达查找失败例如，在一维数组［］中，查找数据元素首先从第个元素开始21,46,24,99,57,77,8698,121进行比较，与要查找的数据不相等，接着与第个元素进行比较，以此类推，当进行到与246第个元素比较时，它们相等，因此查找成功假如查找数据元素则整个线性表扫描完毕，4100,仍未找到与相等的元素，表达线性表中没有要查找的元素100在下列两种状况下也只能采用次序查找（）假如线性表为无序表，则不管是次序存储构造还是链式存储构造，只能用次序查找1（）虽然是有序线性表，假如采用链式存储构造，也只能用次序查找2考点二分法查找10【考点精讲】二分法查找，也称拆半查找，是一种高效的查找措施能使用二分法查找的线性表必须满足两个条件用次序存储构造；L3［＞线性表是有序表在本书中，为了简化问题，而更以便讨论，“有序”是特指元素按非递减排列，即从小到大排列，但容许相邻元素相等下一节排序中，有序的含义也是如此对于长度为的有序线性表，运用二分法查找元素的过程如下n X环节将与线性表的中间项比较1X环节假如的值与中间项的值相等，则查找成功，结束查找；2X环节假如不不小于中间项的值，则在线性表的前半部分以二分法继续查找；3X环节假如不小于中间项的值，则在线性表的后半部分以二分法继续查找4X例如，长度为的线性表关键码序列为［］被查元素为首先将与86,13,27,30,38,46,47,70,38,线性表的中间项比较，即与第个数据元素相比较，不小于中间项的值，则在线性表4303830［］继续查找；接着与中间项比较，即与第个元素相比较，不不小于38,46,47,702463846,则在线性表［］继续查找，最终一次比较相等，查找成功38次序查找法每一次比较，只将查找范围减少而二分法查找，每比较一次，可将查找范围减少1,为本来的二分之一，效率大大提高对于长度为的有序线性表，在最坏状况下，二分法查找只需比较次，而次序查找需要n log2n比较次n考点排序11【考点精讲】冒泡排序法和迅速排序法都属于互换类排序法冒泡排序法1首先，从表头开始往后扫描线性表，逐次比较相邻两个元素的大小，若前面的元素不小于背面的元素，则将它们互换，不停地将两个相邻元素中的大者往后移动，最终最大者到了线性表的最终然后，从后到前扫描剩余的线性表，逐次比较相邻两个元素的大小，若背面的元素不不小于前面的元素，则将它们互换，不停地将两个相邻元素中的小者往前移动，最终最小者到了线性表的最前面对剩余的线性表反复上述过程，直到剩余的线性表变空为止，此时已经排好序在最坏的状况下，冒泡排序需要比较次数为n n-1/2o迅速排序法2任取待排序序列中的某个元素作为基准一般取第一种元素，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均不不小于或等于基准元素的排序码，右子序列的排序码则不小于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。