数据结构试卷2006级B卷答案.docVIP

江 西 理 工 大 学 考 试 试 卷 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分） Templateclass T Void prog1(LinkedListT L) { StackTNodeT s; For (L.Reset();!L.EndofLIST();L.Next()) s.Push(L.Data()); L.Reset(); while (!s.StackEmpty()) { L．Data（）=s.POP； L．Next（）； } } 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 [初始化] j?f． R2 [建堆] WHILE j≤?e/2? DO （IF（2j e）AND（K2j ＜ K2j＋1） THEN m?2j+1 ELSE m?2j . // Rm是Rj的具有较大关键词的儿子结点 IF Km Kj THEN（Rm?Rj . j?m ） // Rm和Rj互换，继续重建堆 ELSE // 终止循环 j?e ）▌ 8、用邻接矩阵存储包含100个顶点和100条边的有向图，则该邻接矩阵中的元素个数为①10000 ，非零元素个数为②9900 。（4分） 9、若一个栈的输入序列是1，2，3……n，则输出序列的第一个元素是n，则第j个输出元素是： n-j+1 。（4分） 应用题（30分） 请构造权值为{5，13，21，7，18，30，41}的哈夫曼树。（7分） 某二叉树的结点数据采用层