数据结构试卷(2006级B卷)答案.doc

《数据结构试卷(2006级B卷)答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、试卷编号：0809010544江西理工大学试题纸第9页共9页江西理工大学考试试卷20_08___—20_09____学年第____1_____学期课程名称：__数据结构_____________________考试时间:___________年______月______日考试性质（正考、补考或其它）：[]考试方式(开卷、闭卷)：[闭卷]试卷类别(A、B、C):[B]共大题温馨提示请考生自觉遵守考试纪律，争做文明诚信的大学生。如有违犯考试纪律，将严格按照《江西理工大学学生违纪处分暂行规定》处理。班级学号姓名题号一二三四

2、五六七八九十十一十二总分得分一、填空题（共30分）1、一个“好”的算法应该考虑5条准则，即①：正确性、②时间复杂性、③占用空间、④可读性、⑤坚固性。（5分）2、C++语言对类的声明的通用形式为：（3分）classclassname{private①私有数据成员②私有函数成员public③公有数据成员④公有函数成员protected⑤保护数据成员⑥保护函数成员}3、下面函数prog1执行的操作是：先将链表L的DATA域中的数据按序压入到堆栈S中，然后再将堆栈S中弹出到链表L中，使得链表L中的数据与原数据按反序链接。（3

3、分）TemplateVoidprog1(LinkedList&L){StackNodes;For(L.Reset();!L.EndofLIST();L.Next())s.Push(L.Data());L.Reset();while(!s.StackEmpty()){L．Data（）=s.POP；L．Next（）；}}4、现声明如下字符串：（4分）StringA(“Supperis”),B(“ready!”),C(A),D=B;①C的值是：“Supperis”、②D的值是：“ready

4、!”、③D=A+B的值是：“Supperisready!”、④C+=B的值是：“Supperisready!”。试卷编号：0809010544江西理工大学试题纸第9页共9页5、由下图中的二叉树可以得出其遍历序列其中①先根遍历序列为：ABCEIFJDGHKL、②中根遍历序列为：EICFJBGDAKHL、③后根遍历序列为：IEJFCGBDBKLHA。（3分）6、有n个顶点的无向连通图至少有①条边，有n个顶点的有向连通图至少有②条边。（4分）7、下列重建树根为Rf的二叉树的算法的时间复杂度为：O（）。（6分）算法Resto

5、re（R，f，e）/*重建树根为Rf的二叉树，使之满足堆的特性.Rf的左、右子树是堆，且以Rf为根的树中的任意结点，其编号均不大于e.*/R1[初始化]j¬f．R2[建堆]WHILEj≤ëe/2ûDO（IF（2jKjTHEN（Rm«Rj.j¬m）//Rm和Rj互换，继续重建堆ELSE//终止循环j¬e）▌8、用邻接矩阵存储包含100个顶点和100条边的有向图，则该邻接矩阵中的元素个数为①10000

6、，非零元素个数为②9900。（4分）9、若一个栈的输入序列是1，2，3……n，则输出序列的第一个元素是n，则第j个输出元素是：n-j+1。（4分）一、应用题（30分）1、请构造权值为{5，13，21，7，18，30，41}的哈夫曼树。（7分）2、某二叉树的结点数据采用层次顺序存储表示如下：（9分）(1)试画出此二叉树的图形表示。(3分)(2)写出结点D的双亲结点及左、右子女。   (3分)(3)将此二叉树看作森林的二叉树表示，试将它还原为森林。(3分)3、对于下图的无向网络，利用PRIM算法和Kruskar算法，分别

7、求出最小支撑树，要求写出生成过程（7分）4、给出一组关键字（19，8，26，92，27，11，43，47，21）进行堆排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。（7分）试卷编号：0809010544江西理工大学试题纸第9页共9页一、算法题（40分）1、给出复数类园类的声明（包括计算它的周长、面积函数成员）。（6分）2、已知A[n]为整数数组，写出实现下列运算的递归算法（9分）(1)数组A中的最大数。(3分)(2)求A中n个元素的和。(3分)(3)求A中n个元素的平均值。(3分)3

8、、设文件（，，…,）是一个堆，是任意节点。设计一个算法，把添加到堆（，，…,）中，使（，，…,，）成为一个新堆。（9分）4、写出归并（合并）排序的算法。（8分）5、写出查找正权最短路径的Dijkstra算法。（8分）二应用题（30分）1.解：哈夫曼树为：第1步：(1分)第2步：(1分)、第3步：(1分)第4步：(1分)第5步：(1分)试卷编号：