1.時間復(fù)雜度

2.樹，森林，二叉樹的轉(zhuǎn)換

2.1樹轉(zhuǎn)二叉樹

1. 給所有的兄弟節(jié)點之間加一條連線；
2. 去線，只保留當(dāng)前根節(jié)點與第一個葉子節(jié)點的連線，刪除它與其他節(jié)點之間的連線；
3. 然后根據(jù)左孩子右兄弟進(jìn)行調(diào)整；
   

2.2森林轉(zhuǎn)為二叉樹

把森林的每棵樹轉(zhuǎn)為二叉樹（遵循左孩子右兄弟即可）

2.3二叉樹轉(zhuǎn)為森林

當(dāng)一顆二叉樹的根節(jié)點有右孩子，則說明這顆二叉樹能夠轉(zhuǎn)換為森林；

1. 從根節(jié)點開始，若存在右孩子，則把與右孩子節(jié)點的連線刪除。再查看分離后的二叉樹，若其根節(jié)點的右孩子存在，則連線刪除…。直到所有這些根節(jié)點與右孩子的連線都刪除為止。
   
   
   二叉樹的N1再減去一個1就為T1；

3.鏈表的操作

4.樹的操作

從子節(jié)點的角度，共有節(jié)點數(shù)為：度數(shù)為3的子節(jié)點數(shù)+度數(shù)為2的子節(jié)點數(shù)+度數(shù)為1的子節(jié)點數(shù)+根節(jié)點數(shù)=32+21+1*2+1=11；
從父節(jié)點的角度，共有節(jié)點數(shù)為：度數(shù)為3的節(jié)點數(shù)+度數(shù)為2的節(jié)點數(shù)+度數(shù)為1的節(jié)點數(shù)+度數(shù)為0的節(jié)點數(shù)=2+1+2+x；
解得x=6

5.平均比較次數(shù)的計算

平均比較次數(shù)=總比較次數(shù)/元素待查找的概率；

6.平均查找長度：

根據(jù)分塊查找的原理，平均查找長度可以通過每塊的平均查找長度乘以每塊的概率來計算。在這個問題中，每塊的平均查找長度為3（由于每塊有6個元素，所以平均查找長度為6/2=3），每塊的概率為1/5。

因此，平均查找長度為：

(1 * 1/5) + (2 * 1/5) + (3 * 1/5) + (4 * 1/5) + (5 * 1/5) = 15/5 = 3

接著，在塊內(nèi)查找元素的平均查找長度為：

(1 * 1/6) + (2 * 1/6) + (3 * 1/6) + (4 * 1/6) + (5 * 1/6) + (6 * 1/6) = 21/6 = 3.5

最后，將兩個結(jié)果相加得到平均查找長度：

3 + 3.5 = 6.5

所以，平均查找長度為6.5；

7.拓?fù)湫蛄?#xff1a;

首先按照集合關(guān)系畫出有向圖，從圖中選出入度為0的①的頂點并輸出，刪除從①頂點發(fā)出來的所有有向邊。然后再選擇一個入度為0的頂點④并輸出，刪除從④頂點發(fā)出來的所有有向邊，按此規(guī)律反復(fù)，最后得到的拓?fù)渑判驗?1,4,2,3)

8.循環(huán)隊列和棧

最多能夠存儲m-1個元素；

棧的長度為m，表示可以存儲m個元素，因為棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，插入和刪除操作都在棧頂進(jìn)行，所以不需要額外的空間來區(qū)分?？蘸蜅M的狀態(tài)。

9.冒泡排序：

8，8

10.排序算法空間復(fù)雜度和時間復(fù)雜度：

1.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮，應(yīng)該選擇快速排序。因為在平均情況下，快速排序的時間復(fù)雜度為O(n log n)，比堆排序略快。

2.而如果從節(jié)省存儲空間的角度來考慮，則最好選擇堆排序。因為堆排序是一種原地排序算法，不需要額外的存儲空間，而快速排序在遞歸的過程中需要消耗大量的棧空間，所以在存儲空間方面，堆排序更有優(yōu)勢。

11.平均查找長度：

1.先畫出排序二叉樹——>2.（1+22+32+42）/7=19/7；（比較次數(shù)=層數(shù)——>比較次數(shù)當(dāng)前層數(shù)的節(jié)點數(shù)）

12.哈夫曼樹

哈夫曼樹就是：兩個最小的節(jié)點構(gòu)造一個較大的節(jié)點；

13.初始化堆

(24，65，33，80，70，56，48)——>小根堆思想

(80,70,56,65,24,33,48) ——>大根堆

14.最小生成樹上所有邊的權(quán)值和：

方法： 一種是隨意從一個點開始，找權(quán)值最小的路徑，另一種就是依次找最短的邊的，舍去形成回路的邊，直到遍歷所有結(jié)點

15.有向圖中的鄰接表和鄰接矩陣

**鄰接表：**是一種順序分配和鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲結(jié)構(gòu)。
**逆鄰接表：**任一表頭結(jié)點下的邊結(jié)點的數(shù)量是圖中該結(jié)點入度的弧的數(shù)量，與鄰接表相反。
逆鄰接表中邊節(jié)點個數(shù)等于鄰接表邊結(jié)點個數(shù)。表結(jié)點個數(shù)相同，但是頭結(jié)點個數(shù)不一定相同。

16.鏈表的知識點

鏈表插入和刪除只是改變了相應(yīng)節(jié)點的指針指向，地址并沒有改變，所以不必移動

17.鄰接矩陣知識點：

鄰接表：0(v+e)；
鄰接矩陣：0(v^2)；

鄰接矩陣存儲時，無論有向圖還是無向圖，也無論邊的數(shù)目是多少，其存儲空間都是O（n的平方），書上原話，所以鄰接矩陣存儲空間與邊的數(shù)目無關(guān)