首页  思维导图  详情



 



考研：数据结构

2026-10-21 19:45:09   0  举报





由于考的不是408是自命题，知识点和应用例题相差大，免费的用着玩吧。当初考研时自己做的，知识点太多所以用导图梳理，感兴趣的可以用着玩，自己重新设计补充删减。别看背景绿觉得丑，我纯纯是为了护眼，考研你懂的，数一英一费眼睛。觉得丑的可以自己改改，我就不改了。

数据结构

考研

知识点

考研计算机

模板推荐

作者其他创作

大纲/内容

基本概念

数据结构基本概念

数据结构定义（...学科、...集合）

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

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

数据项、数据元素、数据对象的定义

数据项是构成数据元素不可分割的最小单位

数据元素是数据的基本单位

数据对象是性质相同的数据元素的集合，是数据的一个子集

根据数据元素之间逻辑关系，有哪些基本结构？/逻辑结构

集合、线性结构、树形结构、图状或网状结构

若只问两种，则为线性结构和非线性结构

注意：数据的逻辑结构独立于计算机

存储结构/逻辑存储结构（四种）

顺序存储、链式存储、索引存储、散列存储（如果只问两个，就答前两个）

注意：问的是存储还是逻辑结构，一定要看清楚

抽象数据类型的定义及其三要素、三种类型

抽象数据类型ADT是指一个数学模型以及定义在该模型上的一组操作

三要素：数据对象，数据关系，基本操作

三种类型：原子类型、固定聚合类型、可变聚合类型

算法

定义

对特定问题求解步骤的一种描述，它是指令的有限序列

与程序的区别

程序是算法用某种程序设计语言的具体实现，可以不具备有限性，比如无限循环中执行的操作系统【程序=算法+数据结构】

五个特性

有穷性、确定性、可行性、输入（0个或多个）、输出（1个或多个）

有确可(有缺可行)

好的算法的四个特性

正确性、可读性、健壮性、效率高和低存储量

正可健效(朕可见笑)

（渐进）时间复杂度的计算方法

含递归的主定理公式

T(n) = aT(n/b) + f(n)，其中aT(n/b)相当于，为递归的复杂度

n为算法的问题规模，a为递归函数中的分叉数，b为问题规模n递减的倍数， ，求得x

f(n)为递归中包含的循环代码的时间复杂度

T(n) = 相加的两项中最大的时间复杂度，若复杂度相同，则T(n) = O(其时间复杂度乘以logn)

不含递归的计算方法

只需分开讨论每一层循环语句的执行次数，后相乘即可

时间复杂度的表示形式：比级别高

易错点：区分如循环条件为 i*2<n(logn) 和 i*i*i<n(n^(1/3))

补充概念：

时间复杂度是指最坏情况下，估计算法执行时间的一个上界

同一个算法，实现的语言级别越高，执行效率就越低

评价一个算法的优劣的两个主要指

时间复杂度和空间复杂度

线性表

线性表的性质

线性表中第 i 个元素的存储位置(第i个元素的起始位置)：                                                            （）

线性表相邻元素存在序偶关系（序偶：有顺序，从前到后的顺序也算）

基本代码：创建、插入*、删除*、合并等基本操作

顺序存储

特点

随机访问；用一组地址连续的存储单元存储，插入和删除效率较低

顺序表删除插入的元素移动

1、在长度为n的顺序表中插入一个结点，所需移动的平均次数为/平均移动____个元素

n/2

解释：除以(n+1),在开头插入移动n次，最后一个元素前插入移动0次，总共可插入位置为n+1个

2、删除一个结点时，所需移动结点的平均次数为

（n-1)/2   （由1、2可见顺序表插入和删除的时间复杂度均为O(n) ）【做题时看清楚是说顺序表还是链表，如果是链表则均为O(1)】

一定要记得除以n ：n(n-1+0)/2 × 1/n

3、在长度为n的顺序表中删除第i-1个元素或在第 i个元素之前插入一个元素，需向前或向后移动________个元素

（n-i+1）

改成删除第i个元素则是移动n-i个元素

注意：一定要看清楚是在之前还是之后插入或删除，随机应变

4、如果将3中的插入改为在i之后，则答案应为

移动n-(i+1)+1= n-i个元素

3、4自己假设一个数组进行模拟更靠谱，防止踩坑

关于插入或删除，注意它说的是位序 i（从1开始）还是数组下标（从0开始）

链式存储

用一组任意的存储单元存储

四种链表

单链表

插入和删除某个结点的小段代码（比较简单,略）

注意：单链表的长度不包括头结点

带头结点或不带头结点的判空和只有一个结点的条件

单链表中，头指针始终都有，只是带头结点的链表中头指针指向的第一个结点是头结点

链表是否为空：有头结点判断 L->next == NULL；否则判断 L==NULL 

【易错点】理解： L是头指针，指针的本身的值是一个地址， 那么L->next实际上是指位于这个地址的结点 里存储的下一个结点的地址； 那么没有头结点的指针，L作为头指针它的值应该为空，由此...

只有一个元素结点的条件： 有头结点则 L->next->next == NULL；否则 L->next == NULL

不用加L->next != NULL，目前判断都 已经访问了L->next，加了反而是多余

注意：条件统一用判定格式写，用“==”

双链表

两个指针：prior 和 next

插入和删除小段代码

在p所指结点之后插入结点*s

示例1：s->next=p->next；p->next = s；s->next->prior=s；s->prior=p           

示例2：s->next=p->next；s/p->next->prior=s；s->prior=p；p->next = s

删除结点*p的后继结点*q

（1）p->next = q->next；（2）p/q->next->prior = p；free(q)

（1)（2）步骤是可以交换的

循环链表

经常操作表头和表尾，可以使用只设尾指针的循环单链表；对于设有尾指针的循环单链表，删除最后一个元素的时间复杂度为O(n)

带头结点的循环单链表的判空条件

L->next == L

带头结点的循环双链表L中只有一个元素结点的条件

L->next->next == L && L->next != L(防止只有一个头结点) && L->prior->prior == L;

next和prior两个方向都要判定，确保条件严谨

注意：循环链表表尾指向的是头结点而不是第一个元素结点

带头结点的循环双链表L的判空条件

L->next == L && L->prior == L

头结点的前驱和后驱指针都指向自身

注意：一般都是用next和prior表示，要记得

静态链表

两种线性表的异同和优缺点

逻辑、存储上的位置

线性表上的元素逻辑上都相邻，但顺序存储的物理存储上也相邻，而链式存储物理上不一定相邻

存取方式上

顺序表既可以顺序存取也可以随机存取

链表只能顺序存取

查找、插入和删除操作上

按值查找时

顺序表有序可采用折半查找，时间复杂度为O

链表无论是否有序，都只能扫描全表，时间复杂度为O(n)

插入删除时

顺序表平均要移动半个表长的元素

链表只需要修改相关结点的指针

空间利用效率

链表的结点带有指针域，因此存储空间较顺序存储更大，且存储密度较小

空间分配

顺序存储在静态存储分配时空间不能扩充，否则会内存上溢出； 虽然可以动态存储分配使得空间能够扩充，但需要移动大量元素

链表的结点空间只在需要的时候申请分配，只要内存有空间就能分配，更灵活高效

栈、队列

基本概念

栈

概念：限定在表尾进行插入或删除操作的线性表，又称后进后出的线性表（LIFO）

栈顶（Top），栈底（Bottom），空栈不含任何元素

push( )入栈；pop( )出栈(删除栈顶元素)；top( )获取栈顶元素

共享栈

好处

节省存储空间，降低发生上溢的可能

链栈

概念

单链表实现，操作仅在表头进行。没有头结点时Lhead指向栈顶元素，有头结点时指向栈顶元素位置前一个元素

没有头结点时Lhead指向

栈顶元素

有头结点时Lhead指向

栈顶元素上一个元素

(反正就是永远指向第一个结点)

优点

多个栈共享存储空间，提高效率且不存在栈满上溢的情况

队列

概念：只允许在表的一端插入，表的另一端删除，是先进先出（FIFO）的线性表

队尾（rear) ; 队头（front）

EnQueue()入队；DeQueue()出队；GetHead()读取队头元素

链队列

队列的链式表示和实现，一般带有头结点，其中头指针指向头结点， 尾指针指向队尾元素，初始时，front = rear且都指向头结点

如果没有头结点，初始时，front和rear指向何处，其状态不好判断

循环队列

概念

循环队列是队列的顺序表示和实现（它没有头结点）

通过求模运算使得指针到达数组的尾部的下一位时，自动调整回0

初始时，front=rear=0；非空时，头指针指向队头元素，尾指针指向队尾元素的下一个位置

(都是元素先进或先出)入队时，先赋值再向后移动尾指针；出队时，先出元素再后移头指针， 由此也可得上面非空时指针的状态

注意：头、尾指针的移动方向都是从0->maxsize->0->maxsize...,因此除了在边界点，其余移动都会使rear和front的值增加

链队列和循环队列的使用选择

能确定队列的最大长度，则用循环队列，否则使用链队列

相同点

栈和队列都是操作受限的线性表，属于相同的逻辑结构：线性结构

都只允许在端点处插入和删除元素

栈的计算及小段代码

共享栈栈空栈满条件

关于栈初始时两个指针的状态到底是哪一种？

共享栈的概念

最初状态时，top1和 top2指针分别指向数组的两端，由于规定1、2栈的栈顶指针都是先加1或减1再赋值，因此若数组为[a...b]，则初始时 top1=a-1,top2=b+1，由此可知入栈后两个指针所指的位置都已被赋值

栈满

数组为[a...b]，则数组长度为L=b-a+1,则栈满时假设1栈为空，2栈栈满，则top1=a-1,top2=a,有top2-top1=1

可见栈满的条件与a、b的值无关，一般指针都相差1或-1

注意：(有更改)一般未说明左栈顶(top1)和右栈顶指针(top2)的具体位置，则默认初始时top1=0,top2=maxsize-1,因此是指向栈内元素的下一个位置，先入栈再后移，则栈满条件为top2+1=top1

栈空

栈空则top1和top2都位于初值，题目给了初值，则top2-top1=初值相减，若未给初值，则top2-top1=b+1-(a-1)=b-a+2

n个不同元素进栈，出栈元素不同排列的个数（卡特兰数）

也可能加其他的限制条件，要自己模拟计算种数

栈顶指针指向位置的两种定义方式及其对应的入栈出栈代码

栈为S.data[],入栈或出栈值为x,栈顶位置为top

入栈

top=0，指向栈顶元素的下一个位置，则先赋值后加1，有s.data[top++] = x；

top=-1，指向栈顶元素，则先加1后赋值，有s.data[++top] = x；

出栈

top=0，则先减1后出栈，有x=s.data[--top] ；

top=-1，则先出栈再减1，有x=s.data[top--]；

已知入栈情况，不可能得到的出栈序列为(常考）

依次根据选项中的出栈顺序在脑中进行入栈出栈的模拟，使其顺序相符合，进而找到不符合规则的出栈顺序

小技巧：假设出栈序列开头为元素b，则说明在题目所给的入栈序列中，b之前的所有元素均已入栈且还未出栈

栈的容量至少为

与前一个方法相似：由入栈和出栈序列模拟过程，并记录期间栈中存储的元素个数的最大值

链栈的进栈和出栈操作代码(理解就行)

头指针为Lhead

带头结点

p入栈

p->next=Lhead->next; Lhead->next=p;

Lhead指向头结点，在头结点和栈顶元素之间插入新结点

出栈,临时结点为p,取值x

p=Lhead->next; x=p->data; Lhead->next=p->next;  free(p)；

不带头结点

入栈

p->next=Lhead; Lhead = p；

Lhead直接指向栈顶元素，即它本身就是栈顶元素的位置

出栈

p=Lhead; x=p->data; Lhead=p->next;  free(p)；

队列的计算及小段代码

（常考）牺牲了一个单元用于区分队空队满的情况，因此题目给出队列的元素个数最多为n 时,有数组长度maxsize=n+1

注意

1、若题目给了队列名Q，则答案要写成Q .front , Q .rear形式

2、未告知front和rear所指位置时，默认front指向队列头元素，rear指向队列尾元素的下一个位置(直接用以下公式)      告知了所指位置且与默认不一样时，需自己用循环队列模拟，然后对公式进行调整

3、在顺时针方向上，rear永远等于front或在front后面

例如：若rear指向队尾元素位置，则循环队列元素个数为(rear-front+1+maxsize)%maxsize

循环队列长度/元素个数 (用front和rear表示)(常考、易忘)

(rear-front+maxsize)%maxsize

+maxsize是为了消掉负数； 解释：当rear比front小的时候，rear-front=-x, x则为空的位置个数，因此-x+maxsize就等于队列长度

循环队列判空判满条件(常考)

判空

front == rear

判满

(rear+1)%maxsize ==front

记得要加%maxsize

若为加标签的情况，则判空判满为

判空：front == rear && tag == 0

判满：front == rear && tag == 1

入队则令tag=1和出队则令tag=0，空队列最后一步一定是出队操作，满队列最后一步一定是入队操作

已知front、rear初始位置和相关操作，求最终的位置

删除a个元素

(front+a)%maxsize

添加b个元素

(rear+b)%maxsize

循环队列出队入队操作代码

出队：front = (front+1)%maxsize；入队：rear = (rear+1)%maxsize

链式存储的队列Q，插入删除时头尾指针的修改

插入p

Q.rear->next = p；Q.rear = p；

删除队首结点p

一般情况(不取值)

p = Q.front->next ; Q.front->next = p->next ; free(p);

头指针一直都指向头结点

删除元素为队列最后一个元素

则需要添加 if(Q.rear == p) Q.rear = Q.front ;

栈和队列的实际应用

栈的典型应用

递归、进制转换、迷宫求解、括号匹配、行编辑程序、表达式求解

队列的典型应用

打印数据缓冲区、FCFS(先来先服务，CPU处理请求）、广度优先搜索借助的辅助队列

n个圆盘的汉诺塔，总的移动次数为

次

串

相关概念

空串、空格串、子串、真子串

串：由零个或多个字符组成的序列

串可用链式或顺序存储

真子串：不包含自身

长度为n的字符串的真子串个数

解析：1个空串，减去1个自身，从a1,a2...an，对a1开头，有n种序列；a2开头，有n-1种序列...an开头，有1种序列，因此真子串个数 = (1+2+3...+n)+1-1 = n(n+1)/2

题目给出一个字符串，并给出一个子串，问子串在该串中的位置（默认在字符串中以1开始数，除非规定了从0开始）

求某个字符的所有子串

注意:空串以及本身也是子串

两个串相等的充分必要条件

长度相等，且各个对应位置的字符相同

常用基本操作（要记得名字和参数作用）

Concat(x,y)

连接x和y

Substring(s,i,k)

返回s从第i个位置开始的k个字符组成的子串(i是从1开始数)

Strlnsert(&S,i,T)

在S的第i个位置前插入T

StrDelete(&S,i,k)

删除S从i开始长度为k的子串

Strlength(s)

返回串的长度

StrCompare(x,y)

按照字典序比较x和y

例题1：s1 = "abcdcfg", s2 ="abcde”， Concat(Substring(s1,2,Strlength(s2)) , Substring(s1,Strlength(s2),2))

bcdcfcf

例题2：a1 = "dfafdsaf",a2 = "fdad"， StrInsert(a1,Strlengh(a2),Substring(a2,2,3))； StrDelete(a1,2,6); 问a1=?

ddsaf

存储结构（三种）

定长顺序存储

拼接过程中可能截断，因此并不能有效地实现串的合并操作

堆分配存储

动态分配空间

块链存储

用链表存储

待补充：三种存储的简要理解/定义

中缀转前或后缀

原理：栈在表达式中的应用，如：计算机通过后缀表达式计算表达式的值， 扫描后缀表达式，遇到操作数则将其压入栈中，遇到操作符则从栈中退出 两个操作数进行计算，再将计算结果压入栈中

括号法

从左到右给所有运算加上括号，再改变运算符的位置，最后把括号去掉【如2+3*4-5/2—>（(2+(3*4))-(5/2)】

中缀转前缀（波兰式）

从左到右提取运算符【如：-(+(2*(34))/(52) —>-+2*34/52】

+2-*34/52 好像也可以，不过还是按上面的来吧，即每一个括号都括入一个运算符

中缀转后缀（逆波兰）【常考】

从右到左提取运算符【如：((2(34)*)+(52)/- —>234*+52/-】

例题：a*b+(c-d/e)*f，求波兰式和逆波兰式

+*ab*-c/def

ab*cde/-f*+

注意： 1、如果左右有同优先级的符号，则遵循先左后右的原则; 2、每次算完数一下符号和字母的个数，看看有没有漏写；

对于比较简单的可以使用观察法：观察运算的优先级直接写出后缀表达式（建议还是用括号法检验一下）

理解简单模式匹配和KMP算法及其时间复杂度

主串长为m,子串长为n,模式匹配指子串在主串中的定位操作

简单模式匹配算法的最坏时间复杂度

O(mn)

KMP算法

利用的子串的结构信息，主串指针无需回溯， 只需将子串滑动合适的距离， 滑动的距离 = 已匹配的长度-对应的部分匹配值

时间复杂度

O(m+n)

求next、nextval数组

next数组

初始：前两个无脑写01，从第三个开始，【模式串即在匹配的子串】由于next[j]体现为模式串的第j个字符失配时，需要将模式串向后移动，尽量不从头开始，而是从next[j]位置继续匹配

步骤：在不匹配的位置前，划一条线，此时 j 指针指向与分界线临近的右元素，将模式串往后退，直至分界线之前的元素能全部对上或完全跨过分界线，此时的 j 指向模式串的第几个位置，next[j]就等于几。

例题：ababaaababaa

011234223456

nextval数组

步骤：第一个无脑写0 , 不好描述，看示例

例题：ababaaababaa

010104210104

数组和广义表

特殊矩阵

三种压缩矩阵

压缩矩阵存储的定义

对于三种特殊的矩阵，由于矩阵中含有大量相同元素或0元素，且矩阵排列有一定规律(矩阵默认从开始)，因此考虑用一维数组[0,...]按行或按列存储该矩阵，从而节约存储空间

（题目未说明矩阵和数组从几开始，则默认为以上定义中的形式，注意通过矩阵计算位置后要减1）

压缩存储时下标 k 的计算

【以下对称矩阵和三角矩阵均为下三角+数组从0开始的公式，若计算上三角，只需将公式中的 i 与 j 交换； 若从1开始，只需将k+1】

对称矩阵（只存储上或下三角加上对角线的元素）

推理过程：

按行存储

按列存储

补充：对称矩阵从0开始按行存储下三角，数组为[0...n(n+1)/2],则元素存储位置前面的元素总数为

三角矩阵（上下三角中某三角全为相同元素，只需先存储另一三角，再用数组最后一个位置存储该三角）

非相同元素构成的上下三角公式与对称矩阵相同， 相同元素构成的元素位置=数组最后一个位置，如下：

【三对角矩阵没有上下三角之分，其按行存储和按列存储的排列关于i=j对称， 因此若按列存储，只需将以下表达式的i与j替换】

三对角矩阵（非零元素集中在以对角线为中心的3条对角线上）

推理过程：

2i+j-3

多维数组

按行优先或列优先存储求元素下标

步骤：由给定的数组计算指定元素前的元素个数，指定元素地址=前面的元素个数×单个元素所占字节+起始地址

注意：例如计算从[0-20]的行数，应该为21；计算时不要算上指定元素位置

二维

注意：不要把行列搞混了，a...b是对应行的

例题：

2892；3012

一定要注意只有在计算列数或行数的时候要+1，即算上两点之间的满格

三维

猜测：按列存储和按宽存储的形式

例题：

4426

计算过程：

稀疏矩阵的定义及其转置（考得少）

定义

有大量0元素的矩阵，可以用三元表来存储（前两个存储元素所在行和列，后一个存储元素值）

转置方法（第二个不是太懂）

遍历每一列，去三元组里找到该 列的元素进行转换，复杂度是O(列数*三元表长度)

利用辅助数组。 num[c]表示第c列中非零元素的个数 cpot[c]表示第c列的第一个元素在新三元表的位置 则cpot[1] = 1，cpot[c] = cpot[c-1]+num[c-1]

写出矩阵的三元组

广义表

定义、结构

线性表的推广，其元素可以是单个元素，也可以是广义表，分别称为原子和子表。 LS=(a1,a2,…an)，也可以用树形结构表示

head()、tail()

head()表示取头元素，tail()表示取表尾（实际就是删除表头元素，只有一个照样要删）

注意：1、head()一般要去掉最外层括号(取元素)，而用tail()时外层括号要保留(删元素)；要看清楚括号是哪一层的

2、L在最里面，函数从内往外执行计算

3、tail((a)) = ()【tail取出来一定是个列表，但head取出来可能是元素】

广义表的长度和深度

长度：去掉外括号后的元素个数

宽度：括号的层数(包括外括号)

例题：（0,(a,b),(e),((c,d),f )）

长度为4，深度为3

例题

( )【空列表】

树和二叉树

定义、性质

【常考性质较多，建议多用真题和王道练习】

基本术语

树的结点、结点的度、叶子结点或终端结点、分支结点或非终端结点、 树的度、孩子结点、双亲结点或父结点、兄弟结点、祖先结点、子孙结点、 结点的层次、堂兄弟、树的深度或高度、有序树、无序树、森林

注意

结点的度、树的度

前者表示结点拥有的子树数量

后者表示树内各结点的度的最大值

树的深度或高度为

树最大层次

树的层次从根到分支递增

将树中结点的各子树从左至右有次序，则为有序树，否则为无序树

孩子结点：与当前结点直接连接的子结点；而某结点的子孙结点是以该结点为根的子树中的任意一个结点

兄弟结点有相同双亲；而堂兄弟的双亲在同一层

树的常考性质

结点数与边、度的关系

设度为 i 的结点数为 ，总度数/总边数

总结点数

常用于求总结点数或叶子结点数

补充：

题目只给出未给出结点数， s1,s2可求得，则由，(1)(2)联立消去n1，也能得到n0的值

m叉树和度为m的树的区别

m叉树：每个结点最多只能有m个孩子的树，允许所有结点 的度都小于m，且可以是空树

比如二叉树

度为m:至少有一个结点的度为m,一定是非空树，至少有m+1个结点

至多/至少结点数

（1）度为m的树第i层至多有___个结点          m叉树第i层至多有___个结点

都会是满m叉树

（2）高度为h的m叉树最多有___个结点

推导：

注意：

（3）具有n个结点的m叉树的最小高度为

由(2)推导而来：高h最多有n个结点，n个结点高最少为h

注意是向上取整

（4）高度为h的m叉树至少有 ___个结点

结点一条排下去，注意：这里要区分m叉树和度为m的树， m叉树可以没有度为m的结点

（5）高度为h、度为m的树至少有 ___ 个结点

h+m-1

结点一条排下去形成高h，任意一个结点再加m-1个孩子结点

二叉树

定义

二叉树是有序树

四种特殊的二叉树

满二叉树

深度为k且有个结点的二叉树， 除叶子结点外的每个结点度数都为2

完全二叉树

深度为k的，有n个结点的二叉树为完全二叉树，当且仅当其每一个结点都与 深度为k的满二叉树中编号从1至n的结点一一对应

二叉排序树

可以是空树或者左子树关键字<根节点关键字<右子树关键字

平衡二叉树(AVL树)

可以是空树或者左子树和右子树的深度之差的绝对值不超过1

平衡因子BF：该结点的左子树的深度减去它的右子树深度

概念补充

只有一个结点的二叉树度为0（度对应的是子树数目，而一个结点则只有根结点，无子树）

二叉树的左右子树顺序是确定的，不能任意交换(而度为2的有序树如果只有一个孩子，则无左右次序之分，否则有)

二叉树可以为空，因此度不一定为2，但一定小于等于2

任何一个二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序不发生改变 （因为其中的先、中、后只指父结点的次序变化）

常考性质

（1）在二叉树的第i层上至多有___个结点(i≥1)

（2）深度为k的二叉树至多有___个结点(k≥1)

（3）具有n个结点的完全二叉树的深度为

【注意：满二叉树求深度/高度不需要取整】(或)

由(2)推导得，不确定向上取整还是向下时可以随便代入一个简单的二叉树

（4）叶子结点数与度为2的结点数的关系

可见n0+n2必为奇数

（5）对一棵有n个结点的完全二叉树的结点按层序         编号1~n，设当前结点编号为i

左孩子序号为偶，右孩子序号为奇数

i>1，则双亲Parent(i)为

2in，则Lchild(i)为

否则无左孩子

2i+1n，则Rchild(i)为

2i+1

否则无右孩子

完全二叉树最多只有一个度为1的结点 (这不是假设，是完全二叉树本身的性质)

由(4)推导得

(不要口算)有2k个（偶数）个结点，0、1、2度的结点数各为

有2k-1个（奇数）个结点，0、1、2度的结点数各为

完全二叉树的结点个数为n，则编号最大的分支结点编号为

就是最后一个结点n的父结点，即

第i层有n个叶子结点的完全二叉树不可能有____个结点

分三种情况：（已知高度为i的满二叉树结点数为,第i层的结点数为）

（1）二叉树的高度为i，第i层有n个叶子结点，总结点数等于前i-1层的结点数+ 第i层叶子结点数n：

（2）二叉树的高度为 i+1，第i层有n个结点无孩子，且无度为1的结点：

（3）二叉树的高度为 i+1，第i层有n个结点无孩子，且有度为1的结点：

补：编号为i和j的结点处于不同层的条件

以上并不代表层数，仅用于判定是否处于不同层，比如第一层第一个 结点为1，第二为2，第三为4，每层的首个结点序号以(n=0,1,...)形 式递增，所以上式用于判定

二叉树的遍历

先序(NLR)、中序(LNR)、后序(LRN)及其递归、非递归代码实现

唯一确定一颗二叉树

先序+中序、后序+中序、层序+中序、先序+后序+不存在度为1的结点(没见过)

方法

有中序序列，则先通过其他序列确定根节点，再通过中序序列逐层划分左右子树

中序+先序较简单

中序+后序的方法

例题：画出相应二叉树， 中序：CBDEAGIHJF 后序：CEDBIJHGFA

与先序相反，后序是从后往前确定根结点

先序序列为{a,b,c,d}的不同二叉树个数为_____/4个结点的二叉树个数为___

先序序列和中序序列的关系相当于以先序序列为入栈次序， 中序序列为出栈次序，因为先序和中序可以唯一确定一棵 二叉树

因此这里相当于求{a,b,c,d}的出栈序列个数，则为

两个序列相同或相反对应的二叉树特点

先序与中序相同

为空树或任一结点只有右子树

这个相当于缺左子树的单支树

先序与中序相反

二叉树是缺右子树的单支树

先序与后序相同

空树或只有根结点

先序和后序相反/层序相同

满足只有一个叶结点

每层只有一个结点、高度等于树中结点数

先序与层序相同：除以上情况，还有只有3个结点的满二叉树

中序和后序相同

为空树或只有一个根结点或二叉树是缺右子树的单支树

注意：中序是必先遍历左孩子，如果没有右孩子，就一直是左孩子—>根结点

层序遍历（借助队列）

先将根节点入队，后出队时访问子结点，若存在，则将左右子结点入队

线索二叉树

增加两个标志域

ltag、rtag

相关概念

线索

线索链表中指向结点前驱和后继的指针

线索化

对二叉树以某种次序遍历使其变为线索二叉树的过程

按不同遍历方式建立线索，因此有三种线索二叉树：先序、中序、后序

作用

加快查找结点前驱和后继的速度

是一种存储/物理结构

线索二叉树的遍历以及前驱和后继结点的位置

查找先序前驱和后序后继必须知道该结点的双亲结点或者使用三叉链表，否则找不到

n个结点的二叉链表中有n+1个空指针

中序线索树中某结点(不为根)

有左孩子，则其前驱结点是它的

左子树的最右结点（不一定是叶结点）

有右孩子，则其后继结点是它的

右子树的最左结点(不一定是叶结点)

画出线索二叉树

一般结合唯一确定一颗二叉树，画出二叉树后写出相应的遍历序列， 然后画出指向前驱和后继的线索箭头，注意：画的时候看清楚，没有左/右孩子才画线索

注意：NULL指针在中序线索中前后画出两个，先序后序画出一个； 画完之后记得检查是否有n+1条线索，以免漏写

例图：(中序线索二叉树)

森林、树和二叉树的转换

树的存储结构(不常考)

双亲表示法（顺序表、伪指针）

容易求得双亲，不容易求得孩子

孩子表示法（单链表）

容易求得孩子，找双亲不方便

孩子兄弟表示法（二叉链表）

方便实现树转二叉树，容易找孩子，找双亲麻烦，若增设指针域指向双亲，找双亲也方便

树、森林的遍历(不常考)

树的遍历

先根遍历

若树非空，先访问根结点， 再依次对每棵子树进行先根后子树的遍历

注意：不是层序遍历哦~

后根遍历

若树非空，先依次对每棵子树进行先子树后根的遍历，最后再访问根结 点

森林的遍历

先序遍历

按树的先根遍历访问子树

中序遍历

按树的后根......

遍历序列与其对应二叉树遍历序列的关系

树转二叉树

步骤

兄弟结点之间连线，对每个结点只保留与第一个孩子的连线， 其他删除；以树根为轴心，顺时针旋转45度(树转二叉树，根结点只有左子树)

示例

森林转二叉树

步骤

先将每棵树转为二叉树，再按顺序将每棵树的根相连，后以第一棵树的根为轴心旋转45度

示例

二叉树转树或森林（唯一）

转换基本规则：左连为孩子，右连为兄弟

若一颗二叉树的根结点有右孩子，则转换为森林

步骤：

1、根结点为第一棵树的根，左子树遵循基本规则

2、右子树向右直接相连的n个结点为n棵树，拆分开；再通过基本规则进行整理

否则转换为树（直接使用基本规则）

注意：森林以及非二叉树的子结点不用按左右画

例题：

哈夫曼树的构造以及求带权路径长度

相关概念

结点的带权路径长度

从树的根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积之和

树的带权路径长度

树中所有叶子结点的带权路径长度之和，记作WPL

哈夫曼树或最优二叉树

带权路径长度WPL最小的二叉树

前缀编码

任一个字符的编码都不是另一个字符的编码的前缀

n个不同的关键字建成的哈夫曼树的结点数为

2n-1

n个带值结点，n-1个空白结点，建树时可推得

构造哈夫曼树

步骤

(1)构造一个新结点，从结点群中选取两个权值最小的结点作为左右结点， 并将新结点的权值置于左右结点权值之和

(2)删除结点群中已选出的两个结点，并将新结点加入结点群

(3)重复(1)(2)直到结点群只剩一个结点，该根结点展开即一棵哈夫曼树

规定：从右到左开始构造

示例

现有ABCDEF六个结点，分别带权6,7,1,5,2,8，构造哈夫曼树和哈夫曼编码，计算WPL

答案

注意：编码是左为0，右为1

补充：打草稿时中间的那些结点最好写成空的，不然wpl容易算错

平衡二叉树AVL的构造

概念

AVL

任意结点的左、右子树的高度的绝对值不超过1的二叉树

平衡因子

结点的左子树高度-右子树高度

平衡因子只能为-1,0,1,否则就要调整

插入

插入的调整对象都是最小不平衡子树，即以插入路径上离插入 结点最近的平衡因子绝对值大于1的结点作为根的子树

注意：一旦进行插入一个结点，就要考虑进行平衡调整；若是           初始状态为空时插入构造平衡二叉树，则需边插入边调整

四种调整规律

设平衡二叉树插入一个结点后导致不平衡，最低不平衡结点为A，以下是插入后的状态

A的左子结点平衡因子为1，右子结点平衡因子为0

此时S结点平衡因子为2，结点插入到左孩子的左子树尾部(LL是指结点插入位置)

进行LL平衡旋转（右边单旋转）(LL是指旋转左边的结点和调整左边的)

调整实例：

A的左子结点平衡因子为0，右子结点平衡因子为-1

此时S结点平衡因子为-2，结点插入到右孩子的右子树尾部

进行RR旋转（左单边旋转）

A的左子结点平衡因子为-1，右子结点平衡因子为0

此时S结点平衡因子为2，结点插入到左孩子的右子树尾部

进行LR旋转（先左后右双旋转）

（只是个示例，并不代表原本）

A的左子结点平衡因子为0，右子结点平衡因子为1

此时S结点平衡因子为-2，结点插入到右孩子的左子树尾部

进行RL旋转（先右后左双旋转）

补充：

(1)n个结点的平衡二叉树的最大深度/    高为h的平衡二叉树的最少结点数

递推公式： 1、要记的初值(表示高为h的平衡二叉树的最少结点数)： 2、递推出高为h的最少结点数： 3、若已知结点数为n，找到 h 令 ，则 h 为n个结点的最大深度

例题： 12个结点的平衡二叉树插入一个树上 不存在的新结点最多比较____几次？

5次

1、平衡二叉树一般又是排序树，最大比较次数即比较进行到树的最底部， 则需要考虑的是树的最大高度； 2、由递推公式可得，所以，因此， 则最多比较5次

(2)考试中平衡二叉树默认也是二叉排序树，左结点值>父节点>右结点 或者左结点值<父节点<右结点

答案为D，因为由中序序列为降序可知，该二叉树左结点>父结点>右结点， 所以如果已经是最大元素，则不可能还有左孩子。 关于C，由于平衡二叉树插入后会进行调整，因此不一定是叶子结点。例子？

构造平衡二叉排序树【p43】

二叉排序树BST(考法灵活)

性质

一般直接构造二叉排序树，按左子树结点值<根结点值<右子树结点值来构造， 中序遍历可得到递增的有序序列

插入

为空则直接插入；不为空，查找插入位置，若已存在关键字值相等的结点， 则插入失败，否则插入为查找失败所访问路径上的最后一个结点的左孩子或右孩子

向二叉排序树中插入一个结点，该结点必为叶子结点【这里是指插入成功了，因此没有歧义】

删除

叶结点直接删除；

只有一棵左子树或右子树，用子树根结点替换该结点的位置；

有左右两棵子树，用该结点右子树(因为右子树大于左子树)中的直接后驱替代该结点位置 (这里是指中序遍历序列中的后继)

查找效率以及构造

查找某一个值的比较次数为

经过的结点数，每到一个结点比较一次

查找整棵树的平均查找长度ASL=

所有结点的比较次数之和/结点数

注意：比较次数包括要查找的结点本身

二叉排序树的查找效率取决于树的高度。当构造二叉树的 输入序列有序时，会形成倾斜的单支树，设有n个结点，则 平均查找长度为

(n+1)/2

查找效率与单链表的顺序查找相同

例题：已知数据元素为(34，76，45，18，26，54，92，65)，按 照依次插入结点的方法生成一棵二叉排序树，并求查找成功和失败的ASL

答案

纠正，第二个查找失败的应该是除以9，结果为31/9

建议：先列好表格，然后按层次从上往下数每一层的比较次数，不容易统计错

补充概念

对于两棵具有相同关键字码而形状不同的二叉排序树，如果分别 对这两棵二叉排序树进行中序遍历，则得到的关键字顺序是一样的(可举例验证)

疑问：平衡二叉查找树是什么，它的平均查找长度？

图

相关概念

图

注意：只考简单图，不考虑重复边和顶点到自身的边

图

多对多的数据结构，由非空顶点集V和边集E构成，可以如下表示： G=(V,E)

如果边集E是无序偶集，那G就是无向图；如果边集E是有序偶集，那G就是有向图；

有序偶：有序对，有顺序(A—>B)的一对元素之间的关系

弧

<v,w>VR, v表示弧尾/初始点，w表示弧头/终端点（弧头就是带箭头的那一端）

完全图

边数达到最大即有条边的无向图

有向完全图

具有n(n-1)条弧的有向图

连通

连通：顶点到有路径(可以是间接路径）

连通图

图中任意两个结点都是连通的

n个顶点的连通图最少有_____条边

n-1

（可以2个顶点为例）

若n个顶点的连通图的|E|>n-1,则

一定有回路

（以3个顶点为例，构成三角形回路）

连通分量

无向图中的极大连通子图

连通图的生成树

包含图中全部顶点的一个极小连通子图

极大连通和极小连通的区别

极大即连通子图中包含其所有的能连通的最大边数

极小即连通子图边最少且保持图连通

注意：只写连通，没有加“强”的都是以无向图为前提

强连通图、强连通分量（仅限有向图）

非连通图最多有_____条边

补充

从u到v的最短路径若存在，则此路径的长度为从u到v的距离，若从u到v不存在路径，则记距离为

例题

具有11个结点的连通图，边最多有____条，最少有____条

55、10

至少要有____条边，才能确保具有7个顶点的无向图一定连通

有7个顶点的非连通子图最多15条边，因此加一条就能确保是连通图

结点的度或出入度

无向图全部顶点的度等于

边数的2倍

有向图全部顶点入度之和等于

出度之和边数

图的存储结构

邻接矩阵

定义

存储顶点之间邻接关系的二维数组

不带权图

有路径为1，无路径为0

带权图

有路径为对应权值，无路径为

无向图的邻接矩阵特点

无向图的邻接矩阵关于主对角线对称且唯一

求度的方法(常考)

无向图

第 i 行(或第 i 列)非零元素(或非 元素)的个数即为顶点 i 的度

如果只知顶点v,则前面还要加一句“在顶点向量中找到顶点v的下标i，”

有向图

出度

第 i 行非零元素(或非 元素)的个数即为顶点 i 的出度

入度

<div>第 i 列非零元素(或非 元素)的个数即为顶点 i 的入度</div>

注意：都是指非...元素的个数，而不是"权值的和"

优缺点以及适用图

优点：容易确定顶点之间是否有边

缺点：不容易确定图的边数，需按行、按列进行逐个检测

适用图：稠密图

补充

邻接表

定义

用顶点表顺序存储头指针和顶点，并对图G的每个顶点建立一个单链表， 第i个单链表的中的结点表示依附于顶点的边（对于有向图则是以顶点为尾的弧）

作图思路

表示法不唯一

适用图

稀疏图

优缺点

给定一顶点，容易找邻边，不容易确定两个顶点间是否存在边，不容易求有向图的出度和入度

具有e条边的无向图的邻接表中边结点个数为

画图(只归类，比较简单)

已知图的边，画邻接矩阵

已知图的边，画邻接表

已知邻接表（邻接矩阵），画邻接矩阵（邻接表）

技巧：总之先画出图

十字链表

邻接多重表

图的主要遍历方法

广度优先遍历(BFS)

思路

先访问起始顶点v，再访问与v邻接的所有顶点，后依次访问 相邻顶点的所有未被访问的邻接顶点，重复操作，直至所有顶点被访问完

特点

类似于树的层序遍历的推广，通常用队列实现

深度优先遍历(DFS)

思路

先访问起始顶点v，再访问与v邻接且未被访问的任一顶点，对该邻接点 重复此操作，不断向下直至不能继续访问，再依次退回到最近被访问的顶点， 若有邻接点未被访问，则从该点开始继续访问，直至所有顶点被访问完

特点

类似于树的先序遍历的推广，一般用递归函数实现

概念补充

1、广度遍历生成树描述了从起点到各顶点的最短路径

2、广度遍历和深度遍历无快慢之分

3、深度遍历不能寻找两点间最长路径

易考：不是BFS/DFS遍历序列的是

由以上两种遍历方法的思路可得对应图的遍历序列，遍历序列一般不唯一

由于优先生成树不唯一（尤其是深度），且容易画出，暂略，有问题再补充

例：(深度优先生成树)

两种最小生成树算法(带权无向连通图)

最小生成树的定义、性质

定义

一个连通图的所有生成树中边的权值之和最小的那棵树

性质

最小生成树不唯一，但当各边权值互不相等时，则唯一

最小生成树的边的权值之和总是唯一且最小

Prim(普里姆)算法

理解思路

初始T为空，先从图中任取一顶点加入树T，再选择与T中顶点集合(所有顶点)最近的顶点， 将该顶点和其边加入T，以此类推，直至图中所有顶点并入T (在不构成环的情况下)

算法复杂度

图的顶点数为|V|，则复杂度为，与图的边数无关

适用图

适用于求解边稠密图的最小生成树

Kruskal(克鲁斯卡尔)算法

定义及理解思路

定义：按照权值递增次序选择最合适的边来构造最小生成树的方法

理解思路：初始T有图中所有顶点但无边，按照权值从大到小的           顺序在图中选择边，若加入T后不构成回路，则将边加入T

算法复杂度

设图的边数共为|E|，采用堆存放边的集合，选择权值最小的边需要的时间

构造最小生成树的复杂度为

适用图

适用于边稀疏而顶点多的图

注意：边稀疏的图即稀疏图，就是存储该图的矩阵0元素会很多，对应于稀疏矩阵

补充： 题目没有告知边多还是结点多，问求最小生成树使用什么算法好时， 如果给了点就用prim,给了边就用Kruskal（?）

Prim、Kruskal构造最小生成树过程

示例：写出分别用Prim、Kruskal构造下图的最小生成树的过程，

答案

共同点：都基于贪心算法的策略

求最短路径的两个算法

Dijkstra(迪杰斯特拉)算法【常考】

定义

求解单源最短路径：即求图中某一顶点到其他各顶点的最短路径

基于贪心算法，每次在剩余未确定最短路径的点中寻找到该源点距离最短的点，每次选 择完后要更新各个点到源点的最短距离

示例1

求v0到各点的最短路径：

答案

示例2

答案

13v1v5v3改成14v1v5v3

集合s统一用Vi写吧

Flod(弗洛伊德)算法

含义

利用松弛操作，将距离矩阵迭代n次，其递推式如下： 矩阵含义为i到j的路径经过的中间点的序号不超过k的最短距离

例题

答案

拓扑排序

DAG图

一个有向图中不存在环，则称为有向无环图，即DAG图

AOV网

如果用点表示活动(因此是"V"，从而与后面的AOE网相区别)，有向边表示先后关系，那这个图 叫做AOV网

拓扑排序

算法求解步骤

1、选择一个没有前驱的顶点并输出。 2、从图中删除该顶点和所有以它为起点的有向边。 3、重复1和2，直到AOV网为空或当前网中不存在无前驱的结点，如果最后图不为空，就说明有环。

求拓扑排序序列(在较复杂的图中，序列往往不唯一)

示例：

答案：

时间复杂度

(题目说明了顶点和边则)使用邻接表进行拓扑排序

使用邻接矩阵进行拓扑排序

其他概念

拓扑排序可用于判定图中是否有环

有向无环图拓扑序列(唯一?)不能唯一确定该图

关键路径

AOE网

定义

以顶点表示事件，有向边(弧)表示活动(因此是E)，有向边的权值 表示完成该活动的开销，则称为AOE网

例图：

事件Vk的最早发生时间ve(k)

已知ve(1)=c，沿着箭头往后逐加，遇到多个箭头指向一个事件，取到达该事件的max，可得到所有事件的ve

(k为最后一个事件)事件Vk的最迟发生时间vl(k)

已知ve(k)=c，反沿着箭头往前，遇到多个箭尾为一个事件，取到达该事件的min，可得到所有事件的vl

上面的取max或min都是指加了或减了边的值后在所得事件发生时间中取最大最小

活动ai的最早开始时间e(i)

等于该弧起点的顶点的ve()

活动ai的最迟开始时间l(i)

该弧终点的顶点的vl该弧持续的时间

关键路径

定义

从开始到结束的最长路径决定了整个工程完成的时间，这条路径即关键路径

关键路径不唯一

如何缩短工期

提高所有关键路径上关键活动的速度

边结点个数，关节点

关节点

如果删除一个点以及与它相连的边后，该图产生了更多的连通分量，这个点就称为关节点 （也叫割点）(注意:点也删除了哦)

例题：找以下图中的关节点

关节点为1、2、5

找关节点p19

重连通图

没有关节点的图

查找与排序

查找

查找表

静态查找表

概念

只用于查找

包括

顺序查找表、折半查找表、索引顺序表

动态查找表

概念

除查找外，还用于插入和删除

包括

二叉排序树、平衡二叉树、哈希表

顺序查找

哨兵

比如要查找一个值为key的元素，则令n[0]=key即为哨兵，循环中从后往前找时只需判定 是否与key值相等，若一直查找失败，则遇到n[0]后会自动退出循环，而不用判定数组是否越界

n个元素组成的线性表，每个元素查找概率相等，

(n+1)/2  ; n+1；n

查找成功从1~n，查找失败则必须要查到尾部才能知道

有哨兵，n个元素不包括哨兵，总共从后到前比较n+1次

假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，此时顺序查找的平均 查找长度为_________（无哨兵）

即[n+(n+1)]/2

时间复杂度为

O(n)

优缺点

优点

算法简单且适用面广，对表的结构无任何要求，无论记录是否按关键字有序均可应用

缺点

平均查找长度较大，特别是当n很大时，查找效率较低

折半(二分)查找

概念及基本思想

又称二分查找，适用于有序的顺序表

基本思想

先将key与中间元素比较，若不相等，在以同样方式在前后半部分找

使用的二叉树

判定树

性质

唯一，为平衡二叉树，且只有最下面一层是不满的

可见判定树其实包含了所有的关键值

已知元素个数或表长为n，求高度/深度

和普通二叉树一样，因为都是最下面一层会不满

(可能不靠谱)等概率查找下的

当n>50,近似等于

给定有序序列(无序则先排成有序)，问折半查找的平均查找长度

例题：给11个数据元素有序表（2,3,10,15,20,25,28,29,30,35,40）采用折半查找。 则ASL成功和不成功分别是多少？

答案

先画出判定树：(按折半查找的顺序来构造)

求折半查找某一个元素的比较次数【注意】

low+high/2是向下取整

若题目所给顺序表非有序，则先整理为升序顺序表，再算比较次数

时间复杂度

特点

效率比顺序查找高，但只适用于有序的顺序表

以有序表表示静态查找表时，进行查找的方法除折半查找之外，还有_______

斐波那契查找、插值查找

分块查找

概念及基本思想

又称索引顺序查找

将查找表分为若干子块，块内无序而块间有序，第 i个块的最大关键字第 ( i+1)个块的最小关键字

再建一个索引表，每个元素为每个块最大关键字+块首元素地址

查找步骤(两步)

1、索引查找：确定待查记录所在块（顺序或折半查找）

2、块内查找：块内顺序查找

平均查找长度(等概率情况下)

长度为n的查找表均匀分为b块，每块长度为s【n=sb】

对于查找长度

若索引表、块内均使用顺序查找

设已知查找表长度n以及分块长度s

一般平均查找长度

要使平均查找长度最小

若索引改为折半查找，则平均查找长度为

到时候看看哪个更顺手

顺序表中折半查找某关键码，求比较次数（不用判定树也能做，较简单）

哈希表(散列表)

定义

根据哈希函数和处理冲突的方法，将一组关键字映射到一个优先连续的地址集上， 并以关键字在地址集中的“像”作为记录在表中的存储地址

简言之，可根据关键字直接访问，建立了关键字和存储地址间的一种直接映射关系

冲突

不同的关键字可能得到同一哈希地址，即

同义词

具有相同函数值的关键字

哈希表的构造

1、构造哈希函数H(key)(题目一般已知哈希函数)

常见为直接定址和除留余数结合的哈希函数，

i为递增序列，m为散列表表长

注意事项

1、函数的定义域必须包含全部需要存储的关键字，值域的范围依赖于哈希表的大小或地址范围

2、哈希函数计算出来的地址应该等概率、均匀地分布在整个地址空间中

3、哈希函数应尽可能简单，能够在较短的时间内计算出任一关键字对应的哈希地址

2、有冲突，则用一下方法处理冲突，直至不等于已有的函数值

处理冲突的方法

开放定址法

线形探测再散列

思想：冲突发生时，顺序表不断查看表中下一个单元，直至找出一个空闲单元

K个关键字互为同义词，用线性探测法把K个关键字存入散列表，至少需要探测_____次

(K+1)K/2

插入第一个探测一次，第二个第一次探测冲突，探测两次，第三个第一、二次都冲突，探测三次.......

注意是存入，就当散列表的初始化，而不是在原有的基础上探测

H(key)+1，H(key)+2......

二次探测再散列

H(key)+，H(key)，H(key)+，H(key)-......,H(key)【】

注意是先加后减

伪随机探测再散列

使用特定的方法生成的看起来尽可能的像一个真正随机数序列的序列

H(key)+f(1)，H(key)+f(2)......

再哈希法

链地址法

将产生冲突的同义词连成单链表，存在散列表的同一个单元内

建一个公共溢出区

补充：若问处理冲突的方法，只给两个空，就写上面加粗的

例题

解释：(比较过程)比如要找68，处理第一次为2，和位置2的key比较 发现不一致，然后处理第二次，为3，再比较还是不一样，最后处理一 次为4，比较后匹配，找到位置为4

写哈希表时一定要仔细，多检查，防止写错

补充易错例题：

初步计算：10  2  11  0  5  0  0  12

初步计算后H(key)，用H(key)+1、H(key)-1...调整后，再将(数字+13)/13才是调整后的数字，比如H(key)=0+1=1;0-1=-1,则(-1+13)/13=12

散列/哈希函数的性质

函数值应当以同等概率取其值域的每个值

装填因子

哈希表的查找长度与记录个数n不直接相关

查找过程中的平均查找长度（需和给定值进行比较的关键字的个数）取决于三个因素

处理冲突的方法

哈希函数

装填因子

理想情况下，对散列表进行查找的时间复杂度为

O(1)，与表中元素的个数无关

排序

如何判定排序是稳定的

当序列中存在两个或两个以上数据元素相等时，如果对序列排 序之后这些相等的数据元素的相对位置保持不变，我们称排序 方法是稳定的，否则称排序方法是不稳定的

内部排序(九大排序)

定义

指待排序记录存放在计算机随机存储器中进行的排序过程

插入排序

每次将一个待排序的记录按其关键字大小插入到前面已排 好序的子序列中

题目如果只写插入排序，一般就指直接插入排序

直接插入排序*

步骤

1、将与前面已排好序(最初只有一个)的 依次比较

2、边比较边将元素后移空出一个位置，找出插入位置k

3、将𝐿(𝑖)复制到𝐿(𝑘)

排序过程示例

监视哨的作用

暂存待插入元素和避免检查数组越界，提高效率

适用性

适用于顺序表或链表(可以从前往后排序)

折半插入排序

步骤

1、通过折半查找找出插入位置k(在有序序列中)

2、统一将插入位置后的元素𝐿[𝑘 … 𝑛]后移一个位置

3、将𝐿(𝑖)赋值到𝐿(𝑘)

与直接插入排序相比

减少了比较次数，但是移动次数不变

适用性

数据量不大的排序表

数据量不大，则比较次数就越少，越能体现优势

希尔排序

又称缩小增量排序

步骤

1、将整个待排记录序列分割成若干个子序列分别进行直接插入排序

2、待整个序列中的记录“基本有序”时，再对全体记录进行一次直 接插入排序

步骤有待具体化，看是否需要

过程示例

增量序列的取法

(最初用n/2)，也可以向上取整，每趟排序结束后计算一次d，若某趟排序结束后计算增量d=1， 则判定“基本有序”，下一趟排序即为最后一趟直接插入排序

注意：若增量为 i，相邻的同组元素中间相隔 i-1个元素

适用性

基本有序或数据量不大的排序表

交换排序

根据序列中两个元素关键字的比较结果来对换记录在序列 中的位置进行排序(都可以从小到大排或从大到小排)

冒泡排序

基本思想

从最后一个元素开始往前两两比较相邻元素的值，若为逆序(A[i-1]>a[i])，则交换它们，从而每一趟 都会将待比较序列中最小的元素放到上面的位置，即最终位置，到达最终位置的元素不参与下一轮比较

注意：是两两比较相邻的值，较小的会往上冒，而不是每次拿最后一个元素和前面的元素比较

如何结束：如果一轮下来没有任何元素产生交换，则判定有序，排序停止；因此有序序列一轮就会结束

n个记录的冒泡排序中，关键字最大的比较次数为____

n(n-1)/2

(n-1)(1+n-1)/2

考虑逆序的情况

快速排序*

基本思想

采用分治法，任取一个元素作枢纽(一般是首元素)，通过一趟排序将待排记录分割成独立的两部分，其中一部分记 录的关键字均比另一部分的关键字小，分别对这两部分记录继续进行排序，直到待排序序列只有一个元素，则达到整个序列有序

注意：快速排序的一趟排序是指对整个序列进行一趟排序的过程，且每一趟排序都会将枢纽(基准)元素放到最终位置上

快速排序过程示例

这里主要显示了第一趟排序，枢纽元素为49，指向枢纽元素的指针不移动，将另一个指针下的元素与49比较，如果比它大的在前面就交换，比它小的在后面就交换，一趟排序后枢纽元素前面的元素都比它小，后面的都比它大

使用快速排序移动次数最多的序列

左右越不对称，移动次数越多

注意：还是要模拟一下排序过程，数一下，可以从最不对称的选项开始

快速排序最坏情况下比较次数为

n(n-1)/2

序列为顺序或逆序时，每个枢纽元素都和其他 剩余的数做过比较，总比较次数为n-1+n-2+...+1

特点

所有内部排序算法中平均性能最优的算法

若初始记录序列按关键字有序或基本有序时，快速排序将退化为 冒泡排序，我们可以通过比较最左边、最右边和中间关键字的大 小来选取中间大小作为枢轴来改进该算法

选择排序

每一趟(如第i躺)在后面n-i+1个待排序元素中选取关键字 最小的元素，作为有序序列的第i个元素，直到第n-1躺做完

简单选择排序

无论什么是什么序列，都要排序n-1趟

堆排序*

堆的概念

大根堆：爸爸比儿子都大；小根堆：爸爸伏低做小

基本思想

首先将存放在L[1...n]中的n个元素建成初始堆，由于堆本身的特点(以 大根堆为例)，堆顶元素就是最大值。输出堆顶元素后，通常将堆底元 素送入堆顶，此时根结点已不满足大根堆的性质，堆被破坏，将堆顶元 素向下调整使其继续保持大根堆的性质，再输出堆顶元素。如此重复， 直到堆中仅剩一个元素为止。

建立初始堆

从序列末尾向前遍历，边遍历边调整，相当于从大根堆最下层从右到左层层向上调整(期间有必要时也要向下调整)

插入：先将新元素插入到数组尾部，与父节点对比，一路上升，直到无法继续上升为止

删除：用最后一个元素替换待删除元素，然后令该元素下坠

堆排序过程示例

判断是堆的序列

按照序列画出对应的二叉树，如果满足大根堆或小根堆的要求，就是堆

给定一组序列，建成大顶堆， 并给出输出堆顶元素调整后的新堆

易错点： （1）每次输出堆顶元素都是用最后一个元素代替堆顶元素，然后再向下调整，一定不要忘记！ （2）前往不要抄错结点，比如把87抄成了8 87，一旦抄错，全部白写！

注意：作为元素向下调整时如果两个孩子元素都比该元素大，则选择最大的孩子元素互换位置

错误示例：

纠正：(用6替换，而不是直接调整)

注意

1、每次下坠有几个孩子就要比较几次，不要把比较和交换混淆；而每次上升只比较一次

2、越是靠近堆顶的元素，向下比较的次数越多，比较要进行到底(即使没有交换)

3、初始堆为空，将n个元素依次插入堆，是边建堆边调整，插入一个调整一次

注意：一般将简单选择排序直接称为选择排序

二路归并排序*

基本思路及过程示例

注意

归并的比较次数与序列的初始状态无关，即使一开始就有序，仍要比较相应多次

基数排序

特点

不基于比较和移动进行排序，而是对关键字各个位数的进行排序

方法

最高位优先法（MSD）

按关键字权重递减逐层划分

最低位优先法（LSD）

按关键字权重递增逐层划分

适用性

1、数据元素的关键字可拆分为d组，且d较小(横向)反例：给身份证排序，d过大，不适合

2、关键字的范围不大(纵向)，反例：给中文人名排序

3、数据元素的个数n大

示例

外部排序

指待排序记录的数量很大，以致内存一次不能容纳全部记 录，在排序过程中尚需对外存进行访问的排序过程

九大排序对比

时间复杂度

插入排序

最好情况下

元素基本有序，每插入一个元素，只需比较一次，因此为

最坏情况下

元素逆序，为

平均情况下

平均下来，即为

折半插入排序

最好、最坏以及平均情况下均为

希尔排序

最好情况下

最坏情况下

平均情况下

冒泡排序

最好情况下

最坏情况下

平均情况下

快速排序

最好情况下

最坏情况下

平均情况下

简单选择排序

最好、最坏、平均情况下都为

堆排序

最好、最坏、平均情况下都为

二路归并排序

最好、最坏、平均情况下都为

基数排序

最好、最坏、平均情况下都为

共d趟分配和收集，一趟分配需O(n)，一趟收集需O(rd)

空间复杂度

快速排序

该排序是递归的，需要借助递归工作栈，因此为

二路归并排序

两个有序段合并前会先复制到辅助数组进行比较排序，恰需要n个单元，因此为

基数排序

d为趟数，r为使用的辅助空间，因此为

其余均为O(1)

稳定性

稳定

直接插入排序

从后向前先比较后移动，如果不大于，则不会交换相对位置

折半插入排序

冒泡排序

二路归并排序

基数排序

不稳定

希尔排序

由于会通过增量隔着几个元素进行分组，如果相同的关键字被 分到不同组，则相对次序可能会改变

快速排序

若右端区间有两个均小于基准元素值的关键字，则从右到左被交换到左区间时，相对位置会发生变化

简单选择排序

由于是选择最小的关键字与L[i]交换，如{2*,2,1}—>{1,2,2*},可能导致相对位置变化

堆排序

相同关键词如果分别位于左右子树上，调整时，可能把后面的调到前面

共同点：均可能会隔着顺序未知的元素组进行调换

【这个表要能默写下来】时间空间复杂度稳定性一览表

易错：希尔排序和二路归并排序的时间复杂度，堆排序的空间复杂度

特点

元素的移动次数与关键字的初始排列次序无关的排序

基数排序

元素的比较次数与初始序列无关的序列

折半插入排序

比较次数约为

选择排序

比较次数为n(n-1)/2次

二路归并排序

基数排序

算法的时间复杂度与初始序列无关的排序

选择排序、堆排序、归并排序、基数排序

着重记到：堆排序

排序趟数与序列原始状态无关的排序

插入排序(三个)、选择排序、基数排序、归并排序

每一趟都有元素放在最终位置的排序

冒泡排序(最小的元素冒到最上面)

快速排序(每一趟枢纽元素都会被排在最终位置)

简单选择排序(第 i 趟会选出待排序序列中的最小元素复制到L[i])

堆排序(每次都是从堆中移出最大或最小的元素)

如果序列已基本有序，效率较高的排序方法是

冒泡排序或直接插入排序

堆排序、快速排序、插入排序、冒泡排序中最坏 情况下，移动次数最少的是

堆排序

堆排序最坏为O(nlogn)，这里将时间复杂度的情况更换成移动次数，要稍加注意

用真题更改吧，网上查的不一样

给一组序列的变化过程，问使用的是什么排序【p30t4、p31t12】

注意：题目给的序列顺序是按趟数顺下去的，而不是根据第几次移动

第i趟排序能使前i+1个数有序，则可以判定为直接插入排序

前1-2趟排序可以看见元素调整的顺序很大，则很可能是快速排序(因为是前后调整)， 则可尝试用快速排序模拟，如果序列一致，则可确定

其他题型

将n个不同数据进行排序，至少比较____次，至多比较____次

n-1，n(n-1)/2

以冒泡为例，原序列为升序，只需两两之间比较一次

原序列为降序，从后到前的元素比较次数依次为n-1,n-2...1

由排序变化情况判定所用的排序方法

薄弱点

证明题

树

【p19 t4】n个结点的完全二叉树的深度为+1

【p23 t1】给定二叉树T，证明

【p40 t1】二叉树的结点度为0或2，二叉树的枝数为

【2016应用题T3】二叉树的第i层上最多有个结点(j>=1)

图

【真题】邻接矩阵A的m次方中位于i行j列的非零元素的含 义是图中从点i到点j长度为m的路径条数，为什么？

数学归纳法：  m=1时命题显然成立。 假设m=k时命题成立。 当m=k+1时， ，  中的元素  由于点i到点j长度为m=k+1的路径必定可以分解为 一条长度为 k的路径加上一条长度为1的路径，所 以枚举中间结点w，若w 到j存在路径，则i到j长度 为m的路径数就加上i到w长度为 k的路径数，而这正是等式(1)的含义。因此m=k+1时也成立。  综上所述，命题得证。

【p37 t6】设P是从s到t的一条最短路径，而w是路径中的任一 结点，证明s到w的子路径一定是最短的

假设s到w的子路径不是最短，则存在 一条更短的路径p。令q为P中w到t的 子路径，则p+q的路径长度小于P的 路径长度，这与P是最短路径矛盾。 因此命题得证。

证明普里姆算法得到的树T是最小生成树

假设图的最小生成树为T’且T不等于T’。  在T的构建过程中，第一次出现不同的边为e，e有一个顶点u属于  S，另一个顶点v不属于S。由于T’是生成树必定连通，因此在T’  中u到v存在路径，其中必定有一条边f一端属于V，另一端不属于  V。由Prim算法的构造方式可知：W(e)<=W(f)，若W(e)<W(f)，则  去掉f加入e得到的树权值会更小，矛盾。因此T的权值要等于T’  的权值，即得证。

证明克鲁斯卡尔算法得到的树T是最小生成树

归纳法证明：  n=1时显然成立。  假设n=k时命题成立。  n=k+1时，选出最短边e（最小生成树一定包含最短边，否  则可以加上它，然后删除环中其它的边），将其短接，得  到最小生成树T’。  假设原图的最小生成树为T*，且W(T*)<W(T)。  则W(T*-e)=W(T*)-W(e)<W(T)-W(e)=W(T’)，  这与T’是最小生成树矛盾，因此命题得证。

常用方法

归纳法（命题中有变量如结点数n等）

反证法

(主要还是递归,可以回头看看之前递归的应用算法，可能会考到)给定函数，写递归栈变化/分析函数作用

给定函数f(x), 输入某值后递归栈的变化过程p4 t5

答案

（1）1 2 1 3 1 2  1 （2）栈的变化过程：

画递归变化过程的技巧：(改一下，应该是类似于先序遍历)

(未)汉罗塔问题栈的变化过程 p14 t3

子主题

答案：(好像有错误)

p19：计算表达式时两个栈的变化过程