華中科技大學(xué)研究生考試軟件工程答案數(shù)據(jù)結(jié)構(gòu)“名詞解釋”部分《數(shù)據(jù)結(jié)構(gòu)與算法分析》-文庫吧
2024-10-28 00:06 本頁面
【正文】 第一層，根的孩子為第二層。若某結(jié)點(diǎn)在第 l 層，則其子樹在第 l+1 層。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。 4. 如果將樹中結(jié)點(diǎn)的各種子樹看成是從左到右是有次序的，則稱該樹為有序樹，否則稱為無序樹。 5. 森林 (forest)是 m(m0)棵互不相交的樹的集合。 6. 二叉樹（ Binary Tree)是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)至多只有兩棵子樹，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。 7. 一個深度為 k 且有 2K1 個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。深度為 k 的，有 n 個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為 k 的滿二叉樹中編號從 1 至 n 的結(jié)點(diǎn)一一對應(yīng)時，稱之為完全二叉樹。 8. 遍歷二叉樹 ：指按某條搜索路徑巡訪樹上每個結(jié)點(diǎn)，使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。有先序遍歷、中序遍歷、后序遍歷三種。 9. 若結(jié)點(diǎn)有左子樹，則其 lchild（ rchild）域指向指示其左 (右 )孩子，否則令 lchild（ rchild）域指示其前驅(qū)（后繼），這種結(jié)點(diǎn)構(gòu)成的二叉鏈表做為二叉樹的存儲結(jié)構(gòu)稱為線索鏈表。 10. 從樹中一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支構(gòu)成這兩個結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱做 路徑長度 。樹的路徑長度是從樹根到每一個結(jié)點(diǎn)的路徑長度之和。 樹的帶權(quán)路徑長度 為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。 11. 假設(shè)有 n個權(quán)值 {w1,w2,??， wn}，試構(gòu)造一棵有 n個葉子結(jié)點(diǎn)的二叉樹，每個葉子結(jié)點(diǎn)帶樹為 wi,則其中帶權(quán)路徑長度 WPL 最小的二叉樹稱為 最優(yōu)二叉樹或赫夫曼樹 。 第七章 ：圖 1. 在圖中的數(shù)據(jù)元素通常稱做 頂點(diǎn) ， v,w表示從 v 到 w 的一條弧，且稱 v 為 弧尾 ，稱w 為 弧頭 ,此時稱圖為 有向圖 ，若 v,w表示 v 和 w 之間的一條 邊 ，此時的圖稱為 無向圖。 2. 有 n*(n1)/2 條邊的無向圖稱為 完全圖 。具有 n(n1)條弧的有向圖稱為 有向完全圖 ，有很少條邊或弧的圖稱為 稀疏圖 ，反之稱為 稠密圖 。有時圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做 權(quán) ，這種帶權(quán)的圖稱為 網(wǎng) 。 3. 頂點(diǎn) v 的度 是和 v 相關(guān)聯(lián)的邊的數(shù)目，記為 TD(V)。 4. 無向圖 G=(V,{E})中從點(diǎn) v 到頂點(diǎn) v’的路徑是一個頂點(diǎn)序列， 路徑的 長度 是路徑上邊或弧的數(shù)目。第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為 回路或環(huán) 。序列中不重復(fù)出3 現(xiàn)的路徑稱為 簡單路徑 。除了第一個頂點(diǎn)和最后一個頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為 簡單回路或簡單環(huán) 。 5. 在無向圖 G 中，如果從頂點(diǎn) v 到頂點(diǎn) v’有路徑，則稱 v 和 v’是連通的。如果對于圖中任意兩個頂點(diǎn) vi、 vj∈ V,vi和 vj都是連通的，則稱 G是 連通圖 。所謂 連通分量 指的是無向圖中的極大連通子圖。 6. 在有向圖 G 中，如果對于每一對 vi、 vj∈ V, vi≠ vj,從 vi到 vj和從 vj到 vi都存在路徑，則稱 G 是 強(qiáng)連通圖 。有向圖中的極大強(qiáng) 連通子圖稱做 有向圖的強(qiáng)連通分量 。 7. 一個 連通圖的生成樹 是一個極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的 n1 條邊。如果在一棵生成樹上添加一條邊，必定構(gòu)成一個環(huán)。一棵有 n 個頂點(diǎn)的生成樹有且僅有 n1 條邊。如果一個圖有 n個頂點(diǎn)和小于 n1條邊，則是非連通圖，如果它多于 n1 條邊，則一定有環(huán)。但是，有 n1 條邊的圖不一定是生成樹。 最小生成樹（ MST） ： 在網(wǎng)絡(luò)的多個生成樹中，尋找一個各邊權(quán)值之和最小的生成樹。 8. Kruskal
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1