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

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

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

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

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

5、執(zhí)行有限個步驟之后終止D. 以上三種描述都不對 (C)(C)算法的空間復(fù)雜度是指_。A. 算法程序的長度B. 算法程序中的指令條數(shù)C. 算法程序所占的存儲空間D. 算法執(zhí)行過程中所需要的存儲空間 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成_。A. 循環(huán)、分支、遞歸B. 順序、循環(huán)、嵌套C. 循環(huán)、遞歸、選擇D. 順序、選擇、循環(huán) 算法的復(fù)雜度主要包括_復(fù)雜度和空間復(fù)雜度。(D)(D)答：時間三.數(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ù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲結(jié)構(gòu)。常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的_。答：存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是指_。A. 數(shù)據(jù)所占的存儲空間量B. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示C. 數(shù)據(jù)在計算機(jī)中的順序存儲方式D. 存儲在外存中的數(shù)據(jù) (B)四.數(shù)據(jù)結(jié)構(gòu)的圖形表示：在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點；沒有后件的結(jié)點成為終端結(jié)點。插入和刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運算。還有查找、分類、合并、分解、復(fù)制和修改等。 （1）集合：松散的關(guān)系。（2）線性結(jié)構(gòu):一對一（3）樹形結(jié)構(gòu):一對多 （

7、4）圖狀結(jié)構(gòu):多對多 五.線性結(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)滿足：有且只有一個根結(jié)點；每個結(jié)點最多有一個前件，最多只有一個后件。 非線性結(jié)構(gòu)：如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。常見的線性結(jié)構(gòu)：線性表、棧、隊列 常見的非線性結(jié)構(gòu)：樹、圖 注意：鏈表也屬于線性表，所以也是線性結(jié)構(gòu)注意：鏈表也屬于線性表，所以也是線性結(jié)構(gòu)六.線性表的定義線性表是n 個元素構(gòu)成的有限序列（A1，A2，A3）。表中的每一個數(shù)據(jù)元素，除了第一個以外，有且只有一個前件。除了最后一個以外有且只有一個后件。即

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

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

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

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

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

13、指定的變量。首先將棧頂元素賦給一個指定的變量，然后將棧頂指針退一（TOP-1）讀棧頂元素：將棧頂元素賦給一個指定的變量。棧頂指針不會改變。 例、一疊書或一疊盤子。 棧的抽象數(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，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是_。A. ABCEDB. DBCEAC. CDABED. DCBEA 解題分析： A、B、C、D的出棧順序一定是DCBA

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

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

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

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

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

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

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

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

22、于2的結(jié)點),并且,二叉樹的子樹有左右之分,其次序不能任意顛倒。一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹，如圖(a)，按圖示給每個結(jié)點編號，如果有深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。注意： 滿二叉樹：除最后一層以外，每一層上的所有結(jié)點都有兩個子結(jié)點。在滿二叉樹的第K層上有2 2K-1K-1個結(jié)點，且深度為M的滿二叉樹有2 2M M-1-1個結(jié)點完全二叉樹：除最后一層以外，每一層上的結(jié)點數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點。具有N個結(jié)點的完全二叉樹的深度為log2n+1完全二叉樹總結(jié)點數(shù)

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

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

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

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

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

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

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