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=<1,2>,<2,3>,<3,4>,<4,1>,則數(shù)據(jù)結(jié)構(gòu)A是(C)。(A)線性結(jié)構(gòu)(B)樹型結(jié)本勾(C)圖型結(jié)構(gòu)(D)集合3 .數(shù)組的邏輯結(jié)構(gòu)不同于下列(D)的邏輯結(jié)構(gòu)。(A)線性表(B)棧(C)隊列(D)樹4 .二叉樹中第i(i>1)層上的結(jié)點數(shù)最多有(C)個。(A)2i(B)2i(C)2i-1(D)2i-15 .設(shè)指針變量p指向單鏈表結(jié)點A,則刪除結(jié)點A的后繼

2、結(jié)點B需要的操作為(A)。(A)p->next=p->next->next(B)p=p->next(D)p->next=p(C)p=p->next->next6 .設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S,一個元素出棧后即進(jìn)入隊列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的雙

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

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

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

6、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、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的(B)倍。A.3B.2

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

8、元素的前一個位置，隊尾指針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è)無向圖G中有n個頂點e條邊，所有頂點的度數(shù)之和為m,則e和m有關(guān)系。7 .設(shè)一棵二叉樹的前序

9、遍歷序列和中序遍歷序列均為ABC,則該二叉樹的后序遍歷序列為。8 .設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點的編號是，編號為8的左孩子結(jié)點的編號是。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

10、 .設(shè)一個連通圖G中有n個頂點e條邊，則其最小生成樹上有條邊。三、應(yīng)用題1 .設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE,要求給出該二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。2 .設(shè)給定一個權(quán)值集合W=(3,5,7,9,11),要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度WPL。為基準(zhǔn)3 .設(shè)一組初始記錄關(guān)鍵字序列為(19,21,16,5,18,23),要求給出以19的一趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。4 .設(shè)一組初始記錄關(guān)鍵字集合為(25,10,8,27,32,68),散列表的長度為列函數(shù)H(k)=kmod7,要求用線性探測法作為解

11、決沖突的方法設(shè)計哈希表。5 .設(shè)無向圖G(所右圖所示)，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列給相應(yīng)的生成樹(一)參考答案二、填空題1. (F+1)%m2. O(n),O(n)3. 2n,n+14. s->next=p->next;s->next=s5. n,2e6. m=2e7. CBA8. 4,169. i-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.線性探測:01234567上8上10253227

12、68數(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)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-

13、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è)某棵二叉樹中有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,

14、3,8),以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jì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進(jìn)棧，要求在下劃線處填上正確的語句。typedefstructints100;inttop;sqstack;voidpush(sqstack&stack,intx)if(stack.top=m-1)printf("overflow");else;3 .中序遍歷二叉排序樹所得到的序列是序列(填有序或無序)。

15、4 .快速排序的最壞時間復(fù)雜度為,平均時間復(fù)雜度為。5 .設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N。，度數(shù)為1的結(jié)點數(shù)為則該二叉樹中度數(shù)為2的結(jié)點數(shù)為;若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有個空指針域。6 .設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=。7 .設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為v1-3-2-4V2-1-38.設(shè)某無向圖G的鄰接表為2,則從頂點Vi開始的深度優(yōu)先遍歷序列為;廣v3-1-4-2v4-1-3度優(yōu)先遍歷序列為。三、應(yīng)用題1.設(shè)一組初始記錄關(guān)鍵字序列為(45,80,47

16、,40,20,78),則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2 .設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量q指向被插入結(jié)點B,要求給出在結(jié)點A的后面插入結(jié)點1B的操作序列(設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink)。3 .設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4 .設(shè)一棵樹T中邊的集合為(A,B),(A,C),(A,D),(B,E),(C,F),(C,G),要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化

17、成對應(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、給出下圖鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)；寫出圖的拓?fù)湫蛄小?二)參考答案一、選擇題1. D2,B3.C4.A5.A6.C7.B8.C二、填空題2. 構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法3. stack.top+,stack.sstack.top=x4. 有

18、序5. O(n2),O(nlog2n)6. No-1,2N0+N17. d/28. (31,38,54,56,75,80,55,63)9. (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;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.

19、略8、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法，試舉例說明。【解答】(2)簡單選擇排序275275*512061i=1061275*512275i=2061275*061275*512275i=3275512(3)快速排序%275275*275275*512(4)堆排序275275*170275*275*170061170170061061170061170已經(jīng)是最大堆，交換275與170061275對前3個調(diào)整061275前3個最大堆，交換275*與061275*275對前2個調(diào)整275*275前2個最大堆，交換170與061275*275數(shù)據(jù)結(jié)構(gòu)(三)一、選擇題1.設(shè)某無向圖有n個

20、頂點，則該無向圖的鄰接表中有()個表頭結(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)鍵字序列為(60,80,55,40,42,85),則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是()。(A)40,42,60,55,80,85(C)42,40,55,60,80,85(B)42,45,55,60,85,80(D)42,40,60,85,55,804.()二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷(B)中序遍歷5.設(shè)按照從上到下、從左到右的順序

21、從號為()。(C)后序遍歷(D)層次遍歷1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編(A)2i+1(B)2i6.程序段s=i=0;doi=i+1;s=s+i;(A)O(n)(B)O(nlog2n)(C)i/2(D)2i-1while(i<=n);的時間復(fù)雜度為()。(C)O(n2)(D)O(n3/2)7.設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是()。(A)head=0(C)head->next=head(B)head->next=0(D)head!=08.設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點最多有()。(A)20(B)256

22、(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)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為()。(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ù)結(jié)構(gòu)在計算機中有四種不同的表示方法分為順序存儲結(jié)構(gòu)、鏈?zhǔn)酱?/p>

23、儲結(jié)構(gòu)、索引存儲、文件存儲。.(X)4、算法具有輸入、輸出、可行性、穩(wěn)定性、有窮性五個特性。.(X)5、數(shù)據(jù)的基本單位是數(shù)據(jù)項。.(X)6、算法的復(fù)雜度分為時間復(fù)雜度和效率復(fù)雜度。.(X)7、性質(zhì)相同的數(shù)據(jù)元素的集合成為數(shù)據(jù)對象。.(V)8、所有結(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是集合結(jié)構(gòu)。.(X)9、散列文件不能順序存取、只能按關(guān)鍵字隨機存取。.(V)10、數(shù)據(jù)的基本單位是數(shù)據(jù)元素。.(V)11 .不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。(，)12 .當(dāng)向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。(，)13 .由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為

24、空。(X)14 .線性表中的所有元素都有一個前驅(qū)元素和后繼元素。(X)15 .帶權(quán)無向圖的最小生成樹是唯一的。(X)16 .具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。()17 .關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中的從源點到匯點的最短路徑。()18 .由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。()19 .堆排序是不穩(wěn)定的排序方法。(V)20 .查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合(，)三、填空題1 .設(shè)指針變量p指向雙向鏈表中的結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X的操作序列為=p;s->right=p->right;=s;p->right-

25、>left=s;(設(shè)結(jié)點中的兩個指針域分別為left和right)。2 .設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有條無向邊。3 .設(shè)關(guān)鍵字序列為(K,8,Kn),則用篩選法建初始堆必須從第個元素開始進(jìn)行篩選。4 .解決散列表沖突的兩種方法是和。5 .設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有個。6 .高度為h的完全二叉樹中最少有個結(jié)點，最多有個結(jié)點。7 .設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟直接插入排序結(jié)束后的結(jié)果的是8 .設(shè)有一組初始關(guān)鍵字序

26、列為(24,35,12,27,18,26),則第3趟簡單選擇排序結(jié)束后的結(jié)果的是9 .設(shè)一棵二叉樹的前序序列為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+

27、1;while()i=i+1;if(i<j)rj=ri;j=j-1;；數(shù)據(jù)結(jié)構(gòu)(三)、選擇題1.B2.B3.C4.B5.B6.A7.C8.C9.B10.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ù)結(jié)構(gòu)(四)一、選擇題1 .設(shè)輸入序列是1、2、3、n,經(jīng)過棧的作用后輸出序列的第一個元素是n

28、,則輸出序列中第i個輸出元素是(c)。(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)14 .對于只在表的首、尾兩端進(jìn)行插入操作白線性表，宜采用的存儲結(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è)某棵二叉

29、樹中有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ù)算法，則從頂點Vo出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是()A.0321B.0123C.0132D.03129 .若進(jìn)棧序列為a,b,c,d,e,則棧的不可能的輸出序列是()A.edcbaB.dceabC.decbaD.abcde10 .把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是()。A.唯一的B.有多種C.有多種，但根結(jié)點都沒有左孩子D.有

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

31、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用15 .用鄰接表表示圖進(jìn)行廣度優(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)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”19 .設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有()

32、條邊。(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)于線性表的敘述錯誤的是()。(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒?/p>

33、刪除操作的實現(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)(F-R+M)%M25 .設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為()。(A)BADC(B)BCDA(C)CDAB(

34、D)CBDA二、填空題1.1. for(i=1,t=1,s=0;i<=n;i+)t=t*i;s=s+t;的時間復(fù)雜度為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;intbisear

35、ch(structrecordr,intk)intlow=0,mid,high=n-1;while(low<=high);if(rmid.key=k)return(mid+1);elseif()high=mid-1;elselow=mid+1;return(0);3 .根據(jù)二叉樹的定義可知二叉樹共有種不同的形態(tài)。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è)一棵完全二叉樹中有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)先遍歷可以訪問到圖中的所有頂點。(x)2 .