【数据结构】考研真题攻克与重点知识点剖析 - 第 1 篇：绪论

前言

• 本文基础知识部分来自于b站：分享笔记的好人儿的思维导图与王道考研课程，感谢大佬的开源精神，习题来自老师划的重点以及考研真题。
• 此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析，本人技术有限，最终数据清洗结果不够理想，相关CSDN文章便没有发出。
• 从这篇文章开始，这里我将按章节顺序，围绕考研真题展开计算机组成原理总共8章的知识,边学习边整理数据。

（考研真题待更新）

欢迎订阅专栏：408直通车

请注意，本文中的部分内容来自网络搜集和个人实践，如有任何错误，请随时向我们提出批评和指正。本文仅供学习和交流使用，不涉及任何商业目的。如果因本文内容引发版权或侵权问题，请通过私信告知我们，我们将立即予以删除。

第一章 绪论

概述

数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和操作的学科

• 一些问题无法用数学公式和方程描述，只能用描述非数值计算问题的数学模型，如表、树、图等具有逻辑关系的数据
  

章节串联

基本概念和术语

• 数据：能被计算机处理的符号集合

  • 

  • 学生表

• 现代计算机处理的数据

• 数据元素：数据的基本单位，若干数据项组成

  • 

  • 个人记录

• 数据项：不可分割的最小单位

  • 学号、姓名

• 数据对象：性质相同的数据元素集合，数据的子集
  

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

数据结构三要素

逻辑结构

• 逻辑结构

  • 概念

    • 指数据元素之间的逻辑关系，与数据的存储无关，独立于计算机的

  • 分类

    • 线性结构

      • 一般线性表

      • 受限线性表

        • 栈、队列、串

      • 线性表推广

        • 数组、广义表

    • 非线性结构

      • 集合结构
        

      • 树形结构
        

      • 图状结构
        

存储结构/物理结构

• 存储结构/物理结构

  • 概念

    • 指数据结构在计算机中的表示（映像）

  • 分类

    • 顺序存储

      • 逻辑上相邻的元素存储在物理位置上也相邻的存储单元中

    • 链式存储

      • 借助指示元素存储地址的指针来表示元素之间的逻辑关系

    • 索引存储

      • 存储元素信息的同时，建立附加的索引表

        • 类似按姓名排序的手机通讯录

    • 散列存储

      • 根据元素的关键字直接计算出该元素的存储地址（哈希存储）

数据的运算

• 运算与实现：对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现
  

小结

抽象数据类型的表示与实现

数据类型=值的集合+值集合上的一组操作

• 约束变量或常量的取值范围

• 约束变量或常量的操作

抽象数据类型

• 

  • 数据对象

  • 数据关系：数据元素间逻辑关系的定义

  • 基本操作

    • 基本操作名（参数表）

      • 赋值参数：只为操作提供输入值

      • 引用参数：&打头，可返回操作结果

    • 初始条件

      • 执行操作前，数据结构和参数应满足条件

    • 操作结果

      • 操作正常完成后，数据结构变化和返回结果

• C语言实现抽象数据类型

  • 用已有数据类型定义描述它的存储结构

  • 用函数定义描述它的操作

小结

算法和算法评价

算法的基本概念

• 概念

  • 算法是对特定问题求解步骤的一种描述，指令的有限序列，每条指令表示一个或多个操作

• 重要特性

  • 有穷性
  • 确定性（无二义性）
    
  • 可行性、输入、输出

• 算法设计要求

  • 正确性、可读性（晦涩难懂可能隐藏错误）、健壮性（当输入非法数据，能恰当做出反应）、高效性
    
    

小结

算法效率的度量

（渐近）时间复杂度

• （渐近）时间复杂度
  
  
  
  
  
  
  

  • 概念

    • 算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作：T(n) = O( f(n) )

    • 基本语句：执行次数最多、重复执行次数与算法执行时间成正比的语句

  • 分类
    

    • 最好时间复杂度

    • 平均时间复杂度：所有可能输入实例在等概率条件下，算法的期望运行时间

    • 最坏时间复杂度：默认情况下算这个

  • 计算方法

    • 找出语句频度最大的那条语句作为基本语句

    • 计算基本语句的频度得到问题规模n的某个函数法 f(n)

    • 取其数量级用符号“O”表示

  • 常见复杂度排序

    • O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

  • 计算规则

    • 加法规则： O( f(n) ) + O( g(n) ) = O( max( f(n), g(n) ) )

    • 乘法规则：O( f(n) ) × O( g(n) ) = O( f(n) × g(n) )

  • 经典例题

    • 

    • 

    • for(int i=0;i<n;i++){ //该语句执行n+1次，因为最后条件判断不满足还有一次
      干点啥; //只执行n次
      }

小结

空间复杂度

• 算法所需存储空间的度量：S(n) = O( f(n) )

• 算法本身要占据的空间+辅助空间（算这个，注意递归深度也是）

• 算法原地工作：算法所需的辅助空间为常量，O(1)

考研真题

408 - 2023

（考研真题待更新）