试卷代号：1010 中央广播电视大学2007一2008学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题答案及评分标准 (供参考) 2008年1月 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分】 1.C 2.C 3.B 4.B 5.C 6.A 7.C 8.A 9.D 二、填空题，在横线处填写合适内容（每小题2分，共14分）】 1.逻辑结构 2.下标（或顺序号） 3.n(n+1)/2 4.n-1 5.8 6.19 7.顶点 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1.错 2.对 3.对 4.错 5.对 6.错 7.对 四、运算题（每小题6分，共30分） 1.中序：c,b,a,e,d,f //2分 后序：c,b,e,f,d,a 1/2分 按层：a,b,d,c,e,f 112分 2.度为1的结点个数：5 /13分 平均搜索长度：37/12 113分 3.左子树为空的所有单支结点：15,23,42,44 /12分 右子树为空的所有单支结点：30 /12分 所有叶子结点：26,48,74 /2分 4.(1)1,2,4,5,3,6 //3分 (2)1,2,3,4,5,6 /13分 5.最大堆：{64,45,56,23,41,15,27,16} 五、算法分析题（每小题6分，共12分） 1.pl=pl->link,p=p->link //每空3分 2.生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右 子树（或左、右孩子的值）交换的结果。 73试卷代号:1010 中央广播电视大学2007-2008学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题答案及评分标准 (供参考) 2008年 1月 一、单项选择题 ，在括号内填写所选择的标号(每小题·2分，共 18分) 1. C 6. A 2. C 3.B 4. B 5.C 7. C 8. A 9. D 二、填空题 。在横线处填写合适内容(每小题 2分 ，共 14分) 1.逻辑结构 5.8 2.下标(或顺序号) 6. 19 3. n(n-F-1)/2 7，顶 点 4. n一 1 三、判断题，在每小题前面打对号表示正确或打叉号表示错误(每小题2分，共14分) 1.错 2.对 3.对 4.错 5.对 6.错 7.对 四、运算题 (每小题 6分，共 30分) 1.中序 :c,b,a,e,d,f //2分 后序 ;c,b,e,f,d,a //2分 按层 :a,b,d,c,e,f //2分 2.度为 1的结点个数 :5 //3分 平均搜索长度:37/12 //3分 3.左子树为空的所有单支结点:15,23,42,44 //2分 右子树为空的所有单支结点:30 //2分 所有叶子结点 :26,48,74 //2分 4.(1)1，2，4，J，3，G //3分 (2) 1,2，3，4，5，6 //3分 5.最大堆 :{64,45,56,23,41,15,27,16} 五、算法分析题 (每小题 6分 ，共 12分) l, pl=pl一>link,p= }。一、link //每空 3分 2.生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树 13"I}中所有结点的左、右 子树(或左 、右孩子的值)交换的结果。 7;3