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

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

一、填空題(共30分)

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

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

2、C++語言對類的聲明的通用形式為：(3分)

classclassname

(

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

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

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

pubIic

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

④公有函數(shù)成員

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

protected

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

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

1點，其編號均不大于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é)點

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、用鄰接矩陣存儲包含100個頂點和100條邊的有向圖，則該鄰接矩陣中的元素個數(shù)為①15咽

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

)9、若一個棧的輸入序列是1,2,3……n,則輸出序列的第一個元素是n,則第J個輸出元素是:工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、請構(gòu)造權(quán)值為｛5,13,21,7,18,30,41｝的哈夫曼樹。(7分)

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

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

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

IEIAIFIIDIIHIIIcl□IGIIII］IIB］

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

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

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

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

成過程（7分）

第2步：（1分）

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

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

三、算法題（40分）

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

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

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

（2）求A中n個元素的和。（3分）

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

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

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

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

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

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

1.解：哈夫曼樹為：

第1步：（1分）

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

16

第5步：得最小支撐樹（2分）

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

第1步:（0.5分）

用Kruskar算法，求出最小支撐樹生成過程如下：（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、解：圓的類聲明如下：(6分)

classcircularity

{private：floatradii;

public：

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

circularity(floatradii=0)；

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

floatGetradii(void)const；

voidGiveradii(floatrad)：

//計算并返回圓的周長和面積

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；}

//計算并返回圓的的周長

floatcircularity::Perimeter(void)const

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

{return2.0*3.14159*radii；)

//計算并返回圓的的面積

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]并這兩個文件后得到排序好的大文件(Xt,Xt+1,…，Xn)*/

Returnmax(n-1)

ElseM1［初始化給每個文件一個頭指針］

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

(2)求A中n個元素的和。(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ù)制余留記錄項］

(3)求A中n個元素的平均值。(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)單源最短路徑問題的Dijkstra算法：(8分)

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

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是否被訪問過

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〃初始頂點v的數(shù)組值

WHILEDOP=head[v].adjacent;

(IF(2j<m+1)AND(K2j<K2j+1)THENn<-2j+1u=v;〃u為即將訪問的頂點

ELSEn<-2j.