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

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

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

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

1.下列選項(xiàng)中，屬于邏輯結(jié)構(gòu)的是(　　)

A.線性表
B.鏈表
C.順序棧
D.循環(huán)隊(duì)列

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

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

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

A.采用順序存儲時(shí)一定相鄰，采用鏈?zhǔn)酱鎯r(shí)也一定相鄰
B.采用順序存儲時(shí)一定相鄰，采用鏈?zhǔn)酱鎯r(shí)不一定相鄰
C.采用順序存儲時(shí)不一定相鄰，采用鏈?zhǔn)酱鎯r(shí)一定相鄰
D.采用順序存儲時(shí)不一定相鄰，采用鏈?zhǔn)酱鎯r(shí)也不一定相鄰

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

A.先進(jìn)先出，先進(jìn)后出
B.先進(jìn)先出，先進(jìn)先出
C.先進(jìn)后出，先進(jìn)先出
D.先進(jìn)后出，先進(jìn)后出

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

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.設(shè)深度為k(k≥1)的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則該二叉樹中所包含的結(jié)點(diǎn)數(shù)至少是(　　)

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

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

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

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

A.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1
B.所有頂點(diǎn)的度之和為偶數(shù)
C.度為1的頂點(diǎn)個(gè)數(shù)一定為偶數(shù)
D.度為1的頂點(diǎn)個(gè)數(shù)一定為奇數(shù)

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

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

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

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

12.下列排序方法中，時(shí)間復(fù)雜度與數(shù)據(jù)初始狀態(tài)相關(guān)的是(　　)

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

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

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

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

A.根結(jié)點(diǎn)最多有m棵子樹
B.所有葉結(jié)點(diǎn)都在同一層上
C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列
D.葉結(jié)點(diǎn)之間通過指針鏈接

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

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

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

11.著名計(jì)算機(jī)科學(xué)家沃思曾指出：算法+_________=程序。

12.描述算法占內(nèi)存空間效率的術(shù)語是_________。

13.設(shè)順序表第1個(gè)元素的存儲地址是2000，每個(gè)數(shù)據(jù)元素占4個(gè)字節(jié)，則第41個(gè)元素的存儲地址是_________。

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

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

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

17.除鄰接表外，圖的另一種鏈?zhǔn)酱鎯Ψ绞绞莀________。

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

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

110.若構(gòu)造一顆具有n個(gè)結(jié)點(diǎn)的二叉排序樹，在最壞情況下，其深度為_________。

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

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

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

23.將百分制成績分成五個(gè)等級，已知成績的對應(yīng)關(guān)系及分布情況如下表所示：請根據(jù)最優(yōu)二叉樹的基本原理，采用類C語言，描述你所設(shè)計(jì)的成績判定過程。

24.給定有向無環(huán)圖G如題29圖所示，寫出G的5種不同的拓?fù)渑判蛐蛄小?img src="https://status.shangxueba.com/exam/2019-03-21/922033321238178.png" width="188" height="162"/>

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

31.請寫出下列程序段的輸出結(jié)果。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 );輸出結(jié)果

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

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

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

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

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