1、數(shù)據(jù)結(jié)構(gòu)（一）一、選擇題1組成數(shù)據(jù)的基本單位是（ C ）。 (A) 數(shù)據(jù)項(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量2設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D=1，2，3，4，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是（ C ）。(A) 線性結(jié)構(gòu)(B) 樹型結(jié)構(gòu) (C) 圖型結(jié)構(gòu)(D) 集合3數(shù)組的邏輯結(jié)構(gòu)不同于下列（ D ）的邏輯結(jié)構(gòu)。(A) 線性表(B) 棧 (C) 隊列(D) 樹4二叉樹中第i(i1)層上的結(jié)點數(shù)最多有（C ）個。(A) 2i(B) 2i(C) 2i-1(D) 2i-15設(shè)指針變量p指向單鏈表結(jié)點A，則刪除結(jié)點A的后繼結(jié)點B需要的操作為（A ）。(A) p-next=p-next-nex

2、t(B) p=p-next(C) p=p-next-next(D) p-next=p6設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應(yīng)該是（ C ）。(A) 6(B) 4(C) 3(D) 27將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（ C ）。(A) 100(B) 40(C) 55(D) 808設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點，則結(jié)點B的度數(shù)數(shù)為（ B ）。(A) 3(B) 4(C) 5(D) 19根據(jù)二叉樹的定義可知二叉

3、樹共有（ B ）種不同的形態(tài)。(A) 4(B) 5(C) 6(D) 710. 設(shè)有以下四種排序方法，則（ B ）的空間復(fù)雜度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希爾排序11、以下說法正確的是 （ A ）A.連通圖的生成樹，是該連通圖的一個極小連通子圖。B.無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一定是不對稱的。C.任何一個有向圖，其全部頂點可以排成一個拓撲序列。D.有回路的圖不能進行拓撲排序。12、以下說法錯誤的是 ( D ) A.一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近B.哈夫曼樹中沒有度數(shù)為1的分支結(jié)點C.若初始森林中共有n裸二叉樹，最終求得的哈夫曼樹共有2n

4、-1個結(jié)點D.若初始森林中共有n裸二叉樹，進行2n-1次合并后才能剩下一棵最終的哈夫曼樹13、如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是( B ) A.完全圖 B.連通圖 C.有回路 D.一棵樹14、將一棵有50個結(jié)點的完全二叉樹按層編號，則對編號為25的結(jié)點x，該結(jié)點(B ) A.無左、右孩子 B.有左孩子，無右孩子C.有右孩子，無左孩子 D.有左、右孩子15、深度為6的二叉樹最多有(B )個結(jié)點 A.64 B.63 C.32 D.3116、一個有序順表有255個對象，采用順序搜索法查表，搜索長度為（ A ）。A、128 B、127 C、126 D、2551

5、7、在有向圖中每個頂點的度等于該頂點的（ C ）。A. 入度 B. 出度C. 入度與出度之和 D. 入度與出度之差18、具有n個頂點的有向無環(huán)圖最多可包含( D )條有向邊。 An-1 Bn Cn(n-1)/2 Dn(n-1)19、用鄰接表作為有向圖G的存儲結(jié)構(gòu)。設(shè)有n個頂點、e條弧，則拓撲排序的時間復(fù)雜度為(B ) A. O(n) B. O(n+e) C. O(e) D. O(n*e)20、一個有序順表有255個對象，采用順序搜索法查表，搜索長度為（A）。A、128 B、127 C、126 D、25521、在有向圖中，所有頂點的入度之和是所有頂點出度之和的（B）倍。 A.0.5 B. 1 C

6、. 2 D.4 22、以下說法錯誤的是（B）A.用相鄰矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。B.鄰接表法只能用于有向圖的存儲，而相鄰矩陣法對于有向圖和無向圖的存儲都適用。C.存儲無向圖的相鄰矩陣是對稱的，因此只要存儲相鄰矩陣的下（或上）三角部分就可以了D.用相鄰矩陣A表示圖，判定任意兩個結(jié)點Vi和Vj之間是否有長度為m的路徑相連，則只要檢查A的第 i行第j列的元素是否為0即可。23、在圖的鄰接表存儲結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類似于二叉樹上的（ A ）A.先根遍歷 B. 中根遍歷 C. 后根遍歷 D按層次遍歷24、在一個無向圖中

7、，所有頂點的度數(shù)之和等于所有邊數(shù)的（ B ）倍。A3 B2 C1 D1/225、在無向圖中，所有頂點的度數(shù)之和是所有邊數(shù)的（ C ）倍。A.0.5 B.1 C.2 D.4 26、設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有（B）條邊能確保是一個連通圖。 A. 5 B. 6 C. 7 D. 827、以下說法正確的是（ D ）A.連通分量是無向圖中的極小連通子圖。B.強連通分量是有向圖中的極大強連通子圖。C.在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧。D.對有向圖G,如果從任意頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖。二、填空題1. 設(shè)順序循環(huán)隊列Q0

8、：m-1的隊頭指針和隊尾指針分別為F和R，其中隊頭指針F指向當(dāng)前隊頭元素的前一個位置，隊尾指針R指向當(dāng)前隊尾元素所在的位置，則出隊列的語句為F =_;。2. 設(shè)線性表中有n個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為_，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為_。3. 設(shè)一棵二叉樹中有n個結(jié)點，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時，該二叉鏈表中共有_個指針域，_個空指針域。4. 設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點B，則在結(jié)點A的后面插入結(jié)點B的操作序列為_。5. 設(shè)無向圖G中有n個頂點和e條邊，則其對應(yīng)的鄰接表中有_個表頭結(jié)點和_個表結(jié)點。6. 設(shè)無向圖

9、G中有n個頂點e條邊，所有頂點的度數(shù)之和為m，則e和m有_關(guān)系。7. 設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為_。8. 設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點的編號是_，編號為8的左孩子結(jié)點的編號是_。9. 下列程序段的功能實現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。int index(char s , char t )i=j=0;while(istrlen(s) & jnext=p-next; s-next=s5. n, 2e6. m=2e7. CBA8. 4，169. i-

10、j+1，010. n-1三、應(yīng)用題1. 鏈?zhǔn)酱鎯Y(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。2. 哈夫曼樹略，WPL=783. (18,5,16,19,21,23)，(5，16，21，19，18，23)4. 線性探測： 數(shù)據(jù)結(jié)構(gòu)（二）一、選擇題1下面關(guān)于線性表的敘述錯誤的是（ ）。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C) 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（ ）個空指針域。(A

11、) 2m-1(B) 2m(C) 2m+1(D) 4m3設(shè)順序循環(huán)隊列Q0：M-1的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（ ）。(A) R-F(B) F-R(C) (R-F+M)M(D) (F-R+M)M4設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA5設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有（ ）條邊。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-16設(shè)某棵二

12、叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（ ）。(A) 9(B) 10(C) 11(D) 127設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有（ ）個表頭結(jié)點。(A) n-1(B) n(C) n+1(D) 2n-18設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進行一趟快速排序的結(jié)果為（ ）。(A) 2，3，5，8，6(B) 3，2，5，8，6(C) 3，2，5，6，8(D) 2，3，6，5，8二、填空題1. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是_和_。2. 下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。typedef s

13、truct int s100; int top; sqstack;void push(sqstack &stack,int x)if (stack.top=m-1) printf(“overflow”);else _;_;3. 中序遍歷二叉排序樹所得到的序列是_序列（填有序或無序）。4. 快速排序的最壞時間復(fù)雜度為_，平均時間復(fù)雜度為_。5. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點數(shù)為_；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_個空指針域。6. 設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_。7. 設(shè)一組

14、初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為_。8. 設(shè)某無向圖G的鄰接表為，則從頂點V1開始的深度優(yōu)先遍歷序列為_；廣度優(yōu)先遍歷序列為_。三、應(yīng)用題1 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，47，40，20，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2 設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink）。3 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法

15、用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4 設(shè)一棵樹T中邊的集合為(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5 設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。7、給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)。8、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法, 試舉例說明。9、給出下圖鄰接矩陣和鄰

16、接表兩種存儲結(jié)構(gòu)；寫出圖的拓撲序列。V2V1V3V6V5V41 （二）參考答案一、選擇題1.D2.B3.C4.A5.A6.C7.B8.C二、填空題1. 構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法2. stack.top+，stack.sstack.top=x3. 有序4. O(n2)，O(nlog2n)5. N0-1，2N0+N16. d/27. (31，38，54，56，75，80，55，63)8. (1，3，4，2)，(1，3，2，4)三、應(yīng)用題1. (20，40，45，47，80，78)，(40，45，47，80，20，78)2. q-llink=p; q-rlink=p-rlink;

17、 p-rlink-llink=q; p-rlink=q;3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略5. E=(1，3)，(1，2)，(3，5)，(5，6)，(6，4)6. 略8、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法, 試舉例說明?！窘獯稹?2) 簡單選擇排序 275 275* 512 061 i = 1 061275* 512 275 i = 2 061 275* 512 275 i = 3 061 275* 275 512 (3) 快速排序 512275 275* 275*275 512 (4) 堆排序 275 275* 06

18、1 170 已經(jīng)是最大堆，交換275與170 170 275* 061 275 對前3個調(diào)整 275* 170 061 275 前3個最大堆，交換275*與061 061 170 275* 275 對前2個調(diào)整 170 061 275* 275 前2個最大堆，交換170與061 061 170 275* 275 數(shù)據(jù)結(jié)構(gòu)（三）一、選擇題1設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有（ ）個表頭結(jié)點。(A) 2n(B) n(C) n/2(D) n(n-1)2設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（ ）條邊。(A) n(B) n-1(C) 2n(D) 2n-13設(shè)一組初始記錄關(guān)鍵字序列

19、為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（ ）。(A) 40，42，60，55，80，85(B) 42，45，55，60，85，80(C) 42，40，55，60，80，85(D) 42，40，60，85，55，804（ ）二叉排序樹可以得到一個從小到大的有序序列。(A) 先序遍歷(B) 中序遍歷(C) 后序遍歷(D) 層次遍歷5設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（ ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-16程序段s=i=0；do i=i+1； s=s+i

20、；while(inext=0(C) head-next=head(D) head!=08設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（ ）。(A) 20(B) 256(C) 512(D) 10249設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（ ）。(A) 1(B) 2(C) 3(D) 410.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（ ）。(A) top=top+1;(B) top=top-1;(C) top-next=top;(D) top=top-nex

21、t;二、判斷題1、數(shù)據(jù)的最小單位是數(shù)據(jù)項。.( )2、多重表文件中主索引為非稠密索引，次索引為稠密索引。.( )3、通常數(shù)據(jù)結(jié)構(gòu)在計算機中有四種不同的表示方法分為順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲、文件存儲。.( )4、算法具有輸入、輸出、可行性、穩(wěn)定性、有窮性五個特性。.( )5、數(shù)據(jù)的基本單位是數(shù)據(jù)項。.( )6、算法的復(fù)雜度分為時間復(fù)雜度和效率復(fù)雜度。.( )7、性質(zhì)相同的數(shù)據(jù)元素的集合成為數(shù)據(jù)對象。.( )8、所有結(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是集合結(jié)構(gòu)。.( )9、散列文件不能順序存取、只能按關(guān)鍵字隨機存取。.( )10、數(shù)據(jù)的基本單位是數(shù)據(jù)元素。.( )11不論是入隊列操作還

22、是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（ ）12當(dāng)向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（ ）13由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（ ）14線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（ ）15.帶權(quán)無向圖的最小生成樹是唯一的。（ ）16.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。（）17.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中的從源點到匯點的最短路徑。（）18. 由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（ ）19.堆排序是不穩(wěn)定的排序方法。（）20.查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合()三、填空題1. 設(shè)指針變量p指向雙向鏈表中的結(jié)點A

23、，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為_=p；s-right=p-right；_=s； p-right-left=s；（設(shè)結(jié)點中的兩個指針域分別為left和right）。2. 設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有_條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有_條無向邊。3. 設(shè)關(guān)鍵字序列為(Kl，K2，Kn)，則用篩選法建初始堆必須從第_個元素開始進行篩選。4. 解決散列表沖突的兩種方法是_和_。5. 設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有_個。6. 高度為h的完全二叉樹中最少有_個結(jié)點，

24、最多有_個結(jié)點。7. 設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是_。8. 設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是_。9. 設(shè)一棵二叉樹的前序序列為ABC，則有_種不同的二叉樹可以得到這種序列。10. 下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。struct record int key;datatype others;void quickpass(struct record r, int s, int t, int &i) int j=t; struct

25、record x=rs; i=s; while(ij) while (ix.key) j=j-1; if (ij) ri=rj;i=i+1; while (_) i=i+1; if (ileft=p，p-right2. n(n-1)，n(n-1)/23. n/24. 開放定址法，鏈地址法5. 146. 2h-1，2h-17. (12，24，35，27，18，26)8. (12，18，24，27，35，26)9. 510. ij & ri.keyx.key，ri=x數(shù)據(jù)結(jié)構(gòu)（四）一、選擇題1設(shè)輸入序列是1、2、3、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（ c ）

26、。(A) n-i(B) n-1-i (C) n+1-i(D) 不能確定2.為查找某一特定單詞在文本中出現(xiàn)的位置，可應(yīng)用的串運算是( ) A.插入 B.刪除 C.串聯(lián)接 D.子串定位3設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（ ）次。(A) 25 (B) 10 (C) 7 (D) 1 4.對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為( ) A.順序表 B.用頭指針表示的單循環(huán)鏈表 C.用尾指針表示的單循環(huán)鏈表 D.單鏈表5設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有（ ）條邊。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-16設(shè)

27、某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（ ）。(A) 9(B) 10(C) 11(D) 127 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 ( ) A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) D. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 8 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點V0出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是( )A0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 29 若進棧序列為a,b,c,d,e,則棧的不可能的輸出序列是 ( ) A. edcba B. dceab C. decba D. abcde 10把一棵樹轉(zhuǎn)換為二叉樹后，這

28、棵二叉樹的形態(tài)是( )。A.唯一的 B.有多種C.有多種，但根結(jié)點都沒有左孩子 D.有多種，但根結(jié)點都沒有右孩子11.為查找某一特定單詞在文本中出現(xiàn)的位置，可應(yīng)用的串運算是( ) A.插入 B.刪除 C.串聯(lián)接 D.子串定位12.ALV樹是一種平衡的二叉樹，樹中任一結(jié)點的( ) A.左、右子樹的高度均相同 B.左、右子樹高度差的絕對值不超過1 C.左子樹的高度均大于右子樹的高度 D.左子樹的高度均小于右子樹的高度 13.對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為( ) A.順序表 B.用頭指針表示的單循環(huán)鏈表 C.用尾指針表示的單循環(huán)鏈表 D.單鏈表14. 二叉樹是非線性數(shù)

29、據(jù)結(jié)構(gòu)，所以( )。.它不能用順序存儲結(jié)構(gòu)存儲; B.它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲; C.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲; D.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用15. 用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用( )來實現(xiàn)算法的。A棧 B. 隊列 C. 樹 D. 圖16數(shù)據(jù)的最小單位是（ ）。(A) 數(shù)據(jù)項(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量17設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（ ）。(A) 9(B) 10(C) 11(D) 1218函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（ ）。(A) “STRUCTURE”(B) “DAT

30、A”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”19設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有（ ）條邊。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-120 深度為k的完全二叉樹中最少有（ ）個結(jié)點。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-121設(shè)連通圖G中的邊集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（ ）。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb22下面關(guān)于線性表的敘述

31、錯誤的是（ ）。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C) 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)23設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（ ）個空指針域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m24設(shè)順序循環(huán)隊列Q0：M-1的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（ ）。(A) R-F(B) F-R(C) (R-F+M)M(D)

32、 (F-R+M)M25設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA二、填空題11for(i=1，t=1，s=0；i=n；i+) t=t*i；s=s+t；的時間復(fù)雜度為 。2下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1; ;rj=temp;exchange=1;if (exchange=0) return；3下面程序段

33、的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct recordint key; int others;int bisearch(struct record r , int k) int low=0,mid,high=n-1; while(low=high) ; if(rmid.key=k) return(mid+1); else if( ) high=mid-1;else low=mid+1; return(0);3根據(jù)二叉樹的定義可知二叉樹共有 種不同的形態(tài)。4快速排序的最壞時間復(fù)雜度為 ，平均時間復(fù)雜度為 。5設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為N1，

34、則該二叉樹中度數(shù)為2的結(jié)點數(shù)為 ；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有 個空指針域。6設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e= 。7.設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點的編號是_，編號為8的左孩子結(jié)點的編號是_。8.設(shè)一個連通圖G中有n個頂點e條邊，則其最小生成樹上有_條邊。9設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為 。10設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為 。三、判斷題1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（