《数据结构》第一章练习题
1、单项选择题
1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。
①A 数据元素 B 计算方法 C 逻辑存储 D 数据映像
②A 结构 B 关系 C 运算 D 算法
1.2数据结构被形式的定义为（K,R ），其中K 是（ ）的有限集，R 是K 上的（ ）有限集。
①A 算法B 数据元素C 数据操作D 逻辑结构
②A 操作B 映像C 存储D 关系
1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。
A 动态结构和静态结构 B 紧凑结构和非紧凑结构
C 线性结构和非线性结构 D 内部结构和外部结构
1.4数据结构在计算机内存中的表示是指（ ）。
A 数据的存储结构 B 数据结构
C 数据的逻辑结构 D 数据元素之间的关系
1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
A 逻辑 B 存储 C 逻辑和存储 D 物理
1.6算法分析的目的是（) ，算法分析的两个主要方面是（ ）。
①A 找出数据结构的合理性 B 研究算法中输入与输出的关系
C 分析算法效率以求改进 D 分析算法的易懂性和文档性
②A 空间复杂度和时间复杂度 B 正确性和简明性
C 可读性和文档性 D 数据复杂性和程序复杂性
1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。 ①A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法
②A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性
C 确定性、有穷性和稳定性 D 易读性、稳定性和安全性
1.8在以下的叙述中，正确的是（ ）。
A 线性表和线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出
1.9在决定选择何种存储结构时，一般不考虑（ ）。
A 各结点的值如何 B 结点个数的多少
C 对数据有哪些运算 D 所用编程语言实现这种结构是否方便
1.10在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。 A 数据的处理方法 B 数据元素的类型
C 数据元素之间的关系 D 数据的存储方法
1.11下面说法错误的是（ ）。
（1）方法原地工作的含义是指不需要额外的辅助空间
（2）在相同的规模n 下，复杂度O （n ）的算法在时间上总是优于复杂度O （2n) 算法
（3）所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界
（4）同一个算法，实现语句的级别越高，执行效率越低
A （1） B （10（2） C （1）（4） D （3）
1.12通常要求同一逻辑结构中所有数据元素具有相同的特性，这意味着（ ）。 A 数据元素具有同一特点
B 不仅数据元素所包含的数据项个数要相同，而且对应的数据项类型要一致
C 每个数据元素都一样
D 数据元素所包含的数据项的个数要相等
1.13以下说法正确的是（ ）。
A 数据元素师数据的最小单位
B 数据项是数据的基本单位
C 数据结构是带结构的各数据项的集合
D 一些表面上很不相同的数据可以有相同的逻辑结构
2、设计与分析题
2.1设有数据逻辑结构为：
B=(K,R)
K={k1,k2,……，k9}
R={,,,}
画出这个逻辑结构的图示，并确定相对关系R ，哪些结点是开始结点，哪些结点是终端结点。
2.2设有如图所示的逻辑结构图示，给出它的逻辑结构。
2.3下面程序段的时间复杂度是（ ）。
for (i=0;i
for (j=0;j
A[i][j]=0;
2.4下面程序段的时间复杂度是（ ）。
i=s=0;
while (s
{
i++; //i=i+1
s+=i; //s=s+i
}
2.5下面程序段的时间复杂度是（ ）。
s=0;
for (i=0;i
for (j+0;j
s+=B[i][j];
sum=s
2.6下面程序段的时间复杂度是（ ）。
i=1
while(i
i=i*3;
2.7有如下递归函数fact(n),分析其时间复杂度。
fact(int n)
{ if (n
return 1;
else
return (n*fact(n-1))
}
2.8求两个n 阶矩形的乘法C=A*B,其算法如下：
#define MAX 100
V oid maxtrixmult(int n, float a[MAX][MAX]),b[MAX][MAX],float
{
int i,j,k;
float x;
for (i=1;
for (j=1;j
x=0; //③
for( k=1;k
x+=a[i][k]*b[k][j]; //⑤ c[MAX][MAX])
c[i][j]=x; //⑥ } } }
3、填空题。
1．数据的物理结构包括 的表示和 的表示。
2. 对于给定的n 个元素, 可以构造出的逻辑结构有 ， ， ，__ _四种。
3．数据的逻辑结构是指 。
4．一个数据结构在计算机中 称为存储结构。
5．抽象数据类型的定义仅取决于它的一组__ _，而与_ _无关，即不论其内部结构如何变化，只要它的数学特征不变，都不影响其外部使用。
6．数据结构中评价算法的两个重要指标是 。
7. 数据结构是研讨数据的_ _和_ _，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的 算法_。
8． 一个算法具有5个特性: 、 、 、 、 。
9. 下面程序段中带下划线的语句的执行次数的数量级是： 。
i=1； WHILE i
10. 下面程序段的时间复杂度为________。(n>1)
sum=1；
for (i=0;sum
4、简答题。
1. 数据结构是一门研究什么内容的学科？
2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？
3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？
4. 回答问题：
（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？
（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。
（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。
（4）评价各种不同数据结构的标准是什么？
5．评价一个好的算法，您是从哪几方面来考虑的？
6．解释和比较以下各组概念：
（1）算法的时间复杂性 ；
（2）算法；
（3）频度；
7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？
8．对于一个数据结构，一般包括哪三个方面的讨论？
9. 若将数据结构定义为一个二元组（D ，R ）, 说明符号D ，R 应分别表示什么？
10．数据的存储结构由哪四种基本的存储方法实现？
《数据结构》第一章练习题
1、单项选择题
1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。
①A 数据元素 B 计算方法 C 逻辑存储 D 数据映像
②A 结构 B 关系 C 运算 D 算法
1.2数据结构被形式的定义为（K,R ），其中K 是（ ）的有限集，R 是K 上的（ ）有限集。
①A 算法B 数据元素C 数据操作D 逻辑结构
②A 操作B 映像C 存储D 关系
1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。
A 动态结构和静态结构 B 紧凑结构和非紧凑结构
C 线性结构和非线性结构 D 内部结构和外部结构
1.4数据结构在计算机内存中的表示是指（ ）。
A 数据的存储结构 B 数据结构
C 数据的逻辑结构 D 数据元素之间的关系
1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
A 逻辑 B 存储 C 逻辑和存储 D 物理
1.6算法分析的目的是（) ，算法分析的两个主要方面是（ ）。
①A 找出数据结构的合理性 B 研究算法中输入与输出的关系
C 分析算法效率以求改进 D 分析算法的易懂性和文档性
②A 空间复杂度和时间复杂度 B 正确性和简明性
C 可读性和文档性 D 数据复杂性和程序复杂性
1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。 ①A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法
②A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性
C 确定性、有穷性和稳定性 D 易读性、稳定性和安全性
1.8在以下的叙述中，正确的是（ ）。
A 线性表和线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出
1.9在决定选择何种存储结构时，一般不考虑（ ）。
A 各结点的值如何 B 结点个数的多少
C 对数据有哪些运算 D 所用编程语言实现这种结构是否方便
1.10在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。 A 数据的处理方法 B 数据元素的类型
C 数据元素之间的关系 D 数据的存储方法
1.11下面说法错误的是（ ）。
（1）方法原地工作的含义是指不需要额外的辅助空间
（2）在相同的规模n 下，复杂度O （n ）的算法在时间上总是优于复杂度O （2n) 算法
（3）所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界
（4）同一个算法，实现语句的级别越高，执行效率越低
A （1） B （10（2） C （1）（4） D （3）
1.12通常要求同一逻辑结构中所有数据元素具有相同的特性，这意味着（ ）。 A 数据元素具有同一特点
B 不仅数据元素所包含的数据项个数要相同，而且对应的数据项类型要一致
C 每个数据元素都一样
D 数据元素所包含的数据项的个数要相等
1.13以下说法正确的是（ ）。
A 数据元素师数据的最小单位
B 数据项是数据的基本单位
C 数据结构是带结构的各数据项的集合
D 一些表面上很不相同的数据可以有相同的逻辑结构
2、设计与分析题
2.1设有数据逻辑结构为：
B=(K,R)
K={k1,k2,……，k9}
R={,,,}
画出这个逻辑结构的图示，并确定相对关系R ，哪些结点是开始结点，哪些结点是终端结点。
2.2设有如图所示的逻辑结构图示，给出它的逻辑结构。
2.3下面程序段的时间复杂度是（ ）。
for (i=0;i
for (j=0;j
A[i][j]=0;
2.4下面程序段的时间复杂度是（ ）。
i=s=0;
while (s
{
i++; //i=i+1
s+=i; //s=s+i
}
2.5下面程序段的时间复杂度是（ ）。
s=0;
for (i=0;i
for (j+0;j
s+=B[i][j];
sum=s
2.6下面程序段的时间复杂度是（ ）。
i=1
while(i
i=i*3;
2.7有如下递归函数fact(n),分析其时间复杂度。
fact(int n)
{ if (n
return 1;
else
return (n*fact(n-1))
}
2.8求两个n 阶矩形的乘法C=A*B,其算法如下：
#define MAX 100
V oid maxtrixmult(int n, float a[MAX][MAX]),b[MAX][MAX],float
{
int i,j,k;
float x;
for (i=1;
for (j=1;j
x=0; //③
for( k=1;k
x+=a[i][k]*b[k][j]; //⑤ c[MAX][MAX])
c[i][j]=x; //⑥ } } }
3、填空题。
1．数据的物理结构包括 的表示和 的表示。
2. 对于给定的n 个元素, 可以构造出的逻辑结构有 ， ， ，__ _四种。
3．数据的逻辑结构是指 。
4．一个数据结构在计算机中 称为存储结构。
5．抽象数据类型的定义仅取决于它的一组__ _，而与_ _无关，即不论其内部结构如何变化，只要它的数学特征不变，都不影响其外部使用。
6．数据结构中评价算法的两个重要指标是 。
7. 数据结构是研讨数据的_ _和_ _，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的 算法_。
8． 一个算法具有5个特性: 、 、 、 、 。
9. 下面程序段中带下划线的语句的执行次数的数量级是： 。
i=1； WHILE i
10. 下面程序段的时间复杂度为________。(n>1)
sum=1；
for (i=0;sum
4、简答题。
1. 数据结构是一门研究什么内容的学科？
2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？
3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？
4. 回答问题：
（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？
（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。
（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。
（4）评价各种不同数据结构的标准是什么？
5．评价一个好的算法，您是从哪几方面来考虑的？
6．解释和比较以下各组概念：
（1）算法的时间复杂性 ；
（2）算法；
（3）频度；
7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？
8．对于一个数据结构，一般包括哪三个方面的讨论？
9. 若将数据结构定义为一个二元组（D ，R ）, 说明符号D ，R 应分别表示什么？
10．数据的存储结构由哪四种基本的存储方法实现？