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

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

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

1.在數(shù)據(jù)的邏輯結(jié)構(gòu)中，樹結(jié)構(gòu)和圖結(jié)構(gòu)都是(　　)

A.非線性結(jié)構(gòu)
B.線性結(jié)構(gòu)
C.動態(tài)結(jié)構(gòu)
D.靜態(tài)結(jié)構(gòu)

2.在一個長度為n的順序表中插入一個元素的算法的時間復雜度為(　　)

A.O(1)
B.O( )
C.O(n)

D.

3.指針p1和p2分別指向兩個無頭結(jié)點的非空單循環(huán)鏈表中的尾結(jié)點，要將兩個鏈表鏈接成一個新的單循環(huán)鏈表，應(yīng)執(zhí)行的操作為(　　)

A.p1->next=p2->next;p2->next-=p1->next;
B.p2->next-=p1->next;p1->next-=p2->next;
C.p=p2->next;p1 ->next-=p;p2->next=p1->next;
D.p=p1->next;p1->next=p2->next;p2->next-=p;

4.設(shè)棧的初始狀態(tài)為空，入棧序列為1,2,3,4,5,6，若出棧序列為2,4,3,6,5,1，則操作過程中棧中元素個數(shù)最多時為(　　)

A.2個
B.3個
C.4個
D.6個

5.隊列的特點是(　　)

A.允許在表的任何位置進行插入和刪除
B.只允許在表的一端進行插入和刪除
C.允許在表的兩端進行插入和刪除
D.只允許在表的一端進行插入，在另一端進行刪除

6.一個鏈串的結(jié)點類型定義為 (　　)#define NodeSize 6typedef struct node{char data[NodeSize];struct node*next;}LinkStrNode;如果每個字符占1個字節(jié)，指針占2個字節(jié)，該鏈串的存儲密度為(　　)

A.1/3
B.1/2
C.2/3
D.3/4

7.廣義表A=(a，B，(a，B，(a，B，……)))的長度為(　　)

A.1
B.2
C.3
D.無限值

8.已知10x12的二維數(shù)組A，按“行優(yōu)先順序”存儲，每個元素占1個存儲單元，已知A[1] [1]的存儲地址為420，則A[5][5]的存儲地址為(　　)

A.470
B.471
C.472
D.473

9.在一棵二叉樹中，度為2的結(jié)點數(shù)為15，度為1的結(jié)點數(shù)為3，則葉子結(jié)點數(shù)為(　　)

A.12
B.16
C.18
D.20

10.在帶權(quán)圖的最短路徑問題中，路徑長度是指(　　)

A.路徑上的頂點數(shù)
B.路徑上的邊數(shù)
C.路徑上的頂點數(shù)與邊數(shù)之和
D.路徑上各邊的權(quán)值之和

11.具有n個頂點，e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為(　　)

A.e
B.2e

C.

D.

12.要以O(shè)(n log n)時間復雜度進行穩(wěn)定的排序，可用的排序方法是(　　)

A.歸并排序
B.快速排序
C.堆排序
D.冒泡排序

13.若希望在1000個無序元素中盡快求得前10個最大元素，應(yīng)借用(　　)

A.堆排序
B.快速排序
C.冒泡排序
D.歸并排序

14.對有序表進行二分查找成功時，元素比較的次數(shù)(　　)

A.僅與表中元素的值有關(guān)
B.僅與表的長度和被查元素的位置有關(guān)
C.僅與被查元素的值有關(guān)
D.僅與表中元素按升序或降序排列有關(guān)

15.散列文件是一種(　　)

A.順序存取的文件
B.隨機存取的文件
C.索引存取的文件
D.索引順序存取的文件

二、填空題(本大題共10小題，每小題2分，共20分) 請在每小題的空格中填上正確答案。錯填、不填均無分。

11.若一個算法中的語句頻度之和為 ，則該算法的漸近時間復雜度為 。

12.在單鏈表中，除了第1個元素結(jié)點外，任一結(jié)點的存儲位置均由 指示。

13.棧的修改是按 的原則進行。

14.字符串中任意個連續(xù)的字符組成的予序列稱為該串的 。

15.假設(shè)一個10階的上三角矩陣A按z…--…-順I(yè)序壓縮存儲在一維數(shù)組B中，若矩陣中的第一個元素a1，1在B中的存儲位置k=O，則元素a5，5在B中的存儲位置k=

16.在一棵具有n個結(jié)點的嚴格二叉樹中，度為1的結(jié)點個數(shù)為 。

17.對于稀疏圖，采用 表示法較為節(jié)省存儲空間。

18.在排序過程中，如果 ，則稱其為外部排序。

19.設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，12，10，78，25}，用鏈地址法構(gòu)造散列表，散列函數(shù)為h(key)=key%11，散列地址為1的鏈中有 個記錄。

110.多關(guān)鍵字文件的特點是除主文件和主索引外，還建有 。

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

21.對于下列稀疏矩陣(注：矩陣元素的行列下標均從1開始)(1)畫出三元組表;(2)畫出三元組表的行表。

22.已知一個森林的前序遍歷序列為CBADHEGF，后序遍歷序列為ABCDEFGH。(1)畫出該森林;(2)畫出該森林所對應(yīng)的二叉樹。

23.對關(guān)鍵字序列(429，653，275，897，170，908，473，256，726)進行基數(shù)排序，寫出每一趟的排序結(jié)果。

24.對下列關(guān)鍵字序列 (87，25，310，08，27，132，68，96，187，133，70，63，47，135)構(gòu)造散列表，假設(shè)散列函數(shù)為h(key)=key%13，用拉鏈法解決沖突。(1)畫出該散列表;(2)求等概率情況下查找成功的平均查找長度ASL;(3)寫出刪除值為70的關(guān)鍵字時所需進行的關(guān)鍵字比較次數(shù)。

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

31.閱讀下列算法，并回答問題：(1)假設(shè)p(3，7，7，11，20，20，20，51，51)，寫出執(zhí)行函數(shù)=f30(&L)后的L.(2)簡述f30的功能。

32.閱讀下列算法，并回答問題：(1)假設(shè)棧S=(3，8，6，2，5)，其中5為棧頂元素，寫出執(zhí)行函數(shù)f3l(&S)后的S;(2)簡述函數(shù)f31的功能。void f31(Stack*S){ Queue Q;InitQueue(&Q);while(!StackEmpty(S))EnQueue(&Q，Pop(&S));while(!QueueEmpty(Q))Push(&S，DeQueue(&Q));}

33.假設(shè)具有n個結(jié)點的完全二叉樹順序存儲在向量BT[ 1..n]中，閱讀下列算法，并回答問題：(1)若向量BT為：      1 2 3 4 5 6 7畫出執(zhí)行函數(shù)f32(BT，7，1)的返回結(jié)果;(2)簡述函數(shù)f32的功能。BinTree f32(DataType BT[]，intn，inti){BinTree p;if(i>n)return NULL;p=(BinTNode*)malloc(sizeof(BinTNode));p->data=BT[i];p->lchild=f32(BT,n，i*2);p->rchild=f32(BT，n，i*2+1);return p;}

34.已知有向圖的鄰接表和鄰接矩陣定義如下：#define MaxNum 50 圖的最大頂點數(shù)typedef struct node{int adjvex; ∥鄰接點域struct node半next; ∥鏈指針域}EdgeNode; ∥邊表結(jié)點結(jié)構(gòu)typedef struct{char vertex; ∥頂點域EdgeNode *frrstedge; ∥邊表頭指針}VertexNode; ∥頂點表結(jié)點結(jié)構(gòu)typedef struct{VertexNode adjlist[MaxNum]; ∥鄰接表int n，e; ∥圖中當前頂點數(shù)和邊數(shù)}ALGraph; ∥鄰接表描述的圖typedef struct{char vertex[MaxNum]; ∥頂點表int adjmatrix[MaxNum][MaxNum]; ∥鄰接矩陣int n，e; ∥圖中當前頂點數(shù)和邊數(shù)}AMGraph; ∥鄰接矩陣描述的圖下列算法是將鄰接表描述的圖Gl改為鄰接矩陣描述的圖G2趁，在空白處填上適當內(nèi) 容使算法完整： 

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

41.設(shè)順序表L是一個遞增有序表。編寫算法，要求利用二分查找法確定插入位置，將元素x插入到L中，使L保持有序。