数据结构试卷(2007级A卷答案)16K.doc

江 西 理 工 大 学 考 试 试 卷 试卷编号：0910010545-A 20__09__—20__10___ 学年第____1_____学期 课程名称：______数据结构 _______________ 考试时间:___________ 年______月______日 考试性质（正考、补考或其它）：[ ] 考试方式(开卷、闭卷)：[ 闭卷 ] 试卷类别(A、B、C):[ A ] 共 3 大题 温 馨 提 示 请考生自觉遵守考试纪律，争做文明诚信的大学生。如有违犯考试纪律，将严格按照《江西理工大学学生违纪处分暂行规定》处理。 班级 学号 姓名 题号 一 二 三 四 五 六 七 八 九 十 十一 十二 总 分 得分 填空题（共30分） 1、二叉树的遍历方法至少应包括以下四种：① 层次遍历 、 ② 先根遍历 、 ③ 中根遍历 、④ 后根遍历 。（4分） 2、下面函数prog1执行的操作是： 将链表L中的数据按从前到后得顺序依次压入堆栈S，再从S中依次弹出并链接到链表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（）； } } 3、有n个顶点的无向连通图至少有① n-1 条边，有n个顶点的有向连通图至少有② n-1 条边。（4分） 4、C++语言对类的声明的通用形式为：（3分） class classname { private ① 私有函数 成员 ② 私有数据 成员 public ③ 公有函数 成员 ④ 公有数据 成员 protected ⑤ 保护函数 成员 ⑥ 保护数据 成员 } 5、由下图中的二叉树可以得出其遍历序列 其中①先根遍历序列为： ABCEIDGHKFJL 、②中根遍历序列为： CEIBGDAKFJHL 、③后根遍历序列为： IECGDBJFKLHA 。（3分） 6、下列直接选择排序算法的时间复杂度为： O(n2) 。（5分） 算法SSort（R,n） /* 对文件（R1，R2，…,RN）进行排序 */ SS1 [排序] FOR j=n TO 2 STEP -1 DO (t=1. FOR i=2 TO j DO IF KtKi THEN t=i. Rj--Rt）▌ 7、若一个队列的输入序列是n,n-1,…,3,2,1，则输出序列的第一个元素是① n ，则第j个输出元素是： n-j+1 。（4分） 8、用邻接矩阵存储包含100个顶点和100条边的有向图，则该邻接矩阵中的元素个数为① 10000 ，非零元素个数为② 100 。（4分） 应用题（30分） 若一棵二叉树终端结点数为R，度为2的结点数为S，试证明R=S+1。（7分） 证明：设度为1的结点数为P,则： 除根节点外其余各节点有且仅有一条边连接的父节点，因此有边数： R+P+S-1 度为1的结点的边数为P, 度为2的结点的边数为2S, 终端结点的边数为0. 根据边数恒等的原则有： R+P+S-1=P+2S 既有：R=S+1 证毕。 某二叉树的结点数据采用顺序存储表示如下：（9分） (1) 试画出此二叉树的图形表示。???? (3分) (2) 写出结点D的双亲结点及左、右子女。??? (3分) (3) 将此二叉树看作森林的二叉树表示，试将它还原为森林。(3分) 解：(1) 二叉树的图形如下: (2) 结点D的双亲结点是A, 左孩子无、右孩子是B. (3) 还原为森林如下： 根据下面给定的几个数（14，19，2，6，32，3，21，1