線性表
- 順序表
-
鏈表（物理上離散，邏輯上連續(xù)）
鏈表的類別
- 單鏈表
- 循環(huán)鏈表
-
雙鏈表
鏈表的操作
順序表與鏈表的比較
棧
- FILO
- 棧頂别惦、棧底
隊列
- FIFO
- 隊尾允趟、對頭（非循環(huán)）
-
循環(huán)隊列（head屎慢、tail指針）（rear=(rear+1）mod m)
- 答案：C
樹和二叉樹
樹概念
- 結(jié)點的度、樹的度
- 葉子咽块、分支绘面、內(nèi)部、父侈沪、子揭璃、兄弟結(jié)點
- 樹除了葉子結(jié)點全部為分支結(jié)點，包括根結(jié)點
- 除了根結(jié)點和葉子結(jié)點亭罪，都為內(nèi)部結(jié)點
- 層次
*結(jié)點數(shù)=結(jié)點度總和+1（n=k+1）
樹的遍歷
- 前序遍歷
- 后序遍歷
- 層次遍歷
二叉樹概念
- 二叉樹不是特殊的樹
- 滿二叉樹瘦馍、完全二叉樹、非完全二叉樹
- 完全二叉樹：n-1層是滿樹应役，按左到右連續(xù)排列
- 第i層最多2^（i-1）個結(jié)點
- 深度為k的最多有(2^k)-1個結(jié)點
-
葉子結(jié)點數(shù)為n0情组，度為2結(jié)點數(shù)為n2燥筷，則n0=n2+1
- 答案：B
二叉樹遍歷
- 前序
- 中序
- 后序
-
層次
樹與二叉樹的轉(zhuǎn)換
- 正向：孩子結(jié)點作左子樹結(jié)點，兄弟結(jié)點作右子樹
- 二叉樹中序遍歷和轉(zhuǎn)換的樹的后序遍歷對應(yīng)
- 二叉樹前序遍歷和轉(zhuǎn)換的樹的前序遍歷一樣
圖
圖的概念
- 線性表和樹是圖的特殊形式
- 有限非空頂點集合+頂點對表示的邊集合
- G=(V,E)院崇，樹可以空樹肆氓，圖不能沒有頂點
- 無向圖與有向圖（A,B）<A,B>≠<B,A>
- 頂點的度，有向圖頂點的度=入度+出度
- 子圖
- 完全圖（每對頂點都有 一條/兩條 邊/有向邊 相連）
- 路徑和回路底瓣、簡單回路
- 連通圖和連通分量
- 網(wǎng)絡(luò)（圖+權(quán)值）
- 圖的存儲：鄰接矩陣（1有邊谢揪、0無邊）
圖的遍歷
- 深度優(yōu)先（類似樹的先根遍歷）
- 廣度優(yōu)先（類似樹的層次遍歷）
最小生成樹
- 普里姆算法
- 克魯斯卡爾算法
