数据结构（Day20）

标签：排序 元素 Day20 链表 查找 哈希 遍历 数据结构

一、学习内容

1. 树形结构

   1. 概念

      1. (1树是n个元素的有限集合

      2. n==0 空树

      3. n>0 有且只有一个根结点

         1. 其他的结点 互不相交的子集

         2. 树具有递归性：树中有树

   2. 树的术语

      1. (结点：树的数据元素

      2. (根结点： 唯一的 没有前驱(没有双亲)

      3. 叶子：终端结点 不是唯一的 没有后继(没有孩子) 度为0

      4. 分支：内部结点 有前驱 有后继 度不为0

      5. 结点的度：后继结点的个数【分支数】【树杈】

      6. 树的度：结点度的最大值max

      7. 树的深度：高度、树的层次 【有几层】【几代人】

      8. 双亲：某结点的直接前驱

      9. 孩子：某结点的直接后继

      10. 兄弟：双亲是同一个 亲兄弟

      11. 堂兄弟：双亲在同一层 但不是同一个

      12. 祖先：根节点到该结点的分支结点

      13. 子孙：下层结点的任一结点

      14. 森林：互不相交的树的集合

      15. 有序树：左右子树不能颠倒

      16. 无序树：左右子树没有顺序

   3. 二叉树

      1. 概念：每个节点最多拥有两个子树，并且严格区分左右子树的树形结构

   4. 二叉树的基本形态

      1. 二叉树的基本形态一共有五种：空树（没有任何节点）、只有根结点、只有根结点和左子树、只有根结点和右子树、根结点和左右子树都有

         1. 

   5. 特殊的二叉树

      1. 左斜树：只有左孩子节点

      2. 右斜树：只有右孩子节点

      3. 满二叉树：在不增加层次的基础上，不能再向该树上增加节点

      4. 完全二叉树：在一个满二叉树的基础上，从左向右依次增加结点的二叉

   6. 二叉树的性质

      1. 在一个二叉树的第k层上，最多拥有2^(k-1)个节点，最少1个

         1. 

      2. 前k层最多有（2^k） -1个节点，最少k个

         1. 

      3. 在二叉树的第n个节点处，如果该节点有左孩子，那么该左孩子是该树的第2*n个节点，如果有右孩子，那么是第2*n+1个节点

      4. 在任意一棵二叉树上，叶子节点的个数总比度为2的节点数目多n0 = n2 + 1

         1. 假设：n0表示度数为0的节点个数，n1表示度数为1的节点个数，n2表示度数为2的节点个数 总结点数 = 树杈数 + 1 = 0*n0 + 1*n1 + 2*n2 + 1 总结点数 = n0+n1+n2 0*n0 + 1*n1 + 2*n2 + 1 == n0+n1+n2 n2 + 1 == n0 n0 = n2 +1 :叶子节点的个数是度为2的节点个数+1

      5. 已知结点总个数n个，求深度/高度 [log2n]+1 []向下取整

         1. 

            1. 结点总个数：15个 深度：4

            2. 结点总个数：7个 深度：3

            3. 结点总个数：1000个 深度：10

   7. 二叉树的顺序存储

      1. 

         1. 对于树的顺序存储而言，如果是完全二叉树，使用顺序存储没有问题，但是，如果存储的是普通二叉树，就会造成中间数据的大量浪费空间。所以，一般对于二叉树的操作，通常使用链式存储

   8. 二叉树的链式存储

      1. 孩子表示法——找孩子方便

         1. 

      2. 节点结构体类型

         1. typedef struct node{
                int data;        //数据域
                struct node *left;    //左孩子指针域
                struct node *right;    //右孩子指针域
            }tree, *treePtr;

      3. 创建二叉树

         1. 

            1. treePtr create(){
                   char e;            //定义结点值
                   scanf("%c", &e);    //输入结点值
                   if(e=='#'){        //若结点值为#  表示空节点  返回NULL
                       return NULL;    
                   }
                   //否则是非空结点
                   //1、开辟空间
                   treePtr p = (treePtr)malloc(sizeof(tree));
                   if(p==NULL){
                       printf("error\n");
                       return NULL;    
                   }
                   //2、给数据域赋值
                   p->data = e;    
                   //3、给左孩子指针域赋值
                   p->left = create();    
                   //4、给右孩子指针域赋值
                   p->right = create();
                   //5、返回创建的结点
                   return p;
               }
               
               测试数据：AB#D##C#EF##G##

               1. 函数功能：创建一个节点，存储数据，然后给左右子孩子指针创建一棵二叉树。同思路

               2. 函数返回值：成功返回树的地址，失败返回NULL

               3. 函数名：符合命名规则

               4. 参数列表：无

      4. 先序遍历

         1. void first_show(treePtr T){
                if(T==NULL){
                    return;    
                }
                //根
                printf("%c", T->data);
                //左
                first_show(T->left);
                //右
                first_show(T->right);
            }
            

            1. 函数功能：每次遍历到节点时，先访问数据域，然后访问左子树，最后访问右子树。 ---> 先根 再左 再右

            2. 函数返回值：无

            3. 函数名：符合命名规则

            4. 参数列表：二叉树

      5. 中序遍历

         1. void mid_show(treePtr T){
                if(T==NULL){
                    return;    
                }
                //左
                mid_show(T->left);
                //根
                printf("%c", T->data);
                //右
                mid_show(T->right);
            }

            1. 函数功能：每次访问一个新节点时，先中序遍历其左子树，然后访问根节点的数据，最后访问右子树。 --->左 根 右

            2. 函数返回值：无

            3. 函数名：符合命名规则

            4. 参数列表：二叉树

            5. void mid_show(treeP

      6. 后序遍历

         1. void last_show(treePtr T){
                if(T==NULL){
                    return;    
                }
                //左
                last_show(T->left);
                //右
                last_show(T->right);
                //根
                printf("%c", T->data);
            }

            1. 函数功能：每次访问一个节点时，先进行后序遍历左子树，然后再后序遍历右子树，最后访问根结点。 ---> 左右根

            2. 函数返回值：无

            3. 函数名：符合命名规则

            4. 参数列表：二叉树

   9. 根据已知序列反推二叉树

      1. 由先序序列和中序序列推二叉树

         1. 先序：G D A F E M H Z

         2. 中序：A D E F G H M Z

      2. 由后序遍历和中序遍历反推二叉树

         1. 后序：d a b e c

         2. 中序：d e b a c

      3. 不能通过先序遍历序列和后序遍历序列来唯一确定一棵二叉树

2. 算法

   • 算法概念

     • 算法就是计算机解决问题的方法或步骤 沃斯提出——面向过程的程序 = 数据结构 + 算法 数据结构是肉体 算法是灵魂

   • 算法的特性

     • 确定性：算法的每一条语句具有确定的意思，不能模棱两可，不具有二义性

     • 有穷性：在执行一定时间后，有限的步骤内，会自动结束算法

     • 输入：至少要有0个或多个输入【可以没有输入】

     • 输出：至少要有一个或多个输出

     • 可行性：经济可行、社会可行性

   • 算法设计要求

     • 正确性：对于正确的输入，会给出正确的结果，尽可能少的出现Bug

     • 健壮性：对于错误的输入，要给出合理的处理 switch语句中 default语句

     • 可读性：要求代码要有注释、有缩进、命名要规范

     • 高效率：要求时间复杂度尽可能低 T(n) = O(f(n));

     • 低存储：空间复杂度尽可能低 S(n) = O(f(n));

   • 算法时间复杂度（T(n)）

     • 算法时间复杂度计算公式：T(n) = O(f(n)); T(n):时间复杂度 n:表示问题的规模 f(n) :是问题规模与执行次数之间的函数 O(f(n)):使用O阶记法，记录算法时间复杂度

     • 时间复杂度推导

       • 

     • 常见的时间复杂度

       • 

3. 排序算法

   • 概念

     • 定义：将给定的序列，按照关键字进行升序【小-大】或降序【大-小】排列的过程叫做排序

     • 分类

       • 换类排序：冒泡排序、快速排序

       • 选择类排序：简单选择排序，堆排序

       • 插入类排序：直接插入排序、折半插入排序、希尔排序

       • 归并排序：二路归并、三路归并

       • 基数排序

   • 直接插入排序 （抓牌）

     • 定义：每次将待排序序列的第一个元素，放在已排序序列中对应的位置

     • 原理

       • 从第一个元素开始,该元素可以认为已经被排序【有序】

       • 取出下一个元素,在有序序列中从后向前扫描【倒序循环】

       • 如果已排序元素大于新元素,将已排序元素向后移【腾出空位，便于插入】

       • 重复②③,直到排序完成

     • void insert_sort(int a[], int len){
           //因为a[0]已经有序，所以从a[1] a[2] a[3]……a[len-1]依次前插排序
           for(int i=1; i<len; i++){    //控制待排序元素
               //1、找个临时变量保存待排元素——因为后移会覆盖元素
               int temp = a[i];
               //2、让待排元素temp与前面的有序序列依次进行比较
               for(int j=i-1; j>=0&&temp<a[j]; j--){ //控制前面有序序列
                     a[j+1] = a[j];      
               }
               //3、把待排元素放入腾出的空位
               a[j+1] = temp;
           }
       }

   • 快速排序（O(N*logN)）

     • 定义：快速排序是在序列元素与选定基准元素比较分割为大小两部分的交换排序

     • 原理：从待排序序列中，选定一个基准，以此为基准，将待排序序列分为大小两个部分，对每个部分，再次选择基准进行上述操作，直到每一部分的元素只有一个，则排序成功

       • 假设第一个元素为中轴(支点)

       • 从最右边元素和中轴比， 比中轴大，下标减减，前移继续比较，遇到一个比中轴小的放在左边

       • 然后从最左边元素和中轴比，比中轴小，下标加加，后移继续比较，遇到一个比中轴大的放在右边

       • 当左右下标重叠时，放入中轴元素

       • 然后以中轴元素为分界点，对左右两边，继续进行快速排序【递归调用】

       • 直到完全有序

     • 功能：实现一趟快排，确定中轴下标

     • 参数：数组、头下标、尾下标

     • 返回值：int 中轴下标

     • 
       int once(int a[] , int low, int high){    //头下标  尾下标
           //1、确定中轴值——假设第一个元素
           int key = a[low];
           //2、循环左右往复确定中轴下标
           while(low<high){
               while(key<=a[high] && low<high){
                   high--;        
               }//该循环结束时，key>a[high] 找到小的了，放入左边
               a[low] = a[high];
               while(key>=a[low] && low<high){
                   low++;        
               }//该循环结束事，key<a[low] 找到大的了，放入右边
               a[high] = a[low];
           }
           //3、把中轴值放入找到的low==high的位置
           a[low] = key;    //a[high] = key;
           //4、返回中轴下标
           return low;      //return high;
       }
       
       //以中轴划分左右子序列，递归快排
       void quick_sort(int a[], int low, int high){
           if(low<high){
               //1、调用函数，找到中轴
               int mid = once(a, low, high);
               //2、以中轴划分左右子序列，递归快排   
               quick_sort(a, low, mid-1);
               quick_sort(a, mid+1, high);
           }
       }

4. 查找算法

   • 概念

     • 按照关键字，在查找表中查询是否存在的算法叫做查找

   • 分类

     • 顺序查找：将给定的查找表进行全部遍历一遍，与要查找的关键字进行比对。

     • 折半查找（二分查找）：在顺序存储的有序序列中，通过进行逐次减半查找范围，查找特定的关键字的算法，叫做折半查找。

     • 哈希查找：通过哈希函数，在哈希表中定位要找的数据元素

   • 折半查找

     • 要求：查找表是顺序存储，并且有序序列

     • 通过不断减半查找范围，最后确定查找的值

   • 哈希查找

     • 哈希表是借助哈希函数将序列存储于连续存储空间的查找表

     • 哈希函数是根据关键字确定存储位置的函数

     • 哈希函数的构造方式：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法

     • 哈希冲突是不同关键字由哈希函数得到相同存储位置的现象

     • 解决哈希冲突的方法

       • 开放定址法

         • 线性探测法

         • 二次探测法

         • 伪随机探测法

       • 再哈希法

       • 链地址法 （顺序表和链表的集合）

         • 

       • 建立公共溢出区

       • 哈希表的长度确定方法：数据元素个数除以四分之三得到的最大素数

5. 脑图

二、作业

1、简答题

①顺序表与链表的区别？

解答：

1. 存储方式

顺序表：顺序表使用连续的内存空间存储数据，即数组。每个元素的地址是相邻的。

链表：链表使用非连续的内存空间，每个结点存储数据以及指向下一个结点的指针。

2. 内存使用

顺序表：因为顺序表使用连续的内存空间，因此在创建时需要预先分配一整块内存。一旦内存满了，需要重新分配更大空间，效率较低。

链表：链表的内存是动态分配的，每个结点可以在需要时动态创建，因此链表的内存利用率较高，可以有效避免内存浪费。

3. 访问速度

顺序表：由于顺序表的元素是连续存储的，支持随机访问，可以通过数组下标在O(1) 时间内直接访问任意元素。

链表：链表的元素是通过指针链接的，访问某个元素需要从头开始遍历，因此访问速度为O(n)，不支持随机访问。

4. 插入和删除操作

顺序表：

插入或删除一个元素时，可能需要移动大量元素，以保证数据的连续性，因此时间复杂度为O(n)。

但如果插入或删除操作发生在最后一位（末尾），时间复杂度为O(1)。

链表：

插入或删除元素只需要调整指针，不需要移动元素，因此时间复杂度通常为O(1)。但是，找到插入或删除位置的时间复杂度为O(n)。

5. 空间浪费

顺序表：由于需要预先分配一定大小的连续内存，当元素数量小于分配的数组空间时，可能会造成内存浪费。

链表：由于链表是动态分配的内存，理论上不会浪费内存，但每个结点额外需要存储指针信息，会有额外的内存开销。

6. 扩展性

顺序表：在存储空间满了之后，如果需要插入新的元素，必须扩容。这时需要重新分配一块更大的连续内存空间，并将原来的数据复制过去，效率较低。

链表：链表由于是动态分配内存的，所以在插入新元素时不需要像顺序表那样扩展整个表，扩展性较强。

7. 类型

顺序表：常见的顺序表就是数组，它是一维数组的实现。

链表：链表有多种形式，如单链表、双向链表、循环链表等。

②队列与栈的区别？

解答：

1.存取顺序

栈（Stack）：

栈遵循后进先出（LIFO，Last In First Out）的原则，最后插入的元素最先被取出。

常用操作：

push：将元素压入栈顶。

pop：将栈顶元素弹出。

top/peek：获取栈顶元素但不弹出。

例子：堆盘子——最后放的盘子必须最先拿走。

队列（Queue）：

队列遵循先进先出（FIFO，First In First Out）的原则，最早插入的元素最先被取出。

常用操作：

enqueue：将元素加入队尾。

dequeue：将队头元素出队。

front：获取队头元素但不出队。

例子：排队买票——最先排队的人最先买到票。

2. 操作的主要位置

栈：元素的插入和删除都发生在栈顶，只能对栈顶进行操作。

队列：元素的插入发生在队尾，删除发生在队头，即不同的端进行不同的操作。

3.实现方式

栈：栈可以通过数组或链表实现。

数组实现栈时，栈顶指针指向数组最后的位置。

链表实现栈时，链表头部就是栈顶。

队列：队列可以通过数组、链表或循环队列实现。

顺序队列使用数组，队尾指针指向数组最后一个位置。

链表实现队列时，队头和队尾分别对应链表的头部和尾部。

循环队列优化了顺序队列的问题，通过将数组首尾相连，避免数据移动操作。

③单链表和双链表的区别？

解答：

指针数量：

单链表：每个节点只有一个指针，指向下一个节点。

双链表：每个节点有两个指针，分别指向前一个节点和后一个节点。

遍历方向：

单链表：只能从头到尾单向遍历。

双链表：可以双向遍历，即从头到尾和从尾到头都可以遍历。

插入/删除效率：

单链表：在删除某个节点时，如果需要访问前驱节点，必须从头遍历，效率较低。

双链表：因为有前驱指针，可以直接访问前驱节点，插入和删除操作效率较高。

内存开销：

单链表：每个节点只需要一个指针，内存开销较小。

双链表：每个节点需要两个指针，内存开销较大。

④简述你学过的查找算法

解答：

1.顺序查找（线性查找）

原理：从数据结构的第一个元素开始，依次与目标值比较，直到找到目标值或遍历结束。

时间复杂度：O(n)

适用场景：适合无序列表或列表较小时使用。

特点：实现简单，但效率较低。

2.二分查找

原理：在有序数组中查找。每次将数组分成两半，比较中间值与目标值，如果目标值比中间值小，继续在左半部分查找，否则在右半部分查找。

时间复杂度：O(log n)

适用场景：只适用于有序数组。

特点：效率较高，但必须基于有序结构。

3.哈希查找

原理：通过哈希函数将关键字映射到数组的某个位置，然后在这个位置进行直接查找。

时间复杂度：O(1)（理想情况下）

适用场景：适合快速查找，适用于哈希表。

特点：查找速度非常快，但需要处理哈希冲突问题，且构建哈希表需要额外的内存。

⑤简述你学过的排序算法【尽可能多的列举】

解答：

1.冒泡排序（Bubble Sort）

原理：每次比较相邻的两个元素，如果顺序不对就交换。每一趟会将最大的元素“冒泡”到最后。

时间复杂度：O(n²)

特点：实现简单，适合小规模数据，不适合大型数据集。

2.选择排序（Selection Sort）

原理：每一趟从未排序的序列中选择最小（或最大）的元素，放到已排序部分的末尾。

时间复杂度：O(n²)

特点：不稳定排序，交换次数较少。

3.插入排序（Insertion Sort）

原理：将未排序的元素插入到已排序的部分中，使得部分序列保持有序。

时间复杂度：O(n²)

特点：稳定排序，适合小规模或基本有序的数据。

4.快速排序（Quick Sort）

原理：选择一个基准元素，将序列划分为两部分，一部分比基准小，另一部分比基准大，然后递归排序。

时间复杂度：平均 O(n log n)，最坏 O(n²)

特点：不稳定排序，通常是最快的通用排序算法，适合大规模数据。

⑥写出直接插入排序的思想

解答：

构建有序序列：将未排序的元素逐个插入到已排序的序列中。初始时，默认第一个元素是有序的。

逐步插入：从第二个元素开始，依次将每个元素与前面已经排序的部分进行比较，并插入到适当的位置，保证前面的部分始终是有序的。

操作步骤：

取出一个未排序的元素作为当前待插入元素。

从已排序部分的末尾开始，依次向前比较待插入元素与已排序部分的元素。

如果待插入元素小于当前已排序的元素，则将已排序的元素向后移动一位，直到找到合适的位置。

将待插入元素插入到合适的位置。

重复：重复以上步骤，直到所有元素都被插入到有序序列中。

⑦结构体与共用体的区别？

解答：

内存分配：

结构体（struct）：每个成员都有自己的内存空间，结构体的大小是所有成员大小之和。各个成员互不干扰，可以同时存储多个不同类型的数据。

共用体（union）：所有成员共用同一块内存，大小等于最大成员的大小。任一时刻只能存储一个成员的数据，因为修改一个成员会影响到其他成员。

访问方式：

结构体：可以同时访问多个成员。

共用体：同一时刻只能访问一个成员。

使用场景： 

结构体：适用于需要同时存储和操作多个不同类型的数据的情况。

共用体：适用于节省内存、需要多个数据类型共用同一块内存的情况。

⑧简述二分查找的思想 和 前提条件

解答：

分治法：将待查找的范围逐步缩小到一半。通过比较目标元素与中间元素的大小关系，决定继续在哪一半进行查找。

步骤：

计算数组中间元素的索引（通常为 mid = (left + right) / 2）。

如果中间元素等于目标元素，查找成功。

如果目标元素小于中间元素，则在左半部分继续查找（更新右边界 right = mid - 1）。

如果目标元素大于中间元素，则在右半部分继续查找（更新左边界 left = mid + 1）。

重复上述步骤，直到找到目标元素或范围为空。

前提条件

数组必须有序：二分查找要求输入的数组是按升序或降序排列的，否则无法保证正确的查找结果。

已知查找范围：需要有明确的查找区间（左边界和右边界），以便于在每一步中进行有效的范围缩小。

⑨简述哈希查找的过程

解答：

1. 哈希表的构建

选择哈希函数：选择一个适合的哈希函数，将关键字映射到哈希表的索引。哈希函数应尽量均匀分布，以减少哈希冲突。

2. 插入元素

计算哈希值：使用哈希函数对要插入的元素进行哈希运算，得到对应的哈希值。

存储元素：将元素存储在哈希表的对应位置。如果该位置已经被占用（发生哈希冲突），则根据选择的解决冲突的方法（如链地址法、开放地址法）进行处理。

3. 查找元素

计算哈希值：使用哈希函数对要查找的元素进行哈希运算，得到对应的哈希值。

访问哈希表：根据哈希值直接访问哈希表的相应位置。

检查元素：

如果该位置的元素与要查找的元素相同，则查找成功。

如果发生哈希冲突，则根据冲突解决的方法在该位置的链表或后续的探测位置中查找目标元素。

4. 删除元素

计算哈希值：与查找过程相同，使用哈希函数计算要删除的元素的哈希值。

查找元素：在哈希表中找到该元素的位置。

删除元素：根据冲突解决的方法进行删除（例如，从链表中移除节点或标记为已删除）。

⑩如何使用两个栈，来实现队列，简述思路即可

解答：

1. 数据结构

两个栈：使用两个栈，分别命名为 stack1 和 stack2。

stack1 用于存储入队元素。

stack2 用于存储出队元素。

2. 入队操作

当执行入队操作时，将元素直接压入 stack1 中。

3. 出队操作

当执行出队操作时，首先检查 stack2 是否为空：

如果 stack2 不为空：直接从 stack2 弹出栈顶元素，返回该元素。

如果 stack2 为空：将 stack1 中的所有元素逐个弹出并压入 stack2。这样，stack2 的栈顶元素就是 stack1 的底部元素，从而实现队列的 FIFO（先进先出）特性。然后从 stack2 弹出栈顶元素并返回。

2、选择题

①假设要存储一个数据集，数据维持有序，对其的操作只有插入、删除和顺序遍历，综合存储效率和运行速度，下列哪种数据结构是最适合的是?

A、数组

B、链表

C、哈希表

D、队列

解析：

A. 数组

优点：支持快速的随机访问，适合顺序遍历。

缺点：插入和删除操作需要移动元素，时间复杂度为 O(n)，因此在插入和删除操作频繁的情况下效率较低。

B. 链表

优点：插入和删除操作相对高效，时间复杂度为 O(1)（在已知位置时）。

缺点：为了保持有序，需要在插入时找到合适的位置，查找的时间复杂度为 O(n)，顺序遍历效率较好，但随机访问效率较低。

C. 哈希表

优点：支持快速的插入、删除和查找操作，平均时间复杂度为 O(1)。

缺点：哈希表不保持元素的顺序，因此不适合需要有序存储的场景。

D. 队列

优点：适合先进先出（FIFO）的访问模式。

缺点：不支持随机访问和有序遍历，且在删除和插入时只能在一端操作，不适合本题的需求。

解答： 

B

②关于链表，描述不正确的选项是（）（鲁科安全）

[A] 在运行期间可以动态添加

[B] 物理空间不连续，空间开销大

[C] 查找元素不需要顺序查找

[D] 可以在任意节点位置插入元素

解析：

A. 在运行期间可以动态添加

正确：链表的一个主要优点是能够在运行期间动态地增加或减少节点，不需要预先定义大小。

B. 物理空间不连续，空间开销大

不正确：虽然链表的节点在内存中是非连续存储的，但这并不一定意味着空间开销大。链表的空间开销主要取决于存储每个节点所需的指针，通常比数组在大小固定时的空闲空间开销要小。因此，这个选项表述为“空间开销大”是不准确的。

C. 查找元素不需要顺序查找

正确：链表查找元素通常需要顺序查找，因为链表的节点是通过指针相连的，不支持随机访问。但如果在链表中存储的是某些特定类型的节点（如带有索引的跳表），则可以提高查找效率。

D. 可以在任意节点位置插入元素

正确：链表可以在任意位置插入元素，只需调整相关节点的指针即可。

解答： 

B

③下列关于线性表的描述错误的是：（华三外协）

A. 线性表是一种线性结构，其最大的特点就是“串”，既一个“头”，一个“尾”，一个前驱，一个后继

B. 线性表是一种数据结构，用一组连续的存储单元依次存储线性表的数据元素

C. 线性链表是一种数据结构，用一组任意的存储单元依次存储线性表的数据元素

D. 静态链表是一种特殊的线性链表，用数组存储线性表的数据元素

解析：

A. 线性表是一种线性结构，其最大的特点就是“串”，既一个“头”，一个“尾”，一个前驱，一个后继

正确：线性表确实是线性结构，具有前驱和后继关系，通常描述为“头”和“尾”。

B. 线性表是一种数据结构，用一组连续的存储单元依次存储线性表的数据元素

错误：这条描述只适用于顺序表，而线性表的定义包括顺序表和链表。线性表可以用连续存储（如顺序表）或非连续存储（如链表）来实现。

C. 线性链表是一种数据结构，用一组任意的存储单元依次存储线性表的数据元素

正确：线性链表的特性正是允许节点在内存中不连续存储，每个节点通过指针连接。

D. 静态链表是一种特殊的线性链表，用数组存储线性表的数据元素

正确：静态链表的实现是通过数组来存储数据元素，并用数组下标来模拟指针。

解答： 

A

④关于链表与数组的优缺点，以下说法正确的是（）

A 数组动态分配内存，并在内存中连续，链表静态分配内存，但不连续

B 查询时，数组的时间复杂度为O(n)，链表为O(1)

C 插入或删除时，数组的时间复杂度为O(1)，链表为O(n)

D 数组元素在栈区，链表元素在堆区

解析：

A. 数组动态分配内存，并在内存中连续，链表静态分配内存，但不连续

错误：数组可以是静态分配的（在编译时大小固定）或动态分配的（在运行时分配），但无论如何它在内存中都是连续的。链表则通常是动态分配的，且在内存中是非连续的。因此这个选项的描述不准确。

B. 查询时，数组的时间复杂度为 O(n)，链表为 O(1)

错误：数组的查询时间复杂度为 O(1)，因为可以通过索引直接访问。而链表的查询时间复杂度为 O(n)，因为需要从头节点开始顺序遍历。这个选项是错误的。

C. 插入或删除时，数组的时间复杂度为 O(1)，链表为 O(n)

错误：在数组中，如果在末尾插入或删除元素，时间复杂度为 O(1)，但如果在中间或开头插入或删除，则需要移动元素，时间复杂度为 O(n)。而在链表中，如果已知插入或删除的位置，时间复杂度为 O(1)，但如果需要先查找位置，则需要 O(n)。因此这个选项也是不正确的。

D. 数组元素在栈区，链表元素在堆区

部分正确：数组可以在栈区（静态数组）或堆区（动态数组）分配内存，而链表通常是在堆区分配内存。因此这条描述并不全面，无法完全被视为正确。

解答： 

D

⑤数组与链表的区别是( )。

A 前者长度固定,后者长度可变

B 后者长度固定,前者长度可变

C 两者长度均固定

D 两者长度均可变

解析：

A. 前者长度固定, 后者长度可变

正确：数组的长度在创建时固定（对于静态数组），一旦定义就不能改变；而链表可以在运行期间动态地增加或减少节点，长度是可变的。

B. 后者长度固定, 前者长度可变

错误：链表的长度是可变的，因此这个选项的描述不准确。

C. 两者长度均固定

错误：数组的长度固定（对于静态数组），而链表的长度是可变的，因此这条说法是错误的。

D. 两者长度均可变

错误：数组的长度在创建时固定，不可变，而链表的长度是可变的。因此这条说法也是错误的。

解答： 

A

⑥元素a、b、c、d依次入栈，则不能得到的出栈序列是 ( ) (北京拓普空间科技)

A、abcd

B、cabd

C、dcba

D、bcda

解析：

A. abcd

这个序列是按顺序出栈的，不可能通过栈操作得到，因为出栈顺序必须是后进先出。

B. cabd

可能的操作：先出 c，再出 b，再出 a，最后出 d。因此可以得到这个序列。

C. dcba

这个序列可以直接从栈中依次出栈，先出 d，再出 c，再出 b，最后出 a。因此可以得到这个序列。

D. bcda

不可能的操作：为了得到 bcda，需要先出 b，再出 c，然后出 d，最后出 a。这是不可能的，因为在 b 和 c 出栈时，a 必须先出栈，因此不能得到这个序列。

解答： 

A、D

⑦栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（）(H3CC语言题目 南京)

A. ABCED

B. DBCEA

C. CDABE

D. DCBEA

解析：

A. ABCED

不可能得到：为了得到 ABCED，我们必须在出栈前将 E 入栈，这与顺序不符，因为 E 是最后入栈的元素，A、B、C、D 必须在 E 入栈后出栈。

B. DBCEA

可能得到：可以按照以下顺序操作：

D 出栈。

B 出栈。

C 出栈。

E 入栈。

A 出栈。

E 最后出栈（不在此序列中）。

C. CDABE

不可能得到：为了得到 CDABE，必须先出 C 和 D，但在出 D 后 A 必须在 C 和 D 之前出栈，因此不可能。

D. DCBEA

可能得到：可以按照以下顺序操作：

D 出栈。

C 出栈。

B 出栈。

E 入栈。

A 出栈。

解答： 

B、D

⑧用链接方式存储的队列，在进行插入运算时 （鲁科安全）

A、仅修改尾指针

B. 仅修改头指针

C. 头、尾指针都要修改

D. 头、尾指针有可能都要修改

解析：

A. 仅修改尾指针

部分正确：如果队列不为空，插入时仅需要修改尾指针；但如果队列为空，还需要修改头指针。

B. 仅修改头指针

错误：在插入时，通常不只修改头指针，因为插入的是尾部。

C. 头、尾指针都要修改

部分正确：在某些情况下（如队列为空时），需要修改头指针和尾指针。但一般情况下，插入时只修改尾指针。

D. 头、尾指针有可能都要修改

正确：这个选项表述最为全面。插入时，若队列为空，则需要修改头指针和尾指针；若队列不为空，仅修改尾指针。

解答： 

D

⑨10个节点的循环队列，从最后一个元素访问到第一个元素需要，遍历多少个节点 ( )（无锡信捷电气）

A.9个

B.1个

C.5个

D.10个

解析：

从最后一个元素访问第一个元素：

如果从最后一个元素开始遍历到第一个元素，实际上需要经过整个队列中的节点。因此，你需要访问 10 个节点来到达第一个元素。

假设循环队列的最后一个元素为 Node 10，从 Node 10 开始访问，依次访问：

Node 10 → Node 1 → Node 2 → Node 3 → Node 4 → Node 5 → Node 6 → Node 7 → Node 8 → Node 9

解答： 

D

⑩采用哪种遍历方法可唯一确定一棵二又树?() （中航安为）

A.给定一棵二叉树的先序和后序遍历序列

B.给定一棵二叉树的后序和中序遍历序列

C.给定一棵二叉树的先序和中序遍历序列

D.给定先序、中序和后序遍历序列中的任意一个即可

解析：

A. 给定一棵二叉树的先序和后序遍历序列

无法唯一确定：仅有先序和后序遍历无法确定二叉树的结构，因为同样的先序和后序遍历可能对应多棵不同的二叉树。

B. 给定一棵二叉树的后序和中序遍历序列

可以唯一确定：后序和中序遍历可以唯一确定一棵二叉树。通过中序遍历可以确定根节点的位置，而后序遍历可以确定节点的顺序。

C. 给定一棵二叉树的先序和中序遍历序列

可以唯一确定：先序和中序遍历也可以唯一确定一棵二叉树。先序遍历提供了根节点的信息，而中序遍历提供了左右子树的分割。

D. 给定先序、中序和后序遍历序列中的任意一个即可

不正确：仅有一个遍历序列（无论是先序、中序还是后序）都无法唯一确定一棵二叉树。

解答： 

B、C

11、已知数据域表 A 中每个元素距其最终位置不远，为节省时间，应该采用的算法是（）(智洋C++)

A、直接选择排序

B、维排序

C、快速排序

D、直接插入排序

解析：

A. 直接选择排序

选择排序的时间复杂度是 O(n2)O(n2)，对于每次选择最小元素的过程不适合处理“近乎有序”的数据。

B. 维排序

维排序（Heap Sort）虽然在最坏情况下时间复杂度是 O(nlog⁡n)O(nlogn)，但由于需要构建堆和多次调整，对于近乎有序的数据不够高效。

C. 快速排序

快速排序在平均情况下是高效的，时间复杂度为 O(nlog⁡n)O(nlogn)，但在处理近乎有序的数据时，其性能可能受到影响，特别是在选择枢轴时。

D. 直接插入排序

直接插入排序在处理近乎有序的数据时表现出色。因为在这种情况下，元素只需移动少量位置，所以其时间复杂度接近于 O(n)O(n)，且实现简单。

解答： 

D

12、数据结构可以在数据排序后，能用最快的方式找到任意指定的数据(杭州时划科技)

A、栈

B、双向链表

C、数组

D、哈希表

解析：

A. 栈

栈是一种后进先出（LIFO）的数据结构，无法高效查找特定元素。查找元素的时间复杂度为 O(n)O(n)。

B. 双向链表

双向链表允许双向遍历，但查找元素的时间复杂度也是 O(n)O(n)，因为需要遍历链表以找到特定元素。

C. 数组

数组可以通过索引快速访问，但如果数据未排序，查找的时间复杂度是 O(n)O(n)；如果是有序数组，可以使用二分查找，时间复杂度为 O(log⁡n)O(logn)。

D. 哈希表

哈希表通过哈希函数实现近乎常数时间的查找，平均情况下，查找操作的时间复杂度为 (O(1)。因此，在排序后的数据中，使用哈希表可以快速找到任意指定的数据。

解答：

D

13、现在最快且最通用的排序算法是什么? ( ）（中科能德）

A.快速排序

C.选择排序

B.冒泡排序

D. 外部排序

解析：

A. 快速排序

快速排序在平均情况下具有 O(nlog⁡n)O(nlogn) 的时间复杂度，并且常常在实际应用中表现得非常快。它使用分治法，将大问题分解为小问题，并利用递归进行排序。在许多编程语言的标准库中，快速排序是默认的排序算法。

B. 冒泡排序

冒泡排序的时间复杂度是 O(n2)O(n2)，因此在处理大量数据时效率很低。它只适用于小规模数据或教学用途。

C. 选择排序

选择排序的时间复杂度也是 O(n2)O(n2)，同样不适合大规模数据的排序。其效率低于快速排序。

D. 外部排序

外部排序通常用于处理不能完全放入内存的数据（如大型文件），而不是一种通用排序算法。虽然外部排序有效，但它不适用于内存中的小型数据集。

解答： 

A

三、总结

学习内容概述

1. 树的基本概念：

学习树的定义及其常见类型，如二叉树、满二叉树、完全二叉树、平衡二叉树等。树是一种层次型数据结构，其中节点通过边进行连接。

2. 二叉树的基本操作：

包括树的创建、遍历（前序、中序、后序和层序遍历），以及插入、删除和查找操作。

3. 树的存储结构：

学习二叉树的链式存储和顺序存储方式。链式存储中每个节点包含指向左右子节点的指针，顺序存储则使用数组表示。

4. Huffman 树和优先队列：

理解 Huffman 编码的生成过程，掌握如何通过优先队列来构建 Huffman 树。

5. 平衡二叉树（AVL 树）：

学习平衡因子和平衡调整操作，确保 AVL 树在插入和删除后依然保持平衡。

6. 树的应用：

如文件系统目录的层次结构、表达式树的求值、决策树等。

学习难点

1. 二叉树的递归遍历：

在不同遍历方式下（前序、中序、后序），需要掌握递归调用的顺序和递归终止条件，尤其在非递归实现中容易出现问题。

2. Huffman 树的构建过程：

需要理解优先队列的运作机制，以及如何将最小频率的两个节点合并以构建 Huffman 树，进而生成对应的编码。

3. 平衡二叉树的插入和删除：

在 AVL 树中，插入或删除节点后，需要重新计算平衡因子，并根据情况执行单旋转或双旋转操作，确保树的高度平衡。

4. 树的存储结构选择：

在不同场景下选择合适的存储方式（链式或顺序存储），特别是在树的动态增长或查找操作频繁的情况下，需要平衡内存使用与操作效率。

主要事项

1. 树的创建和遍历：

掌握递归与非递归的树遍历方法，并能够根据需要灵活选择不同的遍历方式，特别是在树的深度优先和广度优先遍历中。

2. 二叉树的平衡性维护：

在 AVL 树中，保持平衡的关键是理解旋转操作的必要性和操作顺序，以保证树的时间复杂度维持在 O(log n)。

3. 树的应用场景：

深入理解树在实际应用中的使用，如 Huffman 编码在压缩算法中的应用，树结构在文件目录、表达式求值、搜索引擎等中的广泛应用。

 4. 动态树的操作：

学习如何在动态变化的树结构中进行高效的插入、删除和查找操作，特别是在维护树的平衡性时，需要掌握高效的算法和数据结构。

未来学习的重点

1. 高级树结构的应用：

进一步学习红黑树、B 树、B+ 树等更复杂的树结构，并了解其在数据库、文件系统等场景中的应用。

2. 树的优化与性能提升：

研究如何在大规模数据环境下，优化树的操作性能，特别是如何减少树的高度、优化查找效率等。

3. 树与图的结合：

探索树结构与图结构的异同，并学习如何将树结构扩展到图结构，理解二者在复杂问题求解中的应用场景。

4. 树的并发与分布式操作：

研究树结构在并发环境和分布式系统中的应用，学习如何在多线程或分布式环境中保持树的高效操作和数据一致性。

标签：排序,元素,Day20,链表,查找,哈希,遍历,数据结构
From： https://blog.csdn.net/weixin_65095004/article/details/142530801