數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年4月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年4月真題及答案解析（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

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

1.任意兩個(gè)結(jié)點(diǎn)之間都沒(méi)有鄰接關(guān)系，組織形式松散，這種組織形式稱(chēng)為(　　)

A.集合
B.線(xiàn)性結(jié)構(gòu)
C.樹(shù)形結(jié)構(gòu)
D.圖結(jié)構(gòu)

2.表示數(shù)據(jù)元素之間的關(guān)聯(lián)方式通常采用的存儲(chǔ)方式是(　　)

A.順序存儲(chǔ)方式和索引存儲(chǔ)方式
B.鏈?zhǔn)酱鎯?chǔ)方式和散列存儲(chǔ)方式
C.順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式
D.鏈?zhǔn)酱鎯?chǔ)方式和索引存儲(chǔ)方式

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

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

4.雙向循環(huán)鏈表中，在指針P所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t，正確的語(yǔ)句為(　　)

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.先進(jìn)先出
B.后進(jìn)先出
C.?？談t進(jìn)
D.棧滿(mǎn)則出

6.設(shè)有一順序隊(duì)列SQ，已知尾指針rear<隊(duì)列的最大長(zhǎng)度-1，則數(shù)據(jù)x進(jìn)行入隊(duì)列操作的語(yǔ)句為(　　)

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.一個(gè)數(shù)組的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素占2存儲(chǔ)單元，則第5個(gè)元素的存儲(chǔ)地址是(　　)

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

8.樹(shù)中葉子的度是(　　)

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

9.將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，若編號(hào)i所對(duì)應(yīng)的結(jié)點(diǎn)為A，且i>1，則A的雙親的編號(hào)為(　　)

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

10.含有100個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存儲(chǔ)時(shí)，空指針域NULL的個(gè)數(shù)是(　　)

A.99個(gè)
B.100個(gè)
C.101個(gè)
D.200個(gè)

11.一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為(　　)

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

12.圖的深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的(　　)

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

13.靜態(tài)查找表指對(duì)查找表只進(jìn)行兩項(xiàng)操作，即(　　)

A.插入和刪除一個(gè)數(shù)據(jù)元素
B.查找表中某一元素和插入一個(gè)數(shù)據(jù)元素
C.讀取表中“特定”數(shù)據(jù)元素和刪除一個(gè)數(shù)據(jù)元素
D.查找表中某一元素和讀取表中“特定”數(shù)據(jù)元素

14.若在線(xiàn)性表中采用二分查找法查找元素，該線(xiàn)性表應(yīng)該(　　)

A.元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
B.元素按值無(wú)序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
C.元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)
D.元素按值無(wú)序，且采用順序存儲(chǔ)結(jié)構(gòu)

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

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

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

11.從宏觀上看，數(shù)據(jù)、數(shù)據(jù)元素和_________反映了數(shù)據(jù)組織的三個(gè)層次。

12.線(xiàn)性表、棧和隊(duì)列中的元素具有相同的邏輯結(jié)構(gòu)，即_________。

13.一個(gè)算法的時(shí)空性是指該算法的時(shí)間性能和_________。

14.為了便于運(yùn)算的實(shí)現(xiàn)，在單鏈表的第一個(gè)結(jié)點(diǎn)之前增設(shè)一個(gè)類(lèi)型相同的結(jié)點(diǎn)，稱(chēng)之為_(kāi)________。

15.假設(shè)一個(gè)8階的上三角矩陣A按照列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組8中，則B數(shù)組的大小應(yīng)為_(kāi)________。

16.在棧中，允許進(jìn)行插入和刪除操作的一端稱(chēng)為_(kāi)________。

17.即使輸入非法數(shù)據(jù)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生預(yù)料不到的運(yùn)行結(jié)果， 這種評(píng)價(jià)算法好壞的因素稱(chēng)為_(kāi)________。

18.設(shè)棧S的初始狀態(tài)為空，若元素a，b，C，d依次進(jìn)棧，得到的出棧序列是c，d，b，a，則棧的容量至少是_________。

19.若一棵完全二叉樹(shù)有14個(gè)結(jié)點(diǎn)，則它的深度為_(kāi)________。

110.樹(shù)的雙親表示法由一個(gè)一維數(shù)組構(gòu)成，數(shù)組的每個(gè)分量包含_________和雙親域兩個(gè)域。

111.如果包含n個(gè)頂點(diǎn)的連通圖G的一個(gè)子圖G’的邊數(shù)大于n-1，則G’中一定有_________。

112.在含有9個(gè)元素的有序表(2，4，12，18，23，37，49，51，68)中二分查找關(guān)鍵字(關(guān)鍵字即為數(shù)據(jù)元素的值)為37的元素時(shí)，所需進(jìn)行的比較次數(shù)為_(kāi)________次。

113.從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱(chēng)為_(kāi)________排序法。

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

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

22.已知一棵二叉樹(shù)的先序遍歷結(jié)果為ABDCEF，中序遍歷結(jié)果為DBAECF，試畫(huà)出這棵二叉樹(shù)，并寫(xiě)出這棵二叉樹(shù)的后序遍歷序列。

23.畫(huà)出題31圖所示森林經(jīng)轉(zhuǎn)換后所對(duì)應(yīng)的二叉樹(shù)。

24.已知如題 32 圖所示的無(wú)向帶權(quán)圖，請(qǐng)從結(jié)點(diǎn) A 出發(fā)，用普里姆(Prim)算法求其最小生成樹(shù)，并畫(huà)出過(guò)程示意圖。

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

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

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

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