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

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

2、接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線(xiàn)性表采用鏈接存儲(chǔ)，便于插入和刪除操作。5、假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m6、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn),正確的操作是（ ）。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)二、判斷題，在正確的題后括號(hào)內(nèi)打“”，在錯(cuò)誤的題后括號(hào)內(nèi)打“×”（每小題1分，共10分）9、棧和隊(duì)都是（ ）A順序存儲(chǔ)的線(xiàn)性結(jié)構(gòu) B鏈?zhǔn)酱鎯?chǔ)的非線(xiàn)性結(jié)構(gòu)C限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu) D限制存

4、取點(diǎn)的非線(xiàn)性結(jié)構(gòu)10、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類(lèi)。A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線(xiàn)性結(jié)構(gòu)、非線(xiàn)性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)11、下列四個(gè)序列中，哪一個(gè)是堆（ ）。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é)論中，正確的是（ ）只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0; 二叉樹(shù)的度為2； 二叉樹(shù)的左右子樹(shù)可任意交換;深度為K的完全二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿(mǎn)二叉樹(shù)。 A B C D13、若一棵二叉樹(shù)具有10

5、個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A9 B11 C15 D不確定 14、設(shè)森林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。AM1 BM1+M2 CM3 DM2+M315、在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（ ）。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、一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（ ）。An-1 Bn Cn+1 Dnlogn；17、二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為

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

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

8、題8分，第5題9分，共55分）1、已知一棵樹(shù)邊的集合為：( 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 )用樹(shù)形表示法畫(huà)出此樹(shù)，并回答下列問(wèn)題：（1）哪個(gè)是此樹(shù)的根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？（2）樹(shù)的度數(shù)和樹(shù)的深度是多少？（3）寫(xiě)出結(jié)點(diǎn)G的雙親、祖先、孩子？（4）寫(xiě)出結(jié)點(diǎn)E的子孫、兄弟和結(jié)點(diǎn)E所在的層次？2、已知一棵二叉樹(shù)的中序遍歷序列和后序遍歷序列分別為EBIFJAGDH和EIJFBGHDA。要求：（1）畫(huà)出這棵二叉樹(shù)；（2）寫(xiě)出這棵

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

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

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

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

13、 I，M，N結(jié)點(diǎn)E的兄弟為D結(jié)點(diǎn)E所在的層次為3。2、.8分（1）該二叉樹(shù)為： （2）該二叉樹(shù)前序序列： A B E F I J D G HAABDEFGHIJ3、.8分（1）六大城市的交通網(wǎng)絡(luò)圖1138995929733210855581242181109PeTLMNPa82（2）最小生成樹(shù)6個(gè)頂點(diǎn)和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)對(duì)應(yīng)的哈夫曼樹(shù)10040601921283211175671023這8個(gè)字母a,b,c,d,e,f,g，h的哈夫曼編碼

14、分別為：1010 ，00 ，10000 ，1001 ，11 ，10001 ，01 ，1011（2）其最小的加權(quán)路徑長(zhǎng)度：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）用線(xiàn)性探查法解決沖突時(shí)所構(gòu)造的散列表：散列地址0123456789101112關(guān)鍵字14168275519208479231110比較次數(shù)121431139113 （2）在等概率情況下，這種方法的

16、查找成功及查找不成功的平均查找長(zhǎng)度（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è)計(jì)（第1題7分，第2題8分，共計(jì)15分）1、linklist * insert(linklist *h,datatype x)/*h是遞增有序單鏈表的頭指針，X為待插入元素*/ linklist *p,*s; p=h; while(p->next!=NULL