[考研类试卷]2008年北京航空航天大学计算机专业基础综合（数据结构）真题试卷及答案与解析.doc

1、2008 年北京航空航天大学计算机专业基础综合（数据结构）真题试卷及答案与解析一、综合题1 请简要列出影响一个算法（或程序）时间效率的主要因素，并指出其中与算法（或程序）本身直接有关的因素。2 若 5 个元素 A,B,C,D,E 按此先后次序进入一初始为空的堆栈，请写出在所有可能的出栈序列，第一个元素为 C、且第二个元素为 D 的出栈序列。3 4 证明：具有 n 个顶点的无向图最多有 nn-1)/2 条边。5 有人说，采用折半查找法一定比采用顺序查找法的时间效率高，你认为如何？请说明你的理由。二、设计题6 7 2008 年北京航空航天大学计算机专业基础综合（数据结构）真题试卷答案与解析一、综合

2、题1 【正确答案】 影响一个算法（或程序）时间效率的主要因素有：*算法涉的问题的规模大小；*编译程序功能的强弱以及所产生的机器代码质量的优劣；*机器执行一条指令的时间长短；*算法（或程序）中诸如循环语句的那些关键语句的执行次数。2 【正确答案】 CDEBA CDBAE CDBEA3 【正确答案】 4 【正确答案】 5 【正确答案】 这种说法不正确。当被查找的对象处在序列的前部，比如查找序列的第一个元素，折半查找法的时间效率比顺序查找法要低。二、设计题6 【正确答案】 递归算法基本都可以采用非递归算法来实现，递归算法思想比较简单，但是需要更多的资源，实质仍然是采用堆栈来完成的。7 【正确答案】