一、绪论

1.数据结构的术语

数据：所有能输入计算机并被计算机程序处理的符号的总称；数据元素：数据的基本单位；数据项：组成数据元素的、有独立含义的、不可分割的最小单位；数据对象：是性质相同的数据元素的集合，是数据的一个子集；

范围大小：数据>数据对象>数据元素>数据项

举例：数据为所有学生信息，数据对象为学生信息集合，数据元素为一个学生信息，数据项是学生信息的姓名、年龄、性别等。这里性质相同的数据元素集合可以是班干部学生、非班干部学生等。

2.数据结构

逻辑结构

集合结构（非线性结构）线性结构：线性表、栈和队列、字符串树结构（非线性结构）图结构（网状结构）（非线性结构）

存储结构

顺序存储结构（要用索引）链式存储结构（要用指针）

3.算法

特性

有穷性：不能死循环确定性可行性输入输出

评价算法优劣的基本标准

正确性；可读性；健壮性；高效性；

算法复杂度

（1）时间复杂度（重要）

分析方法：找出语句频度最大的语句（循环最深处），计算其因问题规模n而循环的次数f(n)，取其数量级用符号“O”表示。

常见的算法复杂度：O(1)、O(

)、O(n)、O(

)、O(

)。（按数量级排序）

这里需要注意的是递归函数，通常情况下递归函数会在数量级上加n，这是主要是看递归操作中调用递归函数时，输入的实参相对于传进来的实参看少了多少。

例题：

#include <stdio.h>

void recursion(int n) {

if (n <= 0) {

return;

}

for (int i = 0; i < n; i++) {

printf("%d\n", i);

}

recursion(n-1);

}

int main() {

int n = 5;

recursion(n);

return 0;

}

这里的算法时间复杂度为 O(

)，其中循环最深处的语句为

printf("%d\n", i);

它一共是循环了5+4+3+2+1=15，若传入数据为n，则一共循环n+(n-1)+(n-2)……3+2+1=n*(n+1)/2

则：取其数量级

，时间复杂度为 O(

)

（2）空间复杂度（不重要）

分析方法同上，只是f(n)计算的是因问题规模而需要的空间。

二、线性表

        线性表的逻辑结构特性是指数据元素之间存在这线性关系，n个数据特性相同的元素构成的有限序列，就是线性表。

        线性表有顺序表和单链表两种，这里主要讲解操作和如何做题，不进行代码展示。

1.顺序表

取指定位置的值

        用索引寻找顺序表第i+1的空间的值，时间复杂度为O(1)，这里注意题中索引从几开始，这里是索引为0开始。

查找元素位置

        寻找元素在顺序表中的位置，这里要用循环方法对顺序表的元素进行比较，元素相同时返回此时顺序表的长度，这里在题中总是喜欢索引从1开始，在0处不存元素，使用此方法时将查找元素存入0的位置，从顺序表最后一个元素开始遍历（即索引为length的位置），若顺序表中有该元素，返回其位置，若没有返回0，此方法的时间复杂度为O(n)。

给指定位置插入元素

       此方法的时间复杂度为O(n)。在顺序表中，如果要插入元素，则要将其指定位置后的元素都向后移动一个位置，将插入位置留下，若在尾部插入，则时间复杂度为O(1)。

删除指定位置元素

        此方法的时间复杂度为O(n)。在顺序表中，如果要删除元素，则要将其指定位置后的元素都向前移动一个位置，将删除位置填上，若在尾部删除，则时间复杂度为O(1)。

注意：这里还有许多方法，如删除指定元素，这里要先进行查找，在进行删除，这里元素若在尾部，时间复杂度也为O(n)，这里要具体情况具体分析。

2.单链表

        单链表的元素在实际排序中可以不是相接的，，而是用指针的方式链接的，在单链表中没有索引，注意链式存储所占空间分为两个部分，一部分是数据域存放数据，一部分是指针域存放指针。要想会做链表的相关题型，你需要知道三个东西，一个是现在是哪个结点，二是它的前驱是谁，三是它的后继是谁。

        概念补充与区分

首元结点：链表中存储第一个数据元素的结点头结点：在首元结点前的一个假设的结点，可以不存储任何信息，也可以存入一些附加信息（链表中可以没有头结点，它的存在就是为了方便链表的一些方法的实现）头指针：链表中第一个结点的指针，有头结点的情况头指针指向的是头结点，没有则指向的是首元结点

取指定位置的值

        该方法的时间复杂度为O(n)，这里要循环将指针移动到下一个结点，要查找第一个元素就要移动几次，核心代码为p = p->;next。

查找元素位置

        该方法的时间复杂度为O(n)，原理同上，但需要进行比较。

插入元素

        该方法的时间复杂度为O(n)，先循环找到要插入的位置，然后进行插入操作，若要插入元素结点为s，要插入位置元素结点为p，则核心代码为s->next = p->next;p->next = s。

删除元素

        该方法的时间复杂度为O(n)，先循环找到要删除的位置，然后进行删除操作，若要删除的前一个位置元素结点为p，则核心代码为p->next = p->next->next。

3.常见题型

（1）计算顺序表中的存储地址

例题：

公式：第i个元素的存储地址 = A + (i-1) * S（假设顺序表的起始地址为A，每个元素占据的存储空间为S）

顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是多少？

答案：108；

解析：100 + （5-1）* 2 = 108；

这里要注意的是二维数组的地址，若告诉你首地址元素地址，问你地址为多少的位置元素为什么，倒退公式，先求出i，然后一行一行的数就行。

（2）线性表操作问题

例题：

在含n个结点的顺序表中，算法的时间复杂度O(1)的操作是（）

A.访问第i个结点和求第i个结点的直接前驱；

B.在第i个结点后插入一个新结点；

C.删除第i个结点；

D.将n个结点从小到大排序

答案：A;

解析：上述操作中的知识点，其中D的时间复杂度会在后面相关章节进行讲解。

（3）存储密度问题

        存储密度是指数据元素本身所占的存储量和整个结点结构所占的存储量之比，顺序表的存储密度为1，单链表因为有指针域，则存储密度一定小于1

（4）选择线性表存储结构问题

公式：顺序表的存储效率低，查找效率高；单链表存储效率高，查找效率低

例题：

线性表L在什么情况下适用于使用链式结构实现？

A.需要经常修改L中的结点值；

B.需要不断对L进行删除；

C.L中含有大量的结点；

D.L中结点结构复杂；

答案：B；

解析：符合公式存储效率高。

（5）链表和特殊链表的插入删除

双向链表：多了一个指针prior指向前面的元素，一个结点可以向两边移动

循环链表：首位相连

例题一：

在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。

A.p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

答案:C;

解析：

q->prior=p;           //将结点x的前驱指针指向结点pq->next=p->next;           //结点x的后继指针指向结点bp->next->prior=q;          //结点b的前驱指针指向结点xp->next=q;           //结点a的后继指针指向结点x

例题二：

在双向链表存储结构中，删除p所指的结点时须修改指针（）

A.p->;prior->next=p->next; p->next->prior=p->prior;

B.p->next=p->next->next; p->next->prior=p;

C.p->prior->next=p; p->prior=p->prior->prior;

D.p->prior=p->next->next; p->next=p->prior->prior;

答案：A

解析：

p->prior->next=p->next;           //将结点a的后继指针指向结点cp->next->prior=p->prior;           //将结点c的前驱指针指向结点a注意：这里两个语句前后调换也是可以的

（6）头结点有无的问题

常见题型举例：

对于一个头指针为head的带头结点的单链表，判断该表为空表的条件是head->;next==NULL对于一个头指针为head的不带头结点的单链表，判断该表为空表的条件是head==NULL

三、栈和队列

1.栈和队列的概念和特点

栈：是限定仅在表尾进行插入或删除操作的线性表。表尾被称为栈顶，表头被称为栈底。栈的修改是按后进先出的原则进行的，类似于小时候的垒宝塔：

这里只有拿出最上面的，才能拿下面的。

队列：是只允许在表的一端进行插入，而在另一端删除元素的线性表。插入端叫队尾，删除端叫队头。 队列的修改是按先进先出的原则进行的，就像我们平常排队一样：

不允许插队！

        这里的算法和线性表一样，就是增加了一些限制。在使用中，栈我们通常使用的是顺序表，因为增加和减少都是在表尾（栈顶）操作，用索引时间复杂度为O(1)，而队列通常用链表，因为不知道到底有多少个元素排队，用链表可以避免假溢出的出现。

这里图示三中，就是“假溢出”现象，还有三个空间，但已经无法入队，这里如果是链表就不会出现这种情况，但如果非要用顺序表的话，可以改为循环的队列，即rear达到最大时，令其指向索引为0的地址。

注意：这里无论是队尾还是栈顶，其指向的都是最后一个元素的下一个地址，这样方便插入操作。

2.栈的常见题型

（1）出栈次序和入栈次序问题

例题一：

若让元素1、2、3、4、5依次进栈，则出栈次序不可能出现哪种情况？

A.5,4,3,2,1

B.2,1,5,4,3

C.4,3,1,2,5

D.2,3,5,4,1

答案：C

解析：A选项1、2、3、4、5依次进栈再出栈，则出栈顺序为5、4、3、2、1；B选项1、2进栈，2、1出栈，3、4、5再依次进栈再出栈，则出栈顺序为2、1、5、4、3；D选项1、2进栈，2出栈，3再进栈再出栈，4、5进栈再全部出栈，则出栈顺序为2、3、5、4、1。

方法：栈底元素总是最后一个出栈，看出栈顺序中栈底元素是否最后一个出栈，这里要注意的是进栈进去了几个元素，并且栈底元素是谁，建议画图。

例题二：

若已知一个栈的入栈序列是1，2，3……，n，其输出序列为

，

，

，……，

，若

=n，则

为（）

A.i          B.n-i          C.n-i+1          D.不确定

答案：C

解析：一个栈的入栈序列是1，2，3，……，n，而输出序列的第一个元素为n，说明1，2，3，……，n一次性全部进栈，再进行输出，所以

=n,

=n-1,……,

=n-i+1，因此答案选c。

（2）栈的应用场景：递归调用、函数调用、表达式求值、进栈转换、括号匹配等

例题：

设计一个判断表达式中左、右括号是否配对出现的算法，采用哪种数据结构最佳？

A.线性表的顺序存储结构          B.队列

C.线性表的链式存储结构          D.栈

答案：D

（3）栈的容量大小问题

例题：

设栈的初始状态为空，有元素1、2、3、4、5、6要按顺序入栈，它们的出栈顺序为2、4、3、6、5、1，则栈的容量至少为（）

A.2      B.3      C.4        D.6

答案：B

解析：首先1、2入栈，需要2个容量，2出栈，此时有一个元素，3、4依次入栈再出栈，此过程需要3个容量，5、6入栈，然后全部出栈，此过程需要3个容量，再这三个所需容量中选择最大的一个，则至少需要3个容量。

（4）栈的特殊情况操作

例题：

若一个栈以向量V[1…n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（）。

A.top++;V[top]=x;          B.V[top]=x;top++;

C.top--;V[top]=x;          D.V[top]=x;top--;

答案：C

解析：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，因为初始栈顶指针top设为n+1，所以元素x进栈时top指针先下移变为n（top--），之后将元素x存储在V[n]中。

（5）链栈的实际操作（本质上考的是链表知识）

例题：

链栈的结点表示为（data，next），top指向栈顶，则插入一个新结点（用指针x指向）的操作为

A.top->;next=x;          B.x->next=top;top=x;

C.x->next=top;top=top->next;          D.x->next=top->next;top->next=x

答案：B

解析：链栈在入栈时首先在栈顶插入一个结点（x->next=top;），然后将栈顶指针指向该结点（top=x;）。

3.队列常见题型

（1）判断队列中元素问题

例题一：

一个循环队列，f为当前队列头元素的前一位置，r为队尾元素位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为（）

A.r-f          B.(n+f-r)%n          C.n+r-f          D.(n+r-f)%n

答案：D

解析：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上n，然后于n求余，即(n+r-f)%n。

例题二：

循环队列存储在数组A[0…m]中，则入队时的操作为（）。

A.rear=rear+1          B.rear=(rear+1)%(m-1)

C.rear=(rear+1)%m          D.rear=(rear+1)%(m+1)

答案：D

解析：该队列为有m+1个元素的循环队列，为了防止越界，要在队尾位置加1时对其进行取模运算。

例题三：

最大容量为n的循环队列，尾指针为rear，头指针是front，则队空的条件是（）。

A.(rear+1)%n==front          B.rear==front

C.rear+1=front          D.(rear-1)%n=front

答案：B

解析：在这种标准的循环队列中有这样的规律

对空的条件：front==rear队满的条件：(rear+1)%n==front

（2）链队列的实际操作问题

例题：

链队中头指针为front，尾指针尾rear，则将新结点（用指针x指向）插入队列需要执行的操作是

A.front->next=x;front->next;x->next=NULL;

B.rear->next=x;rear=rear->next;

C.x->next=NULL;rear->next=x;rear=rear->next;

D.x->next=rear->next;rear=x;

答案：C

解析：x要进入队尾，则其指向只能是NULL，rear指向的是为加入前的队尾，rear->next=x是让现在队尾的指针指向x，将x加入队列，rear=rear->next;是改变rear的指向，使其再次指向当前队尾。

4.做题中的一些注意点

栈和队列的共同点是只允许在端点处插入和删除元素栈和队列具有相同的逻辑结构一个递归算法必须包括终止条件和递归部分递归和迭代可以相互转换，递归是通过函数的递归调用来解决问题，而迭代是通过循环结构来解决问题。前者可读性更好，后者效率更高。

四、串、数组和广义表

1.串、数组和广义表的相关概念

（1）串

串：由零个或多个字符组成的有限序列，即线性表但元素是char类型的。串中任意个连续的字符组成的子序列称为该串的子串，包含字串的串相应的称为主串。

子串的定位运算通常称为串的模式匹配或串匹配，最直观的是BF算法：

        BF算法的基本思想是，对于给定的问题，尝试所有可能的解决方案，并判断每个解决方案是否满足问题的要求。在实现上，可以使用嵌套的循环来遍历所有可能的解。对于每个解，进行问题的验证和判断，如果满足问题要求，则得到问题的解决方案，否则继续遍历下一个解。

#include <stdio.h>

#include <string.h>

int bfSearch(char* text, char* pattern) {

int n = strlen(text);

int m = strlen(pattern);

for (int i = 0; i <= n - m; i++) {

int j;

for (j = 0; j < m; j++) {

if (text[i + j] != pattern[j])

break;

}

if (j == m)

return i; // 子串在文本中的起始位置

}

return -1; // 子串不存在

}

int main() {

char text[] = "Hello, World!";

char pattern[] = "World";

int pos = bfSearch(text, pattern);

if (pos == -1) {

printf("Substring not found\n");

} else {

printf("Substring found at position %d\n", pos);

}

return 0;

}

kmp算法：KMP算法的时间复杂度为O(n + m)，其中n是文本字符串的长度，m是子串的长度。KMP算法通过利用已经匹配过的信息，避免了不必要的比较，从而提高了搜索效率。在大部分情况下，KMP算法的性能更好。这里不多进行讲解，考试中最多的是对其next数组的考察，如果想进行更深的理解，可以去看此链接文章。

（2）数组

        数组在c语言已经大量的使用了，这里就不对其进行讲解，需要注意的是，二维数组一般是先行后列，可以看成数据元素是线性表的线性表。

（3）广义表

        广义表是线性表的推广，也称为列表。简单来说，广义表更像是树一样的数据结构，因为广义表的元素也可以是广义表，这里用几个例子来对其定义进行说明：

A=（）——A是一个空表，其长度为0；B=（e）——B只有一个原子e，其长度为1。C=（a，（b，c，d））——C的长度为2，两个元素分别为原子a和子表（b，c，d）D=（A，B，C）——D的长度为3，3个元素都是广义表。显然，将子表的值代入后，则D=（（），（e），（a，（b，c，d）））。

对D进行图例展示：

其中圆圈为广义表，方框为原子。

广义表最重要的两个算法是取表头（GetHead(LS)）和取表尾（GetTail(LS)），其中取表头为非空广义表的第一个元素，它可以是一个但原子也可以是一个子表，取表尾是取出除去表头之外由其余元素构成的表，表尾必然是一个广义表。

这里用上述举例的广义表进行举例：

GetHead(B)=e,GetTail(B)=(),

GetHead(D)=A,GetTail(D)=(B,C),

观察可以得到规律，取表头方法不用加小括号，而取表尾必须加小括号。

这里需要注意一下一个特殊情况（（）），这种情况不是空表，其长度为1。

2.串的常见题型

（1）关于串的概念问题

例题一：

串是一种特殊的线性表，其特殊性体现在（）

答案：数据元素是一个字符。

易错点：数据元素可以是多个字符。

例题二：

下面关于串的叙述中，不正确的是（）

A.串是字符的有限序列

B.空串是由空格构成的串

C.匹配模式是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

答案：B

解析：由一个或多个空格组成的串叫做空格串

（2）kmp算法中next数组的计算

例题一：

串“ababaaababaa”的next数组为（）

答案：011234223456

解析：

方法一：

首先给字符串每个字符标号（从1开始），next的第一位和第二位一定是0和1，从第三个开始就要进行比较了，当你需要计算i个字符的next值时，需要看i-1位置上的next值，让i-1位置上的字符与其next位置上的字符比较，若相等，则i的next值为i-1位置上的next+1，若不相等，则看next位置上的next值，将next的字符与其next位置的值做比较，如果最终都没有得到相等的，则i位置上的next值为1.

用上题举例：

第三个位置上的字符next计算：3-1位置上为b，其next值为1，位置1的字符为a，a与b不相等，a的next为0，无法比较，则第三个位置上next值为1；

第四个位置上的字符next计算：4-1位置上为a，其next值为1，位置1的字符为a，a与a相等，则第四个位置上的next值为第三个位置的next值1+1=2；

第五个位置上的字符next计算：5-1位置上为b，其next值为2，位置为2的字符为b，b与b相等，则第五个位置上的next值为第四个位置的next值2+1=3；

第六个位置上的字符next计算：6-1位置上为a，其next值为3，位置为3的字符为a，a与a相等，则第六个位置上的next值为第五个位置的next值3+1=4；

第七个位置上的字符next计算：7-1位置上为a，其next值为4，位置为4的字符为b，a与b不相等，位置为4的b的next值为2，位置为2的字符为b，a与b不相等，位置为2的b的next值为1，a与a相等，则第七个位置上的next值为第二个位置的next值1+1=2；

第八个位置上的字符next计算：8-1位置上为a，其next值为2，位置为2的字符为b，a与b不相等，位置为2的b的next值为1，a与a相等，则第八个位置上的next值为第二个位置的next值1+1=2；

第九个位置上的字符next计算：9-1位置上为b，其next值为2，位置为2的字符为b，b与b相等，则第九个位置上的next值为第八个位置上的next值2+1=3；

第十个位置上的字符next计算：10-1位置上为a，其next值为3，位置为3的字符为a，a与a相等，则第十个位置上的next值为第九个位置上的next值3+1=4；

依次类推……

方法二：

看前缀和后缀子串有几个相同，则其next等于相同的字符数量+1

用上题举例：

第一个位置和第二个位置永远是0和1，从第三个位置开始计算，ab有o个前后缀相同，则next为0+1=1；

第四个位置：aba有一个前后缀相同（a），则next为1+1=2；

第五个位置：abab有两个前后缀相同（ab），则next为2+1=3；

第六个位置：ababa有三个前后缀相同（aba），则next为3+1=4；

第七个位置：ababaa有一个前后缀相同（a），则next为1+1=2；

第八个位置：ababaaa有一个前后缀相同（a），则next为1+1=2；

第九个位置：ababaaab有两个前后缀相同（ab），则next为2+1=3；

第十个位置：ababaaaba有三个前后缀相同（aba），则next为3+1=4；

第十一个位置：ababaaabab有四个前后缀相同（abab），则next为4+1=5；

第十二个位置：ababaaababa有五个前后缀相同（ababa），则next为5+1=6；

答案为：011234223456

（3）字串数量问题注意点

是否有重复的字符，如果有要根据具体情况删减重复字串数量空串也算字串，要在最后+1

3.数组的常见题型

（1）二维数组的地址计算

例题：

假设以行序为主序存储二维数组A=array[1…100，1…100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）

A.808        B.818        C.1010        D.1020

答案：B

解析：该二维数组以行为主序存储，索引从1开始，则1~5有四个行区间，一个行区间内是一个长度为100的一维数组，则LOC[5,1]=10+100*2*4=810，又因为1~5有四个列区间，一个区间是一个长度为2的数组元素，则则LOC[5,5]=LOC[5,1]+4*2=818，故选B。

（2）特殊矩阵的地址计算

例题：

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，

为第一元素，其存储地址为1，每个元素占一个地址空间，则

的地址为（）

A.13          B.32          C.33          D.40

答案：C

解析：对于对称矩阵，当以行序为主序存储其下三角中的元素时，

的地址为：1+2+3+4+5+6+7+5=33。这里是因为对称矩阵的性质，主对角线的数据元素相同，故只用计算下三角形的元素就行。

（3）二维数组转一维数组下标计算

例题：

二维数组A[1…m，1…n]（即m行n列）按行存储在数组B[1…m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（）

A.(i-1)*n+j          B.(i-1)*n+j-1           C.i*(j-1)         D.j*m+i-1

答案：A

解析：该二维数组以行序为主序，则A[i,j]有(i-1)行，一行有n个元素，而在第i行的第j列，故一共有(i-1)*n+j个元素。

4.广义表的常见题型

（1）判断广义表的长度和深度

例题一：

设广义表L=（a，b，L），其深度是（）

A.2          B.3          C.正无穷        D.都不对

答案：C

解析：该广义表的子表为其本身，形成一个递归的广义表，其深度为正无穷，故选C。

例题二：

设广义表L=((a,b,c))，则L的长度和深度分别为（）

A.1和1        B.1和3          C.1和2           D.2和3

答案：C

解析：广义表的长度是指广义表中所含元素的个数，深度是指广义表中括号的层数。故选C。

（2）广义表的取表头和取表尾算法问题

例题：

广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值为（）

A.(g)         B.(d)           C.c         D.d

答案：D

解析：由定义可知，按步骤进行分析

Tail(A)=(b,(c,d),(e,(f,g)))，令其为广义表BTail(B)=((c,d),(e,(f,g)))，令其为广义表CHead(C)=(c,d)，令其为广义表DTail(D)=(d)，令其为广义表EHead(E)=d，故选D

五、树和二叉树

1.树的基本术语

结点：树中的一个独立单元；结点的度：结点的子树的数量；树的度：树内各结点的最大值；叶子：度为0的结点称为叶子；非终端结点：度不为0的结点；双亲和孩子：结点的子树的根称为结点的孩子，相应的，该结点称为孩子的双亲；兄弟：同一个双亲的孩子之间互称兄弟；祖先：和族谱一样；子孙：同上；堂兄弟：同上；层次：根为第一层，根的孩子为第二层，依次类推；树的深度：树中的最大层次；森林：多颗互不相交的树的集合。

2.二叉树的概念和性质

       二叉树有且仅有一个称之为根的结点，除根结点以外的其余结点分为两个互不相交的子集

和

，分别称为T的左子树和右子树，且两个子树本身也是二叉树。二叉树与树的区别为：二叉树每个结点至多只有两颗子树，且二叉树的子树有左右之分，其次序不能任意颠倒。

性质

在二叉树的第i层上至多有

个结点；深度为k的二叉树至多有

个结点；对任何一棵二叉树T，如果其终端结点数为

，度为2的结点数为

，则

=

+1；具有n个结点的完全二叉树的深度为

;对于一棵有n个结点的完全二叉树的结点按层序编号，则对于任一结点i，有结论：

如果i>n，则其双亲是结点

；如果2i>n，则结点i无左孩子，否则其左孩子是结点2i；如果2i>n，则结点i无右孩子，否则其右孩子是结点2i+1；

这里用图示方便性质五的理解：

这里可以尝试用手挡住满二叉树，看看完全二叉树的情况。

3.完全二叉树和满二叉树

（1）完全二叉树

       深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。这样可以简单理解为最后一层可以有空位，但从左到右直到为空时中间不能有空的。

特点

叶子结点只可能在层次最大的两层出现；对任一结点，若其由分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1.

（2）满二叉树

        深度为k且含有

个结点的二叉树。简单点来说就是结点长满的树，如上述性质五的图示。

特点

        每一层上的结点数都是最大结点数，即每一层i的结点数都具有最大值

。

4.二叉树的遍历

（1）先序遍历：先根再左再右

（2）中序遍历：先左再根再右

（3）后序遍历：先左再右再根

5.树的常见题型

（1）二叉树的构建与树转换为二叉树问题

例题一：把一棵树转换为二叉树后，这棵二叉树的形态是______。

答案：唯一的（转换规则是唯一的，一般是孩子兄弟表示法）

这里是如何将一棵树转化为二叉树的具体方法链接

例题二：由3个结点可以构造出__种不同的二叉树

答案：5

这里需要注意的是，有左孩子和有右孩子是两种二叉树，还有要满足二叉树的定义，度不要超过2，还有就是这里如果是普通树，则只有2种，因为普通树不分左右孩子。

例题三：利用二叉链表（孩子兄弟表示法）存储树，则根结点的右指针是______

答案：空

此方法右指针指向的是自身的下一个兄弟结点，而树的根没有兄弟结点。

（2）树的计算问题

例题一：一棵完全二叉树上有1001个结点，其中叶子结点的个数是_______。

答案：501

公式：给结点数加1除2，向下取整不要小数部分，只要是完全二叉树都适用。

例题二：一个具有1025个节点的二叉树的高h为_______。

答案：11至1025之间

解析：

的值为1024，2的11次方的值为2048，有性质可知，该二叉树高为11时，最少有1024个结点，而二叉树高为12时，最少有2048个结点，11≤h，则证明该树的高度至少为11，当该树只有左孩子或右孩子时，高为1025。

（3）哈夫曼树的构建和最小权值的计算

哈夫曼树详解及其应用(哈夫曼编码）-CSDN博客

例题一：假设有一棵树的叶子节点的权分别为：5、9、12、13、16、45，使用哈夫曼算法构建哈夫曼树，并计算其带权最小路径。

方法总结：每次找俩个最小的相加，然后带上相加的再找两个最小的依次类推，计算带权最小路径时，只计算叶子节点的权，在第几层，则层数减1和权相乘，最后全部相加起来，这里如果遇见变式如三叉树的带权最小路径，仍然按此方法，找三个最小的相加，最后如果无法形成三叉树，可以增加一个权为0的叶子节点来构成三叉树。

（4）二叉树的遍历和线索二叉树

例题一：线索二叉树是一种______结构。

答案：物理

例题二：引入二叉线索树的目的是_______。

答案：加快查找结点的前驱或后继的速度

这里对线索二叉树进行基本的介绍：

线索二叉树是对普通二叉树的优化，在遍历时不需要使用递归的方式，而是通过线索查找。其数据类型在二叉树的基础上增加了两个标志区域LTag和RTag。其中LTag记录的是左结点的使用情况，当其为0时，lchild指示的是结点的左孩子，而为1时，lchild指示的是结点的前驱；RTag记录的是右结点的使用情况，当其为0时，rchild指示的是结点的右孩子，而为1时，rchlid指示的是结点的后继。这里注意，根据线索二叉树类型的不同，线索会不同，前驱后继要根据具体情况而定。

例题三：n个结点的线索二叉树上含有的线索数为________。

答案：n+1

解析：一共有2n个指针，n-1个支，则剩下的指针都作为线索出现，则答案为2n-n+1=n+1。

例题四：树的遍历方式，这里前序中序后序大家应该已经很熟悉了，这里有时候会考察特殊的遍历

给定一个如图所示的二叉树。设N代表二叉树的根，L代表根节点的左子树，R代表根结点的右子树。若遍历后结点的序列为3、1、7、5、6、2、4，则其遍历方式为（）

A.LRN         B.NRL           C.RLN          D.RNL

答案：D

解析：由图可知，该遍历方式先右再根再左

补充：对于这个图来说

前序遍历：1、2、4、5、6、7、3中序遍历：4、2、6、5、7、1、3后序遍历：4、6、7、5、2、3、1

例题五：若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为_______。

答案：X的左子树中的最右结点

解析：这里X的前驱是指中序遍历时，X前一个遍历的结点是谁，可以以例题四的图为例子，2的前驱是4，5的前驱是6，这里读者可以在6处增加一个右孩子8，对其进行验证，此时中序遍历为：4、2、6、8、5、7、1、3，可以看出，此时5的前驱为8，符号题意。

六、图

1.图的定义和基本术语

无向图：边没有方向的图有向图：边有方向的图子图：和子树和子表概念相同无向完全图和有向完全图：具有n(n-1)/2条边的无向图叫做完全无向图，具有n(n-1)条边的有向图叫做完全有向图度：有几条边与结点连接，则结点的度为几，在有向图中有方向，则有出度（指出去的）和入度（指进来的）之分简单路径：序列中顶点不重复出现的路径简单回路（简单环）：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路连通分量（无向图中的极大连通子图）：非连通无向图的连通子图的数量。强连通图和强连通分量：在有向图中，每个顶点都存在路径，则称为强连通图，强连通分量（极大强连通子图）是非强连通无向图的非连通子图的数量。

2.图的遍历

（1）BFS——广度优先搜索

          类似于树中的层序遍历，这种遍历方式用到了队列，过程如下：

从图中某个顶点v出发，将v入队，访问v；依次访问v的未曾访问的邻接点，并将其依次入队；访问完一个顶点的邻接点后，将其出队，从队头拿出下一个进行访问，循环这个过程直到所有顶点被访问过一边；

（2）DFS——深度优先搜索

          类似与树的先序遍历，可以用栈实现，过程如下：

从图中某个顶点v出发，将v入栈；寻找v的有没有未访问的邻接点，将找到的第一个入栈，打印元素，以栈顶元素未新顶点重复这个过程直到这条路径上的所有第一次访问的新顶点都入栈；出栈，然后再以栈顶的元素为新顶点，进行2过程，直到所有顶点都被访问。所有顶点都只会访问过一遍；

3.图的其他重要算法

          图在这里还有几个重要算法，这里只提一下，感兴趣或者时间足够的同学可以去搜索一下相关资料进行进一步的了解。

最小生成树：普利姆算法（Prim）（适用于稠密图）、克鲁斯卡尔算法（Kruskal）（适用于稀疏图）

最短路径：迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）

拓扑排序：AOV网，该算法可以判断图中有没有环

关键路径：AOE网，该算法可以找到一条从源点（出度为0）到汇点（入度为0）的带权路径最长的路径，即关键路径。

4.图的常见题型

（1）图的顶点和边数的关系计算问题

例题一：在一个无向图中，所有顶点的度数之和等于图的边数的________倍。

答案：2

例题二：在一个有向图中，所有顶点的入度之和等于所有顶点的出读之后的_______倍。

答案：1

例题三：具有n个顶点的有向图最多有_______边。

答案：n(n-1)

例题四：n个顶点的连通图用邻接矩阵表示时，该矩阵至少有_________个非零元素。

答案：2(n-1)

解题方法：像上述题目这种规律题，可以之间画图用数学归纳法解决，不好画的再用图的性质和定义进行计算。

例题五：G是一个非连通无向图，共同28条边，则该图至少有________个顶点。

答案：9

解析：8个顶点的连通无向图最多有28条边，再添加一个点即构成非连通无向图，故该图至少有九个顶点。

公式：n个顶点的连通无向图最多有n*(n-1)/2条边。

（2）图的算法与概念问题

例题一：若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中的所有顶点，则该图一定是_________。

答案：连通图

解析：这里要注意的是题目说的是无向图还是有向图。

例题二：最适合构造一个稠密图G的最小生成树的算法是_________。

答案：Prim算法

解析：由算法概念可知

例题三：图的BFS生成树的树高比DFS生成树的树高________。

答案：小或相等

a解析：画图法最好解决。

例题四：可以判断一个有向图是否有环的算法是__________。

答案：拓扑排序

（3）图的遍历结果问题

例题一：图类型的遍历结果

如图所示，在下面5个序列中，符号深度优先遍历的序列个数是______。

a、e、b、f、d、ca、c、f、d、e、ba、e、f、d、e、ba、e、f、d、b、ca、e、c、f、d、b

答案：2

解析：第一个和第四个是对的，该图深度优先遍历的可能有：

a、b、e、d、f、ca、b、e、f、d、ca、e、b、d、f、ca、e、b、f、d、ca、c、b、e、d、fa、c、b、e、f、da、c、e、b、d、fa、c、e、b、f、d

例题二：邻接矩阵类型遍历结果

图的邻接矩阵如图所示，则从顶点v0出发按深度优先遍历的结果是________。

答案：v0、v1、v3、v4、v2、v5、v6

解析：

这里需要注意的是在第四步中，v2与v0和v4相连，但前面已经遍历过，所以之间返回，在v4中找到v5然后再继续进行。

例题三：邻接表类型的遍历结果

已知图的邻接表如图所示，则从顶点v0出发按广度优先遍历的结果是________，按深度优先遍历的结果是________。

答案：v0、v1、v2、v3；v0、v1、v2、v3

解析：

其中广度优先搜索时，因为v0处就给遍历完了，后面就不用进行了。

其实后面两种题型可以画图转化成第一种题型，然后在做。

七、查找

1.线性表

（1）顺序查找

        从表的一端开始，依次将记录的关键字和给定值进行比较。

        算法时间复杂度：O(n)

        特点：

对表结构和顺序无任何要求，适用于顺序结构和链式结构平均查找长度较大，查找效率较低，所以当n很大时，不宜采用顺序查找

（2）折半查找

         也称二分查找，一次可以排除一般的元素，效率较高但适用范围小。查找过程为（此时是递增的有序表）：从表的中间开始，如果给定值和中间值相等，则查找成功；如果给定值大于或小于中间值，则在表中大于或小于中间值的范围内寻找，重复查找，直到找到或找完（一般结束条件是left>right）

        核心代码：mid = （left+right）/2;

        算法时间复杂度：O(

)

        特点：

要求线性表必须是顺序结构的顺序表中的元素必须是有序的

（3）分块查找

        又称索引顺序查找，除表本身外，还需创建一个索引表。索引表中的数据是子表的起始位置和最大值。先找元素可能存在的块，进行顺序查找

        

        特点：

在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在块内进行插入和删除运算要增加一个索引表的存储空间并对初始索引表进行排序运算

2.树表

（1）二叉排序树

         二叉排序树是具有以下性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

性质：中序遍历一个二叉排序树时可以得到一个结点值递增的有序序列。

（2）平衡二叉树（AVL树）

         平衡二叉树是具有以下性质的二叉排序树：

左子树和右子树的深度之差的绝对值不超过1；左子树和右子树也是平衡二叉树。

（3）B+树和B-树：这里不进行讲解，感兴趣或时间充裕的同学可以在网上自行了解。

3.散列表（哈希表）

（1）散列函数的构造方法（计算哈希值做索引）

数字分析法平方取中法折叠法除留余数法（最常用）：H(key)=key%p

（2）处理冲突（哈希值相等）的方法

开放地址法：

=（H(key)+d)%m

线性探测法：将散列表假想为一个循环表，发生冲突时，按顺序找下一个空单元，直到找到空的存进去，如果找不到，这要做数据溢出处理，此时d=1，2，3…m-1二次探测法：d=

……

(k<=m/2)伪随机探测法

链地址法

        把具有相同散列地址的记录放在同一个单链表中，称之为同义词链表。有m个散列地址就有m个单链表，同时用数组HT[0……m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入以HT[i]为头结点的单链表。

4.查找的常见题型

（1）查找的定义和特点的考察问题

例题一：适用于折半查找的表的存储方式，以及元素排列要求为__________。

答案：顺序方式存储且元素有序

例题二：如果要求一个线性表即能较快地查找，又能适应动态变化的要求，最好采用哪种查找？

答案：分块查找

例题三：折半查找与二叉排序树的时间性能_______。

答案：有时不相同

解析：折半查找的时间复杂度为O(

)，而二叉排序树在形态均匀时查找性能最好，时间复杂度为O(

)。

（2）折半查找结果和构造二叉排序树问题

例题一：

折半查找有序表（4、6、10、12、20、30、50、70、88、100）。若查找表中元素58，则它将依次与表中___________________比较大小，查找结果失败。

答案：20、70、30、50

解析：

left=1，right=10，mid=5，中间值为20；left=6，right=10，mid=8，中间值为70；left=6，right=7，mid=6，中间值为30；left=7，right=7，mid=7，中间值为50；left=8，right=7，left>right,查找结果失败。

例题二：

分别以下列序列构造二叉排序树，与用其他3个序列所构造的结果不同的是（）。

A.(100,80,90,60,120,110,130)          B.(100,120,110,130,80,60,90)

C.(100,60,80,90,120,110,130)          D.(100,80,60,90,120,130,110)

答案：C

解析：

 （3）查找的相关计算问题

例题一：对包含n个元素的表进行顺序查找时，若查找每个元素的概率相同，则平均查找长度为__.

答案：(n+1)/2

解析：(1+2+3+……+n)/n=n(n+1)/2n=(n+1)/2

例题二：现有长度为7初始为空的散列表HT，散列函数H(k)=k%7，用线性探测法解决冲突。将关键字22，43，15依次插入到HT后，查找成功的平均长度是_________。

答案：2

解析：

H(22)=22%7=1H(43)=43%7=1，冲突1次，放在2处H(15)=15%7=1，冲突3次，放在3处(1+2+3)/3=2

例题三：现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，线性探测法解决冲突。将关键字序列87、40、30、6、11、22、98、20依次插入HT后，HT查找失败的平均查找长度为___________________。

答案：6

解析：

H(87)=87%7=3H(40)=40%7=5H(30)=30%7=2H(6)=6%7=6H(11)=11%7=4H(22)=22%7=1H(98)=98%7=0H(20)=20%7=6，冲突1次，放在7处因为key的值为0~6，则（9+8+7+6+5+4+3）/7=6

（4）平衡二叉树问题

例题一：在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应该做哪种调整实在平衡？

答案：RL

解析：题目中已知最低的不平衡结点为A，其左孩子平衡因子为0，右孩子平衡因子为1，当把结点插入到A的右子树根结点的左子树上时，结点A的平衡因子绝对值超过1，即应做RL调整。

调整类型一共有LL、RR、RL、LR，这里用哪种类型取决于其平衡因子。

八、排序

          这一部分主要是对算法的理解，这里我推荐去b站寻找各个算法的动态效果，通过视频加深理解。