《数据结构》习题集：第1章 绪论.doc

数据结构课后练习题 第1章 绪论
第1章 绪论
一、 选择题
1. 数据结构被形式定义为（D，S），其中D是（ B ）的有限集合，S是D上的（ H ）有限集合。
A、算法 B、数据元素 C、数据操作 D、逻辑关系 E、操作 F、映象 G、存储 H、关系
2. 数据结构是一门研究非数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算
的学科。
（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象
（2）A、结构 B、关系 C、运算 D、算法
3. 算法分析的目的是（ D ），算法分析的二个主要方面是（ C ）。
A、给出数据结构的合理性 B、研究算法中输入输出的关系
C、空间复杂性和时间复杂性 D、分析算法的效率以求改进
E、正确性和简明性 F、分析算法的易懂性和文档性
4. 在数据结构中，从逻辑上可以把数据结构分成（ C ）。
A、动态和静态结构 B、紧凑接和非紧凑结构
C、线性与非线性结构 D、内部结构和外部结构
5. 计算机算法指的是（ C ），它必具备输入、输出和（ E ）5 个特性。
A、计算方法 B、排序方法 C、解决问题的有限运算序列
D、可行性、可移植性和可扩充性 E、可行性、确定性和有穷性
6. 线性表的顺序存储结构是一种（ A ）的存储结构，线性表的链式存储结构是一种（ B ）。
A、随机存取 B、顺序存取 C、索引存取 D、散列存取
7. 算法的时间复杂度取决于（ A ）。
A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态
8. 线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ D ）。
A、必须是连续的 B、部分地址必须是连续的
C、一定是不连续的 D、连续不连续都可以
9. 在以下的叙述中，正确的是（ B ）。
A、线性表的顺序存储结构优于链式存储结构
B、二维数组是它的每个数据元素为一个线性表
C、栈的操作方式是先进先出
D、队列的操作方式是先进后出
10. 根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 ( A )。
A、集合中任何两个结点之间都有逻辑关系但组织形式松散
B、线性结构中结点按逻辑关系依次排列形成一条"锁链"
C、树形结构具有分支、层次特性，其形态有点像自然界中的树
D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
11. 以下说法正确的是( D )。
A、数据元素是数据的最小单位
B、数据项是数据的基本单位
C、数据结构是带有结构的各数据项的集合
D、数据结构是带有结构的数据元素的集合
二、 填空题
1. 数据逻辑结构包括（集合）、（线性）、(树型)、(图型)四种类型，树型和图型结构合称（非线性）。
2. 对于给定的n 个元素，可以构造出的逻辑结构有（集合）、（线性）、（树型）和（图形结构）四种。
3. 算法的五个重要特性是（有穷性）(确定性）、（可行性）、(输入)、(输出)。
4. 评价算法的性能从利用计算机资源角度看主要从（时间复杂度和空间复杂度）方面进行分析。
5. 线性结构中元素之间存在（一对一）关系，树型结构中元素之间存在（一对多）关系，图型结构中元素之间存在（多对多）关系。
6. 下面程序段的时间复杂度是（O(n)）。
i=s=0;
while(s<n) {i++;s++;}
7. 下面程序段的时间复杂度是（O(m*n)）。
s=0;
for(I=0;I<n;I++)
for(j=0;j<m;j++)
s+=a[i][j];
8. 所谓数据的逻辑结构指的是数据元素之间的 __逻辑关系_____。
9. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作_____。
10. 在线性结构中，开始结点__没有___直接前驱结点，其余每个结点有且只有_一个___个直接前驱结点。
11. 在树形结构中，根结点只有__一个____，根结点无前驱，其余每个结点有且只有___一个___直接前驱结点；叶子结点没有__后继____结点，其余每个结点的后继结点可以__任意个___。
12. 在图形结构中，每个结点的前驱结点和后继结点可以有__任意个_____。
13. 存储结构是逻辑结构的____物理______实现。
14. 从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__数据__、___数据元素___和_数据项___。
15. 根据需要，数据元素又被称为__结点____、___记录___、__元素___或__顶点__。
16. 通常，存储结点之间可以有_顺序存储__、__链式存储___、__索引存储__、__散列存储__四种关联方式，称为四种基本存储方式。
17. 通常从__正确性__、__可读性___、__健壮性__、__高效性__等几方面评价算法的(包括程序)的质量。
18. 一个算法的时空性能是指该算法的___时间复杂度___ 和__空间复杂度__ ， 前者是算法包含的__计算量__，后者是算法需要的__存储量__。
19. 在一般情况下，一个算法的时间复杂性是_问题规模__的函数。
20. 常见时间复杂性的量级有：常数阶O(__1__)、对数阶O(__log2 n __)、线性阶O ( __ n __)、平方阶O(___n2__)、和指数阶O(__2n __)。通常认为，具有指数阶量级的算法是__不可行__的。
21. 数据结构的基本任务是数据结构的__设计___和__实现__。
22. 数据对象是性质相同的 数据元素 的集合。
23. 抽象数据类型是指一个 数学模型 以及定义在该模型上的一组操作。
三、 判断题
1. 数据元素是数据的最小单位。×
2. 数据结构是带有结构的数据元素的集合。√
3. 数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。√
4. 数据项是数据的基本单位。×
5. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。√
6. 数据的物理结构是数据在计算机中实际的存储形式。√
7. 算法和程序没有区别，所以在数据结构中二者是通用的。×
8. 顺序存储结构属于静态结构，链式存储结构属于动态结构。×
四、 计算应用题
1. 设 n 为正整数。确定下列各程序段中前置以记号@的语句的频度。
（1）
I=1;k=0;
While(I<n-1){
k+=10*I; @
I++;
}
k=0;
for(I=1;I<=n;I++){
for(j=I;j<=n;j++)
k++; @
}
答案：n-2
(2)
I=1;j=0;
While(I+j<=n){
if(I>j) j++; @
else I++;
}
答案：n(n+1)/2
2. 指出下列两个算法的时间复杂度。
（1）
int sum1(int n){
int p=1,sum=0,I;
for(I=1;I<=n;I++){
p*=I;
sum+=p;
}
return(sum);
}
答案：O(n)
(2)
int sum2(int n){
int sum=0,I,j;
for(I=1;I<=n;I++){
p=1;
for(j=1;j<=I;j++)
p*=j;
sum+=p;
}
returm(sum);
}
答案：O(n2)
3. 简述下列术语：数据，数据元素，数据结构，数据对象。
解答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。
4. 逻辑结构与存储结构是什么关系?
解答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素及其之间的关系在计算机中的表示。
5. 将数量级210，n，n2，n3，nlog2n，log2n，2n， n1/2 ，n!，(2/3)n，n2/3，按增长率进行排列。
答案：（2/ 3）n，210，log2n， √n ，n，n2/3，nlog2n，n2，n3，2n，n!
4/4
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1