1、2007 年北京航空航天大学计算机专业基础综合(数据结构)真题试卷及答案解析(总分:12.00,做题时间:90 分钟)一、综合题(总题数:4,分数:8.00)1. (分数:2.00)_2. (分数:2.00)_3. (分数:2.00)_4. (分数:2.00)_二、分析题(总题数:2,分数:4.00)5.请写一非递归算法,该算法在按值严格递增排列的顺序表 A1n中采用折半查找法查找值不小于item 的最小元素。若表中存在这样的元素,则算法给出该最小元素在表中的位置,否则,给出信息0。(分数:2.00)_6.已知非空二叉树采用顺序存储结构,结点的数据信息依次存放于一维数组 BTOn1中(假设每个
2、结点的数据信息为一个非 O 整数;若数组元素值为 0,则表示该元素对应的结点在二叉树中不存在)。请写一算法,生成该二叉树的二叉链表结构。(分数:2.00)_2007 年北京航空航天大学计算机专业基础综合(数据结构)真题试卷答案解析(总分:12.00,做题时间:90 分钟)一、综合题(总题数:4,分数:8.00)1. (分数:2.00)_正确答案:(正确答案: )解析:2. (分数:2.00)_正确答案:(正确答案: )解析:3. (分数:2.00)_正确答案:(正确答案:(1)可能的出栈序列以及相应的操作序列分别为: c,b,a 相应操作为:PUSH、PUSH、PUSH、POP、POP、POP
3、。 b,C,a 相应操作为:PUSH、PUSH、POP、PUSH、POP、PoP。 a,c,b 相应操作为:PUSH、POP、PUSH、PUSH、POP、POP。 a,b,c 相应操作为:PUSH、POP、PUSH、POP、PUSH、POP。 b,a,c 相应操作为:PUSH、PUSH、POP、POP、PUSH、POP。 (2)不可能的出栈序列为 C,a,b。)解析:4. (分数:2.00)_正确答案:(正确答案:采用深度优先遍历。如果从有向图中某个顶点 v 出发进行遍历,遍历结束前出现了从顶点 u 到顶点 v 的回边,则可以断定图中包含了顶点 v 到顶点 u 的回路。)解析:二、分析题(总题数:2,分数:4.00)5.请写一非递归算法,该算法在按值严格递增排列的顺序表 A1n中采用折半查找法查找值不小于item 的最小元素。若表中存在这样的元素,则算法给出该最小元素在表中的位置,否则,给出信息0。(分数:2.00)_正确答案:(正确答案: )解析:6.已知非空二叉树采用顺序存储结构,结点的数据信息依次存放于一维数组 BTOn1中(假设每个结点的数据信息为一个非 O 整数;若数组元素值为 0,则表示该元素对应的结点在二叉树中不存在)。请写一算法,生成该二叉树的二叉链表结构。(分数:2.00)_正确答案:(正确答案: )解析: