试卷代号：1010 中央广播电视大学2008一2009学年度第二学期“开放本科"期末考试 数据结构 试题答案及评分标准 (供参考) 2009年7月 一、单项选择题（在括号内填写所选择的标号，每小题2分，共18分） 1.B 2.A 3.A 4.C 5.B 6.C 7.C 8.D 9.C 二、填空题（在横线处填写合适的内容，每小题2分，共14分）】 1.相同 2.MaxSize-1 3.31 4.最大值 5.n-1 6.O(1og2n) 7.2 三、判断题（在每小题前面打对号表示正确或打叉号表示错误，每小题2分，共14分） 1.X 2.√ 3.V 4.X 5.X 6.V 7.X 四、运算题（每小题6分，共30分】 1.分支结点数：4、叶子结点数：3 /1全对给6分，否则0分 2.深度搜索顶点序列：a,b,d,e,c 1/3分 广度搜索顶点序列：a,b,d,e,c /3分 3.评分标准：对1个给1分，全对给6分。 顶点： 0 1 2 3 4 5 路径长度： 01610.142521 4.查找23、68、84的搜索长度分别为：1、3、4 //每个数据占2分 5.最大堆：{62,40,53,25,36,30,46) 76试卷代号:1010 中央广播电视大学2008-2009学年度第二学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2009年 7月 一、单项选择题 (在括号内填写所选择的标号 ，每小题 2分 ，共 18分) 1.B 6.C 2.A 3.A 7.C 8.D 二、填空题(在横线处填 写合适的内容 ，每小题 2分 ，共 1.相 同 4.C 9. C 14分) 5.召 2. MaxSize一 1 3. 31 4.最大值 5. n一 1 6. O(1092n) 7. 2 三、判断题(在每小题前面打对号表示正确或打叉号表示错误，每小题2分，共 14分) 1.火 2.丫 3.侧 4.只 5.又 6.丫 7.X 四、运算题(每小题 6分，共 30分) 1.分支结点数:4、叶子结点数:3 /全对给6分，否则。分 2.深度搜索顶点序列:a,b,d,e,c //3分 广度搜索顶点序列:a,b,d,e,c //3分 3.评分标准:对 1个给 1分，全对给 6分。 顶点 : 路径长度: 4.查找 23, 5.最大堆 : 0 1 2 3 4 5 1。}16}10!14!25}21 68,84的搜索长度分别为:1,3,4 {62，40，53，25，36，30，46} 刀每个数据占2分