一、选择题
1. 从逻辑结构上可以把数据结构分为( c )。
A. 静态结构和动态结构 B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构 D. 内部结构和外部结构
2. 顺序存储表示中数据元素之间的逻辑关系是由（ c ）表示的。
A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题的上下文
3. 链式存储表示中数据元素之间的逻辑关系是由（ A ）表示的。
A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题的上下文
4. 若某算法的时间复杂度是O(n2 ) ，表明该算法（ D ）。
A. 问题规模是n2 B. 执行时间是n2
C. 问题规模与n2成正比 D. 执行时间与n2成正比
5. 算法的时间复杂度与（A ）有关。
A. 问题规模 B. 计算机硬件的运行速度
C. 源程序的长度 D. 编译后机器代码的质量
6. 算法必须具备（ B ）这3个特性
A. 可执行性，可移植性，可扩充性 B. 可执行性，确定性，有穷性
C. 确定性，有穷性，稳定性 D. 易读性，稳定性，安全性
7. 下面程序段的时间复杂度为（ C ）。
for( i=0; i<m; i++)
for(j=0; j<n; j++)
a[i][j]=i*j;
A. O(m2) B. O(n2) C. O(m×n) D. O(m+n)
8. 以下程序段中，S语句的执行次数是（ C ）
for( i=1; i<=n; i++)
for(j=i; j<=n; j++)
S；
A. n B. n2 C. n(n+1)/2 D. n(n+1)
二、填空题
1. 数据元素之间的4种基本结构是：集合、 图结构 、 树结构 、 线性结构 。
2. 线性结构中元素的关系是一对一，树形结构中元素的关系是 一对多 ，图形结构中元素的关系是 多对多 。
3. 顺序存储结构中数据元素的存储位置与其 元素在数组的下标 是对应的。
4. 算法效率的度量方法有：事后统计方法和 事前分析估算的方法法 。
5. 一个好算法应达到的目标有： 正确性 、 可读性 、 健壮性 、 效率 、 低存储量 。
6. 抽象数据类型可细分为3种： 原子类型 、 固定聚合类型 和 可变聚合类型 。
7. 抽象数据类型的定义一般包括3方面： 数据对象 、 数据关系 、 基本操作 。
三、判断题
1. 数据结构主要研究非数值型数据。（ 对）
2. 数据的逻辑结构相同则对应的存储结构也相同。（错 ）
3. 数据的逻辑结构独立于其存储结构。（ 对 ）
4. 数据元素是数据的最小单位。（ 错 ）数据项
5. 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。（ 对 ）
6. 数据的逻辑结构与数据元素本身的内容和形式无关。（对 ）
7. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ 错 ）数据元素
8. 抽象数据类型只是一个数学模型。（ 错 ）
9. 算法和程序原则上没有区别，在 讨论数据结构时二者是通用的。（ 错 ）
10. 数据结构是数据元素的集合和该集合中各数据元素之间关系的集合。（ 对 ）
11. 顺序存储方式只能用于线性结构，不能用于非线性结构。（ 错 ）
四、简答题
1. 什么是数据结构，写出数据结构的形式定义。
2. 什么是算法，算法的5个特性是什么？
3. 数据的逻辑结构分为线性结构和非线性结构,这两类结构各自的特点是什么?
五、应用题
1. 按增长率从小到大的顺序排列下列各函数：
n2，n，
，n!，(2/3)n 。
2. 写出以下各函数的功能，并求出其时间复杂度。
(1) int fun1(int n)
{ int i, x;
i=2; x=(int )sqrt(n);
while(i<=x)
{ if (n%i==0) break;
i++;
}
if ( i>x) return 1;
else return 0;
}
(2) int fun2(int n)
{ int i, p=1, sum=0;
for( i=1; i<=n; i++)
{ p=p*i;
sum=sum+p;
}
return(sum);
}
(3) int fun3(int n)
{ int i, j, p, sum=0;
for( i=1; i<=n; i++)
{ p=1;
for(j=1; j<=i; j++)
p=p*j;
sum=sum+p;
}
return(sum);
}
本文含有隐藏内容，请 开通VIP 后查看