全國2012年10月自考數(shù)據(jù)結(jié)構(gòu)試題(課程代碼：02331)

1、全國2012年10月高等教育自學考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。選擇題部分注意事項： 1. 答題前，考生務(wù)必將自己的考試課程名稱、姓名、準考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。2. 每小題選出答案后，用2B鉛筆把答題紙上對應(yīng)題目的答案標號涂黑。如需改動，用橡皮擦干凈后，再選涂其他答案標號。不能答在試題卷上。一、單項選擇題(本大題共l5小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題 紙”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。1一個算法的時間耗費的數(shù)量級稱為該算法的 A

2、效率 B難度 C可實現(xiàn)性 D時間復雜度2順序表便于 A插入結(jié)點 B刪除結(jié)點 C按值查找結(jié)點 D按序號查找結(jié)點3設(shè)帶頭結(jié)點的單循環(huán)鏈表的頭指針為head，指針變量P指向尾結(jié)點的條件是 Ap->next->next=head Bp->next=head Cp->next->next=NULL Dp->next=NULL 4設(shè)以數(shù)組A0.m-1存放循環(huán)隊列，front指向隊頭元素，rear指向隊尾元素的下一個位置，則當前隊列中的元素個數(shù)為 A(rear-front+m)m Brear-front+1 C(front-rear+m)m D(rear-front)m

3、5下列關(guān)于順序棧的敘述中，正確的是 A入棧操作需要判斷棧滿，出棧操作需要判斷?？?B入棧操作不需要判斷棧滿，出棧操作需要判斷?？?C入棧操作需要判斷棧滿，出棧操作不需要判斷?？?D入棧操作不需要判斷棧滿，出棧操作不需要判斷?？?A是一個10×10的對稱矩陣，若采用行優(yōu)先的下三角壓縮存儲，第一個元素a0,0的存儲地址為1，每個元素占一個存儲單元，則a7,5的地址為 A25 B26 C33 D34 7樹的后序遍歷等價于該樹對應(yīng)二叉樹的 A層次遍歷 B前序遍歷 C中序遍歷 D后序遍歷8使用二叉線索樹的目的是便于 A二叉樹中結(jié)點的插入與刪除 B在二叉樹中查找雙親 C確定二叉樹的高度 D查找一

4、個結(jié)點的前趨和后繼9設(shè)無向圖的頂點個數(shù)為n，則該圖邊的數(shù)目最多為 An-l Bn(n-1)2 Cn(n+1)2 Dn210可進行拓撲排序的圖只能是 A有向圖 B無向圖 C有向無環(huán)圖 D無向連通圖11下列排序方法中穩(wěn)定的是 A直接插入排序 B直接選擇排序 C堆排序 D快速排序12下列序列不為堆的是 A75,45,65,30,15,25 B75,65,45,30,25,15 C75,65,30,l5,25,45 D75,45,65,25,30,1513對線性表進行二分查找時，要求線性表必須是 A順序存儲 B鏈式存儲 C順序存儲且按關(guān)鍵字有序 D鏈式存儲且按關(guān)鍵字有序14分別用以下序列生成二叉排序樹

5、，其中三個序列生成的二叉排序樹是相同的，不同 的序列是 A(4,1,2,3,5) B(4,2,3,l,5) C(4,5,2,1,3) D(4,2,1,5,3)15下列關(guān)于m階B樹的敘述中，錯誤的是 A每個結(jié)點至多有m個關(guān)鍵字 B每個結(jié)點至多有m棵子樹 C插入關(guān)鍵字時，通過結(jié)點分裂使樹高增加 D刪除關(guān)鍵字時通過結(jié)點合并使樹高降低非選擇題部分注意事項：用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題(本大題共10小題，每小題2分，共20分)16數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的_結(jié)構(gòu)。17在線性表中，表的長度定義為_。18用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1

6、、2、3、4，為了得到 1、3、4、2的出棧順序，相應(yīng)的S和X的操作序列為_。19在二叉樹中，帶權(quán)路徑長度最短的樹稱為_。20已知廣義表G，head(G)與tail(G)的深度分別為4和6，則G的深度是_。21一組字符(a,b,c,d)在文中出現(xiàn)的次數(shù)分別為(7，6，3，5)，字符d的哈夫曼編碼的長度為_。22在一個具有n個頂點的無向圖中，要連通全部頂點至少需要_條邊。23直接選擇排序算法的時間復雜度是_。24對于長度為81的表，若采用分塊查找，每塊的最佳長度為_。25用二叉鏈表保存有n個結(jié)點的二叉樹，則結(jié)點中有_個空指針域。三、解答題(本大題共4小題，每小題5分，共20分)26假設(shè)Q是一個具

7、有11個元素存儲空間的循環(huán)隊列(隊尾指針指向隊尾元素的下一 個位置，隊頭指針指向隊頭元素)，初始狀態(tài)Q.front=Q.rear=0；寫出依次執(zhí)行 下列操作后頭、尾指針的當前值。 a,b,c,d,e,f入隊，a,b,c,d出隊； (1) Q.front=_；Q.rear=_。 g,h,i,j,k,l入隊，e,f,g,h出隊； (2) Q.front=_；Q.rear=_。 M,n,o,P入隊， i,j,k,l,m出隊； (3) Q.front=_；Q.rear=_。27已知一個無向圖如題27圖所示，以為起點，用普里姆(Prim)算法求其最小生成樹，畫出最小生成樹的構(gòu)造過程。28用歸并排序法對序

8、列 (98,36,-9,0,47,23,1,8)進行排序，問： (1)一共需要幾趟歸并可完成排序。 (2)寫出第一趟歸并后數(shù)據(jù)的排列次序。29一組記錄關(guān)鍵字(55,76,44,32,64,82,20,16,43)，用散列函數(shù)H(key)=key11將記錄 散列到散列表HT0.12中去，用線性探測法解決沖突。 (1)畫出存入所有記錄后的散列表。 (2)求在等概率情況下，查找成功的平均查找長度。四、算法閱讀題(本大題共4小題，每小題5分，共20分)30順序表類型定義如下： # define ListSize 100 typedef struct int dataListSize； int leng

9、th； SeqList； 閱讀下列算法，并回答問題： void f30(SeqList *L) int i,j； i=0； while(i<L->length) if (L->datai2!=0) for(j=i+1; j<L->length; j+ L->dataj-1=L->dataj; L->length-;else i+（1）若L->data 中的數(shù)據(jù)為（22,4,63,0,15,29,34,42,3）,則執(zhí)行上述算法后L->data中的數(shù)據(jù)以及L->length的值各是什么？（2）該算法的功能是什么？31.有向圖的鄰接

10、矩陣類型定義如下： #define MVN 100 最大頂點數(shù) typedef int EType; 邊上權(quán)值類型 typedef struct EType edgesMVNMVN; 鄰接矩陣，即邊表 int n; 圖的頂點數(shù)MGraph; 圖類型例如，一個有向圖的鄰接矩陣如下所示：閱讀下列算法，并回答問題：Void f31(MGraph G) Int i,j,k=0; Step1: for (i=0; i<G.n; i+) for (j=0; j<G.n; j+) if (G.edgesij= =1) k+; printf(“%dn”,k); step2: for (j=0; j

11、<G.n; j+) k=0; for (i=0; i<G.n; j+) if (G.edgesij= =1) k+; printf(“%dn”,k); (1)stepl到step2之間的二重循環(huán)語句的功能是什么? (2)step2之后的二重循環(huán)語句的功能是什么?32閱讀下列算法，并回答問題： void f32(int r， int n) Int i，j； for (i=2；i<n；i+) r0=ri； j=i-l； while (r0<rj) rj+l=rj； j=j-1； rj+l=r0； (1)這是哪一種插入排序算法?該算法是否穩(wěn)定? (2)設(shè)置r0的作用是什么?3

12、3順序表類型定義如下： typedef int SeqList100； 閱讀下列算法，并回答問題： void f33(SeqList r， int n) int a, b，i； if (r0<r1) a=r0；b=r1； > else a=r1； b=r0； for (i=2；i<n；i+) if (ri<a) a=ri; else if (ri>b) b=ri； printf(a=d，b=d。n，a，b)； (1)給出該算法的功能； (2)給出該算法的時間復雜度。五、算法設(shè)計題(本題10分)34二叉樹的存儲結(jié)構(gòu)類型定義如下 typedef struct node

13、 int data； struct node *lchild， *rchild； BinNode；typedef BinNode *BinTree； 編寫遞歸算法，求只有一個孩子結(jié)點的結(jié)點總數(shù)，并計算這些結(jié)點的數(shù)據(jù)值的和。 函數(shù)的原型為：void f34(BinTree T, int *count, int *sum) *count和*sum的初值為0。一、單項選擇題1. (   B   ) 2. (   D   )3. (   A   )4. (

14、0;  A   )5. (   D   )6. (   C   )7. (   C   )8. (   A   )9. (   B   )10.(   A   )11.(   B   )12.(   D   )13.( 

15、  C   )  14.(   B   )15.(   C   )二、填空題(本大題共10小題，每空2分，共20分)16. 存儲結(jié)構(gòu)17. q = p->pre;    q->pre->next = p;    p->pre = q->pre;    free( q );18. 棧空19. "DEFG" /注意雙引號不

16、能少20. 表尾21.(I-2)+M/2 葉子結(jié)點22. 入度23. 基數(shù)24. 同義詞25. 已有m個同義詞記錄三、解答題(本大題共4小題，每小題5分，共20分)26. (1) quelen = m(2) quelen = 0(3) ( 13 - 19 + 40 ) % 40 = 34(4) ( rear - quelen + m ) % m27.          B        /     

17、;     A     F            /            E   G          /       

18、0; C                     D28. 3個: a 、 bce、dfg29. 我們知道，對n個關(guān)鍵自序列進行一趟快速排序，要進行n-1次比較，也就是基準和其他n-1個關(guān)鍵字比較。這里要求10次，而7 - 1 + 2 * ( 3 - 1 ) = 10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分(1)4 1 3 2 6

19、5 7 或 4 1 3 7 6 5 2或 4 5 3 7 6 1 2或 4 1 3 5 6 2 7 .(2)自己列吧 :)四、算法閱讀題(本大題共4小題，每小題5分，共20分)30. (1) L=(3,7,11,14,15,20,51)(2) L=(4,7,14,20,51)(3) 在順序表L中查找數(shù)x,    找到，則刪除x，    沒找到，則在適當?shù)奈恢貌迦離，插入后，L依然有序.31. (1) FALSE /初始化為未訪問(2) DSFTree( G, p->adjvex ); /從相鄰結(jié)點往下繼續(xù)深度搜索(3) p = p->next; /下一個未訪問的相鄰結(jié)點32.(1) L = 0, 1, 2, 3, 4, 5, 6, 7 ;(2)5次33. (1) NULL