前言：本篇博客只做博主復(fù)習(xí)使用，不做其它，若有問題，也歡迎大家留言反饋。所有例題均為ZZULI往年期末題，正當(dāng)途徑獲得。最后一章排序章節(jié)較簡單，博主沒有單獨列出。

參考&鳴謝
AVL樹的插入操作（旋轉(zhuǎn)）圖解 MaxBruce
解決Hash（哈希表）沖突的四種方案 FrozenPenguin
圖——關(guān)鍵路徑 傅華濤Fu
拓撲排序詳解 Dream of maid
生成樹（基礎(chǔ)) 莫忘、莫念
圖的連通性問題 _Tham
數(shù)據(jù)結(jié)構(gòu)】樹、二叉樹和森林的相互轉(zhuǎn)換 Jacky_Feng
【專題】樹和森林的遍歷 ????? hm

💘 數(shù)據(jù)結(jié)構(gòu)的基本概念

😈 數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)?！x自百度百科

😈 邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別和聯(lián)系

😈 算法及其特性

😈 簡答題

2)

3)

💘 線性表（鏈表、單鏈表）

順序存儲結(jié)構(gòu)及其基本操作：請看博主這篇博客。

鏈式存儲結(jié)構(gòu)及其基本操作：請看博主這篇博客

😈 大題1

?? 題目解析

?? 算法思想和時間復(fù)雜度

• 題目說了，需要我們釋放結(jié)點的空間。

首先創(chuàng)建兩個結(jié)點指針變量pre，cur，讓pre初始化為Head，cur初始化為Head->next，開始遍歷帶頭單鏈表,分為兩種情況：

1. 如果pre指針的數(shù)據(jù)域和cur指針的數(shù)據(jù)域相等，那我們就刪除掉cur指針指向的結(jié)點（釋放結(jié)點空間后，完成鏈接即可），刪除cur之前，保存cur->next給變量next_,刪除完之后更新cur為next_，pre不用更新，因為當(dāng)前的值還可能和pre的數(shù)據(jù)域相等。
2. 如果pre指針的數(shù)據(jù)域和cur指針的數(shù)據(jù)域不相等，更新這兩個指針，pre更新為cur，cur更新為cur->next。

最后cur結(jié)點指針指向NULL，循環(huán)結(jié)束。

時間復(fù)雜度是$O(logN)$。

?? 代碼實現(xiàn)

void remove(LinkList Head)
{LinkList pre = Head;//前一個結(jié)點指針LinkList cur = Head->next;//后一個結(jié)點指針while (cur != NULL){if (pre->data != cur->data)//如果pre和cur的data不相等{pre = cur;cur = cur->next;}else//如果pre和cur的data相等{//先刪除掉cur結(jié)點LinkList node = cur->next;//保存cur->next指針結(jié)點free(cur);//釋放結(jié)點空間pre->next = node;//鏈接cur = node;//更新cur指針}}
}

?? 某搜題軟件上的答案

😈 大題2

?? 答案解析

在寫代碼前，我們還是畫圖來分析以下，刪除鏈表結(jié)點是如何刪除的：

代碼示例(C語言實現(xiàn))：

LinkList deleteodd(LinkList L)
{LinkList pre = L;//pre是當(dāng)前遍歷位置的前一個結(jié)點指針LinkList cur = L->next;//cur變量是當(dāng)前遍歷位置的結(jié)點指針while (cur != NULL)//cur為空就停止循環(huán){if (cur->data % 2 == 0)//如果當(dāng)前結(jié)點指針指向的結(jié)點的數(shù)據(jù)域是偶數(shù),正常更新{pre = cur;cur = cur->next;}else//否則，就刪除當(dāng)前結(jié)點{//先保存當(dāng)前結(jié)點的下一個結(jié)點指針，防止將當(dāng)前結(jié)點釋放后無法找到下一個結(jié)點的指針LinkList next_ = cur->next;free(cur);pre->next = next_;//更新pre的nextcur = next_;//更新cur}}return L;//返回頭節(jié)點
}

💘 棧和隊列

棧和隊列的基本特征：棧里面的數(shù)據(jù)后進先出。隊列里的數(shù)據(jù)先進先出。

它們的邏輯結(jié)構(gòu)都是線性結(jié)構(gòu)。可以用線性表或者單鏈表來實現(xiàn)。詳細請看博主這篇博客

棧和隊列作為線性結(jié)構(gòu)中比較典型的兩個結(jié)構(gòu)（應(yīng)用多），是很可能出一道大題的，下面我們來看一道大題（ZZULI往年期末題）：

😈 大題1

?? 題目分析

上圖忘記說明一點了，終態(tài)不為空也不叫滿足要求，需要返回false。

?? 答案解析

2. 代碼實現(xiàn)：

bool is_valid(char* s)
{int cnt_i = 0;//統(tǒng)計入棧的次數(shù)int cnt_o = 0;//統(tǒng)計出棧的次數(shù)int i = 0;while (s[i] != '\0'){if (s[i] == 'O')cnt_o++;elsecnt_i++;if (cnt_i < cnt_o){std::cout << "序列非法“ << std::endl;//用printf打印也可以return false; }i++;}if (cnt_i > cnt_o){std::cout << "序列非法“ << std::endl;//用printf打印也可以return false;}std::cout << "序列合法" << std::endl;return true;
}

上述代碼應(yīng)該是C++語言實現(xiàn)，因為C語言中沒有bool這個類型。打印處使用printf也可以，因為c++語言兼容C語言。

?? 標準答案（取自某搜題軟件）

😈 簡答題1

題目讓我們描述棧和隊列的邏輯結(jié)構(gòu)和特性，并分別舉出兩個應(yīng)用實例。

棧和隊列的邏輯結(jié)構(gòu)都是線性結(jié)構(gòu)，棧具有后進先出的特性，意思是后面入棧的元素，在進行出棧操作時會先出去。
隊列具有先進先出的特性，意思是先入隊列的元素，在進行出隊列操作時，會先出去。

應(yīng)用示例：棧：遞歸、后綴表達式求值。隊列：二叉樹的層次遍歷、圖的廣度優(yōu)先搜索。

😈 簡答題2

1. 首先來回答第一個問題
   什么是循環(huán)隊列？

循環(huán)隊列是隊列的一種，普通的隊列如果采用數(shù)組的方式存儲的話，為了不挪動數(shù)據(jù)，刪除隊列元素時，我們可能會直接將隊列首元素的下標后移，這樣就會造成一個問題，就是隊列的空間在減少，繼續(xù)入隊列（尾插）如果數(shù)組的空間滿了，這個時候如果進行過出隊列，就會造成隊列的元素小于數(shù)組實際的大小的情況。循環(huán)隊列就是為了解決這種問題，讓空間的利用大大提高。我們只需要把一個數(shù)組邏輯上想象成首尾相接即可。

用文字描述可能很抽象，我們畫圖來解釋：

2. 其次就是循環(huán)隊列的判空和判滿問題。
   先說結(jié)論： front = rear時為空
   (rear+1)%n = front時為滿，n為數(shù)組的大小。我們畫圖來分析一下為什么是這樣:
   

貼一個 標準答案：

1. 在順序隊列中由于數(shù)組空間不夠而產(chǎn)生的溢出叫真溢出；順序隊列因多次入隊列和出隊列操作后出現(xiàn)的有存儲空間但不能進入隊列操作的溢出稱為假溢出。 假溢出是由于隊尾rear的值和隊頭front的值不能由所定義數(shù)組下界值自動轉(zhuǎn)為數(shù)組上界值而產(chǎn)生的。其解決辦法有二一是將隊列元素向前“平移”(占用0至rear－front－1)；二是將隊列看成首尾相連即循環(huán)隊列[0…m－1]。
2. 在循環(huán)隊列下仍定義。front=rear時為隊空而判斷隊滿則用兩種辦法: 一是用“犧牲一個單元”即rear+1=front(準確記是(rear+1)％m=frontm是隊列容量)時為隊滿。
   另一種解法是“設(shè)標記”方法如設(shè)標記tag,tag等于0的情況下若刪除時導(dǎo)致front=tear為隊空；tag=1的情況下若因插入導(dǎo)致front=rear則為隊滿。

💘 樹

如果你對二叉樹什么都不了解，可以看博主，這篇博客

😈 二叉樹的定義、性質(zhì)和應(yīng)用

1. 定義

   二叉樹是一種特殊的樹，它的每個結(jié)點至多有兩個子樹，它的子樹是有順序的，即使一個結(jié)點只有一個子樹，你也要指明是左子樹還是右子樹。

2）性質(zhì)

3）應(yīng)用

😈 二叉樹的先序、中序遍歷和后序遍歷

這里在上述博客鏈接里面的文章里我們也有詳細的敘述，這里我們在簡單的畫圖敘述一下：

😈 已知遍歷序列構(gòu)造二叉樹

一般都是給一個中序遍歷序列、后序和前序遍歷序列給一個，讓你構(gòu)造二叉樹。

中序遍歷序列的作用是劃分某個結(jié)點的左子樹和右子樹。
后序或者前序遍歷序列的作用是確定當(dāng)前根結(jié)點。

?? 大題1

我們通過題目來講解

💑 二叉樹如何轉(zhuǎn)換成森林

🐸 二叉樹如何轉(zhuǎn)換成樹

要學(xué)會二叉樹轉(zhuǎn)換成森林，我們首先要學(xué)會將一棵二叉樹轉(zhuǎn)化成樹。

我們畫圖來詳細說明其步驟：

🐸 將二叉樹如何轉(zhuǎn)換成森林

很簡單，一共有兩步：

1. 刪除當(dāng)前二叉樹根節(jié)點與其右孩子結(jié)點的連線（使其獨立成一個新的二叉樹），然后看這個新的二叉樹有沒有右孩子結(jié)點，如果有繼續(xù)刪除連線。
2. 將上述獨立出來的所有二叉樹都轉(zhuǎn)化為樹。

下面我們演示一下我們本題二叉樹轉(zhuǎn)化為森林的過程：

💑 標準答案（出自某搜題軟件）

?? 大題2

💑 答案解析

本題看著沒有什么頭緒，只要讓根結(jié)點存運算符，然后得到它的左子樹和右子樹求得的值(后序遍歷)，然后做運算，即可得到整個表達式的值。

代碼:

typedef int DataType;typedef struct node
{DataType data;//存儲數(shù)據(jù)char op;//存儲運算符（可能有些結(jié)點只有運算符或者只有數(shù)據(jù)）struct node* left;struct node* right;
}*Pnode;float PostOrder(Pnode root)//假設(shè)對于是值的結(jié)點其運算符是一個特殊符號
{if (!root)//如果root為空return 0;float left_val, right_val = 0;//創(chuàng)建兩個臨時變量用來保存左邊子樹和右邊子樹的值float val = root->data;//返回值,如果當(dāng)前結(jié)點沒有左子樹和右子樹就證明其應(yīng)該是一個值，而不是運算符left_val = PostOrder(root->left);//先去得到左邊子樹的值right_val = PostOrder(root->right);//再得到右邊子樹的值switch (root->op){case '+':val = left_val + right_val;break;case '-':val = left_val - right_val;break;case '*':val = left_val * right_val;break;case '/': val = left_val / right_val;break;default: break;//如果這個}return val;//返回結(jié)果
}

💑 標準答案

?? 大題3

💑 答案

此題和上面一道有重復(fù)，我們熟練之后可
以不用那么詳細，照著先序遍歷序列和中序遍歷序列直接畫出二叉樹即可，就是要注意不要看錯了。

💑 標準答案

?? 簡答題1

💑 標準答案

?? 簡答題2

答案：

鏈域就是指針域，每個結(jié)點有四個指針域。

💑 標準答案

?? 簡答題3

💑 答案解析

💑 標準答案

標準答案的邊界值對應(yīng)下圖兩種情況：

😈 森林的先序遍歷和中序遍歷（可能出選擇題）

考的不多，不需要作為重點，重點應(yīng)該放在二叉樹的遍歷上。

😈 樹轉(zhuǎn)化為二叉樹以及森林轉(zhuǎn)化成二叉樹

我們前面以及介紹過了將二叉樹轉(zhuǎn)化成樹和將二叉樹轉(zhuǎn)化成森林，現(xiàn)在我們來介紹一下將樹轉(zhuǎn)化成二叉樹以及將森林轉(zhuǎn)化成二叉樹：

1. 將樹轉(zhuǎn)化成二叉樹：

2. 將一棵森林轉(zhuǎn)變成二叉樹：

😈 哈夫曼樹和哈弗曼編碼（這里肯定會出大題）

知識點：

😈 大題1

這種題比較簡單，基本上掌握一下基本套路就完事了。

?? 答案解析

😈 線索二叉樹

線索二叉樹就是將一個二叉樹線索化的過程。

二叉樹中有些左指針和右指針是空的，我們線索化的時候可以把它們利用起來。

• 無論是前序遍歷，中序遍歷還是后序遍歷，如果一個節(jié)點沒有左子樹就讓他的左指針指向他的前驅(qū)節(jié)點（前面一個要訪問的結(jié)點），如果一個節(jié)點沒有右子樹，就讓他的右指針指向他的后繼節(jié)點（后面一個要訪問的結(jié)點）。比較簡單我們不再舉例子。

💘 圖

😈 圖的連通性問題

😈 出度和入度

出度：某個頂點指向的頂點有幾個，它的出度就是幾。

入度：某個頂點被多少個頂點指向，它的入度就是幾。

😈 帶權(quán)無向圖的最小生成樹Prim、KrusKal算法

這兩個算法都可以求最小生成樹，我們只介紹Prim算法。

生成樹：首先只有連通圖才有生成樹。生成樹是所有頂點都連接在一起，但不存在回路的圖。因為樹就是不存在回路的。

最小生成樹：所有生成樹中使得各邊權(quán)值總和最小的那棵生成樹叫做最小生成樹。

Prim算法的原理：從某一個頂點開始構(gòu)建生成樹，每次將代價最小（到原先的生成樹權(quán)值
最小）的頂點加入這個生成樹中構(gòu)成新的生成樹。(后面我們會用具體的題目來演示)

KrusKal算法的原理：Prime算法更傾向于點之間的關(guān)系，所以又叫做加點法。而KrusKal算法更傾向于邊，它先將所有邊按照權(quán)值的大小升序排列，然后依次按照邊權(quán)值的大小開始建立最小生成樹，如果加入當(dāng)前權(quán)值最小的邊時會導(dǎo)致出現(xiàn)回路，就舍棄，知道我們加入了n-1條邊為止。

😈 有向無環(huán)圖、拓撲排序

在圖論中，如果一個有向圖無法從某個頂點出發(fā)經(jīng)過若干條邊回到該點，則這個圖是一個有向無環(huán)圖（DAG圖）。

拓撲排序的定義：
在有向無環(huán)圖中，我們將全部活動（頂點和邊的關(guān)系）排列成一個線性序列，使得這個圖中中有弧<i,j>存在 則在這個序列中，i 一定排在j的前面 具有這種線性序列稱為拓撲有序序列，相應(yīng)的拓撲有序排序的算法稱為拓撲排序。
拓撲排序的方法：

😈 大題1

下面題目涉及拓撲序列和最小生成樹的構(gòu)建比較重要，一定得掌握：

?? 答案解析

😈 大題2

（1）G1最多有n-1+n-2+n-3+…+1 = $n(n?1)/2$。G1最少有n-1條邊（不成環(huán)，但是連通）。

(2)和（3）：

?? 標準答案

😈 關(guān)鍵路徑和關(guān)鍵活動

關(guān)鍵路徑這塊的概念比較多。

AOE網(wǎng)：在一個表示工程的帶權(quán)有向圖中，頂點表示事件，用邊來表示活動，邊上的權(quán)值叫做活動持續(xù)的時間，這個有向圖就是活動的網(wǎng)。

源點：在這個AOE網(wǎng)中，入度為0的點叫做源點。

終點：在這個AOE網(wǎng)，出度為0的點叫做終點。

AOE網(wǎng)的兩個性質(zhì)：

1. 只有這個頂點的入度的活動都已經(jīng)結(jié)束，這個頂點表示的事件才會開始。
2. 只有這個頂點的事件開始后，從這個頂點出發(fā)的活動才會開始。

由于到達終點前，所有指向這個終點邊上的活動都必須結(jié)束，所以完成整個工程的最短時間必須是那個源點到終點的最大長度，這個最大長度叫做關(guān)鍵路徑。關(guān)鍵路徑上的活動叫做關(guān)鍵活動。

事件的最早發(fā)生時間（ve(i)）: 從源點出發(fā)（假設(shè)開始是0），該頂點的入度的各個活動中的最長時間（只有這個活動完成了，這個事件才能發(fā)生）。

事件的最晚發(fā)生時間（vl(i)）:從終點出發(fā)，要在保證不耽誤工期的情況下（關(guān)鍵路徑，也就是最短頂點對應(yīng)的事件完成的時間），在終點的最晚發(fā)生時間一定的條件下，倒推其它點的最晚發(fā)生時間。如果一個點有兩個出度，推出了兩個最晚發(fā)生時間，要取最小的那個（取更大的那個就有一個事件就不能完成了，工程最晚完成時間就要推遲）。

終點的事件最晚發(fā)生時間 = 最早發(fā)生時間。

活動的最早發(fā)生時間（ee(i)）:某個活動開始的前提是那個頂點表示的時間開始了，所以這個值和這個活動所在邊的起點的事件最早發(fā)生事件相等。

活動的最晚發(fā)生時間（el(i)）:只有這個頂點的入度的活動都已經(jīng)結(jié)束，這個頂點表示的事件才會開始，所以我們知道這個頂點的最晚發(fā)生時間，減去入度的活動的權(quán)值，就是對應(yīng)的該活動的最晚發(fā)生時間。

el(i) = ee(i)的活動叫做關(guān)鍵活動，關(guān)鍵活動所連成的源點到終點路徑叫做關(guān)鍵路徑（可能有多條）。證明省略。
下面我們通過題來演示一下：

?? 大題2

💑 答案解析

畫兩個表格，照著帶權(quán)有向圖直接寫時間即可，只要了解了這四個概念所代表的意思，及其如何來求。

💑 標準答案

😈 圖的遍歷（廣度優(yōu)先和深度優(yōu)先）

我們先介紹思想，大題三會有具體的題目來演示操作：

廣度優(yōu)先遍歷（類似于樹的廣度優(yōu)先遍歷，也就是層序遍歷）：它的基本思想是這樣的：

1. 先任選一個頂點開始遍歷。
2. 依次遍歷這個頂點的鄰接頂點。
3. 按照剛剛遍歷的順序去遍歷鄰接頂點的鄰接點。
4. 如果圖中還有頂點沒有訪問完，任選一個沒有被訪問的頂點，按照上面的步驟，直到所有頂點被訪問完。

深度優(yōu)先遍歷（類似于樹的先序遍歷，是其在圖上的推廣）：它的基本思想如下：

1. 先選一個頂點開始遍歷。
2. 再從這個剛剛訪問的頂點vi出發(fā)去訪問它的第一個鄰接點，重復(fù)本步驟，直到當(dāng)前頂點沒有鄰接點。
3. 返回剛剛訪問過的且還有未被訪問鄰接點的頂點，找出并訪問該頂點未被訪問的鄰接點，執(zhí)行步驟2。
4. 重復(fù)執(zhí)行以上步驟，直到所有頂點被訪問完。

😈 最短路徑

最短路徑有四種算法可以求，詳細原理可以看博主這篇博客。

?? 大題3

💑 答案解析

💑 標準答案

答案的深度優(yōu)先遍歷序列是錯誤的。

💘 查找

😈 靜態(tài)查找表：順序查找、折半查找

順序查找：按照順序在表（一般是數(shù)組）中依次查找，時間復(fù)雜度是$O(N)$。一般不用。

折半查找：即我們所說的二分查找算法。這個算法的前提是表已經(jīng)有序。時間復(fù)雜度是$O(logN)$。

?? 大題1

💑 答案解析

💑 標準答案

.

😈 動態(tài)查找表: 二叉排序樹、二叉平衡樹、m階B樹

?? 二叉排序樹

請看博主這篇博客
這個很簡單考的不多，重點看二叉平衡樹和m階B樹。

?? 二叉平衡樹

二叉樹平衡樹上課只介紹了AVL樹。

AVL樹是平衡搜索二叉樹的一種，它是為了解決普通二叉搜索樹不平衡的問題，它通過保持每個結(jié)點的左右兩棵子樹的高度差不超過1來維持查找效率。

AVL樹有以下性質(zhì)，滿足以下性質(zhì)的二叉樹也叫做高度平衡：

1. 左右子樹的高度差不超過1（-1，0，1）。
2. 左右子樹也為AVL樹

• 我們這里的左右子樹的高度均為左右子樹的最長路徑的結(jié)點個數(shù)。

如果一棵二叉樹是高度平衡的，那么它就是平衡二叉樹，它的高度是$O(logN)$,搜索的效率也在$O(logN)$量級。

我們重點來看一下AVL樹的插入調(diào)整：

1. 左單旋
   在當(dāng)前高度較高的某節(jié)點的右子樹的右邊插入了一個新結(jié)點引發(fā)了不平衡，需要右單旋。

2. 右單旋
   在當(dāng)前高度較高的某節(jié)點的左子樹的左邊插入了一個新結(jié)點引發(fā)的不平衡，需要左單旋。

3. 左右雙旋
   當(dāng)前高度較高的某節(jié)點的左子樹的右子樹插入了一個結(jié)點，引發(fā)了不平衡，需要先左單旋，再右單旋轉(zhuǎn)。

4. 右左雙旋
   當(dāng)前高度較高的某節(jié)點的右子樹的左子樹插入了一個結(jié)點，引發(fā)了不平衡，需要先右單旋，再左單旋轉(zhuǎn)。

我們用具體的題目來演示如何旋轉(zhuǎn)：

?? 大題1

💑 答案解析

💑 標準答案

這個答案有點問題，最后一個數(shù)據(jù)65插入的它沒寫，命名的話博主是按照旋轉(zhuǎn)的方向命名，這個答案是按照插入的方向命名。

😈 B樹

B樹是多路平衡二叉樹。

1. B樹的性質(zhì)

2. B樹的插入和刪除
我們用下面的題目來演示，如果你沒有搞懂，請自行去B站上學(xué)習(xí)。

?? 大題2

💑 答案解析

😈 哈希表

?? 哈希表的長度、哈希表的裝填因子等

哈希表的長度是指的是哈希表可以存儲的最大元素數(shù)量。
哈希表的裝填因子是指的是當(dāng)前已經(jīng)存儲的元素的數(shù)量（桶的數(shù)量）/ 哈希表的長度

?? 常用的構(gòu)造哈希函數(shù)的方法

1. 除留余數(shù)法
   除留取余法是將關(guān)鍵字除以一個不大于哈希表長度的正整數(shù)p（一般是小于哈希表長度的最大質(zhì)數(shù)），并將所得余數(shù)作為地址。

具體而言，除留取余法的步驟如下：

1、選擇一個不大于哈希表長度的正整數(shù)p（一般是小于哈希表長度的最大質(zhì)數(shù)）作為模。
2、將關(guān)鍵字對p取模作為哈希表的索引地址。

2. 直接定址法
   直接定址法就是將關(guān)鍵字作為索引地址，關(guān)鍵字就是下標，要求關(guān)鍵字范圍小且連續(xù)，否則會造成空間浪費。

?? 處理沖突的方法

1. 開放尋址法

   原理是當(dāng)發(fā)生沖突時，是以當(dāng)前地址為基準，去通過尋址找到下一個地址。
   常用的尋址方法：

   • 線性探測：發(fā)生沖突時，從當(dāng)前地址開始往后面去找空地址，如果到達表尾，就回到表頭繼續(xù)找，直到找到或者已經(jīng)遍歷全表。
   • 二次探測(平方探測)：發(fā)生沖突時，從當(dāng)前地址開始，左右跳躍，di = $1^2,?1^2,2^2,?2^2,3^2,?3^2......$直到找到為止。

2.鏈地址法
又叫做拉鏈法，這個方法是把哈希表的每個位置看成一個桶，每個桶里面都是一個鏈表，然后如果發(fā)生沖突了，就把新的結(jié)點，尾插到這個位置桶的尾部。

我們通過下面的題目來演示：

?? 大題3

💑 答案解析