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

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

2、數(shù)據(jù)元素之間邏輯關(guān)系的描述。物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映像（又稱表示），即數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方法。算法：是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。時(shí)間復(fù)雜度：算法執(zhí)行所需時(shí)間的量度?？臻g復(fù)雜度：算法執(zhí)行所需存儲(chǔ)空間的量度。存儲(chǔ)密度：指結(jié)點(diǎn)數(shù)據(jù)本身所占存儲(chǔ)量和整個(gè)結(jié)構(gòu)所占存儲(chǔ)量之比。填空題：程序設(shè)計(jì)的一些基本原則：分解、抽象和信息隱蔽。根據(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ù)的存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)剑ㄦ溄樱┐鎯?chǔ)結(jié)構(gòu)、索引結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)常用的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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