數(shù)據(jù)結構試卷及答案.doc

姓名:_ 學號:_ 年級:_ 專業(yè):_.密封線 期末考試數(shù)據(jù)結構A卷注意事項：題號一二三四總分核分人得分得分評卷人一、單項選擇題（請將正確答案的字母填寫在每題對應的括號內(nèi)，每小題1分，共20分）1、下面關于串的敘述中，哪一個是不正確的？（ ）A串是字符的有限序列 B空串是由空格構成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈式存儲2、設無向圖的頂點個數(shù)為n，則該圖最多有（ ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D03、以下數(shù)據(jù)結構中，（ ）是非線性數(shù)據(jù)結構。A樹 B字符串 C隊列 D棧4、下面關于線性表的敘述中，錯誤的是哪一個？（ ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。5、假設以數(shù)組Am存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m6、在單鏈表指針為p的結點之后插入指針為s的結點,正確的操作是（ ）。Ap-next=s; s-next=p-next; Bs-next=p-next; p-next=s;Cp-next=s; p-next=s-next; Dp-next=s-next; p-next=s;7、設棧的輸入序列是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)9、棧和隊都是（ ）A順序存儲的線性結構 B鏈式存儲的非線性結構C限制存取點的線性結構 D限制存取點的非線性結構10、從邏輯上可以把數(shù)據(jù)結構分為（ ）兩大類。A動態(tài)結構、靜態(tài)結構 B順序結構、鏈式結構 C線性結構、非線性結構 D初等結構、構造型結構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、在下述結論中，正確的是（ ）只有一個結點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹結點個數(shù)小于或等于深度相同的滿二叉樹。 A B C D13、若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數(shù)是（ ）A9 B11 C15 D不確定 14、設森林F中有三棵樹，第一，第二，第三棵樹的結點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數(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層上最多含有結點數(shù)為（ ）A2I B 2I-1-1 C 2I-1 D2I -118、下列排序算法中( )排序在一趟結束后不一定能選出一個元素放在其最終位置上。A選擇 B冒泡 C歸并 D堆19、二維數(shù)組A的元素都是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10。若A按行存放，元素A8，5的起始地址與A按列存放時的元素（ ）的起始地址一致。AA8,5 B A3,10 C A5,8 D A0,920、散列文件使用散列函數(shù)將記錄的關鍵字值計算轉化為記錄的存放地址，因為散列函數(shù)是一對一的關系，則選擇好的（ ）方法是散列文件的關鍵。A散列函數(shù) B除余法中的質數(shù) C沖突處理 D散列函數(shù)和沖突處理得分評卷人二、判斷題，在正確的題后括號內(nèi)打“”，在錯誤的題后括號內(nèi)打“”（每小題1分，共10分）姓名:_ 學號:_ 年級:_ 專業(yè):_.密封線1、算法是由若干條指令組成的有窮序列，而一個程序不一定滿足有窮性。（ ）2、順序存儲方式只能用于存儲線性結構。( )3、對任何數(shù)據(jù)結構鏈式存儲結構一定優(yōu)于順序存儲結構。( ) 4、有向圖的鄰接矩陣是對稱矩陣，無向圖的鄰接矩陣是非對稱矩陣。（ ）5、所有二叉樹的度均為2。（ ）6、滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。（ ）7、循環(huán)鏈表不是線性表。 ( ) 8、文件是記錄的集合，文件上的操作主要有兩類：檢索和維護。（ ）9、線性表的特點是每個元素都有一個前驅和一個后繼。( )10、按中序遍歷二叉排序樹所得到中序序列是一個遞增有序序列。（ ）得分評卷人三、應用題（第1、4、6題每題10分，第2、3題每題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）哪個是此樹的根結點？哪些是葉子結點？（2）樹的度數(shù)和樹的深度是多少？（3）寫出結點G的雙親、祖先、孩子？（4）寫出結點E的子孫、兄弟和結點E所在的層次？2、已知一棵二叉樹的中序遍歷序列和后序遍歷序列分別為EBIFJAGDH和EIJFBGHDA。要求：（1）畫出這棵二叉樹；（2）寫出這棵二叉樹的前序遍歷序列。3、已知世界六大城市為:北京(Pe)、紐約(N)、巴黎(Pa)、 倫敦(L) 、 東京(T) 、 墨西哥(M),下表給定了這六大城市之間的交通里程:姓名:_ 學號:_ 年級:_ 專業(yè):_.密封線 世界六大城市交通里程表(單位:百公里)PeNPaLTMPe109828121124N109585510832Pa825839792L815539589T211089795113M124329289113 （1）畫出這六大城市的交通網(wǎng)絡圖;（2）畫出該交通網(wǎng)絡圖按權值遞增的順序來構造的最小(代價)生成樹。 4、假設用于通信的電文由字符集a,b,c,d,e,f,g，h中的字母構成。它們在電文中出現(xiàn)的頻度分別為7,19,2,6,32,3,21,10。要求：（1) 請為這8個字母設計哈夫曼編碼，并畫出對應的哈夫曼樹；（2）計算該哈夫曼樹的最小加權路徑長度WPL。5、對給定的一組關鍵字：49，38，65，97，76，13，27，49，55，4 分別寫出希爾排序（增量為5，3，1）、起泡排序和歸并排序的前3趟排序結果。姓名:_ 學號:_ 年級:_ 專業(yè):_.密封線6、設散列表長度為13，即其地址空間為0-12，散列函數(shù)H(k)=K mod 13,對關鍵字序列19，14，23，01，68，20，84，27，55，11，10，79。要求：（1）畫出用線性探查法解決沖突時構造的散列表（哈希表）。（2）設每個記錄的查找概率相等，計算查找成功的平均查找長度（ASLsucc）以及查找不成功的平均查找長度(ASLunsucc)。得分評卷人四、算法設計題（第1題7分，第2題8分，共15分）1、已知帶頭結點的動態(tài)單鏈表L中的結點是按整數(shù)值遞增排列，試寫一算法將值為X的結點插入鏈表L中，使L仍然有序。單鏈表的描述如下：typedef int datatype;typedef struct node datatype data; struct node *next; linklist;2、試寫出遞歸的二分查找（折半查找）算法。本試卷共 6 頁第5頁 本試卷共 6 頁第6頁黃淮學院 2006 2007 年第二學期計科系 數(shù)據(jù)結構期末試卷（A）評分標準及標準答案一、選擇題，共20個小題，每小題1分，共20分；本題為單項選擇題，多選或錯選均不能得分。標準答案如下：題號1234567891011121314151617181920答案B BABABDCCCCDBDCACCBD二、判斷題（在正確的題后括號內(nèi)打“”，在錯誤的題后括號內(nèi)打“” ，共10個小題，每小題1分，共10分）。標準答案如下：題號12345678910答案三、應用題（共計55分）1、.10分（1）根結點為A葉子結點為：D，F(xiàn)，J，K，L，M，N （2）樹的度為3；樹的深度為5。 （3）結點G的雙親為C結點G祖先為C，A結點G孩子為J，K （4）結點E的子孫為 I，M，N結點E的兄弟為D結點E所在的層次為3。2、.8分（1）該二叉樹為： （2）該二叉樹前序序列： A B E F I J D G HAABDEFGHIJ3、.8分（1）六大城市的交通網(wǎng)絡圖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)對應的哈夫曼樹10040601921283211175671023這8個字母a,b,c,d,e,f,g，h的哈夫曼編碼分別為：1010 ，00 ，10000 ，1001 ，11 ，10001 ，01 ，1011（2）其最小的加權路徑長度：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趟排序結果：第1趟結果：13 27 49 55 4 49 38 65 97 76第2趟結果：4 27 13 49 38 55 49 65 97 76第3趟結果：4 13 27 38 49 49 55 65 76 97起泡排序的前3趟排序結果：第1趟結果：4 49 38 65 97 76 13 27 49 55第2趟結果：4 13 49 38 65 97 76 27 49 55第3趟結果：4 13 27 49 38 65 97 76 49 55歸并排序（二路歸并）的前3趟排序結果：第1趟結果：38 49 65 97 13 76 27 49 4 55第2趟結果：38 49 65 97 13 27 49 76 4 55第3趟結果：13 27 38 49 49 65 76 97 4 556、.10分（1）用線性探查法解決沖突時所構造的散列表：散列地址0123456789101112關鍵字14168275519208479231110比較次數(shù)121431139113 （2）在等概率情況下，這種方法的查找成功及查找不成功的平均查找長度（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; whil