數(shù)據(jù)結構綜合練習題

1、列Q若6個兀素出列的順序為E2、E4、E&E6、E5和E1,則棧S的容量至少應該是(A)6(B)4(C)3(D)27.將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為(C)。(A)100(B)40(C)55(D)808.設結點A有3個兄弟結點且結點B為結點A的雙親結點，則結點B的度數(shù)數(shù)為(A)3(B)4(C)5(D)19.根據(jù)一叉樹的定義可知一叉樹共有(B)種不向的形態(tài)。(A)4(B)5(C)6(D)7一、選擇題1.組成數(shù)據(jù)的基本單位是(6.設棧S和隊列Q的初始狀態(tài)為空，元素B)。(B)p=p->next(D)p->next=pE1、E2、E3、的空間復雜度最大

2、。(C)堆排序(D)希爾排序10.設有以下四種排序方法，則(B(A)冒泡排序(B)快速排序11、以下說法正確的是(A)數(shù)據(jù)結構(一)(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)兀素(D)數(shù)據(jù)變量2.設數(shù)據(jù)結構A=(D,R),其中D=1,2,3,4,R=r,r=<1,2>,<2人是(C)。(A)線性結構(B)樹型結構(C)圖型結構(D)集合3.數(shù)組的邏輯結構不同于卜列(D)的邏輯結構。(A)線性表(B)棧(C)隊列(D)樹4.二叉樹中第i(i>1)層上的結點數(shù)最多有(C)個。(A)2i(B)2i(C)2i-1(D)2i-1C)。,3>,<3,4>,<4,1

3、>,則數(shù)據(jù)結構5.設指針變量p指向單鏈表結點(A)p->next=p->next->next(C)p=p->next->nextA,則刪除結點A的后繼結點B需要的操作為(A)。E4、E5和E6依次通過棧S,一個元素出棧后即進入隊C)。A.連通圖的生成樹，是該連通圖的一個極小連通子圖。B.無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一定是不對稱的。C.任何一個有向圖，其全部頂點可以排成一個拓撲序列。D.有回路的圖不能進行拓撲排序。12、以下說法錯誤的是(D)A.一般在哈夫曼樹中，權值越大的葉子離根結點越近B.哈夫曼樹中沒有度數(shù)為1的分支結點C.若初始森林中共有n

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

5、有向圖中每個頂點的度等于該頂點的(C)。A.入度B.出度C.入度與出度之和D.入度與出度之差18、具有n個頂點的有向無環(huán)圖最多可包含(D)條有向邊。A.n-1B.nC.n(n-1)/2D.n(n-1)19、用鄰接表作為有向圖G的存儲結構。設有n個頂點、e條弧，則拓撲排序的時間復雜度為(B)A.O(n)B.O(n+e)C.O(e)D.O(n*e)20、一個有序順表有255個對象，采用順序搜索法查表，搜索長度為(A)。A128B、127C、126D、25521、在有向圖中，所有頂點的入度之和是所有頂點出度之和的(B)倍。A.0.5B.1C.2D.422、以下說法錯誤的是(B)A.用相鄰矩陣法存儲一

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

7、向圖中，所有頂點的度數(shù)之和是所有邊數(shù)的(C)倍。A.0.5B.1C.2D.426、設有6個結點的無向圖，該圖至少應有(B)條邊能確保是一個連通圖。A.5B.6C.7D.827、以下說法正確的是(D)A.連通分量是無向圖中的極小連通子圖。B.強連通分量是有向圖中的極大強連通子圖。C.在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b>。D.對有向圖G,如果從任意頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖。二、填空題1 .設順序循環(huán)隊列Q0:m-1的隊頭指針和隊尾指針分別為F和R,其中隊頭指針F指向當前隊頭元素的前一個位置，隊尾指針

8、R指向當前隊尾元素所在的位置，則出隊列的語句為F=;。2 .設線性表中有n個數(shù)據(jù)元素，則在順序存儲結構上實現(xiàn)順序查找的平均時間復雜度為，在鏈式存儲結構上實現(xiàn)順序查找的平均時間復雜度為。3 .設一棵二叉樹中有n個結點，則當用二叉鏈表作為其存儲結構時，該二叉鏈表中共有個指針域，個空指針域。4 .設指針變量p指向單鏈表中結點A,指針變量s指向被插入的結點B,則在結點A的后面插入結點B的操作序列為。5 .設無向圖G中有n個頂點和e條邊，則其對應的鄰接表中有個表頭結點和個表結點。6 .設無向圖G中有n個頂點e條邊，所有頂點的度數(shù)之和為m則e和m有關系。7 .設一棵二叉樹的前序遍歷序列和中序遍歷序列均為A

9、BC則該二叉樹的后序遍歷序列為。8 .設一棵完全二叉樹中有21個結點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結點的編號是，編號為8的左孩子結點的編號是。9 .下列程序段的功能實現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。intindex(chars,chart)i=j=0;while(i<strlen(s)&&j<strlen(t)if(si=tj)i=i+l;j=j+l;elsei=;j=;if(j=strlen(t)return(i-strlen(t);elsereturn(-1);10 .設一個連通圖G中有n個頂點e條

10、邊，則其最小生成樹上有條邊。三、應用題1.設完全二叉樹的順序存儲結構中存儲數(shù)據(jù)ABCDE要求給出該二叉樹的鏈式存儲結構并給出該二叉樹的前序、2.3.4.中序和后序遍歷序列。設給定一個權值集合W=(3,5,7,9,11),要求根據(jù)給定的權值集合構造一棵哈夫曼樹并計算哈夫曼樹的帶權路徑長度WPL設一組初始記錄關鍵字序列為(19,21,16,5,18,23),要求給出以19為基準的一趟快速排序結果以及第2趟直接選擇排序后的結果。設一組初始記錄關鍵字集合為(25,10,8,27,32,68),散列表的長度為7,散列5.函數(shù)H(k)=kmod7,要求用線性探測法作為解決沖突的方法設計哈希表。設無向圖G(

11、所右圖所示)，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列給相應的生成樹二、填空題1.2.3.4.5.6.7.8.9.10.(F+1)%mO(n),O(n)2n,n+1s->next=p->next;s->next=sn,2em=2eCBA4,16i-j+1,0n-11.2.3.、應用題鏈式存儲結構略，前序哈夫曼樹略，WPL=78(18,5,16,19,21,23)4.,01線性探測：2.3.4.5.ABDEC中序DBEAC后序DEBCA16,19,18,23)1025322768數(shù)據(jù)結構(二)、選擇題下面關于線性表的敘述錯誤的是(A)(B)(C)(D)線性表采用順序存儲必須占

12、用一片連續(xù)的存儲空間線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)設哈夫曼樹中的葉子結點總數(shù)為m若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有(A)2m-1(B)2m(C)2m+1(D)4m設順序循環(huán)隊列Q0:M-1的頭指針和尾指針分別為F和R,頭指針針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為(A)R-F(B)F-R設某棵二叉樹的中序遍歷序列為(A)BADC(B)BCDA設某完全無向圖中有n個頂點,(A)n(n-1)/2(B)n(n-1)(C)(R-F+M)%MABCD前序遍歷序列為(C)CDAB

13、則該完全無向圖中有(C)n2(D)(F-R+M)()個空指針域。F總是指向隊頭元素的前一位置，尾指)°%MCABD則后序遍歷該二叉樹得到序列為(D)CBDA)條邊。(D)n2-16 .設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為()。(A)9(B)10(C)11(D)127 .設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有()個表頭結點。(A)n-1(B)n(C)n+1(D)2n-18 .設一組初始記錄關鍵字序列(5,2,6,3,8),以第一個記錄關鍵字5為基準進行一趟快速排序的結果為()。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2

14、,3,6,5,8二、填空題1 .為了能有效地應用HASH查找技術，必須解決的兩個問題是和2 .下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。typedefstructints100;inttop;sqstack;voidpush(sqstack&stack,intx)if(stack.top=m-1)printf("overflow");else;3 .中序遍歷二叉排序樹所得到的序列是序列(填有序或無序)。4 .快速排序的最壞時間復雜度為,平均時間復雜度為。5 .設某棵二叉樹中度數(shù)為0的結點數(shù)為N0,度數(shù)為1的結點數(shù)為N,則該二叉樹中度數(shù)為2的結點數(shù)

15、為;若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有個空指針域。6 .設某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=。7 .設一組初始記錄關鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為Vi-3-2-4一.一.vo-1-38.設某無向圖G的鄰接表為2,則從頂點Vi開始的深度優(yōu)先遍歷序列為;廣度V3-1-54。、2v4-1-53優(yōu)先遍歷序列為。三、應用題1 .設一組初始記錄關鍵字序列為(45,80,47,40,20,78),則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結果。2 .設指針變量p指向雙向鏈表中結點A,指針變

16、量q指向被插入結點B,要求給出在結點A的后面插入結點B的操作序列(設雙向鏈表中結點的兩個指針域分別為llink和rlink)。3 .設一組有序的記錄關鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求計算出查找關鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4 .設一棵樹T中邊的集合為(A,B),(A,C),(A,D),(B,E),(C,F),(C,G),要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。5 .設有無向圖G(如右圖所示)，要求給出用普里姆算法構造最小生成樹所走過的邊的集合。6 .設有一組初始記錄關鍵

17、字為(45,80,48,40,22,78),要求構造一棵二叉排序樹并給出構造過程。7、給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結構。8、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法，試舉例說明。9、給出下圖鄰接矩陣和鄰接表兩種存儲結構；寫出圖的拓撲序列。(二)參考答案一、選擇題1 .D2,B3.C4.A5.A6.C7.B8.C二、填空題2 .構造一個好的HAS闊數(shù)，確定解決沖突的方法3 .stack.top+,stack.sstack.top=x4 .有序2、4. O(n),O(nlog2n)5. N0-1,2N0+Ni6. d/27. (31,38,54,56,75,80,55,

18、63)8. (1,3,4,2),(1,3,2,4)三、應用題1. (20,40,45,47,80,78),(40,45,47,80,20,78)2. q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 樹的鏈式存儲結構略，二叉樹略5. E=(1,3),(1,2),(3,5),(5,6),(6,4)6. 略8、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法，試舉例說明?！窘獯稹?2)簡單選擇排序275275*512061)i=1

19、061275*512275)i=2061275*512275)i:=3061275*275512)快速排序512275275*)275*275512)(4)堆排序275275*061170)已經(jīng)是最大堆，交換275與170170275*061275)對前3個調(diào)整275*170061275)前3個最大堆，交換275*與061061170275*275)對前2個調(diào)整170061275*275)前2個最大堆，交換170與061061170275*275)數(shù)據(jù)結構(三)一、選擇題1 .設某無向圖有n個頂點，則該無向圖的鄰接表中有()個表頭結點。(A)2n(B)n(C)n/2(D)n(n-1)2 .設無

20、向圖G中有n個頂點，則該無向圖的最小生成樹上有()條邊。(A)n(B)n-13.設一組初始記錄關鍵字序列為排序結果是()。(C)2n(D)2n-1(A) 40,42,60,55,80,85(C)424055608085(B) 424555608580(D)424060855580(60,80,55,40,42,85),則以第一個關鍵字45為基準而得到的一趟快速4 .()二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷5 .設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為()。(A)2i+16.程

21、序段s=i=0;(A)O(n)(B)2idoi=i+1；s=s+i(B) O(nlog2n)(C)i/2;while(i<=n)(C) O(n2)(D)2i-1;的時間復雜度為(D) O(n3/2)7.設帶有頭結點的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是()。(A)head=0(B)head->next=0(C)head->next=head(D)head!=08 .設某棵二叉樹的高度為10,則該二叉樹上葉子結點最多有()。(A)20(B)256(C)512(D)10249 .設一組初始記錄關鍵字序列為(13,18,24,35,47,50,62,83,90,字90

22、需要比較的關鍵字個數(shù)為()。115,134),則利用二分法查找關鍵(A)1(B)2(C)3(D)410.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為()。(A) top=top+1;(C)top->next=top;(B) top=top-1;(D)top=top->next;二、判斷題1、數(shù)據(jù)的最小單位是數(shù)據(jù)項。,.(V)2、多重表文件中主索引為非稠密索引，次索引為稠密索引。，,.(V)3、通常數(shù)據(jù)結構在計算機中有四種不同的表示方法分為順序存儲結構、鏈式存儲結構、索引存儲、文件存儲。，,，.,.(X)4、算法具有輸入、輸出、可行性、穩(wěn)定性、有窮性五個特性。.(

23、X)5、數(shù)據(jù)的基本單位是數(shù)據(jù)項。,.(X)6、算法的復雜度分為時間復雜度和效率復雜度。,.(X)7、性質(zhì)相同的數(shù)據(jù)元素的集合成為數(shù)據(jù)對象。.(V)8、所有結點按1對1的鄰接關系構成的整體就是集合結構。,.(X)9、散列文件不能順序存取、只能按關鍵字隨機存取。，,，.(V)10、數(shù)據(jù)的基本單位是數(shù)據(jù)元素。,.(V)11 .不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。(，)12 .當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。(，)13 .由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（x）14 .線性表中的所有元素都有一個前驅元素和后繼元素。（X）15 .帶權

24、無向圖的最小生成樹是唯一的。（X）16 .具有12個結點的完全二叉樹有5個度為2的結點。（）17 .關鍵路徑是事件結點網(wǎng)絡中的從源點到匯點的最短路徑。（）18 .由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（）19 .堆排序是不穩(wěn)定的排序方法。（V）20 .查找表是由同一類型的數(shù)據(jù)元素（或記錄）構成的集合（，）三、填空題1 .設指針變量p指向雙向鏈表中的結點A,指針變量s指向被插入的結點X,則在結點A的后面插入結點X的操作序列為=p;s->right=p->right;=s;p->right->left=s;（設結點中的兩個指針域分別為left和right）。2 .設

25、完全有向圖中有n個頂點，則該完全有向圖中共有條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有條無向邊。3 .設關鍵字序列為（Kl,%,K）,則用篩選法建初始堆必須從第個元素開始進行篩選。4 .解決散列表沖突的兩種方法是和。5 .設一棵三叉樹中有50個度數(shù)為0的結點，21個度數(shù)為2的結點，則該二叉樹中度數(shù)為3的結點數(shù)有個。6 .高度為h的完全二叉樹中最少有個結點，最多有個結點。7 .設有一組初始關鍵字序列為（24,35,12,27,18,26）,則第3趟直接插入排序結束后的結果的是8 .設有一組初始關鍵字序列為（24,35,12,27,18,26）,則第3趟簡單選擇排序結束后的結果的是9

26、 .設一棵二叉樹的前序序列為ABC則有種不同的二叉樹可以得到這種序列。10 .下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。structrecordintkey;datatypeothers;voidquickpass(structrecordr,ints,intt,int&i)intj=t;structrecordx=rs;i=s;while(i<j)while(i<j&&rj.key>x.key)j=j-1;if(i<j)ri=rj;i=i+1;while()i=i+1;if(i<j)rj=ri;j=j-1;；數(shù)據(jù)結構

27、（三）一、選擇題1.B2.B3.C4B5B6.A7.C8.C9B10.D三、填空題1. s->left=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. i<j&&ri.key<x.key,ri=x數(shù)據(jù)結構(四)一、選擇題1 .設輸入序列是1、2、3、，、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第i個輸出元素是(c)。(A)n-i(B)n-1-i(C)n+1-

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

29、D)127 .在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分為()A.動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構C.內(nèi)部結構和外部結構D.線性結構和非線性結構8 .已知圖的鄰接表如下所示，根據(jù)算法，則從頂點Vo出發(fā)按廣度優(yōu)先遍歷的結點序列是()A.0321B.0123C.0132D.03129 .若進棧序列為a,b,c,d,e,則棧的不可能的輸出序列是()A.edcbaB.dceabC.decbaD.abcde10 .把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是()。A.唯一的B.有多種C.有多種，但根結點都沒有左孩子D.有多種，但根結點都沒有右孩子11 .為查找某一特定單詞在文本中出現(xiàn)的位置，可應用的

30、串運算是()A.插入B.刪除C.串聯(lián)接D.子串定位12 .ALV樹是一種平衡的二叉樹，樹中任一結點的()A.左、右子樹的高度均相同B.左、右子樹高度差的絕對值不超過1C.左子樹的高度均大于右子樹的高度D.左子樹的高度均小于右子樹的高度13 .對于只在表的首、尾兩端進行插入操作白線性表，宜采用的存儲結構為()A.順序表B.用頭指針表示的單循環(huán)鏈表C.用尾指針表示的單循環(huán)鏈表D.單鏈表14 .二叉樹是非線性數(shù)據(jù)結構，所以()。A.它不能用順序存儲結構存儲；B.它不能用鏈式存儲結構存儲；C.順序存儲結構和鏈式存儲結構都能存儲；D.順序存儲結構和鏈式存儲結構都不能使用15 .用鄰接表表示圖進行廣度優(yōu)先

31、遍歷時，通常是采用()來實現(xiàn)算法的。A.棧B.隊列C.樹D.圖16 .數(shù)據(jù)的最小單位是()。(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量17 .設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為()。(A)9(B)10(C)11(D)1218 .函數(shù)substr("DATASTRUCTURE5,9)的返回值為()。(A)“STRUCTURE(B)“DATA(C)“astructUr(D)“datastructURe19 .設某完全無向圖中有n個頂點，則該完全無向圖中有()條邊。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-120 .深度為k的完全二叉樹中

32、最少有()個結點。(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-121 .設連通圖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 .下面關于線性表的敘述錯誤的是()。(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B)線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C)線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)23 .設哈夫曼樹中的葉子結點總數(shù)為m

33、,若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有()個空指針域。(A)2m-1(B)2m(C)2m+1(D)4m24 .設順序循環(huán)隊列Q0:M-1的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為()。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M25 .設某棵二叉樹的中序遍歷序列為ABCD前序遍歷序列為CABD則后序遍歷該二叉樹得到序列為()。(A)BADC(B)BCDA(C)CDAB(D)CBDA二、填空題1 .1.for(i=1,t=1,s=0;i<=n;i+)t=t*i;s=s

34、+t;的時間復雜度為2 .下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。voidbubble(intrn)for(i=1;i<=n-1;i+)for(exchange=0,j=0;j<j+)if(rj>rj+1)temp=rj+1;rj=temp;exchange=1;if(exchange=0)return;3 .下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。structrecordintkey;intothers;intbisearch(structrecordr,intk)intlow=0,mid,high=n-1;while(low

35、<=high)J.if(rmid.key=k)return(mid+1);elseif()high=mid-1;elselow=mid+1;)return(0);)3 .根據(jù)二叉樹的定義可知二叉樹共有種不同的形態(tài)。4 .快速排序的最壞時間復雜度為,平均時間復雜度為。5 .設某棵二叉樹中度數(shù)為0的結點數(shù)為NQ度數(shù)為1的結點數(shù)為N1,則該二叉樹中度數(shù)為2的結點數(shù)為;若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有個空指針域。6 .設某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=。7 .設一棵完全二叉樹中有21個結點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結點的編號是,編號為8的左孩子結點的編號是。8 .設一個連通圖G中有n個頂點e條邊，則其最小生成樹上有條邊。9 .設一組初始記錄關鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為。10 .設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)