1. 關(guān)于算法

(1) 什么是算法?
算法：顧名思義，一種計算的方法，在程序設(shè)計上，就表現(xiàn)為一組指令序列。

(2）算法與程序有什么區(qū)別和聯(lián)系?
程序是指用某種計算機語言對一個算法的具體實現(xiàn)，即具體要怎么做，
算法偏重于對解決問題的方法的描述，即要做什么。

(3）如何評價算法的優(yōu)劣?
時間復(fù)雜度與空間復(fù)雜度

一個算法應(yīng)該具有以下五個重要的特征：

有窮性（Finiteness）
算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止；

確切性(Definiteness)
算法的每一步驟必須有確切的定義；

輸入項(Input)
一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；

輸出項(Output)
一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；

可行性(Effectiveness)

2. 棧的特性是什么

棧的特點是先進后出表。棧是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)。


3.?稀疏矩陣
0 0 3 0 0 0
1 0 0 0 0 6
0 0 4 0 0 0
0 2 0 0 5 0
0 0 0 0 0 0
(1) 寫出該稀疏矩陣的三元組順序表(行優(yōu)先)存儲表示。
(2) 簡要敘述將稀疏矩陣進行轉(zhuǎn)置的算法思想，并給出轉(zhuǎn)置結(jié)果。

行優(yōu)先的表現(xiàn)形式: (行，列，數(shù)值)
（(1,3,3),(2,1,1),(2,6,6),(3,3,4),(4,2,2),(4,5,5)）

進行行轉(zhuǎn)置的方法有：
方法1（簡單，但是無序）：直接將行和列的值互換
方法2（最后有序，還是按照行優(yōu)先顯示）：

1. 遍歷三元組順序表，找列為1的值，執(zhí)行行列互換 ；

4.?哈夫曼樹、哈夫曼編碼
假定電文字符集為{A,B,C,D,E,F,G,H),它們在電文中出現(xiàn)的次數(shù)分別為{20,7,13,6,39,4,14,5},請為這8個字符設(shè)計哈夫曼編碼。畫出哈夫曼樹并給出編碼。要求在構(gòu)造哈夫曼樹的過程中，其中權(quán)值較小結(jié)點放在左側(cè)，編碼時左分支生成代碼0，右分支生成代碼1
(術(shù)語： 路徑 、 路徑長度、權(quán)重 、wpl : 【路徑長度 * 權(quán)重】 的總和 )

（畫圖方法：將最小的兩個數(shù)進行連接，連接的和又放入比較的數(shù)中; ?注： 左小右大）


哈夫曼編碼：根據(jù)畫的圖寫出編碼；（左0右1）

wpl : 路徑長度*權(quán)重 ?相加之和
如： wpl = (20+39) *2 + (13+14)*3 + (4+5+6+7) * 4

5.?哈希函數(shù)

對關(guān)鍵字集合{1,19,10,23,11, 84,14,27,20}，哈希地址空間為HT[O0 ..14]，若采用除留余數(shù)法構(gòu)造哈希函數(shù)和線性探測再散列方法處理沖突，試畫出最后得到的哈希表，并計算在等概率情況下查找成功時的平均查找長度ASL。

(1)寫出用除留余數(shù)法構(gòu)造的哈希函數(shù)。
( 函數(shù) ： H（key）=key ?MOD ?p , p<=m ? （最簡單，最常用）p的選取很重要
一般情況，p可以選取為小于或等于空間長度的最大質(zhì)數(shù)）)
H(key) = key ?mod 13

(2）采用線性探測再散列處理沖突，試畫出最后得到的哈希表。
1 mod 13 = 1 ? ? ? 23 mod 13 = 10 ? ? 14 mod 13 = 1
19 mod 13 = 6 ? ? 11 mod 13 = 11 ? ? 27 mod 13 = 1
10 mod 13 = 10 ? ?84 mod 13 = 6 ? ?20 mod 13 = 7

?下標(biāo)?0?1?2?...?數(shù)值?
?1?14?
?查找長度?
?1?2?


(3）計算在等概率情況下該哈希表在查找成功時的平均查找長度ASL。ASL = ?(1+2+3+1+2+2+1+2+2) / 9

6.二叉排序樹
依次讀入給定的整數(shù)序列{6,15,5,7,19,8,5,17,4},完成下列操作:

(1）構(gòu)造該二叉排序樹;?(以第一個數(shù)為根，比根結(jié)點小的放在左邊，比根結(jié)點大的放在右邊)

(2）計算在等概率情況下該二叉排序樹的平均查找長度ASL。
（第一層的一次，第二層的兩次，依次累推）ASL = ?(1+(2*2) + ?(3*3) + (4*2) ) / 9 =


7. 最小生成樹

克魯斯卡爾算法(Kruskal算法):
1. 對邊進行排序（升序）
2. 不同連通分量上的頂點進行連接



普界姆Prim算法方法:
1. 選擇任何一頂點，做為起始點
2. 找與頂點相連接的最小權(quán)的邊，注:不形成回路的邊
3. 重復(fù)1、2步驟，直到所有頂點相連，即邊為n-1為止


注意事項：

構(gòu)成生成樹的準(zhǔn)則有三條:
<1> 必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹。
<2>必須使用且僅使用n-1條邊來連接網(wǎng)絡(luò)中的n個頂點
<3>不能使用產(chǎn)生回路的邊。

8. 線索二叉樹

建立線索的規(guī)律如下：
1、若當(dāng)前訪問的結(jié)點的左指針域為空，則左指針域指向prior指的結(jié)點，同時置lbit為0，否則，置lbit為1；
2、若prior所指結(jié)點的右指針域為空，則右指針域指向當(dāng)前訪問的結(jié)點，同時置rbit為0，否則，置rbit為1；
3、遍歷結(jié)束時，將prior->rchild指向頭結(jié)點，并置prior->rbit為0。


（畫線索二叉樹時，會告訴你是先序線索二叉樹，中序線索二叉樹，后序線索二叉樹；當(dāng)結(jié)點無左孩子時，將其指向它前面的結(jié)點，而結(jié)點的順序是指先序或中序或后序的順序。無右孩子時，指向序列后面的結(jié)點）

9. 平衡二叉樹

定義：任意結(jié)點的左、右子樹高度差的絕對值不超過1，將這樣的二叉樹稱為平衡二叉樹，簡稱平衡樹（AVL樹）。
? 定義結(jié)點左子樹與右子樹的高度差為該結(jié)點的平衡因子，則平衡二叉樹節(jié)點的平衡因子的值只可能是-1，0，1


判斷是否為大頂堆的方法，參考：https://www.bilibili.com/video/BV1RL4y1e72q

（看前面的數(shù)字是否大于后臺兩個數(shù)字，依次進行判斷 - 相當(dāng)于轉(zhuǎn)成對應(yīng)二叉樹，再來比較）


10. Dijkstra 最短路徑

列出起點， 終點，path , dist 距離起點：根據(jù)題的要求為0
終點為1,2,3,4;path 表示，從那個點到的終點
dist 表示距離起點到終點有路徑就寫對應(yīng)的值，沒有就寫-1，其它在找距離中最小的點，加入到起點集合中，判斷此到其它點的路徑，如果小于就一次寫的路徑，就對路徑與距離進行替換

11. 判斷有向圖是否有環(huán)

判斷方法：
拓撲排序：?還有頂點末輸出，但已經(jīng)不存在沒有前驅(qū)的頂點了
深搜：從一個頂點出發(fā)存在搜回到自己的路徑

12. 拓撲序列
1、從AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點并且輸出
2、從AOV網(wǎng)中刪除去該頂，并且刪除所有以該頂點為尾的弧
2、重復(fù)所有操作，直到所有頂點全部輸出 ，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點

若此時輸出的頂數(shù)小于有向圖的頂點數(shù)，則說明有向圖中存在回路
對一個有向圖構(gòu)造拓撲序列的過程，稱為拓撲排序


13. 圖的深度遍歷DFS與廣度遍歷BFS

DFS：
1、遍歷過的節(jié)點不重復(fù)遍歷（根據(jù)鄰接表）
2、回溯


BFS:進入一個元素，出隊，然后，將出隊的這個元素后面的節(jié)點，添加再隊列后面
判斷是否為AOV,什么意思，判斷的條件是什么注：不要重復(fù)，重復(fù)的不要入隊


14. 森林與二叉樹的轉(zhuǎn)換

森林轉(zhuǎn)二叉樹的方法
a.?將森林中所有的普通樹各自轉(zhuǎn)化為二叉樹
b. 森林中第一棵樹的樹根作為整個森林的樹根，其他樹的根節(jié)點看作是第一棵樹根節(jié)點的兄弟節(jié)點，采用孩子兄弟表示法將所有樹進行連接
樹或森林與二叉樹之間有一個自然的一一對應(yīng)關(guān)系。任何一個森林或一棵樹可惟一地對應(yīng)到一棵二叉樹；反之，任何一棵二叉樹也能惟一地對應(yīng)到一個森林或一棵樹。

將樹轉(zhuǎn)換為二叉樹：
樹中每個結(jié)點最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟。按照這種關(guān)系很自然地就能將樹轉(zhuǎn)換成相應(yīng)的二叉樹：
1.在所有兄弟結(jié)點之間加一連線
2.對每個結(jié)點，除了保留與其長子的連線外，去掉該結(jié)點與其它孩子的連線