數據結構導論2017年4月真題及答案解析（02142）

數據結構導論2017年4月真題及答案解析（02142），該試卷為數據結構導論自考歷年真題試卷，包含答案及詳細解析。

一、單項選擇題(本大題共15小題。每小題2分，共30分)在每小題歹硅出的四個備選項中只有一個是符合題目要求的請將其選躦并將“答題卡”的相應代碼涂黑。錯涂、多涂或未涂均無分。

1.任意兩個結點之間都沒有鄰接關系，組織形式松散，這種組織形式稱為(　　)

A.集合
B.線性結構
C.樹形結構
D.圖結構

2.表示數據元素之間的關聯方式通常采用的存儲方式是(　　)

A.順序存儲方式和索引存儲方式
B.鏈式存儲方式和散列存儲方式
C.順序存儲方式和鏈式存儲方式
D.鏈式存儲方式和索引存儲方式

3.下面幾種算法時間復雜度階數中，最小的是(　　)

A.O(log₂n)
B.O(n)
C.O(n²)
D.O(2ⁿ)

4.雙向循環鏈表中，在指針P所指結點的后面插入一個新結點*t，正確的語句為(　　)

A.t->prior-P;

 t->next=p->next;

 p->next->prior=t;

 p->next=t;

B.t->prior=p;

 t->next=p->next;

 p->next=t;

C.t->prior-P;

  p->next->prior=t;

  t->next=p->next;

 P->next=t;

D.p->next-->prior=t;

  p->next=t;

5.棧的修改原則是(　　)

A.先進先出
B.后進先出
C.?？談t進
D.棧滿則出

6.設有一順序隊列SQ，已知尾指針rear<隊列的最大長度-1，則數據x進行入隊列操作的語句為(　　)

A.SQ.front=SQ.front+1;
B.SQ.front=SQ.rear+1;
C.SQ.front=SQ.front+1; SQ.dataF[Sq.front]=x;
D.SQ.rear=SQ.rear+1; SQ.datar[SQ.rear]=x;

7.一個數組的第一個元素的存儲地址是100，每個元素占2存儲單元，則第5個元素的存儲地址是(　　)

A.105
B.108
C.115
D.118

8.樹中葉子的度是(　　)

A.0
B.1
C.2
D.3

9.將一棵有n個結點的完全二叉樹按層編號，若編號i所對應的結點為A，且i>1，則A的雙親的編號為(　　)

A.i
B.i/2
C.
D.

10.含有100個結點的二叉樹采用二叉鏈表存儲時，空指針域NULL的個數是(　　)

A.99個
B.100個
C.101個
D.200個

11.一個具有n個頂點的有向完全圖的弧數為(　　)

A.n(n-1)/2
B.n(n-1)
C.n²/2
D.n²

12.圖的深度優先搜索遍歷類似于樹的(　　)

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

13.靜態查找表指對查找表只進行兩項操作，即(　　)

A.插入和刪除一個數據元素
B.查找表中某一元素和插入一個數據元素
C.讀取表中“特定”數據元素和刪除一個數據元素
D.查找表中某一元素和讀取表中“特定”數據元素

14.若在線性表中采用二分查找法查找元素，該線性表應該(　　)

A.元素按值有序，且采用鏈式存儲結構
B.元素按值無序，且采用鏈式存儲結構
C.元素按值有序，且采用順序存儲結構
D.元素按值無序，且采用順序存儲結構

15.下列排序方法中不穩定的是(　　)

A.冒泡排序
B.二路歸并
C.堆排序
D.直接插入排序

二、填空題(本大題共13小題，每小題2分。共26分)

11.從宏觀上看，數據、數據元素和_________反映了數據組織的三個層次。

12.線性表、棧和隊列中的元素具有相同的邏輯結構，即_________。

13.一個算法的時空性是指該算法的時間性能和_________。

14.為了便于運算的實現，在單鏈表的第一個結點之前增設一個類型相同的結點，稱之為_________。

15.假設一個8階的上三角矩陣A按照列優先順序壓縮存儲在一維數組8中，則B數組的大小應為_________。

16.在棧中，允許進行插入和刪除操作的一端稱為_________。

17.即使輸入非法數據，算法也能適當地做出反應或進行處理，不會產生預料不到的運行結果， 這種評價算法好壞的因素稱為_________。

18.設棧S的初始狀態為空，若元素a，b，C，d依次進棧，得到的出棧序列是c，d，b，a，則棧的容量至少是_________。

19.若一棵完全二叉樹有14個結點，則它的深度為_________。

110.樹的雙親表示法由一個一維數組構成，數組的每個分量包含_________和雙親域兩個域。

111.如果包含n個頂點的連通圖G的一個子圖G’的邊數大于n-1，則G’中一定有_________。

112.在含有9個元素的有序表(2，4，12，18，23，37，49，51，68)中二分查找關鍵字(關鍵字即為數據元素的值)為37的元素時，所需進行的比較次數為_________次。

113.從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為_________排序法。

三、應用題(本大題共5小題。每小題6分，共30分)

21.設A、B、C、D、E五個元素依次進棧(進棧后可立即出棧)，問能否得到下列序列：(1)A，B，C，D，E; (2)A，C，E，B，D若能得到，剛給出該序列的操作過程(用push(A)表示A進棧，pop(A)表示A出棧);若不能，則說明理由。

22.已知一棵二叉樹的先序遍歷結果為ABDCEF，中序遍歷結果為DBAECF，試畫出這棵二叉樹，并寫出這棵二叉樹的后序遍歷序列。

23.畫出題31圖所示森林經轉換后所對應的二叉樹。

24.已知如題 32 圖所示的無向帶權圖，請從結點 A 出發，用普里姆(Prim)算法求其最小生成樹，并畫出過程示意圖。

25.將一組鍵值 {83，69，41，22，15，33，8，76} 應用二路歸并排序算法從小到大排序，試寫出各趟排序的結果。

四、算法設計題(本大題共2小題，每小題7分。共14分)

31.設計一個算法實現以下功能：在整型數組A[n]中查找值為k的元素，若找到，貝!1輸出其位置i(0≤i≤n-1)，否則輸出-1作為標志。

32.已知二叉鏈表的類型定義如下：typedef struct btnode{  DataType data;   struct btnode *lchild, *rchild;}*BinTree;利用二叉樹遍歷的遞歸算法，設計求二叉樹的高度的算法Height(BinTree bt)。