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）_正确答案：(正确答案： )解析：
