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

數(shù)據(jù)結(jié)構(gòu)的關(guān)系和操作等的科學(xué)。數(shù)據(jù)(data)被計算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素(dataelement)行考慮和處理。數(shù)據(jù)對象(dataobject)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)(datastructure)合。根據(jù)數(shù)據(jù)結(jié)構(gòu)之間關(guān)系的不同特性，通常有下列4結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。抽象數(shù)據(jù)類型(ADT)：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作，有“數(shù)據(jù)抽象”和“數(shù)據(jù)封裝”兩個重要特性。算法(algorithm)是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每五個特性。算法設(shè)計的要求：正確性、可讀性、健壯性、效率與低存儲需求。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)T(n)=O(f(n))nf(n)漸近時間復(fù)雜度，簡稱時間復(fù)雜度。線性表：是n個數(shù)據(jù)元素的有限序列，有順序存儲和鏈?zhǔn)酱鎯煞N表示形式。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)針域。循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點(diǎn)是表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個鏈表形成一個環(huán)。雙向鏈表是指有兩個指針域，其一指向直接后繼，另一指向直接前趨。棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義先出表。1. 隊列在隊列中，允許插入的一端稱做隊尾，允許刪除的一端稱做隊頭。串(string)中的位置。并且各個對應(yīng)位置的字符都相等時才相等。樹(tree)是指n(n>=0)有且僅有一個特定的稱為根。2）當(dāng)n>1時，其余結(jié)點(diǎn)可分為m(m>0)個互不相交的有限集，其中每一個集合本身又是一棵樹。度。度為0葉子或終端結(jié)點(diǎn)樹的度孩子雙親稱兄弟結(jié)點(diǎn)的祖先1子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點(diǎn)在第l層，則其子樹在第l+1的深度或高度。無序樹。森林(forest)m(m>0)棵互不相交的樹的集合。二叉樹Tree)并且二叉樹的子樹有左右之分，其次序不能任意顛倒。k2K-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。深度為kn個結(jié)點(diǎn)的二k1n時，稱之為完全二叉樹。遍歷二叉樹：指按某條搜索路徑巡訪樹上每個結(jié)點(diǎn)，使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。有先序遍歷、中序遍歷、后序遍歷三種。若結(jié)點(diǎn)有左子樹，則其(右)孩子，否則令（后繼從樹中一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支構(gòu)成這兩個結(jié)點(diǎn)之間的路徑目稱做路徑長度。樹的路徑長度是從樹根到每一個結(jié)點(diǎn)的路徑長度之和。樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。假設(shè)有n{w,w,}，試構(gòu)造一棵有n個葉子結(jié)點(diǎn)的二叉樹，每個葉子結(jié)1 2 n點(diǎn)帶樹為w,則其中帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹。i頂點(diǎn)vwv弧尾，稱w為弧頭有向圖vw邊向圖。有n*(n-1)/2完全圖。具有n(n-1)有向完全圖，稀疏圖稠密圖權(quán)網(wǎng)。v是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(V)。v路徑的長度是路徑上邊回路或環(huán)。序列中不重復(fù)出簡單路徑簡單回路或簡單環(huán)。G中，如果從頂點(diǎn)v有路徑，則稱v是連通的。如果對于圖中任意兩個頂點(diǎn)v、v∈V,v和v都是連通的，則稱G是連通圖。所謂連通分量指的是i j i j無向圖中的極大連通子圖。G中，如果對于每一對v、v∈V,v≠vvvvv

都存在路徑，i j i j i j j i則稱G是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱做有向圖的強(qiáng)連通分量。連通圖的生成樹棵樹的n-1n個頂點(diǎn)的生成樹有且僅有n-1條邊。如果一個圖有n個頂點(diǎn)和小于n-1如果它多于n-1條邊，則一定有環(huán)。但是，有n-1條邊的圖不一定是生成樹。如果一個有向圖恰有一個頂點(diǎn)的入度為01有向樹。一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。2圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表、逆鄰接表以及十字鏈表等。圖的遍歷通常有兩條遍歷圖的路徑：深度優(yōu)先搜索：類似于樹的先序遍歷，假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次從vv有路徑相的頂點(diǎn)做為起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。廣度優(yōu)先搜索：類似于村的層序遍歷，假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之有頂點(diǎn)都被訪問到為止。假若在刪去頂點(diǎn)v以及和v以上的邊通分量，則稱頂點(diǎn)v關(guān)節(jié)點(diǎn)連通圖。若在連通圖上至少刪去k連通度。這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上頂點(diǎn)的弧。拓?fù)渑判?Topological序。AOV-網(wǎng)的網(wǎng)。AOE-網(wǎng)：指用邊表示活動的網(wǎng)，是一個帶權(quán)的有向無環(huán)圖，其中，頂點(diǎn)表示事件弧表示活動，權(quán)表示活動持續(xù)的時間，通常一個AOE-網(wǎng)可用來估算工程的完成時間。在正常的情況（無環(huán)）下，網(wǎng)中只有一個入度為零的點(diǎn)，稱做源點(diǎn)匯點(diǎn)。在AOE-關(guān)鍵路徑活動。查找表（SearchTable：是由同一類型的數(shù)據(jù)元素構(gòu)成的集合。若對查找表只作靜態(tài)查找表(StaticSearch中同時插入查找表中不存在的數(shù)據(jù)元素，則稱此類表為動態(tài)查找表(DynamicSearchTable)。關(guān)鍵字（Key主關(guān)鍵字(PrimaryKey)，次關(guān)鍵字(SecondaryKey)。查找成功，此時查找的結(jié)果可給出一個“空”記錄或“空”指針。順序查找(SequentialSearch)的查找過程為：從表中最后一個記錄開始，逐個進(jìn)行記錄平均查找長度(AverageSearchLength)：為確定記錄在查找表中的位置，需和3給定值進(jìn)行比較的關(guān)鍵字的個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度。折半查找(BinarySearch)后逐步縮小范圍直到找到或找不到該記錄為止。判定樹：樹中每個結(jié)點(diǎn)表示表中一個記錄，結(jié)點(diǎn)中的值為該記錄在表中的位置，通常稱這個查找過程的二叉樹稱為判定樹不超過樹的深度。次優(yōu)查找樹(NearlyOptimalSearch帶權(quán)內(nèi)路徑長度PH值在所有具有同樣權(quán)值的二叉樹中近似為最小。二叉排序樹(BinarySortTree)樹:若它的左子樹不空，則左子村上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。它的左、右子樹也分別為二叉排序樹。平衡二叉樹(BalancedBinary。平衡因子BF(BalanceFactor)：為該結(jié)點(diǎn)的左子樹深度減去它的右子樹的深度，1，則該二叉樹是不平衡的。哈希表(HashTable)：根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法將一組關(guān)鍵字映射到一個有限的連續(xù)的地址集上，并以關(guān)鍵字在越來越集中的像作為記錄在表中的存儲位地址或散列地址。沖突(Collision)：對不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱為沖突，具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱做同義詞。常用的構(gòu)造哈希函數(shù)的方法有：直接定址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。r先知道的，則可取關(guān)鍵字的若干位組成哈希地址。平方取中法：取關(guān)鍵字平方的后的中間幾位做為哈希地址。m的數(shù)p除后的余數(shù)為哈希地址。隨機(jī)數(shù)法：選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址。常用的處理沖突的方法：生。鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。建立一個公共溢出區(qū)。二次聚集繼哈希地址的現(xiàn)象。裝填因子：是表中填入的記錄數(shù)與哈希表的長度之商，哈希表的平均查找長度是裝填因子的函數(shù)，不是規(guī)模n的函數(shù)。排序(Sorting)：是指將一個數(shù)據(jù)元素的任意序列重新排列成一個按關(guān)鍵字有序的序4列。R=R,且在排序前的序列中RR，若在排序后的序列中R仍領(lǐng)先于R，則i j i j i j稱所用的排序方法是穩(wěn)定的，反之稱所用的排序方法是不穩(wěn)定的。兩大類：內(nèi)部排序：指的是待排序記錄放在計算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程外部排序排序過程中尚需對外存進(jìn)行訪問的排序過程。直接插入排序(StraightInsertionSort)：它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數(shù)增1的有序表。希爾排序(Shell’sSort)：又稱縮小增量排序，基本思想是先將整個記錄序列分進(jìn)行一次直接插入排序。起泡排序(BubbleSort)：首先將第一個記錄的關(guān)鍵字同第二個記錄的關(guān)鍵字進(jìn)行n-1個記錄和第n個記錄的關(guān)鍵字進(jìn)行比較快速排序(QuickSort)：它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的快