【考研类试卷】计算机专业基础综合数据结构（概论）历年真题试卷汇编2及答案解析.doc

1、计算机专业基础综合数据结构（概论）历年真题试卷汇编 2 及答案解析(总分：88.00，做题时间：90 分钟)一、单项选择题(总题数：11，分数：22.00)1.数据元素之间的关系称为( )。【北京理工大学 2006 九、2(1 分)】（分数：2.00）A.操作B.结构C.数据对象D.数据集合2.(多选)一个算法具有( )等特点。【华中科技大学 2007 二、17(2 分)】（分数：2.00）A.有 0 个或多个输入量B.健壮性C.正确性D.可行性3.下面程序的时间复杂性为( )。【南京理工大学 2004 一、4(1 分)】for(int i=0；iA.O(n 2 )B.O(m*n)C.O(m

2、2 )D.O(m+n)4.在下列算法中，“x=x*2”的执行次数是( )。【华中科技大学 2006 一、16(2 分)】int suanfa(int n)int i，j，x=1;for(i=0；iA.m(n+1)2B.Nlog 2 nC.n 2D.n(n 一 1)25.执行下列算法 suanfa2(1000)，输出结果是( )。【华中科技大学 2006 一、17(2 分)】void suanfa2(int n)int i=i;while(in： for(int i=0;imi; change(m，0，n 一 1)； for(i=0；in： for(int i=0;imi; change(m，0

3、，n 一 1)； for(i=0；in；i+)coutmi_正确答案：(正确答案：1 0 8 2 6 4 5 7 3 9 1)解析：40.请简要列出影响一个算法(或程序)时间效率的主要因素，并指出其中与算法(或程序)本身直接有关的因素。【北京航空航天大学 2008 一、1(4 分)】（分数：2.00）_正确答案：(正确答案：事先估算算法运行时间主要考虑问题的“规模”和算法执行的“基本操作”的次数。问题 “规模”指待解决问题的数量，如查找中元素的个数，元素个数越多，查找需要的时间越长，这是影响算法运行时间的主要因素。“基本操作”是算法在解决某问题时的主要操作，如在查找运算中元素间的比较操作可以看

4、作是基本操作，执行基本操作的次数越少，运行时间越短，执行基本操作的次数越多，运行时间就越长。)解析：41.调用下列 C 函数 f(n)(略去 Pascal 函数 f(n)编者注)，回答下列问题： (1)试指出 f(n)值的大小，并写出 f(n)值的推导过程；(2)假定 n=5，试指出 f(5)值的大小和执行 f(5)时的输出结果。C 函数： int f(int n) int i，j，k，flum=0； for(i=1; ii 一 1；j 一一) for(k=1；k_正确答案：(正确答案：第一层 for 循环判断 n+1 次，往下执行 n 次，第二层 for 循环执行次数为(n+n 一1)(n

5、一 2)+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表： )解析：42.有下列运行时间函数： (1)T 1 (n)=1000; (2)T 2 (n)=n 2 +1000n； (3)T 3 (n)=3n 3 +100n 2 +b+1；分别写出相应的大 O 表示的运算时间。 【吉林工业大学 1999 二(12 分)】（分数：2.00）_正确答案：(正确答案：(1)O(1) (2)O(n 2 ) (3)O(n 2 )解析：斐波那契数列 F n 定义如下：F 0 =0， F 1 =1， F n =F n-1 +F n-2 ， n=2，3，请就此斐波那契数列回答下列问题。（分数：4

6、.00）(1).在递归计算 F n 的时候，需要对较小的 F n-1 ，F n-2 ，F 1 ，F 0 精确计算多少次?（分数：2.00）_正确答案：(正确答案：由斐波那契数列的定义可得： F n =F n-1 +F n-2 =2F n-2 +F n-3 =3F n-3 +2F n-4 =5F n-4 +3F n-5 =pF 1 +qF 0 设 F m 的执行次数为 B m (m=0、1、2、n 一 1)，由以上等式可知，F n-1 被执行一次，即 B n-1 =1；F n-2 被执行两次，即 B n-2 =2;直至 F 1 被执行 p 次、F 0 被执行 q 次，即 B 1 =p，B 0 =q。B m 的执行次数为前两个等式第一因式系数之和，即 B m =B m-1 +B m-2 再有 B n-1 =1和 B n-2 =2，这也是一个斐波那契数列。可以解得： )解析：(2).如果用大 O 表示法，试给出递归计算 F n 时递归函数的时间复杂度是多少。【清华大学 2000 二(12分)】（分数：2.00）_正确答案：(正确答案：时间复杂度为 O(n)。)解析：