數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)題

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

2、。(C)堆排序(D)希爾排序10.設(shè)有以下四種排序方法，則(B(A)冒泡排序(B)快速排序11、以下說(shuō)法正確的是(A)數(shù)據(jù)結(jié)構(gòu)(一)(A)數(shù)據(jù)項(xiàng)(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人是(C)。(A)線性結(jié)構(gòu)(B)樹(shù)型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集合3.數(shù)組的邏輯結(jié)構(gòu)不同于卜列(D)的邏輯結(jié)構(gòu)。(A)線性表(B)棧(C)隊(duì)列(D)樹(shù)4.二叉樹(shù)中第i(i>1)層上的結(jié)點(diǎn)數(shù)最多有(C)個(gè)。(A)2i(B)2i(C)2i-1(D)2i-1C)。,3>,<3,4>,<4,1

3、>,則數(shù)據(jù)結(jié)構(gòu)5.設(shè)指針變量p指向單鏈表結(jié)點(diǎn)(A)p->next=p->next->next(C)p=p->next->nextA,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為(A)。E4、E5和E6依次通過(guò)棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)C)。A.連通圖的生成樹(shù)，是該連通圖的一個(gè)極小連通子圖。B.無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的。C.任何一個(gè)有向圖，其全部頂點(diǎn)可以排成一個(gè)拓?fù)湫蛄小.有回路的圖不能進(jìn)行拓?fù)渑判颉?2、以下說(shuō)法錯(cuò)誤的是(D)A.一般在哈夫曼樹(shù)中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近B.哈夫曼樹(shù)中沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)C.若初始森林中共有n

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

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

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

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

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

9、BC則該二叉樹(shù)的后序遍歷序列為。8 .設(shè)一棵完全二叉樹(shù)中有21個(gè)結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開(kāi)始順序編號(hào)，則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是，編號(hào)為8的左孩子結(jié)點(diǎn)的編號(hào)是。9 .下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語(yǔ)句。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 .設(shè)一個(gè)連通圖G中有n個(gè)頂點(diǎn)e條

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

11、所右圖所示)，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列給相應(yīng)的生成樹(shù)二、填空題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.、應(yīng)用題鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，前序哈夫曼樹(shù)略，WPL=78(18,5,16,19,21,23)4.,01線性探測(cè)：2.3.4.5.ABDEC中序DBEAC后序DEBCA16,19,18,23)1025322768數(shù)據(jù)結(jié)構(gòu)(二)、選擇題下面關(guān)于線性表的敘述錯(cuò)誤的是(A)(B)(C)(D)線性表采用順序存儲(chǔ)必須占

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

13、則該完全無(wú)向圖中有(C)n2(D)(F-R+M)()個(gè)空指針域。F總是指向隊(duì)頭元素的前一位置，尾指)°%MCABD則后序遍歷該二叉樹(shù)得到序列為(D)CBDA)條邊。(D)n2-16 .設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為()。(A)9(B)10(C)11(D)127 .設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有()個(gè)表頭結(jié)點(diǎn)。(A)n-1(B)n(C)n+1(D)2n-18 .設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個(gè)記錄關(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

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

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

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

17、字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。7、給出如圖所示的無(wú)向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。8、簡(jiǎn)單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法，試舉例說(shuō)明。9、給出下圖鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)；寫(xiě)出圖的拓?fù)湫蛄小?二)參考答案一、選擇題1 .D2,B3.C4.A5.A6.C7.B8.C二、填空題2 .構(gòu)造一個(gè)好的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)三、應(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. 樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹(shù)略5. E=(1,3),(1,2),(3,5),(5,6),(6,4)6. 略8、簡(jiǎn)單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法，試舉例說(shuō)明?！窘獯稹?2)簡(jiǎn)單選擇排序275275*512061)i=1

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

20、向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有()條邊。(A)n(B)n-13.設(shè)一組初始記錄關(guān)鍵字序列為排序結(jié)果是()。(C)2n(D)2n-1(A) 40,42,60,55,80,85(C)424055608085(B) 424555608580(D)424060855580(60,80,55,40,42,85),則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速4 .()二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷5 .設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為()。(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;的時(shí)間復(fù)雜度為(D) O(n3/2)7.設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是()。(A)head=0(B)head->next=0(C)head->next=head(D)head!=08 .設(shè)某棵二叉樹(shù)的高度為10,則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有()。(A)20(B)256(C)512(D)10249 .設(shè)一組初始記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90,字90

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

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

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

25、完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有條有向條；設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中共有條無(wú)向邊。3 .設(shè)關(guān)鍵字序列為（Kl,%,K）,則用篩選法建初始堆必須從第個(gè)元素開(kāi)始進(jìn)行篩選。4 .解決散列表沖突的兩種方法是和。5 .設(shè)一棵三叉樹(shù)中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹(shù)中度數(shù)為3的結(jié)點(diǎn)數(shù)有個(gè)。6 .高度為h的完全二叉樹(shù)中最少有個(gè)結(jié)點(diǎn)，最多有個(gè)結(jié)點(diǎn)。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ǎn)單選擇排序結(jié)束后的結(jié)果的是9

26、 .設(shè)一棵二叉樹(shù)的前序序列為ABC則有種不同的二叉樹(shù)可以得到這種序列。10 .下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。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ù)結(jié)構(gòu)

27、（三）一、選擇題1.B2.B3.C4B5B6.A7.C8.C9B10.D三、填空題1. s->left=p,p->right2. n(n-1),n(n-1)/23. n/24. 開(kāi)放定址法，鏈地址法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)過(guò)棧的作用后輸出序列的第一個(gè)元素是n,則輸出序列中第i個(gè)輸出元素是(c)。(A)n-i(B)n-1-i(C)n+1-

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

29、D)127 .在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()A.動(dòng)態(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ù)算法，則從頂點(diǎn)Vo出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是()A.0321B.0123C.0132D.03129 .若進(jìn)棧序列為a,b,c,d,e,則棧的不可能的輸出序列是()A.edcbaB.dceabC.decbaD.abcde10 .把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是()。A.唯一的B.有多種C.有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子D.有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子11 .為查找某一特定單詞在文本中出現(xiàn)的位置，可應(yīng)用的

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

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

32、最少有()個(gè)結(jié)點(diǎn)。(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),則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為()。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb22 .下面關(guān)于線性表的敘述錯(cuò)誤的是()。(A)線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間(B)線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C)線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D)線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)23 .設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m

33、,若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有()個(gè)空指針域。(A)2m-1(B)2m(C)2m+1(D)4m24 .設(shè)順序循環(huán)隊(duì)列Q0:M-1的頭指針和尾指針?lè)謩e為F和R,頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M25 .設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD前序遍歷序列為CABD則后序遍歷該二叉樹(shù)得到序列為()。(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;的時(shí)間復(fù)雜度為2 .下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。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 .下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。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ù)二叉樹(shù)的定義可知二叉樹(shù)共有種不同的形態(tài)。4 .快速排序的最壞時(shí)間復(fù)雜度為,平均時(shí)間復(fù)雜度為。5 .設(shè)某棵二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為NQ度數(shù)為1的結(jié)點(diǎn)數(shù)為N1,則該二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)數(shù)為;若采用二叉鏈表作為該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有個(gè)空指針域。6 .設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則e=。7 .設(shè)一棵完全二叉樹(shù)中有21個(gè)結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開(kāi)始順序編號(hào)，則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是,編號(hào)為8的左孩子結(jié)點(diǎn)的編號(hào)是。8 .設(shè)一個(gè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則其最小生成樹(shù)上有條邊。9 .設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為。10 .設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)