試卷編號(hào)：（）卷

數(shù)據(jù)結(jié)構(gòu)（C）課程課程類別：必

閉卷（J）、開(kāi)卷（范圍）（）：考試日期：__________

一二三

題號(hào)四五六七A九十總分累分人

題分1010100簽名

“302030

軟

邂得分

刊

料

考生注意事項(xiàng)：1、本試卷共0頁(yè)，總分100分,考試時(shí)間120分鐘。

2、考試結(jié)束后,考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。

。

曲一、選擇題（每題分，共分）

妲230

s

i1.計(jì)算機(jī)算法指的是（C）o

g亞A.計(jì)算方法B.排序方法

科

四C.解決問(wèn)題的步驟序列D.調(diào)度方法

一

m2.算法的計(jì)算量的大小稱為計(jì)算的（B）。

wA.效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度

3.在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（C）

-s即

for（i=l;i<=n;i++）

懶

for（j=l;j<=n;j++）

哩

x+=l;

沿

寐A.0（2n）B.0（n）C.0（n2）D.0(log")

中2

器4.線性表是具有n個(gè)（C）的有限序列（n>0）o

滸

A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)

沖

朝5.在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：（B）。

KA.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;

斐C.p->next=s;p->next=s->next;D.p->next=s->next;p->next=s;

爾

&6.在循環(huán)隊(duì)列中用數(shù)組加0../zrl］存放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針?lè)謩e為front

與和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（D）。

三A.（front-rear+1）%/B.（rear-front+1）%zzz

因C.（front-rear+ni）%mD.（rear-front+ni）%m

如

當(dāng)

歸7.棧和隊(duì)都是（C）

布

而A.順序存儲(chǔ)的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)

C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)

8.某棧的輸入序列為a,b,c,d,下面的四個(gè)序列中，不可能是它的輸出序列

的是（D）o

A.a,c,b,dB.b,c,d,aC.c,d,b,aD.d,c,a,b

9.廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為(D)o

Head(Tai1(Head(Tai1(Tai1(A)))))

A.(g)B.(d)C.cD.d

10.在數(shù)組4中，每一個(gè)數(shù)組元素/占用3個(gè)存儲(chǔ)字，行下標(biāo)/從1到8,

列下標(biāo)J,從1到10。所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中，則存放該

數(shù)組至少需要的存儲(chǔ)字?jǐn)?shù)是（C）。

A80B100C240D270

11.若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)

個(gè)數(shù)是（B）

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

12.在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為（A）

A.n-1B.2n-lC.n+1D.2n+l

13.由權(quán)值分別為11,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑

長(zhǎng)度為（B）

A.24B.71C.48D.53

14.下列哪一種圖的鄰接矩陣是對(duì)稱矩陣（B）

A.有向圖B.無(wú)向圖C.A0V網(wǎng)D.AOE網(wǎng)

15.采用順序查找方法查找長(zhǎng)度為n的順序表時(shí)，搜索成功的平均搜索長(zhǎng)度為

（D）。

AnBn/2C（n-l）/2D（加1）/2

二、判斷題（每題1分，共10分）得分評(píng)閱人

1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（X）

2.線性表就是順序存儲(chǔ)的表。（X）

3.為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（V）

4.棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（V）

5.一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（X）

6.連通分量指的是有向圖中的極大連通子圖。（X）

7.深度為K的二叉樹(shù)中結(jié)點(diǎn)總數(shù)忘2--1。（V）

8.二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。（V）

9.任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃ㄒ?。（X）

10.關(guān)鍵路徑是AOE網(wǎng)中從源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑。（J）

得分評(píng)閱人

三、填空題(每題2分，共20分)

1.數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是算法的時(shí)間復(fù)雜度和度間復(fù)雜度。

2.一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素(l〈=i〈=n)之前插入一個(gè)元素時(shí)，需向后

移動(dòng)n-i+1個(gè)元素o

3.鏈接存儲(chǔ)的特點(diǎn)是利用指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。

4.INDEX('DATASTRUCTURE','STR')=5

5.兩個(gè)字符串相等的充分必要條件是兩串中對(duì)應(yīng)位置的字符相等且長(zhǎng)度也相等。

6.一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為」。

7.一棵完全二叉樹(shù)有900個(gè)結(jié)點(diǎn)，則共有450個(gè)葉子結(jié)點(diǎn)。

8.由一棵二叉樹(shù)的前序序列和中序序列唯一確定這棵二叉樹(shù)。

9.已知一無(wú)向圖G=(V,E),其中V={a,b,c,d,e)

E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)始遍歷

圖，得到的序列為abecd,則采用的是深度優(yōu)先遍歷方法。

10.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹(shù)的邊數(shù)為n-1。

得分評(píng)閱人

四、應(yīng)用題(共3。分)

1.請(qǐng)讀下列程序，該程序是在單鏈表中刪除一個(gè)結(jié)點(diǎn)的算法,

為空出的地方填上正確的語(yǔ)句。(共6分)

voiddemo2(LinkListhead,ListNode*p)

{//head是帶頭結(jié)點(diǎn)的單鏈表，刪除P指向的結(jié)點(diǎn)

ListNode*q=head;

while(q&&q->next!=p)q=q->next;(2分)

if(!q)Errornotinhead");

q->next=p->next;(2分)

free(p);(2分)

2.已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是

EBCDAFHIGJ,試畫(huà)出與其對(duì)應(yīng)的二叉樹(shù)（4分），并給出這棵二叉樹(shù)的后序遍歷序

列（2分）。

參考答案：根據(jù)前序序列和中序序列能得到唯一的二叉樹(shù)，所得二叉樹(shù)如圖：

這棵二叉樹(shù)的后序遍歷序列為：EDCBIHJGFA（2分）

https:〃/question/626936867/99883084.html?qbl=relatequestion4

&word=%D2%a%D6<%\k%O2%BB%BF%C3%B6%FE%B2%E6%CA%F7%B5%

C4%C7%B0%D0%F2%Bl%E9%CO%FA%B5%C4%BD%E1%B9%FB%CA%C7ABE

CDFGH1J%2C%2O%D6%Q0%Q0%/2%3/%E9%C0%E4%B5%C4%BD%ET%89%

FB%CA%C7EBCDAFHIGJ%

https:〃/question/94952674Jitml?qbl=relatequestion0&word=%D2

%Z)/%D6%AA%Q2%B8%BF%C3%B6%FE%32%E6%C4%/7%35%C4%C7%30%

DO%F2%B1%E9%CO%FA%B5%C4%BD%E1%B9%FB%CA%C7ABECDFGHIJ%2c

%20%D6%D0%D0%F2%Bl%E9%C0%FA%B5%C4%BD%El%B9%FB%CA%C7EB

CDAFHIGJ%2C%20%CA%D

3.將下面的森林變換成二叉樹(shù)（6分）。

https:〃/linraise/aiticle/details/11745559

4.已知帶權(quán)無(wú)向圖，求解下列問(wèn)題：

1）寫(xiě)出它的鄰接矩陣.（2分）

2）用普里姆算法求出最小生成樹(shù)（要求從龍點(diǎn)發(fā)，畫(huà)出構(gòu)造過(guò)程）。（4分）

參考答案：鄰接矩陣為:

ns5000000oo

區(qū)03120010oc

5300015oo7

0012oc00062

00oc150000000

0010006oc09

0000720090

（2分）

最小生成樹(shù)為:

https:〃/question/2138002214749093668.html?qbl=relatequestion6

&word=%D2%D1%D6%AA%B4%F8%C8%A8%CE%DE%CF%F2%CD%BC%2c

%C7%F3%BD%E2%CF%C2%Cl%D0%CE%CA%CC%E2:%201%29%D0%B4%B3

%F6%CB%FC%B5%C4%C1%DA%BD%D3%BE%D8%D5%F3.%282%B7%D6%2

9%202%29%D3%C3%C6%D5

（4分）

5.下圖所示的AOE網(wǎng)絡(luò)

（1）給出全部的拓?fù)渑判颉＃?分）

（2）這個(gè)工程最早可能在什么時(shí)間結(jié)束和關(guān)鍵路徑。（2分）

（3）求每個(gè)事件的最早開(kāi)始時(shí)間Ve[i]和最遲開(kāi)始時(shí)間（2分）

參考答案：（1）拓?fù)渑判颍?/p>

①③