专业课真题小题考点

基础考点

评价算法应该从正确性、可读性、健壮性、高效率与低存储需求来考虑
算法具有有穷性、确定性、可行性、输入、输出
数据结构包含：存储结构、逻辑结构和数据的运算。
数据的存储结构主要有：顺序存储、链式存储、索引存储、散列存储
⚠️ 记录是文件中可存取的基本单位，数据项是文件中可使用的最小单位
数据结构中被定义成（K, R），其中 K 是数据元素的有限集合，R 是 K 上的关系有限集合
- 数据结构是带有结构的数据元素集合
数据元素是数据基本单位，一个数据元素可用若干数据项组成 ，数据项是数据的不可分割的最小单位
⭐ 抽象数据类型一个特点是抽象数据类型的用户看不到抽象数据类型的数据存储及其操作的实现
- 一个抽象数据类型包括数据元素，元素之间的关系以及元素的操作
- 一个抽象数据类型包括数据和操作两个部分
- 抽象数据类型是指数据逻辑结构与之相关的一组运算
- 抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用数据对象、数据关系和基本操作集这样的三元组来表示。
数据对象：具有相同特征的数据元素的集合
逻辑结构包含：线型和非线型，其中非线型包括：集合、树型、图型。、
⭐ 结构化程序设计中三种基本结构：顺序结构、选择结构（分支结构）、循环结构
算法的五个特征：
- 有穷性：保证在有限步骤之后结束，并不是无限
- 确定性：算法每一个指令都必须有明确的含义不能是模棱两可
- 可行性：每个操作步骤的必须在有限时间完成
- 输入：算法可以有一个或多个输入，也可以没有输入
- 输出：可以有一个或多个输出，没有输出的算法是没有意义的

c 语言

*在 C 语言中整型、字符型、float 型之间关系：整型+float 型 = float 型、整型 字符型 = 整型、字符型+float 型 = float 型
- 从大到小关系为：float 型 > 整型 > 字符型（大吃小）
if 语句后面的判断条件可以跟任意表达式
- ⚠️ 在C语言中，如果if语句后面没有使用大括号{}，那么if只会控制紧跟其后的一条语句。
for语句里面包含（初始化语句、循环条件、循环变化量）其中三个都可以省略，变成死循环，或者省略循环条件，变成死循环
- :warning:e .g. for(inti👨 ;i==0😉 printf(“%d”,i—); 会循环0次，因为循环条件是i=😮 （相等判断）为false，即不会进入循环
C语言函数定义不可以嵌套，函数可以嵌套
常量指针不能进行自增或自减运算；&s 返回的是整个数组的地址，也不能进行加减运算
文本文件存储：
eg：-8765 在文本文件中存储为字符串 “-8765”，包含 5 个字符：负号(1 字节) + 8(1 字节) + 7(1 字节) + 6(1 字节) + 5(1 字节)
- 每个 ASCII 字符占 1 字节，共需 5 字节
二进制文件存储：
-8765 用二进制存储时，因为在 16 位整型范围，只需要 2 字节(16 位)就能表示 [-32768, 32767]

运算符表达式

运算符优先级排序（从高到低）：() 括号----->! 逻辑非------>&& 逻辑与------>= 赋值------>
- 在有多个&&时，按照从左到右的顺序计算（左结合），同时要注意&&的短路特性【左边为假则整体为假】，||也是如此【左边为真则整体为真】
括号运算符最高
算术运算符优先级高于关系运算符
关系运算符优先级高于逻辑运算符
赋值运算符优先级最低

指针

⭐ ⚠️ **⚠️ 设 int b [3] [ 3 ]; 则数组元素 b [1] [2] 用指针表示为：*(*(b + 1) + 2) **
- 本题解题步骤：
  - b+i => 指针 b 向后移动 i 行。
  - *(b+i) 表示对 i 行的首地址
  - *(b + 1) + 2 表示第 1 行第 2 列元素的地址
  - *(*(b + 1) + 2) 表示对第一行第二列元素解引用，即取值
- 即 b[i][j] 用指针表示为：*(*(b + i) + j)
- 补充知识点：
  - 一维数组：数组名是指向第一个元素的指针。二维数组：数组名是指向数组第一行的指针，即 b [0] 的指针。
  - 注意下标均是从0开始
对于一个具 n 个结点的线性链表，在已知的结点 *p 后插入一个新结点的时间复杂性为 O(1)
- *已知 p（若改为&p 一样），意味着我们已经有办法直接访问到 p 所指向的内存地址，则不用遍历到该结点所在位置。
解析：因为 s 是二级指针，不能直接赋值字符串常量，只能有 *s = "hello" 或 **s = 'h'
- *若题目改成一级指针 char s，*S 表示 S 所指向的地址的内容，默认指向第一个字母，则正确的语句为 *s = 'h'

线性表

n个元素的线性表第 i 个位置插入元素，平均移动 n/2 次，需移动 n-i+1 次元素
- 同顺序表查找区分开，顺序查找比较次数：n-i+1，平均查找长度为:（n+1)/2
删除含 n 个元素的线性表第 i 个位置的元素，平均移动 (n-1)/2 次，需移动 n-i 次元素
- ⚠️做题注意：先判断是插入删除还是查找，然后再看是移动还是比较，最后看是否平均，如果插入删除：插入平均移动n/2 、删除平均移动n-1 /2
  - 如果是查找的话，顺序表比较次数：n-i+1，平均查找长度n+1 /2
在插入或删除第一个元素时单链表比顺序表效率高，单链表无需移动元素，仅需修改指针，时间复杂度 O(1)
- 若单链表删除中间元素或尾部则需要遍历到该元素才能进行删除，故没有线性表高效
- 总结：链式存储在插入和删除操作方面具有较高的效率，只需要修改指针链接即可。而顺序存储在插入和删除操作方面效率较低，因为它需要移动大量元素以保持数据的连续性
  - 顺序表适宜于做查找这样的静态操作，顺序存储：访问某一结点、查找某结点前驱、删除尾结点的时间复杂度都是O（1）
⭐ 链式存储设计时，结点内的存储单元地址一定连续，结点外的存储单元地址可以是任意的------带内部的地址一定是连续
- 连续存储设计，存储单元地址一定连续
线性表的顺序存储结构是一种随机存取的存储结构，其线性表的链式存储结构也是一个随机存取的存储结构
- 顺序表的存储结构是顺序表，其具有随机存取的特点
- 顺序表和链表都可以顺序存取----------不是存储
- 链式存储比顺序存储可以更好的表示各种逻辑结构
长度为n的线性表中第一个位置插入一个元素，顺序存储结构复杂度为O(n)，采用链式存储结构复杂度为O(1)
- 第一个位置插入元素，顺序存储需要移动n个元素，链式存储不需要移动，只需要修改头指针和新节点的指针即可。

⭐ 链表操作

⚠️ 注意:

等号前面->要理解成指针，等号后面->理解成结点
- e.g. p->next=q->next 是指P的后继指针指向q的后继结点
- p-> Prior-> next = P-> next 是理解成p的前驱结点A的后继指针指向P的后继结点
双向链表插入需要借助后继结点，删除需要借助前驱结点
- 插入新结点顺序：是先用新插入结点的指针分别指向其后继和前驱

⚠️ 在带有头结点的双链表L中，判断指针P所指结点是第一个元素结点的条件是：L->next==p、p->prior==L-----判断的话必须是双
⚠️在一个附设头结点的双向链表中删除 P 所指结点的操作是：
- 第一步：p-> Prior-> next = P-> next；（A 的后继指向 C）
- 第二步：P-> next-> Prior = P-> Prior；（C 的前驱指向 A）【从左到右写】
- 第三步：free(P);
  - 理解图： p 默认指向 B
- 若在单向链表删除p所指的结点A后面的结点操作为：q = p->next; p->next = q->next; free(q)
  - q 的作用是 临时存储要被删除的结点，用于释放已删除结点空间
设指针变量 P，指向单链表结点 A，指针变量 S，指向被插入结点 A 后面的结点，则操作为：s—> next = p—> next、p-> next = s; 也是单链表的头插法
⚠️ ⭐ 双向链表交换结点：
- P指向B，Q指向C，交换BC
- 核心
  - 让B后继指针指向D，让D的前驱指针指向B，让A的后继指针指向C，让C的前驱指针指向A，然后C和B再相互链接（C的后继指向B，B的前驱指向C，只能放在最后）
  - p->next=q->next q->next->prior😛 p->prior->next=q q->prior=p-prior q->next😛 p-prior=q
设指针变量 p 指向双向链装中结点 A，指针变量 q 指向被插入结点 B，要求给出在结点 A 的后面插入结点 B 的操作序列(设双向链装中结点的两个指针域分别为 left 和 right)：
- 核心：
  - 让B的前驱指针指向A ，让B的后继指针指向C，让C的前驱指针指向B，让A的后继指针指向B （先让新插入的结点分别指向A和C，再更新A和C的指向）
  - 1、q->left😛 2、q-right=p->right 3、p->right->left=q 4、p->next=q（必须在最后一步）
  - ⚠️即p-next=q必须在最后一步，其中2和3在某种情况下也可以交换
- 若题目中是删除结点 B，则分为两步：
- 核心：
  - 让A的后继指针指向C，让C的前驱指针指向A
  - p->right=q->right q-right->left😛
⭐ 常见链表
- 单循环链表：单循环链表和普通单链表的区别在于，最后一个结点的 next 指针指向头结点，从而使得链表形成一个环。
  - 但是，插入尾结点仍然需要遍历整个链表，时间复杂度为 O(n)，因为需要找到末尾结点。
- 带尾指针的单循环链表：带尾指针的单循环链表可以直接访问尾结点，无需遍历整个链表--------------尾指针可以直接访问尾结点不用经过遍历
- 带头结点的双循环链表：带头结点的双循环链表是双向链表，并且头结点和尾结点都指向循环结构中的相邻结点。
  - 插入尾元素时，直接访问尾结点指针并插入，不需要遍历，时间复杂度为O（1）
  - 删除尾结点：直接访问尾结点指针进行删除，不需要遍历，时间复杂度为O（1）
  - 但带头结点的双向循环链表比带尾指针的单循环链表灵活性更高，因此更推荐使用带头结点的双向循环链表

栈和队列

⚠️ 若一个栈的输入序列是1，2，3，.，n，输出序列的第一个元素是n，则第i个输出的是：n-i+1
⭐ ⚠️ n个不同的元素入栈，可能的出栈顺序有 ---------（卡特兰数）
⭐ 栈的应用：括号匹配、表达式求值、递归、二叉树的遍历、图的深度优先搜索
- 队列的应用：在计算机系统中的应用、树的层序遍历、图的广度优先搜索
- ⭐ 其中：图的深度优先搜索是类似树的先序遍历，是栈的应用，广度优先搜索是类似于二叉树的层序遍历，是队列的应用
前后缀表达式求值（前缀：从后往前入栈，后入栈放前面进行运算，后缀：从前往后入栈，先入栈放前面进行运算）
⭐ 仅在表尾进行插入和删除操作的线性表称为栈，修改原则为后进先出
- 队列是表头删除，表尾插入
⚠️栈的入栈和出栈均遵循：：出栈要先取出元素再更新指针，入栈就先更新指针在放入元素
- 若设sq为一个顺序存储的栈，变量top指示栈项元素的位置。作进栈操作时，必须判别栈是否已满(top==maxsize-1); 如果把栈顶元素取到X中（指出栈操作，将出栈的元素的值保存到变量 X 中）需执行下列语句: x=sq[top--]（或者x=sq.elem[top]，sq.top=sq.top-1)
  - 入栈是：sq.top😒 q.top+1，sq.elem[top]=x
  - 这里top指针是向上增长的，top初始位于-1或者0，入栈指针+1，出栈指针-1
- ⚠️若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，x进栈的操作为：top=top-1，V[top]=x，出栈操作为：x=V[top]，top=top+1
  - 这里top初始位置是位于n+1，表示是向下增长，入栈指针-1，出栈指针+1
  - 出题陷阱：将top指针放在n+1处
链式栈，栈顶指针为top，将指针p所指结点插入栈顶的语句依次为：p->next=top和top=p
- 这里默认是用单链表，而且栈顶相当于头指针，栈可以理解成头插法（没有头结点的头插法）、队列可以理解成尾插法

循环队列

⭐ 若题设中具有 MAXSIZE 个单元顺序循环队列，则可用单元为 MAXSIZE-1 个
具有 n 个单元的循环队列，队满时共有 n-1 个元素
- ⚠️若题目中没说明 rear 和 front 的时候，可用单元和队满元素个数均为 n-1 或 MAXSIZE-1
⚠️循环队列 front 为队头指针，rear 为队尾指针，采用数组 elem [n] 作为存储空间：
队列长度（当前队伍元素个数）：（rear-front+n）%n
**队满条件：（rear+1）%n == front **
**队空条件： rear == front **
循环队列中插入或删除元素时；操作：在尾结点后插入，在首结点处删除（尾插首删），即rear每插入一结点指针+1，front每删除一结点指针-1（尾插+1，首删-1，互不干涉）
- 删除（出队）：
  - front 😦 front+1)% QUEUEMAX
  - 删除操作不改变 rear 的位置。
  - 会引起循环队列对头位置发生变化
- 插入（入队）：
  - rear 😦 rear+1)% QUEUEMAX
  - 插入操作不改变 front 的位置。

数组与广义表

对称矩阵压缩（一般为下三角矩阵压缩）存储成数组，则数组长度为 n(n+1)/2，下三角矩阵元素为 n²
- 若为上三角矩阵压缩，如题所示（19 年）：
  - 答案：
    - ⚠️上三角存储即邻接矩阵上三角部分按照数组顺序填，下三角统一用无穷符号来填
    - 带权有向图，且没有提到自环的存在。因此，所有的顶点 i 到自身 i 的权值默认为 0----------无向图也是如此。
广义表的长度可以通过转换成树，其深度为其树中 o 结点的所在的最大层数或者通过数出最深嵌套层的括号数
⚠️稀疏矩阵通常使用三元组顺序表、行逻辑链接的顺序表和十字链表法，稀疏矩阵压缩后会失去随机存取的特性-
⭐ 三元组存储稀疏矩阵所需字节数：设有 n 个非零元素则所需字符数为 (n+1)*3*每个元素所占字节数（+1是因为表头也占字符）

数组存储公式

二维数组的存储`m*n`

行优先和总列数n相关
- 下标从0开始：loc(aij) = loc(a0,0)+[i*n+j]*d
- 下标不从0开始A[c1...d1, c2...d2]：loc(aj) = loc(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*d
列优先和总行数m相关
- 下标从0开始：loc(aij) = loc(a0,0)+[j*m+i]*d
- 下标不从0开始A[c1...d1, c2...d2]：loc(aj) = loc(c1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*d

三维数组存储

⭐ ⚠️ 对于三维数组m*n*z，以行为主序，a[i][j][k]地址计算：loc(a[i][j][k])=loc(a000)+[(i*n*z)+j*z+k]*d
- ⚠️ 如果数组不从首地址开始 loc(a[i][j][k]) = loc(a[b,c,d]) + [(i - b)*n*z + (j - c)*z + (k - d)] * d ------i,j,k减去对应的首地址
注意：
- 若矩阵下标从1开始，则i和j减1，若压缩后的一维数组从1开始，则算出来的k再加1

矩阵压缩

三角矩阵的压缩存储（三角矩阵是对称矩阵的一种）

⚠️三角矩阵（对称矩阵）顺序压缩到一维数组中，其长度至少为：n(n+1)/2--------也为元素个数
三角矩阵均为n阶方阵
按行序存储，a[i][j]与s[k]的对应方式：

\begin{align} \pmb{\text{下三角： } k=i(i+1)/2+j} \\ \text{上三角：}k=n(n+1)/2 \\ \pmb{\text{计算地址：}loc(aij) = loc(a0,0)+[i(i+1)/2+j]*d} \end{align}

若对称矩阵为（i=j）的存储地址的下标为，即：a[i][i]=i(i+1)/2 +i=i(i+3)/2

注：⚠️若矩阵下标从1开始，则i和j减1，若压缩后的一维数组从1开始，则算出来的k再加1

对角矩阵的压缩存储

非零元素分布在主对角线上和其他对角线上，其余元素为0

地址计算：

m对角矩阵，其m=2b+1，m为所有对角线的条数，b为主对角上面或下面对角线的条数
用一维数组存储，k=i(2b+1)+j-i=im+j-i（下标均从0开始）
- 地址计算：loc(aij) = loc(a0,0)+[i(2b+1)+j-i]*d
  - 注：若矩阵下标均从1开始，则i和j减1，若压缩后的一维数组从1开始，则算出来的k再加1

串

⚠️主串长度为 n，子串长度为 m，则简单模式匹配的最坏时间复杂度为 O（nm）, KMP 算法时间复杂度为 O（n+m）
串既可以链式存储也可以顺序存储
串是字符的有限序列，空串是不包含任何字符组成的串，由空格组成的串是空格串
⭐ ⚠️串中字符均不相同，由n个字符组成的串，其含子串n(n+1)/2 +1
串的特殊性在于：数据元素是一个字符【这里数据元素是指串中每一个元素，其每个元素都是由字符组成】
Substring(s,i,k)---i是提取从第i个字符开始，长度为 k 的子串。
:warning:c 语言中“hello” 字符串的长度为：5，占用内存数为：6
- 字符串长度不包括结束符’\0’，但内存占用要包括。

⚠️ kmp算法

next数组：
- 下标前两位默认从-1，0开始，看重复字符串的数量（第n位看前n-1位）（重复是指：最前面n位和最后面n位【最后面元素必须到最右头，且方向始终是从左往右看】，e.g. aba重复数为1，abab重复数为2，ababa重复数为3，ababaa重复数为1），
nextval数组：
- 下标前两位默认从-1，0开始，从第三位开始看next数组的下标所对应原始元素，如果相同则将next数组对应的原始元素的nextval取过来，如果不相同，则取当前元素的next数组为该元素的nextval值。
注：如果题目中要从0开始，则所有数组+1

树与二叉树知识点

树/二叉树

先序森林等同于先序遍历二叉树，先序树等先序二叉树----先序都一样
后序森林等于中序二叉树，后序树等于中序二叉树，后序树等于中序森林（中序森林=中序二叉树）-----后序都转化为二叉树中序
⚠️树中结点数=度*度数+1
- 用于求叶子结点数量=度*度数+1-各度的结点数
二叉树总结点数目最少为（只有度为0和度为2情况，不含度为1的情况）：n0+n2=2n2+1，（n0=n2+1）【注：n2已经包含了根节点】
线索二叉链表树：有孩子结点为 1，线索（无子结点）为 0，缺左子树指向中序前一个，缺右子树指向中序后一个（缺左指前，缺右指后（左前右后））
⚠️ 高度为 h 的 m 叉树的至多有(m^h-1)/(m-1)个结点----->一般给出树的总结点数量用此公式求m叉树的高度
⚠️ n个结点的二叉树共有：(2n)!/n!(n+1)!个形态-----等于栈的卡特兰数（记哪个都行）
⭐ 树二叉树森林转化：
- 树转二叉树：1、将兄弟结点加线；2、给除左结点外的结点去线；3、由兄弟转化的结点都是该结点的右子结点
- 二叉树转树：1、将所有结点其的右孩子连线；2、去除所有兄弟间的连线；3、层次调整；（从上至下，依次加线，依次去线）
- 森林转二叉树：1、将森林中的每棵树都转化成二叉树；2、将第二棵树的根节点作为第一棵树的右孩子，第三棵树作为第二棵树的右孩子，依次类推。
- 二叉树转森林：1、从上到下将所有右孩子去线；2、将分离的二叉树转化为树

满二叉树/完全二叉树

⭐高度为 h 的满二叉树，其结点总数为 2^h -1
- 满二叉树第i层，结点数目为 2^(h-1)
⭐ 完全二叉树深度： ┗log2n┛+1 或 ┏log2(n+1)┓
⚠️深度为k的完全二叉树，最少结点数：2^(k-1)，最多结点数：2^k -1------最多结点数即对应满二叉树
- 设高为h的二又树只有度为0和2的结点，则此类二又树的结点至少为：2h-1，最多结点为满二叉树对应的结点数目
完全二叉树边号为 i 的结点的双亲结点为：i/2（向下取整）
- 若编号为 i 的结点有左孩子，则左孩子结点为 2i，若编号为 i 的结点有右孩子，则右孩子结点的编号为 2i+1

⚠️一个深度为 k 的，具有最少结点数的完全二叉树按层次，用自然数依次对结点编号，则编号最小的叶子结点的序号为2^(k-2)+1

⭐ 编号最小的叶子结点不是第 k 层第一个结点，而是第 k 层第一个结点的父结点的右兄弟--------即k-1层第二个结点
- 计算方式：最小结点的完全二叉树，其k-1层是满二叉树，此时结点总数是2^(k-1)-1，第 k 层是第一个出现叶子节点的层。若要求最小编号的叶子结点，则为第k-1层的第二个结点（从左到右），即编号为2^(k-2)-1+2=2^(k-2)+1
⚠️n个结点的完全二叉树叶子结点数：
- 如果n是奇数，那么叶子节点的数量是：(n+1)/2。
- 如果n是偶数，那么叶子节点的数量是：n/2。
⚠️已知完全二叉树的第8层(根结点的层次为0)有240个结点，则整个完全二又树的叶子结点数是 248个
- 解析：正常满二叉树第八层为256个结点，题设为240个结点，说明没满，还缺256-240=16个结点，其对应的父节点数量为8个，同时也是叶子结点，则整个二叉树的叶子结点数量为240+8=248个结点

哈夫曼树

⭐ 哈夫曼树带权路径长度（wpl）为结点值乘以树的边数（即层数-1）
⭐ 哈夫曼树中叶子结点有 n 个，则哈夫曼总共有 2n-1 个结点即有2(2n-1)个总链域，若转为二叉链表存储时，有效链域为 2n-2 个（总结点数-1），空链域为 2n 个（总链域-有效链域）
- 二叉树有n个结点，则有效链域为n-1（总结点-1），空链域为2n-(n-1)=n+1
- 非常规计算题：
  - 计算等长编码位数，满足2^t>=n，t为等长编码位数，n为元素个数
    - 等长编码长度为频率和*等长编码位数
  - 非等长编码即为哈夫曼编码，变长编码平均长度为：∑编码出现频率*变长编码的位数
  - 计算哈夫曼的压缩率：用(等长编码的长度- 变长编码的平均长度)/ 等长编码的位数
⭐ ⭐ 判断是否是前缀编码：
- 在编码方案中，任何一个编码都不是其他任何编码的前缀，即一个编码不能以另一个编码作为开头或者完全一样。（例：110 和 1100，1100 包含了 110，即不是前缀比编码）

二叉排序树/平衡二叉树

⭐ 二叉排序树中序是递增的，且二叉排序树关键字比较次数：最好情况下是 O(log2n)，最坏情况下是 O(n)（最大值为n）
- 二叉排序树的三种情况
  - 若是删除叶子结点则直接进行删除
  - 若删除结点有右子树就用右子树的值来进行替换，左子树同理
  - 若删除结点有左右子树，则用其右边靠近该结点的第一个中序元素来进行替换。
⭐ 二叉排序树的ASL：
- 成功：每层结点数 * 所在该层的层数 / 结点个数
- 失败：每层补齐的个数 * 往上的结点数（不含自身）/总补齐的个数
⭐ 高度为n的平衡二叉树至少有f(n) = f(n-1) + f(n-2) +1,(n>👨 )，其中：f(1) = 1;f(2) = 2;f(3)=4;f(4)=7
⚠️ 平衡二叉树（高度差小于1的二叉排序树）的插入，若左右子树的高度大于1，则找其不平衡的最小子树的根节点相邻的三个结点，将其重新按照二叉排序树放入，在更新整个平衡二叉树
- ⭐若题目中出现根据字典顺序来比较大小，则是指根据ASCII码来比较，字母越靠后，ASCII 码值越大，大写字母<小写字母，若首字母ASCII一样，则比较第二位

⚠️ n阶B树（B+树）相关知识点

关键字数量：
- 每个节点最多含有 n−1个关键字。至少含有

\pmb{\text{每个节点至少含有：} \lceil \frac{n}{2} \rceil - 1 \text{ 个关键字，除非这个节点是根节点。---【向上取整】}}

子节点数量：
- 每个节点最多可以有 n 个子节点。

\pmb{\text{每个节点至少有：} \lceil \frac{n}{2} \rceil \text{ 个子节点，除非这个节点是根节点。---【向上取整】}}

子节点数量>关键字数量

B+树是B树的升级版本，核心就是使查询速度更快，主要用于数据库的索引，

e.g.MySQL数据库，B树、B+树的时间复杂度为O(log2n)

图

完全无向图共有 n(n-1)/2 条边，完全有向图有 n(n-1)条边。----这里n为顶点数量
- 若题目中给出为非连通无向图，则顶点数量由边数和上述公式得出后，需要额外+1
- :warning:e .g.：若G非连通无向图共有28条边，则该图至少与多少个顶点----------根据n(n+1)/2得出n为8，但为非连通则需额外+1，顶点数至少为9。
  - 也可根据非连通图最大边树(n-1)(n-2)/2 = 28得出n为9
⭐ 无向图 n 个顶点，要使得无向图为连通图，则至少为n-1条边，若是无向图为非连通图则最多可能有 (n-1)(n-2)/2边----------根据此公式知总边数可计算非连通图的顶点数
- ⚠️n个顶点的无向图,至少有条(n-1)(n-2)/2+1边才能确保该图是连通图-------------题目若带有确保二字则写此公式（非连通图最多边+1）。
- 若连通图包含 n 个顶点，则对应的生成树为 n-1 条边
  - 如果有一个有向图有N个顶点，如果是强连通图，那么至少需要n 条边（和顶点数量相等，形成回路），如果这个强连通图是一个环，那么它有 n 棵生成树。
无向图邻接表有 m 个边表结点（非零元素个数，为边数的二倍），则无向图边的数为 m/2-----------有向图：边等于边表结点数目
- 无向图邻接矩阵零元素个数为 n²-2e
- 有向图邻接矩阵元素个数为 n²-e
一个图的邻接矩阵表示法是唯一，邻接表不唯一
⚠️ 已知一个图采用邻接矩阵表示，计算第i个结点的入度的方法是：计算第i列的非零个数。
- ⚠️ 计算第i个结点的出度方法为：计算第i行的非零个数
- 总结：出度看行，入度看列
在图中所有顶点度数之和等于所有边数的 2 倍
- ⚠️ 无向图中顶点度的最大值为n-1，有向图顶点的度（入度+出度）的最大值为2*(n-1)
⚠️ 某图有n个顶点，e条边，采用邻接矩阵表示图，拓扑排序算法的时间复杂度为O(n^2)
- ⚠️某图有n个顶点，e条边，采用邻接表表示图，拓扑排序算法的时间复杂度为O(n+e)
- 其中：有向图进行广度优先遍历，其算法复杂度为O(n+e)；在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为O(n+e)。BFS和DFS的时间复杂度都是O(n+e)
连通分量个数：
- ⚠️能连接成一个环算做一个连通子图。连通分量为极大连通子图（最大的环数量），即最大的连通子图，若要在加入其他顶点会破坏连通性。
  - ⭐两个点连接或只有一个顶点也算一个连通子图
- 如果是强连通分量，则需确保任意两个顶点都是可以相互可达的，可算作一个强连通分量
⚠️深度优先遍历回朔的时候，在当前路径无法继续探索带其他结点时才能回朔

经典例题：

一个无向图中有40条边，度为5的顶点有6个，度为4的顶点有4个，其余顶点度均小于4，则该图最少的顶点数为____。
- ⭐ ⭐ 在图中所有顶点度数之等于所有边数的 2 倍，则总度数和为40*2=80，已知度数之和为6*5 + 4*4=46，剩余度数为80-46=34，为使得图中顶点最少则尽量使用度数为3的顶点，故┏34/3┓=12，综上，总顶点数为6+4+12=22

⚠️最短路径

Dijkstra 算法：

不能处理负权边
用Dijkstra求每一对不同顶点之间的最短路径的算法时间是0(m2) -------(图用邻接矩阵表示)

Floyd 算法：

可以处理负权边
不能处理负权回路或者说成不允许有包含带负权值的边组成的回路
迪杰斯特拉算法
- 除去出发的节点，还剩下几个节点就有几轮。
- 除第一轮外，每一轮只能从上一轮顶点集合选择顶点，第二轮最多选择两条路径，第三轮最多选择三条…
- 每一轮确定最短路径的行后，这一行就可以忽略
Floyd 算法
- 先把图转化成邻接矩阵
- ⚠️：依次从第一个对角元素画十字
  - 十字中如有无穷，则不改变该行和该列的值，其余值是基于十字线上行列加和，如果小于原有值则改变，否则不变，
  - 例如某行列值由第三行第一列和第一行第二列相加，则该值路径更新为3-1-2，中间数字为相同的行（列）

⭐关键路径

顶点代表事件，边代表活动

求顶点（事件）的最早发生时间和最迟发生时间-----------即求从起点到各顶点的路径长度
- 最早发生时间：取到达各顶点边的最大值-----------从前往后找取最大
- 最迟发生时间：尾结点的最迟发生时间等于其最早时间，其余结点用后一结点减去路径权值，如果有某一结点有多个出度则用其路径尾结点分别减去路径权值，并取最小值----------从后往前取最小
- ⚠️关键路径即为最早发生时间经过的路径，如果距离相同则都保留，关键路径不止一个
求活动的最早发生时间和最迟发生时间
- 最早发生时间：找边的头结点，取其该顶点的最早时间
- 最晚发生时间：找边的尾结点，取其该顶点的最晚时间，在减去该边的权值。
【AOE网快速寻找到关键路径，事件的最早最晚发生时间，活动的最早最晚开始时间】https😕 /www.bilibili.com/video/BV1L8411h7t7?vd_source=c8b64e308ba0a6999b868fdf4177d69f

查找

复盘总结

时间复杂度：

顺序查找：O(n)
折半查找：O(log₂n)-----最坏是O(n)
分块查找：O(log₂n+n)
散列查找： O(1)，平均查找长度与结点个数 n 无关
二叉排序树查找O(log₂n)

总结：散列查找与n无关，时间复杂度最大的是分块查找，其次是顺序查找，最小的是折半查找与二叉排序树查找

是否有序

顺序查找：适合无序查找
折半查找：需要有序
- 进行折半查找要求该表以顺序方式存储，且结点按关键字有序排列
分块查找：可以无序，适合结点动态变化情况
散列查找、二叉排序树查找：无序

平均查找长度

顺序查找ASL：(n+1)/2
折半查找ASL：一般用判定树来进行计算
- 平均查找长度近似为log₂(n+1)-1，若计算则用判定树来计算
- 成功：每层结点数 * 所在该层的层数 / 结点个数
- 失败：每层补齐的个数 * 往上的结点数（不含自身）/总补齐的个数
  - ⭐ ‘查找次数：为判定树高度=h = ┗ log₂n ┛ + 1或者 h = ┏ log₂(n+1) ┓-----完全二叉树的高度
⚠️ 若表长度为n，子表数量为k，n/k为子表长度，则分块查找ASL为：(k+n/k) / 2 +1----------数量+长度 /2 +1
- ⭐分块查找最理想的状态就是分成数量为根号n
二叉排序树查找ASL：同折半查找
散列查找ASL：用哈希函数计算

⚠️ 顺序查找和线性表区别

顺序查找第i个元素（查找成功）需要比较n-i+1次，查找失败比较次数为n+1次
线性表插入元素，平均移动：n/2次，需要移动：n-i+1次（同顺序查找查找成功比较次数一样）；
- 删除元素：平均移动：(n-1)/2次，需移动：n-i次
顺序查找是比较次数，线性表插入删除是移动次数

顺序查找

顺序查找适合于顺序表和链表，通常用于无序查找，从后往前开始

找第 i 个元素需要比较的次数：n-i+1，平均比较次数为：(n+1)/2
如果要找的不在表中则比较次数为（查找失败）：n+1
长度为 n 的顺序表，查找任一元素平均查找长度为(ASL)：(n+1)/2
- ⚠️长度为n的单链表平均比较次数也是(n+1)/2
时间复杂度：0(n)

优缺点：适用范围大，元素无次序，当 n 较大时效率较低

注意：

单链表和顺序表实现时间复杂度都为 O(n)，但
- 删除第一个元素时，单链表可直接删除不需要移动元素，而顺序表删完后需要移动元素，所需时间更多，故此情况下单链表时间快
- 若在最后一个元素插入一个新的元素，单链表需要遍历到最后一个元素才能进行插入，而顺序表仅需根据下标即可，不需要移动元素，即顺序表速度大于单链表速度
- 若交换两个元素，单链表均需要遍历到该元素位置才能完成交换，而顺序表无需遍历，仅根据下标即可完成（不需要移动，只有插入和删除才需要移动），故顺序表速度快
- 总结：
  - 删除首元素和在首元素之前插入，选链表
  - 在尾结点插入和删除或交换两个元素，选顺序表
  - ⭐总而言之，对于整体而言，链表适合插入和删除、顺序表适合查找

折半查找（二分查找） ┗ ┛ ┏ ┓

适用于有序查找，时间复杂度为 O（log₂n）

对 顺序表进行折半查找 时，该表必须以 顺序方式存储，且结点按关键字有序排序

【注：二分查找（折半查找）查找成功的平均查找长度，用判定树来进行计算，查找成功长度为（每层结点个数 * 树的层数）/结点个数】

⭐确定中间位置为mid = ┗ (low+high) / 2 ┛（向下取整）
若中间位置等于待查数字则查找成功，若中间位置值小于待查数字值，则 low = mid + 1 若中间位置值大于待查数字值，则 high = mid - 1

优缺点：比较次数少，查找速度相对快，查找前需要建立有序表，适用范围少，并不是一定比顺序查找速度快

折半查找的ASL

和二叉排序树的ASL一样

成功：每层结点数 * 所在该层的层数 / 结点个数
失败：每层补齐的个数 * 往上的结点数（不含自身）/总补齐的个数

折半查找判定树

折半查找判定树是一颗平衡二叉树，其核心思想同二叉排序树一致，（核心思想：中间大的放中间，最小的放左子树，最大的放右子树）

判定树的高度为：h = ┗ log₂n ┛ + 1或者 h = ┏ log₂(n+1) ┓，比较成功时，同关键字比较次数最多为 h，时间复杂度为 O（log₂n）

例，若有 1000 个元素，则采用折半查找则至多比较 ┏ log₂(1000+1) ┓ 次（即树的高度） 数

构建判定树快速法

根据元素数量，画出二叉树，每次先画右结点的右子树，再画左结点的右子树，当每行所有右子树都画完时，然后再先画右结点的左子树，再画其他左子树---------------（均是从右往左）
画完二叉树，确定根节点元素，然后按照序列的中序遍历进行填充，和根节点元素进行比对

补充：

查找元素需要与哪些元素进行比较时，可按照二叉排序树的插入进行比较，（从根节点开始，若大于根节点则从右子树开始比较，若小于根节点则从左子树开始比较，依次递归，直到查找完成）
其中 ASL 查找成功和失败按照二叉排序树的查找成功失败来进行计算

分块查找（索引查找）

分块查找又成索引顺序查找，是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合结点动态变化的情况

🌠 若表长度为 n，子表数量为k，且每个子表的长度相等为s=n/k，则进行成功查找的平均查找长度为：(k+n/k) / 2 +1
- (子表数量+子表长度) /2 +1

二叉排序树查找

n 个结点的二叉排序树，平均情况时间复杂度为 O（log₂n）, 最坏情况下为 O(n)
二叉排序树的进行中序遍历，得到的结点序列一定是个有序序列

散列查找

哈希函数构造方法：假定散列表长度为M，取一个不大于M但最接近或等于M的质数（只有1和它本身整除）P
平均查找长度与结点个数 n 无关

相关计算公式和注意事项：

装填因子=表中记录数/散列表长度，P为小于等于散列表长的最大质数（素数）
⚠️线性探测法处理冲突时，成功ASL是除以关键字长度，失败ASL是从当前位开始数到有空格【只关注前P位（哈希函数里的P）】，若本身就是空格则失败次数直接置为1 ，求和后除以散列表长

排序

⚠️注意点

快速排序中，第一趟排序完成后，分别比较第一趟选取的关键字前面序列和第一趟选取的关键字后面序列，无需对整个进行重新排序
直接插入排序第一趟：默认第一个元素为有序序列，然后依次插入，如果第二个元素比第一个元素小则交换位置。
简单选择排序：第一趟：从原有序列中选择最小的元素与第一个元素交换位置，其余元素不变
- 第二趟：是从第二位开始（第一位已经确定位置不动）找最小的元素与第二位交换位置，依次类推

复盘总结

选择什么排序

数据量大（n 较大）且需挑选前十个最大元素：----------堆排序
- ⚠️数据量大（n 较大）且需挑选前十个最大元素，且要求稳定：----------归并排序
数据量大（n 较大），关键字位数少且可分解-------------基数排序
数据量小（n 较小）-----------------------------------------------直接插入排序或简单选择排序。
⭐ 数据基本有序--------------------------------------------------------直接插入排序或冒泡排序
需要稳定性且时间复杂度为O(nlogn)------------------------归并排序
数据量大且时间复杂度要求为O(nlogn)---------------------快速排序、堆排序或归并排序------快速排序随机分布情况下平均时间复杂度最短，但不稳定；
数据量大且关键字随机，无需稳定性-------------------------快速排序

基数排序不是基于比较的排序算法

对于堆排序和快速排序，若原始序列接近有序，则选堆排序
- ⭐ 对于接近有序的序列：速度从快到慢排序：直接插入排序—>冒泡排序--->堆排序—>选择排序—>快速排序
- ⭐ 在堆排序中，关键字递减（降序）选择小根堆，递增（升序）选择大根堆。
  - ⚠️⚠️若是大根堆进行堆调整，每一次将栈顶元素与最后一层最右元素交换，同时将原来栈顶元素（最大的）放入序列，重新进行大根堆调整，将调整后的堆从上到下从左到右依次输出，依次类推。----序列是从右往左展示
    - ⚠️构建堆排序的初始序列，可先找第一个非叶结点┗ n/2 ┛-1，然后依次递减
不稳定排序：“快些选一堆好友来聊天”--------（快速希尔选择堆）
平均复杂时间复杂度快：”快些归队”-----（快速希尔归并堆）
⭐每趟至少确定一个元素位置：“快插选一堆帽子”------（快速插入选择堆冒泡）

与序列有无关

与初始序列无关
- 移动次数无关：“基数排”-----（基数排序）
- 比较次数无关：”选堆归折”------”折比”
- 时间复杂度无关：”选堆归基“-----（选择堆归并基数排序）--------堆屎
- 排序趟数无关：”选插归基“----（选择插入归并基数排序）-------“插排”
与初始序列有关
- ⭐ 冒泡和快速排序----易受初始序列影响

排序思想

⚠️ 快速排序：二分法思想，在待排数列基本有序的情况下不利于发挥其长处

归并排序：分治法

时间复杂度

堆排序：全部情况均为O(nlog2n)
归并排序：全部情况均为O(nlog2n)
快速排序：平均和最好都是O(nlog2n)，最坏是O(n^2)

这些排序是平均时间复杂度相对较小

希尔排序：平均为O(n^1.3)

简单选择排序：全部情况均为O(n^2)
冒泡和直接插入排序：最好情况为O(n)，平均和最坏是O(n^2)
⭐ 对于冒泡排序：在有序时性能极佳为O(n)，逆序时最坏为O(n^2)

⚠给定有n个元素的一维数组，建立一个有序的单链表的最低时间复杂度是：O(nlog2n)

方案：先将数组拍好序，最小的为（nlog2n）归并或者堆排序

建立链表，n个元素插入n次，时间复杂度为O(n),，则总的时间复杂度为二者相加取最大值即：O(nlog2n)

空间复杂度

O(1)------即需要一个辅助单元
- 堆排序、直接插入排序、冒泡排序、选择排序、希尔排序
⚠️O(log2n)
- 快速排序（最好）
O(n)
- 快速排序：（最坏）
- 归并排序---占用空间复杂度最多

堆排序（插入、冒泡、选择、希尔）< 快速排序 < 归并排序

比较次数

简单选择排序：比较次数固定始终为n(n-1)/2，交换次数固定为n-1次
m路归并排序：每选出一个元素需要比较m-1次
冒泡排序：最少的比较次数为n-1次----即在有序情况下，最坏的情况：n(n-1)/2
直接插入排序：最少的比较次数为n-1次----即在升序排列情况下，最坏的情况：n(n-1)/2-------即在降序排列情况

题目中问最少则计算为n-1，问最坏或者固定次数均为：n(n-1) /2

考研数据结构考点

专业课真题小题考点

基础考点

c 语言

运算符表达式

指针

线性表

⭐ 链表操作

栈和队列

循环队列

数组与广义表

数组存储公式

二维数组的存储m*n

三维数组存储

矩阵压缩

三角矩阵的压缩存储（三角矩阵是对称矩阵的一种）

对角矩阵的压缩存储

串

⚠️ kmp算法

树与二叉树知识点

树/二叉树

满二叉树/完全二叉树

哈夫曼树

二叉排序树/平衡二叉树

⚠️ n阶B树（B+树）相关知识点

图

经典例题：

⚠️最短路径

迪杰斯特拉算法

Floyd 算法

⭐关键路径

查找

复盘总结

时间复杂度：

是否有序

平均查找长度

⚠️ 顺序查找和线性表区别

顺序查找

折半查找 （二分查找） ┗ ┛ ┏ ┓

折半查找的ASL

折半查找判定树

构建判定树快速法

分块查找（索引查找）

二叉排序树查找

散列查找

排序

⚠️注意点

复盘总结

选择什么排序

与序列有无关

排序思想

时间复杂度

空间复杂度

比较次数

二维数组的存储`m*n`

折半查找（二分查找） ┗ ┛ ┏ ┓