華中科技大學研究生考試軟件工程答案數(shù)據(jù)結(jié)構(gòu)“名詞解釋”部分《數(shù)據(jù)結(jié)構(gòu)和算法分析》.doc

1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系與操作等的科學。2. 數(shù)據(jù)(data)是對客觀事物的符號表示，在計算機科學中是指所有以輸入到計算機中并被計算機程序處理的符號的總稱。3. 數(shù)據(jù)元素(data element)是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮與處理。4. 數(shù)據(jù)對象(data object)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。5. 數(shù)據(jù)結(jié)構(gòu)(data structure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。6. 根據(jù)數(shù)據(jù)結(jié)構(gòu)之間關(guān)系的不同特性，通常有下列4類基本結(jié)構(gòu):集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。7. 抽象數(shù)據(jù)類型(ADT)：是指一個數(shù)學模型以及定義在該模型上的一組操作，有“數(shù)據(jù)抽象”與“數(shù)據(jù)封裝”兩個重要特性。8. 算法(algorithm)是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作，具有“有窮性”，“確定性”，“可行性”，“輸入”，“輸出”五個特性。9. 算法設(shè)計的要求：正確性、可讀性、健壯性、效率與低存儲需求。10. 一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作T(n)=O(f(n)，它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率與f(n)的增長率相同，稱做算法的漸近時間復雜度，簡稱時間復雜度。1. 線性表：是n個數(shù)據(jù)元素的有限序列，有順序存儲與鏈式存儲兩種表示形式。2. 線性表的鏈式存儲結(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，包括兩個域，其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲直接后繼存儲位置的域稱為指針域。3. 循環(huán)鏈表是另一種形式的鏈式存儲結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。4. 雙向鏈表是指有兩個指針域，其一指向直接后繼，另一指向直接前趨。棧是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義稱為棧頂，相應(yīng)地，表頭端稱為棧底。棧的修改是按后進先出的原則進行的，因此又稱后進先出表。1. 隊列是一種先進先出的線性表，它只允許在表的一端進行插入，而在另一端刪除元素，在隊列中，允許插入的一端稱做隊尾，允許刪除的一端稱做隊頭。1. 串(string)是由零個或多個字符組成的有限序列。串中任意個連續(xù)的字符組成的子序列稱該串的子串，通常稱字符在序列中的序號為該字符在序列中的序號為該字符的在串中的位置。2. 稱兩個串是相等的，當且僅當這兩個串的值相等。也就是說，只有當兩個串的長度相等，并且各個對應(yīng)位置的字符都相等時才相等。1. 樹(tree)是指n(n=0)個結(jié)點的有限集，在任意一棵非空樹中：1）有且僅有一個特定的稱為根。2）當n1時，其余結(jié)點可分為m(m0)個互不相交的有限集，其中每一個集合本身又是一棵樹。2. 樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點擁有的子樹稱為結(jié)點的度。度為0的結(jié)點稱為葉子或終端結(jié)點。樹的度是樹內(nèi)各結(jié)點的度的最大值。結(jié)點的子樹的根稱為該結(jié)點的孩子，相應(yīng)的該結(jié)點稱為孩子的雙親。同一個雙親的孩子之間互稱兄弟。結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。反之，以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。3. 結(jié)點的層次從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點在第l層，則其子樹在第l+1層。其雙親在同一層的結(jié)點互為堂兄弟。樹中結(jié)點的最大層次稱為樹的深度或高度。4. 如果將樹中結(jié)點的各種子樹看成是從左到右是有次序的，則稱該樹為有序樹，否則稱為無序樹。5. 森林(forest)是m(m0)棵互不相交的樹的集合。6. 二叉樹（Binary Tree)是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。7. 一個深度為k且有2K-1個結(jié)點的二叉樹稱為滿二叉樹。深度為k的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。8. 遍歷二叉樹：指按某條搜索路徑巡訪樹上每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。有先序遍歷、中序遍歷、后序遍歷三種。9. 若結(jié)點有左子樹，則其lchild（rchild）域指向指示其左(右)孩子，否則令lchild（rchild）域指示其前驅(qū)（后繼），這種結(jié)點構(gòu)成的二叉鏈表做為二叉樹的存儲結(jié)構(gòu)稱為線索鏈表。10. 從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑，路徑上的分支數(shù)目稱做路徑長度。樹的路徑長度是從樹根到每一個結(jié)點的路徑長度之與。樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之與。11. 假設(shè)有n個權(quán)值w1,w2,，wn，試構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子結(jié)點帶樹為wi,則其中帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹。1. 在圖中的數(shù)據(jù)元素通常稱做頂點，表示從v到w的一條弧，且稱v為弧尾，稱w為弧頭,此時稱圖為有向圖，若表示v與w之間的一條邊，此時的圖稱為無向圖。2. 有n*(n-1)/2條邊的無向圖稱為完全圖。具有n(n-1)條弧的有向圖稱為有向完全圖，有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。有時圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)，這種帶權(quán)的圖稱為網(wǎng)。3. 頂點v的度是與v相關(guān)聯(lián)的邊的數(shù)目，記為TD(V)。4. 無向圖G=(V,E)中從點v到頂點v的路徑是一個頂點序列，路徑的長度是路徑上邊或弧的數(shù)目。第一個頂點與最后一個頂點相同的路徑稱為回路或環(huán)。序列中不重復出現(xiàn)的路徑稱為簡單路徑。除了第一個頂點與最后一個頂點之外，其余頂點不重復出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。5. 在無向圖G中，如果從頂點v到頂點v有路徑，則稱v與v是連通的。如果對于圖中任意兩個頂點vi、vjV,vi與vj都是連通的，則稱G是連通圖。所謂連通分量指的是無向圖中的極大連通子圖。6. 在有向圖G中，如果對于每一對vi、vjV, vivj,從vi到vj與從vj到vi都存在路徑，則稱G是強連通圖。有向圖中的極大強連通子圖稱做有向圖的強連通分量。7. 一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵樹的n-1條邊。如果在一棵生成樹上添加一條邊，必定構(gòu)成一個環(huán)。一棵有n個頂點的生成樹有且僅有n-1條邊。如果一個圖有n個頂點與小于n-1條邊，則是非連通圖，如果它多于n-1條邊，則一定有環(huán)。但是，有n-1條邊的圖不一定是生成樹。8. 如果一個有向圖恰有一個頂點的入度為0，其余頂點的入度均為1，則是一棵有向樹。一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點，但只有足以構(gòu)成若干棵不相交的有向樹的弧。9. 圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表、逆鄰接表以及十字鏈表等。10. 圖的遍歷：指從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。11. 通常有兩條遍歷圖的路徑：1） 深度優(yōu)先搜索：類似于樹的先序遍歷，假設(shè)從圖中某頂點v出發(fā)，在訪問了v之后依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直到圖中所有與v有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點做為起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。2） 廣度優(yōu)先搜索：類似于村的層序遍歷，假設(shè)從圖中某頂點v出發(fā)，在訪問了v之后依次訪問它們的鄰接點，并使先被訪問的頂點的鄰接點先于后訪問的頂點的鄰接點，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述過程，直到圖中所有頂點都被訪問到為止。12. 假若在刪去頂點v以及與v相關(guān)聯(lián)的各邊之后，將圖的一個連通分量分割成兩個或兩個以上的邊通分量，則稱頂點v為該圖的一個關(guān)節(jié)點。一個沒有關(guān)節(jié)點的圖稱為重連通圖。若在連通圖上至少刪去k個頂點才能破壞圖的連通性，則稱此圖的連通度為k。13. 對于無向圖來說，若深度優(yōu)先搜索過程中遇到回邊，則必定存在環(huán)，而對于有向圖來說，這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上頂點的弧。14. 拓撲排序(Topological Sort)：指由某個集合上的一個偏序得到該集合上的一個全序。15. AOV-網(wǎng)：指用頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)。16. AOE-網(wǎng)：指用邊表示活動的網(wǎng)，是一個帶權(quán)的有向無環(huán)圖，其中，頂點表示事件弧表示活動，權(quán)表示活動持續(xù)的時間，通常一個AOE-網(wǎng)可用來估算工程的完成時間。17. 在正常的情況（無環(huán)）下，網(wǎng)中只有一個入度為零的點，稱做源點與一個出度為零的點，稱為匯點。18. 在AOE-網(wǎng)點，路徑長度最長的路徑叫做關(guān)鍵路徑，關(guān)鍵路徑上的所有活動都是關(guān)鍵活動。1. 查找表（Search Table）：是由同一類型的數(shù)據(jù)元素構(gòu)成的集合。若對查找表只作查找操作，則稱此類查找表為靜態(tài)查找表(Static Search Table)，若在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，則稱此類表為動態(tài)查找表(Dynamic Search Table)。2. 關(guān)鍵字（Key）：是數(shù)據(jù)元素或記錄中某個數(shù)據(jù)項的值，用它可能標識一個數(shù)據(jù)元素，若此關(guān)鍵字可以惟一地標識一個記錄，則稱此關(guān)鍵字為主關(guān)鍵字(Primary Key)，反之，稱用以識別若干記錄的關(guān)鍵為次關(guān)鍵字(Secondary Key)。3. 查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等給定值的記錄或數(shù)據(jù)元素，若表中存在這樣一個記錄，則稱查找是成功的，此時查找的結(jié)果為給出整個記錄的信息，或指示該記錄在查找表中的位置，若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找不成功，此時查找的結(jié)果可給出一個“空”記錄或“空”指針。4. 順序查找(Sequential Search)的查找過程為：從表中最后一個記錄開始，逐個進行記錄的關(guān)鍵字與給定值的比較，若某個記錄的關(guān)鍵字與給定值比較相等，則查找成功。反之，若直至第一個記錄，其關(guān)鍵字與給定值比較都不相等，則表明表中沒有所查記錄，查找不成功。5. 平均查找長度(Average Search Length)：為確定記錄在查找表中的位置，需與給定值進行比較的關(guān)鍵字的個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度。6. 折半查找(Binary Search)的查找過程：先確定待查記錄在有序表中所在范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。7. 判定樹：樹中每個結(jié)點表示表中一個記錄，結(jié)點中的值為該記錄在表中的位置，通常稱這個查找過程的二叉樹稱為判定樹。折半查找法在成功時進行比較的關(guān)鍵字個數(shù)最多不超過樹的深度。8. 次優(yōu)查找樹(Nearly Optimal Search Tree)：構(gòu)造一棵二叉樹，使這棵二叉樹的帶權(quán)內(nèi)路徑長度PH值在所有具有同樣權(quán)值的二叉樹中近似為最小。9. 二叉排序樹(Binary Sort Tree)：或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹:a) 若它的左子樹不空，則左子村上所有結(jié)點的值均小于它的根結(jié)點的值。b) 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值。c) 它的左、右子樹也分別為二叉排序樹。10. 平衡二叉樹(Balanced Binary Tree)：又稱AVL樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹，它的左子樹與右子樹都是平衡二叉樹，且左子樹與右子樹的深度之差的絕對值不超過1。11. 平衡因子BF(Balance Factor)：為該結(jié)點的左子樹深度減去它的右子樹的深度，則平衡二叉樹上所有結(jié)點的平衡因子只能是-1，0，1，只要二叉樹上一個結(jié)點的平衡因子的絕對值大于1，則該二叉樹是不平衡的。12. 哈希表(Hash Table)：根據(jù)設(shè)定的哈希函數(shù)與處理沖突的方法將一組關(guān)鍵字映射到一個有限的連續(xù)的地址集上，并以關(guān)鍵字在越來越集中的像作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映射過程稱為哈希造表或散列，所得的存儲位置稱哈希地址或散列地址。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) 隨機數(shù)法：選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的哈希地址。15. 常用的處理沖突的方法：a) 開放定址法：其中增量序列有線性探測再散列，二次探測再散列，隨機探測再散列。b) 再哈希法：即在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。c) 鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。d) 建立一個公共溢出區(qū)。16. 二次聚集：指在處理沖突過程中發(fā)生的兩個第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現(xiàn)象。17. 裝填因子：是表中填入的記錄數(shù)與哈希表的長度之商，哈希表的平均查找長度是裝填因子的函數(shù)，不是規(guī)模n的函數(shù)。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)部排序：指的是待排序記錄放在計算機隨機存儲器中進行的排序過程b) 外部排序：指的是待排序記錄的數(shù)量很大，以致內(nèi)在一次不能容納全部記錄