數(shù)據(jù)結(jié)構(gòu)真題2005年下半年

1、數(shù)據(jù)結(jié)構(gòu)真題 2005 年下半年（ 總分： 154.98 ，做題時(shí)間： 90 分鐘 ）一、 B 單項(xiàng)選擇題 /B（ 總題數(shù)： 15，分?jǐn)?shù)： 30.00）1. 若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組（K,R），其中K是數(shù)據(jù)元素的有限集合，則R是K上（）（分?jǐn)?shù)： 2.00 ）A. 操作的有限集合B. 映象的有限集合C. 類型的有限集合D. 關(guān)系的有限集合V解析：2. 在長度為n的順序表中刪除第i個(gè)元素（1 <i <n）時(shí)，元素移動(dòng)的次數(shù)為（）（分?jǐn)?shù)： 2.00 ）A. n-i+1B. iC. i+1D. n-iV解析：3. 若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則該鏈表為空的判定條件是（）（分

2、數(shù)： 2.00 ）A. head=NULL VB. head > next=NULLC. head!=NULLD. head > next=head解析：4. 引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是（ ）（分?jǐn)?shù)： 2.00 ）A. 出隊(duì) VB. 入隊(duì)C. 取隊(duì)頭元素D. 取隊(duì)尾元素解析：5. 若進(jìn)棧序列為 1,2,3,4,5,6 ，且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列是 （ ） （分?jǐn)?shù)： 2.00 ）A. 2,4,3,1,5,6B. 3,2,4,1,6,5C. 4,3,2,1,5,6D. 2,3,5,1,6,4V解析：6. 字符串通常采用的兩種存儲(chǔ)方式是（ ）（分?jǐn)?shù)： 2

3、.00 ）A. 散列存儲(chǔ)和索引存儲(chǔ)B. 索引存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)C. 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) VD. 散列存儲(chǔ)和順序存儲(chǔ)解析：7. 設(shè)主串長為n，模式串長為m（nn），則在匹配失敗情況下，樸素匹配算法進(jìn)行的無效位移次數(shù)為（）（分?jǐn)?shù)： 2.00 ）A. mB. n-mC. n-m+1 VD. n解析：8. 二維數(shù)組A1218采用列優(yōu)先的存儲(chǔ)方法，若每個(gè)元素各占3個(gè)存儲(chǔ)單元，且第1個(gè)元素的地址為 則元素A97的地址為()(分?jǐn)?shù)：2.00 )A. 429 VB. 432C. 435D. 438解析：9. 對(duì)廣義表 L=(a,b) , (c,d) , (e,f)執(zhí)行操作 tail(tail(L) 的結(jié)果是()(

4、分?jǐn)?shù)：2.00 )A. (e,B. (e,)VC. (D. ()解析：10. 下列圖示的順序存儲(chǔ)結(jié)構(gòu)表示的二叉樹是(分?jǐn)?shù)：2.00 )A. VB.C.D.解析：11. n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有()(分?jǐn)?shù)：2.00 )A. n-1條有向邊B. n條有向邊VC. n(n-1)/2 條有向邊D. n(n-1)條有向邊進(jìn)行增量為3的一趟希爾排序的結(jié)果為()則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為()解析：12. 對(duì)關(guān)鍵字序列(56,23,78,92,88,67,19,34)(分?jǐn)?shù)：2.00 )A. (19,23,56,34,78,67,88,92)B. (23,56,78,66,88,92,19,34)

5、C. (19,23,34,56,67,78,88,92)D. (19,23,67,56,34,78,92,88)V解析：13. 若在9階B-樹中插入關(guān)鍵字引起結(jié)點(diǎn)分裂,(分?jǐn)?shù)：2.00 )A. 4B. 5C.8 VD.9解析：14. 由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹 （ ）（分?jǐn)?shù)： 2.00 ）A. 其形態(tài)不一定相同，但平均查找長度相同B. 其形態(tài)不一定相同，平均查找長度也不一定相同VC. 其形態(tài)均相同，但平均查找長度不一定相同D. 其形態(tài)均相同，平均查找長度也都相同解析：15.ISAM文件和VSAM文件的區(qū)別之一是（）（分?jǐn)?shù)： 2.00 ）A. 前者是索引順序文件，后者是索引非順序文件B

6、. 前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取C. 前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動(dòng)態(tài)索引結(jié)構(gòu)VD. 前者的存儲(chǔ)介質(zhì)是磁盤，后者的存儲(chǔ)介質(zhì)不是磁盤解析：二、 B 填空題 /B（ 總題數(shù)： 10，分?jǐn)?shù)： 20.00）16. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的 1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：存儲(chǔ)結(jié)構(gòu)）解析：17. 刪除雙向循環(huán)鏈表中 *p 的前驅(qū)結(jié)點(diǎn) （ 存在 ） 應(yīng)執(zhí)行的語句是 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： p> prior=p > prior > prior;）解析：p> prior > next=p;（

7、或 p> prior > prior > next=p; p> prior=p > prior > prior;18. 棧下溢是指在 1 時(shí)進(jìn)行出棧操作。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：?？眨┙馕觯?9. 已知 substr（s,i,len） 函數(shù)的功能是返回串 s 中第 i 個(gè)字符開始長度為 len 的子串， strlen（s） 函數(shù)的功能是返回串 s 的長度。若 s="ABCDEFGHU,t="ABCD"，執(zhí)行運(yùn)算 substr（s,strlen（t）,strlen（t）后的返回值為 1 。（分?jǐn)?shù)： 2.00

8、 ）填空項(xiàng) 1: （正確答案： "EFGH"）解析：20. 去除廣義表LS=（a1,日2,日3, ,an）中第1個(gè)元素，由其余元素構(gòu)成的廣義表稱為LS的1。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：表尾）解析：21. 已知完全二叉樹T的第5層只有7個(gè)結(jié)點(diǎn)，則該樹共有1個(gè)葉子結(jié)點(diǎn)。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： 11）解析：22. 在有向圖中，以頂點(diǎn) V為終點(diǎn)的邊的數(shù)目稱為 V的1 o（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：入度）解析：23. 當(dāng)關(guān)鍵字的取值范圍是實(shí)數(shù)集合時(shí)，無法進(jìn)行箱排序和1排序。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案

9、：基數(shù)）解析：(分?jǐn)?shù)： 2.00 )填空項(xiàng) 1:解析：25. 假設(shè)散列文件中一個(gè)桶能存放(分?jǐn)?shù)： 2.00 )填空項(xiàng) 1:解析：24. 產(chǎn)生沖突現(xiàn)象的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的 1正確答案：同義詞)m個(gè)記錄，則桶“溢出”的含義是，當(dāng)需要插入新的記錄時(shí)，該桶中1(正確答案：已有 m個(gè)同義詞的記錄(或：已有m個(gè)記錄；或：已滿)、 B 解答題 /B( 總題數(shù)： 2，分?jǐn)?shù)： 30.00)假設(shè)以數(shù)組 seqnm 存放循環(huán)隊(duì)列的元素，設(shè)變量 rear 和 qHelen 分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和 元素的個(gè)數(shù)。(1) 寫出隊(duì)滿的條件表達(dá)式；(2) 寫出隊(duì)空的條件表達(dá)式；(3) 設(shè) m=40， rea

10、r=13 ， quelen=19 ，求隊(duì)頭元素的位置；(4) 寫出一般情況下隊(duì)頭元素位置的表達(dá)式。(分?jǐn)?shù)： 19.98 )(1) . (分?jǐn)?shù)： 3.33 ) 正確答案： ()解析：(2) .(分?jǐn)?shù)： 3.33 ) 正確答案： ()解析： quelen=0(3) .(分?jǐn)?shù)： 3.33 ) 正確答案： ()解析： 35(4) .(分?jǐn)?shù)： 3.33 ) 正確答案： ()解析： (rear-quelen+1+m)%m解析： 解析：對(duì)7 個(gè)關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行 1 0次關(guān)鍵字的比較。(1) 假設(shè)關(guān)鍵字集合為 1,2,3,4,5,6,7 ，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列；(2)

11、 對(duì)所舉序列進(jìn)行快速排序，寫出排序過程。(分?jǐn)?shù)： 10.00 )(1) . (分?jǐn)?shù)： 5.00 ) 正確答案： ()解析：(2) .分?jǐn)?shù)： 5.00 )正確答案： ()解析：初始關(guān)鍵字 4 7 1 3 6 5 2 四、 B 算法閱讀題 /B(一次劃分后得 (2 3 1)4(6 5 7)繼續(xù)劃分后得 (1)2(3) (5)6(7)總題數(shù)：4，分?jǐn)?shù)：55.00)閱讀下列算法，并回答問題：(1) 設(shè)順序表 L=(3,7,11,14,20,51)，寫出執(zhí)行f30(&L,15)之后的 L；(2) 設(shè)順序表 L=(4,7,10,14,20,51)，寫出執(zhí)行f30(&L,10)之后的 L；(

12、3) 簡述算法的功能。void f30(SeqList*L,DataType x)int i=0,j;while(i < L- > length&&x > L- > datai)i+if(i < L> length&& x=L > dataifor(j=i+1;j < L> length;j+)L> dataj-1=L > dataj;L> length-;elsefor(j=L > length;j>i;j-)L> dataj=L > dataj-1;L> d

13、atai=x;L> length+;(分?jǐn)?shù)： 15.00 )(1).(分?jǐn)?shù)： 5.00 )解析：填空項(xiàng) 1: (正確答案： (4,7,14,20,51) )解析：(3) .(分?jǐn)?shù)： 5.00 ) 正確答案： ()解析：當(dāng)非遞減順序表中存在元素 x 時(shí)，從表中刪除該元素；否則將 X 保序插入到順序表中 已知圖的鄰接表表示的形式說明如下：#define MaxNum 50 / 圖的最大頂點(diǎn)數(shù)typedef struct nodeint adjvex; / 鄰接點(diǎn)域struct node*next; / 鏈指針域EdgeNode; / 邊表結(jié)點(diǎn)結(jié)構(gòu)描述typedef structchar ve

14、rtex; / 頂點(diǎn)域EdgeNode*firstedge;/ 邊表頭指針VertexNode; / 頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述typedef struetVertexNode adjlistMaxNum;/ 鄰接表int n,e; / 圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)ALGraph; / 鄰接表結(jié)構(gòu)描述下列算法輸出圖G的深度優(yōu)先生成樹(或森林)的邊。閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一 個(gè)完整的算法。typedef enumFALSE,TRUEBoolean;Boolean visitedMaxNurn;void DFSForest(ALGraph*G)int i;for(i=0;iv G->

15、 n;i+)visitedi=U/U;for(i=0;iv G-> n;i+)if(!visitedi)DFSTree(G,i);void DFSTree(ALGraph*G,int i)EdgeNode*p;visitedi=TRUE;p=G> adjlisti.firstedge;while(p!=NULL)if(!visitedp > adjvex)printf("v %c,%c",G> adjlisti.vertex,G> adjlistp> adjvex.vertex);U (2) /U;U (3) /U;(分?jǐn)?shù)： 15.00

16、)(1).(分?jǐn)?shù)： 5.00 )解析：填空項(xiàng) 1: (正確答案： DFSTree(G,P> adjvex) )解析：填空項(xiàng) 1: (正確答案： p=p> next )解析：閱讀下列算法，并回答問題：(1) 假設(shè)數(shù)組 L8=3,0,5,1,6,4,2,7 ，寫出執(zhí)行函數(shù)調(diào)用 f32(L,8) 后的 L；(2) 寫出上述函數(shù)調(diào)用過程中進(jìn)行元素交換操作的總次數(shù)。void fS2(int R,int n)int i,t;for(i=0;i v n-1;i+)while(Ri!=i)t=RRi-1;RRi=Ri;Ri=t;(分?jǐn)?shù)： 10.00 )(1).(分?jǐn)?shù)： 5.00 )解析：填空項(xiàng) 1

17、: (正確答案：共進(jìn)行 5 次元素交換。)解析：已知帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為 m,散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為：。請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)內(nèi)容，使 其成為一個(gè)完整算法。void f33(LinkList L,LinkList H,int m)/由帶頭結(jié)點(diǎn)的單鏈表L生成散列表H,散列表生成之后原鏈表不再存在int i,j;LinkList p,q;for(i=O;i < m;i+)H【i=【U (1) /U;p=L> next;while(p)q=p> nextj=p &g

18、t; key%m;U (2) /U;Hj=p;U (3) /U;free(L);已知帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為 m,散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為：。請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)內(nèi)容，使 其成為一個(gè)完整算法。void f33(LinkList L, LinkList H,int m)/由帶頭結(jié)點(diǎn)的單鏈表L生成散列表H,散列表生成之后原鏈表不再存在int i,j;LinkList p,q;for(i=0;i < m;i+)Hi=U (1) /U;p=L> next;while(p)q=p

19、> nextj=p > key%m;U (2) /U;Hj=p;U (3) /U;free(L);(分?jǐn)?shù)：15.00 )(1).(分?jǐn)?shù)：5.00 )解析：填空項(xiàng)1: (正確答案：p> next=Hj)解析：填空項(xiàng)1: (正確答案：p=q)解析：五、 B 算法設(shè)計(jì)題 /B（ 總題數(shù)： 1，分?jǐn)?shù)： 20.00）假設(shè)以帶雙親指針的二叉鏈表作為 - 二叉樹的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)的類型說明如下所示： typedef char DataType;typedef struct nodeDataType data;struct node*lchild,*rchild; / 左右孩子指針struct node*parent; / 指