華中科技大學(xué)研究生考試軟件工程答案數(shù)據(jù)結(jié)構(gòu)“名詞解釋”部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法分析-資料下載頁
2024-11-17 00:06本頁面
【導(dǎo)讀】的關(guān)系和操作等的科學(xué)。被計算機(jī)程序處理的符號的總稱。結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。抽象”和“數(shù)據(jù)封裝”兩個重要特性。的增長率相同，稱做算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。含義稱為棧頂，相應(yīng)地，表頭端稱為棧底。在隊列中，允許插入的一端稱做隊尾，允許刪除的一端稱做隊頭。結(jié)點擁有的子樹稱為結(jié)點的度。樹的根稱為該結(jié)點的孩子，相應(yīng)的該結(jié)點稱為孩子的雙親。子樹中的任一結(jié)點都稱為該結(jié)點的子孫。則其子樹在第l+1層。并且二叉樹的子樹有左右之分，其次序不能任意顛倒。時，稱之為完全二叉樹。且僅被訪問一次。域指示其前驅(qū)（后繼），這種結(jié)點構(gòu)成的二叉鏈表做為二叉樹的存儲結(jié)構(gòu)稱為線索鏈表。點帶樹為wi,則其中帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹。任意兩個頂點vi、vj∈V,vi和vj都是連通的，則稱G是連通圖。
【正文】 地址。 13. 沖突 (Collision)：對不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱為沖突，具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱做同義詞。 14. 常用的構(gòu)造哈希函數(shù)的方法有： a) 直接定址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。 b) 數(shù)字分析法：假設(shè)關(guān)鍵字是以 r 為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干位組成哈希地址。 c) 平方取中法：取關(guān)鍵字平方的后的中間幾位做為哈希地址。 d) 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和為哈希地址。 e) 除留余數(shù)法：取關(guān)鍵字 被某個不大于哈希表表長 m的數(shù) p 除后的余數(shù)為哈希地址。 f) 隨機(jī)數(shù)法：選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址。 15. 常用的處理沖突的方法： a) 開放定址法：其中增量序列有線性探測再散列，二次探測再散列，隨機(jī)探測再散列。 b) 再哈希法：即在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。 c) 鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。 d) 建立一個公共溢出區(qū)。 16. 二次聚集 ：指在處理沖突過程中發(fā)生的兩個第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現(xiàn)象。 17. 裝填因子 ：是表中填入的記錄數(shù)與哈希表的 長度之商，哈希表的平均查找長度是裝填因子的函數(shù)，不是規(guī)模 n 的函數(shù)。 第十章：內(nèi)部排序 1. 排序 (Sorting)：是指將一個數(shù)據(jù)元素的任意序列重新排列成一個按關(guān)鍵字有序的序列。 2. 假設(shè) Ri=Rj,且在排序前的序列中 Ri領(lǐng)先于 Rj，若在排序后的序列中 Ri仍領(lǐng)先于 Rj，則稱所用的排序方法是穩(wěn)定的，反之稱所用的排序方法是不穩(wěn)定的。 3. 由于待排序的記錄的數(shù)量不同，使得排序過程中涉及的存儲器不同，可將排序方法分為兩大類： a) 內(nèi)部排序 ：指的是待排序記錄放在計算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程 b) 外部排序 ：指的是待排序記錄的數(shù)量很大，以 致內(nèi)在一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。 6 4. 直接插入排序 (Straight Insertion Sort)：它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數(shù)增 1 的有序表。 5. 希爾排序 (Shell’ s Sort)：又稱縮小增量排序，基本思想是先將整個記錄序列分割成若干子序列分別進(jìn)行直接插入排序，待整個序列中記錄基本有序時，再對全體記錄進(jìn)行一次直接插入排序。 6. 起泡排序 (Bubble Sort)：首先將第一個記錄的關(guān)鍵字同第二個記錄的關(guān)鍵字進(jìn)行比較，或為逆序，則 交換，依此類推，直至第 n1 個記錄和第 n個記錄的關(guān)鍵字進(jìn)行比較為止。判別起泡排序結(jié)束的條件應(yīng)該是在一趟排序過程中沒有進(jìn)行交換記錄的操作。 7. 快速排序 (Quick Sort)：它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，分別對這丙部分繼續(xù)進(jìn)行快速排序，直至整個序列有序。 8. 選擇排序 ：它的基本思想是每一趟在 ni+1 個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第 i個記錄。 9. 堆排序 (Heap Sort)：若在輸出堆頂?shù)淖钚≈抵?，使得剩余?n1 個元素的序列重新又構(gòu)成一個堆，則得到 n個元素中的次小值，如此反復(fù)，便能得到一個有序序列，稱這個過程為堆排序。 10. 歸并排序 (Merging Sort)是將兩個或兩個以上的有序表組合成一個新的有序表，其中 2歸并中的核心操作是將一維數(shù)組中前后相信的兩個有序序列歸并為一個有序序列。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1