1、2008 年北京航空航天大学计算机专业基础综合（数据结构）真题试卷及答案解析(总分：14.00，做题时间：90 分钟)一、综合题(总题数：5，分数：10.00)1.请简要列出影响一个算法（或程序）时间效率的主要因素，并指出其中与算法（或程序）本身直接有关的因素。（分数：2.00）_2.若 5 个元素 A,B,C,D,E 按此先后次序进入一初始为空的堆栈，请写出在所有可能的出栈序列，第一个元素为 C、且第二个元素为 D 的出栈序列。（分数：2.00）_3. （分数：2.00）_4.证明：具有 n 个顶点的无向图最多有 nn-1)/2 条边。（分数：2.00）_5.有人说，采用折半查找法一定比采用
2、顺序查找法的时间效率高，你认为如何？请说明你的理由。（分数：2.00）_二、设计题(总题数：2，分数：4.00)6. （分数：2.00）_7. （分数：2.00）_2008 年北京航空航天大学计算机专业基础综合（数据结构）真题试卷答案解析(总分：14.00，做题时间：90 分钟)一、综合题(总题数：5，分数：10.00)1.请简要列出影响一个算法（或程序）时间效率的主要因素，并指出其中与算法（或程序）本身直接有关的因素。（分数：2.00）_正确答案：(正确答案：影响一个算法（或程序）时间效率的主要因素有： *算法涉的问题的规模大小； *编译程序功能的强弱以及所产生的机器代码质量的优劣； *机器
3、执行一条指令的时间长短； *算法（或程序）中诸如循环语句的那些关键语句的执行次数。)解析：2.若 5 个元素 A,B,C,D,E 按此先后次序进入一初始为空的堆栈，请写出在所有可能的出栈序列，第一个元素为 C、且第二个元素为 D 的出栈序列。（分数：2.00）_正确答案：(正确答案：CDEBA CDBAE CDBEA)解析：3. （分数：2.00）_正确答案：(正确答案： )解析：4.证明：具有 n 个顶点的无向图最多有 nn-1)/2 条边。（分数：2.00）_正确答案：(正确答案： )解析：5.有人说，采用折半查找法一定比采用顺序查找法的时间效率高，你认为如何？请说明你的理由。（分数：2.00）_正确答案：(正确答案：这种说法不正确。当被查找的对象处在序列的前部，比如查找序列的第一个元素，折半查找法的时间效率比顺序查找法要低。)解析：二、设计题(总题数：2，分数：4.00)6. （分数：2.00）_正确答案：(正确答案： )解析：7. （分数：2.00）_正确答案：(正确答案： )解析：
