计算机二级选择题——数据结构与算法[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

按照自己的理解写的解题思路，如有错误希望指正。

1.  算法的复杂度：

     ①时间复杂度：执行算法所需的计算工作量（又叫：基本运算次数）

     ②空间复杂度：执行算法所需的内存（存储空间）

      它们是没有任何关系的！！！

 

2.  求二叉树序列类题目

     要点：前序—根左右    中序—左根右    后序—左右根

    例1：已知前序ABCDE，中序BCADE，求后序；同类型，已知任意两个求第三个

      解题思路：  由前序知道A是根，结合中序，CB是左子树，DE是右子树，画图如下所示

                                      A

                              /                 \

                        C                          D

                    /                                     \

                 B                                         E

        后序:左右根————————从左写BC到右ED再到根A——->  BCEDA

 

   例2：看图求前序或者后序

   由图可知：根结点为A

   求前序，前序—>根左右  —>ABDEG遍历完左子树再便利右子树   —–>     ABDEGCFH

   求后序—->左右根   B结点下有DE结点，从左边的D开始所以         ——>    DGEBHFCA

   求中序—–>左根右—>左子树DBGE—->A—->右子树FHC             ——>     DBGEAFHC

 

 

    例3：设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为

            解题： 前序—>根左右  中序—->左根右     后序—->左右根

            所以根—–>A         中序  —->左根右 —–>左A右     所以 没有左子树，右子树为BC，因为只有三个结点，根据中序规则可以判断出C在B的右子树上，画图应如下所示。

            A                                                                               

                \                                                                      

                   B                                                               

                      \                                                          

                        C                                                   

 

     

3.可能考概念或者如下题类型，知识点是差不多的

    要点：非空数据表结构之线性结构

   线性结构的特点：①有且只有一个根结点

                                ②每个结点最多有一个前件，也最多只有一个后件

   例1：设数据元素的集合D={ 1,2,3,4,5 }，则满足下列关系R的数据结构中为线性结构的是
　　   A) R={ (1,2), (3,4), (5,1) }
　　   B) R={ (1,3), (4,1), (3,2), (5,4) }
　　   C) R={ (1,2), (2,3), (4,5) }
　　   D) R={ (1,3), (2,4), (3,5) } 

       解题思路：一个根结点，一个前件一个后件

      前一个的后件与后一个的前件相同就合并如（1，3）（3，4）—–>（1，3，4）

      前一个的前件与后一个的后件相同就把后一个的前件拿到前面去如 （1，2）（5，1） —>（5，1，2）

      也可以写的时候把它写成一个圆，相邻的相同的元素合并成1个

       A     (1,2) 与(3,4)  无重复，先放至  接着到(5,1)   5，1后件与1，2前件相同所以   （5，1，2），（3，4）前件作为根结点，所以A的根结点是：5，3

       B     (1,3)与(4,1) 重复   —->（4，1，3)  与（3，2）重复 —->（4，1，3，2）与（5，4）—–>(5,4,1,3,2) 根结点为5

       C     (1,2)与(2,3)—->（1，2，3）与（4，5）—->（1，2，3）,(4,5)根节点为1，4

       D     (1,3)与(2,4)—->(1,3),(2,4)与(3,5)—–>（1，3，5）（2，4）根结点为1，2

 

       

4.  关于排序：

   冒泡=快速=插入=选择（最坏情况下） n(n-1)/2

    希尔是小于上面四种的：希尔—>O(n1.5)

    堆排序O(nlog2n)  复杂度 < 冒泡···<希尔

    顺序：n

    二分法：log2n

    补充———>二分法查找（又称对分查找）——->只适用于——–>顺序存储的有序表

     快速排序法，每一次数据元素的移动会产生新的逆序的排序方法

 

5.关于二叉树的计算

要点：二叉树的性质

①任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点数 大1

②总结点数 = 叶子结点数 + 度为 1 的结点数 + 度为2的结点数

③如果前序和中序相同，说明没有左子树结点——->二叉树中共有多少个结点，二叉树的深度也为多少

④如果后序与中序相同，说明没有右子树结点——->二叉树中共有多少个结点，二叉树的深度也为多少

例1：一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为

套性质，总结点 = 80 + 70 + （80-1） = 229

例2：某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根结点在第1层）

由题可知：度为1的结点数为11个，度为2的结点为0个。叶子结点只有一个，其余结点每个层只有一个结点。12个结点分布12层，所以深度为12

例3：满二叉树题

在深度为7的满二叉树中，度为2的结点个数为

要点：第k层有2的（k-1)次方个结点           深度为m有  2的m次方 – 1 个结点

因为是满叉树，所以只有度0结点和度2结点

总结点 = 叶子结点 + 度2的结点  = 2的7次方 – 1 = 127 —–>  n + n – 1 = 127 ——>n = 63

例4： 深度为７的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为

要点：

         ①完全二叉树指除最后一层外，每一层上的结点数均达到最大值（即满叉树）。

            在最后一层上只缺少右边的若干结点

         ②第k层有2的（k-1)次方个结点           深度为m有  2的m次方 – 1 个结点

          前6层总和，2的6次方 – 1 = 63个 ，第6层结点数—>2的（6-1）次方 = 32

          第7层   =  125 -前6层 —->  125-63 = 62个

          分别挂在第6层的左边31个结点上所以第6层的最后1个为叶子结点，整棵树共有62+1=63个叶子结点

例5:某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的深度（根结点在第1层）为

     解:A为根结点，又由于在中序遍历中访问根结点的次序为居中，而访问左子树上的结点为居先，访问右子树上的结点为最后。由中序可知，DCB为左子树，EFG为右子树。又因为前序和中序的顺序不一样，可得出C为B的一个之点，在左边的之分点为C的一个之点，在左边的之分点，右边同理。

    验算时可倒推

             A

      B            E

  C                   F

D                        G

 

例6：深度为5的完全二叉树的结点数不可能是（）

         A）18

         B）15

         C）16

         D）17

         解：深度为m的二叉树最多有——>   2的m次方-1   <—–个结点

                深度为4的最多  15个结点，所以深度为5的>15

例7：某完全二叉树共有256个结点，则该完全二叉树的深度为

         解:完全二叉树具有以下性质:具有n个结点的完全二叉树的深度为[log2n]+1。

              [log底数2 256]+1=9。

 

例7:某棵树只有度为3的结点和叶子结点，其中度为3的结点有8个，则该树中的叶子结点数为

     解:在树结构中，树中的结点数即为树中所有结点的度数之和再加1。

          总度数为3×8=24，所以结点总数为25个，则该树中叶子结点个数为25-8=17

 

例8：某棵树的度为4，且度为4、3、2、1的结点个数分别为1、2、3、4，则该树中的叶子结点数为

       解：树的结点个数为4*1+3*2+2*3+1*4+1=21，所以度为0的结点个数为21-1-2-3-4=11个。

 

例8：某棵树中共有25个结点，且只有度为3的结点和叶子结点，其中叶子结点有7个，则该树中度为3的结点数为

         解:叶子结点7个，度为3的结点数是25-7=18个，树中的结点数为树中所有结点的度数之和再加1，则树的总结点数是18*3+1=55个 不等于25个

 

 

         

6.  循环队列问题

   ① 队头、队尾、栈顶指针会变——————–栈底指针不变

       元素个数跟队头、队尾指针有关

   ② 循环队列是顺序存储结构。

       链式存储方式既可表示线性结构，也可表示非线结构；

       栈与队列都是线性表，也都可以采用链式存储结构。

    ③当需要插入的数据大于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象

        大于—->溢出

 

7.  线性表、链表

   ①  线性表的链式存储结构中——>存储空间可以不连续、可以连续

                                               ——>各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致

      数据元素之间的逻辑关系—–>由指针域来确定

   ②  线性链表又称线性单链表。每一个结点只有一个指针域，由这个指针只能找到后件结点；

       这种线性链表——->只能顺着指针向—–>链尾方向——->进行扫描——–>所以不能从任何结点开始遍历

   ③  双向链表结点有两个指针域，指向前一个结点的指针和指向后一个结点的指针—–>线性结构

   ④  栈与队列都是线性表，带链的栈与队列是线性结构；

   ⑤  结点中有多个指针域的所有链表不一定是非线性结构

   ⑥  能顺序存储的数据结构可以是线性结构也可以是非线性结构，例如树可以顺序存储数据，而树是非线性结构。

   ⑦  如果有两个结点的同一个指针域的值相等，则说明至少有一个结点有两个前件，不符合线性结构的定义

   ⑧  线性表的前件结点的存储序号可以小于也可以大于后件结点的存储序号

   ⑨  线性表的顺序存储结构的两个特点：

                   Ⅰ.线性表中所有元素所占的存储空间是连续的；

                    Ⅱ.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。(即元素的存储顺序与逻辑顺序一致）

                         线性表中数据元素所占的存储空间（字节数）相等

    ⑩  循环链表的第一个结点就是根结点，最后一个结点就是叶子结点——->非空循环链表所表示的数据结构,有根结点也有叶子结点

 

8.  数据结构

   ① 非空的数据结构的两个条件：

      Ⅰ.有且只有一个根结点；Ⅱ.每个结点最多有一个前件，也最多有一个后件。

   ② 根结点的数量并不能说明这个数据结构是线性的还是非线性的

   ③数据结构是指相互关联的数据元素的集合，只有一个空结点的结构也为数据结构

   ④数据结构是指反映数据元素之间关系的数据元素集合的表示——–>数据结构是指带有结构的数据元素的集合

   ⑤线性结构与非线性结构都可以是空的数据结构；一个空数据结构可以是线性结构也可以是非线性结构

 

9.  关于栈

   ①循环队列中——>队尾指针rear指向队列中的队尾元素

                         ——>排头指针front指向排头元素——>前一个位置

                         当front=rear时，可能队列满，可能队列空

    ②循环队列下，最坏情况  需要-1;

        顺序查找，最坏情况与实际结点个数一致

 

      循环队列中的元素个数随队头指针与队尾指针的变化而动态变化。

      例1：设循环队列为Q(1: m)，初始状态为front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为

            0 或 m个

      例2： 设循环队列为Q(1: m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为

            元素个数 = 20 – 15 =  5

            由于寻找的是最大值的元素，需要比较四次（循环队列下！！！！！最坏情况比较次数——>元素个数 – 1）

      例3；设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为

            front到尾的元素个数：m-20  ；rear到尾的元素:15

            所以元素个数：m-20+15 = m -5

            次数: m – 5 – 1 = m – 6

      

      

   ② 栈按照“先进后出”的原则组织

       插入与删除操作被限制在栈顶一端进行，入栈使栈顶位置进1，退栈使栈顶退1

       栈底  bottom    栈顶  top   

      当top = 1说明在栈顶，再加要溢出了    

       top <  bottom 时 ———–>   栈中元素=|top-bottom|+1

     例1：设栈的顺序存储空间为S(1: 50),初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为

         解题：初始状态top=0表示栈为空——>一系列操作后top = 20 ——->元素个数  =  20 – 0 = 20

 

     例2：设栈的顺序存储空间为S(1: m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为

         解题：初始状态时top＝m+1，每次出栈top+1，每次入栈top-1。当栈中有n个元素时，top=m+1-n=20，所以n=m-19

 

      例3：设栈的顺序存储空间为S(0:49)，栈底指针bottom=49，栈顶指针top=30（指向栈顶元素）。则栈中的元素个数为

           |30-49|+1=20

 

      例4：一个栈的初始状态为空，现将元素A,B,C,D,E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为

            “先进后出”原则———->跟动车三个位置一样，坐窗边的就要等走廊边的先出去才能出去

             CDE进入新队列，C先进…….，E—–>D—–>C，所以退队顺序        E<—–D<—–C

 

10.算法

     ①指解题方案的描述，不等于程序，不等于计算方法；

     ②要考虑对数据对象的运算和操作，算法的控制结构、时间复杂度和空间复杂度等；

     ③程序可以作为算法的一种描述方法。

 

11.堆

   堆的定义如下：具有n个元素的序列(h1,h2,…,hn),当且仅当满足hi>=h2i，hi>=h2i+1或hi<=h2i，hi<=h2i+1(i=1,2,…,n/2)时称之为堆。由堆的定义可以看出，堆顶元素(即第一个元素)必为最大项。

           条件：第一个元素必须为最大

     例1：下列各序列中不是堆的是

              A）(47,91,53,85,30,12,24,36)

              B）(91,85,53,47,36,30,24,12)

              C）(91,85,53,47,30,12,24,36)

              D）(91,85,53,36,47,30,24,12)

      解：堆顶元素必须为最大项，所以选A