計(jì)算機(jī)二級(jí)C語言(公共基礎(chǔ)知識(shí)基本數(shù)據(jù)結(jié)構(gòu)與算法)

1、計(jì)算機(jī)二級(jí)C語言(公共基礎(chǔ)知識(shí)基本數(shù)據(jù)結(jié)構(gòu)與算法)計(jì)算機(jī)二級(jí)C語言(公共基礎(chǔ)知識(shí)基本數(shù)據(jù)結(jié)構(gòu)與算法)公共基礎(chǔ)知識(shí)公共基礎(chǔ)知識(shí) 基本要求基本要求1. 掌握算法的基本概念。2. 掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3. 掌握基本排序和查找算法。4. 掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。5. 掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。6. 掌握數(shù)據(jù)的基本知識(shí)，了解關(guān)系數(shù)據(jù)庫的設(shè)計(jì)一、數(shù)據(jù)結(jié)構(gòu)與算法一、數(shù)據(jù)結(jié)構(gòu)與算法 二、程序設(shè)計(jì)基礎(chǔ) 三、軟件工程基礎(chǔ) 四、數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ) 數(shù)據(jù)結(jié)構(gòu)與算法 1. 算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。2. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯

2、結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3. 線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。4. 棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6. 樹的基本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7. 順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。 一.算法的基本概念計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。就是指解題方案的準(zhǔn)確而完備的描述。一個(gè)算法通常由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作對(duì)象的運(yùn)算和操作，二

3、是算法的控制結(jié)構(gòu)算法的控制結(jié)構(gòu)。 1.算法的基本特征：可行性，確定性，有窮性可行性，確定性，有窮性，擁有足夠的情報(bào)。2.算法的基本要素：算法中對(duì)數(shù)據(jù)的運(yùn)算和操作、算法的控制結(jié)構(gòu)。3.算法設(shè)計(jì)的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。4.算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求效率與低存儲(chǔ)量需求 在計(jì)算機(jī)中，算法是指_。A. 查詢方法B. 加工方法C. 解題方案的準(zhǔn)確而完整的描述D. 排序方法 C二.算法的復(fù)雜度1.算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量2.算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間 算法的復(fù)雜度的表示算法

4、的復(fù)雜度的表示 時(shí)間復(fù)雜度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間量度記作T(n)=O(f(n) 表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。 空間復(fù)雜度：算法所需存儲(chǔ)空間的量度。記作：S(n)=O(f(n) 算法的時(shí)間復(fù)雜度是指_。A. 執(zhí)行算法程序所需要的時(shí)間B. 算法程序的長(zhǎng)度C. 算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)D. 算法程序中的指令條數(shù) 下面敘述正確的是_。A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)B. 算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)C. 算法的有窮性是指算法必須能在

5、執(zhí)行有限個(gè)步驟之后終止D. 以上三種描述都不對(duì) (C)(C)算法的空間復(fù)雜度是指_。A. 算法程序的長(zhǎng)度B. 算法程序中的指令條數(shù)C. 算法程序所占的存儲(chǔ)空間D. 算法執(zhí)行過程中所需要的存儲(chǔ)空間 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成_。A. 循環(huán)、分支、遞歸B. 順序、循環(huán)、嵌套C. 循環(huán)、遞歸、選擇D. 順序、選擇、循環(huán) 算法的復(fù)雜度主要包括_復(fù)雜度和空間復(fù)雜度。(D)(D)答：時(shí)間三.數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 1.數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線形結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)四種。2.

6、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的_。答：存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指_。A. 數(shù)據(jù)所占的存儲(chǔ)空間量B. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C. 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D. 存儲(chǔ)在外存中的數(shù)據(jù) (B)四.數(shù)據(jù)結(jié)構(gòu)的圖形表示：在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)。插入和刪除是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。還有查找、分類、合并、分解、復(fù)制和修改等。 （1）集合：松散的關(guān)系。（2）線性結(jié)構(gòu):一對(duì)一（3）樹形結(jié)構(gòu):一對(duì)多 （

7、4）圖狀結(jié)構(gòu):多對(duì)多 五.線性結(jié)構(gòu)和非線性結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)：非空數(shù)據(jù)結(jié)構(gòu)滿足：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，最多只有一個(gè)后件。 非線性結(jié)構(gòu)：如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。常見的線性結(jié)構(gòu)：線性表、棧、隊(duì)列 常見的非線性結(jié)構(gòu)：樹、圖 注意：鏈表也屬于線性表，所以也是線性結(jié)構(gòu)注意：鏈表也屬于線性表，所以也是線性結(jié)構(gòu)六.線性表的定義線性表是n 個(gè)元素構(gòu)成的有限序列（A1，A2，A3）。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)以外，有且只有一個(gè)前件。除了最后一個(gè)以外有且只有一個(gè)后件。即

8、線性表是一個(gè)空表，或可以表示為（a1,a2,an）, 其中ai(I=1,2,n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。非空線性表有如下一些特征：（1）有且只有一個(gè)根結(jié)點(diǎn)a1,它無前件；（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。 七.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序表指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表的順序存儲(chǔ)結(jié)構(gòu)具備如下兩個(gè)基本特征：1.線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；2.線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按

9、邏輯順序依次存放的。即線性表邏輯上相鄰、物理也相鄰，則已知第一個(gè)元素首地址和每個(gè)元素所占字節(jié)數(shù)，則可求出任一個(gè)元素首地址。 順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置_的存儲(chǔ)單元中。答：相鄰 假設(shè)線性表的每個(gè)元素需占用K個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系:LOC(ai+1)=LOC(ai)+KLOC(ai)=LOC(a1)+(i-1)*K 其中，LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。因?yàn)樵陧樞虼鎯?chǔ)結(jié)

10、構(gòu)中，每個(gè)數(shù)據(jù)元素地址可以通過公式計(jì)算得到，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。在線性表的順序存儲(chǔ)結(jié)構(gòu)下，可以對(duì)線性表做以下運(yùn)算：插入、刪除、查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)八.順序表的插入運(yùn)算線性表的插入運(yùn)算是指在表的第I個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表（a1,a2 aian）變成長(zhǎng)度為n+1的線性表(a1,a2x,aian).該算法的時(shí)間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語句上，執(zhí)行次數(shù)是n-I+1。當(dāng)I=n+1,最好情況，時(shí)間復(fù)雜度o(1) 當(dāng)I=1, 最壞情況，時(shí)間復(fù)雜度o(n)算法的平均時(shí)間復(fù)雜度為o(n) 九.順序表的刪除運(yùn)算線性表的刪除運(yùn)算是指在表的第I個(gè)位置上，

11、刪除一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表（a1,a2 aian）變成長(zhǎng)度為n-1的線性表(a1,a2ai-1,ai+1an).當(dāng)I=n,時(shí)間復(fù)雜度o(1),當(dāng)I=1,時(shí)間復(fù)雜度o(n) ,平均時(shí)間復(fù)雜度為o(n) 順序表的插入運(yùn)算過程十.棧的的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算1.什么是棧？ 棧實(shí)際上也是一個(gè)線性表，只不過是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂（TOP），另一端為棧底（BOTTOM）。當(dāng)表中沒有元素時(shí)稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。假設(shè)棧S=（a1,

12、a2,a3,an），則a1 稱為棧底元素，an稱為棧頂元素。棧中元素按a1,a2,a3an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)該是棧頂元素。即后進(jìn)先出。注意： 棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。棧的表尾稱為棧頂，表頭稱為棧底，不含元素的空表稱為空棧。棧又稱后進(jìn)先后進(jìn)先出出（LIFO，last in first out）的線性表。 2.棧的順序存儲(chǔ)及其運(yùn)算用S（1：M）作為棧的順序存儲(chǔ)空間。M為棧的最大容量。棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。入棧運(yùn)算：在棧頂位置插入一個(gè)新元素。首先將棧頂指針進(jìn)一（TOP+1），然后將新元素插入到棧頂指針指向的位置。退棧運(yùn)算：指取出棧頂元素并賦給一個(gè)

13、指定的變量。首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針退一（TOP-1）讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。棧頂指針不會(huì)改變。 例、一疊書或一疊盤子。 棧的抽象數(shù)據(jù)類型的定義如下： a n a n-1 a2 a1棧頂top 棧底bottom下列關(guān)于棧的敘述中正確的是_。 A. 在棧中只能插入數(shù)據(jù)B. 在棧中只能刪除數(shù)據(jù)C. 棧是先進(jìn)先出的線性表D. 棧是先進(jìn)后出的線性表 棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是_。A. ABCEDB. DBCEAC. CDABED. DCBEA 解題分析： A、B、C、D的出棧順序一定是DCBA

14、,E在其中任何位置都可以(D)(D)十一.隊(duì)列的的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算1.什么是隊(duì)列隊(duì)列是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做隊(duì)頭，允許插入的一端叫做隊(duì)尾。隊(duì)列的修改是先進(jìn)先出。往隊(duì)尾插入一個(gè)元素成為入隊(duì)運(yùn)算。從對(duì)頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。注意： 隊(duì)列隊(duì)列：限定僅在表的一端進(jìn)行插入，在另一端進(jìn)行刪除操作的線性表。是一種先進(jìn)先出先進(jìn)先出（FIFO，first in first out）的線性表。允許插入的的一端叫隊(duì)尾，允許刪除的一端則稱為隊(duì)頭。 下圖是隊(duì)列的示意圖： a1a2an出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾 由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，因而要設(shè)兩個(gè)指針和分別指示隊(duì)頭和隊(duì)尾元素

15、在隊(duì)列中的位置，它們的初始值隊(duì)列初始化時(shí)均應(yīng)置為。入隊(duì)時(shí)將新元素插入所指的位置，然后將加。出隊(duì)時(shí)，刪去所指的元素，然后將加并返回被刪元素。由此可見，當(dāng)頭尾指針相等時(shí)隊(duì)列為空。在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素的下一位置。 0 1 2 3FrontrearabcFront rear (a)隊(duì)列初始為空（b）A,B,C入隊(duì) b c front rear front rear （c) a出隊(duì) (d) b,c出隊(duì)，隊(duì)為空和棧類似，隊(duì)列中亦有上溢和下溢現(xiàn)象。此外，順序隊(duì)列中還存在“假上溢”現(xiàn)象。因?yàn)樵谌腙?duì)和出隊(duì)的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無法重新利

16、用。因此，盡管隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊(duì)操作。該現(xiàn)象稱為假上溢。下列關(guān)于隊(duì)列的敘述中正確的是_。A. 在隊(duì)列中只能插入數(shù)據(jù)B. 在隊(duì)列中只能刪除數(shù)據(jù)C. 隊(duì)列是先進(jìn)先出的線性表D. 隊(duì)列是先進(jìn)后出的線性表 (C)2.循環(huán)隊(duì)列及其運(yùn)算在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，從隊(duì)頭指針front指向的后一個(gè)位置直到隊(duì)尾指針 re

17、ar指向的位置之間所有的元素均為隊(duì)列中的元素。 克服上述假上溢現(xiàn)象的方法 是將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（Circular Queue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1，朝前移動(dòng)。只不過當(dāng)頭尾指針指向向量上界（QueueSize-1）時(shí)，其加1操作的結(jié)果是指向向量的下界0在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)滿還是隊(duì)列空，通常需要增加一個(gè)標(biāo)志S：隊(duì)列空，則S=0，rear=front=m 隊(duì)列滿，則S=1，rear=front=m循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算入隊(duì)運(yùn)算指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素，首

18、先rear=rear+1,當(dāng)rear=m+1時(shí)，置rear=1,然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)S=1，rear=front,說明隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，稱為“上溢”。退隊(duì)運(yùn)算指在循環(huán)隊(duì)列的隊(duì)頭位置退出一個(gè)元素并賦給指定的變量。首先front=front+1,并當(dāng)front=m+1時(shí)，置front=1,然后將對(duì)頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空S=0，不能進(jìn)行退隊(duì)運(yùn)算，這種情況成為“下溢”。 存儲(chǔ)結(jié)構(gòu): 以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線性表稱之為線性鏈表。缺點(diǎn)是不容易找到直接前趨。頭指針只相當(dāng)于結(jié)點(diǎn)的指針域，頭結(jié)點(diǎn)即整個(gè)線性鏈表的第一個(gè)結(jié)點(diǎn)，它的數(shù)據(jù)域可以放數(shù)據(jù)元素，也可以放線性表的

19、長(zhǎng)度等附加信息，也可以不存儲(chǔ)任何信息。 十三.線性鏈表的基本運(yùn)算 1.線性鏈表的插入 2.線性鏈表的刪除 用鏈表表示線性表的優(yōu)點(diǎn)是_。A. 便于插入和刪除操作B. 數(shù)據(jù)元素的物理順序與邏輯順序相同C. 花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少D. 便于隨機(jī)存取 (A)十四十四. .雙向鏈表的雙向鏈表的存儲(chǔ)結(jié)構(gòu)：在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。 十五.循環(huán)鏈表的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。因此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。 在 中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)

20、依次依次訪問到表中其他所有結(jié)點(diǎn)。 A線性單鏈表 B雙向鏈表 C線性鏈表 D循環(huán)鏈表 這里的關(guān)鍵詞是“依次依次”，線性單鏈表不能找到前面的節(jié)點(diǎn)。這題有2個(gè)答案。（B，D）一、樹的定義：樹是n(n=0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中： (1)有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)； (2)當(dāng)n1時(shí),其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,.Tm,其中每一個(gè)集合本身又是一棵樹,并且稱為根的子樹. 二、樹的基本概念：樹的結(jié)點(diǎn)結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度度。度為0的結(jié)點(diǎn)稱為葉子葉子或終端結(jié)點(diǎn)終端結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)分

21、支結(jié)點(diǎn)。 樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值。結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子孩子，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親雙親。同一個(gè)雙親的孩子之間互稱兄弟兄弟。結(jié)點(diǎn)的祖先祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫子孫。 結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的孩子為第二層。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹中結(jié)點(diǎn)的最大層次稱為樹的深度，或高度。如果將樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的，則稱該樹為有序樹，否則稱為無序樹。森林是m(m=0)棵互不相交的樹的集合。 十七.二叉樹的定義二叉樹是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大

22、于2的結(jié)點(diǎn)),并且,二叉樹的子樹有左右之分,其次序不能任意顛倒。一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹，如圖(a)，按圖示給每個(gè)結(jié)點(diǎn)編號(hào)，如果有深度為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í)，稱之為完全二叉樹。注意： 滿二叉樹：除最后一層以外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。在滿二叉樹的第K層上有2 2K-1K-1個(gè)結(jié)點(diǎn)，且深度為M的滿二叉樹有2 2M M-1-1個(gè)結(jié)點(diǎn)完全二叉樹：除最后一層以外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1完全二叉樹總結(jié)點(diǎn)數(shù)

23、為N，N為奇數(shù)，則葉子結(jié)點(diǎn)數(shù)為（N+1N+1）/2/2 若N為偶數(shù)，則葉子結(jié)點(diǎn)數(shù)為N/2N/2。（即。（即N/2N/2向上取整）向上取整） 性質(zhì)：在二叉樹的第i層上至多有2i-1次方個(gè)結(jié)點(diǎn)(i=1)。性質(zhì)：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k=1)。性質(zhì)：對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。性質(zhì)：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為|log2n|+1性質(zhì)：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1=i=1,則雙親PARENT(i)是結(jié)點(diǎn)i/2(2)如果2in,則結(jié)點(diǎn)i無左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn));否則其左孩子LCHILD

24、(i)是結(jié)點(diǎn)2i(3)如果2i+1n,則結(jié)點(diǎn)i無右孩子;否則其右孩子RCHILD(i)是結(jié)點(diǎn)2i+11、設(shè)一棵完全二叉樹共有699個(gè)結(jié)點(diǎn)，則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為_。 A.349 B. 350 C. 255 D. 351 2、在一棵二叉樹上第5層的結(jié)點(diǎn)數(shù)最多是_。A. 8 B. 16 C. 32 D. 15 3、在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為4、以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是_。A. 隊(duì)列 B. 線性表 C. 二叉樹 D. 棧5、樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是（ ）6、具有3個(gè)結(jié)點(diǎn)的二叉樹有（ ）種形態(tài)(B)(B)(16)（C）有且只有1（5）二叉樹的存儲(chǔ)結(jié)構(gòu) 二叉樹通常

25、采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 十八十八. .遍歷二叉樹遍歷二叉樹的三種方法：先序先序：1、訪問根結(jié)點(diǎn)2、先序訪問左子樹3、先序訪問右子樹中序中序1、中序訪問左子樹2、中序訪問根結(jié)點(diǎn)3、中序訪問右子樹后序后序1、后序訪問左子樹2、后序訪問右子樹3、訪問根結(jié)點(diǎn)先序遍歷結(jié)果：1,2,4,5,6,7,3中序遍歷結(jié)果：4,2,6,5,7,1,3后序遍歷結(jié)果：4,6,7,5,2,3,11、設(shè)一棵二叉樹中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為（13）分析 2、已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（cedba）分析3、已知一棵二叉樹前序遍歷和中序遍歷分別為

26、ABDGCFK和DGBAFCK，則該二叉樹的后序遍歷為（B）分析 A、ACFKBDG B、GDBFKCA C、KCFAGDB D、ABCDFKG 4、若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是（gdbehfca）十九.順序查找與二分查找 順序查找順序查找：從表中最后一個(gè)記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，查找不成功。平均查找長(zhǎng)度：3(n+1)/4在兩種情況下只能用順序查找： 1、線性表（順序或鏈?zhǔn)剑闊o序表 2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的有序表 二分查找（折半

27、查找）二分查找（折半查找）只適用于順序存儲(chǔ)的有序表（從小到大）。對(duì)于長(zhǎng)度為N的有序線性表，在最壞情況下，二分查找只需要比較log2N次，而順序查找要比較N次。 先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。 對(duì)長(zhǎng)度為N的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為_。A. N+1B. NC. (N+1)/2D. N/2 (B)二分查找查找過程二十.排序排序排序排序：將一個(gè)數(shù)據(jù)元素的無序序列重新排列成一個(gè)按關(guān)鍵字有序的序列。直接插入排序直接插入排序:是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。排序過程：38,49,65,97,

28、76,13,27,49,.二十.交換類排序法冒泡排序與快速排序法屬于交換類的排序方法冒泡排序法 假設(shè)線性表的長(zhǎng)度為N，則在最壞的情況下，冒跑排序需要經(jīng)過N/2遍的從前往后的掃描和N/2遍的從后往前的掃描，需要的比較次數(shù)為N（N-1）/2（1 1）起泡排序：）起泡排序：首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。直至第n-1個(gè)記錄和第n個(gè)記錄的關(guān)鍵字進(jìn)行過比較為止。然后進(jìn)行第二趟起泡排序，對(duì)前n-1個(gè)記錄進(jìn)行同樣操作。.直到在某趟排序過程中沒有進(jìn)行過交換記錄的操作為止。 在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為_。答：n

29、(n-1)/2或n*(n-1)/2或O(n(n-1)/2)或O(n*(n-1)/2)（2）快速排序）快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。 二十一.選擇類排序法 1.簡(jiǎn)單選擇排序法 2.堆排序二十二.插入類排序法 1.簡(jiǎn)單插入排序法2.希爾排序交換類排序交換類排序 冒泡排序：最壞n(n-1)/2 ；最簡(jiǎn)單的交換排序。在待排序的元素序列基本有序的前提下，效率最高?？焖倥判颍鹤顗膎(n-1)/2； 最好 O(Nlog2 N) 插入排序插入排序 簡(jiǎn)單插入排序：最壞 n(n-1)/2 ；每個(gè)元素距其最終位置每個(gè)元素距其最終位置不遠(yuǎn)時(shí)適用不遠(yuǎn)時(shí)適用。 希爾排序：最壞 O(n1.5) 選擇排序選擇排序 簡(jiǎn)單選擇排序：最壞 n(n-1)/2 堆排序：最壞 O(nlog2n) ，適用于較大規(guī)模的線性表。 希