?數(shù)據(jù)結(jié)構(gòu)自考2012年10月真題

數(shù)據(jù)結(jié)構(gòu)自考2012年10月真題及答案解析

本試卷為單選題型，填空題，算法閱讀，算法設(shè)計(jì)等題型。

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。

1.一個(gè)算法的時(shí)間耗費(fèi)的數(shù)量級(jí)稱為該算法的(　　)

A.效率
B.難度
C.可實(shí)現(xiàn)性
D.時(shí)間復(fù)雜度

2.順序表便于(　　)

A.插入結(jié)點(diǎn)
B.刪除結(jié)點(diǎn)
C.按值查找結(jié)點(diǎn)
D.按序號(hào)查找結(jié)點(diǎn)

3.設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，指針變量P指向尾結(jié)點(diǎn)的條件是(　　)

A.p->next->next==head
B.p->next==head
C.p->next->next==NULL
D.p->next==NULL

4.設(shè)以數(shù)組A[0..m-1]存放循環(huán)隊(duì)列，front指向隊(duì)頭元素，rear指向隊(duì)尾元素的下一個(gè)位置，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為(　　)

A.(rear-front+m)%m
B.rear-front+1
C.(front-rear+m)%m
D.(rear-front)%m

5.下列關(guān)于順序棧的敘述中，正確的是(　　)

A.入棧操作需要判斷棧滿，出棧操作需要判斷?？?br/>B.入棧操作不需要判斷棧滿，出棧操作需要判斷?？?br/>C.入棧操作需要判斷棧滿，出棧操作不需要判斷棧空
D.入棧操作不需要判斷棧滿，出棧操作不需要判斷棧空

6.A是一個(gè)10×10的對(duì)稱矩陣，若采用行優(yōu)先的下三角壓縮存儲(chǔ)，第一個(gè)元素,0的存儲(chǔ)地址為1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則的地址為(　　)

A.25
B.26
C.33
D.34

7.樹的后序遍歷等價(jià)于該樹對(duì)應(yīng)二叉樹的(　　)

A.層次遍歷
B.前序遍歷
C.中序遍歷
D.后序遍歷

8.使用二叉線索樹的目的是便于(　　)

A.二叉樹中結(jié)點(diǎn)的插入與刪除
B.在二叉樹中查找雙親
C.確定二叉樹的高度
D.查找一個(gè)結(jié)點(diǎn)的前趨和后繼

9.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖邊的數(shù)目最多為(　　)

A.n-1
B.n(n-1)/2
C.n(n+1)/2

D.

10.可進(jìn)行拓?fù)渑判虻膱D只能是(　　)

A.有向圖
B.無向圖
C.有向無環(huán)圖
D.無向連通圖

11.下列排序方法中穩(wěn)定的是(　　)

A.直接插入排序
B.直接選擇排序
C.堆排序
D.快速排序

12.下列序列不為堆的是(　　)

A.75,45,65,30,15,25
B.75,65,45,30,25,15
C.75,65,30,15,25,45
D.75,45,65,25,30,15

13.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須是(　　)

A.順序存儲(chǔ)
B.鏈?zhǔn)酱鎯?chǔ)
C.順序存儲(chǔ)且按關(guān)鍵字有序
D.鏈?zhǔn)酱鎯?chǔ)且按關(guān)鍵字有序

14.分別用以下序列生成二叉排序樹，其中三個(gè)序列生成的二叉排序樹是相同的，不同的序列是(　　)

A.(4,1,2,3,5)
B.(4,2,3,1,5)
C.(4,5,2,1,3)
D.(4,2,1,5,3)

15.下列關(guān)于m階B樹的敘述中，錯(cuò)誤的是(　　)

A.每個(gè)結(jié)點(diǎn)至多有m個(gè)關(guān)鍵字
B.每個(gè)結(jié)點(diǎn)至多有m棵子樹
C.插入關(guān)鍵字時(shí)，通過結(jié)點(diǎn)分裂使樹高增加
D.刪除關(guān)鍵字時(shí)通過結(jié)點(diǎn)合并使樹高降低

二、填空題(本大題共10小題，每小題2分，共20分) 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。

11.數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的______結(jié)構(gòu)。

12.在線性表中，表的長(zhǎng)度定義為______。

13.用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?、2、3、4，為了得到1、3、4、2的出棧順序，相應(yīng)的S和X的操作序列為______。

14.在二叉樹中，帶權(quán)路徑長(zhǎng)度最短的樹稱為______。

15.已知廣義表G，head(G)與tail(G)的深度分別為4和6，則G的深度是______。

16.一組字符(a,b,c,d)在文中出現(xiàn)的次數(shù)分別為(7，6，3，5)，字符"d"的哈夫曼編碼的長(zhǎng)度為______。

17.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要______條邊。

18.直接選擇排序算法的時(shí)間復(fù)雜度是______。

19.對(duì)于長(zhǎng)度為81的表，若采用分塊查找，每塊的最佳長(zhǎng)度為______。

110.用二叉鏈表保存有n個(gè)結(jié)點(diǎn)的二叉樹，則結(jié)點(diǎn)中有______個(gè)空指針域。

三、解答題(本大題共4小題，每小題5分，共20分)

21.假設(shè)Q是一個(gè)具有11個(gè)元素存儲(chǔ)空間的循環(huán)隊(duì)列(隊(duì)尾指針指向隊(duì)尾元素的下一 個(gè)位置，隊(duì)頭指針指向隊(duì)頭元素)，初始狀態(tài)Q.front=Q.rear=0;寫出依次執(zhí)行 下列操作后頭、尾指針的當(dāng)前值。a,b,c,d,e,f入隊(duì)，a,b,c,d出隊(duì); (1) Q.front=______;Q.rear=______。g,h,i,j,k,l入隊(duì)，e,f,g,h出隊(duì); (2) Q.front=______;Q.rear=______。M,n,o,P入隊(duì)，i,j,k,l,m出隊(duì); (3) Q.front=______;Q.rear=______。

22.已知一個(gè)無向圖如題27圖所示，以①為起點(diǎn)，用普里姆(Prim)算法求其最小生成樹，畫出最小生成樹的構(gòu)造過程。

23.用歸并排序法對(duì)序列 (98,36,-9,0,47,23,1,8)進(jìn)行排序，問：(1)一共需要幾趟歸并可完成排序。(2)寫出第一趟歸并后數(shù)據(jù)的排列次序。

24.一組記錄關(guān)鍵字(55,76,44,32,64,82,20,16,43)，用散列函數(shù)H(key)=key%11將記錄 散列到散列表HT[0..12]中去，用線性探測(cè)法解決沖突。 (1)畫出存入所有記錄后的散列表。 (2)求在等概率情況下，查找成功的平均查找長(zhǎng)度。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)

31.順序表類型定義如下：# define ListSize 100typedef struct {int data[ListSize];int length; }SeqList;閱讀下列算法，并回答問題：(1)若L->data 中的數(shù)據(jù)為(22,4,63,0,15,29,34,42,3),則執(zhí)行上述算法后L->data中的數(shù)據(jù)以及L->length的值各是什么?(2)該算法的功能是什么?

32.有向圖的鄰接矩陣類型定義如下：#define MVN 100 ∥ 最大頂點(diǎn)數(shù)typedef int EType; ∥ 邊上權(quán)值類型typedef struct{EType edges[MVN][MVN]; ∥ 鄰接矩陣，即邊表int n; ∥ 圖的頂點(diǎn)數(shù)｝MGraph; ∥ 圖類型例如，一個(gè)有向圖的鄰接矩陣如下所示：閱讀下列算法，并回答問題：(1)step1到step2之間的二重循環(huán)語句的功能是什么?(2)step2之后的二重循環(huán)語句的功能是什么?

33.閱讀下列算法，并回答問題：(1)這是哪一種插入排序算法?該算法是否穩(wěn)定?(2)設(shè)置r[0]的作用是什么?

34.順序表類型定義如下：(1)給出該算法的功能;(2)給出該算法的時(shí)間復(fù)雜度。

五、算法設(shè)計(jì)題(本大題共1小題，共10分)

41.二叉樹的存儲(chǔ)結(jié)構(gòu)類型定義如下typedef struct node{int data;struct node *lchild， *rchild;} BinNode;typedef BinNode *BinTree;編寫遞歸算法，求只有一個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)總數(shù)，并計(jì)算這些結(jié)點(diǎn)的數(shù)據(jù)值的和。 函數(shù)的原型為：void f34(BinTree T, int *count, int *sum) *count和*sum的初值為0。