華中科技大學(xué)研究生考試軟件工程答案數(shù)據(jù)結(jié)構(gòu)“名詞解釋”部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法分析(編輯修改稿)
2024-12-23 00:06 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 算法 — 在頂點(diǎn)集合中逐漸歸并當(dāng)前權(quán)值最小的邊。 9. Prim 算法 —— 在當(dāng)前最小邊集合 中逐漸歸并相關(guān)的頂點(diǎn)。 10. 如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為 0，其余頂點(diǎn)的入度均為 1，則是一棵 有向樹 。一個(gè) 有向圖的生成森林 由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。 11. 圖的存儲(chǔ)結(jié)構(gòu) 有鄰接矩陣、鄰接表、逆鄰接表以及十字鏈表等。 12. 圖的遍歷 ：指從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次。 13. 通常有兩條遍歷圖的路徑： 1） 深度優(yōu)先搜索 ：類似于樹的先序遍歷，假設(shè)從圖中某頂點(diǎn) v出發(fā)，在訪問(wèn)了 v 之后依次從 v 的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和 v有路徑相通的頂點(diǎn) 都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)做為起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。 2） 廣度優(yōu)先搜索 ：類似于村的層序遍歷，假設(shè)從圖中某頂點(diǎn) v出發(fā)，在訪問(wèn)了 v 之后依次訪問(wèn)它們的鄰接點(diǎn)，并使先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)先于后訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)，直到圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直到圖中所有頂點(diǎn)都被訪問(wèn)到為止。 14. 假若在刪去頂點(diǎn) v以及和 v相關(guān)聯(lián)的各邊之后，將圖的一個(gè)連通分量分割成兩個(gè)或 兩個(gè)以上的邊通分量，則稱頂點(diǎn) v為該圖的一個(gè) 關(guān)節(jié)點(diǎn) 。一個(gè)沒(méi)有關(guān)節(jié)點(diǎn)的圖稱為重 連通圖 。若在連通圖上至少刪去 k 個(gè)頂點(diǎn)才能破壞圖的連通性，則稱此圖的 連通度 為 k。 15. 對(duì)于無(wú)向圖來(lái)說(shuō)，若深度優(yōu)先搜索過(guò)程中遇到回邊，則必定存在環(huán)，而對(duì)于有向圖來(lái)說(shuō)，這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上頂點(diǎn)的弧。 16. 拓?fù)渑判?(Topological Sort)：指由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序。 17. AOV網(wǎng) ：指用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)。 AOV網(wǎng) (Activity On Vertices)—用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò) 。 若用有向圖表示一個(gè)工程，在圖中用頂點(diǎn)表示活動(dòng)，用?。从邢蜻叄┍硎净顒?dòng)間的優(yōu)先關(guān)系。 Vi 必須先于活動(dòng) Vj 進(jìn)行。則這樣的有向圖叫做用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱 AOV。 18. AOE網(wǎng) ： 在帶權(quán)有向無(wú)環(huán)網(wǎng)中， 用有向邊表示一個(gè)工程中的活動(dòng)，用邊上權(quán)值表示活動(dòng)持續(xù)時(shí)間，用頂點(diǎn)表示事件，則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱 AOE。常用于大型工程的計(jì)劃管理。 19. 在正常的情況（無(wú)環(huán)）下，網(wǎng)中只有一個(gè)入度為零的點(diǎn)，稱做 源點(diǎn) 和一個(gè)出度為零的4 點(diǎn)，稱為 匯點(diǎn) 。 20. 關(guān)鍵路徑 ： AOE 網(wǎng)中有 些活動(dòng)可以并行進(jìn)行，所以完工的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度（即沿途各活動(dòng)持續(xù)時(shí)間之和）。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑 ， 關(guān)鍵路徑上的所有活動(dòng) （ l(i) = e(i)的活動(dòng) ） 都是 關(guān)鍵活動(dòng) 。 21. 最早發(fā)生時(shí)間 ： 假設(shè)開始點(diǎn)是 V1，從 V1 到 Vi 的最長(zhǎng)路徑長(zhǎng)度叫做事件 Vi 的最早發(fā)生時(shí)間 [ e(i) ] 。 22. 最遲開始時(shí)間 ： 不推遲整個(gè)工程完成的前提下，活動(dòng) ai最遲必須開始進(jìn)行的時(shí)間 [ l(i) ] 。 23. Dijkstra（迪杰斯特拉）算法 ： 先找出從源點(diǎn) v0到各終點(diǎn) vk 的直達(dá)路徑（ v0,vk），即通過(guò)一條弧到達(dá)的路 徑。從這些路徑中找出一條長(zhǎng)度最短的路徑（ v0,u） ,然后對(duì)其余各條路徑進(jìn)行適當(dāng)調(diào)整：若在圖中存在?。?u,vk），且（ v0,u） +（ u,vk） （ v0,vk） ， 則以路
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1