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

11.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間物的符號表示，在計算機科學(xué)中是指所有以輸入到計算機中并被計算機程序處理的符號的總稱。3.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進4.數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。5.數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(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ù)類型：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作，有“數(shù)據(jù)抽象”與“數(shù)據(jù)封裝”兩個重要特性。8.算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每TnOfnn率與f(n)的增長率相同，稱做算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。n表示形式。括兩個域，其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲直接后繼存儲位置的域稱為指域。3.循環(huán)鏈表是另一種形式的鏈式存儲結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。4.雙向鏈表是指有兩個指針域，其一指向直接后繼，另一指向直接前趨。棧是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義尾，允許刪除的一端稱做隊頭。列稱該串的子串，通常稱字符在序列中的序號為該字符在序列中的序號為該字符的在串中的位置。并且各個對應(yīng)位置的字符都相等時才相等。的稱為根。2)當n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集，其中每一個集合本身又是一棵樹。2.樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點擁有的子樹稱為結(jié)點的度。度為0的結(jié)點稱為葉子或終端結(jié)點。樹的度是樹內(nèi)各結(jié)點的度的最大值。結(jié)點的子樹的根稱為該結(jié)點的孩子，相應(yīng)的該結(jié)點稱為孩子的雙親。同一個雙親的孩子之間互2子樹中的任一結(jié)點都稱為該結(jié)點的子孫。3.結(jié)點的層次從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點在第l層，m6.二叉樹(是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。稱之為完全二叉樹。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)路徑長度之與。點帶樹為wi,則其中帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹。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)。4.無向圖G=(V,{E})中從點v到頂點v’的路徑是一個頂點序列，路徑的長度是路徑上邊或弧的數(shù)目。第一個頂點與最后一個頂點相同的路徑稱為回路或環(huán)。序列中不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除了第一個頂點與最后一個頂點之外，其余頂點不重復(fù)出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。5.在無向圖G中，如果從頂點v到頂點v’有路徑，則稱v與v’是連通的。如果對于圖中任意兩個頂點vi、vj∈與都是連通的，則稱是連通圖。所謂連通分量指的是無向圖中的極大連通子圖。G圖。有向圖中的極大強連通子圖稱做有向圖的強連通分量。7.一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一的生成樹有且僅有n-1條邊。如果一個圖有n個頂點與小于n-1條邊，則是非連通圖，如果它多于n-1條邊，則一定有環(huán)。但是，有n-1條邊的圖不一定是生成樹。向樹。若干棵不相交的有向樹的弧。39.圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表、逆鄰接表以及十字鏈表等。索：類似于樹的先序遍歷，假設(shè)從圖中某頂點v出發(fā)，在訪問了v之通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點做為起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。2)廣度優(yōu)先搜索：類似于村的層序遍歷，假設(shè)從圖中某頂點v出發(fā)，在訪問了v之于后訪問的頂點的鄰接點，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復(fù)上述過程，直到圖中所有頂點都被訪問到為止。vv個關(guān)節(jié)點。一個沒有關(guān)節(jié)點的圖稱為重連通圖。若在連通圖上至少刪去k個頂點才能破壞圖的連通性，則稱此圖的連通度為k。這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上頂點的弧。14.拓撲排序：指由某個集合上的一個偏序得到該集合上的一個全15.網(wǎng)：指用頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖稱為頂點表示活動16.網(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.查找表()：是由同一類型的數(shù)據(jù)元素構(gòu)成的集合。若對查找表只作查找操作，則稱此類查找表為靜態(tài)查找表，若在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，則稱此類表為動態(tài)查找表2.關(guān)鍵字()：是數(shù)據(jù)元素或記錄中某個數(shù)據(jù)項的值，用它可能標識一個數(shù)據(jù)元素，若此關(guān)鍵字可以惟一地標識一個記錄，則稱此關(guān)鍵字為主關(guān)鍵字，反之，稱用以識別若干記錄的關(guān)鍵為次關(guān)鍵字。3.查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等給定值的記錄或數(shù)據(jù)元素，或指示該記錄在查找表中的位置，若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找不查找不成功。5.平均查找長度：為確定記錄在查找表中的位置，需與4給定值進行比較的關(guān)鍵字的個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度。6.折半查找的查找過程：先確定待查記錄在有序表中所在范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。7.判定樹：樹中每個結(jié)點表示表中一個記錄，結(jié)點中的值為該記錄在表中的位置，通常稱這個查找過程的二叉樹稱為判定樹。折半查找法在成功時進行比較的關(guān)鍵字個數(shù)最多8.次優(yōu)查找樹：構(gòu)造一棵二叉樹，使這棵二叉樹的PH9.二叉排序樹：或者是一棵空樹，或者是具有下列性質(zhì)的二叉a)若它的左子樹不空，則左子村上所有結(jié)點的值均小于它的根結(jié)點的值。b)若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值。c)它的左、右子樹也分別為二叉排序樹。10.平衡二叉樹：又稱AVL樹，它或者是一棵空樹，或者是11.平衡因子：為該結(jié)點的左子樹深度減去它的右子樹的深度，則平衡二叉樹上所有結(jié)點的平衡因子只能是-1，0，1，只要二叉樹上一個結(jié)點的平衡因12.哈希表：根據(jù)設(shè)定的哈希函數(shù)與處理沖突的方法將一組關(guān)鍵字映射到一個有限的連續(xù)的地址集上，并以關(guān)鍵字在越來越集中的像作為記錄在表中的存儲位地址或散列地址。13.沖突：對不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱為沖突，具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱做同義詞。14.常用的構(gòu)造哈希函數(shù)的方法有：a鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。先知道的，則可取關(guān)鍵字的若干位組成哈希地址。c平方取中法：取關(guān)鍵字平方的后的中間幾位做為哈希地址。15.常用的處理沖突的方法：a。c同義詞的記錄存儲在同一線性鏈表中。d)建立一個公共溢出區(qū)。16.二次聚集：指在處理沖突過程中發(fā)生的兩個第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現(xiàn)象。17.裝填因子：是表中填入的記錄數(shù)與哈希表的長度之商，哈希表的平均查找長度是裝填因子的函數(shù)，不是規(guī)模n的函數(shù)。1.排序：是指將一個數(shù)據(jù)元素的任意序列重新排列成一個按關(guān)鍵字有序的序5j稱所用的排序方法是穩(wěn)定的，反之稱所用的排序方法是不穩(wěn)定的。a)內(nèi)部排序：指的是待排序記錄放在計算機隨機存儲器中進行的排序過程b)外部排序：指的是待排序記錄的數(shù)量很大，以致內(nèi)在一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。4.直接插入排序：它的基本操作是將一個記錄插入到5.希爾排序’：又稱縮小增量排序，基本思想是先將整個記錄序列分進行一次直接插入排序。6.起泡排序：首先將第一個記錄的關(guān)鍵字同第二個記錄的關(guān)鍵字進行較為止。判別起泡排序結(jié)束的條件應(yīng)該是在一趟排序