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

1、名詞解釋：數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，是計算機存儲和數(shù)據(jù)組織的方式，它分為三個方面，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的物理結(jié)構(gòu)，數(shù)據(jù)的操作。數(shù)據(jù)項：是數(shù)據(jù)不可分割的最小單位，用它可以識別一個或一個組數(shù)據(jù)，一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中被計算機程序處理的符號的總稱，是計算機化的信息。數(shù)據(jù)類型：是一個值的集合以及定義在這個值集上的一組操作，可分為原子類型和結(jié)構(gòu)類型。抽象數(shù)據(jù)類型：是基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個類型之上的一組操作。邏輯結(jié)構(gòu)：是

2、數(shù)據(jù)元素之間邏輯關(guān)系的描述。物理結(jié)構(gòu)（存儲結(jié)構(gòu)）：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的映像（又稱表示），即數(shù)據(jù)結(jié)構(gòu)在計算機中的存儲方法。算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。時間復雜度：算法執(zhí)行所需時間的量度?？臻g復雜度：算法執(zhí)行所需存儲空間的量度。存儲密度：指結(jié)點數(shù)據(jù)本身所占存儲量和整個結(jié)構(gòu)所占存儲量之比。填空題：程序設(shè)計的一些基本原則：分解、抽象和信息隱蔽。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，有四類基本的數(shù)據(jù)結(jié)構(gòu)：集合結(jié)構(gòu)，線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖形結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）。數(shù)據(jù)的存儲結(jié)構(gòu)有：順序存儲結(jié)構(gòu)、鏈式（鏈接）存儲結(jié)構(gòu)、索引結(jié)構(gòu)、散列存儲結(jié)構(gòu)常用的

3、兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。算法的五個特性：確定性、有窮性、可行性、輸入和輸出。（可以有零個或多個數(shù)據(jù)輸入，但必須至少有一個輸出數(shù)據(jù)。算法設(shè)計的要求：正確性、可讀性、穩(wěn)健性、高效率低存儲量。沃斯公式：程序=算法+數(shù)據(jù)結(jié)構(gòu)。（算法分析）衡量算法的兩個標準：時間復雜度和空間復雜度。一個算法的設(shè)計取決于所選的邏輯結(jié)構(gòu)。一個算法的實現(xiàn)取決于所選的存儲結(jié)構(gòu)。結(jié)構(gòu)化程序設(shè)計思想的要求：自頂向下、逐步細化、模塊化設(shè)計、結(jié)構(gòu)化編程。簡答題：順序存儲結(jié)構(gòu)的特點？（順序存儲和鏈式存儲的優(yōu)缺點）1、結(jié)點中只存放數(shù)據(jù)元素本身的信息，無附加內(nèi)容。（優(yōu)點）2、可直接存儲數(shù)據(jù)元素。（優(yōu)點）3、存儲操作速度較快

4、。（優(yōu)點）4、插入、刪除數(shù)據(jù)元素時，由于需要保持數(shù)據(jù)元素之間的邏輯關(guān)系，必須大量移動元素，因此實現(xiàn)起來比較慢。（缺點）5、順序存儲是一種靜態(tài)結(jié)構(gòu)、存儲密度大，空間利用率低，預分配空間大小難以確定，（缺點）鏈式存儲結(jié)構(gòu)的特點？（順序存儲和鏈式存儲的優(yōu)缺點）1、結(jié)點中除存放數(shù)據(jù)元素本身的信息外，還需存放附加的指針。2、不能直接存取數(shù)據(jù)元素，需順鏈路查找，存取速度較慢。3、插入、刪除元素時不必移動其他元素，速度較快。（優(yōu)點）4、鏈式存儲是一種動態(tài)存儲結(jié)構(gòu)，空間利用率高，存儲密度小，不存在預分配空間問題。線性結(jié)構(gòu)與非線性結(jié)構(gòu)的特點（或差異）？線性結(jié)構(gòu)的特點：是除第一個元素和最后一個元素外，每個數(shù)據(jù)元素

5、都有唯一的前驅(qū)和唯一的后繼，第一個元素沒有前驅(qū)，最后一個元素沒有后繼，關(guān)系是一對一的。非線性結(jié)構(gòu)的特點是：表示結(jié)點間關(guān)系的前驅(qū)后繼不具有唯一性，結(jié)點間是一對多或多對多的關(guān)系。邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系？1、數(shù)據(jù)的物理結(jié)構(gòu)也為存儲結(jié)構(gòu)。2、數(shù)據(jù)的邏輯結(jié)構(gòu)僅考慮數(shù)據(jù)之間的邏輯關(guān)系。3、數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的映像。4、數(shù)據(jù)的邏輯結(jié)構(gòu)獨立于數(shù)據(jù)的存儲介質(zhì)。數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型的區(qū)別和聯(lián)系？數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，是計算機存儲和數(shù)據(jù)組織的方式，它分為三個方面，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的物理結(jié)構(gòu)，數(shù)據(jù)的操作，它偏向于邏輯方面，而數(shù)據(jù)類型是一個值的集合以

6、及定義在這個值上的一組操作，可分為原子類型和結(jié)構(gòu)類型，它偏向于物理方面的線性表。名詞解釋：線性表：是最常用，最簡單的一種數(shù)據(jù)結(jié)構(gòu)，一個線性表是n個數(shù)據(jù)元素的有限序列，除首尾元素外，每個元素有唯一的前驅(qū)和唯一的后繼。順序表：采用順序存儲結(jié)構(gòu)的線性表通常稱為順序表。鏈表：采用鏈式存儲結(jié)構(gòu)的線性表通常稱為順序表。結(jié)點：由數(shù)據(jù)元素和指示其后繼結(jié)點地址的信息組成的存儲映像稱為結(jié)點。表長：表中元素的個數(shù)稱為表的表長。循環(huán)鏈表：是另一種形式的鏈式存儲結(jié)構(gòu)，它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。雙鏈表：采用鏈式存儲結(jié)構(gòu)的線性表，每個結(jié)點除一個數(shù)據(jù)域外，還有兩個指針域，其一指向直接前

7、驅(qū)，另一指向直接后繼。靜態(tài)單鏈表：是利用一塊連續(xù)的空間，按鏈表的存儲方式組織數(shù)據(jù)，按順序存儲結(jié)構(gòu)分配空間，所構(gòu)成的一種鏈表。頭指針：是指向鏈表表頭結(jié)點的指針，只要鏈表存在，該指針始終不會改變，單鏈表由頭指針唯一確定，因單鏈表可以用頭指針的名字來命名。頭結(jié)點：在鏈表的開始結(jié)點之前附加的一個結(jié)點，是鏈表的表頭，當鏈表不空時，其內(nèi)的指針指向鏈表的第一個結(jié)點，當鏈表是空鏈表時，該指針為空指針。填空題：線性表的兩種基本的存儲結(jié)構(gòu)：順序結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。從實現(xiàn)角度看，鏈表可分為靜態(tài)鏈表和動態(tài)鏈表。從鏈接方式的角度看，鏈表可以分為單鏈表，循環(huán)鏈表，雙鏈表。添加哨兵可以保持首指針的穩(wěn)定性，方便表示空表。一元

8、多項式的表示和相加可以使用鏈表實現(xiàn)。簡答題：順序表的優(yōu)缺點？優(yōu)點：1、無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間，存儲密度大2可隨機存取表中的任一元素，查找方便缺點：1插入，刪除運算不方便，須移動大量元素，效率較低2存在預分配空間問題鏈表的優(yōu)缺點？優(yōu)點：1插入，刪除操作很方便2空間利用率高缺點：1查找不方便，需順鏈查找2存儲密度小順序表和鏈表的區(qū)別和聯(lián)系及適用范圍？順序表：內(nèi)存中地址連續(xù)長度一般不可變更支持隨機查找，可在O（1）內(nèi)查找元素適用于需要大量訪問元素的，而少量増刪元素的程序鏈表：內(nèi)存中地址連續(xù)或非連續(xù)都可以長度可實時變化不支持隨機查找，查找元素的時間復雜度為O（n）適用于需要大量

9、增刪元素，而對訪問元素幾乎無要求的程序頭指針和頭結(jié)點的作用？1頭指針是指向鏈表表頭結(jié)點的指針，只要鏈表存在，該指針就不會變化，已知該指針便己知該鏈表2頭結(jié)點是在鏈表的開始結(jié)點之前夫婦家的一個結(jié)點，當鏈表是空鏈表時，該指針為空指針，因此空表和非空表的處理也就統(tǒng)一了簡述在單循環(huán)鏈表上尾指針取代頭指針的作用？在用頭指針表示的單循環(huán)鏈表中，找開始結(jié)點a1的時間是O（1），然而要找終端結(jié)點an則需要從頭指針開始遍歷整個鏈表，其時間是O（n），在很多實際問題中，表的操作常常是在表尾進行的，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便，如果改用尾指針來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便查找

10、時間都是O（1）名詞解釋：棧：也叫后進先出表，是限定僅在表尾進行插入和刪除操作的線性表，表尾端稱為棧頂，表頭端稱為棧底，不含元素的空表稱為空棧順序棧：采用順序存儲結(jié)構(gòu)的棧稱為順序棧鏈棧：采用鏈式存儲結(jié)構(gòu)的棧稱為鏈棧隊列：是一種先進先出的線性表，它只允許在表的一段進行插入，而另一端刪除元素，允許插入的一端叫做隊尾，允許刪除的一端稱為隊首鏈隊列：用鏈表示的隊列，需要兩個指針分別指示隊頭和隊尾，為了操作方便，也給鏈隊列添加一個哨兵結(jié)點循環(huán)隊列：隊列是先進先出表”，隨著入隊出隊的進行，會使整個隊列整體向后移動，當隊尾指針移到最后，若再有元素入隊就會出現(xiàn)“假溢出”，因為此時隊頭部分還有空間可用，循環(huán)隊列

11、是將隊列的數(shù)據(jù)區(qū)看成頭尾相接的循環(huán)結(jié)構(gòu)，可解決“假溢出”雙端隊列：是限定插入，刪除在表的兩端進行的線性表，這兩端分別稱為端點。填空題棧的兩種存儲方式：順序存儲和鏈式存儲滿的判斷條件：s.top stack.size棧空的判斷條件：s.top0棧滿入棧棧上溢，?？粘鰲Ｏ乱珂湕Ｊ褂枚鄺９蚕砑夹g(shù)時，可使用靜態(tài)鏈表結(jié)構(gòu)實現(xiàn)隊列的兩種存儲方式：順序存儲和鏈式存儲循環(huán)隊列采用少用一個元素存儲空間的辦法下，判斷隊列滿的條件：front=（rear+1）%size循環(huán)隊列判斷隊列滿的方法有：少用一個元素存儲空間，增設(shè)一個標志量，使用計數(shù)器隊列的應(yīng)用：楊輝三角棧的應(yīng)用：數(shù)制轉(zhuǎn)換，括號匹配，表達式求值，漢諾塔（

12、遞歸用棧實現(xiàn)）簡答題：什么是多棧共享技術(shù)？在一個程序中經(jīng)常會同時使用多個棧，使用順序存儲結(jié)構(gòu)的?？臻g大小難以估計，這樣使得有的棧已出，有的棧還有空閑空間，可以讓多個棧共享一個足夠大的連續(xù)向量空間（數(shù)組），通過利用棧的動態(tài)特性來使其存儲空間互相補充，這就是多棧的共享技術(shù)，兩個棧共享空間，主要利用了“棧底位置不變，棧頂位置動態(tài)變化”的特性順序隊列相比，循環(huán)隊列有哪些優(yōu)點？可解決假溢出現(xiàn)象（內(nèi)容自行拓展）簡述線性表棧，隊列的區(qū)別和聯(lián)系？相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念，都可以用順序存儲或鏈式存儲，棧和隊列是兩種特殊的線性表，即受限的線性表，只對插入和刪除運算加以限制不同點：1，運算規(guī)則不同，

13、線性表為隨機存取，而棧只允許在一端進行插入、，刪除運算，因而是后進先出表，隊列只允許在一端進行插入，另一端刪除運算，因而是先進先出表2用途不同，堆棧用于子程調(diào)用和保護現(xiàn)場，隊列用于多道作業(yè)處理，指令寄存及其他運算等名詞解釋：串：是由零個或多個字符組成的有限序列子串：串中任意個連續(xù)的字符組成的子序列稱作該串的子串主串：包含子串的串相應(yīng)的稱為主串子串在主串中的位置：子串的第一個字符在主串中的位置表示空串：長度為零的串稱為空串空格串：串中元素均為空格的串稱為空格串串相等：長度相等且對應(yīng)位置字符都相等填空題在程序中，串分為串常量和串變量串的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)，堆存存儲結(jié)構(gòu)串的應(yīng)用：文

14、本編輯簡答題串和線性表的區(qū)別？串的邏輯結(jié)構(gòu)與線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集，然而串的操作與線性表有很大的差別，在線性表基本操作中，大多以單個元素作為操作對象；而在串的基木操作中通常以“串的整體”作為操作對象簡述靜態(tài)分配的順序串與動態(tài)分配的順序串的區(qū)別？程序運行前被分配以一個給定大小的數(shù)組空間的順序串稱為靜態(tài)順序串，在程序運行過程中，動態(tài)分配空間能以鏈表形式存在的順序串稱為動態(tài)順序串，靜態(tài)申在內(nèi)存一片連續(xù)的數(shù)據(jù)區(qū)中，動態(tài)串在內(nèi)存堆中串的鏈式存儲與串順序存儲相比，在哪些操作上效率更高？插入，刪除，因為無需移動其他元素（內(nèi)容自行擴充）名詞解釋：廣義表：是由零個或多個單元素或子表所

15、構(gòu)成的有限序列，是線性表的推廣，也有人稱其為列表數(shù)組：類型一致的有限個數(shù)據(jù)元素按順序連續(xù)存儲矩陣的壓縮存儲：有的矩陣中有許多值相同元素或者是零元素，為了節(jié)省存儲空間對這類矩陣采用多個值相同的元素只分配一個存儲空間，有時零元素不存儲的存儲策略，稱為矩陣的壓縮存儲特殊矩陣：值相同的元素或者零元素在矩陣中的分布有一定規(guī)律的矩陣稱為特殊矩陣稀疏矩陣：非零的數(shù)據(jù)元素個數(shù)很少的矩陣稱為稀疏矩陣對稱矩陣：一個n階方陣，若滿足aij=aji，則稱該矩陣為對稱矩陣三角矩陣：主對角線上方和下方的元素（不包括對角線）均為常數(shù)或零元素的矩陣行表：記錄稀疏矩陣中每行非零元素在三元組表中的起始位置的表三元組表：若線性表順

16、序存儲的每一個結(jié)點均是三元組，則該線性表的存儲結(jié)構(gòu)稱為三元組表帶狀矩陣：所有非零元素均集中在以主對角線為中心的帶狀區(qū)域的矩陣填空題數(shù)組的兩種存儲方式：順序存儲和鏈式存儲數(shù)組的順序存儲有兩種方式：按行存儲和按列存儲稀疏矩陣可以采用三元組表和十字鏈表來存儲簡答題廣義表和線性表的區(qū)別？1廣義表是線性表的推廣，是由零個或多個單元素或子表所構(gòu)成的有限序列2線性表的成分都是結(jié)構(gòu)上不可分制的單個數(shù)據(jù)元素，而廣義表的成分既可以是單元素，也可以是有結(jié)構(gòu)的表其定義是遞歸的定義名詞解釋：樹：是n個結(jié)點的有限集合，n0，有且只有一個稱為根的結(jié)點，根結(jié)點無前驅(qū)有序樹：樹中結(jié)點的各子樹看成是從左至右依次有序的，且不能交換

17、森林：m（m1）棵互不相交的樹的集合二叉樹：是一種樹型的結(jié)構(gòu)，它的特點是每個結(jié)點之多有兩棵子樹，且有左右之分，不可任意顛倒。完全二叉樹：深度為k的有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時滿二叉樹：是一棵深度為k的，且有（2k）-1個結(jié)點的二叉樹遍歷二叉樹：是按照某種搜索路徑巡訪二叉樹中的每個結(jié)點，使得這些結(jié)點均被訪問一次線索二叉樹：由每個結(jié)點中包含左指針，左標志位，數(shù)據(jù)域，右標志位，右指針五部分組成的二叉鏈表，叫做線索鏈表，指向前驅(qū)或后繼的指針叫做線索，以二叉樹某種遍歷順序給空指針加線索的過程叫做線索化，線索化了的二叉樹稱為線索二叉樹哈夫曼樹

18、：又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹哈夫曼編碼：在哈夫曼樹中，約定左分支代表0，右分支代表1，把葉子結(jié)點到根結(jié)點的路徑上的左右分支代表的碼從下至上一次連接起來，組成的字符串稱為該葉子結(jié)點的哈夫曼編碼，這就是哈夫曼編碼二叉排序樹：或者是空樹，或者是符合以下性質(zhì)的二叉樹1若它的左子樹不空，則左子樹上所有結(jié)點均小于它的根結(jié)點值2若它的右子樹不空則右子樹上所有結(jié)點均大于它的根結(jié)點值平衡二叉排序樹（AVL樹）：或者是空樹，或者是符合一下性質(zhì)的二叉排序樹1左子樹和右子樹的高度之差的絕對值小于等于12左子樹和右子樹也是平衡二叉排序樹填空題在二叉樹中，第i層結(jié)點最多為2k1個深度為k的二叉樹中，結(jié)點總

19、數(shù)最多為（2k）1個二叉樹中，n0n21，n2n01（no為二叉樹中度為0的結(jié)點的個數(shù)n2為二叉樹中度為2的結(jié)點的個數(shù)）有n個結(jié)點的完全二叉樹，深度為k，則klog2n1（log以2為底括號是向下取整不是方括號）k層的完全二叉樹至少有2k2個葉子結(jié)點二叉樹的兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)樹的三種常用的存儲方法：孩子表示法，雙親表示法和孩子兄弟表示法樹的遍歷方法：先根遍歷、中根遍歷、后根遍歷、層次遍歷簡答題非線性結(jié)構(gòu)的特點？表示結(jié)點間關(guān)系的前驅(qū)后繼不具有唯一性，結(jié)點間是一對多或多對多的關(guān)系二叉樹的五種基本形態(tài)？只有三個結(jié)點的二叉樹的五種形式？因為二叉樹是有序樹，所有有左右之分，這是五棵

20、不同的二叉樹，但若下列五棵是樹，不是二叉樹，則后面四種為同一棵樹名詞解釋：圖：圖G由兩個集合V和E組成，記為G（V，E），其中V是頂點的有窮非空集合，E是由V中頂點的序偶組成的有窮集，這些序偶稱為邊或弧頂點：圖中的數(shù)據(jù)元素稱為頂點完全圖：邊數(shù)恰好等于n（n1）/2的n個頂點的無向圖稱為完全圖（無向圖中任意兩個頂點之間都有一條邊相連，稱該圖為完全圖）有向完全圖：有n(n-1）條邊的有向圖稱為有向完全圖（圖中每個頂點和其余n-1個頂點都有弧相連）入度：以頂點V為頭的弧的數(shù)目稱為V的入度出度：以頂點V為尾的弧的數(shù)目稱為V的出度連通圖：在無向圖中，任意兩個頂點之間都有路徑相通強連通圖：在有向圖中，任意

21、兩個頂點之間都有來回路徑相通生成樹：生成樹是無向連通圖的一個極小連通子圖，它含有圖中的全部頂點和使任意頂點都連通的最少的邊鄰接矩陣：表示圖中結(jié)點之間關(guān)系的矩陣稱為鄰接矩陣鄰接表：由頂點數(shù)據(jù)表和表示數(shù)據(jù)關(guān)系的邊（?。?gòu)成的表十字鏈表：可以把它看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來形成的一種存儲形式圖的遍歷：從某一頂點出發(fā)按序訪問圖中所有結(jié)點，且使每個結(jié)點僅被訪問一次最小生成樹：無向網(wǎng)中邊上權(quán)值之和為最小的生成樹DAG：有向無環(huán)網(wǎng)拓撲排序：由某個集合上的一個偏序得到該集合上一個全序的操作稱為拓撲排序關(guān)鍵路徑：在AOE網(wǎng)中，從源點到匯點的最長路徑稱為關(guān)鍵路徑AOE網(wǎng)：用頂點表示事件，用弧表示活動，

22、弧的權(quán)值表示活動所需的時間，構(gòu)造的有向網(wǎng)稱為AOE網(wǎng)簡單路徑：一條路徑上除了開始頂點和結(jié)束頂點外，其余頂點均不相同弧頭：邊的終點稱為弧頭弧尾：邊的始點稱為弧尾填空題：邊很少的圖稱為稀疏圖，反之稱為稠密圖有向圖中，所有頂點的入度與出度的和等于邊個數(shù)的2倍圖的存儲方法：鄰接矩陣，鄰接表，鄰接多重表，十字鏈表和邊集數(shù)組圖的深度優(yōu)先搜索類似于樹的先根遍歷圖的廣度優(yōu)先搜索類似于樹的層次遍歷連通圖深度優(yōu)先搜索遍歷深度搜索生成樹連通圖廣度優(yōu)先搜索遍歷廣度搜索生成樹簡答題鄰接矩陣表示法的特點？1對于無向圖而言，它的鄰接矩陣是對稱矩陣，因此可以采用特殊矩陣的壓縮存儲法，但對于有向圖而言，其中的弧是有方向的，因此

23、有向圖的鄰接矩陣不一定是對稱矩陣，對于有向圖的鄰接矩陣的存儲則需要n*n個存儲空間2采用鄰接矩陣表示法，便于判斷圖中任意兩個頂點之間是否有邊相連，即根據(jù)鄰接矩陣中的信息來判斷，另外還便于求得各個頂點的度，對于無向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個頂點的度鄰接表表示法的特點？1n個頂點，e條邊的無向圖，若采取鄰接表作為存儲結(jié)構(gòu)，需要n個頂點數(shù)據(jù)和2e個表示邊的結(jié)點，顯然在邊很稀疏的情況下，用鄰接表存儲所需的空間比鄰接矩陣所需的空間少2無向圖的度，在無向圖的鄰接表中，頂點Vi的度恰好就是第i個邊鏈表上結(jié)點的3有向圖的度，在有向圖中，第i個邊鏈表上結(jié)點的個數(shù)就是頂點Vi的出度，只需通過表

24、頭向量表中找到第i個頂點的邊鏈表的頭指針，實現(xiàn)順鏈查找計數(shù)即可DFS（深度優(yōu)先搜索遍歷）的基本思路？假設(shè)初始狀態(tài)是圖中所有頂點均未被訪問過，則深度優(yōu)先搜索可從某個頂點V出發(fā)，首先訪間此頂點（稱此頂點為初始點），然后依次從V的任一個未被訪問的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷，直到圖中所有與有路徑相通的頂點都被訪問到，若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作為初始點，重復上述步驟，直到圖中所有頂點都被訪問過為止BFS（廣度優(yōu)先搜索遍歷）的基本思路？1從圖中某個頂點VO出發(fā)，首先訪問VO，依次訪問Vo的各個未被訪間的鄰接點2分別從這些鄰接點（端結(jié)點）出發(fā)，依次訪問各個未被訪問的鄰接點

25、，訪問時應(yīng)保證：如果Vi和Vk為當前結(jié)點，且Vi在Vk之前被訪問，則Vi的所有未被訪問的鄰接點應(yīng)在Vk的所有未被訪問的鄰接點之前訪問3重復步驟2，直到所有結(jié)點均沒有未被訪問的鄰接點4若此時還有頂點未被訪問，則選一個未被訪問的頂點作為起始點，重復上述過程，直至所有頂點均被訪問過為止名詞解釋關(guān)鍵字：是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以識別一個或一組數(shù)據(jù)元素査找：根據(jù)給定的關(guān)鍵字的值，檢索某個與該值相等的數(shù)據(jù)元素是否在查找表中找到為查找成功，找不到為查找失敗査找表：是由同一類型的數(shù)據(jù)元素或記錄構(gòu)成的集合靜態(tài)査找表：査詢某個特定的數(shù)據(jù)元素是否在査找表中，檢素某個特定的數(shù)據(jù)元素的各種屬性動態(tài)査找表：在查

26、找過程中同時插入查找不存在的數(shù)據(jù)元素，或者從査找表中刪除已存在的某個數(shù)據(jù)元素平均査找長度（ASL）：為確定數(shù)據(jù)元素在査找表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度沖突：兩個不同的關(guān)鍵字，其散列函數(shù)值相同，因而被映射到同一表位置的現(xiàn)象稱為沖突填空題哈希函數(shù)的構(gòu)造方法：直接定址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法和隨機數(shù)法哈希函數(shù)處理沖突的方法：開放地址法，再哈希法，鏈地址法和建立一個公共溢出區(qū)。簡答題：各查找方法的基本思想，平均査找長度？順序查找的基本思路：對于給定的關(guān)鍵字k，從線性表的第一個元素開始依次向后與記錄的關(guān)鍵字域相比較，如果某

27、個記錄的關(guān)鍵字等于k，則查找成功，否則查找失敗，平均查找長度ASL=3（n1）/4折半（二分）查找的基本思路：先取表的中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進行此較，若相等，則查找成功，如果給定關(guān)鍵字比該記錄的關(guān)鍵字小，則說明所要查找的記錄只可能在表的前半部分，反之，則在后半部分，重復步驟，每一次比較就可以將查找范圍縮小一半，直到找到給定的關(guān)鍵字的記錄，查找成功，找不到為查找失敗，平均查找長度 ASLlog2（n1）-1分塊查找（索引順序表查找）的基本思路：先確定待査記錄所在的塊（子表）然后在塊中順序查找平均查找長度ASL=1/2(n/s)+1+s/2哈希查找（散列查找）的基本思路：在進行查找時，在

28、記錄的存儲位置與它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系h，以線性表中每個元素的關(guān)鍵字k為自變量通過函數(shù)h（k）計算出該元素的存儲位置，我們將h函數(shù)稱為散列函數(shù)或哈希函數(shù)，這種査找方法稱為散列查找或哈希查找名詞解釋：排序：就是按關(guān)鍵字值的遞增或遞減的次序，把文件中的各記錄一次排列起來，可使一個無序文件變成有序文件的一種操作排序算法的穩(wěn)定性：相同元素排序前后的相對位置沒有發(fā)生變化，則為穩(wěn)定，反之為不穩(wěn)定內(nèi)部排序：在排序過程中，所有待排序記錄都放在內(nèi)存中進行的排序稱為內(nèi)部排序外部排序：當待排序的記錄很多，排序時不僅要使用內(nèi)存，而且還要使用外部存儲器的排序方法稱為外部排序簡答題：各排序方法的基本思想，時間復雜度，空間復雜度及穩(wěn)定性？直接插入排序的基本思想：直接插入排序是一種最簡單的排序方法，基本操作是將條記錄插入到已排好的有序表中，從而得到一個新的，記錄數(shù)量増一的有序表時間復雜度O（n2）空間復雜度O（1）直接插入排序是穩(wěn)定的希爾排序的基本思想：先將整個待排元素序列分割成若干子序列分別進行直接插入