【专业课】数据结构（分数：96）

1. 简述数据结构的定义和组成

数据结构是 相互之间存在的 一种或多种特定关系的 数据元素 的集合

数据结构包括：

• 逻辑结构
  • 线性结构
    • 线性表、栈、队列
  • 非线性结构
    • 集合、树、图
• 存储结构
  • 顺序存储、链式存储、索引存储、散列存储
• 数据的运算
  

  2. 复杂度

  时间复杂度：算法中所有语句的频度
  空间复杂度：算法运行过程中使用的辅助空间

  3. 抽象数据结构

  相当于定义了数据的逻辑结构和数据的运算

  4. 数据的基本单位和最小单位

  数据的基本单位：数据元素
  数据的最小单位：数据项
  学生的记录就是一个数据元素，由姓名，学号，性别等数据项组成

  5. 简述一个好的算法应该达到哪些目标？

  1. 正确性：算法应当能够正确地解决求解问题
  2. 可读性：算法应当具有良好的可读性
  3. 健壮性：当输入非法数据时，不会产生莫名其妙的输出结果
  4. 效率与低存储需求：
     • 效率是算法执行的时间，对同一个问题如果有多种算法可以求解，则执行时间短的算法效率高
     • 存储量需求是指算法执行过程中所需的最大存储空间
       

       6. 算法的五个特征

  5. 有穷性：一个算法必须在有限步骤和有限时间内完成
  6. 确定性：相同输入只能得到相同输出；组成算法的每条指令是清晰的、无歧义的
  7. 可行性：每一步都是可实现的，具有可行性
  8. 输入：有0个或多个由外部提供的量作为输入
  9. 输出：产生至少1个量作为输出
     

     7. 线性表和顺序表以及链表的区别

• 线性表是逻辑结构，表示元素之间一对一的相邻关系
• 顺序表和链表是存储结构
  • 顺序表是逻辑上相邻的两个元素在物理位置上相邻
  • 链表不要求逻辑上相邻的元素在物理位置上也是相邻的
    

    8. 顺序表和链表存储的优缺点

• 顺序表存储
  • 优点：存储速度高效，可以实现随机存储，数据存取密度比较大
  • 缺点：插入和删除比较慢，不可以增加长度
• 链表存储
  • 优点：插入和删除速度快，保留原有物理顺序，不会发生存储溢出的问题
  • 缺点：查找速度慢，需要循环链表访问
    

    9. 头指针和头结点的区分

• 头指针是指链表指向第一结点的指针，若链表有头结点，则是指向头结点的指针
• 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义
  

  10. 简述链表中引入头结点带来的优点

  1. 第一个位置的插入删除更加方便
  2. 使用头结点，无论表是否为空，头指针都指向头结点
     

     11. 头插法和尾插法的区别

• 头插法：不断将新节点插入到头结点，但头插法会改变数据输入顺序
• 尾插法：将新节点插入到队尾，不会改变数据的顺序
  

  12. 数组和线性表的关系

• 线性表与数组都是数据结构，只是描述的角度不同
• 线性表是从逻辑结构的角度来说，而数组是从物理存储的角度来说的
• 线性表可以用数组存储，形成顺序表
  

  13. 数组和链表的区别

  1. 物理存储结构不同：数组是顺序存储结构，链表是链式存储结构；
  2. 内存分配方式不同：数组的存储空间一般采用静态分配；链表的存储空间一般采用动态分配；
  3. 元素的存取方式不同：数组元素为直接存取，链表元素的存取需要遍历链表
  4. 元素的插入和删除方式不同：数组在进行元素插入和删除时，需要移动数组的元素，而链表不需要
     

     14. 循环队列的顺序表中，为什么要空一个位置？

     为了区分队空和队满的情况，如果不空一个位置，则判断队空和队满的条件是一样的
     当 (rear + 1 == front) % MAX_CNT 时表示栈满
     

     15. 串是一种特殊的线性表，请从存储和运算两方面来分析它的特殊之处

     串是零个或多个任意字符组成的有限序列。

• 存储方面：串中每个存储单元只存储一个字符
• 运算方面：串有连接、判串相等、求子串和子串替换等基本运算
  

  16. 字符串匹配算法

• 串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置
• 朴素模式匹配算法：将模式串的字符与主串中的每一个子串一一进行比对
• KMP算法：指向主串的指针不回溯，依次往后进行比较，而指向模式串的指针需要回溯，当某个位置的字符匹配失败时，模式串指针根据next数组指向相应的位置，再进行匹配。
  

  17. 二叉树与度为2的有序数的区别

  1. 二叉树允许为空，后者至少要有三个结点
  2. 二叉树需要区分左右孩子，后者不需要
     

     18. 完全二叉树和满二叉树的区别

• 满二叉树中每层都含有最多的结点
• 完全二叉树指有n个结点的二叉树，最后一个分支结点的序号是n/2
  

  19. 二叉排序树和平衡二叉树的区别

• 二叉排序树：树中每个节点的值都比左子树所有节点的值大，比右子树中所有节点的值小，同时左右子树本身也是二叉排序树。
• 平衡二叉树：左子树和右子树的深度之差不超过1
  

  20. 什么叫二叉树的遍历

  沿着某条搜索路径，依次对树中每个结点仅做一次访问。

  21. 哈夫曼树和哈夫曼编码的作用是什么？什么是前缀编码？

• 哈夫曼树：带权路径长度WPL最小的二叉树；
• 哈夫曼树作用：用来实现哈夫曼编码以及后续的解码；
• 哈夫曼编码作用：用来压缩网络传输的文件；
• 前缀编码：编码不是任何其他编码前缀的编码。

41. 什么是二叉搜索树，二叉搜索树有什么特征，如何向二叉搜索树中插入新的元素

二叉搜索树是一棵二叉树，
其中每个节点的值都比左子树所有节点的值大，比右子树中所有节点的值小，
同时左右子树本身也是二叉树。

二叉树的特征包括：

1. 节点值有序性：从根节点出发按照中序遍历读取到的值是递增的
2. 查找效率高：理想状态下（树高度接近平衡）时间复杂度为O(log⁡n)。
   {时间复杂度：n=2^h+1-1 -> h≈log2(n+1)-1，共logn层，每层1次比较}
   {树高度平衡：一棵树的左右子树的高度差较小}
3. 动态插入和删除：支持动态操作，同时保持树的有序性

插入新元素的方法是递归或迭代地查找适当地位置，将新元素插入，具体步骤：

• 从根节点开始，如果树为空，新元素就成为根结点
• 如果新元素值小于当前节点，就递归地向左子树查找
• 反之向右子树查找
  

  42. 快速排序算法的思想

  快速排序算法基于分治思想，核心思想是通过选择一个基准值，将数组分为小于基准值和大于基准值的两部分，然后递归地对两个部分进行排序

• 平均时间复杂度O(nlogn)：分割平衡，共logn层，每层遍历整个数组一次
• 最坏时间复杂度O(n²)：基准值每次选最大或最小，导致递归退化成类似链表的结构，递归深度变成n层
• 空间复杂度O(logn)