2021年1月開放教育?？茢?shù)據(jù)結(jié)構(gòu)

1月開放教誨?？啤皵?shù)據(jù)構(gòu)造”期末考試試題

一、單選題(每小題2分，共12分)

1.在一種單鏈表HL中，若要向表頭插入一種由指針p指向結(jié)點(diǎn)，則執(zhí)行()。

A.HL=psp一＞next=HL

B.p一〉next=HL；HL=p3

C.pnext=Hl；p=HL；

D.p一＞next=HL一＞next;HL一＞next=p；

2.n個(gè)頂點(diǎn)強(qiáng)連通圖中至少具有()o

A.n—1條有向邊B.n條有向邊

C.n(n—1)/2條有向邊D.n(n-l)條有向邊

3.從-一棵二叉搜索樹中查找一種元素時(shí)，其時(shí)間復(fù)雜度大體為()。

A.O(l)B.O(n)

C.O(1Ogzn)D.O(n2)

4.由權(quán)值分別為3,8,6,2,5葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它帶權(quán)途徑長(zhǎng)度為()。

A.24B.48

C.72D.53

5.當(dāng)一種作為實(shí)際傳遞對(duì)象占用存儲(chǔ)空間較大并也許需要修改時(shí)，應(yīng)最佳把它闡明為

()參數(shù)，以節(jié)約參數(shù)值傳播時(shí)間和存儲(chǔ)參數(shù)空間。

A.整形B.引用型

C.指針型D.常值引用型?

6.向一種長(zhǎng)度為n順序表中插人一種新元素平均時(shí)間復(fù)雜度為()。

A.0(n)B.0(1)

C.0(n2)D.O(10g2n)

二、填空題(每空1分，共28分)

1-數(shù)據(jù)存儲(chǔ)構(gòu)造被分為----、----、----和----四種。

2.在廣義表存儲(chǔ)構(gòu)造中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一種域相應(yīng)不同，各自分別為一

一域和一一域。

3.——中綴表達(dá)式3十x*(2.4/5—6)所相應(yīng)后綴表達(dá)式為

4.在一棵高度為h3叉樹中，最多具有一一結(jié)點(diǎn)。

5.假定--棵二叉樹結(jié)點(diǎn)數(shù)為18,則它最小深度為一一，最大深度為---

6.在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)左子樹上所有結(jié)點(diǎn)值一定一一該結(jié)點(diǎn)值，右子

樹上所有結(jié)點(diǎn)值一定一一該結(jié)點(diǎn)值。

7.當(dāng)向一種小根堆插入一種具備最小值元素時(shí)，該元素需要逐級(jí)一一調(diào)節(jié)，直到被調(diào)

節(jié)到——位置為止。

8.表達(dá)圖三種存儲(chǔ)構(gòu)造為--、----和------。

9.對(duì)用鄰接矩陣表達(dá)具備n個(gè)頂點(diǎn)和e條邊圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為一

一，對(duì)用鄰接表表達(dá)圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為——0

10.從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時(shí)，其

查找長(zhǎng)度分別為--和----?

11.假定對(duì)長(zhǎng)度n=144線性表進(jìn)行索引順序查找，并假定每個(gè)子表長(zhǎng)度均為，則

進(jìn)行索引順序查找平均查找長(zhǎng)度為一一，時(shí)間復(fù)雜度為-----

12.一棵B一樹中所有葉子結(jié)點(diǎn)均處在一一上。

13.每次從無序表中順序取出一種元素，把這插入到有序表中恰當(dāng)位置，此種排序辦法

叫做一一排序；每次從無序表中挑選出一種最小或最大元素，把它互換到有序表一

端，此種排序辦法叫做一一排序。

14.迅速排序在乎均狀況下時(shí)間復(fù)雜度為一一，最壞狀況下時(shí)間復(fù)雜度為

O

三、運(yùn)算題(每小題6分，共24分)

1.假定一棵二叉樹廣義表表達(dá)為a(b(c,d),c(((,8))),分別寫出對(duì)它進(jìn)行先序、中序、

后序和后序遍歷成果。

先序：

中序；

后序：

2.已知一種帶權(quán)圖頂點(diǎn)集V和邊集G分別為：

V={0,1,2,3,4,5)；

E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10),

則求出該圖最小生成樹權(quán)。

最小生成樹權(quán)；

3.假定一組記錄排序碼為(46,79,56,38,40,84,50,42),則運(yùn)用堆排序辦法建

立初始堆為一一。

4.有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~子結(jié)點(diǎn)生

成一棵哈夫曼樹，求出該樹帶權(quán)途徑長(zhǎng)度、高度、雙分支結(jié)點(diǎn)數(shù)。

帶權(quán)途徑長(zhǎng)度：----高度：------雙分支結(jié)點(diǎn)數(shù)：------。

四、閱讀算法，回答問題(每小題8分，共16分)

1.V01dAC(List&L)

(

InitList(L)；

InsertRear(L;25)；

InsertFront(L,50)；

IntaL4]={5,8,12,15,36};

for(inti=0；i<5；i++)

if(a[i]%2==0)InsertFront(L,a[i])；

elselnsertRear(L,a[i])；

)

該算法被調(diào)用執(zhí)行后，得到線性表L為：

2.voidAG(Queue&Q)

(

InitQueue(Q)；

inta[5]={6,12,5,15,8}；

for(inti=0;i<5；i++)QInsert(Q,a[i])；

QInsert(Q,QDelete(Q))；

QInsert(Q,20)；

QInsert(Q,QDelete(Q)十16)；

while(!QueueEmpty(Q))cout?QDelete(Q)?”；

)

該算法被調(diào)用后得到輸出成果為：

五、算法填空，在畫有橫線地方填寫適當(dāng)內(nèi)容(每小題6分，共12分)

1.從一維數(shù)組A[n)中二分查找核心字為K元素遞歸算法，若查找成功則返回相應(yīng)元素

下標(biāo)，否則返回一1。

IntBinsch(ElemTypeA[J,Intlow,inthigh,KeyTypeK)

(

if(low<=high)

(

intmid=(low+high)/2；

if(K==A[mid].key)------；

elseif(K<A[mid].key)------；

else；

)

elsereturn-1；

}

2.已知二叉樹中結(jié)點(diǎn)類型BinTreeNode定義為：

structBinTreeNode{ElemTypedata；BinTreeNode*left,*right)；

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)指針域。下面函數(shù)功能

是返回二叉樹BT中值為x結(jié)點(diǎn)所在層號(hào)，請(qǐng)?jiān)趧澯袡M線地方填寫適當(dāng)內(nèi)容。

IntNodeLevel(BinTreeNode*BT,ElemTypeX)

(

if(BT：=NULL)return0；//空樹層號(hào)為0

elseif(BT—>data==X)retum1；//根結(jié)點(diǎn)層號(hào)為1

//向子樹中查找x結(jié)點(diǎn)

else(

intcl=NodeLevel(BT—>left,X)；

if(cl>=l)retumcl+1;

intc2=；

if—;

//若樹中不存在X結(jié)點(diǎn)則返回。

elsereturn0；

六、編寫算法（8分）

按所給函數(shù)聲明編寫一種算法，從表頭指針為HL單鏈表中查找出具備最大值結(jié)點(diǎn)，該

最大值由函數(shù)返回，若單鏈表為空則中斷運(yùn)營(yíng)。

ElemTypeMaxVaiue（LNOde*HL）;

1月開放教誨?？啤皵?shù)據(jù)構(gòu)造”期末考試試題答案

一、單選題（每小題2分，共12分）

評(píng)分原則；選對(duì)者得2分，否則不得分。

1.B2.B3.C4.D5.B6.A

二、填空題（每空1分，共28分）

1.順序構(gòu)造鏈接構(gòu)造索引構(gòu)造散列構(gòu)造（順序無先后）

2.值（或data）子表指針（或sublist）

3.3x2.45/6—*+

4.（3"-1）/2

5.518

6.不大于不不大于（或不不大于等于）

7.向上堆頂

8.鄰接矩陣鄰接表邊集數(shù)組（順序無先后）

9.0（1?）0（e）

10.13

11.130（）

12.同一層

13.插人選取

14.O（nlog2n）O（n2）

三、運(yùn)算題（每小題6分，共24分）

1.先序：a,b,c,d,e,f,e//2分

中序：c,b,d,a,f,8,e//2分

后序：c,d,b,e,f,e,a//2分

2.最小生成樹權(quán)：31//6分

3.(84,79,56,42,40,46,50,38)//6分

4.帶權(quán)途徑長(zhǎng)度：131//3分

高度：5//2分

雙分支結(jié)點(diǎn)數(shù)：6//1分

四、閱讀算法，回答問題(每小題8分，共16分)

評(píng)分原則：每小題對(duì)的得8分，浮現(xiàn)一處錯(cuò)誤扣4分，兩處及以上錯(cuò)誤不得分。

1.(36,12,8,50,25,5,15)

2.515862028

五、算法填空，在畫有橫線地方填寫適當(dāng)內(nèi)容(每小題6分，共12分)

1.fetummid