【数据结构】——数据结构概论习题_数据结构 习题 scdn

一、数据元素和数据项

1、在数据结构中，数据的基本单位是（），最小单位是（）。
A、数据元素、数据项
B、数据项、数据元素
C、数据类型、数据变量
D、数据变量、数据类型

解析：（A）
数据由数据元素组成，即数据元素是数据的基本单位，而数据元素又由若干个数据项组成，所以，数据项是组成数据元素的最基本、不可分割的最小单位。

二、数据对象

1、数据对象是指（）。
A、描述客观事物且由计算机处理的数值、字符等带符号的总称
B、数据的基本单位
C、性质相同的数据元素的集合
D、相互之间存在一种或多种特定关系的数据元素的集合

解析：（C）
具有相同性质的数据元素集合称为数据对象；
数据的基本单位是数据元素；
描述客观事物且由计算机处理的数值、字符等带符号的总称是数据；
相互之间存在一种或多种特定关系的数据元素的集合指的是数据结构。

三、抽象数据类型

1、在定义ADT时，除了数据对象和数据关系外，还需说明（）。
A、数据元素
B、数据项
C、基本操作
D、算法

解析：（C）
抽象数据类型（ADT）是指由用户定义，即用数学化的语言来定义数据的逻辑结构、运算等等，从而表示的数学模型，它包括三个部分，数据对象、数据对象上关系的集合、对数据对象的基本操作的集合，简单可概括为数据对象、数据关系和基本操作。

2、可以用（）定义一个完整的数据结构。
A、数据元素
B、数据对象
C、数据关系
D、抽象数据类型

解析：（D）
可以用抽象数据类型定义一个完整的数据结构。

四、逻辑结构

1、以下属于逻辑结构的是（）。
A、顺序表
B、哈希表
C、有序表
D、单链表

解析：（C）
有序表是关键字有序的线性表，它是线性结构，可以顺序存储和链式存储，故属于逻辑结构。而其他三种是不同的数据结构，即描述逻辑结构，又描述存储结构和数据运算。

2、（多选）下列数据结构中，（）是非线性数据结构。
A、树
B、图
C、字符串
D、队列
E、栈

解析：（AB）
逻辑结构分为线性结构和非线性结构，如下：
线性结构是一对一的关系，例如一维数组、线性表、栈、队列、串等；
非线性结构是一对多或多对多的关系，例如二维数组（多维数组）、广义表、树、图等。

3、（判断）数据的逻辑结构与数据元素本身的内容和形式无关。

解析：（√）

4、（判断）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而可以得到不同的数据结构。

解析：（×）
错误，例如栈和队列的逻辑结构都是相同的（线性结构，都是操作受限制的线性表），存储结构也相同（顺序和链式），但由于其运算集合不同，从而成为不同的数据结构。

五、存储结构（物理结构）

1、每个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，这种存储方式是（）。
A、顺序
B、链式
C、索引
D、散列

解析：（C）
顺序存储由存储单元的邻接关系体现；链式存储不要求逻辑上相邻的元素物理位置上也相邻，通过指示元素存储地址的指针来体现元素之间的逻辑关系；索引存储在存储数据元素的同时还需要建立附加的索引表，其中的索引项的形式为关键字和地址；散列存储是根据数据元素的关键字直接计算其存储地址，也称为哈希存储（Hash）。

2、链式存储的存储结构所占存储空间（）。
A、分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针
B、只有一部分，存放结点的值
C、只有一部分，存放表示结点间关系的指针
D、分两部分，一部分存放结点的值，另一部分存放结点所占单元素

解析：（A）
链式存储的存储结构所占存储空间分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针。（结点内的存储单元要求连续，而不同结点的存储空间可以不连续）

3、以下与数据的存储结构无关的术语是（）。
A、循环队列
B、链表
C、哈希表
D、栈

解析：（D）
循环队列用到了顺序存储结构，链表用到了链式存储结构，哈希表用到了散列存储结构，而栈是一种抽象数据类型，是一种逻辑结构，其顺序存储结构为顺序栈，链式存储结构为链栈。

4、二维数组A[m][n]以行为主顺序存储，每个元素占用l个存储单位。元素A[0][0]的存储地址是b，则元素A[i][j]（0≤i≤m-1，0≤j≤n-1）的存储地址是（）。
A、b + ( i * n + j ) * l
B、b + i * j * l
C、b + ( i + j ) * l
D、b + ( ( i - 1 ) * n + ( j - 1 ) ) * l

解析：（A）
元素A[i][j]的前面一共有i行元素，每行元素有n个，A[i][j]为本行的第j+1个元素，j个元素位于其前面，所以共有i * n + j个元素，每个元素占用l个存储单位，乘以l，另外加上元素A[0][0]的存储地址，即元素A[i][j]的存储地址是b + ( i * n + j ) * l。

六、算法的概念

1、算法分析的目的是（）。
A、找出数据结构的合理性
B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进
D、分析算法的易懂性和文档性

解析：（C）
算法通过计算机算法语言描述，是计算机解一类问题的精确、有效的方法，算法分析是对一个算法需要多少计算时间和存储空间作定量的分析，所以其目的是分析算法的效率以求改进。

2、（多选）设计一个″好″的算法应考虑达到的目标是（）。
A、可行性
B、健壮性
C、无二义性
D、可读性好的

解析：（B、D）
设计一个具有正确性、可读性、健壮性、高效率（执行速度快，时间复杂度低）和低存储（不费内存，空间复杂度低）的算法，再加上合适的数据结构，从而构成一个良好的程序。

七、时间复杂度

1、算法的时间复杂度取决于（）
A、问题的规模
B、待处理的数据的初态
C、A和B
D、以上都不是

解析：（C）

2、计算算法的时间复杂度是属于一种（）。
A、事前统计的方法
B、事前分析估算的方法
C、事后统计的方法
D、事后分析估算的方法

解析：（B）
时间复杂度是对算法运行时间的数量级，有两种度量方法，分别是事前分析估算法和事后统计法。

3、下列程序段的时间复杂度是（）。
A、O(nlog₂n)
B、O(n²)
C、O(n)
D、O(log₂n)

count=0;
for(k=1;k<=n;k*=2)
	for(j=1;j<=n;j++)
		count++;
1
2
3
4

解析：（A）
由for循环决定，假设最外层m次循环结束，则有2^m+k=n，可得：m=log₂n，即变量k成倍数增加，呈现出log对数关系。另外，内层for循环n次，所以该程序段的时间复杂度，即O(n)=n×log₂n=nlog₂n。

4 、下列程序段的时间复杂度是（）。
A、O(nlog₃n)
B、O(log₃n)
C、O(n²)
D、O(n³)

i=1;
while(i<=n)
	i=i*3;
1
2
3

解析：（B）
循环次数由i³=n，可得O(log₃n)，即变量i成倍数增加，呈现出log对数关系。

5、下列程序段的时间复杂度是（）。
A、O(logn)
B、O(n^1/2)
C、O(n)
D、O(n²)

x=0;
while(n>=(x+1)*(x+1))
	x=x+1;
1
2
3

解析：（B）
执行k次while()循环，每循环一次，x加1，最终x=k，故n≥k²，得O(n^1/2)。

6 、下列程序段的时间复杂度是（）。
A、O(log₂n)
B、O(n)
C、O(n²)
D、O(nlog₂n)

int fact(int n){
	if(n<=1)
		return 1;
	return n*fact(n-1)
}
1
2
3
4
5

解析：（B）
由于是n次阶乘，n个数相乘，一共执行n次递归调用fact()函数，所以即为O(n)。