數(shù)據(jù)結(jié)構(gòu)試題-附答案

1、一、選擇題1、在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為()A)內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B)靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu))緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。2、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須A.以鏈接方式存儲(chǔ)，且數(shù)據(jù)元素有序B.以鏈接方式存儲(chǔ)D.以順序方式存儲(chǔ)3、 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，在第i個(gè)位置上插入一個(gè)新元素的時(shí)間復(fù)雜度為()2B) O(1)C) O(n )4、順序循環(huán)隊(duì)列中(數(shù)組的大小為 刪除1個(gè)元素，再插入A ) 5 和 1 B) 2 和5 在下列排序方法中，A.直接插入排序C.快速排序6、設(shè)有數(shù)組Ai , j,A) 0(n)3D) O(n )6)，隊(duì)頭指示front和隊(duì)尾指示rear的

2、值分別為3和0,當(dāng)從隊(duì)列中front和rear的值分別為()2個(gè)元素后，C) 1 和 5D) 4 和 2)的比較次數(shù)與記錄的初始排列狀態(tài)無(wú)關(guān)。B.起泡排序D.簡(jiǎn)單選擇排序數(shù)組的每個(gè)元素長(zhǎng)度為首地址BA開始順序存放，當(dāng)以列為主序存放時(shí)，DA) BA+41 B ) BA+180 C ) BA+2227、下面哪個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)( A)順序表B)鏈表C)散列表&在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為(|2k-1D)og2 k +11 001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)為( C) 2543字節(jié)，i的值為1到8，j的值為1到10,數(shù)組從內(nèi)存 元素 A5,8的存儲(chǔ)首地址為()BA+225)、k-1、

3、kA) 2B) 2C9、一棵完全二叉樹上有A) 250 B) 500 C) 254 D) 50110、利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是(A)指向最左孩子B )指向最右孩子 C若鄰接表中有奇數(shù)個(gè)邊結(jié)點(diǎn)，則一定(A )圖中有奇數(shù)個(gè)頂點(diǎn)B)圖中有偶數(shù)個(gè)頂點(diǎn)12、 無(wú)向圖 G= (V , E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d),對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是()A) abecdf B) acfebdC) aebcfd D) aedfcb13、 在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的(

4、 )A )最小生成樹中 B)深度優(yōu)先生成樹中C)廣度優(yōu)先生成樹中D)深度優(yōu)先生成森林中14、已知含10個(gè)結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平 均查找長(zhǎng)度等于(A)15、A)C)二、應(yīng)用題1、已知一棵度為該樹中有多少個(gè)葉子結(jié)點(diǎn)？要求寫出分析過程。2、 已知一棵二叉樹的中序遍歷的結(jié)果為ABCEFGHD，后序遍歷的結(jié)果為 ABFHGEDC，試畫出此二叉11、D)C)非空?qǐng)D為無(wú)向圖B) 2.9)C) 3.4 D) 5.51.0下面的序列中初始序列構(gòu)成最小堆(小根堆)的是(10、 60、 20、20、 60、 50、50、 30、 26、 35、 4040、30、1

5、0、8、72m的樹中有m個(gè)度為)B) 70、40、36、30、20、16、28、101的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn),nm個(gè)度為m的結(jié)點(diǎn)，問樹。3、 設(shè)用于通信的電文由 8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為：7, 19, 2, 6, 32 , 3, 21 ,10。試為這八個(gè)字母設(shè)計(jì)哈夫曼編碼，并求出總碼長(zhǎng)。4、對(duì)于下圖，從頂點(diǎn) V0出發(fā)，按照普里姆算法求出它的最小生成樹，畫出求解過程。5、 設(shè)散列表長(zhǎng)度為11,散列函數(shù)H(x) = x%11，給定的關(guān)鍵字序列為 1 , 13, 12, 34, 38, 33, 27, 22。 試畫出分別用拉鏈法和線性探測(cè)法解決沖突時(shí)所構(gòu)造的散列表，并求出在等概

6、率的情況下，這兩種方法 查找成功時(shí)的平均查找長(zhǎng)度。6、 對(duì)下面關(guān)鍵字序列，寫出采用希爾排序算法進(jìn)行排序的每一趟的結(jié)果。其中增量序列的取值為5, 3, 1。(125, 11, 22, 34, 15, 44, 76, 66, 100, 8, 14, 20, 2, 5, 1)三、編程題注意：先進(jìn)行類型定義，再寫算法。1、 已知一個(gè)順序表中的各結(jié)點(diǎn)值是從小到大有序的，設(shè)計(jì)一個(gè)算法，插入一個(gè)值為x的結(jié)點(diǎn)，使順序表中的結(jié)點(diǎn)仍然是從小到大有序(不考慮空間不夠用的情況)。2、 設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表中的各個(gè)結(jié)點(diǎn)值是否遞增有序(帶頭結(jié)點(diǎn)的單鏈表)。3、 編寫一個(gè)函數(shù)，求一棵給定二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)(提示

7、：采用任何一種遍歷方法都可以)。一、 選擇CCADB BDCDC DDABD1、設(shè)葉子個(gè)數(shù)為x總度數(shù)=n 1+2* n2+3* n3+m* nm 結(jié)點(diǎn)總數(shù)=ni+n2+n m+x而結(jié)點(diǎn)總數(shù)=總度數(shù)+12、2817113、哈夫曼樹的構(gòu)造過程如下:6011密 封 線 內(nèi) 不 要 答 題假設(shè)八個(gè)字母分別為B、C、D、E、F、G、H，則這八個(gè)字母對(duì)應(yīng)得編碼為:A 1010 B 00C 10000D1001E11F10001G 01 H 1011WPL=(19+21+32)*2+(6+7+10)*4+(2+3)*5=2616、15、采用線性探測(cè)解決沖突構(gòu)造哈希表過程如下:第一趟：141125 14420

8、22348125766610015第二趟：51 2 8 111514223420100446612576第三趟：125 8111415202234446676100125密 封 線 內(nèi) 不 要 答 題H( 1)=1 H( 13)H(34) =1 H1( 34)H (28) =5H( 33)=0 H1( 33)H(27)=5H1(27)=6H(22)=0H7(22)=7哈希表結(jié)構(gòu)如下：=2 H (12) =1=2 H2 (34) =3=1 H4 (33) =427 平均查找長(zhǎng)度 ASL= (1+1+3+4+1+1+2+8 ) /8=2.625 采用拉鏈法構(gòu)造的哈希表如下：331131234387

9、228910平均查找長(zhǎng)度ASL=13/81、typedef structelemtype *elem;int len gth;SqList;void in sert(SqList &L, elemtype x) p=L.elem+L .len gth;while(xn ext;while(p- next!=NULL) if(p-datap-n ext-data) break; else p=p-n ext;if(p-n ext=NULL) return 1;else return 0;3、typedef struct BitNodeelemtype data;struct BitNode *Lchild,Rchild; BitNode,*BiTree;int leafco un t(BiTree bt)int num=0;Queue Q;BiTree p;if(bt) p=bt;密 封 線 內(nèi) 不 要 答 題en Queue(Q,