2005年10月全國自考數(shù)據(jù)結(jié)構(gòu)試題及答案

1、2005年10月全國自考 數(shù)據(jù)結(jié)構(gòu)試題課程代碼： 02331、單項選擇題 ( 本大題共 15 小題，每小題 2 分，共 30 分)7 / 71. 若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K, R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上(D)A. 操作的有限集合B.映象的有限集合C. 類型的有限集合D.關(guān)系的有限集合2. 在長度為 n 的順序表中刪除第 i個元素(1 w i w n)時，元素移動的次數(shù)為(D)A. n-i+1B. iC. i+1D. n-i3. 若不帶頭結(jié)點的單鏈表的頭指針為head，則該鏈表為空的判定條件是(A)A. head=NULLC. head!=NULLA. 出隊5. 若進(jìn)棧序

2、列為B. 入隊1，2，3，4， 5， 6，C. 取隊頭元素 D. 取隊尾元素且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不 可能出現(xiàn)的出棧序B. head->next=NULLD. head->next=head4. 引起循環(huán)隊列隊頭位置發(fā)生變化的操作是 (A)列是 (D)A. 2 ， 4， 3， 1，5，B. 3， 2， 4， 1 ， 6， 5C. 4 ， 3， 2， 1，5，D. 2， 3， 5， 1 ， 6， 46.字符串通常采用的兩種存儲方式是( C)A.散列存儲和索引存儲B.索引存儲和鏈?zhǔn)酱鎯.順序存儲和鏈?zhǔn)酱鎯.散列存儲和順序存儲7.設(shè)主串長為n,模式串長為m(mw n) ，則在匹

3、配失敗情況下，樸素匹配算法進(jìn)行的無效位移次數(shù)為 (C)A. mB. n-mC. n-m+1D. n8.二維數(shù)組A : 12 18采用列優(yōu)先的存儲方法，若每個元素各占3 個存儲單元，且第 1個元素的地址為150,則元素A :9 :7的地址為(A)A. 429B. 432C. 435D. 4389. 對廣義表 L=(a,b),(c,d),(e,f)執(zhí)行操作 tail(tail(L)的結(jié)果是 (B)A. (e,f)B. (e,f)C. (f)D. ( )10. 下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是 (A)11. n個頂點的強(qiáng)連通圖中至少含有(B)A. n-1 條有向邊B. n條有向邊C. n(n-1

4、)/2 條有向邊D. n（n-1）條有向邊12.對關(guān)鍵字序列(56，23，78，92,88,67, 19, 34）進(jìn)行增量為3的一趟希爾排序的結(jié)果6ABCDEF0 1 2 3 4 5 6 7 8 9 10 H12為(D)A. (19 ，23，56,34， 78, 67, 88,92)B. (23,56, 78, 66, 88, 92, 19,34)C. (19 , 23, 34,56, 67, 78, 88,92)D. (19,23, 67, 56, 34, 78, 92,88)13.若在9階B-樹中插入關(guān)鍵字引起結(jié)點分裂,則該結(jié)點在插入前含有的關(guān)鍵字個數(shù)為(C)A. 4B. 5C. 8D.

5、914.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(B)A. 其形態(tài)不一定相同，但平均查找長度相同B. 其形態(tài)不一定相同，平均查找長度也不一定相同C. 其形態(tài)均相同，但平均查找長度不一定相同D. 其形態(tài)均相同，平均查找長度也都相同15. ISAM文件和VSAM文件的區(qū)別之一是（C）A. 前者是索引順序文件，后者是索引非順序文件B. 前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取C. 前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動態(tài)索引結(jié)構(gòu)D. 前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤、填空題（本大題共10小題，每空2分，共20分）16. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的（存儲結(jié)構(gòu)）。17. 刪除雙

6、向循環(huán)鏈表中*p的前驅(qū)結(jié)點(存在)應(yīng)執(zhí)行的語句是(p->prior=p->prior->prior;p->prior- >n ext=p;)。18. 棧下溢是指在(空棧)時進(jìn)行出棧操作。19. 已知substr(s,i,len)函數(shù)的功能是返回串s中第i個字符開始長度為len的子串，strlen(s)函數(shù)的功能是返回串s的長度。若s= ABCDEFGHIJ'K ,t= ” ABCD ,執(zhí)行運算substr(s,strlen(t), strlen(t)后的返回值為("EFGH )。20. 去除廣義表LS=(a1,a2,a3,aj中第1個元素，由其余

7、元素構(gòu)成的廣義表稱為LS的(表尾)。21. 已知完全二叉樹 T的第5層只有7個結(jié)點，則該樹共有(11)個葉子結(jié)點。22. 在有向圖中，以頂點 v為終點的邊的數(shù)目稱為v的(入度)。23. 當(dāng)關(guān)鍵字的取值范圍是實數(shù)集合時，無法進(jìn)行箱排序和( 基數(shù))排序。24. 產(chǎn)生沖突現(xiàn)象的兩個關(guān)鍵字稱為該散列函數(shù)的( 同義詞)。25. 假設(shè)散列文件中一個桶能存放m個記錄，則桶“溢出”的含義是，當(dāng)需要插入新的記錄時，該桶中(已有m個記錄)。三、解答題(本大題共4小題，每小題5分，共20分)26. 假設(shè)以數(shù)組seqnm存放循環(huán)隊列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。(1

8、) 寫出隊滿的條件表達(dá)式；(2) 寫出隊空的條件表達(dá)式； 設(shè)m=40,rear=13,quelen=19, 求隊頭元素的位置；(4)寫出一般情況下隊頭元素位置的表達(dá)式。答：(1)quelen=m quelen=0 (3)35(rear-quelen+1+m)%m27. 已知一棵二叉樹的中序序列為ABCDEFG層序序列為BAFEGC D請畫出該二叉樹。答:題28圖28.畫出下圖所示有向圖的所有強(qiáng)連通分量。29. 對7個關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。（1）假設(shè)關(guān)鍵字集合為123,4,5,6,7，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列;（2）對所舉序列進(jìn)行快速排序，寫出

9、排序過程。答：（1）4 7 1 3 6 5 2（2）初始關(guān)鍵字：4 7 1 3 6 5 2一次劃分后得：（2 3 1）4 （ 6 5 7）再次劃分后得：（1）2 （ 3）4 （ 5）6 （ 7）四、算法閱讀題（本大題共4小題，每小題5分，共20分）30. 閱讀下列算法，并回答問題：(1)設(shè)順序表 L=(3,7,11,14,20,51) ，寫出執(zhí)行 f30(&L,15)之后的 L； 設(shè)順序表L=(4,7,10,14,20,51) ，寫出執(zhí)行f30(&L,10)之后的L；(3) 簡述算法的功能。void f30(SeqList*L, DataType x)int i =0, j;w

10、hile(i<L->length && x>L->datai)i+;if(i<L->length && x=L->datai)for(j=i+1;j<L->le ngth;j+)L->dataj-1=L->dataj;L->le ngth-;elsefor(j=L->le ngth;j>i;j_)L->dataj=L->dataj-1;L->datai=x;L->le ngth+;答：(1) (3,7,11,14,15,20,51 ) (2) ( 4,7,

11、14,20,51 ) (3) 當(dāng)非遞減順序表中存在 元素 x 時，從表中刪除該元素，否則將 x 按按值的順序插入到順序表中。31. 已知圖的鄰接表表示的形式說明如下：#define MaxNum 50 typedef struct node int adjvex; struct node* next;EdgeNode; typedef struct char vertex; EdgeNode *firstedge;VertexNode; typedef struct VertexNode adjlistMaxNum; int n,e;ALGraph; 下列算法輸出圖 G 的深度優(yōu)先生成樹 使其

12、成為一個完整的算法。typedef enumFALSE,TRUEBoolean; Boolean visitedMaxNum;void DFSForest(ALGraph *G) int i;for(i=0;i<G->n;i+) visitedi= (1) ; for(i=0;i<G->n;i+) if(!visitedi)DFSTree(G,i);void DFSTree(ALGraph *G, int i)EdgeNode *p;/ 圖的最大頂點數(shù)/ 鄰接點域/ 鏈指針域/ 邊表結(jié)點結(jié)構(gòu)描述/ 頂點域/ 邊表頭指針/ 頂點表結(jié)點結(jié)構(gòu)描述/ 鄰接表/ 圖中當(dāng)前的頂點數(shù)

13、和邊數(shù)/ 鄰接表結(jié)構(gòu)描述( 或森林 ) 的邊。閱讀算法，并在空缺處填入合適的內(nèi)容Visitedi=TRUE;p=G->adjlisti.firstedge;while(p!=NULL)if(!visitedp->adjvexprintf(" <%c,%c>'G->adjlisti.vertex,G->adjlistp->adjvex.vertex);(2) ;(3) ;答： (1)FALSE(2)DFSTree(G,p->adjvex)(3)p=p->next32閱讀下列算法，并回答問題：假設(shè)數(shù)組L8=3,0,5,1,6,

14、4,2,7 ，寫出執(zhí)行函數(shù)調(diào)用 f32(L , 8)后的L;(2)寫出上述函數(shù)調(diào)用過程中進(jìn)行元素交換操作的總次數(shù)。void f32(int R,int n)int i,t;for (i=0;i< n_1;i+)while(Ri!=i)t=RRi；RRi=Ri；Ri=t;答：(1)L8=0,1,2,3,4,5,6,7(2)共進(jìn)行 5 次交換。33.已知帶頭結(jié)點的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為m散列函數(shù)為 Hash(key)=key%m。keynext請在空缺處填入適當(dāng)內(nèi)容，使其成為一個完整算法。void f33(Li nkL

15、ist L,Li nkListH,i ntwhile(p)m)q=p->n ext;II由帶頭結(jié)點的單鏈表L生成散列表H,j=p->key%m;散列表生成之后原鏈表不再存在(2);int i,j;Hj=p;LinkList p,q;(3);for(i=0;i<m;i+)Hi=(1) ;free(L);p=L->n ext;答：(1)NULL(2)p->next=Hi(3)p=q五、算法設(shè)計題(本大題10分)34.假設(shè)以帶雙親指針的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)的類型說明如下所示：typedef char DataType;typedef struct n

16、ode DataType data;struct node *lchild,*rchild;/ 左右孩子指針struct node *parent;BinTNode;/ 指向雙親的指針typedef BinTNode *BinTree;若 px 為指向非空二叉樹中某個結(jié)點的指針， 可借助該結(jié)構(gòu)求得 px 所指結(jié)點在二叉樹的中序 序列中的后繼。(1) 就后繼的不同情況，簡要敘述實現(xiàn)求后繼操作的方法；(2) 編寫算法求 px 所指結(jié)點的中序序列后繼，并在算法語句中加注注釋。答：(1) 分兩種情況討論當(dāng) *px 的右子樹不為空時，則從 *px 的右孩子開始，沿其左孩子往下查找，直至找到一個 沒有左孩子的結(jié)點為止則該結(jié)點為止，則該節(jié)點為 *px 在中序序列中的后繼。當(dāng) *px 的右子樹為空時，則沿 的最年輕祖先，則該祖先結(jié)點為 (2) BinTree f34(BinTree px)*px 的雙親指針鏈向上查