數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題要點(整理版)-資料下載頁
2025-04-17 01:46本頁面
【正文】 n，則結(jié)點 i無右孩子。 3． 二叉樹的遍歷（遞歸調(diào)用與訪問的順序不同而產(chǎn)生不同的遍歷方法）（1） 先序遍歷void XianXu(BiTree T){ if(T){ printf(%c,Tdata)。 //先訪問 XianXu(Tlchild)。 //再繼續(xù)遍歷 XianXu(Trchild)。 }}（2） 中序遍歷（3） 后序遍歷4. 森林與二叉樹的轉(zhuǎn)換 （1）同級以左為親，即左一結(jié)點的右孩子是與它同級的右一結(jié)點 （2）只認(rèn)最左路線為親子路線，即結(jié)點的左孩子是它下一級結(jié)點的最左的元素 5. 哈夫曼樹（1）哈夫曼樹的基本概念：哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點，帶權(quán)路徑長度最小的二叉樹。（2）哈夫曼樹的特點：1. 權(quán)值越大的葉子結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉子結(jié)點越遠(yuǎn)離根結(jié)點。 2. 只有度為0（葉子結(jié)點）和度為2（分支結(jié)點）的結(jié)點，不存在度為1的結(jié)點. （3）哈夫曼樹的構(gòu)造算法思想及構(gòu)造過程（森林與哈夫曼編碼）就是求各權(quán)值和路徑相乘之后疊加的最小值。已知一棵完全二叉樹有47個結(jié)點，則該二叉樹有（C）個葉子結(jié)點。A. 6 B. 12 C. 24 解法如下：1+2+4+8+16=31 計算從第一層到n1層的結(jié)點個數(shù)4731=16 計算第n層的葉子結(jié)點個數(shù)1616/2=8 計算第n1層的葉子結(jié)點個數(shù)所以，葉子結(jié)點數(shù)=16+8=24 計算第n層和第n1層的總?cè)~子結(jié)點數(shù)已知遍歷一棵二叉樹的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵樹（C ）。C圖如下： A ↙ ↘ B F ↙ ↘ ↘ C D G ↙ E 完全二叉樹必須滿足的條件為: ：一棵具有n個結(jié)點的二叉樹，它的結(jié)構(gòu)與滿二叉樹的前n個結(jié)點的的結(jié)構(gòu)相同。哈夫曼樹不存在度為1的結(jié)點。有5個帶權(quán)結(jié)點，其權(quán)值分別為2，5，3，7，11，根據(jù)哈夫曼算法構(gòu)建該樹，并計算該樹的帶權(quán)路徑長度。（構(gòu)建哈夫曼樹，很簡單，從小開始，計算相加，然后把所有葉子結(jié)點乘以等級數(shù)字然后相加。也即是：帶權(quán)路徑長度=葉結(jié)點的權(quán)值*路徑長度）：⑴ 前序序列和中序序列相同：只有右子樹⑵ 中序序列和后序序列相同：只有左子樹⑶ 前序序列和后序序列相同：只有根，空二叉樹第七章 圖1. 圖的基本概念：圖的基本術(shù)語及推論圖的結(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。設(shè)圖有n個頂點，則：有1/2 n(n1)條邊的無向圖稱為完全圖有n（n1）條弧的有向圖稱為有向完全圖元素被多少條弧的箭頭所指，它的入度就為多少；反之，出度。第一個頂點和最后一個頂點相同的路徑叫做回路或環(huán)頂點不重復(fù)出現(xiàn)的路徑叫簡單路徑若圖中任意兩個頂點之間存在路徑（不一定是直接相連），則稱作連通圖2. 鄰接矩陣： Wi,j Vi，Vj ∈VR鄰接矩陣的定義： A[i][j]={ 0 即VR中不存在Vi，Vj時3. 圖的遍歷 （1）深度優(yōu)先遍歷 步驟：。 ，并從該頂點開始進(jìn)行訪問 4. 重復(fù)3步驟直到該連通圖的所有頂點均已訪問完畢 （2）廣度優(yōu)先遍歷 步驟：。 ，并按順序入列直到所有鄰接頂點均已訪問完畢 ，以它為頂點開始訪問 5. 重復(fù)4步驟直到該連通圖的所有頂點均已訪問完畢第八九十章查找表是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合對查找表的操作有：（1） 查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；（2） 檢索某個“特定的”數(shù)據(jù)元素的各種屬性（3） 在查找表中插入一個數(shù)據(jù)元素；（4） 從查找表中刪去某個特定元素靜態(tài)查找表只進(jìn)行前兩種“查找”操作的查找表為靜態(tài)查找表動態(tài)查找表若在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素，則成為動態(tài)查找表排序其功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。 技術(shù)資料 專業(yè)分
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1