1、2007年北京航空航天大学计算机专业基础综合（数据结构）真题试卷及答案与解析 一、综合题 1 2 3 4 二、分析题 5 请写一非递归算法，该算法在按值严格递增排列的顺序表 A1 n中采用折半查找法查找值不小于 item的最小元素。若表中存在这样的元素，则算法给出该最小元素在表中的位置，否则，给出信息 0。 6 已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于一维数组BTO n 1中 (假设每个结点的数据信息为一个非 O整数；若数组元素值为 0，则表示该元素对应的 结点在二叉树中不存在 )。请写一算法，生成该二叉树的二叉链表结构。 2007年北京航空航天大学计算机专业基础综合（数据结构
2、真题试卷答案与解析 一、综合题 1 【正确答案】 2 【正确答案】 3 【正确答案】 (1)可能的出栈序列以及相应的操作序列分别为： c， b， a相应操作为： PUSH、 PUSH、 PUSH、 POP、 POP、 POP。 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 【正确答案】 采用深度优先遍历。如果从有向图中某个顶点 v出发进行遍历，遍历结束前出现了从顶点 u到顶点 v的回边，则可以断定图中包含了顶点 v到顶点u的回路。 二、分析题 5 【正确答案】 6 【正确答案】
