數(shù)據(jù)結(jié)構(gòu)-試卷資料2

試卷編號：（）卷

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

閉卷（J）、開卷（范圍）（）：考試日期：__________

一二三

題號四五六七A九十總分累分人

題分1010100簽名

“302030

軟

邂得分

刊

料

考生注意事項：1、本試卷共0頁，總分100分,考試時間120分鐘。

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

。

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

妲230

s

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

g亞A.計算方法B.排序方法

科

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

一

m2.算法的計算量的大小稱為計算的（B）。

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

3.在下面的程序段中，對x的賦值語句的頻度為（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個（C）的有限序列（n>0）o

滸

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

沖

朝5.在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：（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)隊列中用數(shù)組加0../zrl］存放隊列元素，其隊頭和隊尾指針分別為front

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

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

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

如

當(dāng)

歸7.棧和隊都是（C）

布

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

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

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

的是（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中，每一個數(shù)組元素/占用3個存儲字，行下標(biāo)/從1到8,

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

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

A80B100C240D270

11.若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點

個數(shù)是（B）

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

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

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

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

長度為（B）

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

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

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

15.采用順序查找方法查找長度為n的順序表時，搜索成功的平均搜索長度為

（D）。

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

二、判斷題（每題1分，共10分）得分評閱人

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

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

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

4.棧和隊列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健＃╒）

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

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

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

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

9.任何有向圖的結(jié)點都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃ㄒ弧＃╔）

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

得分評閱人

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

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

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

移動n-i+1個元素o

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

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

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

6.一棵具有257個結(jié)點的完全二叉樹，它的深度為」。

7.一棵完全二叉樹有900個結(jié)點，則共有450個葉子結(jié)點。

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

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

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

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

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

得分評閱人

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

1.請讀下列程序，該程序是在單鏈表中刪除一個結(jié)點的算法,

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

voiddemo2(LinkListhead,ListNode*p)

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

ListNode*q=head;

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

if(!q)Errornotinhead");

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

free(p);(2分)

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

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

列（2分）。

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

這棵二叉樹的后序遍歷序列為：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.將下面的森林變換成二叉樹（6分）。

https:〃/linraise/aiticle/details/11745559

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

1）寫出它的鄰接矩陣.（2分）

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

參考答案：鄰接矩陣為:

ns5000000oo

區(qū)03120010oc

5300015oo7

0012oc00062

00oc150000000

0010006oc09

0000720090

（2分）

最小生成樹為:

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）這個工程最早可能在什么時間結(jié)束和關(guān)鍵路徑。（2分）

（3）求每個事件的最早開始時間Ve[i]和最遲開始時間（2分）

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

①③