1、计算机专业基础综合数据结构（概论）历年真题试卷汇编 3 及答案与解析一、单项选择题1 数据元素之间的关系称为( )。【北京理工大学 2006 九、2(1 分)】（A）操作（B）结构（C）数据对象（D）数据集合2 (多选 )一个算法具有 ( )等特点。【华中科技大学 2007 二、17(2 分)】（A）有 0 个或多个输入量（B）健壮性（C）正确性（D）可行性3 下面程序的时间复杂性为( )。【南京理工大学 2004 一、4(1 分)】for(int i=0；in：for(int i=0;imi;change(m，0，n 一 1)；for(i=0；ii 一 1；j 一一)for(k=1；k4 时
2、，算法 A2 好于 A1。37 【正确答案】 从小到大排列为：logn，n 1/2+logn，n，nlogn ，n 2+logn，n 3，n 一n3+7n5，2 n/2，(32) n，n!，38 【正确答案】 (1)n(n+1)2 (2)n2 (3)O(n 2) (4)s=15，x=439 【正确答案】 1 0 8 2 6 4 5 7 3 9 140 【正确答案】 事先估算算法运行时间主要考虑问题的“规模” 和算法执行的“基本操作”的次数。问题 “规模 ”指待解决问题的数量，如查找中元素的个数，元素个数越多，查找需要的时间越长，这是影响算法运行时间的主要因素。“基本操作” 是算法在解决某问题时
3、的主要操作，如在查找运算中元素间的比较操作可以看作是基本操作，执行基本操作的次数越少，运行时间越短，执行基本操作的次数越多，运行时间就越长。41 【正确答案】 第一层 for 循环判断 n+1 次，往下执行 n 次，第二层 for 循环执行次数为(n+n 一 1)(n 一 2)+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：执行次数为(1+2+n)+(2+3+n)+n=n*(n+1) 2 一 n(n21)6。在 n=5 时，f(5)=55，执行过程中，输出结果为：sum=15 sum=29 sum=41 sum=50 sum=55 (每个输出应为单独一行)42 【正确答案
4、】 (1)O(1) (2)O(n 2) (3)O(n2)43 【正确答案】 由斐波那契数列的定义可得：F n=Fn-1+Fn-2=2Fn-2+Fn-3=3Fn-3+2Fn-4=5Fn-4+3Fn-5=pF1+qF0 设 Fm 的执行次数为 Bm(m=0、1、2、n 一 1)，由以上等式可知，F n-1 被执行一次，即 Bn-1=1；F n-2 被执行两次，即 Bn-2=2;直至 F1 被执行 p 次、F 0 被执行 q 次，即 B1=p，B 0=q。B m 的执行次数为前两个等式第一因式系数之和，即 Bm=Bm-1+Bm-2 再有 Bn-1=1 和 Bn-2=2，这也是一个斐波那契数列。可以解得：44 【正确答案】 时间复杂度为 O(n)。
