專(zhuān)業(yè)課資料附有答案

專(zhuān)業(yè)課資料[復(fù)制]名詞解釋?zhuān)?/p>

數(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)的總稱(chēng)，是計(jì)算機(jī)化的信息。

數(shù)據(jù)類(lèi)型：是一個(gè)值的集合以及定義在這個(gè)值集上的一組操作，可分為原子類(lèi)型和結(jié)構(gòu)類(lèi)型。

抽象數(shù)據(jù)類(lèi)型：是基于一類(lèi)邏輯關(guān)系的數(shù)據(jù)類(lèi)型以及定義在這個(gè)類(lèi)型之上的一組操作。

邏輯結(jié)構(gòu)：是數(shù)據(jù)元素之間邏輯關(guān)系的描述。

物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映像（又稱(chēng)表示），即數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方法。

算法：是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。

時(shí)間復(fù)雜度：算法執(zhí)行所需時(shí)間的量度。

空間復(fù)雜度：算法執(zhí)行所需存儲(chǔ)空間的量度。

存儲(chǔ)密度：指結(jié)點(diǎn)數(shù)據(jù)本身所占存儲(chǔ)量和整個(gè)結(jié)構(gòu)所占存儲(chǔ)量之比。

填空題：

程序設(shè)計(jì)的一些基本原則：分解、抽象和信息隱蔽。

根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，有四類(lèi)基本的數(shù)據(jù)結(jié)構(gòu)：集合結(jié)構(gòu)，線性結(jié)構(gòu)，樹(shù)形結(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)

常用的兩種存儲(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ù)元素本身的信息，無(wú)附加內(nèi)容。（優(yōu)點(diǎn)）[填空題]_________________________________2、可直接存儲(chǔ)數(shù)據(jù)元素。（優(yōu)點(diǎn)）[填空題]_________________________________3、存儲(chǔ)操作速度較快。（優(yōu)點(diǎn)）[填空題]_________________________________4、插入、刪除數(shù)據(jù)元素時(shí)，由于需要保持?jǐn)?shù)據(jù)元素之間的邏輯關(guān)系，必須大量移動(dòng)元素，因此實(shí)現(xiàn)起來(lái)比較慢。（缺點(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ù)分配空間問(wèn)題。[單選題]*線性結(jié)構(gòu)與非線性結(jié)構(gòu)的特點(diǎn)（或差異）？(正確答案)線性結(jié)構(gòu)的特點(diǎn)：是除第一個(gè)元素和最后一個(gè)元素外，每個(gè)數(shù)據(jù)元素都有唯一的前驅(qū)和唯一的后繼，第一個(gè)元素沒(méi)有前驅(qū)，最后一個(gè)元素沒(méi)有后繼，關(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ù)類(lèi)型的區(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ù)類(lèi)型是一個(gè)值的集合以及定義在這個(gè)值上的一組操作，可分為原子類(lèi)型和結(jié)構(gòu)類(lèi)型，它偏向于物理方面的線性表。名詞解釋?zhuān)壕€性表：是最常用，最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列，除首尾元素外，每個(gè)元素有唯一的前驅(qū)和唯一的后繼。順序表：采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱(chēng)為順序表。鏈表：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表通常稱(chēng)為順序表。結(jié)點(diǎn)：由數(shù)據(jù)元素和指示其后繼結(jié)點(diǎn)地址的信息組成的存儲(chǔ)映像稱(chēng)為結(jié)點(diǎn)。表長(zhǎng)：表中元素的個(gè)數(shù)稱(chēng)為表的表長(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è)指針域，其一指向直接前驅(qū)，另一指向直接后繼。靜態(tài)單鏈表：是利用一塊連續(xù)的空間，按鏈表的存儲(chǔ)方式組織數(shù)據(jù)，按順序存儲(chǔ)結(jié)構(gòu)分配空間，所構(gòu)成的一種鏈表。頭指針：是指向鏈表表頭結(jié)點(diǎn)的指針，只要鏈表存在，該指針始終不會(huì)改變，單鏈表由頭指針唯一確定，因單鏈表可以用頭指針的名字來(lái)命名。頭結(jié)點(diǎn)：在鏈表的開(kāi)始結(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)定性，方便表示空表。一元多項(xiàng)式的表示和相加可以使用鏈表實(shí)現(xiàn)。簡(jiǎn)答題：順序表的優(yōu)缺點(diǎn)？?jī)?yōu)點(diǎn)：1、無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間，存儲(chǔ)密度大2．可隨機(jī)存取表中的任一元素，查找方便[單選題]*缺點(diǎn)：1．插入，刪除運(yùn)算不方便，須移動(dòng)大量元素，效率較低(正確答案)2．存在預(yù)分配空間問(wèn)題[單選題]*鏈表的優(yōu)缺點(diǎn)？(正確答案)優(yōu)點(diǎn)：1．插入，刪除操作很方便2．空間利用率高[單選題]*缺點(diǎn)：1．查找不方便，需順鏈查找(正確答案)2．存儲(chǔ)密度小[單選題]*順序表和鏈表的區(qū)別和聯(lián)系及適用范圍？(正確答案)順序表：內(nèi)存中地址連續(xù)長(zhǎng)度一般不可變更支持隨機(jī)查找，可在O（1）內(nèi)查找元素適用于需要大量訪問(wèn)元素的，而少量増刪元素的程序鏈表：內(nèi)存中地址連續(xù)或非連續(xù)都可以長(zhǎng)度可實(shí)時(shí)變化不支持隨機(jī)查找，查找元素的時(shí)間復(fù)雜度為O（n）適用于需要大量增刪元素，而對(duì)訪問(wèn)元素幾乎無(wú)要求的程序頭指針和頭結(jié)點(diǎn)的作用？1．頭指針是指向鏈表表頭結(jié)點(diǎn)的指針，只要鏈表存在，該指針就不會(huì)變化，已知該指針便己知該鏈表[填空題]_________________________________2．頭結(jié)點(diǎn)是在鏈表的開(kāi)始結(jié)點(diǎn)之前夫婦家的一個(gè)結(jié)點(diǎn)，當(dāng)鏈表是空鏈表時(shí)，該指針為空指針，因此空表和非空表的處理也就統(tǒng)一了[單選題]*簡(jiǎn)述在單循環(huán)鏈表上尾指針取代頭指針的作用？(正確答案)在用頭指針表示的單循環(huán)鏈表中，找開(kāi)始結(jié)點(diǎn)a1的時(shí)間是O（1），然而要找終端結(jié)點(diǎn)an則需要從頭指針開(kāi)始遍歷整個(gè)鏈表，其時(shí)間是O（n），在很多實(shí)際問(wèn)題中，表的操作常常是在表尾進(jìn)行的，此時(shí)頭指針表示的單循環(huán)鏈表就顯得不夠方便，如果改用尾指針來(lái)表示單循環(huán)鏈表，則查找開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an都很方便查找時(shí)間都是O（1）名詞解釋?zhuān)簵＃阂步泻筮M(jìn)先出表，是限定僅在表尾進(jìn)行插入和刪除操作的線性表，表尾端稱(chēng)為棧頂，表頭端稱(chēng)為棧底，不含元素的空表稱(chēng)為空棧順序棧：采用順序存儲(chǔ)結(jié)構(gòu)的棧稱(chēng)為順序棧鏈棧：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱(chēng)為鏈棧．隊(duì)列：是一種先進(jìn)先出的線性表，它只允許在表的一段進(jìn)行插入，而另一端刪除元素，允許插入的一端叫做隊(duì)尾，允許刪除的一端稱(chēng)為隊(duì)首鏈隊(duì)列：用鏈表示的隊(duì)列，需要兩個(gè)指針?lè)謩e指示隊(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ì)列是將隊(duì)列的數(shù)據(jù)區(qū)看成頭尾相接的循環(huán)結(jié)構(gòu)，可解決“假溢出”雙端隊(duì)列：是限定插入，刪除在表的兩端進(jìn)行的線性表，這兩端分別稱(chēng)為端點(diǎn)。填空題棧的兩種存儲(chǔ)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)滿的判斷條件：s.top＝stack.size?？盏呐袛鄺l件：s.top＝0棧滿入棧棧上溢，?？粘鰲Ｏ乱珂湕Ｊ褂枚鄺９蚕砑夹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á)式求值，漢諾塔（遞歸用棧實(shí)現(xiàn)）簡(jiǎn)答題：什么是多棧共享技術(shù)？在一個(gè)程序中經(jīng)常會(huì)同時(shí)使用多個(gè)棧，使用順序存儲(chǔ)結(jié)構(gòu)的棧．空間大小難以估計(jì)，這樣使得有的棧已出，有的棧還有空閑空間，可以讓多個(gè)棧共享一個(gè)足夠大的連續(xù)向量空間（數(shù)組），通過(guò)利用棧的動(dòng)態(tài)特性來(lái)使其存儲(chǔ)空間互相補(bǔ)充，這就是多棧的共享技術(shù)，兩個(gè)棧共享空間，主要利用了“棧底位置不變，棧頂位置動(dòng)態(tài)變化”的特性順序隊(duì)列相比，循環(huán)隊(duì)列有哪些優(yōu)點(diǎn)？可解決假溢出現(xiàn)象（內(nèi)容自行拓展）簡(jiǎn)述線性表

棧，隊(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ī)則不同，線性表為隨機(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ù)的字符組成的子序列稱(chēng)作該串的子串主串：包含子串的串相應(yīng)的稱(chēng)為主串子串在主串中的位置：子串的第一個(gè)字符在主串中的位置表示空串：長(zhǎng)度為零的串稱(chēng)為空串空格串：串中元素均為空格的串稱(chē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)用：文本編輯串和線性表的區(qū)別？串的邏輯結(jié)構(gòu)與線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集，然而串的操作與線性表有很大的差別，在線性表基本操作中，大多以單個(gè)元素作為操作對(duì)象；而在串的基木操作中通常以“串的整體”作為操作對(duì)象簡(jiǎn)述靜態(tài)分配的順序串與動(dòng)態(tài)分配的順序串的區(qū)別？程序運(yùn)行前被分配以一個(gè)給定大小的數(shù)組空間的順序串稱(chēng)為靜態(tài)順序串，在程序運(yùn)行過(guò)程中，動(dòng)態(tài)分配空間能以鏈表形式存在的順序串稱(chēng)為動(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(wú)需移動(dòng)其他元素（內(nèi)容自行擴(kuò)充）廣義表：是由零個(gè)或多個(gè)單元素或子表所構(gòu)成的有限序列，是線性表的推廣，也有人稱(chēng)其為列表數(shù)組：類(lèi)型一致的有限個(gè)數(shù)據(jù)元素按順序連續(xù)存儲(chǔ)矩陣的壓縮存儲(chǔ)：有的矩陣中有許多值相同元素或者是零元素，為了節(jié)省存儲(chǔ)空間對(duì)這類(lèi)矩陣采用多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，有時(shí)零元素不存儲(chǔ)的存儲(chǔ)策略，稱(chēng)為矩陣的壓縮存儲(chǔ)特殊矩陣：值相同的元素或者零元素在矩陣中的分布有一定規(guī)律的矩陣稱(chēng)為特殊矩陣稀疏矩陣：非零的數(shù)據(jù)元素個(gè)數(shù)很少的矩陣稱(chēng)為稀疏矩陣對(duì)稱(chēng)矩陣：一個(gè)n階方陣，若滿足aij=aji，則稱(chēng)該矩陣為對(duì)稱(chēng)矩陣三角矩陣：主對(duì)角線上方和下方的元素（不包括對(duì)角線）均為常數(shù)或零元素的矩陣行表：記錄稀疏矩陣中每行非零元素在三元組表中的起始位置的表三元組表：若線性表順序存儲(chǔ)的每一個(gè)結(jié)點(diǎn)均是三元組，則該線性表的存儲(chǔ)結(jié)構(gòu)稱(chēng)為三元組表帶狀矩陣：所有非零元素均集中在以主對(duì)角線為中心的帶狀區(qū)域的矩陣數(shù)組的兩種存儲(chǔ)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)．?dāng)?shù)組的順序存儲(chǔ)有兩種方式：按行存儲(chǔ)和按列存儲(chǔ)．稀疏矩陣可以采用三元組表和十字鏈表來(lái)存儲(chǔ)廣義表和線性表的區(qū)別？1廣義表是線性表的推廣，是由零個(gè)或多個(gè)單元素或子表所構(gòu)成的有限序列[填空題]_________________________________2．線性表的成分都是結(jié)構(gòu)上不可分制的單個(gè)數(shù)據(jù)元素，而廣義表的成分既可以是單元素，也可以是有結(jié)構(gòu)的表其定義是遞歸的定義[單選題]*名詞解釋?zhuān)?正確答案)樹(shù)：是n個(gè)結(jié)點(diǎn)的有限集合，n≥0，有且只有一個(gè)稱(chēng)為根的結(jié)點(diǎn)，根結(jié)點(diǎn)無(wú)前驅(qū)有序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成是從左至右依次有序的，且不能交換森林：m（m≥1）棵互不相交的樹(shù)的集合二叉樹(shù)：是一種樹(shù)型的結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)之多有兩棵子樹(shù)，且有左右之分，不可任意顛倒。完全二又樹(shù)：深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)滿二叉樹(shù)：是一棵深度為k的，且有（2^k）-1個(gè)結(jié)點(diǎn)的二又樹(shù)遍歷二叉樹(shù)：是按照某種搜索路徑巡訪二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使得這些結(jié)點(diǎn)均被訪問(wèn)一次線索二叉樹(shù)：由每個(gè)結(jié)點(diǎn)中包含左指針，左標(biāo)志位，數(shù)據(jù)域，右標(biāo)志位，右指針五部分組成的二叉鏈表，叫做線索鏈表，指向前驅(qū)或后繼的指針叫做線索，以二又樹(shù)某種遍歷順序給空指針加線索的過(guò)程叫做線索化，線索化了的二叉樹(shù)稱(chēng)為線索二叉樹(shù)哈夫曼樹(shù)：又稱(chēng)最優(yōu)二叉樹(shù)，是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù)．哈夫曼編碼：在哈夫曼樹(shù)中，約定左分支代表0，右分支代表1，把葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑上的左右分支代表的碼從下至上一次連接起來(lái)，組成的字符串稱(chēng)為該葉子結(jié)點(diǎn)的哈夫曼編碼，這就是哈夫曼編碼二又排序樹(shù)：或者是空樹(shù)，或者是符合以下性質(zhì)的二叉樹(shù)1若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)均小于它的根結(jié)點(diǎn)值[填空題]_________________________________2．若它的右子樹(shù)不空則右子樹(shù)上所有結(jié)點(diǎn)均大于它的根結(jié)點(diǎn)值．[單選題]*平衡二叉排序樹(shù)（AVL樹(shù)）：或者是空樹(shù)，或者是符合一下性質(zhì)的二又排序樹(shù)(正確答案)1．左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值小于等于1[填空題]_________________________________2左子樹(shù)和右子樹(shù)也是平衡二叉排序樹(shù)[單選題]*在二叉樹(shù)中，第i層結(jié)點(diǎn)最多為2^k—1個(gè)深度為k的二又樹(shù)中，結(jié)點(diǎn)總數(shù)最多為（2^k）—1個(gè)二叉樹(shù)中，n0＝n2＋1，n2＝n0－1（no為二又樹(shù)中度為0的結(jié)點(diǎn)的個(gè)數(shù)n2為二叉樹(shù)中度為2的結(jié)點(diǎn)的個(gè)數(shù)）有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，深度為k，則k＝[log2n]＋1（log以2為底括號(hào)是向下取整不是方括號(hào)）k層的完全二叉樹(shù)至少有2^k－2個(gè)葉子結(jié)點(diǎn)二叉樹(shù)的兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)樹(shù)的三種常用的存儲(chǔ)方法：孩子表示法，雙親表示法和孩子兄弟表示法樹(shù)的遍歷方法：先根遍歷和后根遍歷簡(jiǎn)答題1非線性結(jié)構(gòu)的特點(diǎn)？表示結(jié)點(diǎn)間關(guān)系的前驅(qū)后繼不具有唯一性，結(jié)點(diǎn)間是一對(duì)多或多對(duì)多的關(guān)系二叉樹(shù)的五種基本形態(tài)？只有三個(gè)結(jié)點(diǎn)的二叉樹(shù)的五種形式？因?yàn)槎謽?shù)是有序樹(shù)，所有有左右之分，這是五棵不同的二叉樹(shù)，但若下列五棵是樹(shù)，不是二叉樹(shù)，則后面四種為同一棵樹(shù)名詞解釋?zhuān)?圖：圖G由兩個(gè)集合V和E組成，記為G＝（V，E），其中V是頂點(diǎn)的有窮非空集合，E是由V中頂點(diǎn)的序偶組成的有窮集，這些序偶稱(chēng)為邊或弧完全圖：邊數(shù)恰好等于n（n－1）/2的n個(gè)頂點(diǎn)的無(wú)向圖稱(chēng)為完全圖（無(wú)向圖中任意兩個(gè)頂點(diǎn)之間都有一條邊相連，稱(chēng)該圖為完全圖）有向完全圖：有n(n-1）條邊的有向圖稱(chēng)為有向完全圖（圖中每個(gè)頂點(diǎn)和其余n-1個(gè)頂點(diǎn)都有弧相連）入度：以頂點(diǎn)V為頭的弧的數(shù)目稱(chēng)為V的入度出度：以頂點(diǎn)V為尾的弧的數(shù)目稱(chēng)為V的出度連通圖：在無(wú)向圖中，任意兩個(gè)頂點(diǎn)之間都有路徑相通強(qiáng)連通圖：在有向圖中，任意兩個(gè)頂點(diǎn)之間都有來(lái)回路徑相通生成樹(shù)：生成樹(shù)是無(wú)向連通圖的一個(gè)極小連通子圖，它含有圖中的全部頂點(diǎn)和使任意頂點(diǎn)都連通的最少的邊鄰接矩陣：表示圖中結(jié)點(diǎn)之間關(guān)系的矩陣稱(chēng)為鄰接矩陣鄰接表：由頂點(diǎn)數(shù)據(jù)表和表示數(shù)據(jù)關(guān)系的邊（?。?gòu)成的表十字鏈表：可以把它看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)形成的一種存儲(chǔ)形式圖的遍歷：從某一頂點(diǎn)出發(fā)按序訪問(wèn)圖中所有結(jié)點(diǎn)，且使每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次最小生成樹(shù)：無(wú)向網(wǎng)中邊上權(quán)值之和為最小的生成樹(shù)DAG：有向無(wú)環(huán)網(wǎng)拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上一個(gè)全序的操作稱(chēng)為拓?fù)渑判蜿P(guān)鍵路徑：在AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑稱(chēng)為關(guān)鍵路徑AOE網(wǎng)：用頂點(diǎn)表示事件，用弧表示活動(dòng)，弧的權(quán)值表示活動(dòng)所需的時(shí)間，構(gòu)造的有向網(wǎng)稱(chēng)為AOE網(wǎng)簡(jiǎn)單路徑：一條路徑上除了開(kāi)始頂點(diǎn)和結(jié)束頂點(diǎn)外，其余頂點(diǎn)均不相同弧頭：邊的終點(diǎn)稱(chēng)為弧頭弧尾：邊的始點(diǎn)稱(chēng)為弧尾填空題：1邊很少的圖稱(chēng)為稀疏圖，反之稱(chēng)為稠密圖有向圖中，所有頂點(diǎn)的入度與出度的和等于邊個(gè)數(shù)的2倍圖的存儲(chǔ)方法：鄰接矩陣，鄰接表，鄰接多重表，十字鏈表和邊集數(shù)組圖的深度優(yōu)先搜索類(lèi)似于樹(shù)的先根遍歷(正確答案)圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的層次遍歷連通圖→深度優(yōu)先搜索遍歷→深度搜索生成樹(shù)連通圖→廣度優(yōu)先搜索遍歷→廣度搜索生成樹(shù)簡(jiǎn)答題111鄰接矩陣表示法的特點(diǎn)？1．對(duì)于無(wú)向圖而言，它的鄰接矩陣是對(duì)稱(chēng)矩陣，因此可以采用特殊矩陣的壓縮存儲(chǔ)法，但對(duì)于有向圖而言，其中的弧是有方向的，因此有向圖的鄰接矩陣不一定是對(duì)稱(chēng)矩陣，對(duì)于有向圖的鄰接矩陣的存儲(chǔ)則需要n*n個(gè)存儲(chǔ)空間．[填空題]_________________________________2．采用鄰接矩陣表示法，便于判斷圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連，即根據(jù)鄰接矩陣中的信息來(lái)判斷，另外還便于求得各個(gè)頂點(diǎn)的度，對(duì)于無(wú)向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個(gè)頂點(diǎn)的度[單選題]*鄰接表表示法的特點(diǎn)？(正確答案)1．n個(gè)頂點(diǎn)，e條邊的無(wú)向圖，若采取鄰接表作為存儲(chǔ)結(jié)構(gòu)，需要n個(gè)頂點(diǎn)數(shù)據(jù)和2e個(gè)表示邊的結(jié)點(diǎn)，顯然在邊很稀疏的情況下，用鄰接表存儲(chǔ)所需的空間比鄰接矩陣所需的空間少[填空題]_________________________________2．無(wú)向圖的度，在無(wú)向圖的鄰接表中，頂點(diǎn)Vi的度恰好就是第i個(gè)邊鏈表上結(jié)點(diǎn)的[填空題]_________________________________3．有向圖的度，在有向圖中，第i個(gè)邊鏈表上結(jié)點(diǎn)的個(gè)數(shù)就是頂點(diǎn)Vi的出度，只需通過(guò)表頭向量表中找到第i個(gè)頂點(diǎn)的邊鏈表的頭指針，實(shí)現(xiàn)順鏈查找計(jì)數(shù)即可[單選題]*DFS（深度優(yōu)先搜索遍歷）的基本思路？(正確答案)假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問(wèn)過(guò)，則深度優(yōu)先搜索可從某個(gè)頂點(diǎn)V出發(fā)，首先訪間此頂點(diǎn)（稱(chēng)此頂點(diǎn)為初始點(diǎn)），然后依次從V的任一個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷，直到圖中所有與有路徑相通的頂點(diǎn)都被訪問(wèn)到，若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作為初始點(diǎn)，重復(fù)上述步驟，直到圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止BFS（廣度優(yōu)先搜索遍歷）的基本思路？1．從圖中某個(gè)頂點(diǎn)VO出發(fā)，首先訪問(wèn)VO，依次訪問(wèn)Vo的各個(gè)未被訪間的鄰接點(diǎn)[填空題]_________________________________2．分別從這些鄰接點(diǎn)（端結(jié)點(diǎn)）出發(fā)，依次訪問(wèn)各個(gè)未被訪問(wèn)的鄰接點(diǎn)，訪問(wèn)時(shí)應(yīng)保證：如果Vi和Vk為當(dāng)前結(jié)點(diǎn)，且Vi在Vk之前被訪問(wèn)，則Vi的所有未被訪問(wèn)的鄰接點(diǎn)應(yīng)在Vk的所有未被訪問(wèn)的鄰接點(diǎn)之前訪問(wèn)[填空題]_________________________________3．重復(fù)步驟2，直到所有結(jié)點(diǎn)均沒(méi)有未被訪問(wèn)的鄰接點(diǎn)[填空題]_________________________________4．若此時(shí)還有頂點(diǎn)未被訪問(wèn)，則選一個(gè)未被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至所有頂點(diǎn)均被訪問(wèn)過(guò)為止[單選題]*名詞解釋1(正確答案)關(guān)鍵字：是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以識(shí)別一個(gè)或一組數(shù)據(jù)元素査找：根據(jù)給定的關(guān)鍵字的值，檢索某個(gè)與該值相等的數(shù)據(jù)元素是否在查找表中找到為查找成功，找不到為查找失敗査找表：是由同一類(lèi)型的數(shù)據(jù)元素或記錄構(gòu)成的集合靜態(tài)査找表：査詢某個(gè)特定的數(shù)據(jù)元素是否在査找表中，檢素某個(gè)特定的數(shù)據(jù)元素的各種屬性動(dòng)態(tài)査找表：在查找過(guò)程中同時(shí)插入查找不存在的數(shù)據(jù)元素，或者從査找表中刪除已存在的某個(gè)數(shù)據(jù)元素平均査找長(zhǎng)度（ASL）：為確定數(shù)據(jù)元素在査找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱(chēng)為查找算法在查找成功時(shí)的平均查找長(zhǎng)度．沖突：兩個(gè)不同的關(guān)鍵字，其散列函數(shù)值相同，因而被映射到同一表位置的現(xiàn)象稱(chēng)為沖突填空題1哈希函數(shù)的構(gòu)造方法：直接定址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法和隨機(jī)數(shù)法哈希函數(shù)處理沖突的方法：開(kāi)放地址法，再哈希法，鏈地址法和建立一個(gè)公共溢出區(qū)。簡(jiǎn)答題：1各查找方法的基本思想，平均査找長(zhǎng)度？順序查找的基本思路：對(duì)于給定的關(guān)鍵字k，從線性表的第一個(gè)元素開(kāi)始依次向后與記錄的關(guān)鍵字域相比較，如果某個(gè)記錄的關(guān)鍵字等于k，則查找成功，否則查找失敗，平均查找長(zhǎng)度ASL=3（n＋1）/4．折半（二分）查找的基本思路：先取表的中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行此較，若相等，則查找成功，如果給定關(guān)鍵字比該記錄的關(guān)鍵字小，則說(shuō)明所要查找的記錄只可能在表的前半部分，反之，則在后半部分，重復(fù)步驟，每一次比較就可以將查找范圍縮小一半，直到找到給定的關(guān)鍵字的記錄，查找成功，找不到為查找失敗，平均查找長(zhǎng)度ASL＝log2（n＋1）-1分塊查找（索引順序表查找）的基本思路：先確定待査記錄所在的塊（子表）然后在塊中順序查找．平均查找長(zhǎng)度ASL=1/2(n/s)+1]+s/2哈希查找（散列查找）的基本思路：在進(jìn)行查找時(shí)，在記錄的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系h，以線性表中每個(gè)元素的關(guān)鍵字k為自變量通過(guò)函數(shù)h（k）計(jì)算出該元素的存儲(chǔ)位置，我們將h函數(shù)稱(chēng)為散列函數(shù)或哈希函數(shù)，這種査找方法稱(chēng)為散列查找或哈希查找名詞解釋?zhuān)?排序：就是按關(guān)鍵字值的遞增或遞減的次序，把文件中的各記錄一次排列起來(lái)，可使一個(gè)無(wú)序文件變成有序文件的一種操作排序算法的穩(wěn)定性：相同元素排序前后的相對(duì)位置沒(méi)有發(fā)生變化，則為穩(wěn)定，反之為不穩(wěn)定內(nèi)部排序：在排序過(guò)程中，所有待排序記錄都放在內(nèi)存中進(jìn)行的排序稱(chēng)為內(nèi)部排序外部排序：當(dāng)待排序的記錄很多，排序時(shí)不僅要使用