數據結構筆記匯總
線性： 線性（1:1）、棧、隊、數組
非線性：樹形（1：多）、圖形（多：多）
存儲結構：順序（數組）、鏈式（指針）
2. 邏輯結構與元素相對位置無關
鏈式存儲物理地址和邏輯地址不一定相同連續，所以它記憶體中可⽤存儲單元的地址/數據結點地址：連續與否都可以
3. （解釋）不生成可執行文件
4. 讀取元素花費時間最少：順序表
5. 在具有 n 個結點的單鏈表上查找值為 x 的元素時，其時間複雜度為O（n）
6. 設指針 q 指向單鏈表中結點 A，指針 p 指向單鏈表中結點 A 的後繼結點 B，指針 s 指向被插⼊的結點 X，則在結點 A 和結點 B 插⼊結點 X 的操作序列為:q->next=s;s->next=p;
7. 訪問第 i 個元素的前驅（1<i<=n）的時間複雜度為O（1）
8. 添加/刪除操作
單鏈表
帶頭結點的單鏈表
帶頭結點的雙循環單鏈表
單鏈表的頭插法建立鏈表
單鏈表的頭插法建⽴鏈表所得到的數據的順序與輸⼊的時候的順序相反
單鏈表的頭插法建⽴鏈表演算法不簡單，要引⼊⼤量的指針輔助運算。（F）
單鏈表的尾插發建立鏈表
單鏈表的尾插法建⽴鏈表所得到的數據的順序與輸⼊的時候的順序相同
雙鏈表
帶頭結點的雙循環鏈表
鏈式存儲的後插法
帶頭結點的雙循環鏈表的空表
9. 3n+nlog2n+n2+8的數量級：n2
10. 演算法的評價不包括並行性
11. 集合中任何兩個結點之間都有邏輯關係但組織形式鬆散（F）
12. 數據元素具有相同的特性=數據項個數相同，類型一致
13. 數據在電腦存儲器內表示時，物理地址與邏輯地址相同並且是連續的，稱之為順序存儲結構
14. 演算法
定義：有限序列
目的：分析效率求改進
15. 高效性：指演算法的執行效率高（T）
指演算法需要的時間性能（F）
16. 鏈表
Malloc（）申請
Free（）釋放
在⼀個帶頭結點的雙向循環鏈表中，若要在 p 所指向的結點之前插⼊⼀個新結點，則需要相繼修改（4）個指針域的值
1、該新結點前驅指針指向p的前驅
2、p的前驅指針指向該新結點
3、該新結點的後繼域指向p結點
4、前驅的後繼域指向該新結點
17. 線性表
在進⾏添加/刪除元素時，應該在刪除元素前判空
在添加元素前判空（F）
可以在任何位置插入刪除
除第⼀個和最後⼀個元素外，其餘每個元素都由⼀個且僅有⼀個直接前驅和直接後繼
元素之間的邏輯關係是通過（物理位置）決定的.
有限序列，可以為空
串是⼀種特殊的線性表
兩種存儲結構：線性和鏈式
線性錶鏈式
線性錶鏈式：插入刪除方便，只需要向前或向後移動元素即可（F）
線性表鏈接存儲：
鏈表是⼀種動態存儲結構，鏈表的結點可調⽤申請 malloc()和 free()釋放
鏈表的結點可⽤free()申請和⽤malloc()釋放（F）
鏈表是⾮隨機存取存儲結構，對鏈表的存取必須從頭指針開始
對鏈表的存取可以從任何結點開始（F）
插⼊刪除運算⾮常⽅便；只需修改相應指針值
只需要向前或向後移動元素即可（F）
邏輯上相鄰的元素，其物理位置⼀定相鄰，元素之間的鄰接關係由指針域指示
不需要預先分配存儲空間，適用於數據量變化較大的情況
表的長度：數據結點的個數
適用於經常進行插入和刪除的操作
鏈接存儲的存儲結構所佔存儲空間分兩部分，⼀部分存放結點值，另⼀部分存放表示結點間關係的指針
線性表順序存儲
不便於插入和刪除的實現，而鏈式存儲便於
適用於變化量小的情況
必須按最⼤可能⻓度預分存儲空間，存儲空間利⽤率低，表的容量難以擴充,是⼀種靜態存儲結構
是一種隨機存取結構
適用於經常進行存取的操作
刪除時的最壞情況：要刪除的元素是順序表的第一個元素
刪除時的最好情況：要刪除的元素是順序表的最後一個元素
要求能夠較快的插⼊和刪除，⼜要求儲存結構能夠反映數據元素之間的邏輯關係則應該以順序儲存⽅式儲存
在⼀個⻓度為 n 的順序存儲的線性表中，向第 i 個元素(1<=i<=n+1)位置插⼊⼀個新元素時，需要從後向前依次後移（n-i+1）個元素
線性表一旦建立，就不能添加元素（F）
最後一個元素之後插入一個元素和刪除最後一個元素，採用容量足夠大的順序表
長度為n，刪除第i個元素，要向前移動n-1個元素
長度為n，第i個位置插入一個新元素，時間複雜度為O（n）
線性表是n個數據元素的有限序列(所以學院組織結構表就不是線性表)
順序線性表中有 n 個數據元素，則刪除表中第 i 個元素需要移動（n-1）個元素
18. 順序表
做刪除操作時，應該將表的長度-1
插⼊⼀個元素所需移動的元素平均數是（n+1）/2
順序表的⻓度是指：表中數據元素的個數
向⼀個有 127 個元素的順序表中插⼊⼀個新元素並保持原來順序不變，平均要移動(63.5)個元素
在⼀個⻓度為 n 的順序表中，刪除值為 x 的元素時需要⽐較元素和移動元素的總次數為n
表尾插⼊⼀個元素的時間複雜性的量級為O(1)
19. 數組
邏輯結構à線性結構
存儲結構à順序結構
設⼀維數組中有 n 個數組元素，則讀取值為 x 的數據元素的平均時間複雜度為O(n)
設⼀維數組中有 n 個數組元素，則讀取第 i 個數組元素的平均時間複雜度為0(1)
假定利⽤數組 a[N]順序存儲⼀個棧，⽤ top 表示棧頂指針，top==-1 表示棧空，並已知棧未滿，當元素 x進棧時所執⾏的操作為a[++top]= x
在⼀個具有 n 個單元的順序棧中，假定以地址低端（即 0 單元）作為棧底，以 top 作為棧頂指針，則當做出棧處理時，top 變化為top—
20. 隊列
先進先出
只能在隊尾添加/插入新元素
只能在隊首刪除元素
⽆論是順序存儲還是鏈接存儲的棧和隊列，進⾏插⼊或刪除運算的時間複雜性均為O(1)
利⽤順序隊進⾏元素⼊隊時最⼤的問題是會出現假溢出現象
隊列是被限定為只能在表的⼀端進⾏插⼊運算，在表的另⼀端進⾏刪除運算的線性表
當利⽤⼤⼩為 N 的數組存儲循環隊列時，該隊列的最⼤⻓度是n
從⼀個順序循環隊列中刪除元素時，⾸先需要後移隊首指針
判定⼀個隊列 QU（最多元素為 m0）為滿隊列的條件是QU->rear － QU->front = = m0
在⼀個鏈隊列中，front 和 rear 分別為頭指針和尾指針，則插⼊⼀個結點 s 的操作為rear->next=s;rear=s;
在⼀個 n 個結點的雙向鏈表中指針 p 所指向的結點之前插⼊⼀個新結點時，其時間複雜性的量級為O(1)
21. 棧
先進後出，後進先出
只能在棧頂做插入/刪除操作
向順序棧中插⼊新的元素分三步，分別是：判斷溢出或棧滿 修改棧頂指針 把新元素賦給棧頂單元
從順序棧中刪除元素分三步，分別是：判斷棧空 棧頂指針的值返回 修改棧頂指針
向棧中壓⼊元素的操作是：先移動棧頂指針，然後存⼊元素
設⽤鏈表作為棧的存儲結構則退棧操作：必須判別棧是否為空
設⽤鏈表作為棧的存儲結構則進棧操作：對棧不作任何判別
順序棧中在做出棧運算時，應先判別棧是否為空
順序棧中在做進棧運算時，應先判別棧是否為滿
Push進pop出
設棧 S 和隊列 Q 的初始狀態為空，元素 e1,e2,e3,e4,e5,e6依次通過棧 S，⼀個元素出棧後即進⼊隊列 Q，若 6 個元素出隊的序列是 e2,e4,e3,e6,e5,e1，則棧的容量⾄少應該是3
⼀個棧的輸⼊序列為：1,2,3,4，則棧的不可能輸出的序列是4321
印表機à隊列
判定⼀個順序棧 ST（最多元素為 m0）為空的條件是ST->top==0
假定⼀個鏈式棧的棧頂指針⽤ top 表示，每個結點的結構具有兩個域 data 和 next,出棧時進⾏的指針操作為top=top->next
刪除⾮空的順序存儲結構的堆棧的棧頂元素，棧頂指針 top 的變化是top=top-1
向⼀個棧頂指針為 hs 的鏈棧中插⼊⼀個*s 結點時，應執⾏s->next=hs；hs=s；
順序棧中當棧中元素為 m 時，做進棧運算時發⽣上溢，則說明棧的可⽤最⼤容量為m
判定⼀個順序棧的 S(最多元素時 m0)為滿的條件是S->top==m0-1
為了增加記憶體空間的利⽤率和減少發⽣上溢的可能性，由兩個棧共享⼀⽚連續的記憶體空間時，應將兩個
棧的（棧底）分別設在這⽚記憶體空間的兩端，這樣只有當兩個棧的棧頂在棧空間的某⼀位置相遇時才產⽣上溢
設輸⼊序列 1、2、3、…、n 經過棧作⽤後，輸出序列中的第⼀個元素是 n，則輸出序列中的第 i 個輸出元素是n+1-i
判定⼀個順序棧 S（棧空間⼤⼩為 n）為空的條件是S->top==0
設輸⼊序列為 1、2、3、4、5、6，則通過棧的作⽤後可以得到的輸出序列為：3，2，5，6，4，1
設指針變數 front 表示鏈式隊列的隊頭指針，指針變數 rear 表示鏈式隊列的隊尾指針，指針變數 s 指向將要⼊隊列的結點 X，則⼊隊列的操作序列為rear->next=s；rear=s；
解決順序隊上溢的⽅法
1、每當刪除⼀個隊頭元素時,則依次移動隊中的元素,始終使 front 指針指向隊列中的第⼀個位置
2、采⽤平移元素的⽅法:每當隊列中加⼊⼀個元素時,隊列中已有的元素向隊頭移動⼀個位置
3、建⽴⼀個⾜夠⼤的存儲空間,但這樣做會造成空間的使⽤效率降低
4、發⽣上溢時，⾃動丟失多餘元素(F)
22. 單鏈表
已知單鏈表尾指針，時間複雜度為O(1)
單鏈表中設置頭結點：空表和非空表統一，演算法處理一致
⾮空的循環單鏈表 head 的尾結點（由 p 所指向），滿⾜條件：p->next==head
將⻓度為 n 的單鏈錶鏈接在⻓度為 m 的單鏈表之後的演算法的時間複雜度為O(m)
⼀個單鏈表中，若刪除 p 所指向結點的後續結點(=單鏈表中指針 p 指向結點 m，若要刪除 m 之後的結點（若存在），則需要修改指針的操作為)，則執⾏p->next=p->next->next;
在⼀單鏈表中 n 個數據結點，則讀第 i 個數據結點的平均時間複雜度為O（n）
對於⼀個具有 n 個結點的單鏈表，在已知的結點*p 後插⼊⼀個新結點的時間複雜性為O(1)
單鏈表的判空條件
不帶頭結點的單鏈表head為空：head=null
⼀條單鏈表的頭指針變數為 head 且該鏈表沒有頭結點，判空：head=0
23. 樹
樹à層次
二叉樹不是特殊的樹，使用不是樹轉化過來的特殊情形
⼆叉樹與樹具有相同的樹形結構（F）
二叉樹是非線性數據結構，順序存儲結構和鏈式存儲結構都能存儲，但，不是所有的⼆叉樹樹形結構都適⽤順序存儲結構
若初始森林中共有 n 裸⼆叉樹，進⾏ 2n-1 次合併後才能剩下⼀棵最終的哈夫曼樹（F）
若⽬標串的⻓度為 n，模式串的⻓度為[n/3]，則執⾏模式匹配演算法時，在最壞情況下的時間複雜度是O(n2)
分支
設⾮空⼆叉樹上葉⼦節點數為 n0，雙分⽀數為 n²，單分⽀數為 n1，則n0=n2+1
深度
深度為 k 的完全⼆叉樹中最少有（2k-1）個結點
設⼀棵完全⼆叉樹中有 65個結點，則該完全⼆叉樹的深度為7，因為2n-1
設⼆叉樹有 n 個結點，則其深度無法確定
結點數
⼆叉樹的第 k 層的結點數最多為2k-1
⼀棵⼆叉樹上第 5 層的結點數最多為16個，因為2k-1
深度為 5 的⼆叉樹最少有(5)個結點
如果 T2是由有序樹 T 轉化⽽來的⼆叉樹，T後序結點=T2中序結點，T前序結點=T2前序結點
設某棵⼆叉樹中有 2000 個結點，則該⼆叉樹的最⼩⾼度為11，因為210=1024<2000，211=2048>2000
在⼀棵樹中，每個結點最多有（1）個前驅結點
⼆叉樹中第 i(i≥1)層上的結點數最多有（2i+1）個
利⽤ n 個值⽣成的哈夫曼樹中共有（2n-1）個結點.
設⼆叉樹根結點的層次為 0，⼀棵⾼度為 h 的滿⼆叉樹中的結點個數是2n+1-1
設 F 是由 T1、T2 和 T3三棵樹組成的森林，與 F 對應的⼆叉樹為 B，T1、T2 和 T3 的結點數分別為 N1、N²和 N3，則⼆叉樹 B 的根結點的左⼦樹的結點數為N1-1
對含有（1）個結點的⾮空⼆叉樹，采⽤任何⼀種遍歷⽅式，其結點訪問序列均相同
⼀棵深度為 h 的滿 k 叉樹有如下性質： 第 h 層上的結點都是葉⼦結點，其餘各層上的結點都有 k 棵⾮空⼦樹.如果按層次順序從 1 開始對全部結點編號，則各層上的結點數⽬是ki-1
實現任意⼆叉樹，m 個樹葉，⼀共 n 個結點，度為 1 的結點 t 個，度為 2 的結點有 p 個，則m=p+1
對於⼀棵具有 n 個結點的⼆叉樹，當進⾏鏈接存儲時，其⼆叉鏈表中的指針域的總數為 2n,其中（n-1）個⽤於鏈接孩⼦結點，（n+1）個空閑著
設深度為 k 的⼆叉樹上只有度為 0和度為 2的節點，則這類⼆叉樹上所含結點總數最少2k-1
二叉樹共有5種不同的形態
具有 3 個結點的⼆叉樹共有（5）種狀態.
設某棵⼆叉樹中只有度數為 0 和度數為 2的結點且度數為 0 的結點數為 n，則這棵⼆叉中共有（2n-1）個結點
在⼀棵⼆叉樹中，度為 0 的結點個數為 n0，度為 2 的結點個數為 n²，則 n=n2+1
葉子結點
設某棵完全⼆叉樹中有 100 個結點，則該⼆叉樹中有(50)個葉⼦結點
設某棵⼆叉樹的⾼度為 10，則該⼆叉樹上葉⼦結點最多有512
某哈夫曼樹中有 199 個結點，則該哈夫曼樹中有（100）個葉⼦結點//（n+1）/2
指針域
設⼀棵 m 叉樹的結點數為 n，⽤多重鏈表表示其存儲結構，則該樹中有（n(m-1)+1）個空指針域
設哈夫曼樹中的葉⼦結點總數為m，若⽤⼆叉鏈表作為存儲結構，則該哈夫曼樹中總共有（2m）個空指針
域.
N 個結點鏈接存儲，指針域總數 2n，鏈接孩⼦結點 2n，空閑的有 n+1
高度
對於⼀個具有 n 個結點的⼆叉樹，當它為（完全二叉樹）具有最⼩⾼度
具有 n(n>0)個結點的完全⼆叉樹的⾼度為[log 2 (n+1)]或[log 2 n]+1
對於⼀個具有 n 個結點的⼆叉樹，當它為⼀棵（單分支）⼆叉樹時具有最⼤⾼度.
對於⼀個具有 n 個結點的⼆叉樹，當它為單分⽀⼆叉樹時具有最⼤⾼度，其⾼度為n
帶權路徑長度
左孩子、右孩子、雙親結點
將含有 83 個結點的完全⼆叉樹從根結點開始編號，根為 1 號，後⾯按從上到下、從左到右的順序對結
點編號，那麼編號為 41 的雙親結點編號為20
三叉樹
在三叉鏈表上，⼆叉樹的求雙親運算很容易實現（F）
欲實現任意⼆叉樹的後序遍歷的⾮遞歸演算法⼆不必使⽤棧結構，最佳⽅案是⼆叉樹采⽤(三叉鏈表)存儲結構.
在⼀棵具有 k 層的滿三叉樹中，結點總數為(3k-1)/2
⼀棵三叉樹的結點數為 50，則它的最⼩⾼度為5
哈夫曼樹
設⽤於通訊的電⽂僅由 8個字⺟組成，字⺟在電⽂中出現的頻率分別為
根據這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的⾼度為7
先序、中序、後序遍歷
前序：第⼀個結點 A 是根結點，是後序的最後⼀個結點
前序：⼦樹的第⼀個結點為⼦樹根結點
中序：根據前序的根節點，判斷是否有左右⼦樹。
中序:左⼦樹–> 根節點–> 右⼦樹
後序:左⼦樹–> 右⼦樹–>根節點
先序: 根節點–>左⼦樹–>右⼦樹
⼆叉樹的先序遍歷序列和後序遍歷序列正好相反，則該⼆叉樹滿⾜的條件是任⼀結點⽆右孩⼦
⼆叉樹的先序遍歷序列和後序遍歷序列正好相同，則該⼆叉樹滿⾜的條件是空或只有⼀個結點
⼆叉樹的先序遍歷序列和中序遍歷序列正好相同，則該⼆叉樹滿⾜的條件是任⼀結點⽆左孩⼦
已知⼆叉樹的前序遍歷和後序遍歷序列並不能惟⼀地確定這棵樹，因為不知道樹的根結點是哪⼀個。（F）
任何⼀棵⼆叉樹的葉結點在其先根、中根、後跟遍歷序列中的相對位置肯定不發生變化
任何⼀棵⼆叉樹的葉結點在先序、中序和後序遍歷序列中的相對次序不發生改變
⼆叉樹結點的先根序列、中根序列和後根序列中，所有葉⼦結點的先後順序完全相同
⼆叉樹中，具有兩個⼦⼥的⽗結點，在中序遍歷序列中，它的後繼結點最多只能有⼀個⼦⼥結點
由⼆叉樹的前序和後序遍歷序列（不能）惟⼀確定這棵⼆叉樹
設 a，b 為⼀棵⼆叉樹上的兩個結點，在中序遍歷時，a 在 b 前的條件是.a 在 b 左⽅
⼀棵⼆叉樹滿⾜下列條件：對任意結點，若存在左、右⼦樹，則其值都⼩於它的左⼦樹上所有結點的值，⽽⼤於右⼦樹上所有結點的值.現采⽤（中根）遍歷⽅式就可以得到這棵⼆叉樹所有結點的遞增序列
⼀棵⼆叉樹有 n 個結點，要按某順序對該⼆叉樹中的結點編號，（號碼為 1-n），編號須具有如下性質：
⼆叉樹中任⼀結點 V，其編號等於其左⼦樹中結點的最⼤編號加 1.⽽其右⼦樹中結點的最⼩編號等於 V 的編號加 1.試問應按（中序）遍歷順序編號
在⼆叉鏈表上，求雙親運算的時間性能很好（F）
⼆叉判定樹應用在：描述分類過程和處理判定優化等⽅⾯上
後綴表達式
24. 圖
設 G1=(V1,E1)和 G2=(V2,E2)為兩個圖，如果 V1ÍV2,E1ÍE2 則稱.G1是 G2 的⼦圖
有向圖
某有向圖中有 n 個頂點，則該有向圖對應的鄰接表中有（n）個表頭結點
對於⼀個有向圖，若⼀個頂點的度為 k1，出度為 k2,則對應逆鄰接表中該頂點單鏈表中的邊結點數為k1-k2
圖的逆鄰接表存儲結構只適⽤於（有向圖）圖
在⼀個具有 n 個頂點的有向圖中，若所有頂點的出度數之和為 s，則所有頂點的度數之和為2s
在⼀個具有 n 個頂點的有向圖中，若所有頂點的出度數之和為 s，則所有頂點的⼊度數之和為s
在⼀個具有 n 個頂點的有向完全圖中，所含的邊數為n(n-1)
有 8 個結點的有向完全圖最多有（56）條邊，因為n(n-1)
無向圖
設⽆向圖 G 中有 n 個頂點 e 條邊，則⽤⽤鄰接表作為圖的存儲結構進⾏深度優先或⼴度優先遍歷的時間複雜度為O(n+e)
設⽆向圖 G 中有 n 個頂點 e 條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為n和2e
設某有向圖的鄰接表中有 n 個表頭結點和 m 個表結點，則該圖中有（m）條有向邊
設⽆向圖 G 中有 n 個頂點 e 條邊，則⽤鄰接矩陣作為圖的存儲結構進⾏⼴度優先遍歷時的時間複雜度為O(n2)
如果 n 個頂點的圖是⼀個環，則它有(n)棵⽣成樹
設⽆向圖G中有n個頂點e條邊，則⽤鄰接表作為圖的存儲結構進⾏深度優先遍歷時的時間複雜度為O(n2)
圖中的⼀條路徑⻓度為 k，該路徑所含的頂點數為k+1
當 n 個頂點的⽆向圖 G 的頂點度數的最⼩值⼤於或者等於(n)時，G ⾄少有⼀條迴路
在含 n 個頂點和 e 條邊的⽆向圖的鄰接矩陣中,零元素的個數為n2-2e
對於⼀個具有 n 個頂點和 e 條邊的⽆向圖，若采⽤鄰接表表示，則表頭數量為n
對於⼀個具有 n 個頂點和 e 條邊的⽆向圖，若采⽤鄰接表表示，則所有鄰接表中的結點總數是2e
⼀個⽆向圖有 n 個頂點和 e 條邊，則所有頂點的度的和為（2e）
一個無向圖有 n 個頂點和e 條邊，則該⽆向圖中所有頂點的⼊度之和為2e
在⼀個具有 n 個頂點和 e 條邊的⽆向圖的鄰接矩陣中，表示邊存在的元素（⼜稱為有效元素）的個數為2e
假設⼀個有n個頂點和e條弧的有向圖⽤鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間複雜度是O(n+e)
在⼀個具有 n 個頂點的⽆向圖中，要連通全部頂點⾄少需要（n-1）條邊.
設⽆向圖 G 中有 n 個頂點，則該⽆向圖的最⼩⽣成樹上有（n-1）條邊
⼀個具有 n 個頂點的有向圖最多有（n(n-1)）條邊
⼀個具有 n 個頂點的⽆向完全圖的邊數為n(n-1)/2
設某⽆向圖中有 n 個頂點 e 條邊，則建⽴該圖鄰接表的時間複雜度為O(n+e)
設⽆向圖 G（如下圖所示），則其最⼩⽣成樹上所有邊的權值之和為8
在⽆向圖中定義頂點 vi 與 vj 之間的路徑為從 vi 到 vj 的⼀個頂點序列
路徑長度
⽤ Dijkstra 演算法求某⼀頂點到其餘各頂點間的最短路徑是按路徑⻓度（遞增）的次序來得到最短路徑的
關鍵路徑是事件結點⽹絡中的從源點到匯點的最⻓路徑
鄰接表
鄰接表是圖的⼀種鏈式存儲
連通圖
n 個頂點的連通圖⾄少（n-1）條邊
具有 6 個頂點的⽆向圖⾄少應有（5）條邊才能確保是⼀個連通圖
在⼀個連通圖中存在著（1）個連通分量
設某強連通圖中有 n 個頂點，則該強連通圖中⾄少有（n）條邊
具有 50 個頂點的⽆向圖⾄少應有（49）條邊才能確保是⼀個連通圖
對於⼀個具有 n 個頂點的⽆向連通圖，它包含的連通分量的個數為1
如果從⽆向圖的任⼀頂點出發進⾏⼀次深度優先搜索即可訪問所有頂點，則該圖⼀定是連通圖
任何⼀個⽆向連通圖的最⼩⽣成樹有一棵或多棵
廣度優先遍歷和深度優先遍歷
⼴度優先遍歷類似於⼆叉樹的層次遍歷
若⼀個圖的邊集為{（A,B）,(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點 A 開始對該圖進⾏深度優先搜索，得到的頂點序列可能為A,C,F,D,E,B
已知圖的鄰接矩陣同下圖所示，根據演算法，則從頂點 0 出發，按⼴度優先遍歷的結點序列是0 1 2 3 4 6 5
已知圖的鄰接表如下所示，根據演算法，則從頂點 0 出發按⼴度優先遍歷的結點序列是 0 3 2 1
已知圖的鄰接表如下所示，根據演算法，則從頂點 0 出發按深度優先遍歷的結點序列是 0 1 2 3
圖的邊集
⼀個圖的邊集為{<0,1>3,<0,2>5,<0,3>5,<0,4>10,<1,2>4,<2,4>2,<3,4>6},則從頂點 v0到頂點 v4共有（4）條簡單路徑
若⼀個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},則從頂點 1開始對該圖進⾏⼴度優先搜索，得到的頂點序列可能為1,2,4,5,3
拓撲排序
拓撲排序：可以判斷出⼀個有向圖中是否有環（迴路）
任⼀個有向圖的拓撲序列有一個或多個
稠密圖、稀疏圖（普里姆和克魯斯卡爾）
⽤普⾥姆(Prim)演算法求具有 n 個頂點 e 條邊的圖的最⼩⽣成樹的時間複雜度為n2
若要求⼀個稠密圖 G 的最⼩⽣成樹，最好⽤(普里姆) 演算法來求解.
若要求⼀個稀疏圖 G 的最⼩⽣成樹，最好⽤(克魯斯卡爾) 演算法來求解.
設有⼀稠密圖 G，則 G 采⽤（矩陣）存儲較省空間.
設有⼀稀疏圖 G，則 G 采⽤（表）存儲較省空間
領接矩陣
⽆向圖的鄰接矩陣是⼀個對稱矩陣
已知⼀個圖的鄰接矩陣表示，計算第 i 個結點的⼊度的⽅法是：求矩陣第 i 列⾮零元素之和
已知⼀個圖的鄰接矩陣表示，刪除所有從第 i 個結點出發的邊的⽅法是：將矩陣第 i ⾏全部置為 0
帶權有向圖 G ⽤鄰接矩陣 A 存儲，則頂點 i 的⼊度等於 A 中第 i 列⾮⽆窮的元素個數之和
深度優先遍歷類似於⼆叉樹的先序遍歷
圖的深度優先遍歷序列不唯一
⽤鄰接表表示圖進⾏深度優先遍歷時，通常是采⽤(棧)來實現演算法的
⽤鄰接表表示圖進⾏⼴度優先遍歷時，通常是采⽤(隊列)來實現演算法的.
對於具有 n 個頂點的圖，若采⽤鄰接矩陣表示，則該矩陣的⼤⼩為n2
有向圖 G ⽤鄰接矩陣存儲，其第 i ⾏的所有元素之和等於頂點 i 的出度
拓撲排序演算法是通過重複選擇具有(0)個前驅頂點的過程來完成的。//拓撲à沒有前驅的
圖遍歷
⾮連通圖不能⽤深度優先搜索法（F）
頂點與邊
在⼀個圖中，所有頂點的度數之和=所有邊數
設某完全⽆向圖中有 n 個頂點，則該完全⽆向圖中有(n（n-1）)/2條邊
25. 排序
大多數排序演算法都有兩個基本的操作：比較和移動
設需要對 10個不同的記錄關鍵字進⾏排序，則⾄少需要⽐較（9）次
排序的⽬的是為了以後對已排序的數據元數進⾏（查找）操作
直接插⼊排序和冒泡排序的時間複雜性為 O（n²）, 若初始數據有序（即正序），則時間複雜性為O（n）
初始值
選擇排序/簡單選擇排序/直接選擇排序
在直接插⼊和直接選擇排序中，若初始數據基本反序，則選⽤直接選擇排序
在所有的排序⽅法中，關鍵字的⽐較次數與記錄的初始排列⽆關的是直接選擇排序
對⼀個由 n 個整數組成的序列，藉助排序過程找出其中的最⼤值，希望⽐較次數和移動次數最少，應選
⽤（直接選擇排序）
關鍵字的⽐較次數與記錄的初始排列⽆關
在直接選擇排序中，記錄⽐較次數為 O（n²）數量級，記錄的移動次數為O(n)數量級.
將上萬個⼀組⽆序並且互不相等的正整數序列，存放於順序存儲結構中，采⽤（選擇排序）⽅法能夠最快地找出其中最⼤的正整數
⽬前以⽐較操作為基礎的內部排序的時間複雜性 T(m）的範圍是 O（nlog2n）～ O（n²），其⽐較次數
與待排序記錄的初始狀態⽆關的是(直接選擇)排序
排序⽅法中，從未排序序列中挑選元素，並將其依次放⼊已排序序列（初始時為空）的⼀端的⽅法，稱
為選擇排序
插入排序/直接插入排序
對 n 個元素進⾏直接插⼊排序時間複雜性為n2
設⼀組初始記錄關鍵字的⻓度為 8，則最多經過（7）趟插⼊排序可以得到有序序列.
在對 n 個元素進⾏直接插⼊排序的過程中，共需要進⾏（n-1）趟.
當初始序列已按健值有序時，⽤直接插⼊演算法進⾏排序，需要⽐較的次數為n-1
直接插⼊排序演算法的平均時間複雜度為O(n²)
排序⽅法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進⾏⽐較，將其放⼊
已排序序列的正確位置上的⽅法，稱為插入排序
對於直接插⼊排序、冒泡排序、簡單選擇排序、堆排序、快速排序，當⽂件「局部有序」或⽂件⻓度較⼩
的情況下，最佳的內部排序⽅法是直接插入排序
冒泡排序
對 n 個元素的序列進⾏冒泡排序，在降序的情況下⽐較次數最多，其⽐較次數為(n(n-1))/2
對 n 個元素的序列進⾏冒泡排序，最少的⽐較次數是 n，此時元素的排列情況是已從⼩到⼤排列
對 n 個元素的序列進⾏冒泡排序，最少的⽐較次數是 n，此時元素的排列情況是升序
對 n 個元素的序列進⾏冒泡排序，其⽐較次數為 n（n-1）/2時，其原始數據序列是（降序）情況
對ｎ個不同的排序碼進⾏升序冒泡法排列，從⼤到⼩排列好的⽐較的次數最多
對ｎ個不同的排序碼進⾏冒泡排序，在元素⽆序的情況下⽐較的次數為(n(n-1))/2
排序時掃描待排序記錄序列，順次⽐較相鄰的兩個元素的⼤⼩，逆序時就交換位置，這是冒泡排序的基
本思想
對 n 個元素的序列進⾏冒泡排序，在（降序）的情況下⽐較次數最多
對 n 個元素的序列進⾏冒泡排序，最少的⽐較次數是n-1
在對⼀組有 8 個記錄的數據表進⾏冒泡排序時，在整個排序過程中共需進⾏(7)趟才可完成.
在⽂件局部有序或⽂件⻓度較⼩的情況下，最佳的排序⽅法是冒泡排序
快速排序
快速排序是對序列中的元素通過適當的位置交換將有關元素⼀次性地放置在其最終位置上
最壞的情況下的時間複雜度是O(n²)
在最壞情況下（如初始記錄已有序），快速排序的空間複雜性為n
在對 n 個元素進⾏快速排序的過程中，最好情況下需要進⾏（log 2 n）趟
快速排序在（被排序的數據已基本有序）情況下最不利於發揮其⻓處.
在堆排序，快速排序和歸併排序中，若從平均情況下排序最快，則應⾸先選取（快速排序）⽅法
在堆排序中、快速排序和歸併排序中，若從節省存儲空間考慮，排在中間的是（快速排序）⽅法
每次把待排序的元素劃分為左、右兩個⼦區間，其中左區間中元素的關鍵字均⼩於等於基準元素的關鍵字，右區間中元素的關鍵字均⼤於等於基準元素的關鍵字，則此排序⽅法叫作快速排序
快速排序演算法的平均時間複雜度為O(nlog 2 n)
歸併排序
依次將每兩個相鄰的有序表合併成⼀個有序表的排序⽅法叫作歸併排序
在歸併排序過程中，需歸併的趟數為log2n
若對 n 個元素進⾏歸併排序，則進⾏每⼀趟歸併的時間複雜度為n
⼆路歸併排序的時間複雜度為(nlog2n)
在歸併排序中，歸併趟數的數量級表示為O（log2n)
在內部排序中，要求附加的記憶體容量最⼤的是歸併排序
設⼀組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有 5個⻓度為 2 的有序⼦表，則⽤歸併排序的⽅法對該記錄關鍵字序列進⾏⼀趟歸併後的結果為15，25，35，50，20，40，80，85，36，70
在歸併排序中，若待排序記錄的個數為 20，則共需要進⾏ 5趟歸併，在第 3趟歸併中，是把⻓度為 4 的
有序表歸併為⻓度為4的有序表
希爾排序
設⼀組初始記錄關鍵字序列為(9，8，7，6，5，4，3，2，1，0)，則以增量 d=5 的⼀趟希爾排序結束後前 5條記錄關鍵字為4，3，2，1，0
⼀趟排序結束後不⼀定能夠選出⼀個元素放在其最終位置上的是希爾排序
希爾排序的增量序列必須是遞減
堆排序
在堆排序中、快速排序和歸併排序中，若只從最壞的情況下排序最快並且要節省記憶體考慮，應選⽤（堆排序）
時間複雜度不受數據初始狀態影響⽽恆為 O(nlog2n)的是堆排序
在任何情況下，時間複雜度均為 O(nlog2n)的不穩定的排序⽅法是堆排序
已知⼀個鏈表中有 3000 個結點，每個結點存放⼀個整數，（堆排序方法）可⽤於解決這 3000個整數的排序問題且不需要對演算法作⼤的變動
設有 1000 個⽆序的元素，希望⽤最快的速度挑選出其中前 10 個最⼤的元素，最好選⽤（堆）排序法
交換排序
當兩個元素⽐較出現反序時（即逆序）就相互交換位置的排序⽅法叫作交換排序
基數排序
如果將所有中國⼈按照⽣⽇來排序，則使⽤（基數排序）演算法最快
比較排序的穩定和快慢
時間複雜度
關鍵字序列
26. 查找
二分查找
線性： 線性（1:1）、棧、隊、數組
非線性：樹形（1：多）、圖形（多：多）
存儲結構：順序（數組）、鏈式（指針）
2. 邏輯結構與元素相對位置無關
鏈式存儲物理地址和邏輯地址不一定相同連續，所以它記憶體中可⽤存儲單元的地址/數據結點地址：連續與否都可以
3. （解釋）不生成可執行文件
4. 讀取元素花費時間最少：順序表
5. 在具有 n 個結點的單鏈表上查找值為 x 的元素時，其時間複雜度為O（n）
6. 設指針 q 指向單鏈表中結點 A，指針 p 指向單鏈表中結點 A 的後繼結點 B，指針 s 指向被插⼊的結點 X，則在結點 A 和結點 B 插⼊結點 X 的操作序列為:q->next=s;s->next=p;
7. 訪問第 i 個元素的前驅（1<i<=n）的時間複雜度為O（1）
8. 添加/刪除操作
單鏈表
帶頭結點的單鏈表
帶頭結點的雙循環單鏈表
單鏈表的頭插法建立鏈表
單鏈表的頭插法建⽴鏈表所得到的數據的順序與輸⼊的時候的順序相反
單鏈表的頭插法建⽴鏈表演算法不簡單，要引⼊⼤量的指針輔助運算。（F）
單鏈表的尾插發建立鏈表
單鏈表的尾插法建⽴鏈表所得到的數據的順序與輸⼊的時候的順序相同
雙鏈表
帶頭結點的雙循環鏈表
鏈式存儲的後插法
帶頭結點的雙循環鏈表的空表
9. 3n+nlog2n+n2+8的數量級：n2
10. 演算法的評價不包括並行性
11. 集合中任何兩個結點之間都有邏輯關係但組織形式鬆散（F）
12. 數據元素具有相同的特性=數據項個數相同，類型一致
13. 數據在電腦存儲器內表示時，物理地址與邏輯地址相同並且是連續的，稱之為順序存儲結構
14. 演算法
定義：有限序列
目的：分析效率求改進
15. 高效性：指演算法的執行效率高（T）
指演算法需要的時間性能（F）
16. 鏈表
Malloc（）申請
Free（）釋放
在⼀個帶頭結點的雙向循環鏈表中，若要在 p 所指向的結點之前插⼊⼀個新結點，則需要相繼修改（4）個指針域的值
1、該新結點前驅指針指向p的前驅
2、p的前驅指針指向該新結點
3、該新結點的後繼域指向p結點
4、前驅的後繼域指向該新結點
17. 線性表
在進⾏添加/刪除元素時，應該在刪除元素前判空
在添加元素前判空（F）
可以在任何位置插入刪除
除第⼀個和最後⼀個元素外，其餘每個元素都由⼀個且僅有⼀個直接前驅和直接後繼
元素之間的邏輯關係是通過（物理位置）決定的.
有限序列，可以為空
串是⼀種特殊的線性表
兩種存儲結構：線性和鏈式
線性錶鏈式
線性錶鏈式：插入刪除方便，只需要向前或向後移動元素即可（F）
線性表鏈接存儲：
鏈表是⼀種動態存儲結構，鏈表的結點可調⽤申請 malloc()和 free()釋放
鏈表的結點可⽤free()申請和⽤malloc()釋放（F）
鏈表是⾮隨機存取存儲結構，對鏈表的存取必須從頭指針開始
對鏈表的存取可以從任何結點開始（F）
插⼊刪除運算⾮常⽅便；只需修改相應指針值
只需要向前或向後移動元素即可（F）
邏輯上相鄰的元素，其物理位置⼀定相鄰，元素之間的鄰接關係由指針域指示
不需要預先分配存儲空間，適用於數據量變化較大的情況
表的長度：數據結點的個數
適用於經常進行插入和刪除的操作
鏈接存儲的存儲結構所佔存儲空間分兩部分，⼀部分存放結點值，另⼀部分存放表示結點間關係的指針
線性表順序存儲
不便於插入和刪除的實現，而鏈式存儲便於
適用於變化量小的情況
必須按最⼤可能⻓度預分存儲空間，存儲空間利⽤率低，表的容量難以擴充,是⼀種靜態存儲結構
是一種隨機存取結構
適用於經常進行存取的操作
刪除時的最壞情況：要刪除的元素是順序表的第一個元素
刪除時的最好情況：要刪除的元素是順序表的最後一個元素
要求能夠較快的插⼊和刪除，⼜要求儲存結構能夠反映數據元素之間的邏輯關係則應該以順序儲存⽅式儲存
在⼀個⻓度為 n 的順序存儲的線性表中，向第 i 個元素(1<=i<=n+1)位置插⼊⼀個新元素時，需要從後向前依次後移（n-i+1）個元素
線性表一旦建立，就不能添加元素（F）
最後一個元素之後插入一個元素和刪除最後一個元素，採用容量足夠大的順序表
長度為n，刪除第i個元素，要向前移動n-1個元素
長度為n，第i個位置插入一個新元素，時間複雜度為O（n）
線性表是n個數據元素的有限序列(所以學院組織結構表就不是線性表)
順序線性表中有 n 個數據元素，則刪除表中第 i 個元素需要移動（n-1）個元素
18. 順序表
做刪除操作時，應該將表的長度-1
插⼊⼀個元素所需移動的元素平均數是（n+1）/2
順序表的⻓度是指：表中數據元素的個數
向⼀個有 127 個元素的順序表中插⼊⼀個新元素並保持原來順序不變，平均要移動(63.5)個元素
在⼀個⻓度為 n 的順序表中，刪除值為 x 的元素時需要⽐較元素和移動元素的總次數為n
表尾插⼊⼀個元素的時間複雜性的量級為O(1)
19. 數組
邏輯結構à線性結構
存儲結構à順序結構
設⼀維數組中有 n 個數組元素，則讀取值為 x 的數據元素的平均時間複雜度為O(n)
設⼀維數組中有 n 個數組元素，則讀取第 i 個數組元素的平均時間複雜度為0(1)
假定利⽤數組 a[N]順序存儲⼀個棧，⽤ top 表示棧頂指針，top==-1 表示棧空，並已知棧未滿，當元素 x進棧時所執⾏的操作為a[++top]= x
在⼀個具有 n 個單元的順序棧中，假定以地址低端（即 0 單元）作為棧底，以 top 作為棧頂指針，則當做出棧處理時，top 變化為top—
20. 隊列
先進先出
只能在隊尾添加/插入新元素
只能在隊首刪除元素
⽆論是順序存儲還是鏈接存儲的棧和隊列，進⾏插⼊或刪除運算的時間複雜性均為O(1)
利⽤順序隊進⾏元素⼊隊時最⼤的問題是會出現假溢出現象
隊列是被限定為只能在表的⼀端進⾏插⼊運算，在表的另⼀端進⾏刪除運算的線性表
當利⽤⼤⼩為 N 的數組存儲循環隊列時，該隊列的最⼤⻓度是n
從⼀個順序循環隊列中刪除元素時，⾸先需要後移隊首指針
判定⼀個隊列 QU（最多元素為 m0）為滿隊列的條件是QU->rear － QU->front = = m0
在⼀個鏈隊列中，front 和 rear 分別為頭指針和尾指針，則插⼊⼀個結點 s 的操作為rear->next=s;rear=s;
在⼀個 n 個結點的雙向鏈表中指針 p 所指向的結點之前插⼊⼀個新結點時，其時間複雜性的量級為O(1)
21. 棧
先進後出，後進先出
只能在棧頂做插入/刪除操作
向順序棧中插⼊新的元素分三步，分別是：判斷溢出或棧滿 修改棧頂指針 把新元素賦給棧頂單元
從順序棧中刪除元素分三步，分別是：判斷棧空 棧頂指針的值返回 修改棧頂指針
向棧中壓⼊元素的操作是：先移動棧頂指針，然後存⼊元素
設⽤鏈表作為棧的存儲結構則退棧操作：必須判別棧是否為空
設⽤鏈表作為棧的存儲結構則進棧操作：對棧不作任何判別
順序棧中在做出棧運算時，應先判別棧是否為空
順序棧中在做進棧運算時，應先判別棧是否為滿
Push進pop出
設棧 S 和隊列 Q 的初始狀態為空，元素 e1,e2,e3,e4,e5,e6依次通過棧 S，⼀個元素出棧後即進⼊隊列 Q，若 6 個元素出隊的序列是 e2,e4,e3,e6,e5,e1，則棧的容量⾄少應該是3
⼀個棧的輸⼊序列為：1,2,3,4，則棧的不可能輸出的序列是4321
印表機à隊列
判定⼀個順序棧 ST（最多元素為 m0）為空的條件是ST->top==0
假定⼀個鏈式棧的棧頂指針⽤ top 表示，每個結點的結構具有兩個域 data 和 next,出棧時進⾏的指針操作為top=top->next
刪除⾮空的順序存儲結構的堆棧的棧頂元素，棧頂指針 top 的變化是top=top-1
向⼀個棧頂指針為 hs 的鏈棧中插⼊⼀個*s 結點時，應執⾏s->next=hs；hs=s；
順序棧中當棧中元素為 m 時，做進棧運算時發⽣上溢，則說明棧的可⽤最⼤容量為m
判定⼀個順序棧的 S(最多元素時 m0)為滿的條件是S->top==m0-1
為了增加記憶體空間的利⽤率和減少發⽣上溢的可能性，由兩個棧共享⼀⽚連續的記憶體空間時，應將兩個
棧的（棧底）分別設在這⽚記憶體空間的兩端，這樣只有當兩個棧的棧頂在棧空間的某⼀位置相遇時才產⽣上溢
設輸⼊序列 1、2、3、…、n 經過棧作⽤後，輸出序列中的第⼀個元素是 n，則輸出序列中的第 i 個輸出元素是n+1-i
判定⼀個順序棧 S（棧空間⼤⼩為 n）為空的條件是S->top==0
設輸⼊序列為 1、2、3、4、5、6，則通過棧的作⽤後可以得到的輸出序列為：3，2，5，6，4，1
設指針變數 front 表示鏈式隊列的隊頭指針，指針變數 rear 表示鏈式隊列的隊尾指針，指針變數 s 指向將要⼊隊列的結點 X，則⼊隊列的操作序列為rear->next=s；rear=s；
解決順序隊上溢的⽅法
1、每當刪除⼀個隊頭元素時,則依次移動隊中的元素,始終使 front 指針指向隊列中的第⼀個位置
2、采⽤平移元素的⽅法:每當隊列中加⼊⼀個元素時,隊列中已有的元素向隊頭移動⼀個位置
3、建⽴⼀個⾜夠⼤的存儲空間,但這樣做會造成空間的使⽤效率降低
4、發⽣上溢時，⾃動丟失多餘元素(F)
22. 單鏈表
已知單鏈表尾指針，時間複雜度為O(1)
單鏈表中設置頭結點：空表和非空表統一，演算法處理一致
⾮空的循環單鏈表 head 的尾結點（由 p 所指向），滿⾜條件：p->next==head
將⻓度為 n 的單鏈錶鏈接在⻓度為 m 的單鏈表之後的演算法的時間複雜度為O(m)
⼀個單鏈表中，若刪除 p 所指向結點的後續結點(=單鏈表中指針 p 指向結點 m，若要刪除 m 之後的結點（若存在），則需要修改指針的操作為)，則執⾏p->next=p->next->next;
在⼀單鏈表中 n 個數據結點，則讀第 i 個數據結點的平均時間複雜度為O（n）
對於⼀個具有 n 個結點的單鏈表，在已知的結點*p 後插⼊⼀個新結點的時間複雜性為O(1)
單鏈表的判空條件
不帶頭結點的單鏈表head為空：head=null
⼀條單鏈表的頭指針變數為 head 且該鏈表沒有頭結點，判空：head=0
23. 樹
樹à層次
二叉樹不是特殊的樹，使用不是樹轉化過來的特殊情形
⼆叉樹與樹具有相同的樹形結構（F）
二叉樹是非線性數據結構，順序存儲結構和鏈式存儲結構都能存儲，但，不是所有的⼆叉樹樹形結構都適⽤順序存儲結構
若初始森林中共有 n 裸⼆叉樹，進⾏ 2n-1 次合併後才能剩下⼀棵最終的哈夫曼樹（F）
若⽬標串的⻓度為 n，模式串的⻓度為[n/3]，則執⾏模式匹配演算法時，在最壞情況下的時間複雜度是O(n2)
分支
設⾮空⼆叉樹上葉⼦節點數為 n0，雙分⽀數為 n²，單分⽀數為 n1，則n0=n2+1
深度
深度為 k 的完全⼆叉樹中最少有（2k-1）個結點
設⼀棵完全⼆叉樹中有 65個結點，則該完全⼆叉樹的深度為7，因為2n-1
設⼆叉樹有 n 個結點，則其深度無法確定
結點數
⼆叉樹的第 k 層的結點數最多為2k-1
⼀棵⼆叉樹上第 5 層的結點數最多為16個，因為2k-1
深度為 5 的⼆叉樹最少有(5)個結點
如果 T2是由有序樹 T 轉化⽽來的⼆叉樹，T後序結點=T2中序結點，T前序結點=T2前序結點
設某棵⼆叉樹中有 2000 個結點，則該⼆叉樹的最⼩⾼度為11，因為210=1024<2000，211=2048>2000
在⼀棵樹中，每個結點最多有（1）個前驅結點
⼆叉樹中第 i(i≥1)層上的結點數最多有（2i+1）個
利⽤ n 個值⽣成的哈夫曼樹中共有（2n-1）個結點.
設⼆叉樹根結點的層次為 0，⼀棵⾼度為 h 的滿⼆叉樹中的結點個數是2n+1-1
設 F 是由 T1、T2 和 T3三棵樹組成的森林，與 F 對應的⼆叉樹為 B，T1、T2 和 T3 的結點數分別為 N1、N²和 N3，則⼆叉樹 B 的根結點的左⼦樹的結點數為N1-1
對含有（1）個結點的⾮空⼆叉樹，采⽤任何⼀種遍歷⽅式，其結點訪問序列均相同
⼀棵深度為 h 的滿 k 叉樹有如下性質： 第 h 層上的結點都是葉⼦結點，其餘各層上的結點都有 k 棵⾮空⼦樹.如果按層次順序從 1 開始對全部結點編號，則各層上的結點數⽬是ki-1
實現任意⼆叉樹，m 個樹葉，⼀共 n 個結點，度為 1 的結點 t 個，度為 2 的結點有 p 個，則m=p+1
對於⼀棵具有 n 個結點的⼆叉樹，當進⾏鏈接存儲時，其⼆叉鏈表中的指針域的總數為 2n,其中（n-1）個⽤於鏈接孩⼦結點，（n+1）個空閑著
設深度為 k 的⼆叉樹上只有度為 0和度為 2的節點，則這類⼆叉樹上所含結點總數最少2k-1
二叉樹共有5種不同的形態
具有 3 個結點的⼆叉樹共有（5）種狀態.
設某棵⼆叉樹中只有度數為 0 和度數為 2的結點且度數為 0 的結點數為 n，則這棵⼆叉中共有（2n-1）個結點
在⼀棵⼆叉樹中，度為 0 的結點個數為 n0，度為 2 的結點個數為 n²，則 n=n2+1
葉子結點
設某棵完全⼆叉樹中有 100 個結點，則該⼆叉樹中有(50)個葉⼦結點
設某棵⼆叉樹的⾼度為 10，則該⼆叉樹上葉⼦結點最多有512
某哈夫曼樹中有 199 個結點，則該哈夫曼樹中有（100）個葉⼦結點//（n+1）/2
指針域
設⼀棵 m 叉樹的結點數為 n，⽤多重鏈表表示其存儲結構，則該樹中有（n(m-1)+1）個空指針域
設哈夫曼樹中的葉⼦結點總數為m，若⽤⼆叉鏈表作為存儲結構，則該哈夫曼樹中總共有（2m）個空指針
域.
N 個結點鏈接存儲，指針域總數 2n，鏈接孩⼦結點 2n，空閑的有 n+1
高度
對於⼀個具有 n 個結點的⼆叉樹，當它為（完全二叉樹）具有最⼩⾼度
具有 n(n>0)個結點的完全⼆叉樹的⾼度為[log 2 (n+1)]或[log 2 n]+1
對於⼀個具有 n 個結點的⼆叉樹，當它為⼀棵（單分支）⼆叉樹時具有最⼤⾼度.
對於⼀個具有 n 個結點的⼆叉樹，當它為單分⽀⼆叉樹時具有最⼤⾼度，其⾼度為n
帶權路徑長度
左孩子、右孩子、雙親結點
將含有 83 個結點的完全⼆叉樹從根結點開始編號，根為 1 號，後⾯按從上到下、從左到右的順序對結
點編號，那麼編號為 41 的雙親結點編號為20
三叉樹
在三叉鏈表上，⼆叉樹的求雙親運算很容易實現（F）
欲實現任意⼆叉樹的後序遍歷的⾮遞歸演算法⼆不必使⽤棧結構，最佳⽅案是⼆叉樹采⽤(三叉鏈表)存儲結構.
在⼀棵具有 k 層的滿三叉樹中，結點總數為(3k-1)/2
⼀棵三叉樹的結點數為 50，則它的最⼩⾼度為5
哈夫曼樹
設⽤於通訊的電⽂僅由 8個字⺟組成，字⺟在電⽂中出現的頻率分別為
根據這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的⾼度為7
先序、中序、後序遍歷
前序：第⼀個結點 A 是根結點，是後序的最後⼀個結點
前序：⼦樹的第⼀個結點為⼦樹根結點
中序：根據前序的根節點，判斷是否有左右⼦樹。
中序:左⼦樹–> 根節點–> 右⼦樹
後序:左⼦樹–> 右⼦樹–>根節點
先序: 根節點–>左⼦樹–>右⼦樹
⼆叉樹的先序遍歷序列和後序遍歷序列正好相反，則該⼆叉樹滿⾜的條件是任⼀結點⽆右孩⼦
⼆叉樹的先序遍歷序列和後序遍歷序列正好相同，則該⼆叉樹滿⾜的條件是空或只有⼀個結點
⼆叉樹的先序遍歷序列和中序遍歷序列正好相同，則該⼆叉樹滿⾜的條件是任⼀結點⽆左孩⼦
已知⼆叉樹的前序遍歷和後序遍歷序列並不能惟⼀地確定這棵樹，因為不知道樹的根結點是哪⼀個。（F）
任何⼀棵⼆叉樹的葉結點在其先根、中根、後跟遍歷序列中的相對位置肯定不發生變化
任何⼀棵⼆叉樹的葉結點在先序、中序和後序遍歷序列中的相對次序不發生改變
⼆叉樹結點的先根序列、中根序列和後根序列中，所有葉⼦結點的先後順序完全相同
⼆叉樹中，具有兩個⼦⼥的⽗結點，在中序遍歷序列中，它的後繼結點最多只能有⼀個⼦⼥結點
由⼆叉樹的前序和後序遍歷序列（不能）惟⼀確定這棵⼆叉樹
設 a，b 為⼀棵⼆叉樹上的兩個結點，在中序遍歷時，a 在 b 前的條件是.a 在 b 左⽅
⼀棵⼆叉樹滿⾜下列條件：對任意結點，若存在左、右⼦樹，則其值都⼩於它的左⼦樹上所有結點的值，⽽⼤於右⼦樹上所有結點的值.現采⽤（中根）遍歷⽅式就可以得到這棵⼆叉樹所有結點的遞增序列
⼀棵⼆叉樹有 n 個結點，要按某順序對該⼆叉樹中的結點編號，（號碼為 1-n），編號須具有如下性質：
⼆叉樹中任⼀結點 V，其編號等於其左⼦樹中結點的最⼤編號加 1.⽽其右⼦樹中結點的最⼩編號等於 V 的編號加 1.試問應按（中序）遍歷順序編號
在⼆叉鏈表上，求雙親運算的時間性能很好（F）
⼆叉判定樹應用在：描述分類過程和處理判定優化等⽅⾯上
後綴表達式
24. 圖
設 G1=(V1,E1)和 G2=(V2,E2)為兩個圖，如果 V1ÍV2,E1ÍE2 則稱.G1是 G2 的⼦圖
有向圖
某有向圖中有 n 個頂點，則該有向圖對應的鄰接表中有（n）個表頭結點
對於⼀個有向圖，若⼀個頂點的度為 k1，出度為 k2,則對應逆鄰接表中該頂點單鏈表中的邊結點數為k1-k2
圖的逆鄰接表存儲結構只適⽤於（有向圖）圖
在⼀個具有 n 個頂點的有向圖中，若所有頂點的出度數之和為 s，則所有頂點的度數之和為2s
在⼀個具有 n 個頂點的有向圖中，若所有頂點的出度數之和為 s，則所有頂點的⼊度數之和為s
在⼀個具有 n 個頂點的有向完全圖中，所含的邊數為n(n-1)
有 8 個結點的有向完全圖最多有（56）條邊，因為n(n-1)
無向圖
設⽆向圖 G 中有 n 個頂點 e 條邊，則⽤⽤鄰接表作為圖的存儲結構進⾏深度優先或⼴度優先遍歷的時間複雜度為O(n+e)
設⽆向圖 G 中有 n 個頂點 e 條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為n和2e
設某有向圖的鄰接表中有 n 個表頭結點和 m 個表結點，則該圖中有（m）條有向邊
設⽆向圖 G 中有 n 個頂點 e 條邊，則⽤鄰接矩陣作為圖的存儲結構進⾏⼴度優先遍歷時的時間複雜度為O(n2)
如果 n 個頂點的圖是⼀個環，則它有(n)棵⽣成樹
設⽆向圖G中有n個頂點e條邊，則⽤鄰接表作為圖的存儲結構進⾏深度優先遍歷時的時間複雜度為O(n2)
圖中的⼀條路徑⻓度為 k，該路徑所含的頂點數為k+1
當 n 個頂點的⽆向圖 G 的頂點度數的最⼩值⼤於或者等於(n)時，G ⾄少有⼀條迴路
在含 n 個頂點和 e 條邊的⽆向圖的鄰接矩陣中,零元素的個數為n2-2e
對於⼀個具有 n 個頂點和 e 條邊的⽆向圖，若采⽤鄰接表表示，則表頭數量為n
對於⼀個具有 n 個頂點和 e 條邊的⽆向圖，若采⽤鄰接表表示，則所有鄰接表中的結點總數是2e
⼀個⽆向圖有 n 個頂點和 e 條邊，則所有頂點的度的和為（2e）
一個無向圖有 n 個頂點和e 條邊，則該⽆向圖中所有頂點的⼊度之和為2e
在⼀個具有 n 個頂點和 e 條邊的⽆向圖的鄰接矩陣中，表示邊存在的元素（⼜稱為有效元素）的個數為2e
假設⼀個有n個頂點和e條弧的有向圖⽤鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間複雜度是O(n+e)
在⼀個具有 n 個頂點的⽆向圖中，要連通全部頂點⾄少需要（n-1）條邊.
設⽆向圖 G 中有 n 個頂點，則該⽆向圖的最⼩⽣成樹上有（n-1）條邊
⼀個具有 n 個頂點的有向圖最多有（n(n-1)）條邊
⼀個具有 n 個頂點的⽆向完全圖的邊數為n(n-1)/2
設某⽆向圖中有 n 個頂點 e 條邊，則建⽴該圖鄰接表的時間複雜度為O(n+e)
設⽆向圖 G（如下圖所示），則其最⼩⽣成樹上所有邊的權值之和為8
在⽆向圖中定義頂點 vi 與 vj 之間的路徑為從 vi 到 vj 的⼀個頂點序列
路徑長度
⽤ Dijkstra 演算法求某⼀頂點到其餘各頂點間的最短路徑是按路徑⻓度（遞增）的次序來得到最短路徑的
關鍵路徑是事件結點⽹絡中的從源點到匯點的最⻓路徑
鄰接表
鄰接表是圖的⼀種鏈式存儲
連通圖
n 個頂點的連通圖⾄少（n-1）條邊
具有 6 個頂點的⽆向圖⾄少應有（5）條邊才能確保是⼀個連通圖
在⼀個連通圖中存在著（1）個連通分量
設某強連通圖中有 n 個頂點，則該強連通圖中⾄少有（n）條邊
具有 50 個頂點的⽆向圖⾄少應有（49）條邊才能確保是⼀個連通圖
對於⼀個具有 n 個頂點的⽆向連通圖，它包含的連通分量的個數為1
如果從⽆向圖的任⼀頂點出發進⾏⼀次深度優先搜索即可訪問所有頂點，則該圖⼀定是連通圖
任何⼀個⽆向連通圖的最⼩⽣成樹有一棵或多棵
廣度優先遍歷和深度優先遍歷
⼴度優先遍歷類似於⼆叉樹的層次遍歷
若⼀個圖的邊集為{（A,B）,(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點 A 開始對該圖進⾏深度優先搜索，得到的頂點序列可能為A,C,F,D,E,B
已知圖的鄰接矩陣同下圖所示，根據演算法，則從頂點 0 出發，按⼴度優先遍歷的結點序列是0 1 2 3 4 6 5
已知圖的鄰接表如下所示，根據演算法，則從頂點 0 出發按⼴度優先遍歷的結點序列是 0 3 2 1
已知圖的鄰接表如下所示，根據演算法，則從頂點 0 出發按深度優先遍歷的結點序列是 0 1 2 3
圖的邊集
⼀個圖的邊集為{<0,1>3,<0,2>5,<0,3>5,<0,4>10,<1,2>4,<2,4>2,<3,4>6},則從頂點 v0到頂點 v4共有（4）條簡單路徑
若⼀個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},則從頂點 1開始對該圖進⾏⼴度優先搜索，得到的頂點序列可能為1,2,4,5,3
拓撲排序
拓撲排序：可以判斷出⼀個有向圖中是否有環（迴路）
任⼀個有向圖的拓撲序列有一個或多個
稠密圖、稀疏圖（普里姆和克魯斯卡爾）
⽤普⾥姆(Prim)演算法求具有 n 個頂點 e 條邊的圖的最⼩⽣成樹的時間複雜度為n2
若要求⼀個稠密圖 G 的最⼩⽣成樹，最好⽤(普里姆) 演算法來求解.
若要求⼀個稀疏圖 G 的最⼩⽣成樹，最好⽤(克魯斯卡爾) 演算法來求解.
設有⼀稠密圖 G，則 G 采⽤（矩陣）存儲較省空間.
設有⼀稀疏圖 G，則 G 采⽤（表）存儲較省空間
領接矩陣
⽆向圖的鄰接矩陣是⼀個對稱矩陣
已知⼀個圖的鄰接矩陣表示，計算第 i 個結點的⼊度的⽅法是：求矩陣第 i 列⾮零元素之和
已知⼀個圖的鄰接矩陣表示，刪除所有從第 i 個結點出發的邊的⽅法是：將矩陣第 i ⾏全部置為 0
帶權有向圖 G ⽤鄰接矩陣 A 存儲，則頂點 i 的⼊度等於 A 中第 i 列⾮⽆窮的元素個數之和
深度優先遍歷類似於⼆叉樹的先序遍歷
圖的深度優先遍歷序列不唯一
⽤鄰接表表示圖進⾏深度優先遍歷時，通常是采⽤(棧)來實現演算法的
⽤鄰接表表示圖進⾏⼴度優先遍歷時，通常是采⽤(隊列)來實現演算法的.
對於具有 n 個頂點的圖，若采⽤鄰接矩陣表示，則該矩陣的⼤⼩為n2
有向圖 G ⽤鄰接矩陣存儲，其第 i ⾏的所有元素之和等於頂點 i 的出度
拓撲排序演算法是通過重複選擇具有(0)個前驅頂點的過程來完成的。//拓撲à沒有前驅的
圖遍歷
⾮連通圖不能⽤深度優先搜索法（F）
頂點與邊
在⼀個圖中，所有頂點的度數之和=所有邊數
設某完全⽆向圖中有 n 個頂點，則該完全⽆向圖中有(n（n-1）)/2條邊
25. 排序
大多數排序演算法都有兩個基本的操作：比較和移動
設需要對 10個不同的記錄關鍵字進⾏排序，則⾄少需要⽐較（9）次
排序的⽬的是為了以後對已排序的數據元數進⾏（查找）操作
直接插⼊排序和冒泡排序的時間複雜性為 O（n²）, 若初始數據有序（即正序），則時間複雜性為O（n）
初始值
選擇排序/簡單選擇排序/直接選擇排序
在直接插⼊和直接選擇排序中，若初始數據基本反序，則選⽤直接選擇排序
在所有的排序⽅法中，關鍵字的⽐較次數與記錄的初始排列⽆關的是直接選擇排序
對⼀個由 n 個整數組成的序列，藉助排序過程找出其中的最⼤值，希望⽐較次數和移動次數最少，應選
⽤（直接選擇排序）
關鍵字的⽐較次數與記錄的初始排列⽆關
在直接選擇排序中，記錄⽐較次數為 O（n²）數量級，記錄的移動次數為O(n)數量級.
將上萬個⼀組⽆序並且互不相等的正整數序列，存放於順序存儲結構中，采⽤（選擇排序）⽅法能夠最快地找出其中最⼤的正整數
⽬前以⽐較操作為基礎的內部排序的時間複雜性 T(m）的範圍是 O（nlog2n）～ O（n²），其⽐較次數
與待排序記錄的初始狀態⽆關的是(直接選擇)排序
排序⽅法中，從未排序序列中挑選元素，並將其依次放⼊已排序序列（初始時為空）的⼀端的⽅法，稱
為選擇排序
插入排序/直接插入排序
對 n 個元素進⾏直接插⼊排序時間複雜性為n2
設⼀組初始記錄關鍵字的⻓度為 8，則最多經過（7）趟插⼊排序可以得到有序序列.
在對 n 個元素進⾏直接插⼊排序的過程中，共需要進⾏（n-1）趟.
當初始序列已按健值有序時，⽤直接插⼊演算法進⾏排序，需要⽐較的次數為n-1
直接插⼊排序演算法的平均時間複雜度為O(n²)
排序⽅法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進⾏⽐較，將其放⼊
已排序序列的正確位置上的⽅法，稱為插入排序
對於直接插⼊排序、冒泡排序、簡單選擇排序、堆排序、快速排序，當⽂件「局部有序」或⽂件⻓度較⼩
的情況下，最佳的內部排序⽅法是直接插入排序
冒泡排序
對 n 個元素的序列進⾏冒泡排序，在降序的情況下⽐較次數最多，其⽐較次數為(n(n-1))/2
對 n 個元素的序列進⾏冒泡排序，最少的⽐較次數是 n，此時元素的排列情況是已從⼩到⼤排列
對 n 個元素的序列進⾏冒泡排序，最少的⽐較次數是 n，此時元素的排列情況是升序
對 n 個元素的序列進⾏冒泡排序，其⽐較次數為 n（n-1）/2時，其原始數據序列是（降序）情況
對ｎ個不同的排序碼進⾏升序冒泡法排列，從⼤到⼩排列好的⽐較的次數最多
對ｎ個不同的排序碼進⾏冒泡排序，在元素⽆序的情況下⽐較的次數為(n(n-1))/2
排序時掃描待排序記錄序列，順次⽐較相鄰的兩個元素的⼤⼩，逆序時就交換位置，這是冒泡排序的基
本思想
對 n 個元素的序列進⾏冒泡排序，在（降序）的情況下⽐較次數最多
對 n 個元素的序列進⾏冒泡排序，最少的⽐較次數是n-1
在對⼀組有 8 個記錄的數據表進⾏冒泡排序時，在整個排序過程中共需進⾏(7)趟才可完成.
在⽂件局部有序或⽂件⻓度較⼩的情況下，最佳的排序⽅法是冒泡排序
快速排序
快速排序是對序列中的元素通過適當的位置交換將有關元素⼀次性地放置在其最終位置上
最壞的情況下的時間複雜度是O(n²)
在最壞情況下（如初始記錄已有序），快速排序的空間複雜性為n
在對 n 個元素進⾏快速排序的過程中，最好情況下需要進⾏（log 2 n）趟
快速排序在（被排序的數據已基本有序）情況下最不利於發揮其⻓處.
在堆排序，快速排序和歸併排序中，若從平均情況下排序最快，則應⾸先選取（快速排序）⽅法
在堆排序中、快速排序和歸併排序中，若從節省存儲空間考慮，排在中間的是（快速排序）⽅法
每次把待排序的元素劃分為左、右兩個⼦區間，其中左區間中元素的關鍵字均⼩於等於基準元素的關鍵字，右區間中元素的關鍵字均⼤於等於基準元素的關鍵字，則此排序⽅法叫作快速排序
快速排序演算法的平均時間複雜度為O(nlog 2 n)
歸併排序
依次將每兩個相鄰的有序表合併成⼀個有序表的排序⽅法叫作歸併排序
在歸併排序過程中，需歸併的趟數為log2n
若對 n 個元素進⾏歸併排序，則進⾏每⼀趟歸併的時間複雜度為n
⼆路歸併排序的時間複雜度為(nlog2n)
在歸併排序中，歸併趟數的數量級表示為O（log2n)
在內部排序中，要求附加的記憶體容量最⼤的是歸併排序
設⼀組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有 5個⻓度為 2 的有序⼦表，則⽤歸併排序的⽅法對該記錄關鍵字序列進⾏⼀趟歸併後的結果為15，25，35，50，20，40，80，85，36，70
在歸併排序中，若待排序記錄的個數為 20，則共需要進⾏ 5趟歸併，在第 3趟歸併中，是把⻓度為 4 的
有序表歸併為⻓度為4的有序表
希爾排序
設⼀組初始記錄關鍵字序列為(9，8，7，6，5，4，3，2，1，0)，則以增量 d=5 的⼀趟希爾排序結束後前 5條記錄關鍵字為4，3，2，1，0
⼀趟排序結束後不⼀定能夠選出⼀個元素放在其最終位置上的是希爾排序
希爾排序的增量序列必須是遞減
堆排序
在堆排序中、快速排序和歸併排序中，若只從最壞的情況下排序最快並且要節省記憶體考慮，應選⽤（堆排序）
時間複雜度不受數據初始狀態影響⽽恆為 O(nlog2n)的是堆排序
在任何情況下，時間複雜度均為 O(nlog2n)的不穩定的排序⽅法是堆排序
已知⼀個鏈表中有 3000 個結點，每個結點存放⼀個整數，（堆排序方法）可⽤於解決這 3000個整數的排序問題且不需要對演算法作⼤的變動
設有 1000 個⽆序的元素，希望⽤最快的速度挑選出其中前 10 個最⼤的元素，最好選⽤（堆）排序法
交換排序
當兩個元素⽐較出現反序時（即逆序）就相互交換位置的排序⽅法叫作交換排序
基數排序
如果將所有中國⼈按照⽣⽇來排序，則使⽤（基數排序）演算法最快
比較排序的穩定和快慢
時間複雜度
關鍵字序列
26. 查找
二分查找
