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

试卷编号 试卷编号 0809010544 江江 西西 理理 工工 大大 学学 试试 题题 纸纸 第 1 页 共 9 页 江 西 理 工 大 学 考 试 试 卷 一 填空题 共 30 分 1 一个 好 的算法应该考虑 5 条准则 即 正确性 时间复杂性 占用空间 可读性 坚固性 5 5 分 分 2 C 语言对类的声明的通用形式为 3 3 分 分 class classname private 私有数据 成员 私有函数 成员 public 公有数据 成员 公有函数 成员 protected 保护数据 成员 保护函数 成员 3 下面函数 prog1 执行的操作是 先将链表 L 的 DATA 域中的数据按序 压入到堆栈 S 中 然后再将堆栈 S 中弹出到链表 L 中 使得链表 L 中的数据 与原数据按反序链接 3 3 分 分 Template Void prog1 LinkedList For L Reset L EndofLIST L Next s Push L Data L Reset while s StackEmpty L Data s POP L Next 4 现声明如下字符串 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 考试性质 正考 补考或其它 考试性质 正考 补考或其它 考试方式考试方式 开卷 闭卷开卷 闭卷 闭卷闭卷 20 08 20 09 学年第 1 学期 课程名称 数据结构 考试时间 年 月 日 试卷类别试卷类别 A A B B C C B B 共共 大题大题 温温 馨馨 提提 示示 请考生自觉遵守考试纪律 争做文明诚信的大学生 如有违犯考试纪律 将严 格按照 江西理工大学学生违纪处分暂行规定 处理 班级 学号 姓名 题号题号一二三四五六七八九十 十 一 十 二 总总 分分 得分得分 试卷编号 试卷编号 0809010544 江江 西西 理理 工工 大大 学学 试试 题题 纸纸 第 2 页 共 9 页 ready 5 由下图中的二叉树可以得出其遍历序列 其中 先根遍历序列为 ABCEIFJDGHKL 中根遍历序列为 EICFJBGDAKHL 后根遍历序列为 IEJFCGBDBKLHA 3 3 分 分 6 有 n 个顶点的无向连通图至少有 条边 有 n 个顶点的有向连 CN 2 通图至少有 条边 4 4 分 分 PN 2 7 下列重建树根为 Rf 的二叉树的算法的时间复杂度为 O e 2 log 6 6 分 分 算法 Restore R f e 重建树根为 Rf 的二叉树 使之满足堆的特性 Rf 的左 右子树是堆 且以 Rf 为根的树中的任意 结点 其编号均不大于 e R1 初始化 j f R2 建堆 WHILE j e 2 DO IF 2j Kj THEN Rm Rj j m Rm 和 Rj 互换 继续重建堆 ELSE 终止循环 j e 8 用邻接矩阵存储包含 100 个顶点和 100 条边的有向图 则该邻接矩阵 中的元素个数为 10000 非零元素个数为 9900 4 4 分 分 9 9 若一个栈的输入序列是 1 2 3 n 则输出序列的第一个元素是 n 则第 j 个输出元素是 n j 1 4 4 分 分 二 二 应用题 应用题 3030 分 分 1 请构造权值为 5 13 21 7 18 30 41 的哈夫曼树 7 7 分 分 2 某二叉树的结点数据采用层次顺序存储表示如下 9 9 分 分 1 试画出此二叉树的图形表示 3 分 2 写出结点 D 的双亲结点及左 右子女 3 分 3 将此二叉树看作森林的二叉树表示 试将它还原为森林 3 分 3 对于下图的无向网络 利用 PRIM 算法和 Kruskar 算法 分别求出 最小支撑树 要求写出生成过程 7 7 分 分 4 给出一组关键字 19 8 26 92 27 11 43 47 21 进行堆 排序 试列出每一趟排序后关键字的排列次序 并比较每遍排序所进行的关 键字比较次数 7 7 分 分 试卷编号 试卷编号 0809010544 江江 西西 理理 工工 大大 学学 试试 题题 纸纸 第 3 页 共 9 页 三 三 算法题 算法题 4040 分 分 1 给出复数类园类的声明 包括计算它的周长 面积函数成员 6 6 分 分 2 已知 A n 为整数数组 写出实现下列运算的递归算法 9 9 分 分 1 数组 A 中的最大数 3 分 2 求 A 中 n 个元素的和 3 分 3 求 A 中 n 个元素的平均值 3 分 3 设文件 是一个堆 是任意节点 设计一 1 R 2 RRn1 Rn 个算法 把添加到堆 中 使 1 Rn 1 R 2 RRn 1 R 2 RRn 成为一个新堆 9 9 分 分 1 Rn 4 写出归并 合并 排序的算法 8 8 分 分 5 写出查找正权最短路径的 Dijkstra 算法 8 8 分 分 二二 应用题 应用题 3030 分 分 1 解 解 哈夫曼树为 第第 1 1 步 步 1 1 分分 第第 2 2 步 步 1 1 分分 第第 3 3 步 步 1 1 分分 第第 4 4 步 步 1 1 分分 第第 5 5 步 步 1 1 分分 试卷编号 试卷编号 0809010544 江江 西西 理理 工工 大大 学学 试试 题题 纸纸 第 4 页 共 9 页 2 2 解 解 1 1 二叉树的图形是 二叉树的图形是 3 3 分分 2 2 D D 的双亲节点是的双亲节点是 A A 左子女为 左子女为 C C 无右子女 无右子女 3 3 分分 3 3 还原成森林如下 还原成森林如下 3 3 分分 3 3 解 解 用 PRIM 算法 求出最小支撑树生成过程如下 4 4 分分 第第 1 1 步 步 0 5 0 5 分分 第第 2 2 步 步 0 5 0 5 分分 第第 3 3 步 步 0 5 0 5 分分 第第 4 4 步 步 0 5 0 5 分分 第第 5 5 步 得步 得最小支撑树 2 2 分分 试卷编号 试卷编号 0809010544 江江 西西 理理 工工 大大 学学 试试 题题 纸纸 第 5 页 共 9 页 用 Kruskar 算法 求出最小支撑树生成过程如下 3 3 分分 第第 1 1 步 步 0 5 0 5 分分 第第 2 2 步 步 0 5 0 5 分分 第第 3 3 步 步 0 5 0 5 分分 第第 4 4 步 步 0 5 0 5 分分 第第 5 5 步 得步 得最小支撑树 1 1 分分 4 4 解 解 堆排序的情况如下 7 7 分分 第第 1 1 步 初始化之前步 初始化之前 0 5 0 5 分分 第第 2 2 步 初始化建堆 排序比较次数为 步 初始化建堆 排序比较次数为 2 2 4 6 14 0 52 2 4 6 14 0 5 分分 第第 3 3 步 第步 第 1 1 次交换 排序比较次数为 次交换 排序比较次数为 2 2 4 0 52 2 4 0 5 分分 试卷编号 试卷编号 0809010544 江江 西西 理理 工工 大大 学学 试试 题题 纸纸 第 6 页 共 9 页 第第 4 4 步 第步 第 2 2 次交换 排序比较次数为 次交换 排序比较次数为 2 2 4 0 52 2 4 0 5 分分 第第 5 5 步 第步 第 3 3 次交换 排序比较次数为 次交换 排序比较次数为 2 2 4 0 52 2 4 0 5 分分 第第 6 6 步 第步 第 4 4 次交换 比较次数为 次交换 比较次数为 2 0 52 0 5 分分 第第 7 7 步 第步 第 5 5 次交换 比较次数为 次交换 比较次数为 2 1 3 0 52 1 3 0 5 分分 第第 8 8 步 第步 第 6 6 次交换 排序比较次数为 次交换 排序比较次数为 2 0 52 0 5 分分 第第 9 9 步 第步 第 7 7 次交换 排序比较次数为 次交换 排序比较次数为 1 0 51 0 5 分分 第第 1010 步 第步 第 8 8 次交换 排序比较次数为 次交换 排序比较次数为 0 0 50 0 5 分分 试卷编号 试卷编号 0809010544 江江 西西 理理 工工 大大 学学 试试 题题 纸纸 第 7 页 共 9 页 第第 1111 步 第步 第 9 9 次交换 比较次数为 次交换 比较次数为 因此 总的排序比较次数为 因此 总的排序比较次数为 14 4 4 4 2 3 2 1 0 3414 4 4 4 2 3 2 1 0 34 次次 2 2 分分 三三 算法题 算法题 4040 分 分 1 1 解 圆 解 圆 的类声明如下 的类声明如下 6 6 分分 class circularity private 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 2 解 解 1 数组 A 中的最大数算法是 3 分 Long Max Long n If n 1 Return A 1 Else If max n 1 A n Return max n 1 Else Return A n 2 求 A 中 n 个元素的和 3 分 Long Sum Long n if n 1 Return A 1 Else Return A n Sum n 1 3 求 A 中 n 个元素的平均值 3 分 Long j n i 0 Long Avg Long n if n 1 I A 1 Return i j Else I A n Avg n 1 试卷编号 试卷编号 0809010544 江江 西西 理理 工工 大大 学学 试试 题题 纸纸 第 8 页 共 9 页 3 3 解 解 9 9 分分 算法Resetupheap R f Rm 1 R1 R2 Rm已经建好堆 其根为Rf Rm 1为要插入的元素 R1 初始化 j f R2 建堆 WHILE j m 1 2 DO IF 2j Kj THEN Rn Rj j n Rm和Rj互换 继续重建堆 ELSE 终止循环 j m 1 4 4 解 解 8 8 分分 算法Merge R t m n X 假定文件 Rt Rt 1 Rm 和文件 Rm 1 Rn 都已经 排序 该算法合并这两个文件后得到排序好的大文件 Xt Xt 1 Xn M1 初始化给每个文件一个头指针 i t j m l k l M2 比较 i和 j所指记录 WHILE i m AND j n DO IF Ki Kj THEN Xk Ri i i 1 ELSE Xk Rj j j l k k 1 M3 复制余留记录项 IF i m THEN FOR p k TO n DO Xp Rj p k ELSE FOR p k TO n DO Xp Ri p k 5 5 解 解 下面给出解决正权单源最短路径问题的下面给出解决正权单源最短路径问题的Dijkstra算法 算法 8 8分分 在顶点个数为n的图中 求从初始顶点v到其他各顶点的最短路径 void Graph ShortestPath const n const int v int u k edge p s new int 数组s i 记录i是否被访问过 for i 0 i n i 数组path dist s