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

试卷编号：0809010544 江 西 理 工 大 学 试 题 纸 第 9 页 共 9 页江 西 理 工 大 学 考 试 试 卷20_08_20_09_ 学年第_1_学期课程名称：_数据结构_考试时间:_ 年_月_日考试性质（正考、补考或其它）： 考试方式(开卷、闭卷)： 闭卷 试卷类别(A、B、C): B 共 大题温 馨 提 示请考生自觉遵守考试纪律，争做文明诚信的大学生。如有违犯考试纪律，将严格按照江西理工大学学生违纪处分暂行规定处理。班级 学号 姓名 题号一二三四五六七八九十十一十二总 分得分一、 填空题（共30分）1、一个“好”的算法应该考虑5条准则，即：正确性 、 时间复杂性 、占用空间 、可读性 、坚固性 。（5分）2、C+语言对类的声明的通用形式为：（3分）class classname private 私有数据 成员私有函数 成员 public 公有数据 成员公有函数 成员 protected 保护数据 成员保护函数 成员 3、下面函数prog1执行的操作是：先将链表L的DATA域中的数据按序压入到堆栈S中，然后再将堆栈S中弹出到链表L中，使得链表L中的数据与原数据按反序链接 。（3分）TemplateVoid prog1(LinkedList &L) StackNode s; For (L.Reset();!L.EndofLIST();L.Next()s.Push(L.Data();L.Reset();while (!s.StackEmpty()LData（）=s.POP；LNext（）；4、现声明如下字符串：（4分） String A(“ Supper is ”),B(“ready!”),C(A),D=B;C的值是：“ Supper is ” 、D的值是：“ready!” 、D=A+B的值是：“ Supper is ready!” 、C+=B的值是：“ Supper is ready!” 。5、由下图中的二叉树可以得出其遍历序列其中先根遍历序列为：ABCEIFJDGHKL 、中根遍历序列为： EICFJBGDAKHL 、后根遍历序列为： IEJFCGBDBKLHA 。（3分）6、有n个顶点的无向连通图至少有 条边，有n个顶点的有向连通图至少有 条边。（4分） 7、下列重建树根为Rf的二叉树的算法的时间复杂度为：O（） 。（6分）算法Restore（R，f，e） /* 重建树根为Rf的二叉树，使之满足堆的特性. Rf的左、右子树是堆，且以Rf为根的树中的任意结点，其编号均不大于e . */R1 初始化 jf R2 建堆 WHILE je/2 DO （IF（2j Kj THEN（RmRj . jm ） / Rm和Rj互换，继续重建堆 ELSE / 终止循环 je ）8、用邻接矩阵存储包含100个顶点和100条边的有向图，则该邻接矩阵中的元素个数为10000 ，非零元素个数为9900 。（4分）9、若一个栈的输入序列是1，2，3n，则输出序列的第一个元素是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分） 4、 给出一组关键字（19，8，26，92，27，11，43，47，21）进行堆排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。（7分）三、 算法题（40分）1、 给出复数类园类的声明（包括计算它的周长、面积函数成员）。（6分）2、 已知An为整数数组，写出实现下列运算的递归算法（9分）(1)数组A中的最大数。 (3分)(2) 求A中n 个元素的和。 (3分)(3) 求A中n 个元素的平均值。(3分)3、 设文件（，, ）是一个堆，是任意节点。设计一个算法，把添加到堆（，, ）中，使（，, ，）成为一个新堆。（9分）4、 写出归并（合并）排序的算法。（8分）5、 写出查找正权最短路径的Dijkstra算法。（8分）二 应用题（30分）1. 解：哈夫曼树为：第1步：(1分)第2步：(1分)、第3步：(1分)第4步：(1分)第5步：(1分)2. 解：（1）二叉树的图形是：(3分) （2）D的双亲节点是A，左子女为C，无右子女。(3分) （3）还原成森林如下：(3分)3. 解：用PRIM算法，求出最小支撑树生成过程如下：(4分) 第1步：(0.5分) 第2步：(0.5分) 第3步：(0.5分) 第4步：(0.5分) 第5步：得最小支撑树(2分) 用Kruskar算法，求出最小支撑树生成过程如下：(3分) 第1步：(0.5分) 第2步：(0.5分) 第3步：(0.5分) 第4步：(0.5分) 第5步：得最小支撑树(1分)4. 解：堆排序的情况如下：(7分) 第1步：初始化之前(0.5分)第2步：初始化建堆，排序比较次数为：2+2+4+6=14(0.5分)第3步：第1次交换，排序比较次数为：2+2=4(0.5分)第4步：第2次交换，排序比较次数为：2+2=4(0.5分)第5步：第3次交换，排序比较次数为：2+2=4(0.5分)第6步：第4次交换，比较次数为：2(0.5分)第7步：第5次交换，比较次数为：2+1=3(0.5分)第8步：第6次交换，排序比较次数为：2(0.5分)第9步：第7次交换，排序比较次数为：1(0.5分)第10步：第8次交换，排序比较次数为：0(0.5分)第11步：第9次交换，比较次数为：因此，总的排序比较次数为：14+4+4+4+2+3+2+1+0=34次(2分)三 算法题（40分） 1、解：圆 的类声明如下：(6分)class circularityprivate： float radii ； public： / 构造函数 circularity （ float radii = 0 ）；/ 读取和修改私有数据的函数float Getradii （void）const；void Giveradii（float rad）；/ 计算并返回圆的周长和面积float Perimeter （void）const；float Area （void）const；/ 构造函数circularity: circularity（ float rad ） radii = rad ；/ 返回圆的半径值float circularity: Getradii （ void ） const return radii ； / 重置圆的半径值float circularity: Giveradii（float rad） radii = leng ； / 计算并返回圆的的周长float circularity:Perimeter（ void ） const return 2.0 * 3.14159*radii ； / 计算并返回圆的的面积float circularity:Area （ void ） const return 3.14159*radii*radii ； 2、解： (1)数组A中的最大数算法是 (3分)： Long Max（Long n） If (n=1) Return A1; Else If max(n-1)An Return max(n-1) Else Return An;(2) 求A中n 个元素的和。 (3分)Long Sum（Long n）if (n=1)Return A1; Else Return An+ Sum（n-1）;(3) 求A中n 个元素的平均值。(3分) Long j=n,i=0Long Avg（Long n） if (n=1) I=A1 Return i/j; Else I= An+ Avg（n-1）;3、解：(9分) 算法Resetupheap(R,f,Rm+1) /R1,R2,Rm已经建好堆，其根为Rf，Rm+1为要插入的元素 R1 初始化 jf R2 建堆 WHILE jm+1/2 DO （IF（2j Kj THEN（RnRj .jn ） / Rm和Rj互换，继续重建堆 ELSE / 终止循环 jm+1）4、解：(8分)算法Merge (R，t，m，n. X) /* 假定文件（Rt，Rt1，Rm）和文件（Rm1，Rn）都已经排序，该算法合并这两个文件后得到排序好的大文件（Xt，Xt1，Xn） */ M1 初始化给每个文件一个头指针 it jml kl M2 比较 i和 j所指记录 WHILE（im） AND（jn） DO （ IF KiKj THEN（XkRi ii1） ELSE（XkRj jjl）. kk+1）. M3 复制余留记录项 IF im THEN FOR pk TO n DO XpRj+pk ELSE FOR p=k TO n DO XpRi+pk 5、解：下面给出解决正权单源最短路径问题的Dijkstra算法：(8分) /在顶点个数为n的图中，求从初始顶点v到其他各顶点的最短路径。 void Graph : ShortestPath( const n , const int v ) int u , k ; edge *p ; s = new int ; /数组si 记录i是否被访问过 for( i = 0 ; i n ; i + + ) /数组path,dist,s初始化 pathi=-1;disti=max; si=0 Distv=0;sv=1 /初始顶点v的数组值 P=headv.adjacent; u=v; /u为即将访问的顶