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