华南师范大学——数据结构期末总复习

华南师范大学2020-2021学年第1学期《数据结构》期末考试试卷(A卷)含标准答案.docx,PAGE PAGE 1 华南师范大学2020—2021学年第1学期 《数据结构》考试试卷(A卷)...

期末总复习

• 第一章 绪论
  • 算法
    • 概念
      • 算法是对特定问题求解步骤的一种描述，是指令的有限序列
      • 算法+数据结构=程序
    • 特性
      • 0或多个输入
      • 一个或者多个输出
      • 有穷性
        • 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成
      • 确定性
        • 算法中的每一条指令都必须有确切的含义，不存二义性，并且在任何条件下，对于相同的输入只能得到相同的输出
      • 可行性
        • 描述算法的每一条指令可以转换为某种程序语言对应的语句，并在计算机上可以执行
    • “好”特性
      • 正确性
        • 能满足解决问题的需求
      • 健壮性
        • 算法对非法输入的抵抗能力
      • 可理解性
        • 算法容易理解和实现
      • 抽象分级
        • 把算法分成一个个模块来写
      • 高效性
        • 时间效率和空间效率高
    • 描述
      • 自然语言
      • 流程图
      • 程序设计语言
      • 伪代码
        • 算法的语言
    • 度量方法（理解性掌握）
  • （理解性）数据结构的基本概念
    • 数据结构
      • 数据（data）
        • 概念
          • 是能输入到计算机中并且能被计算机程序识别和处理的符号，数据是计算机程序的处理对象
        • 分类
          • 整数、实数等数值数据
          • 文字、声音、图像和图形等非数值数据
      • 数据元素（data element）
        • 概念
          • 是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理
          • 数据元素是讨论数据结构是涉及到的最小数据单位，其中的数据项一般不予考虑
        • 广泛定义
          • 能独立、完整地描述问题世界的一切实体都是数据元素
        • 例子
          • 一场球赛、一门课程、棋盘布局
      • 数据项
        • 概念
          • 构成数据元素的最小单位为数据项，并且数据元素通常具有相同个数和类型的数据项
      • 数据结构
        • 概念
          • 相互之间存在一定关系的数据元素的集合
        • 分类（按视点）
          • 逻辑结构（理解）
            • 概念
              • 数据元素以及数据元素之间的逻辑关系，是从实际问题中抽象出来的数据模型，在形式上可以定义为一个二元组
              • Data_Structure=（D,R）
                • 其中D是数据元素的有限集合，R是D上关系的集合
            • 表达
              • 逻辑关系图
                • 将每一个数据元素看作一个结点，用圆圈表示，元素之间的逻辑关系用结点之间的连线表示，如果强调关系的方向性，则用带箭头的连线表示关系
            • 分类（特点，元素之间的关系）
              • 线性结构
                • 集合结构
                  • 数据元素之间就是“同属一个集合”，除此之外没有任何关系
                • 线性结构
                  • 数据元素之间存在着一对一的线性关系
              • 非线性结构
                • 树结构
                  • 数据元素之间存在着一对多的层次关系
                • 图结构
                  • 数据元素之间存在着多对多的任意关系
          • 存储结构（理解）
            • 别称
              • 物理结构
            • 概念
              • 是数据以及其逻辑结构在计算机中的表示（也称映像）
              • 存储结构除了存储数据元素之外，必须隐式或显式地存储数据元素之间的逻辑关系
            • 分类（特点，元素之间的关系）
              • 顺序存储结构
                • 概念
                  • 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
              • 链接存储结构
                • 概念
                  • 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
    • 抽象数据类型
      • 数据类型
        • 概念
          • 一组值的集合以及定义于这个值集上的一组操作的总称
      • 抽象
        • 概念
          • 抽出问题的本质特征而忽略非本质的细节，是对具体事物的一个概括
          • 无论是在数学领域还是程序涉及领域，抽象的作用都源于这样子一个事实：一旦一个抽象的问题得到了解决，很多同类的具体问题便可以迎刃而解
        • 例子
          • 水果是对苹果、香蕉、橘子等的一种抽象
      • 抽象数据类型（abstract data type,ADT）
        • 概念
          • 是一个数据模型以及定义在该模型上的一组数据的总称
          • ADT可以理解为对数据类型的进一步抽象，数据类型是指高级程序设计语言支持的基本数据类型，而ADT指的是用自定义的数据类型
          • 事实上，ADT理论催生了面向对象程序设计的诞生和发展
      • 数据结构的实现
        • 抽象层
          • ADT的定义，定义数据及其逻辑结构和所允许的基本操作的集合
        • 设计层
          • ADT的设计，是数据模型的存储表示和算法设计
        • 实现层
          • ADT的具体实现，用某种程序设计语言来实现数据结构
  • （会求）算法的时间复杂度
    • 前提概念
      • 问题规模
        • 指算法的输入量是多少，一般可以从问题的具体描述中得到，而问题规模是影响算法时间代价的最主要因素
      • 基本语句
        • 执行次数与整个算法的执行次数成正比的语句，基本语句对算法运行时间的贡献最大，是算法中最重要的操作
    • 时间复杂度
      • 概念
        • 只考察当问题规模充分大的时候，算法中基本语句的执行次数在渐进意义下的阶，称作算法的渐进时间复杂度，简称时间复杂度
      • 定义
        • 若存在两个正的常数c和n0，对于任何的n>=n0，都有T（n）<=c*f（n），则称T（n）=O（f（n））
  • （会求）算法的空间复杂度
    • 存储空间
      • 输入/输出数据所占用的空间
        • 取决于问题，和算法本身无关
      • 算法本身所占用的空间
        • 算法本身占用空间虽与算法相关，但是一般都是固定的
      • 执行算法需要的辅助空间
    • 概念
      • 算法在执行过程中需要的辅助空间的数量
    • 定义
      • S（n）=O（f（n））
      • n为问题规模
• 第二章
  • （理解性）线性表的特点、元素的存储地址、会求顺序表元素的存储地址
  • （重点掌握）单链表的插入、删除、遍历的算法（伪代码）及算法思想
  • （掌握）单链表的构造算法及算法思想
    • 头插法
    • 尾插法
  • （掌握）顺序表的插入、删除、查找算法
  • （理解）线性表和链表的比较，时间性能和空间性能
• 第三章
  • （深刻领会）栈的定义、特点，栈在计算机中的存储
    • 存储
      • 顺序存储的顺序栈
      • 链接存储的链栈
  • （理解）栈顶、栈底的含义
  • （掌握）利用栈的特点写进栈、出栈序列
  • （掌握）队列的定义特点，会写进队、出队序列，了解队列的典型应用
  • 什么是循环队列，（理解性掌握）判断队列满和空的条件
  • （掌握）在链队列中入队、出队的算法
• 第四章
  • 了解kmp算法的执行过程，理解kmp算法如何求nextj，nextj有什么用
    • kmp
      • 概念
        • kmp算法就是减少了BP算法的回溯时间，因为一些很明显的逻辑原因，导致我们根本不需要从第二个开始比，因为我们在之前的对比中，已经获取了一些信息了，我们可以从不匹配的一段开始，往后翻，找到一个和前面的字符串相同的一个串，来进行我们的下一次匹配，而这个串，是根据模式本身而定的，和匹配的串无关。这样子就能大幅度减少我们的比较次数，从而得到一个较好的时间复杂度
    • next[j]
      • 这个的值代表T[j]对应的k值，j=0时，next[j]==-1
    • 例子
      • ababc
        • -1 0 0 1 2
  • 理解二维数组按行列有限存储的寻址方式
  • 理解对称矩阵的压缩储存，三角矩阵
• 第五章（重点）
  • 树
    • 定义
    • 概念
    • 结点
      • 树中的数据元素
    • 度
      • 某节点拥有的子树个数
    • 叶子结点
      • 度为0的结点
    • 分支结点
      • 度不为0的结点
    • 有序树
      • 树中任意结点的子节点之间是有顺序关系的，不能调换的，这种树称为有序树
    • 无序树
      • 树中任意结点的子节点之间没有顺序关系，这种树是无序树，也是自由树
    • 应用
      • 求度为1和2的叶子结点的个数
  • 二叉树
    • 性质(熟练掌握)
      • 性质5.1
        • 在一颗二叉树中，如果叶子结点个数为n0，度为2的结点个数为n2，则n0=n2+1
      • 性质5.2
        • 二叉树的第i层上最多有2的i-1个结点
      • 性质5.3
        • 在一棵深度为k的二叉树中，最多只有2的k-1次方个结点
      • 性质5.4
        • 具有n个结点的完全二叉树的深度为(log2 n)取下限，+1
      • 性质5.5
        • 对于一颗具有n个结点的完全二叉树，从1开始按层序给每个结点编号，对于编号为i的结点，有以下性质
          • 如果i>1,则其双亲的编号为[i/2]，否则该结点是根节点，没有双亲
          • 如果2*i<=n，则结点i的左孩子编号为2*i，否则无左孩子
          • 如果2*i+1<=n，则结点i的左孩子编号为2*i+1，否则无左孩子
    • 要求
      • 灵活应用
    • 深刻理解并重点掌握 二叉树 前中后序遍历算法及其思想（重点），灵活应用
      • 求叶子等
    • 会写遍历序列
    • 应用
      • 重点 已知中后或前中，如何确定一颗二叉树，叶子、高度、双亲、结点的个数、左右子树交换
  • 森林
    • 定义
      • 森林是m（m>=0）棵互不相交的树的集合
    • （掌握）树、森林与二叉树的转换
      • 树转二叉树
        • 将所有的兄弟结点，都用线连起来
        • 去除原双亲结点和除了第一个孩子的连线
        • 调整层次结构
      • 森林转化为二叉树
        • 将全部树都转化为二叉树
        • 将所有二叉树的根节点相连
        • 调整结构层次
      • 二叉树转化为树或森林
        • 若双亲结点的左孩子存在右孩子，则将其右孩子、右孩子的右孩子、等等和双亲结点连起来
        • 去除原二叉树与右孩子的连线
        • 调整结构层次
  • （理解性掌握）最优二叉树
    • 哈夫曼树
      • 理解构造过程，会灵活应用
    • 哈夫曼编码
      • 理解其原则，了解其特点，会灵活应用
• 第六章（重点）
  • 深刻掌握图的定义和基本术语
    • 有向图
    • 无向图
    • 有向完全图
      • 任意顶点都直接相连的无向图
    • 无向完全图
      • 任意顶点都直接互连的有向图
    • 连通图
      • 无向图中，任意两个顶点之间都存在路径
    • 连通分量
      • 是连通的最大子图
    • 强连通图
      • 有向图中，任意两个顶点均有路径存在
    • 强连通分量
      • 是连通的最大子图
    • 应用
      • 求顶点数，求边数，不会直接让你背概念
  • 掌握度、入度、出度的计算方法，会根据存储结构（重点邻接矩阵、邻接表的表示方法）求度、入度、出度
  • 深度优先遍历
    • 时间复杂度（了解）？？？
  • （掌握）广度优先遍历
    • 时间复杂度（了解）？？？
  • 最小生成树
    • 概念
      • 生成树
        • 连通图的生成树是包含图中所有顶点的极小连通子图，就是说在这里任意添加一条边，都会产生回路，任意减少一条边，都会变成非连通，所以有n个顶点的生成树有且仅有n-1条边
      • 最小生成树
        • 无向连通网图的生成树上各边的权值之和称为该生成树的代价，在图的所有生成树中，代价最小的生成树称为最小生成树
    • 重点Prim
      • 选定一个顶点集adjvex，里面放着U中，与五个点距离最短的点，然后lowcost中放着这五个点，也就是adjvex存储的五个点与其他对应5个点的距离，然后每次都从这些距离中选出最小的，就是U中的最短边，然后将lowcost对应的位置置零，然后重复，调整adjvex，然后再重复上述步骤
    • 重点Kruskal
    • 如何求最小生成树，会求最小生成树的权值
  • 掌握拓朴排序的思想，给定一个图，重点掌握如何进行拓扑排序，会写出拓扑排序的序列
    • AOV网
      • 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样子的有向图为顶点表示活动的网，也就是AOV图
      • AOV网中不能出现回路，拓扑排序就是检测AOV网是否存在回路的方法
    • 拓扑序列
      • 一个满足若vi与vj存在路径，则vi必定在vj的前面
      • 拓扑序列不唯一
    • 拓扑排序
      • 对一个有向图构造拓扑序列的过程就叫拓扑排序
      • 基本思路
        • 选择一个没有箭头指向的点并输出
        • 从图中去除这个点，并且去除以该点为尾的弧
        • 重复上述步骤，直到不能再去除
      • 结果
        • 全部点被输出，说明其不存在回路
        • 有点剩下，说明其存在回路
  • 会计算关键路径，及关键路径的长度
    • AOE网
      • 在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样子的有向图为AOE网
      • 没有入边的顶点称为源点，没有出边的顶点称为出点
      • 只有进入某顶点的各项活动都已经结束了，该顶点所代表的事件才能发生
    • 关键路径
      • 具有源点到终点的最大路径长度的路径，关键路径上的活动称为关键活动
  • 采用邻接矩阵的表示方法构造一个无向图的算法
  • 采用邻接表的表示方法构造一个无向图的算法
• 第七章（重点）
  • 查找的基本概念
    • 关键码
      • 可以标识某个数据项的东西，就是比较排序的时候用到的值
    • 查找
      • 静态查找
        • 不成功时只返回一个标志
      • 动态查找
        • 不成功时会将被查找的记录插入到集合中
  • 线性表的查找技术
    • 顺序查找（重点）
      • 思想
        • 从存储结构的一端开始，挨个将待查找元素和相应记录比较，成功则返回该记录在表中的位置，不成功则返回不成功标志
      • 递归
      • 非递归
      • 时间复杂度
        • O（n）
      • 存储结构
        • 顺序存储结构
        • 链接存储结构
    • 折半查找（重点）
      • 思想
        • 假设有序表按关键码有序排列，每次都取中间元素和查找元素比较，若相等，则查找成功，若不相等，再往两边的区间去查找，重复上述步骤，直至查找成功
      • 递归
      • 非递归
      • 时间复杂度
        • log2 n
      • 存储结构
        • 顺序存储结构
  • 树表的查找技术
    • 二叉排序树（重点）
      • 概念
        • 若左子树不空，则左子树上的所有结点均小于根结点
        • 若右子树不空，则右子树上的所有结点均大于根节点
        • 左右子树都是二叉排序树
        • 中序遍历可以得到一个有序序列
        • 采用二叉链表进行存储
      • 插入
      • 删除
      • 构造
    • 平衡二叉树
      • 概念
        • 根节点的左子树和右子树的深度最多相差1
        • 根结点的左子树和右子树都是平衡二叉树
      • 平衡因子
        • 结点的平衡因子是该结点的左子树的深度和右子树的深度之差
      • 插入
      • 删除
      • 构造（理解）
  • 散列表的查找技术
    • 散列查找
      • 概念
      • 算法
      • 算法思想
    • 处理冲突的方法（重点）
      • 开，闭，如何处理
• 第八章（重点）
  • 排序的基本概念（了解）
    • 将一个记录的任意序列重新排列成一个按关键码有序的序列
  • 直接插入排序（理解）
  • 希尔排序（重点）
    • 方法
    • 过程
  • 起泡排序（重点）
    • 方法
    • 过程
  • 快速排序（重点）
    • 方法
    • 过程
  • 堆排序（重点）
    • 定义
    • 调整过程
    • 排序过程