《数据结构》期末考试试卷及答案

大学《数据结构》期末考试试卷及答案

一、填空题(共30分)

1、一个“好”的算法应该考虑5条准则，即①：正确性、②时间复杂性、③占用

空间、④可读性、⑤坚固性。(5分)

2、C++语言对类的声明的通用形式为：(3分)

classclassname

(

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

Q)私有数据成员历序列为：IEJFCGBDBKLHA。(3分)

②私有函数成员6、有n个顶点的无向连通图至少有①—条边，有n个顶点的有向连通图至少有②p;_条

pubIic

③公有数据成员边。(4分)

④公有函数成员

7、下列重建树根为Rf的二叉树的算法的时间复杂度为：0_£log2e^_o(6分)

protected

⑤保护数据成员算法Restore(R,f,e)

⑥保护函数成员/*重建树根为Rf的二叉树，使之满足堆的特性.Rf的左、右子树是堆，且以Rf为根的树中的任意结

1点，其编号均不大于e.*/

3、下面函数progl执行的操作是：先将链表L的DATA域中的数据按序压入到堆栈S中，然后再R1［初始化］

将堆栈S中弹出到链表L中，使得链表L中的数据与原数据按反序链接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的具有较大关键词的儿子结点

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

L.Reset();j<-m)//Rm和Rj互换，继续重建堆

while(!s.StackEmpty())ELSE//终止循环

(e)|

L.Data()=s.POP；8、用邻接矩阵存储包含100个顶点和100条边的有向图，则该邻接矩阵中的元素个数为①15咽

L.Next()；非零元素个数为②9900。(4分)

)9、若一个栈的输入序列是1,2,3……n,则输出序列的第一个元素是n,则第J个输出元素是:工hL。

)(4分)

4、现声明如下字符串：(4分)

StringA(uSupperisn),B(uready!n),C(A),D=B:应用题(30分)

①C的值是：“Supperis"、②D的值是：“ready!”、③D=A+B的值是：Supperis1、请构造权值为｛5,13,21,7,18,30,41｝的哈夫曼树。(7分)

ready!"、@C+=B的值是：“Supperisready!"。2、某二叉树的结点数据采用层次顺序存储表示如下：(9分)

5、由下图中的二叉树可以得出其遍历序列

0IJ34J5JBJIQ1112产14尸IS。1B叫

IEIAIFIIDIIHIIIcl□IGIIII］IIB］

(1)试画出此二叉树的图形表示。(3分)

（2）写出结点D的双亲结点及左、右子女。（3分）

（3）将此二叉树看作森林的二叉树表示.试将它还原为森林口（3分）

3、对于下图的无向网络，利用PRIM算法和Kruskar算法，分别求出最小支撵树，要求写出生

成过程（7分）

第2步：（1分）

4、给出一组关键字（19,8,26,92,27,11,43,47,21）进行堆排序，试列出每一趟排序

后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。（7分）

三、算法题（40分）

1、给出复数类园类的声明（包括计算它的周长、面积函数成员）。（6分）

2、已知A[n]为整数数组，写出实现下列运算的递归算法（9分）

（1）数组A中的最大数。（3分）

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

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

3、设文件（《，&,…，/?〃）是一个堆，+l是任意节点。设计一个算法，把R〃+l添

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

4、写出归并（合并）排序的算法。（8分）

5、写出查找正权最短路径的Dijkstra算法。（8分）

二应用题（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次交换，排序比较次数为：2+2=4（0.5分）

第5步：第3次交换，排序比较次数为：2+2=4（0.5分）

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

第7步：第5次交换，比较次数为：2+1=3。5分）

三算法题(40分)

1、解：圆的类声明如下：(6分)

classcircularity

{private：floatradii;

public：

//构造函数

circularity(floatradii=0)；

//读取和修改私有数据的函数

floatGetradii(void)const；

voidGiveradii(floatrad)：

//计算并返回圆的周长和面积

floatPerimeter(void)const；

floatArea(void)const；

};

//构造函数

circularity::circularity(floatrad)

第9步：第7次交换，排序比较次数为：1（0.5分）

{radii=rad；}

//返回圆的半径值

floatcircularity::Getradii(void)const

{returnradii；}

//重置圆的半径值

floatcircularity::Giveradii(floatrad)

{radii=Ieng；}

//计算并返回圆的的周长

floatcircularity::Perimeter(void)const

第10步：第8次交换，排序比较次数为：0（0.5分）

{return2.0*3.14159*radii；)

//计算并返回圆的的面积

floatcircularity::Area(void)const

{return3.14159*radii*radii；}

2、解：(1)数组A中的最大数算法是(3分)：

LongMax(Longn)

{If(n==1)

ReturnA[1];

第11步：第9次交换，比较次数为：

因此，总的排序比较次数为：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［复制余留记录项］

(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、解：下面给出解决正权单源最短路径问题的Dijkstra算法：(8分)

Else//在顶点个数为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已经建好堆，其根为Rf.Rm+1为要插入的元素s=newint［］;〃数组s［i］记录i是否被访问过

R1［初始化］for(i=0;i<n;i++)〃数组path,dists初始化

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

R2[建堆]Dist［v］=0;s［v］=1〃初始顶点v的数组值

WHILEDOP=head[v].adjacent;

(IF(2j<m+1)AND(K2j<K2j+1)THENn<-2j+1u=v;〃u为即将访问的顶点

ELSEn<-2j.