數據結構自考2011年10月真題及答案解析

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

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

1.在數據的邏輯結構中，樹結構和圖結構都是(　　)

A.非線性結構
B.線性結構
C.動態結構
D.靜態結構

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

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

D.

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

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.設棧的初始狀態為空，入棧序列為1,2,3,4,5,6，若出棧序列為2,4,3,6,5,1，則操作過程中棧中元素個數最多時為(　　)

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

5.隊列的特點是(　　)

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

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

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的二維數組A，按“行優先順序”存儲，每個元素占1個存儲單元，已知A[1] [1]的存儲地址為420，則A[5][5]的存儲地址為(　　)

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

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

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

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

A.路徑上的頂點數
B.路徑上的邊數
C.路徑上的頂點數與邊數之和
D.路徑上各邊的權值之和

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

A.e
B.2e

C.

D.

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

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

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

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

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

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

15.散列文件是一種(　　)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33.假設具有n個結點的完全二叉樹順序存儲在向量BT[ 1..n]中，閱讀下列算法，并回答問題：(1)若向量BT為：      1 2 3 4 5 6 7畫出執行函數f32(BT，7，1)的返回結果;(2)簡述函數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 圖的最大頂點數typedef struct node{int adjvex; ∥鄰接點域struct node半next; ∥鏈指針域}EdgeNode; ∥邊表結點結構typedef struct{char vertex; ∥頂點域EdgeNode *frrstedge; ∥邊表頭指針}VertexNode; ∥頂點表結點結構typedef struct{VertexNode adjlist[MaxNum]; ∥鄰接表int n，e; ∥圖中當前頂點數和邊數}ALGraph; ∥鄰接表描述的圖typedef struct{char vertex[MaxNum]; ∥頂點表int adjmatrix[MaxNum][MaxNum]; ∥鄰接矩陣int n，e; ∥圖中當前頂點數和邊數}AMGraph; ∥鄰接矩陣描述的圖下列算法是將鄰接表描述的圖Gl改為鄰接矩陣描述的圖G2趁，在空白處填上適當內 容使算法完整： 

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

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