數(shù)據(jù)結(jié)構(gòu)試卷及答案

1、數(shù)據(jù)結(jié)構(gòu)期末考試一、單項選擇題（請將正確答案的字母填寫在每題對應(yīng)的括號內(nèi)，每小題1分，共20分）1、下面關(guān)于串的敘述中，哪一個是不正確的？（ ）A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?、設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（ ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D03、以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。A樹 B字符串 C隊列 D棧4、下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈

2、接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。5、假設(shè)以數(shù)組Am存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m6、在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點,正確的操作是（ ）。Ap->next=s; s->next=p->next; Bs->next=p->next; p->next=s;Cp->next=s; p->next=s->

3、next; Dp->next=s->next; p->next=s;7、設(shè)棧的輸入序列是1，2，3，4,則（ ）不可能是其出棧序列。A1，2，4，3 B2，1，3，4 C1，4，3，2 D4，3，1，2，8、廣義表（a,(b,c),d,e）的表頭和表尾分別為（ ）。 Aa和(b,c),d,e B（a）和(b,c),d,e Ca 和 (b,c)，d,e) D(a) 和(b,c)，d,e)二、判斷題，在正確的題后括號內(nèi)打“”，在錯誤的題后括號內(nèi)打“×”（每小題1分，共10分）9、棧和隊都是（ ）A順序存儲的線性結(jié)構(gòu) B鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)C限制存取點的線性結(jié)構(gòu) D限制存

4、取點的非線性結(jié)構(gòu)10、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)11、下列四個序列中，哪一個是堆（ ）。A75,65,30,15,25,45,20,10 B75,65,45,10,30,25,20,15C75,45,65,30,15,25,20,10 D75,45,65,10,25,30,20,1512、在下述結(jié)論中，正確的是（ ）只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。 A B C D13、若一棵二叉樹具有10

5、個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ ）A9 B11 C15 D不確定 14、設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（ ）。AM1 BM1+M2 CM3 DM2+M315、在下面的程序段中，對x的賦值語句的頻度為（ ）。FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n)16、一個n個頂點的連通無向圖，其邊的個數(shù)至少為（ ）。An-1 Bn Cn+1 Dnlogn；17、二叉樹的第I層上最多含有結(jié)點數(shù)為

6、（ ）A2I B 2I-1-1 C 2I-1 D2I -118、下列排序算法中( )排序在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。A選擇 B冒泡 C歸并 D堆19、二維數(shù)組A的元素都是6個字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10。若A按行存放，元素A8，5的起始地址與A按列存放時的元素（ ）的起始地址一致。AA8,5 B A3,10 C A5,8 D A0,920、散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存放地址，因為散列函數(shù)是一對一的關(guān)系，則選擇好的（ ）方法是散列文件的關(guān)鍵。A散列函數(shù) B除余法中的質(zhì)數(shù) C沖突處理 D散列函數(shù)和沖突處理1、算法是由

7、若干條指令組成的有窮序列，而一個程序不一定滿足有窮性。（ ）2、順序存儲方式只能用于存儲線性結(jié)構(gòu)。( )3、對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。( ) 4、有向圖的鄰接矩陣是對稱矩陣，無向圖的鄰接矩陣是非對稱矩陣。（ ）5、所有二叉樹的度均為2。（ ）6、滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。（ ）7、循環(huán)鏈表不是線性表。 ( ) 8、文件是記錄的集合，文件上的操作主要有兩類：檢索和維護。（ ）9、線性表的特點是每個元素都有一個前驅(qū)和一個后繼。( )10、按中序遍歷二叉排序樹所得到中序序列是一個遞增有序序列。（ ）三、應(yīng)用題（第1、4、6題每題10分，第2、3題每

8、題8分，第5題9分，共55分）1、已知一棵樹邊的集合為：( I , M ),( I ,N ),( E, I ),( B,E ),( B,D ),( A,B ),( G, J ),( G,K ),( C,G ),( C,F ),(H,L ),( C,H ),( A,C )用樹形表示法畫出此樹，并回答下列問題：（1）哪個是此樹的根結(jié)點？哪些是葉子結(jié)點？（2）樹的度數(shù)和樹的深度是多少？（3）寫出結(jié)點G的雙親、祖先、孩子？（4）寫出結(jié)點E的子孫、兄弟和結(jié)點E所在的層次？2、已知一棵二叉樹的中序遍歷序列和后序遍歷序列分別為EBIFJAGDH和EIJFBGHDA。要求：（1）畫出這棵二叉樹；（2）寫出這棵

9、二叉樹的前序遍歷序列。3、已知世界六大城市為:北京(Pe)、紐約(N)、巴黎(Pa)、 倫敦(L) 、 東京(T) 、 墨西哥(M),下表給定了這六大城市之間的交通里程:姓名:_ 學(xué)號:_ 年級:_ 專業(yè):_.密封線 世界六大城市交通里程表(單位:百公里)PeNPaLTMPe109828121124N109585510832Pa825839792L815539589T211089795113M124329289113 （1）畫出這六大城市的交通網(wǎng)絡(luò)圖;（2）畫出該交通網(wǎng)絡(luò)圖按權(quán)值遞增的順序來構(gòu)造的最小(代價)生成樹。 4、假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g，h中的字母構(gòu)成。它

10、們在電文中出現(xiàn)的頻度分別為7,19,2,6,32,3,21,10。要求：（1) 請為這8個字母設(shè)計哈夫曼編碼，并畫出對應(yīng)的哈夫曼樹；（2）計算該哈夫曼樹的最小加權(quán)路徑長度WPL。5、對給定的一組關(guān)鍵字：49，38，65，97，76，13，27，49，55，4 分別寫出希爾排序（增量為5，3，1）、起泡排序和歸并排序的前3趟排序結(jié)果。6、設(shè)散列表長度為13，即其地址空間為0-12，散列函數(shù)H(k)=K mod 13,對關(guān)鍵字序列19，14，23，01，68，20，84，27，55，11，10，79。要求：（1）畫出用線性探查法解決沖突時構(gòu)造的散列表（哈希表）。（2）設(shè)每個記錄的查找概率相等，計算

11、查找成功的平均查找長度（ASLsucc）以及查找不成功的平均查找長度(ASLunsucc)。四、算法設(shè)計題（第1題7分，第2題8分，共15分）1、已知帶頭結(jié)點的動態(tài)單鏈表L中的結(jié)點是按整數(shù)值遞增排列，試寫一算法將值為X的結(jié)點插入鏈表L中，使L仍然有序。單鏈表的描述如下：typedef int datatype;typedef struct node datatype data; struct node *next; linklist;2、試寫出遞歸的二分查找（折半查找）算法。 數(shù)據(jù)結(jié)構(gòu)姓名:_ 學(xué)號:_ 年級:_ 專業(yè):_.密封線期末試卷答案一、選擇題，共20個小題，每小題1分，共20分；本題

12、為單項選擇題，多選或錯選均不能得分。標(biāo)準(zhǔn)答案如下：題號1234567891011121314151617181920答案B BABABDCCCCDBDCACCBD二、判斷題（在正確的題后括號內(nèi)打“”，在錯誤的題后括號內(nèi)打“×” ，共10個小題，每小題1分，共10分）。標(biāo)準(zhǔn)答案如下：題號12345678910答案××××××三、應(yīng)用題（共計55分）1、.10分（1）根結(jié)點為A葉子結(jié)點為：D，F(xiàn)，J，K，L，M，N （2）樹的度為3；樹的深度為5。 （3）結(jié)點G的雙親為C結(jié)點G祖先為C，A結(jié)點G孩子為J，K （4）結(jié)點E的子孫為

13、 I，M，N結(jié)點E的兄弟為D結(jié)點E所在的層次為3。2、.8分（1）該二叉樹為： （2）該二叉樹前序序列： A B E F I J D G HAABDEFGHIJ3、.8分（1）六大城市的交通網(wǎng)絡(luò)圖1138995929733210855581242181109PeTLMNPa82（2）最小生成樹6個頂點和5條邊的集合如下： V(G)=Pe,N,Pa,L,T,M E(G)=(L,Pa,3),(Pe,T,21),(M,N,32),(L,N,55),(L,Pe,81)4、.10分（1)對應(yīng)的哈夫曼樹10040601921283211175671023這8個字母a,b,c,d,e,f,g，h的哈夫曼編碼

14、分別為：1010 ，00 ，10000 ，1001 ，11 ，10001 ，01 ，1011（2）其最小的加權(quán)路徑長度：WPL=19*2+21*2+32*2+6*4+7*4+10*4+2*5+3*5=38+42+64+24+28+40+10+15=2615、.9分希爾排序（增量為5，2，1）的前3趟排序結(jié)果：第1趟結(jié)果：13 27 49 55 4 49 38 65 97 76第2趟結(jié)果：4 27 13 49 38 55 49 65 97 76第3趟結(jié)果：4 13 27 38 49 49 55 65 76 97起泡排序的前3趟排序結(jié)果：第1趟結(jié)果：4 49 38 65 97 76 13 27 4

15、9 55第2趟結(jié)果：4 13 49 38 65 97 76 27 49 55第3趟結(jié)果：4 13 27 49 38 65 97 76 49 55歸并排序（二路歸并）的前3趟排序結(jié)果：第1趟結(jié)果：38 49 65 97 13 76 27 49 4 55第2趟結(jié)果：38 49 65 97 13 27 49 76 4 55第3趟結(jié)果：13 27 38 49 49 65 76 97 4 556、.10分（1）用線性探查法解決沖突時所構(gòu)造的散列表：散列地址0123456789101112關(guān)鍵字14168275519208479231110比較次數(shù)121431139113 （2）在等概率情況下，這種方法的

16、查找成功及查找不成功的平均查找長度（ASL）分別為：ASLsucc=1+2+1+4+3+1+1+3+9+1+1+3）/12=30/12=5/2=2.5ASLunsucc=(1+13+12+11+10+9+8+7+6+5+4+3+2)/13=72、/*初始值：low=0;high=n-1;*/int BINSEARCH（R,low,high,K）table R ;keytype K;int low,high; while(low<=high) mid=(low+high)/2;if(K=Rmid.key) return mid;if(K<Rmid.key)BINSEARCH（R,low,mid-1,K）;ElseBINSEARCH（R,mid+1,high,K）;return(-1); 四、算法設(shè)計（第1題7分，第2題8分，共計15分）1、linklist * insert(linklist *h,datatype x)/*h是遞增有序單鏈表的頭指針，X為待插入元素*/ linklist *p,*s; p=h; while(p->next!=NULL