數(shù)據(jù)結(jié)構(gòu)必背名詞解釋&&簡答題匯總

數(shù)據(jù)結(jié)構(gòu)-名詞合集

第一章：緒論

1.數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物屬性的數(shù)、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。

2.數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

3.數(shù)據(jù)項：數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。是數(shù)據(jù)記錄中基本的，不可分的數(shù)據(jù)單位。

4.數(shù)據(jù)對象：數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

5.數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括3個方面的內(nèi)容：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對數(shù)據(jù)的運算。

6.數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)之間關系的描述，它與數(shù)據(jù)的存儲結(jié)構(gòu)無關，同一種邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)。歸納起來數(shù)據(jù)的邏輯結(jié)構(gòu)主要有四大類：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。

7.數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)又稱為存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示(又稱映像)。它包括數(shù)據(jù)元素的表示和關系的表示。當數(shù)據(jù)元素是由若干數(shù)據(jù)項構(gòu)成的時候，數(shù)據(jù)項的表示稱為數(shù)據(jù)域；比如一個鏈表節(jié)點，節(jié)點包含值域和指針域，這里節(jié)點可以看做一個數(shù)據(jù)元素，其中的值域和指針域都是這個數(shù)據(jù)元素的數(shù)據(jù)域。主要有順序存儲、鏈式存儲、索引存儲、散列存儲。

8.數(shù)據(jù)的運算：施加在數(shù)據(jù)上的運算包括運算的定義和實現(xiàn)。定義是針對邏輯結(jié)構(gòu)，指出運算的功能。實現(xiàn)是針對存儲結(jié)構(gòu)的，指出運算的具體操作步驟。

9.算法：對特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。有5個重要特性(有窮性、確定性、可行性、輸入、輸出)。

　　(1)有窮性：一個算法必須保證執(zhí)行有限步之后結(jié)束。

　　(2)確定性：算法的每一步驟必須有確定的定義。

　　(3)輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身確定了初始條件。

　　(4)輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。

　　(5)可行性：算法中的所有操作都必須可以通過已經(jīng)實現(xiàn)的基本操作進行運算，并在有限次內(nèi)實現(xiàn)，而且人們用筆和紙做有限次運算后也可完成。

10.算法設計的要求：正確性、可讀性、健壯性、效率與低存儲量需求。

　　(1)正確性：要求算法能夠正確地執(zhí)行預先規(guī)定的功能和性能要求。這是重要也是基本的標準。

　　(2)可讀性：要求算法易于人的理解。

　　(3)健壯性：要求算法有很好的容錯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進行檢查。

　　(4)高效率與低存儲量需求：算法的效率主要是指算法的執(zhí)行時間。對于同一個問題如果有多種算法可以求解，執(zhí)行時間短的算法效率高。算法的存儲量指的是算法執(zhí)行過程中所需要的大存儲空間。高效率和低存儲量這兩者都與問題的規(guī)模有關。

11.時間復雜度：算法的時間復雜度，也就是算法的時間量度，記作：T(n)=0(f(n))。它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復雜度，簡稱為時間復雜度。其中f(n)是問題規(guī)模n的某個函數(shù)。

12.空間復雜度：算法的空間復雜度指算法在運行時所需存儲空間的度量，主要考慮在算法運行過程中臨時占用的存儲空間的大小(和時間復雜度一樣，以數(shù)量級的形式給出)。

13.就地算法：就地( In-place)算法指的是直接修改輸入數(shù)據(jù)而不是將輸入數(shù)據(jù)復制一份處理之后再覆蓋回去，這個名稱和時間復雜度沒什么關系，純粹是指算法處理數(shù)據(jù)的方式。比如一個冒泡排序就是就地算法。

第二章：線性表

1.線性表的邏輯特性：線性表中數(shù)據(jù)元素之間的關系是一對一的關系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的，每個元素最多只能有一個前驅(qū)和一個后繼。

2.線性表的存儲結(jié)構(gòu)：線性表的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)兩種，前者稱為順序表，后者稱為鏈表，其中順序表是保存在一片連續(xù)的存儲空間中的，而鏈表則是通過指針來與其他數(shù)據(jù)進行聯(lián)系，每個數(shù)據(jù)元素除了存儲元素本身信息，還要存儲與其他數(shù)據(jù)之間的關系。

3.單鏈表：包含數(shù)據(jù)域和指針域，指針域有一個指針，指針指向下一節(jié)點的地址。

4.雙鏈表：包含數(shù)據(jù)域和指針域，指針域有兩個指針，一個指針指向下一節(jié)點的地址，另一個指針指向上一節(jié)點的地址。

5.循環(huán)單鏈表：在單鏈表基礎上，最后一個節(jié)點的后繼指向第一個節(jié)點

6.循環(huán)雙鏈表：在雙鏈表基礎上，最后一個節(jié)點的后繼指向第一個節(jié)點，第一個節(jié)點的前驅(qū)指向最后一個節(jié)點。

7.靜態(tài)鏈表：借助數(shù)組來描述線性表的鏈式存儲結(jié)構(gòu)，節(jié)點也有數(shù)據(jù)域和指針域。但指針是節(jié)點的相對地址(數(shù)組下標)，需要預先分配連續(xù)的內(nèi)存空間。

第三章：棧與隊列

1.棧：棧是一個特殊的線性表，它在操作上有一些特殊的要求和限制：棧的元素必須“后進先出”，棧的操作只能在這個線性表的表尾進行。

2.隊列：隊列是一個特殊的線性表，它在操作上有一些特殊的要求和限制：隊列的元素必須“先進先出”，隊列的入隊操作只能在這個線性表的一端進行，出隊操作只能在這個線性表的另一端進行。進行刪除操作的一端稱為隊頭，進行插入操作的一端稱為隊尾。

3.假溢出：系統(tǒng)作為隊列用的存儲區(qū)還沒有滿，但隊列卻發(fā)生了溢出，我們把這種現(xiàn)象稱為"假溢出”。

解決辦法：

　　一是將隊列元素向前“平移”(占用0至rear-front-1);

　　二是將隊列看成 首尾相連，即循環(huán)隊列(0..m-1)。

　　另一種解法是“設標記”方法，如設標記tag， tag等于0情況下，若刪除時導致front=rear 為隊空;tag=1情況下,若因插入導致front=rear則為隊滿。

4.循環(huán)隊列:為了克服順序隊列中假溢出,通常將一維數(shù)組Queue[0]到Queue [MAXSIZE-1]看成是一個首尾相連接的圓環(huán),即Queue[0]與Queue[MAXSIZE-1]相連接在一起,將這樣形式的隊列成為循環(huán)隊列。

5.遞歸函數(shù)：對于某一函數(shù)f(x)，其定義域是集合A，若對于A集合中的某一個值X0，其函數(shù)值f(x0)由f(f(x0))決定,那么就稱f(x)為遞歸函數(shù)。

第四章：串

1.串；由零個或者多個字符組成的有限序列。串中任意個連續(xù)的字符組成的子序列稱為該串的子串。字符在序列中的序號為該字符的位置。

2.串的存儲方式：可大致分為三種，定長順序存儲方式、動態(tài)分配的堆分配存儲方式以及鏈式存儲方式。

　　所謂堆，即為一塊內(nèi)存。當程序運行時，系統(tǒng)自動為程序分配一塊內(nèi)存，這塊內(nèi)存是空的。每當使用malloc或new函數(shù)的時候，新聲明的變量就都會被存入這片內(nèi)存中。

　　使用完畢后，若不及時free或delete之前聲明的變量，堆中剛占用的內(nèi)存就不會釋放，即內(nèi)存泄露問題。總而言之，串的堆存儲就是根據(jù)需要動態(tài)分配字符串的存儲空間。

3.模式匹配：模式匹配是數(shù)據(jù)結(jié)構(gòu)中字符串的一種基本運算。其是求第一個字符串(模式串)在第二個字符串(主串)中的位置。

4.KMP: Knuth-Morris-Pratt算法(簡稱KMP),是由D.E. Knuth、J.H. Morris和V.R. Pratt 共同提出的一個改進算法，消除了樸素的模式匹配算法中回溯問題，完成串的模式匹配。

5.BM: BM算法是一種精確字符串匹配算法(區(qū)別于模糊匹配)。采用從右向左比較的方法，同時應用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來決定向右跳躍的距離。

第五章：樹與二叉樹

1.樹的定義：包含n(n>0)個節(jié)點的有窮集合。

　　(1)集合中的每一個元素都稱為一個節(jié)點(Node)

　　(2)有一個特殊的節(jié)點稱為根節(jié)點(Boot)

　　(3)根節(jié)點之外的節(jié)點元素被分為m(m>=0)個互不相交的集合，其中每一個集合本身也是一顆樹，稱為根節(jié)點的子樹。

2.樹的存儲結(jié)構(gòu)：雙親表示法，孩子表示法，孩子兄弟表示法。

3.樹的節(jié)點：包括一個數(shù)據(jù)元素以及若干指向其子樹的分支。

• 節(jié)點擁有的子樹稱為節(jié)點的度。
• 度為0的節(jié)點稱為葉子或終端節(jié)點。
• 樹的度是樹內(nèi)個節(jié)點的度的最大值。
• 節(jié)點的子樹的根稱為該節(jié)點的孩子，相應的該節(jié)點為孩子的雙親。
• 同一個雙親的孩子之間互稱兄弟。
• 節(jié)點的祖先是從根到該節(jié)點的所經(jīng)分支上的所有節(jié)點。
• 反之，以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。

4.節(jié)點的層次：從樹根開始定義，根節(jié)點為第1層，它的子節(jié)點為第2層，以此類推。

5.樹的高度或深度：樹中節(jié)點的最大層數(shù)。

6.有序樹和無序樹：樹中節(jié)點的子樹從左到右是有次序的，不能交換，叫做有序樹。反之為無序樹。

7.二叉樹：是另一種樹形結(jié)構(gòu)，每個節(jié)點至多有兩棵子樹，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。

　　性質(zhì)1：二叉樹第i層上的節(jié)點數(shù)目最多為

　　性質(zhì)2：深度為k的二叉樹至多有 2k-1 個節(jié)點(k≥1)。

　　性質(zhì)3：包含n個節(jié)點的二叉樹的高度至少為！ [log?(N+ 1)]|或者[log₂N]+1

　　性質(zhì)4：在任意一棵二叉樹中，若終端節(jié)點的個數(shù)為n₀，度為2的節(jié)點數(shù)為n₂，則n₀=n₂+1。

8.滿二叉樹：一棵高度為h，并且含有： 2^h?-1個節(jié)點的二叉樹稱為滿二叉樹。即每層都有最多的節(jié)點，葉子集中在二叉樹的最下一層且除葉子之外的每個節(jié)點度為2.

9.完全二叉樹：若設二叉樹的深度為h，除第h層外，其它各層(1~h-1)的節(jié)點數(shù)都達到最大個數(shù)，第h層所有的節(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。

11.森林:m(m>=0)棵互不相交的樹的集合。

12.哈夫曼樹：在含有N個帶權(quán)葉子節(jié)點的二叉樹中，其中帶權(quán)路徑長度(WPL)最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。

13.哈夫曼編碼：一種廣泛應用而且非常有效的數(shù)據(jù)壓縮編碼。

14.路徑和路徑長度：樹中兩個節(jié)點之間的路徑是由這兩個節(jié)點之間所經(jīng)過的節(jié)點序列構(gòu)成的。路徑長度是路徑上經(jīng)過的邊的個數(shù)。

15.樹的路徑長度：樹根到每一個節(jié)點的路徑長度之和

16.樹的帶權(quán)路徑長度(WPL)：樹中所有葉子節(jié)點的帶權(quán)路徑長度之和。

17.二叉樹的遍歷：指按某條搜索路徑訪問樹中的每個節(jié)點，使得每個節(jié)點均被訪問一次且僅被訪問一次。

18.樹的先根遍歷：若樹非空，則先訪問根節(jié)點，再按從左到右的順序遍歷根節(jié)點的每一顆子樹。其訪問順序與這棵樹對應的二叉樹的線序遍歷順序相同。

19.樹的后根遍歷：若樹非空，則按從左到右的順序遍歷根節(jié)點的每一棵子樹，之后再訪問根節(jié)點。其訪問順序與其對應的二叉樹的中序遍歷相同。

20.先序遍歷森林：若森林非空，則按如下規(guī)則遍歷：

• 訪問森林第一棵樹的根節(jié)點
• 先序遍歷第一棵樹中根節(jié)點的子樹森林
• 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林

21.中序遍歷森林：若森林非空，則按如下規(guī)則進行遍歷：

• 中序遍歷森林中第一棵樹的根節(jié)點的子樹森林
• 訪問第一棵樹的根節(jié)點
• 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林

22.線索二叉樹：按照某種遍歷與式對二叉樹進行遍歷，可以把二叉樹中所有節(jié)點排序為一個線性序列。

　　在該序列中，除第一個節(jié)點外每個節(jié)點有且僅有一個直接前驅(qū)節(jié)點；除最后一個節(jié)點外每一個節(jié)點有且僅有一個直接后繼節(jié)點。

　　這些指向直接前驅(qū)節(jié)點和指向直接后續(xù)節(jié)點的指針被稱為線索(Thread)，加了線索的二叉樹稱為線索二叉樹。

23.決策樹：決策樹(Decision Tree)是在已知各種情況發(fā)生概率的基礎上，通過構(gòu)成決策樹來求凈現(xiàn)值的期望值大于等于零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。

　　由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。

　　在機器學習中，決策樹是一個預測模型，他代表的是對象屬性與對象值之間的一種映射關系。

　　Entropy=系統(tǒng)的凌亂程度，使用算法ID3，C4.5和C5.0生成樹算法使用熵。這一度量是基于信息學理論中熵的概念。

　　決策樹是一種樹形結(jié)構(gòu)，其中每個內(nèi)部節(jié)點表示一個屬性上的測試，每個分支代表一個測試輸出，每個葉節(jié)點代表一種類別。

　　分類樹(決策樹)是一種十分常用的分類方法。他是一種監(jiān)管學習，所謂監(jiān)管學習就是給定一堆樣本，每個樣本都有一組屬性和一個類別，這些類別是事先確定的，那么通過學習得到一個分類器，這個分類器能夠?qū)π鲁霈F(xiàn)的對象給出正確的分類。這樣的機器學習就被稱之為監(jiān)督學習。

24.隨機森林：指的是利用多棵樹對樣本進行訓練并預測的一種分類器。

第六章：圖

1.圖:由非空頂點集V和邊集E組成,記作G=(V,E)。

2.圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表、十字鏈表、鄰接多重表、邊集數(shù)組。

3.有向圖：E為有向邊的有限集合時，圖G為有向圖

4.無向圖：E為無向邊的有限集合時，圖G為無向圖

5.簡單圖：不存在重復邊，不存在頂點到自身的邊稱圖G為簡單圖。與多重圖相對

6.完全圖：在無向圖中，若任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。具有n*(n-1)/2條邊。有向圖中，若任意兩個頂點之間存在方向相反的兩條弧，稱為有向完全圖，含有n(n-1)條有向邊。

7.子圖：如果一個圖G2的所在頂點和邊都是另一個圖G1的子集，則稱G2是G1的子圖，只有頂點和邊的集合都是子集，才稱為子圖，也就是說若頂點集合是子集，而邊集合不是子集，不能稱為子圖。

8.連通：若從頂點v到頂點w存在路徑，則v和w是連通的。若圖G中任意兩個頂點都是連通的，則稱圖G為連通圖，否則為非連通圖。

9.連通分量：無向圖中的極大連通子圖稱為連通分量。

10.強連通圖：在有向圖中，若從V到頂點W和從頂點W到頂點V都存在路徑，則稱兩個頂點是強連通的，若圖中任一對頂點都是強連通的，則稱為強連通圖。

11.強連通分量：有向圖中的極大強連通子圖稱為有向圖的強連通分量。

12.生成樹和生成森林：連通圖的生成樹是包含圖中所有頂點的一個極小連通子圖。若頂點為n則含有n-1條邊。非連通圖中，連通分量的生成樹構(gòu)成生成森林

13.最小生成樹：一個帶權(quán)連通無向圖的生成樹中邊的權(quán)值之和最小的那個叫做此圖的最小生成樹。

14.路徑、路徑長度和回路：頂點V到頂點Q之間的一條路徑是指之間的一個頂點序列。路徑的長度是路徑上邊的數(shù)目。第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)。

15.簡單路徑：若一條路徑上頂點不重復出現(xiàn)，則稱這個路徑為簡單路徑。

16.簡單回路：若路徑上第一個頂點和最后一個頂點相同，稱為回路，或環(huán)，除了第一個頂點和最后一個頂點相同，其余各頂點都不重復出現(xiàn)的回路稱為簡單回路。

17.最短路徑：帶權(quán)圖中，從一個頂點V0到另一個頂點V1的一條路徑上所經(jīng)過邊的權(quán)值之和定義為該路徑的帶權(quán)路徑長度，其中最短的那條稱作最短路徑。

　　此路徑的長度稱為從v 到u的距離。

18.圖的遍歷：從圖中某一頂點出發(fā)，按照某種搜索方法沿著圖中的邊對圖中所有頂點訪問一次且僅訪問一次。

19.深度優(yōu)先搜索：類似于樹的先序遍歷，假設從圖中某頂點V出發(fā)，在訪問了V之后一次從V的未被訪問的鄰接點出發(fā)做深度優(yōu)先遍歷，直到圖中所有和V有路徑相同的頂點都被訪問到。

　　若圖中還有頂點未訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述過程，直至圖中所有頂點都被訪問。

20.廣度優(yōu)先搜索：類似于樹的層次遍歷，從頂點v出發(fā)，訪問了V之后依次訪問v的各個未被訪問過的鄰接頂點。再依次訪問它們的鄰接點，并使先被訪問的頂點的的鄰接點先于后訪問的頂點的鄰接點。

　　直到圖中所有已被訪問頂點的鄰接點都被訪問到。如果圖中還有頂點未被訪問，則另選一個未被訪問的頂點作為起始點，重復上述過程，直到圖中所有頂點都被訪問。

21.A0V網(wǎng)，用有向無環(huán)圖表示一個工程，頂點表示活動，有向邊<Vi， Vj>表示Vi必須先于Vj進行的關系。則稱為AOV網(wǎng)。

22.AOE網(wǎng)，在帶權(quán)有向圖中，以頂點表示事件，有向邊表示活動，邊上的權(quán)值表示完成該活動的開銷(如時間)，則稱這個網(wǎng)絡為AOE網(wǎng)。

23.關鍵路徑：在AOE網(wǎng)中，路徑長度最長的路徑叫做關鍵路徑，關鍵路徑上的所有活動都是關鍵活動。

24.拓撲排序：將有向圖中的頂點以線性方式進行排序，通過偏序得到圖的全序。即對于任何連接自頂點u到頂點v的有向邊<u，v>，在最后的排序結(jié)果中，頂點u總是在頂點v的前面。

第七章：排序

1.排序：重新排列表中的元素，使表中的元素滿足按關鍵字遞增或遞減的過程。

2.算法的穩(wěn)定性：假設Ri=Rj，且在排序之前Ri領先于Rj，若在排序后的序列中Ri仍然領先于Rj，則稱所用的排序算法是穩(wěn)定的，反之則稱所用的算法是不穩(wěn)定的。

3.內(nèi)部排序：排序期間元素全部存放在內(nèi)存中的排序；外部排序是指在排序期間元素無法全部同時存放在內(nèi)存中，必須在排序的過程中根據(jù)要求不斷的在內(nèi)外存之間移動的排序。

4.監(jiān)視哨：臨時存儲和判斷數(shù)組邊界。

5.插入排序：每次將一個待排序的記錄，按關鍵字大小插入到前面已經(jīng)排好序的子序列中，直至全部記錄插入完成。

6.希爾排序：又稱縮小增量排序，先將整個記錄序列分割成若干子序列分別進行直接插入排序，待整個序列中記錄基本有序時，再對全體進行一次直接插入排序。

7.冒泡排序：從前往后(或從后往前)兩兩比較相鄰元素的值，若為逆序則交換，知道序列比較完，既完成一趟冒泡排序。這一趟確定的最小元素不再參與比較，重復上述過程直到一趟排序沒有記錄交換。

8.快速排序：通過一趟排序?qū)⒋庞涗浄峙涑瑟毩刹糠?，其中一部分的關鍵字均比另一部分小，分別對兩部分再進行快速排序直至整個序列有序

9.選擇排序：每一趟在未排序的記錄中選擇最小的記錄作為有序序列部分的下一個記錄。

10.歸并排序：將兩個或兩個以上的有序表組合成一個新的有序表。二路歸并排序的核心操作是將一維數(shù)組中前后相鄰的兩個有序序列歸并為一個有序序列。

11.基數(shù)排序：采用多關鍵字排序思想，借助“分配/收集”兩種操作對邏輯關鍵字進行排序。

12.堆排序：一種樹形選擇排序方法。在排序過程中把Z[1…N]堪稱一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親和孩子之間的關系，在當前無序區(qū)選擇最大或最小的元素。

13.堆：堆常用來實現(xiàn)優(yōu)先隊列，在這種隊列中，待刪除的元素為優(yōu)先級最高(最低)的那個。在任何時候，任意優(yōu)先元素都是可以插入到隊列中去的，是計算機科學中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱?！咀⒁馀c棧的區(qū)別】

14.桶排序：工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序)。桶排序是鴿巢排序的一種歸納結(jié)果。當要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間(0(n))。但桶排序并不是比較排序，他不受到0(nlog n)下限的影響。

第八章：查找

1.查找：在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。

2.查找表(查找結(jié)構(gòu))：用于查找的數(shù)據(jù)集合稱為查找表。

3.靜態(tài)查找表：如果一個查找表的操作僅涉及查詢某個特定的數(shù)據(jù)元素是否在查找表中和檢索滿足條件的某個特定的數(shù)據(jù)元素的各種屬性，則稱為靜態(tài)查找表。

4.動態(tài)查找表：需要動態(tài)的插入或刪除的查找表稱為動態(tài)查找表。

5.關鍵字：數(shù)據(jù)元素中唯一標識該元素的某個數(shù)據(jù)項的值，使用基于關鍵字的查找，查找結(jié)果應該是唯一的。

6.平均查找長度(ASL)：在查找的過程中，一次查找的長度指需要比較的關鍵字次數(shù)，而平均查找長度則是所有查找過程中進行關鍵字的比較次數(shù)的平均值。

7.折半查找：僅適用于有序的順序表。將給定的值key與表中間位置元素的關鍵字比較，相等則查找成功返回位置。若不等則縮小查找范圍，重復查找直到找到或者確定表中沒有需查找的元素。

8.二叉排序樹：一棵二叉排序樹或是空二叉樹或是具有以下性質(zhì)的二叉樹：左子樹上所有關鍵字均小于根節(jié)點的關鍵字，右子樹所有節(jié)點關鍵字大于根節(jié)點的關鍵字。左子樹和右子樹又各是一棵二叉排序樹。

9.平衡二叉樹：樹上任一節(jié)點的左子樹和右子樹的深度之差不超過1.

10.平衡因子：該節(jié)點的左子樹深度減去它的右子樹深度。

11.判定樹：樹中每個節(jié)點表示表中的一個記錄，節(jié)點里的值為該記錄在表中的位置，通常稱這個查找過程的二叉樹為判定樹。

12.散列函數(shù)：一個把查找表中的關鍵字照射成該關鍵字對應的地址的函數(shù)，

13.沖突(同義詞)：散列函數(shù)可能會把兩個或以上的不同關鍵字映射到同一地址，這種情況為沖突。

14.散列表：是根據(jù)關鍵字而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。散列表建立了關鍵字和存儲地址指間的一種直接映射關系。

15.開放定址法：指的是可存放新表項的空閑地址既向它的同義詞表項開放，又向它的非同義詞表項開放。

16.拉鏈法(鏈地址法)：把所有的同義詞存儲在一個線性鏈表中，這個線性鏈表由其散列地址唯一標識。

17.裝填因子：填入表中的元素個數(shù)/散列表的長度。

18.二次聚集：指在處理沖突過程中發(fā)生的兩個第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現(xiàn)象。

19.再哈希法：這種方法是同時構(gòu)造多個不同的哈希函數(shù)：H?=RH?(key) i=1,2,……,

k。當哈希地址H?=RH?(key)發(fā)生沖突時,再計算 ，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計算時間。

20.紅黑樹：紅黑樹是一種特定類型的二叉樹，是在計算機科學中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實現(xiàn)關聯(lián)數(shù)組。它是在1972年由RudolfBayer發(fā)明的，他稱之為"對稱二叉B 樹",它現(xiàn)代的名字是在LeoJ. Guibas和RobertSedgewick于1978年寫的一篇論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，并且在實踐中是高效的，它可以在0(logn)時間內(nèi)做查找，插入和刪除，這里的n是樹中元素的數(shù)目。

21.勝者樹與敗者樹：勝者樹和敗者樹都是完全二叉樹，是樹形選擇排序的一種變型。每個葉子節(jié)點相當于一個選手，每個中間節(jié)點相當于一場比賽，每一層相當于一輪比賽。

不同的是，勝者樹的中間節(jié)點記錄的是勝者的標號；而敗者樹的中間節(jié)點記錄的敗者的標號。

數(shù)據(jù)結(jié)構(gòu) - 簡答題合集

第一章：緒論

1、數(shù)據(jù)結(jié)構(gòu)是一門研究什么的學科?

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中，計算機操作對象及對象間的關系和施加于對象的操作等的學科。

2、數(shù)據(jù)存儲結(jié)構(gòu)有哪幾種類型?

存儲結(jié)構(gòu)可分為順序存儲、鏈式存儲、索引存儲和散列存儲。

3、數(shù)據(jù)邏輯結(jié)構(gòu)包括哪幾種類型?

邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)。更細分的話可以說，邏輯結(jié)構(gòu)包括集合、線性結(jié)構(gòu)(線性表、棧、隊列等)、樹形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。

4、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別?

答：數(shù)據(jù)結(jié)構(gòu)這一術(shù)語有兩種含義，一是作為一門課的名稱，二是作為一個科學的概念，目前尚無公認定義，一般認為，數(shù)據(jù)結(jié)構(gòu)包括三個方面數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)的運算。而數(shù)據(jù)類型是值的集合和操作的集合，可以看做是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。

5、數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的?二者有何相同和不同之處?抽象數(shù)據(jù)類型的主要特點是什么?使用抽象數(shù)據(jù)類型的主要好處是什么?數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的?二者有何相同和不同之處?抽象數(shù)據(jù)類型的主要特點是什么?使用抽象數(shù)據(jù)類型的主要好處是什么?

答：數(shù)據(jù)類型是程序設計語言中的一個概念，數(shù)據(jù)類型是值的集合和操作的集合，可以看做是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)

抽象數(shù)據(jù)類型指一個數(shù)學模型及定義在該模型上的一組操作。抽象的意義在于數(shù)據(jù)類型的數(shù)學抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機內(nèi)部如何表示與實現(xiàn)無關。無論其內(nèi)部如何變化。只要它的數(shù)學特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念，但是抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設計軟件系統(tǒng)時自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義，表示和實現(xiàn)三部分，封裝在一起，對用戶透明(提供接口)，而不必了解實現(xiàn)細節(jié)。

第二章：線性表

1、對順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，比較它們的優(yōu)缺點。在什么情況下用順序表比鏈表好?

1)順序存儲時，相鄰數(shù)據(jù)元素的存放地址相鄰(邏輯與物理統(tǒng)一)，內(nèi)存中可用存儲單元的地址也連續(xù)。

優(yōu)點：存儲密度大，存儲空間利用率高。缺點：插入刪除需要移動元素。

2)鏈式存儲時，相鄰元素隨意存放，存儲空間由結(jié)點值和指針兩部分組成。

優(yōu)點：插入刪除方便。缺點：存儲利用率低。

在線性表長度變化不大，主要操作是查找時，采用順序表。

在線性表長度變化較大，插入刪除操作時，采用鏈表。

2、試舉一例說明對相同的邏輯結(jié)構(gòu)，同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。

答：線性表的插入刪除操作。在順序存儲方式下平均移動一半元素，時間復雜度為0(n)，在鏈式存儲方式下，插入和刪除的時間復雜度都是0(1)。

3、說明頭指針、頭節(jié)點、首元結(jié)點的概念

頭指針是指向鏈表中第一個結(jié)點(或頭節(jié)點或首元結(jié)點)的指針。

頭節(jié)點是在鏈表的首元結(jié)點之前附加的一個結(jié)點，頭結(jié)點是為了操作的統(tǒng)一方便而設立的。數(shù)據(jù)域一般無意義，只放空表標志和表長等信息。

首元素結(jié)點是指鏈表中存儲線性表中第一個元素結(jié)點。

4、簡述順序存儲隊列假溢出的避免方法及隊滿和空的條件。

答：避免方法：一是將隊列元素向前“平移”(占用0至rear-front 1)；二是將隊列看成首尾相連，即看做循環(huán)隊列(0…m-1)。

在循環(huán)隊列下，定義front=rear時為隊空，而判斷隊滿則常用兩種方法：一種是用 “犧牲一個單元” ,即rear+1=front(準確說是(rear+1) %m==front時,m是隊列容量)時為隊滿:另一種方法是 “設標記”,如設標記tag, tag=0時為隊空: tag=1時,若因插人導致front=rear 則為隊滿。

第三章：棧與隊列

1、棧、隊列的名詞解釋。棧、隊列和線性表之間的聯(lián)系與區(qū)別。

棧是只允許在一端進行插入和刪除操作的線性表，允許插入和刪除的端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進先出表。

隊列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊尾，允許刪除的端叫隊頭。最先插入隊的元素最先離開(刪除)，故隊列也常稱先進先出表。

棧與隊列都是操作受限的線性表，只允許在端點插入刪除。都可通過順序結(jié)構(gòu)和鏈式結(jié)構(gòu)實現(xiàn)。插入刪除時間復雜度都為0(1)。

棧只允許在棧頂插入刪除，隊列在隊頭刪除隊尾插入。

相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲：棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插人、刪除運算加以限制

不同點：①運算規(guī)則不同，線性表為隨機存取，而棧是只允許在一端進行插人刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插人，另一端進行刪除運算，因而是先進先出表FIF0.②用途不同，堆棧用于子程調(diào)用和保護現(xiàn)場列用于多道作業(yè)處理、指令寄存及其他運算等等

2、棧和隊列的應用有?

棧：表達式的轉(zhuǎn)換和求值、函數(shù)調(diào)用和遞歸實現(xiàn)、深度優(yōu)先搜索遍歷

隊列：計算機系統(tǒng)中各種資源的管理、消息緩沖器的管理、廣度優(yōu)先搜索遍歷

2、什么是遞歸程序?

一個函數(shù)在結(jié)束本函數(shù)前，直接或間接調(diào)時函數(shù)自身，稱為遞歸。

遞歸程序的優(yōu)點是程序結(jié)構(gòu)簡單，清晰，易證明其正確性。缺點是執(zhí)行中占內(nèi)存空間較多，運行效率低。

遞歸程序執(zhí)行中需要借助棧這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。

遞歸程序的入口語句和出口語句一般用條件判斷語句來實現(xiàn)。遞歸程序有基本項和歸納項組成。

第四章：串

1、什么是串?

串是零個至多個字符組成的有限序列。從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)。與線性表的特殊性在于串的元素是字符。

2、描述一下概念的區(qū)別：空格串和空串

空格是一個字符，其ASCII碼值是32?？崭翊怯每崭窠M成的串，其長度等于空格的個數(shù)。

空串是不含任何字符的串，即空串的長度是零。

3、什么是廣義表?廣義表與線性表的區(qū)別

線性表中的元素可以是各種各樣的，但必須具有相同的性質(zhì)，屬于同一數(shù)據(jù)對象。

廣義表中的元素可以是元素也可以是子表。

4、試敘述一維數(shù)組和有序表的異同

一維數(shù)組屬于特殊的順序表，和有序表的差別主要在于有序表中的元素按值排序(非遞增或非遞減)，而一維數(shù)組中元素沒有按元素值排列順序的要求。

第五章：樹與二叉樹

1、樹與二叉樹的區(qū)別和聯(lián)系?

樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，在邏輯上都是樹形結(jié)構(gòu)，區(qū)別主要有：

一是二叉樹的度至多為2，樹無此限制；

二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下，也必須指出是左子樹還有右子樹，樹無此限制；

三是二叉樹允許為空，樹一般不允許為空。

2、什么叫完全二叉樹

完全二叉樹由滿二叉樹而引出來，對于深度為K的，有n結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應時稱之為完全二叉樹。

第六章：圖

1、完全圖

也叫簡單完全圖，假設一個圖有n個頂點，那么如果任意兩個頂點之間都有邊的話，該圖就稱為完全圖。

2、連通、連通分量、強連通分量的概念，極大連通子圖?極小連通子圖?

在無向圖中，若從頂點v到頂點w有路徑存在，則稱v和w是連通的。圖中任意兩點是連通的，則稱圖G為連通圖。無向圖中的極大連通子圖稱為連通分量。

有向圖中，若v到w和w到v都有路徑存在，則稱這兩個點是強連通的。任一對頂點都是強連通的，則此圖為強連通圖。有向圖中的極大強連通子圖稱為有向圖的強連通分量。

極大是要求該連通子圖包含其所有的邊(暗指無向圖)，亦為連通分量。

極小是在保持連通的情況下使邊數(shù)最少的子圖(暗指無向圖)，亦為最小生成樹。

3、對一個圖進行遍歷可以獲得不同的遍歷序列，那么導致得到不同遍歷序列不唯一的因素有哪些?

遍歷不唯一的因素有：開始遍歷的結(jié)點不同；存儲結(jié)構(gòu)不同；在鄰接表情況下鄰接點的順序不同。

4、在什么情況下， Prim算法和Kruskual算法生成不同的最小生成樹MST?

在有相同權(quán)值邊時生成不同的MST，在這種情況下，用Prim算法或Kruskual算法會產(chǎn)生不同的MST。

5、Prim算法和Kruskual算法區(qū)別

Prim算法是加點法，適合邊稠密圖；Kruskual算法是一種按權(quán)值的遞增次序選擇合適邊來構(gòu)造生成樹的加邊法，適合邊稀疏而頂點較多的圖。

第七章：查找

1、散列表存儲的基本思想是什么?

散列表的基本思想是用關鍵字的值決定數(shù)據(jù)元素的不儲地址

2、散列表存儲中解決碰撞的基本方法有哪些?

a、開放定址法根據(jù)di的取值又分為線性探測再散列、二次探測再散列、偽隨機探測再散列

b、再散列法

c、鏈地址法

d、建立公共溢出區(qū)

3、如何衡量hash函數(shù)的優(yōu)劣?

能否將關鍵字均勻映射到哈?？臻g上，有無好的解決沖突的方法，計算哈希函數(shù)是否簡單高效。由于哈希函數(shù)是壓縮映像，沖突難以避免。

4、在查找算法中，設置監(jiān)視哨的作用是什么?

監(jiān)視哨的作用是免去查找過程中每次都要檢測整個表是否查找完畢，提高了查找效率。

5、對于一個有序順序表來說，折半查找是否任何時候比順序查找快?為什么?

答：并非在任何情況下折半查找都比順序查找快。例如，若待查元素是該順序表的第一個元素，則順序查找順序表會更快。對有序順序表采用順序查找，若元素存在表中，則在任一位置，查找都可能成功。同樣，若元素不在表中，則在任一位置，查找都可能結(jié)束。折半查找必須經(jīng)一-系列計算，方知查找成功還是失敗。盡管如此，一般說來，在大多數(shù)情況下，折半查找還是比順序查找快。

第八章：排序

1、排序穩(wěn)定性的概念

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的。

2、穩(wěn)定排序有哪些?不穩(wěn)定排序有哪些?

穩(wěn)定排序：直接插入排序、冒泡排序、歸并排序、基數(shù)排序

不穩(wěn)定排序：選擇排序、希爾排序、快速排序、堆排序

3、快速排序是在所有情況下，排序速度最快的嗎?為什么?

不是，因為當序列已有序時，快速排序退化成了冒泡排序，時間復雜度為0(n2)。

當待排序列無序，使每次劃分完成后，樞軸(pivot)兩側(cè)子文件長度相當，此時快速排序性能最好。

4、比較次數(shù)與序列初態(tài)無關的算法是：二路歸并排序、簡單選擇排序、基數(shù)排序比較次數(shù)與序列初態(tài)有關的算法是：快速排序、直接插入排序、冒泡排序、堆排序、希爾排序

5、簡述堆的結(jié)構(gòu)

堆是一種特殊的完全二叉樹，所有父結(jié)點都比子結(jié)點要小的完全二叉樹我們稱為最小堆。反之，如果所有父結(jié)點都比子結(jié)點要大，這樣的完全二叉樹稱為最大堆。

參考

　　https://mp.weixin.qq.com/s/cgVwFueUzbEoUwg_8o-OUQ文章來源地址http://www.zghlxwxcb.cn/news/detail-748966.html

到了這里，關于數(shù)據(jù)結(jié)構(gòu)必背名詞解釋&&簡答題匯總的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！