数据结构习题及答案（参考）.docVIP

第1章 算法 一、选择题 算法的时间复杂度是指（ ）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数 C）算法执行过程中所需要的基本运算次数 D）算法程序的长度 算法的空间复杂度是指（ ）。 A）算法程序的长度 B）算法程序所占的存储空间 C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数 3.下面（ ）的时间复杂度最好（即执行时间最短）。 A）O(n ) B）O() C）O(n ) D）O(n2) A）O(1 ) B）O( ) C）O(n ) D）O(n2) 5.下面是两个n阶矩阵a[][]与b[][]相加的结果存放到n阶矩阵c[][]中的算法，该算法的时间复杂度为（ ）i,j; for (i=0;in;i++) for(j=0;jn;j++) c[i][j]=a[i][j]+b[i][j]; } A）O(1 ) B）O() C）O( n ) D）O(n2) i=0,s1=0,s2=0; while(in) { if(i%2) s1+=i; else s2+=i; i++; } A）O(1 ) B）O( ) C）O(n ) D）O(n2) i=x) { i++; if(n%i==0) break; } if(ix) return 1; else return 0; } A）O(1 ) B）O() C）O(n ) D）O() A）O(n/2) B）O() C）O(n ) D）O() i,j,m,n,a[][]; for(i=0;im;i++) for(j=0;jn;j++) a[i][j]=i*j; A）O(m2) B）O(n2 ) C）O(m*n ) D）O(m+n) i; s=s+p; } return s; } A）O(1 ) B）O() C）O(n ) D）O(n2) i=0, s=o; while(++i =n) { int p=1; for(int j=1; j=i ; j++ ) p*=j ; s=s+p ; } 5. 通常用平均性态分析和 两种方式来确定一个算法的工作量。 简答题 什么是算法？ 算法的基本特征是什么？ 算法的两种基本要素是什么？ 递归是算法的基本方法之一，其基本思想是什么？ 算法的描述方法有多种，试说出任意三种方法。 四、编写出求下列问题的算法 1.比较两个整型数据a1与a2的大小，对于a1 a2、a1 == a2、a1 a2这三种不同情况应分别返回“”、“=”、“”字符。 2.求一维double型数组a[n]中的所有元素之乘积。 3.假定一维整型数组a[n]中的每个元素值x均在[0，200]区间内，分别统计出落在0≤x 20、20≤x50、50≤x80、80≤x130、13 ≤x≤200各区间内的元素个数。 参考答案 一、单选题 1.C 2.C 3.B 4.C 5.D 6.C 7.D 8.D 9.C 10.C 二、填空题 1. 空间 2. O(n) 3.O(n)，O(1) 4. n，n(n+1)/2，O(n2) 4. 答案：人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解。而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。 5.答案：一个算法可以用多种方式来描述，如自然语言、程序语言、流程图等。 四、算法设计 1.比较两个整型数据a1与a2的大小。 char compare(int a1,int a2) { if(a1a2) return ; elase if(a1==a2) return =; elase return ; } 2.求一维double型数组a[n]中的所有元素之乘积。 double product(dluble a[],int n) { double p=1; for(int i