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