• 数据对象是具有相同特性的数据元素的集合,它是数据的子集。
  • 对一个算法的评价,不包括并行性方面的内容。
  • 数据结构主要涉及两个方面:一是数据元素本身,二是数据元素之间的相互关系
  • 当结点之间存在M对N(M:N)(多对多)的联系时,称这种结构为图状结构
  • 广义表的长度和深度是两个用于描述其结构的重要概念:
    • 长度:广义表的长度是指它的最外层中元素的个数。
    • 深度:广义表的深度是指它的嵌套层数。单个原子(不是广义表的)的深度定义为 0。只包含原子的简单列表(不包含子表)的深度是 1。对于包含子表的广义表,其深度是其所有子表的最大深度加 1。
  • 树节点的度指的是其每个节点拥有的最多子节点数目
  • 二叉树是一个度为2的有序树
  • 对一棵由算术表达式组成的二叉语法树进行前序、中序、后序遍历,输出的分别是前缀(Prefix Expression)、中缀(Infix Expression)、后缀表达式(Postfix Expression)
  • 开放地址法:Open addressing,链接法:Chaining
  • 拓扑排序时遇到两个入度为0时将从小到大的顺序入栈然后再弹出(也就是优先大序号)
  • 队列的插入情况要考虑队列为空的情况,也就是头节点指针也可能发生修改
  • 二分查找变化范围记得+1(比较值小于查找值)-1(比较值大于查找值)
  • 通常从四个方面评价算法的质量:Correctness、Scalability、Robustness and Error Handling、Efficiency
  • AOV网是一种有向无回路的图
  • AOV网(Activity On Vertex network)是一种用于表示活动的有向图,在这种图中,顶点表示活动,而有向边表示活动之间的先后关系。
  • 完全图(不管有向无向)的邻接矩阵只有对角线(特指如(1,1)的点)的点全是0
  • 教材上的B树详解
  • 带权路径长度是指树中所有叶子节点的路径长度与其权重的乘积之和
  • 数据的逻辑结构被分为Set Structures、 Linear Structures 、Hierarchical Structures、Graph-Based Structures
  • 一种抽象数据类型包括Data Representation、Operations
  • 在图的邻接表中,每个结点被称为vertex node,通常它包含三个域:一是adjacent vertex field;二是weight field;三是link field
  • 用具有n个元素的一维数组存储一个循环队列,则其队首指针总是指向队首元素的前一位置,该循环队列的最大长度为n-1
  • 在一个索引文件的索引表中,每个索引项包含对应记录的key value、pointer
  • 算法:解决问题的有限运算序列
  • 由两个栈共享一个向量空间的好处是节省存储空间,降低上溢发生的机率
  • 循环队列出队后要取模(% m,m为初始队列的元素总数)
  • 非空广义表的表头可以是子表或原子
  • 不定长文件是指记录的长度不固定
  • 数据的逻辑结构是从逻辑关系上描述数据,它与数据的Storage Structure无关,是独立于计算机的

排序特性表

  • 冒泡排序(Bubble Sort):
    特性:简单,但效率低下;稳定排序。
    时间复杂度:平均和最坏情况 O(n²),最好情况 O(n)。

  • 选择排序(Selection Sort):
    特性:简单,但效率低下;不稳定排序。
    时间复杂度:平均、最好和最坏情况都是 O(n²)。

  • 插入排序(Insertion Sort):
    特性:效率较高于冒泡和选择排序;稳定排序。
    时间复杂度:平均和最坏情况 O(n²),最好情况 O(n)。

  • 希尔排序(Shell Sort):
    特性:基于插入排序的改进,分组插入排序;不稳定排序。
    时间复杂度:取决于间隔序列,最坏情况可达 O(n²),通常比 O(n²) 快。

  • 归并排序(Merge Sort):
    特性:高效且稳定;使用分治法;需要额外的内存空间。
    递归分子数组,最后分到一个数组一个值时逐级排序合并
    时间复杂度:所有情况都是 O(n log n)。

  • 快速排序(Quick Sort):
    特性:非常高效;使用分治法;不稳定排序。
    时间复杂度:平均和最好情况 O(n log n),最坏情况 O(n²)。

  • 堆排序(Heap Sort):
    特性:高效;基于堆数据结构;不稳定排序。
    通过创造一个最大堆(最小堆)并且通过不断选出根节点将其与堆最后的节点交换,再将堆的大小逐步缩小,最后缩小到1实现排序
    时间复杂度:所有情况都是 O(n log n),对一个分支的操作是O(log n)

  • 计数排序(Counting Sort):
    特性:非比较排序;非常高效于小范围整数;稳定排序。
    时间复杂度:O(n + k),其中 k 是整数的范围。

  • 桶排序(Bucket Sort):
    特性:非比较排序;分布式排序;稳定排序。
    时间复杂度:平均 O(n + k),最坏 O(n²)。

  • 基数排序(Radix Sort):
    特性:非比较排序;按位排序,适用于整数和字符串;稳定排序。
    时间复杂度:O(nk),其中 k 是数字的最大位数。

最小生成树

  • 克鲁斯卡尔算法:先按照权重对边从小到大排序,然后依次插入森林,将后面形成的树不断根据边合并树,如果出现边两端都是同一树中已有节点则忽略
    特性:用于边少的图很便捷
    时间复杂度:O(ElogV),其中 E 是边的数量,V 是顶点的数量
  • Prim算法:首先选择一个顶点加入MST集合,不断在连接MST集合和非MST集合顶点的所有边中选择权重最小的边,并将这条边以及它的非MST端点加入MST集合
    特性:适用于大量边的稠密图
    时间复杂度:O(E+VlogV),其中E 是边的数量,V 是顶点的数量