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

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

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

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

4、1.22.23.24.25.26.27.28.29.30.雙向鏈表線性表采用鏈?zhǔn)酱鎯r，每個結(jié)點除一個數(shù)據(jù)域外，包含兩個指針域，一個指 向該結(jié)點的直接后繼，一個指向該結(jié)點的直接前驅(qū)，這種方式構(gòu)成的鏈表，即 為雙向鏈表。希爾排序是插入排序的一種，又叫縮小增量排序，先按增量進行分組，組內(nèi)插入排序， 然后每次縮短增量，再進行分組和組內(nèi)插入排序，直到增量為1時,進行最后 一次排序止。完全圖任何一個有N個結(jié)點的無向圖，若其邊數(shù)為N(N-1)/2,則這個無向圖就是完 全圖有向完全圖任何一個有N個結(jié)點的有向圖，若其弧個數(shù)為N(N-1)個,則這個有向圖就是 有向完全圖。廣度遍歷按層次編歷方式，從某一點V0開始

5、遍歷它的所有鄰接點 V1,V2,再依次 訪問V1,V2.的所有未被訪問過的鄰接點，直到所有的點均遍歷完成 關(guān)鍵字?jǐn)?shù)據(jù)元素的某個數(shù)據(jù)項的值，用它可以標(biāo)識列表的一個或一組元素。串串是字符線性的有限集合。子串串中任意個連續(xù)的字符組成的子序列稱作該串的子串。棧是一種受限線性表，是插入和刪除操作在同一端進行的，是后進先出的線性 表。樹樹是n(n=0)個結(jié)點的有限集。在任意一棵非空樹中：(1)有且僅有一個特殊的稱為根的結(jié)點；當(dāng)n1時,其余結(jié)點可分成m(m0個互不相交的有限集T1,T2,.,Tm,其 中每一個集合本身又是一棵樹，并且稱為根的子樹。二叉樹二叉樹是每個結(jié)點至多有兩個孩子結(jié)點的一種樹。其中兩個孩子

6、結(jié)點分別被 稱為左孩子結(jié)點和右孩子結(jié)點。子孫子孫結(jié)點以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。孩子結(jié)點與雙親結(jié)點樹中某個結(jié)點的子樹的根結(jié)點稱為該結(jié)點的孩子結(jié)點。相反，稱該結(jié)點為孩子結(jié)點的雙親結(jié)點。結(jié)點的度樹的某個結(jié)點的分支(子樹)個數(shù)叫做該結(jié)點的度。樹的度樹的度是樹中所有結(jié)點的最大度數(shù)。31. 平衡因子結(jié)點的左子樹深度與右子樹深度之差。32. 生成樹一個連通圖的生成樹是指一個極小連通子圖，它含有圖中的全部頂點,N-1條 邊。33. 滿二叉樹深度為K,且有2K -1個結(jié)點的二叉樹34. 物理結(jié)構(gòu)（存儲結(jié)構(gòu)）物理結(jié)構(gòu)又稱為數(shù)據(jù)的存儲結(jié)構(gòu)，是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的映像（表示），即數(shù)據(jù)結(jié)

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

8、個結(jié)點的祖先是指從根結(jié)點到該結(jié)點的路徑上的所有結(jié)點。42. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)元素的集合以及定義在該集合上的關(guān)系。43. 模式匹配子串的定位操作稱作串的模式匹配。44. 單循環(huán)鏈表是單鏈表的另一種形式，它是一個首尾相接的鏈表，表中最后一個結(jié)點的指 針域由null改為指向頭結(jié)點或線性表的第一個結(jié)點，整個鏈表形成了一個 環(huán).45. 線索在二叉樹的存儲結(jié)構(gòu)中，必有N+1個空域，利用這些空域存放某種遍歷的 前驅(qū)和后繼，其中指向前驅(qū)和后繼的指針叫線索.46. 圖圖是頂點與邊的集合。一般表示為一個二元組，即,圖G=（V,E）,各個頂點之間 是多對多的關(guān)系。47. 折半查找對于順序存儲的有序表，先取中間

9、位置的記錄關(guān)鍵字與所給的關(guān)鍵字進行比較,若相等，則查找成功，否則,若給定的關(guān)鍵字比中間的關(guān)鍵字大，在原表的 后半部分比較，反之,在原表的前半部分比較，如此反復(fù)，逐步縮小范圍，直到 找到為止,或找不到，最后查找范圍為空.48. 最小生成樹在圖G的所有生成樹中，樹權(quán)值最小的那棵生成樹，稱作最小生成樹.49. 廣度優(yōu)先搜索（BFS）首先訪問出發(fā)點v,接著依次訪問v的所有鄰接點w1,w2,wt,然后再依次 訪問與wl,w2,wt鄰接的所有未曾訪問過的頂點。依此類推，直至圖中所 有和源點v有路徑相通的頂點都已訪問到為止。 此時從v開始的搜索過程結(jié) 束。（若G是連通圖，則遍歷完成；否則,在圖C中另選一個尚

10、未訪問的頂點作為新 源點繼續(xù)上述的搜索過程，直至G中所有頂點均已被訪問為止。）50. 完全二叉樹對滿二叉樹的結(jié)點從上到下，從左到右進行依次進行編號，若有一棵二叉樹 的每一個結(jié)點都與深度為 K的滿二叉樹中編號都一一對應(yīng)時，只是最后一層 不滿,稱做完全二叉樹.51. 前綴編碼任何一個字符的編碼都不是另一個字符編碼的前綴，這種編碼叫做前綴編碼.52. 廣義表是零個或多個原子表所構(gòu)成的有序序列.53. 線索二叉樹利用二叉樹的一些空閑指針指向該結(jié)點的前驅(qū)或后繼，這種指針叫線索，線索后了的二叉樹，稱為線索二叉樹.54. 樹的高度樹中所有結(jié)點的層次的最大值.55. 堂兄弟同一層上不同雙親的結(jié)點，互稱堂兄弟.

11、56. 葉子結(jié)點度為0的結(jié)點，即沒有后繼的結(jié)點.57. 森林M棵互相不相交的樹構(gòu)成的集合，將一棵非空樹的根結(jié)點刪除，樹就變成了森 林.58. 樹的路徑長度樹中每個結(jié)點到根結(jié)點的路徑長度之和.59. 樹的帶權(quán)路徑長度（WPL）樹中所有葉子結(jié)點的帶權(quán)路徑長度之和.60. 哈夫曼樹設(shè)有N個權(quán)值的結(jié)點構(gòu)造一棵有N個葉子結(jié)點的二叉樹，其中WPL最小的那 棵樹,為哈夫曼樹.61. 哈夫曼編碼一般以N種字符出現(xiàn)的頻率做權(quán)值,構(gòu)造哈付曼樹,左孩子邊做0,右孩子邊 做1,那么從根到葉子結(jié)點經(jīng)過的0和1序列,構(gòu)成了哈夫曼編碼.62. 圖中頂點的度頂點V的度是圖中和頂點V相關(guān)聯(lián)的邊的數(shù)目。包括入度和出度兩種。63.

12、 子圖圖G=（V,E）與圖G仁（V1,E1）,若V1包含于V,且E1包含于E,則G1是G的子 圖。64. 連通圖對于無向圖，若V1到V2有路徑，稱V1V2是連通的，若圖中任意兩點都是連通 的,則稱該無向圖是連通圖。65. 網(wǎng)圖的弧或邊有與它相關(guān)的有意義的數(shù)，稱作權(quán),帶有權(quán)值的圖稱作網(wǎng)。66. 深度優(yōu)先搜索（DFS）類似樹的先序遍歷，在圖中任選一個頂點作為出發(fā)頂點V0,訪問V0后,依次從V0的沒被訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索。直到與V0所連通的所有頂點均被訪問。如果，此時圖中還有頂點尚未訪問，則從剩余的頂點中再任 選一個頂點作為出發(fā)頂點V0,重復(fù)上述過程，直到圖中全部頂點均被訪問為止。67

13、. 簡單回路除了第一個頂點和最后一個頂點之外，其余頂點均不相同的回路稱為簡單回 路。68. 簡單路徑在用一個頂點序列表示一條路徑時，若序列中沒有相同的頂點重復(fù)出現(xiàn)，則稱其為簡單路徑。69. 查找根據(jù)給定的關(guān)鍵字值，在特定的表中，確定一個其關(guān)鍵字與給定值相同的數(shù) 據(jù)元素,并返回該數(shù)據(jù)元素在列表中的位置。這個過程叫查找。70. 平均查找長度（ASL）為確定數(shù)據(jù)元素在表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的數(shù)學(xué)期 望值,成為查找算法在查找成功的平均查找長度。71. 二叉排序樹它或是一棵空樹，或是有下面性質(zhì)的樹：若左或右子樹不空，左子樹所有結(jié)點 值小于根結(jié)點，而右子樹所有結(jié)點值大于根結(jié)點的值 ，其

14、左右子樹也是二叉 排序樹。72. 順序查找對于給定的關(guān)鍵字 K,從線性表的第一個（或最后一個）元素開始，依次向后 （或前）與元素的關(guān)鍵字比較，若某個記錄的關(guān)鍵字與K相等,查找成功，否則 失敗。73. 平衡二叉樹或是一棵空樹，或左右子樹高度差的絕對值小于等于 1而且，左右子樹也是平 衡二叉樹。74. 插入排序在一個已排好序的基礎(chǔ)上，每一步將下一個待排序記錄插到已排好記錄的子 集上,使之重新有序，直到所有待排記錄插完為止。75. 分塊查找（索引查找）分塊查找以前兩個為基礎(chǔ)，將待查記錄分成若干塊，每塊的關(guān)鍵字無序，但每 塊的關(guān)鍵字的最大值有序，查找時,先查找到待查記錄所在的塊，再在塊內(nèi)進行順序查找。

15、找塊時，即可以用折半查找，也可用順序查找。76. 拓?fù)渑判蛴赡硞€集合上的偏序集得到該集合上的一個全序，這個操作叫做拓?fù)渑判颉?7. 歸并排序?qū)蓚€或兩個以上的有序表合并成一個新的有序表 ，開始將每個元素當(dāng)成是 一個個單獨的有序表，逐漸表個數(shù)以原來一半的速度遞減 ，每個表的長度卻 是原來長度的2倍增加,不斷重復(fù),直到最后是一個表，而表的長度是元素個 數(shù)為止。78. 排序根據(jù)關(guān)鍵字的遞減或遞增的次序，把文件中的各個記錄依次排列起來，可使 一個無序的數(shù)據(jù)元素序列變成一個有序的序列的操作。79. shell 排序它是插入排序的一種，又叫縮小增量排序，先按增量進行分組，組內(nèi)插入排序 然后每次縮短增量，再

16、進行分組和組內(nèi)插入排序，直到增量為1時,進行最后 一次排序止。80. 內(nèi)部排序指的是待排序記錄存放在計算機存儲器中進行的排序過程；81. 外部排序指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過 程中對外存進行訪問的排序過程。82. 不穩(wěn)定排序假設(shè)Ki=Kj(1 i n,1 j n,i工j),且在排序前的序列中Ri領(lǐng)先于Rj(即i vj)。若在排序后的序列中Rj領(lǐng)先于Ri ,則稱所用的排序方法是不穩(wěn)定的。83. 穩(wěn)定排序假設(shè)Ki=Kj(1 i n,1 j n,i工j),且在排序前的序列中Ri領(lǐng)先于Rj(即i vj)。若在排序后的序列中Ri仍領(lǐng)先于Rj,則稱所用的排序方法是穩(wěn)定

17、的84. 直接插入排序第1遍,將初始文件中的記錄R1看作有序子文件，將R2插入這個子文件中。 若R2的關(guān)鍵字小于R1的關(guān)鍵字，則R2插在R1的前面，否則R2插在R1的后 面。第2遍，將R3插入前面的兩個記錄的有序子文件中，得到3個記錄的有 序子文件。依此類推，繼續(xù)進行下去，直到將Rn插入到前面的n-1個記錄的 有序子文件中，最后得到n個記錄的有序文件。85. 氣泡排序法氣泡排序的過程很簡單。從第一記錄開始，相鄰的兩個記錄關(guān)鍵字進行比較， 若順序不對，立即交換，直至N-1個與第N個比較為止。得到一個最大(或最 小)的關(guān)鍵字記錄的結(jié)果位置。86. 選擇排序選擇排序是每一趟在 n-i+1(i= 1,2,3n-1)個記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第i個記錄。其中最簡單的是簡單選擇排序87. 快速排序快速排序的基本思想是把當(dāng)前待排序的記錄，存放到整個表排好序后，它應(yīng)當(dāng)在的最終位置上。將原來的待排序表分割成兩部分，其中一部分表中的關(guān)鍵字均比另一部分表中的關(guān)鍵字小。然后，分別對兩部分表用同樣的方式進 行排序,直到整個表排好序。88. 堆排序首先將根結(jié)點的記錄與當(dāng)前樹中具有最大序號的記錄交換，把交換后具有最 大序號的記錄輸出，得到一個排序的結(jié)果。這時的樹不再是堆樹，排序暫