《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷及答案

大學(xué)《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷及答案

一、填空題(共30分)

1、一個(gè)“好”的算法應(yīng)該考慮5條準(zhǔn)則，即①：正確性、②時(shí)間復(fù)雜性、③占用

空間、④可讀性、⑤堅(jiān)固性。(5分)

2、C++語(yǔ)言對(duì)類(lèi)的聲明的通用形式為：(3分)

classclassname

(

private其中①先根遍歷序列為：ABCEIFJDGHKL、②中根遍歷序列為：EICFJBGDAKHL、③后根遍

Q)私有數(shù)據(jù)成員歷序列為：IEJFCGBDBKLHA。(3分)

②私有函數(shù)成員6、有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有①—條邊，有n個(gè)頂點(diǎn)的有向連通圖至少有②p;_條

pubIic

③公有數(shù)據(jù)成員邊。(4分)

④公有函數(shù)成員

7、下列重建樹(shù)根為Rf的二叉樹(shù)的算法的時(shí)間復(fù)雜度為：0_￡log2e^_o(6分)

protected

⑤保護(hù)數(shù)據(jù)成員算法Restore(R,f,e)

⑥保護(hù)函數(shù)成員/*重建樹(shù)根為Rf的二叉樹(shù)，使之滿(mǎn)足堆的特性.Rf的左、右子樹(shù)是堆，且以Rf為根的樹(shù)中的任意結(jié)

1點(diǎn)，其編號(hào)均不大于e.*/

3、下面函數(shù)progl執(zhí)行的操作是：先將鏈表L的DATA域中的數(shù)據(jù)按序壓入到堆棧S中，然后再R1［初始化］

將堆棧S中彈出到鏈表L中，使得鏈表L中的數(shù)據(jù)與原數(shù)據(jù)按反序鏈接c(3分)j-f.

Template<classT>R2［建堆］

Voidprogl(LinkedList<T>&L)WHILEjW|_e/2」DO

((IF(2j<e)AND(K2j<K2j+1)THENnw-2j+1

Stack<T>Node<T>s;ELSEm<-2j.

For(L.Reset();!L.EndofLIST();L.Next())//Rm是Rj的具有較大關(guān)鍵詞的兒子結(jié)點(diǎn)

s.Push(L.Data());IFKm>KjTHEN(RmcRj.

L.Reset();j<-m)//Rm和Rj互換，繼續(xù)重建堆

while(!s.StackEmpty())ELSE//終止循環(huán)

(e)|

L.Data()=s.POP；8、用鄰接矩陣存儲(chǔ)包含100個(gè)頂點(diǎn)和100條邊的有向圖，則該鄰接矩陣中的元素個(gè)數(shù)為①15咽

L.Next()；非零元素個(gè)數(shù)為②9900。(4分)

)9、若一個(gè)棧的輸入序列是1,2,3……n,則輸出序列的第一個(gè)元素是n,則第J個(gè)輸出元素是:工hL。

)(4分)

4、現(xiàn)聲明如下字符串：(4分)

StringA(uSupperisn),B(uready!n),C(A),D=B:應(yīng)用題(30分)

①C的值是：“Supperis"、②D的值是：“ready!”、③D=A+B的值是：Supperis1、請(qǐng)構(gòu)造權(quán)值為｛5,13,21,7,18,30,41｝的哈夫曼樹(shù)。(7分)

ready!"、@C+=B的值是：“Supperisready!"。2、某二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用層次順序存儲(chǔ)表示如下：(9分)

5、由下圖中的二叉樹(shù)可以得出其遍歷序列

0IJ34J5JBJIQ1112產(chǎn)14尸IS。1B叫

IEIAIFIIDIIHIIIcl□IGIIII］IIB］

(1)試畫(huà)出此二叉樹(shù)的圖形表示。(3分)

（2）寫(xiě)出結(jié)點(diǎn)D的雙親結(jié)點(diǎn)及左、右子女。（3分）

（3）將此二叉樹(shù)看作森林的二叉樹(shù)表示.試將它還原為森林口（3分）

3、對(duì)于下圖的無(wú)向網(wǎng)絡(luò)，利用PRIM算法和Kruskar算法，分別求出最小支攆樹(shù)，要求寫(xiě)出生

成過(guò)程（7分）

第2步：（1分）

4、給出一組關(guān)鍵字（19,8,26,92,27,11,43,47,21）進(jìn)行堆排序，試列出每一趟排序

后關(guān)鍵字的排列次序，并比較每遍排序所進(jìn)行的關(guān)鍵字比較次數(shù)。（7分）

三、算法題（40分）

1、給出復(fù)數(shù)類(lèi)園類(lèi)的聲明（包括計(jì)算它的周長(zhǎng)、面積函數(shù)成員）。（6分）

2、已知A[n]為整數(shù)數(shù)組，寫(xiě)出實(shí)現(xiàn)下列運(yùn)算的遞歸算法（9分）

（1）數(shù)組A中的最大數(shù)。（3分）

（2）求A中n個(gè)元素的和。（3分）

（3）求A中n個(gè)元素的平均值。（3分）

3、設(shè)文件（《，&,…，/?〃）是一個(gè)堆，+l是任意節(jié)點(diǎn)。設(shè)計(jì)一個(gè)算法，把R〃+l添

加到堆R2,…,Rn）中，使（％,此，…，R〃，冊(cè)7+1）成為一個(gè)新堆。（9分）

4、寫(xiě)出歸并（合并）排序的算法。（8分）

5、寫(xiě)出查找正權(quán)最短路徑的Dijkstra算法。（8分）

二應(yīng)用題（30分）

1.解：哈夫曼樹(shù)為：

第1步：（1分）

2.解：（1）二叉樹(shù)的圖形是：（3分）

16

第5步：得最小支撐樹(shù)（2分）

3.解：用PRIM算法，求出最小支撐樹(shù)生成過(guò)程如下：（4分）

第1步:（0.5分）

用Kruskar算法，求出最小支撐樹(shù)生成過(guò)程如下：（3分）

第1步：@5分）

?

OO第2步：（0.5分）

第3步：（0.5分）O

?

OO

第3步：第1次交換，排序比較次數(shù)為：2+2=4（0.5分）

第5步：第3次交換，排序比較次數(shù)為：2+2=4（0.5分）

第1步：初始化之前（0.5分）

第7步：第5次交換，比較次數(shù)為：2+1=3。5分）

三算法題(40分)

1、解：圓的類(lèi)聲明如下：(6分)

classcircularity

{private：floatradii;

public：

//構(gòu)造函數(shù)

circularity(floatradii=0)；

//讀取和修改私有數(shù)據(jù)的函數(shù)

floatGetradii(void)const；

voidGiveradii(floatrad)：

//計(jì)算并返回圓的周長(zhǎng)和面積

floatPerimeter(void)const；

floatArea(void)const；

};

//構(gòu)造函數(shù)

circularity::circularity(floatrad)

第9步：第7次交換，排序比較次數(shù)為：1（0.5分）

{radii=rad；}

//返回圓的半徑值

floatcircularity::Getradii(void)const

{returnradii；}

//重置圓的半徑值

floatcircularity::Giveradii(floatrad)

{radii=Ieng；}

//計(jì)算并返回圓的的周長(zhǎng)

floatcircularity::Perimeter(void)const

第10步：第8次交換，排序比較次數(shù)為：0（0.5分）

{return2.0*3.14159*radii；)

//計(jì)算并返回圓的的面積

floatcircularity::Area(void)const

{return3.14159*radii*radii；}

2、解：(1)數(shù)組A中的最大數(shù)算法是(3分)：

LongMax(Longn)

{If(n==1)

ReturnA[1];

第11步：第9次交換，比較次數(shù)為：

因此，總的排序比較次數(shù)為：14+4+4+4+2+3+2+1+0=34次（2分）EIse

Ifmax(n-1)>A[n]并這兩個(gè)文件后得到排序好的大文件(Xt,Xt+1,…，Xn)*/

Returnmax(n-1)

ElseM1［初始化給每個(gè)文件一個(gè)頭指針］

ReturnA[n]};i—t.j-m+l.k*-1.

(2)求A中n個(gè)元素的和。(3分)M2［比較i和j所指記錄］

LongSum(Longn)WHILE(i^m)AND(jWn)DO

(if(n=1)(IFKiWKjTHEN(Xk-Ri.i-i+1)

ReturnA[1];ELSE(Xk-RJ.j-j+l).

Elsek-k+1).

ReturnA[n]+Sum(n-1)};M3［復(fù)制余留記錄項(xiàng)］

(3)求A中n個(gè)元素的平均值。(3分)

IFi>mTHEN

Longj=n,i=0FORp=kTOnDOXp-Rj+p-k

LongAvg(Longn)ELSE

{if(n==1)FORp=kTOnDOXp*-Ri+p-k|

l=A[1]

Returni/j;5、解：下面給出解決正權(quán)單源最短路徑問(wèn)題的Dijkstra算法：(8分)

Else//在頂點(diǎn)個(gè)數(shù)為n的圖中，求從初始頂點(diǎn)v到其他各頂點(diǎn)的最短路徑。

l=A[n]+Avg(n-1)1;voidGraph::ShortestPath(constn,constintv)

3、解：(9分){intu,k;

算法Resetupheap(R,f,Rm+1)edge*p;

〃R1,R2,…Rm已經(jīng)建好堆，其根為Rf.Rm+1為要插入的元素s=newint［］;〃數(shù)組s［i］記錄i是否被訪(fǎng)問(wèn)過(guò)

R1［初始化］for(i=0;i<n;i++)〃數(shù)組path,dists初始化

{path[i]=-1;dist[i]=max:s[i]=0}

R2[建堆]Dist［v］=0;s［v］=1〃初始頂點(diǎn)v的數(shù)組值

WHILEDOP=head[v].adjacent;

(IF(2j<m+1)AND(K2j<K2j+1)THENn<-2j+1u=v;〃u為即將訪(fǎng)問(wèn)的頂點(diǎn)

ELSEn<-2j.