数据结构习题及参考答案

《数据结构习题及参考答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1章算法一、选择题1.算法的时间复杂度是指（）。A）执行算法程序所需要的时间B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2.算法的空间复杂度是指（）。A）算法程序的长度B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间D）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。A）O(n)B）O()C）O(n)D）O(n2)4.下面累加求和程序段的时间复杂度为（）。intsum(inta[],intn){inti,s=0;for(i=0;i

2、)5.下面是将两个n阶矩阵a[][]与b[][]相加的结果存放到n阶矩阵c[][]中的算法，该算法的时间复杂度为（）。voidmatrixadd(inta[][],intb[][],c[][],intn){inti,j;for(i=0;i

3、间复杂度为（）。intprime(intn){inti=1;intx=(int)sqrt(n);while(i<=x){i++;if(n%i==0)break;}if(i>x)return1;elsereturn0;}A）O(1)B）O()C）O(n)D）O()8.下面程序段的时间复杂度为（）intfun(intn){inti=1,s=1;while(s

4、=i*j;A）O(m2)B）O(n2)C）O(m*n)D）O(m+n)10.下面程序段的时间复杂度为（）intsum1(intn){inti,p=1,s=0;for(i=1;i<=n;i++){p*=i;s=s+p;}returns;}A）O(1)B）O()C）O(n)D）O(n2)二、填空题1.算法复杂度主要包括时间复杂度和复杂度。2.一个算法的时间复杂度的计算式为(3n2+2n+5)/n，其数量级表示为。3.从一维数组a[n]中顺序查找出一个最大值元素的平均时间复杂度为，读取一个二维数组b[m][n]中任一元素的时间复杂度为。4.在下面程序段中，s=s+p语句的执行次数为，p*=j语句的

5、执行次数为，该程序段的时间复杂度为。inti=0,s=o;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}5.通常用平均性态分析和两种方式来确定一个算法的工作量。三、简答题1.什么是算法？2.算法的基本特征是什么？571.算法的两种基本要素是什么？2.递归是算法的基本方法之一，其基本思想是什么？3.算法的描述方法有多种，试说出任意三种方法。四、编写出求下列问题的算法1.比较两个整型数据a1与a2的大小，对于a1>a2、a1==a2、a1”、“=”、“<”字符。2.求一维double型数组a[n]中的所

6、有元素之乘积。3.假定一维整型数组a[n]中的每个元素值x均在[0，200]区间内，分别统计出落在0≤x<20、20≤x<50、50≤x<80、80≤x<130、13≤x≤200各区间内的元素个数。参考答案一、单选题1.C2.C3.B4.C5.D6.C7.D8.D9.C10.C二、填空题1.空间2.O(n)3.O(n)，O(1)4.n，n(n+1)/2，O(n2)5.最坏情况复杂性三、简答题1.答案：所谓算法是指解题方案的准确而完整的描述。2.答案：算法的基本特征为：1)可行性；2)确定性；3)有穷性；4)拥有足够的情报。3.答案：算法通常由两种基本要素组成；一是对数据对象的运算和操作；二是

7、算法的控制结构。4.答案：人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解。而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。5.答案：一个算法可以用多种方式来描述，如自然语言、程序语言、流程图等。四、算法设计1.比较两个整型数据a1与a2的大小。charco