《數(shù)據(jù)結(jié)構(gòu)》試題及答案（A卷）

《數(shù)據(jù)結(jié)構(gòu)》考試試卷（A卷）

班級：姓名：學(xué)號：分?jǐn)?shù)：

題號二三四五七八九十總分

得分

評卷

人

單項(xiàng)選擇題（每題2分，共30分）

（1）一個(gè)棧的入棧序列為1234,以下出棧序列不可能得到的是（）

A.1324B.2341

C.4312D.3421

（2）若一個(gè)二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)為（）

A.9B.10C.11D.不確定

（3）鏈?zhǔn)浇Y(jié)構(gòu)線性表的特點(diǎn)是：（）

A.便于隨機(jī)存取B.花費(fèi)的存儲空間比順序結(jié)構(gòu)少

C.便于插入和刪除1）.元素的物理順序與邏輯順序一致

（4）一個(gè)二叉樹的前序遍歷序?yàn)锳BCDEFG,則中序遍歷序可能是：（）

A.CABDEFGB.ABCDEFGC.DACEFBGD.EABCDFG

（5）樹最適合用來表示（）。

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)

（6）下列有關(guān)圖遍歷的說法中不正確的是：（）

A.連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程。

B.圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征。

C.非連通圖不能用深度優(yōu)先搜索法。

D.圖的遍歷要求每一頂點(diǎn)僅被訪問一次。

（7）若已知待排序序列基本有序，則效率最高的排序方法是：（）

A.直接插入排序B.直接選擇排序

C.快速排序D.歸并排序

（8）對一棵完全二叉樹按層次遍歷序進(jìn)行遞增編號，根結(jié)點(diǎn)編號為1,那么編號為49的結(jié)點(diǎn)的

左子的編號是：（）

A.98B.99C.50D.48

（9）下列序列中不符合堆的定義的是：（）

A.acdghmpqrx

B.acmdhpxgor

C.adprcqxmhg

D.adcmpghxrq

do）下列排序方法中，相同關(guān)鍵字元素的順序不會被改變的排序方法是：（）

A.希爾排序法B.堆排序法C.快速排序D.歸并排序法

（11）在有n個(gè)葉結(jié)點(diǎn)的哈夫曼樹上，結(jié)點(diǎn)總數(shù)為：（）

A.2nB.2n+lC.2nTD.不確定

（12）對于關(guān)鍵字值序列（12、13、11、18、60、15、7、18、25、100）建堆,調(diào)整的起點(diǎn)是:（）

A.100B.12C.60D.15

（13）下列關(guān)鍵字序列中，是執(zhí)行完一趟快速排序后得到的序列的是：（）

A.[da,ax,eb,de,bb]ff[ha,gc]B.[cd,eb,ax,da]ff[ha,gc,bb]

C.[gc,ax,eb,cd,bb]ff[da,ha]D.[ax,bb,cd,da]ff[eb,gc,ha]

（14）若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹

是：（）

A.二叉排序樹B.平衡二叉樹C.堆D.哈夫曼樹

（15）在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并己知A的左

孩子的平衡因子為0右孩子的平衡因子為1，則應(yīng)采取的調(diào)整型是：（）

A.LLB.LRC.RLD.RR

填空題（每題2分，共20分）

（1）通常從四個(gè)方面評價(jià)算法的質(zhì)量：、、和

（2）若用鏈表存儲一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指

針。在這種存儲結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有個(gè)指針域，其中有個(gè)指針域

是存放了地址，有個(gè)指針是空指針。

（3）A0V網(wǎng)是一種的圖。

(4)在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有

向完全圖中，包含有________條邊。

三.判斷題(每題2分，共30分)

(1)由二叉樹的前序和后序遍歷序可以推導(dǎo)出其中序遍歷序。()

(2)線性表的邏輯順序和物理順序總是一致的。()

(3)有向圖的鄰接表結(jié)構(gòu)比鄰接矩陣結(jié)構(gòu)要節(jié)省空間。()

(4)棧和隊(duì)列都是限制了讀寫操作的線性表，只是所施加的限制不同。()

(5)大頂堆(降序堆)是根結(jié)點(diǎn)大于其他所有結(jié)點(diǎn)的完全二叉樹。()

(6)連通圖從任意頂點(diǎn)出發(fā)進(jìn)行一趟深度優(yōu)先遍歷，可以訪問到圖中的所有頂點(diǎn)。()

(7)用二叉鏈結(jié)構(gòu)存儲的--棵n個(gè)結(jié)點(diǎn)的二叉樹上，有n+1個(gè)空鏈。()

(8)二路歸并排序的核心操作是將兩個(gè)有序序列歸并為一個(gè)有序序列。()

(9)設(shè)只有根結(jié)點(diǎn)的二叉樹高度為1,則高度為h的二叉樹，至多有2回個(gè)結(jié)點(diǎn).()

(10)遞歸形式的代碼一定可以用非遞歸的形式來實(shí)現(xiàn)。()

(11)穩(wěn)定排序法可以保證排序的效率，不穩(wěn)定排序法不能保證排序的效率。()

(12)鄰接矩陣所需存儲空間大小只與結(jié)點(diǎn)數(shù)有關(guān)，與弧的個(gè)數(shù)無關(guān)。()

(13)二叉樹中，具有兩個(gè)子結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)最多只可能有一個(gè)子結(jié)點(diǎn)。()

(14)若一棵二叉樹的左右子樹都是平衡二叉樹，則該二叉樹亦為平衡二叉樹。()

(15)折半查找法只適用于順序結(jié)構(gòu)的線性表。()

四.(共10分)請畫出下圖的鄰接矩陣(5分)和鄰接表(5分)。

五.已知某工程包括多個(gè)子項(xiàng)目，某些子項(xiàng)目可能存在前期子項(xiàng)目，也就是說，只有當(dāng)前期子

項(xiàng)目都完成后，該子項(xiàng)目才能開始。下面給出各子項(xiàng)目的工期，以及各子項(xiàng)目的前期子項(xiàng)目。

請計(jì)算總工期的下限，以及哪些子項(xiàng)目是影響總工期的關(guān)鍵子項(xiàng)目，寫出計(jì)算過程，并簡要說

明計(jì)算過程。（共10分）

子項(xiàng)目名稱子項(xiàng)目工期前期子項(xiàng)目

A55

B90

C16B

D61A、C

E11B

F80B

G76F

H2D、E

《數(shù)據(jù)結(jié)構(gòu)》考試參考答案（A卷）

題號—二三四五六七八九總分

得分3020301010100

一.單項(xiàng)選擇題(每題2分，共30分)

(1)C(2)C(3)C(4)B(5)C

(6)C(7)A(8)A(9)C(10)D

(11)C(12)C(13)A(14)C(15)C

二.填空題(每空2分，共20分)

(1)正確性易讀性強(qiáng)壯性高效率

(2)2nn_ln+1

(3)有向無回路

(4)n(n-l)/2n(n-l)

三.判斷題(每題2分，共30分)

(1)N(2)N(3)N(4)Y(5)N

(6)Y(7)Y(8)Y(9)N(10)Y

(11)N(12)Y(13)Y(14)N(15)Y

四.請畫出下圖的鄰接矩陣和鄰接表（共10分）。

（1）（5分）鄰接矩陣如下所示：

"01110"

10101

11011

10101

01110

（2）（5分）鄰接表如下所示:

五、（共10分）

由表可知A0E網(wǎng)如下:

計(jì)算拓?fù)湫颉e、vl如下:

拓?fù)湫?21345

ve0