数据结构习题及答案D ）O(n )D ）O(n )D ）O(n ) 第 1 章算法一、选择题1. 算法的时间复杂度是指（）。
A ）执行算法程序所需要的时间B ）算法程序中的指令条数C ）算法执行过程中所需要的基本运算次数D ）算法程序的长度2. 算法的空间复杂度是指（）。
A ）算法程序的长度 B ）算法程序所占的存储空间C ）算法执行过程中所需要的存储空间D ）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。
A ）O(n ) C ）O(n log 2 n )B ）O( log 2 n )24.下面累加求和程序段的时间复杂度为（）。
int sum(int a[],int n){int i, s=0; for (i=0;i<="" a="" bdsfid="82" c="" p="" return="" s+="a[i];" s;="" }="" ）o(1="" ）o(n="">B ）O( log 2 n )25.下面是将两个 n 阶矩阵 a[][]与 b[][]相加的结果存放到 n 阶矩阵c[][]中的算法，该算法的时间复杂度为（）。
void matrixadd(int a[][],int b[][],c[][],int n) { int i,j;for (i=0;i<="">A ）O(1 )C ）O( n )B ）O( log 2 n )26.下面程序段的时间复杂度为（）。
D ）O(n )int i=0,s1=0,s2=0; while(i<="">if(i%2) s1+=i; else s2+=i; i++; } A ）O(1 )C ）O(n )B ）O( log 2 n )27.下面程序段的时间复杂度为（）。
int prime(int n) { int i=1;int x=(int)sqrt(n); while(i<=x) { i++; if(n%i==0) break; } if(i>x) return 1; else return 0;} A ）O(1 ) C ）O(n )B ）O( log 2 n )D ）O( n )8.下面程序段的时间复杂度为（）int fun(int n){int i=1,s=1; while(s<="">i++; s+=i; } return i; } A ）O(n/2)B ）O( log 2 n )A ）O(m )B ）O(n )D ）O(n )2.一个算法的时间复杂度的计算式为 ( 3n +2n+5 ) / n ，其数量级表示为 C ）O(n )D ）O( n )9.下面程序段的时间复杂度为（）int i,j,m,n,a[][];for(i=0;i2C ）O(m*n ) 2D ）O(m+n) 10. 下面程序段的时间复杂度为（）int sum1(int n) {int i,p=1,s=0; for(i=1;i<=n;i++) {p*=i; s=s+p; } return s; } A ）O(1 ) C ）O(n )二、填空题B ）O( log 2 n ) 21.算法复杂度主要包括时间复杂度和复杂度。
23.从一维数组a[n]中顺序查找出一个最大值元素的平均时间复杂度为。
，读取一个二维数组b[m][n]中任一元素的时间复杂度为4.在下面程序段中，s = s+p 语句的执行次数为。
，p*=j 语句的执行次数为，该程序段的时间复杂度为int i=0, s=o; while(++i <=n) { int p=1;for(int j=1; j<=i ; j++ )p*=j ; s=s+p ; }5. 通常用平均性态分析和三、简答题1. 什么是算法？2. 算法的基本特征是什么？。
两种方式来确定一个算法的工作量。
4. n ，n(n+1)/2，O(n 2)3. 算法的两种基本要素是什么？4. 递归是算法的基本方法之一，其基本思想是什么？5. 算法的描述方法有多种，试说出任意三种方法。
四、编写出求下列问题的算法1.比较两个整型数据 a1 与 a2 的大小，对于 a1 > a2、a1 == a2、a1< a2 这三种不同情况应分别返回“>”、“=”、“<”字符。
2.求一维 double 型数组 a[n]中的所有元素之乘积。
3.假定一维整型数组a[n]中的每个元素值x 均在[0，200]区间内，分别统计出落在0≤x < 20、20≤x<50、50≤x<80、80≤x<130、13 ≤x ≤200 各区间内的元素个数。
参考答案一、单选题 1.C 2.C 6.C 7.D 3.B 8.D4.C 9.C5.D 10.C二、填空题 1. 空间 3.O(n)，O(1) 2. O(n)5. 最坏情况复杂性三、简答题1. 答案：所谓算法是指解题方案的准确而完整的描述。
2. 答案：算法的基本特征为：1)可行性；2)确定性；3)有穷性；4)拥有足够的情报。
3. 答案：算法通常由两种基本要素组成；一是对数据对象的运算和操作；二是算法的控制结构。
4. 答案：人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归结为一些最简单的问题。
这种将问题逐层分解的过程，实际上并没有对问题进行求解。
而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。
5.答案：一个算法可以用多种方式来描述，如自然语言、程序语言、流程图等。
四、算法设计1.比较两个整型数据 a1 与 a2 的大小。
char compare(int a1,int a2) { if(a1>a2) return ">"; elase if(a1==a2)return"=";elasereturn "<";}2.求一维double 型数组a[n]中的所有元素之乘积。
double product(dluble a[],int n){double p=1;for(int i=0;i< n;i++)p=p*a[i];return p;}3.统计数组a[n]中的每个元素值x 分别落在0≤x<20、20≤x<50、50≤x< 80、80≤x<130、130≤x≤200 各区间内的元素个数。
int count(int a[],int n,int c[5]) {int d[5]={20,50,80,130,201}; int i,j;for(i=0;i<n;i++)< bdsfid="208" p=""></n;i++)<>c[i]=0;for(i=0;i<n;i++)< bdsfid="211" p=""></n;i++)<>{if(a[i]<0; || a[i]>200)return 0;for(j=0;j< 5;j++)if(a[i]<="" p="">c[j]++;}return 1; //用c[5]保存统计结果//用d[5]保存各统计区间上限//数组中数据有错，统计失败//查找a[i]所在区间//使统计相应区间的元素数增1//表示统计成功}第2 章数据结构的基本概念一、单选题1.一个数据结构可形象地表示成B=(D,R)，其中D 是（①）的有限集合，R 是D 上的（②）有限集合。
①A）算法C）数据操作②A）操作C）存储B）数据元素D）逻辑结构B）映像D）关系2. 数据结构在计算机存储空间中的存放形式称为（）。
A）数据元素之间的关系C）数据的存储结构B）数据结构D）数据的逻辑结构3. 下列叙述中正确的是（）。
A）一个逻辑结构只能有一种存储结构B）数据逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率4. 在数据结构中，与所使用的计算机无关的是数据的（）结构。
A）逻辑C）逻辑和存储B）存储D）物理5. 在存储数据时，通常不仅需要存储各数据元素的值，而且还要存储（）。
A）数据的处理方法C）数据元素之间的关系B）数据元素的类型D）数据的存储方法6. 如果一个非空的数据结构满足两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为（）。
A）线性结构C）物理结构B）非线性结构D）逻辑结构7. 数据的（）包括插入、删除、查找、更新、排序等操作类型。
A）存储结构C）基本运算8. 数据的存储结构是指（）。
A）数据所占的存储空间C）存储在外存中的数据B）逻辑结构D）算法描述B）数据的逻辑结构在计算机中的表示D）数据在计算机中的顺序存储方式9. 在决定选取何种存储结构时，一般不考虑（）。
A）结点个数的多少C）对数据有哪些运算B）各结点的值如何D）所用编程语言实现这种结构是否方便10.以下说法正确的是（）。
A）数据元素是数据的最小单位B）数据项是数据的基本单位C）数据结构是带结构的各数据项的集合D）一些表面上很不相同的数据，可以有相同的逻辑结构11.在数据结构中，从逻辑上可以把数据结构分成（）。
A）动态结构和静态结构B）紧凑结构和非紧凑结构C）线性结构和非线性结构D）内部结构和外部结构12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A）数据元素具有同一特点B）不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C）每个数据元素都一样D）数据元素所包含的数据项的个数要相等二、填空题1.数据的基本单位是，数据的最小单位是。
2. 一种数据的逻辑结构，根据需要可以表示成顺序、基本存储结构。
、和散列四种3. 根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据分为类型。
两大4. 在一个线性结构中插入或删除任何一个结点后还应是5.一种数据结构的元素集合为D，它在D 上的二元关系R 为：D={a,b,c,d,e,f,g,h}R={,,,,,,}。
