華中科技大學(xué)研究生考試軟件工程答案數(shù)據(jù)結(jié)構(gòu)“名詞解釋”部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法分析(完整版)
【正文】 ，稱w 為 弧頭 ,此時稱圖為 有向圖 ，若 v,w表示 v 和 w 之間的一條 邊 ，此時的圖稱為 無向圖。深度為 k 的，有 n 個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為 k 的滿二叉樹中編號從 1 至 n 的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。 3. 結(jié)點的層次 從根開始定義起，根為第一層，根的孩子為第二層。 2. 樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。棧的修改是按后進先出的原則進行的，因此又稱后進先出表。 10. 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問 題規(guī)模 n 的某個函數(shù) f(n)，算法的時間量度記作 T(n)=O(f(n))，它表示隨問題規(guī)模 n 的增大，算法執(zhí)行時間的增長率和 f(n)的增長率相同，稱做算法的 漸近時間復(fù)雜度 ，簡稱時間復(fù)雜度。 2. 數(shù)據(jù) (data)是對客觀事物的符號表示，在計算機科學(xué)中是指所有以輸入到計算機中并被計算機程序處理的符號的總稱。 7. 抽象數(shù)據(jù)類型 (ADT)：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作，有“數(shù)據(jù)抽象”和“數(shù)據(jù)封裝”兩個重要特性。 4. 雙向鏈表 是指有兩個指針域，其一指向直接后繼，另一指向直接前趨。也就是說，只有當(dāng)兩個串的長度相等，并且各個對應(yīng)位置的字符都相等時才相等。同一個雙親的孩子之間互稱 兄弟 。 5. 森林 (forest)是 m(m0)棵互不相交的樹的集合。樹的路徑長度是從樹根到每一個結(jié)點的路徑長度之和。 4. 無向圖 G=(V,{E})中從點 v 到頂點 v’的路徑是一個頂點序列， 路徑的 長度 是路徑上邊或弧的數(shù)目。有向圖中的極大強 連通子圖稱做 有向圖的強連通分量 。 9. Prim 算法 —— 在當(dāng)前最小邊集合 中逐漸歸并相關(guān)的頂點。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復(fù)上述過程，直到圖中所有頂點都被訪問到為止。 若用有向圖表示一個工程，在圖中用頂點表示活動，用?。从邢蜻叄┍硎净顒娱g的優(yōu)先關(guān)系。 21. 最早發(fā)生時間 ： 假設(shè)開始點是 V1，從 V1 到 Vi 的最長路徑長度叫做事件 Vi 的最早發(fā)生時間 [ e(i) ] 。 3. 查找 ：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等給定值的記錄或數(shù)據(jù)元素，若表中存在這樣一個記錄，則稱查找是成功的，此時查找的結(jié)果為給出整個記錄的信息，或指示該記錄在查找表中的 位置，若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找不成功，此時查找的結(jié)果可給出一個“空”記錄或“空”指針。折半查找法在成功時進行比較的關(guān)鍵字個數(shù)最多不超過樹的深度。 13. 沖突 (Collision)：對不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱為沖突，具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱做同義詞。 b) 再哈希法：即在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。 6 4. 直接插入排序 (Straight Insertion Sort)：它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數(shù)增 1 的有序表。 。 6. 起泡排序 (Bubble Sort)：首先將第一個記錄的關(guān)鍵字同第二個記錄的關(guān)鍵字進行比較，或為逆序，則 交換，依此類推，直至第 n1 個記錄和第 n個記錄的關(guān)鍵字進行比較為止。 d) 建立一個公共溢出區(qū)。 b) 數(shù)字分析法：假設(shè)關(guān)鍵字是以 r 為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干位組成哈希地址。 9. 二叉排序樹 (Binary Sort Tree)：或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹 : 5 a) 若它的左子樹不空，則左子村上所有結(jié)點的值均小于它的根結(jié)點的值。反之，
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1