數(shù)據(jù)結(jié)構(gòu)名詞解釋

1、1.數(shù)據(jù)數(shù)據(jù)是描述客觀事物的符號(hào),是能夠被計(jì)算機(jī)輸入,識(shí)別,處理的各種符號(hào),是計(jì)算機(jī)化的信息。2.數(shù)據(jù)項(xiàng)數(shù)據(jù)不可分割的最小單位,一個(gè)元素由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。3.數(shù)據(jù)元素它是組成數(shù)據(jù)的基本單位,是數(shù)據(jù)集合中的個(gè)體,在計(jì)算機(jī)程序中,通常作為一個(gè)整體進(jìn)行考慮和處理。4.數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個(gè)子集。5.數(shù)據(jù)處理是指對(duì)數(shù)據(jù)進(jìn)行查找,插入,刪除,合并,排序,統(tǒng)計(jì)以及簡單計(jì)算等的操作過程。6.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示(即數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)),并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算,設(shè)計(jì)出相應(yīng)的算法,且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是

2、原來的結(jié)構(gòu)類型。7.數(shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。8.抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性,而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。.算法解決一個(gè)問題的方法和步驟。10.時(shí)間復(fù)雜度T(N)O(F(N),它表示隨問題規(guī)模增大,算法執(zhí)行時(shí)間增長率與F(N)的增長率相同,F(N)算法的時(shí)間復(fù)雜性。11.原地工作算法執(zhí)行時(shí),若額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù),則稱此算法為原地工作。12.線性表一種數(shù)據(jù)結(jié)構(gòu),是N(N>=0)個(gè)同質(zhì)元素的有限序列,除首尾元素外,每個(gè)元素有唯一的前驅(qū)和唯一的后繼。13.隊(duì)

3、列是一種受限線性表,是先進(jìn)先出的線性表14.循環(huán)隊(duì)列在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中,把存儲(chǔ)空間的首尾邏輯上相連,構(gòu)成一個(gè)環(huán),使得存儲(chǔ)空間上只要有空余的地址,就可以繼續(xù)進(jìn)行入隊(duì)列操作,極大利用了物理空間。用頭部和尾部兩個(gè)指示器表示隊(duì)列頭和隊(duì)列尾,插入在尾部進(jìn)行,刪除在頭部進(jìn)行。15.單鏈表每一個(gè)數(shù)據(jù)元素,都需用兩部分來存儲(chǔ)：一部分用于存放數(shù)據(jù)元素值,稱為數(shù)據(jù)域；另一部分用于存放直接后繼結(jié)點(diǎn)的地址(指針),稱為指針域,元素的存儲(chǔ)空間可以連續(xù),也可以是不連續(xù)的。而數(shù)據(jù)元素之間的邏輯關(guān)系由指針域來確定。16.雙向鏈表線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí),每個(gè)結(jié)點(diǎn)除一個(gè)數(shù)據(jù)域外,包含兩個(gè)指針域,一個(gè)指向該結(jié)點(diǎn)的直接后繼,一個(gè)指

4、向該結(jié)點(diǎn)的直接前驅(qū),這種方式構(gòu)成的鏈表,即為雙向鏈表。17.希爾排序是插入排序的一種,又叫縮小增量排序,先按增量進(jìn)行分組,組內(nèi)插入排序,然后每次縮短增量,再進(jìn)行分組和組內(nèi)插入排序, 直到增量為1時(shí),進(jìn)行最后一次排序止。18.完全圖任何一個(gè)有N個(gè)結(jié)點(diǎn)的無向圖,若其邊數(shù)為N(N-1)/2,則這個(gè)無向圖就是完全圖19.有向完全圖任何一個(gè)有N個(gè)結(jié)點(diǎn)的有向圖,若其弧個(gè)數(shù)為N(N-1)個(gè),則這個(gè)有向圖就是有向完全圖。20.廣度遍歷按層次編歷方式,從某一點(diǎn)V0開始遍歷它的所有鄰接點(diǎn)V1,V2,再依次訪問V1,V2.的所有未被訪問過的鄰接點(diǎn),直到所有的點(diǎn)均遍歷完成21.關(guān)鍵字?jǐn)?shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值,用它可以

5、標(biāo)識(shí)列表的一個(gè)或一組元素。22.串串是字符線性的有限集合。23.子串串中任意個(gè)連續(xù)的字符組成的子序列稱作該串的子串。24.棧是一種受限線性表,是插入和刪除操作在同一端進(jìn)行的,是后進(jìn)先出的線性表。25.樹樹是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：(1)有且僅有一個(gè)特殊的稱為根的結(jié)點(diǎn); (2)當(dāng)n>1時(shí),其余結(jié)點(diǎn)可分成m(m>0)個(gè)互不相交的有限集T1,T2,.,Tm,其中每一個(gè)集合本身又是一棵樹,并且稱為根的子樹。26.二叉樹二叉樹是每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子結(jié)點(diǎn)的一種樹。其中兩個(gè)孩子結(jié)點(diǎn)分別被稱為左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。27.子孫子孫結(jié)點(diǎn)以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)

6、都稱為該結(jié)點(diǎn)的子孫。28.孩子結(jié)點(diǎn)與雙親結(jié)點(diǎn)樹中某個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。相反,稱該結(jié)點(diǎn)為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。29.結(jié)點(diǎn)的度樹的某個(gè)結(jié)點(diǎn)的分支(子樹)個(gè)數(shù)叫做該結(jié)點(diǎn)的度。30.樹的度樹的度是樹中所有結(jié)點(diǎn)的最大度數(shù)。31.平衡因子結(jié)點(diǎn)的左子樹深度與右子樹深度之差。32.生成樹一個(gè)連通圖的生成樹是指一個(gè)極小連通子圖,它含有圖中的全部頂點(diǎn),N-1條邊。33.滿二叉樹深度為K,且有2K -1個(gè)結(jié)點(diǎn)的二叉樹34.物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))物理結(jié)構(gòu)又稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映像(表示),即數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方法。35.線索在二叉樹中,利用空余的指針指向二叉樹某種

7、遍歷方式的結(jié)點(diǎn)的前驅(qū)和后繼,這種指向前驅(qū)和后繼的指針,叫線索。36.線索二叉樹對(duì)二叉樹以某種次序進(jìn)行遍歷并加上線索的過程叫做線索化。線索化了的二叉樹稱為線索二叉樹。37.廣義表廣義表簡稱表,是零個(gè)或多個(gè)原子表所組成的有限序列。38.強(qiáng)連通分量有向圖的極大強(qiáng)連通子圖,稱為有向圖的強(qiáng)連通分量。39.結(jié)點(diǎn)的帶權(quán)路徑長度該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。40.插入排序在一個(gè)已排好序的記錄子集的基礎(chǔ)上,每一步將下一個(gè)待排序的記錄有序地插入到已排好序記錄的子集上,直到將所有待排記錄全部插入為止。41.祖先一個(gè)結(jié)點(diǎn)的祖先是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。42.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)元素的集合

8、以及定義在該集合上的關(guān)系。43.模式匹配子串的定位操作稱作串的模式匹配。44.單循環(huán)鏈表是單鏈表的另一種形式,它是一個(gè)首尾相接的鏈表,表中最后一個(gè)結(jié)點(diǎn)的指針域由null改為指向頭結(jié)點(diǎn)或線性表的第一個(gè)結(jié)點(diǎn),整個(gè)鏈表形成了一個(gè)環(huán)45.線索在二叉樹的存儲(chǔ)結(jié)構(gòu)中,必有個(gè)空域,利用這些空域存放某種遍歷的前驅(qū)和后繼,其中指向前驅(qū)和后繼的指針叫線索46.圖圖是頂點(diǎn)與邊的集合。一般表示為一個(gè)二元組,即,圖G=(V,E),各個(gè)頂點(diǎn)之間是多對(duì)多的關(guān)系。47.折半查找對(duì)于順序存儲(chǔ)的有序表,先取中間位置的記錄關(guān)鍵字與所給的關(guān)鍵字進(jìn)行比較,若相等,則查找成功,否則,若給定的關(guān)鍵字比中間的關(guān)鍵字大,在原表的后半部分比較,

9、反之,在原表的前半部分比較,如此反復(fù),逐步縮小范圍,直到找到為止,或找不到,最后查找范圍為空48.最小生成樹在圖G的所有生成樹中,樹權(quán)值最小的那棵生成樹,稱作最小生成樹49.廣度優(yōu)先搜索(BFS)首先訪問出發(fā)點(diǎn)v,接著依次訪問v的所有鄰接點(diǎn)w1,w2,wt,然后再依次訪問與wl,w2,wt鄰接的所有未曾訪問過的頂點(diǎn)。依此類推,直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)都已訪問到為止。此時(shí)從v開始的搜索過程結(jié)束。(若G是連通圖,則遍歷完成;否則,在圖C中另選一個(gè)尚未訪問的頂點(diǎn)作為新源點(diǎn)繼續(xù)上述的搜索過程,直至G中所有頂點(diǎn)均已被訪問為止。)50.完全二叉樹對(duì)滿二叉樹的結(jié)點(diǎn)從上到下,從左到右進(jìn)行依次進(jìn)行編

10、號(hào),若有一棵二叉樹的每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)都一一對(duì)應(yīng)時(shí),只是最后一層不滿,稱做完全二叉樹.51.前綴編碼任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴,這種編碼叫做前綴編碼.52.廣義表是零個(gè)或多個(gè)原子表所構(gòu)成的有序序列.53.線索二叉樹利用二叉樹的一些空閑指針指向該結(jié)點(diǎn)的前驅(qū)或后繼,這種指針叫線索,線索后了的二叉樹,稱為線索二叉樹.54.樹的高度樹中所有結(jié)點(diǎn)的層次的最大值.55.堂兄弟同一層上不同雙親的結(jié)點(diǎn),互稱堂兄弟.56.葉子結(jié)點(diǎn)度為 0 的結(jié)點(diǎn),即沒有后繼的結(jié)點(diǎn).57.森林M棵互相不相交的樹構(gòu)成的集合,將一棵非空樹的根結(jié)點(diǎn)刪除,樹就變成了森林.58.樹的路徑長度樹中每個(gè)結(jié)

11、點(diǎn)到根結(jié)點(diǎn)的路徑長度之和.59.樹的帶權(quán)路徑長度(WPL)樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和.60.哈夫曼樹設(shè)有N個(gè)權(quán)值的結(jié)點(diǎn)構(gòu)造一棵有N個(gè)葉子結(jié)點(diǎn)的二叉樹,其中WPL最小的那棵樹,為哈夫曼樹.61.哈夫曼編碼一般以N種字符出現(xiàn)的頻率做權(quán)值,構(gòu)造哈付曼樹,左孩子邊做0,右孩子邊做1,那么從根到葉子結(jié)點(diǎn)經(jīng)過的0和1序列,構(gòu)成了哈夫曼編碼.62.圖中頂點(diǎn)的度頂點(diǎn)V的度是圖中和頂點(diǎn)V相關(guān)聯(lián)的邊的數(shù)目。包括入度和出度兩種。63.子圖圖G=(V,E)與圖G1=(V1,E1),若V1包含于V,且E1包含于E,則G1是G的子圖。64.連通圖對(duì)于無向圖,若V1到V2有路徑,稱V1V2是連通的,若圖中任意兩點(diǎn)都

12、是連通的,則稱該無向圖是連通圖。65.網(wǎng)圖的弧或邊有與它相關(guān)的有意義的數(shù),稱作權(quán),帶有權(quán)值的圖稱作網(wǎng)。66.深度優(yōu)先搜索(DFS)類似樹的先序遍歷,在圖中任選一個(gè)頂點(diǎn)作為出發(fā)頂點(diǎn)V0,訪問V0后,依次從V0的沒被訪問過的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索。直到與V0所連通的所有頂點(diǎn)均被訪問。如果,此時(shí)圖中還有頂點(diǎn)尚未訪問,則從剩余的頂點(diǎn)中再任選一個(gè)頂點(diǎn)作為出發(fā)頂點(diǎn)V0,重復(fù)上述過程,直到圖中全部頂點(diǎn)均被訪問為止。67.簡單回路除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外,其余頂點(diǎn)均不相同的回路稱為簡單回路。68.簡單路徑在用一個(gè)頂點(diǎn)序列表示一條路徑時(shí),若序列中沒有相同的頂點(diǎn)重復(fù)出現(xiàn),則稱其為簡單路徑。69.查找根

13、據(jù)給定的關(guān)鍵字值,在特定的表中,確定一個(gè)其關(guān)鍵字與給定值相同的數(shù)據(jù)元素,并返回該數(shù)據(jù)元素在列表中的位置。這個(gè)過程叫查找。70.平均查找長度(ASL)為確定數(shù)據(jù)元素在表中的位置,需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的數(shù)學(xué)期望值,成為查找算法在查找成功的平均查找長度。71.二叉排序樹它或是一棵空樹,或是有下面性質(zhì)的樹：若左或右子樹不空,左子樹所有結(jié)點(diǎn)值小于根結(jié)點(diǎn),而右子樹所有結(jié)點(diǎn)值大于根結(jié)點(diǎn)的值,其左右子樹也是二叉排序樹。72.順序查找對(duì)于給定的關(guān)鍵字K,從線性表的第一個(gè)(或最后一個(gè))元素開始,依次向后(或前)與元素的關(guān)鍵字比較,若某個(gè)記錄的關(guān)鍵字與K 相等,查找成功,否則失敗。73.平衡二叉樹或是一棵

14、空樹,或左右子樹高度差的絕對(duì)值小于等于1而且,左右子樹也是平衡二叉樹。74.插入排序在一個(gè)已排好序的基礎(chǔ)上,每一步將下一個(gè)待排序記錄插到已排好記錄的子集上,使之重新有序,直到所有待排記錄插完為止。75.分塊查找(索引查找)分塊查找以前兩個(gè)為基礎(chǔ),將待查記錄分成若干塊,每塊的關(guān)鍵字無序,但每塊的關(guān)鍵字的最大值有序,查找時(shí),先查找到待查記錄所在的塊,再在塊內(nèi)進(jìn)行順序查找。找塊時(shí),即可以用折半查找,也可用順序查找。76.拓?fù)渑判蛴赡硞€(gè)集合上的偏序集得到該集合上的一個(gè)全序,這個(gè)操作叫做拓?fù)渑判颉?7.歸并排序?qū)蓚€(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表,開始將每個(gè)元素當(dāng)成是一個(gè)個(gè)單獨(dú)的有序表,逐漸表個(gè)

15、數(shù)以原來一半的速度遞減,每個(gè)表的長度卻是原來長度的2倍增加,不斷重復(fù),直到最后是一個(gè)表,而表的長度是元素個(gè)數(shù)為止。78.排序根據(jù)關(guān)鍵字的遞減或遞增的次序,把文件中的各個(gè)記錄依次排列起來,可使一個(gè)無序的數(shù)據(jù)元素序列變成一個(gè)有序的序列的操作。79.shell排序它是插入排序的一種,又叫縮小增量排序,先按增量進(jìn)行分組,組內(nèi)插入排序,然后每次縮短增量,再進(jìn)行分組和組內(nèi)插入排序, 直到增量為1時(shí),進(jìn)行最后一次排序止。80.內(nèi)部排序指的是待排序記錄存放在計(jì)算機(jī)存儲(chǔ)器中進(jìn)行的排序過程；81.外部排序指的是待排序記錄的數(shù)量很大,以致內(nèi)存一次不能容納全部記錄,在排序過程中對(duì)外存進(jìn)行訪問的排序過程。82.不穩(wěn)定排

16、序假設(shè)Ki=Kj(1in,1jn,ij),且在排序前的序列中Ri領(lǐng)先于Rj(即ij)。若在排序后的序列中Rj 領(lǐng)先于Ri ,則稱所用的排序方法是不穩(wěn)定的。83.穩(wěn)定排序假設(shè)Ki=Kj(1in,1jn,ij),且在排序前的序列中Ri領(lǐng)先于Rj(即ij)。若在排序后的序列中Ri仍領(lǐng)先于Rj,則稱所用的排序方法是穩(wěn)定的84.直接插入排序第1遍,將初始文件中的記錄R1看作有序子文件,將R2插入這個(gè)子文件中。若R2的關(guān)鍵字小于R1的關(guān)鍵字,則R2插在R1的前面,否則R2插在R1的后面。第2遍,將R3插入前面的兩個(gè)記錄的有序子文件中,得到3個(gè)記錄的有序子文件。依此類推,繼續(xù)進(jìn)行下去,直到將Rn插入到前面的

17、n-1個(gè)記錄的有序子文件中,最后得到n個(gè)記錄的有序文件。 85.氣泡排序法氣泡排序的過程很簡單。從第一記錄開始,相鄰的兩個(gè)記錄關(guān)鍵字進(jìn)行比較,若順序不對(duì),立即交換,直至N-1個(gè)與第N個(gè)比較為止。得到一個(gè)最大(或最小)的關(guān)鍵字記錄的結(jié)果位置。86.選擇排序選擇排序是每一趟在n-i+1(i= 1,2,3n-1)個(gè)記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。其中最簡單的是簡單選擇排序87.快速排序快速排序的基本思想是把當(dāng)前待排序的記錄,存放到整個(gè)表排好序后,它應(yīng)當(dāng)在的最終位置上。將原來的待排序表分割成兩部分,其中一部分表中的關(guān)鍵字均比另一部分表中的關(guān)鍵字小。然后,分別對(duì)兩部分表用同樣的方式進(jìn)行排序,直到整個(gè)表排好序。88.堆排序首先將根結(jié)點(diǎn)的記錄與當(dāng)前樹中具有最大序號(hào)的記錄交換,把交換后具有最大序號(hào)的記錄輸出,得到一個(gè)排序的結(jié)果。這時(shí)的樹不再是堆樹,排序暫