数据结构习题及答案概论
第1章算法
一、选择题
1.算法的时间复杂度是指（）。
A）执行算法程序所需要的时间
B）算法程序中的指令条数
C）算法执行过程中所需要的基本运算次数
D）算法程序的长度
2.算法的空间复杂度是指（）。
A）算法程序的长度
B）算法程序所占的存储空间
C）算法执行过程中所需要的存储空间
D）算法程序中的指令条数
3.下面（）的时间复杂度最好（即执行时间最短）。
log)
A）O(n ) B）O(n
2
log ) D）O(n2)
C）O(n n
2
4.下面累加求和程序段的时间复杂度为（）。
int sum(int a[],int n)
{
int i, s=0;
for (i=0;i s+=a[i]; return s; } log ) A）O(1 ) B）O(n 2 C）O(n ) D）O(n2) 5.下面是将两个n阶矩阵a[][]与b[][]相加的结果存放到n阶矩阵c[][]中的算法， 该算法的时间复杂度为（）。 void matrixadd(int a[][],int b[][],c[][],int n) { int i,j; for (i=0;i for(j=0;j c[i][j]=a[i][j]+b[i][j]; } log) A）O(1 ) B）O(n 2 C）O( n ) D）O(n2) 6.下面程序段的时间复杂度为（）。 int i=0,s1=0,s2=0; while(i { if(i%2) s1+=i; else s2+=i; i++; } log) A）O(1 ) B）O(n 2 C）O(n ) D）O(n2) 7.下面程序段的时间复杂度为（）。 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; } log) A）O(1 ) B）O(n 2 C）O(n ) D）O(n) 8.下面程序段的时间复杂度为（） int fun(int n) { int i=1,s=1; while(s { i++; s+=i; } return i; } log) A）O(n/2) B）O(n 2 C）O(n ) D）O(n) 9.下面程序段的时间复杂度为（） int i,j,m,n,a[][]; for(i=0;i for(j=0;j a[i][j]=i*j; A）O(m2) B）O(n2 ) C）O(m*n ) D）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; } log) A）O(1 ) B）O(n 2 C）O(n ) D）O(n2) 二、填空题 1.算法复杂度主要包括时间复杂度和复杂度。 2.一个算法的时间复杂度的计算式为 ( 3n2+2n+5 ) / n ，其数量级表示为。 3.从一维数组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. 通常用平均性态分析和两种方式来确定一个算法的工作量。 三、简答题 3.什么是算法？ 4.算法的基本特征是什么？ 5.算法的两种基本要素是什么？ 6.递归是算法的基本方法之一，其基本思想是什么？ 7.算法的描述方法有多种，试说出任意三种方法。 四、编写出求下列问题的算法 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 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) 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 "="; elase return "<"; } 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]) //用c[5]保存统计结果 { int d[5]={20,50,80,130,201}; //用d[5]保存各统计区间上限 int i,j; for(i=0;i c[i]=0; for(i=0;i { if(a[i]<0; || a[i]>200) return 0; //数组中数据有错，统计失败 for(j=0;j< 5;j++) if(a[i] c[j]++; //使统计相应区间的元素数增1 } return 1; //表示统计成功 } 第2章数据结构的基本概念 一、单选题 1.一个数据结构可形象地表示成B=(D,R)，其中D是（①）的有限集合，R是D上的（②）有限集合。 ① A）算法 B）数据元素 C）数据操作 D）逻辑结构 ② A）操作 B）映像 C）存储 D）关系 2. 数据结构在计算机存储空间中的存放形式称为（）。 A）数据元素之间的关系 B）数据结构 C）数据的存储结构 D）数据的逻辑结构 3. 下列叙述中正确的是（）。 A）一个逻辑结构只能有一种存储结构 B）数据逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率 4. 在数据结构中，与所使用的计算机无关的是数据的（）结构。 A）逻辑 B）存储 C）逻辑和存储 D）物理 5. 在存储数据时，通常不仅需要存储各数据元素的值，而且还要存储（）。 A）数据的处理方法 B）数据元素的类型 C）数据元素之间的关系 D）数据的存储方法 6. 如果一个非空的数据结构满足两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为（）。 A）线性结构 B）非线性结构 C）物理结构 D）逻辑结构 7. 数据的（）包括插入、删除、查找、更新、排序等操作类型。 A）存储结构 B）逻辑结构 C）基本运算 D）算法描述 8. 数据的存储结构是指（）。 A）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示 C）存储在外存中的数据 D）数据在计算机中的顺序存储方式 9. 在决定选取何种存储结构时，一般不考虑（）。 A）结点个数的多少 B）各结点的值如何 C）对数据有哪些运算 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={ 则该数据结构具有结构。 6.一种数据结构的元素集合为D，它在D上的二元关系R为： D={a,b,c,d,e,f,g,h} R={ 则该数据结构具有结构。 7.数据的逻辑结构分为线性结构和非线性结构，其中的非线性结构有两种基本类型。 三、简答题 1.数据结构主要研究的三个问题是什么？ 2.一个数据结构应包含两方面的信息是什么？ 3.简述数据存储结构中的顺序存储方式。 4.简述数据存储结构中的链式存储方式 参考答案 一、单选题 1.①B，②D 2. C 3.D 4.A 5.C 6.A 7.C 8.B 9.B 10.D 11.C 12.B 二、填空题 1. 数据元素，数据项 2. 链式、索引 3. 线性结构与非线性结构 4. 线性结构 5. 线性 6.非线性（或树形） 7. 树和图 三、简答题 1.答案：数据结构主要研究的三个问题是：①数据的逻辑结构，②数据的存储结构， ③对各种数据结构进行的运算。 2.答案：一个数据结构应包含两方面的信息：①表示数据元素的信息；②表示各数据元素之间的前后件关系。 3. 答案：在数据的存储结构中，顺序存储方式的含义如下： 顺序存储方式：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现。 4. 答案：在数据的存储结构中，链式存储方式的含义如下： 链式存储方式：使用指针表示数据元素之间的逻辑关系，各个数据元素的存储位置可以随意，不要求逻辑上相邻的数据元素在物理位置上也相邻。 第3章线性表及其存储结构 一、单选题 1. 在一个长度为n的顺序存储的线性表中，向第i个元素（1 ≤i ≤n+1）位置插入一个新元素时，需要从后向前依次后移（）个元素。 A）n-i B）n–i+1 C）n–i-1 D）i 2. 在一个长度为n的顺序存储的线性表中，删除第i个元素（1 ≤i ≤n+1）时，需要从前向后依次前移（）个元素。 A）n-i B）n–i+1 C）n–i-1 D）i 3. 在一个长度为n的顺序表中，存在值为x的元素。在此表中用顺序搜索法，查找值为x的元素，在等概率情况下，查找成功时的平均查找长度为（）。 A）n B）n/2 C）(n+1)/2 D）(n - 1)/2 4. 在一个长度为n的顺序表中，删除值为x的元素时，需要比较元素的次数和移动元素次数的和为（）。 A）n/2 B）(n+1)/2 C）n D）n+1 5. 在一个顺序表的表尾，插入一个元素时的时间复杂度为（）。 log) A）O(1) B）O(n 2 C）O(n) D）O(n2) 6. 在一个顺序表的任意位置，插入一个元素的时间复杂度为（）。 log) A）O(1) B）O(n 2 C）O(n) D）O(n/2) 7. 线性表的顺序存储比链式存储最有利于进行（）操作。 A）查找 B）表尾插入或删除 C）按值插入或删除 D）表头插入或删除