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

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

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

1.下列選項中，屬于邏輯結構的是(　　)

A.線性表
B.鏈表
C.順序棧
D.循環隊列

2.下列關于算法輸出的敘述中，正確的是(　　)

A.算法一定沒有輸出
B.算法可以沒有輸出
C.算法至少有一個輸出
D.算法必須有多個輸出

3.針對線性表邏輯上相鄰的兩個元素，下列敘述中，正確的是(　　)

A.采用順序存儲時一定相鄰，采用鏈式存儲時也一定相鄰
B.采用順序存儲時一定相鄰，采用鏈式存儲時不一定相鄰
C.采用順序存儲時不一定相鄰，采用鏈式存儲時一定相鄰
D.采用順序存儲時不一定相鄰，采用鏈式存儲時也不一定相鄰

4.隊列和棧的特征分別是(　　)

A.先進先出，先進后出
B.先進先出，先進先出
C.先進后出，先進先出
D.先進后出，先進后出

5.在二維數組a[8][10]中，每個數組元素a[i][j]占用3個存儲空間，所有數組元素存放在一個連續的存儲空間中，則該數組需要的存儲空間個數是(　　)

A.80
B.100
C.240
D.270

6.廣義表A=(a，(b，e，(e，f，g，h)))的表長是(　　)

A.2
B.3
C.4
D.7

7.設深度為k(k≥1)的二叉樹中只有度為0和度為2的結點，則該二叉樹中所包含的結點數至少是(　　)

A.k+1
B.2k+1
C.2k-1
D.2k

8.下列選項中，可以唯一確定一棵二叉樹的兩種遍歷序列是(　　)

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

9.下列關于無向連通圖特性的敘述中，正確的是(　　)

A.邊數大于頂點個數減1
B.所有頂點的度之和為偶數
C.度為1的頂點個數一定為偶數
D.度為1的頂點個數一定為奇數

10.下列關于無向圖廣度優先搜索序列的敘述中，正確的是(　　)

A.廣度優先搜索序列只有一種
B.廣度優先搜索序列可能不存在
C.廣度優先搜索序列可能有多種
D.廣度優先搜索序列一定有多種

11.設帶權連通圖G中含有n(n>1)個頂點e條邊。下列關于G的最小生成樹的敘述中， 正確的是(　　)

A.生成樹中一定含有權值最小的e條邊
B.生成樹中可能含有權值最小的n+1條邊
C.生成樹中一定含有權值最小的n條邊
D.生成樹中可能含有權值最小的n-1條邊

12.下列排序方法中，時間復雜度與數據初始狀態相關的是(　　)

A.直接選擇排序
B.快速排序
C.基數排序
D.箱排序

13.下列排序方法中，效率較高且穩定的方法是(　　)

A.直接插入排序
B.冒泡排序
C.快速排序
D.歸并排序

14.下列敘述中，不符合m階B樹定義的是(　　)

A.根結點最多有m棵子樹
B.所有葉結點都在同一層上
C.各結點內關鍵字均升序或降序排列
D.葉結點之間通過指針鏈接

15.假設散列表長m=11，散列函數H(key)=key%11。表中已有4個結點：H(39)=6，H(41)=8，H(53)=9，H(76)=10，占了4個位置，其余位置為空。現采用線性探查法處理沖突，存儲關鍵字85時需要探查的次數是(　　)

A.2
B.3
C.4
D.5

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

11.著名計算機科學家沃思曾指出：算法+_________=程序。

12.描述算法占內存空間效率的術語是_________。

13.設順序表第1個元素的存儲地址是2000，每個數據元素占4個字節，則第41個元素的存儲地址是_________。

14.棧和隊列是操作受限的線性表，其中只能在表的一端進行插入或刪除操作的是_________。

15.廣義表A=(a,(b,c,(e,f,g,h)))，tail(A)=_________。

16.一顆左子樹為空的二叉樹在中序線索化后，其空指針域的個數為_________。

17.除鄰接表外，圖的另一種鏈式存儲方式是_________。

18.含n個頂點e條邊的帶權連通圖G，采用迪杰斯特拉算法得到的某個給定頂點到其余各頂點最短路徑的條數是_________。

19.DFS算法的中文名稱是_________。

110.若構造一顆具有n個結點的二叉排序樹，在最壞情況下，其深度為_________。

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

21.26.設Q是有N個存儲空間的循環隊列，初始狀態front=rear=0，約定指針rear指向的單元始終為空，回答下列問題。(1)寫出數據元素X入隊的語句序列;(2)寫出隊首元素出隊并保存到變量Y的語句序列;(3)給出計算隊列長度L的表達式。

22.已知稀疏矩陣M如下，采用三元組表存儲。請回答下列問題。(1)給出三元組表的類型定義。(2)畫出矩陣M按行優先的三元組表。

23.將百分制成績分成五個等級，已知成績的對應關系及分布情況如下表所示：請根據最優二叉樹的基本原理，采用類C語言，描述你所設計的成績判定過程。

24.給定有向無環圖G如題29圖所示，寫出G的5種不同的拓撲排序序列。

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

31.請寫出下列程序段的輸出結果。Seqstack S; //初始化棧S char x, y;X='L'; y='O';Push(s, x); Push(S,x);Push(s, y); x=Pop(S);Push(S, 'E'); Push(s,x);x=Pop( S ); Push(S,'H');while(! StackEmpty (s)) {y=Pop(S);putchar( y );}putchar( x );輸出結果

32.帶頭結點的單鏈表定義如下，其中freq域記錄本結點被訪問的次數，初值為0，單鏈表始終以freq值從大到小有序。函數f31完成的功能是：查找給定關鍵字所在結點，若查找成功，則該結點的freq域加1，并按freq值調整結r旨位置。請將空白處(1)～(3)補充完整。在答題卡上作答。

33.閱讀程序，回答下列問題。若順序表R的元素個數n=6，關鍵字依次為{41，82，75，24，8，16}，則：(1)寫出函數f32執行后的輸出結果：(2)函數f32的功能是什么?

34.已知二叉樹的二叉鏈表類型定義如下：typedef struct node {        char data;        struct node *lchild, *rchild;}BinTNode;typedef BinTNode * BinTree;函數f33的功能是將二叉樹Bt變換為它的鏡像。鏡像的含義如題33圖所示請將空白處(1)~(4)填寫適當內容,使其完成指定功能,請在答題卡上作答。

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

41.已知帶頭結點的單鏈表類型定義如下：typedef struct node {        int data;         struct node *next;} ListNode;typedef ListNode *List_ptr;請編寫函數InvertList實現單鏈表的原地逆轉。要求在原鏈表上進行逆轉，不允許申請新的表結點空間。函數原型如下List_ptr InvertList( List_ptr head); //原地逆轉單鏈表head