判断题
1-1. 若用链表来表示一个线性表，则表中元素的地址一定是连续的。
F,链式映射存储是随机的
1-4. 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。
T
1-5. N2logN 和NlogN2具有相同的增长速度。
F
1-6. 2N和NN具有相同的增长速度。
F
1-7.100logN是O(N)的。
F PTA得分答案是T， 正确答案应该是O(logN)
1-8.(NlogN)/1000是O(N)的。
F，求f(n)时忽略其系数
1-9. 在任何情况下，时间复杂度为O(n2) 的算法比时间复杂度为O(n*logn)的算法所花费的时间都长。
F，随着n值增大，各种数量级对应的n的值得增长速度是大不相同的，当n大于一定值后，各种不同的数量级对应的值存在：O( c ) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n 3) < O(2n) < O(n!)
1-10. 对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。
T
单选题
2-1.数据的（）包括集合、线性结构、树形结构和图形结构四种基本类型。
A.存储结构
B.逻辑结构
C.基本运算
D.算法描述
B
2-2.数据在计算机内存中的表示是指（） 。
A. 数据的存储结构
B. 数据结构
C. 数据的逻辑结构
D.数据元素之间的关系
A
2-3.下列关于数据的逻辑结构的叙述中，（）是正确的。
A. 数据的逻辑结构是数据元素间关系的描述
B. 数据的逻辑结构反映了数据在计算机中的存储方式
C. 数据的逻辑结构分为顺序结构和链式结构
D. 数据的逻辑结构分为静态结构和动态结构
A.
B. 数据的存储结构反映了数据在计算机中存储方式
C，D 逻辑结构分为集合结构，线性结构，树形结构，图结构
2-4.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。
A. 操作对象
B. 计算方法
C. 逻辑存储
D. 数据映象
A
2-5.在数据结构中，与所使用的计算机无关的数据结构是（）。
A. 逻辑结构
B. 存储结构
C. 逻辑结构和存储结构
D. 物理结构
A
2-6.在决定选取何种存储结构时，一般不考虑（）。
A.各结点的值如何
B.结点个数的多少
C.对数据有哪些运算
D.所用编程语言实现这种结构是否方便
A
2-7.线性结构中元素之间存在（）关系。
A. 一对一
B. 一对多
C. 多对多
D. 多对一
A
2-8.树形结构中元素之间存在（）关系。
A. 一对一
B. 一对多
C.多对多
D.多对一
B
2-9.图形结构中元素之间存在（）关系。
A. 一对一
B.一对多
C.多对多
D.多对一.
C
2-11.在数据结构中，从逻辑上可以把数据结构分成（ ）。
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
C
2-12.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。
A. 存储结构
B. 存储实现
C. 逻辑结构
D. 运算实现
C
2-13.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。
A. 数据在同一范围内取值
B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C. 每个数据元素都一样
D. 数据元素所包含的数据项的个数要相等
B
2-14.算法的时间复杂度取决于（ ）。
A. 问题的规模
B. 待处理数据的初态
C. 计算机的配置
D. A和B
D
2-15.以下数据结构中，（ ）是非线性数据结构。
A. 树
B. 字符串
C. 队列
D. 栈
A
2-16.以下说法正确的是（ ）。
A. 数据元素是数据的最小单位
B. 数据项是数据的基本单位
C. 数据结构是带有结构的各数据项的集合
D. 一些表面上很不相同的数据可以有相同的逻辑结构
D
A. 数据项是组成数据元素的、有独立含义的，不可分割的最小单位
B. 数据元素是数据的基本单位
C.数据结构是相互之间存在一种或多种特定关系的数据元素的集合
2-17.数据的基本单位是（）。
A. 数据元素
B. 文件
C. 数据项
D. 数据结构
A
2-18.计算机算法指的是（）。
A. 计算方法
B. 排序方法
C. 解决问题的有限运算序列
D. 调度方法
C
2-19.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。
A. 数据的处理方法
B. 数据元素的类型
C. 数据元素之间的关系
D. 数据的存储方法
C
2-20.(neuDS)链式存储设计时，各结点间的存储单元的地址( )。
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
C
2-21.下面代码段的时间复杂度是（）。
x=n; //n>1
y=0;
while( x≥(y+1)*(y+1) )
y++;
A. O(1)
B. O(n1/2)
C. O(n)
D. O(log2n)
B
2-22
下列代码
if ( A > B ) {
for ( i = 0; i <N * N / 100; i++ )
for ( j = N * N; j > i; j-- )
A += B;
}
else {
for ( i = 0; i < N * 2; i++ )
for ( j = N* 3; j > i; j-- )
A += B;
}
的时间复杂度是：
A. O(N3)
B. O(N4)
C. O(N5)
D. O(N6)
B,在if里面，i循环有个n2,j循环有个n2，所以一共n4
2-23
下列函数
int func ( int n )
{ int i = 0, sum = 0;
while ( sum < n ) sum += ++i;
return i;
}
的时间复杂度是：(2分)
A. O(logn)
B.O(n1/2)
C. O(n)
D. O(nlogn)
B
2-24
下列代码
for(i = 0; i < n; i++)
for(j = i; j > 0; j /= 2)
printf(“%d\n”, j);
的时间复杂度是： (3分)
A. O(N×i)
B. O(N)
C.O(N2)
D.O(NlogN)
D，i有个n，j是每次除二，故是logN
2-25
下面代码段的时间复杂度是（）。 (2分)
x=0;
for( i=1; i<n; i++ )
for ( j=1; j<=n-i; j++ )
x++;
A. O(n)
B. O(n2)
C. O(n3)
D. O(2n)
B
2-26.要判断一个整数N（>10）是否素数，我们需要检查3到√N 之间是否存在奇数可以整除N。则这个算法的时间复杂度是：
A. O(N/2)
B. O(√N)
C. O(√NlogN)
D. O(0.5logN)
B
2-27下列函数中，哪个函数具有最慢的增长速度：
A. N1.5
B. NlogN2
C. N2 logN
D. N(logN)2
B
2-28给定N×N×N的三维数组A，则在不改变数组的前提下，查找最小元素的时间复杂度是：
A. O(N2)
B. O(NlogN)
C. O(N3logN)
D. O(N3)
D
2-29计算机算法必须具备输入、输出和（）等五个特性。
A. 可行性、可移植性和可扩充性
B. 可行性、确定性和有穷性
C. 确定性、有穷性和稳定性
D. 易读性、稳定性和安全性
B
主观题
常见的逻辑关系有那些？各有何特点？
- 集合结构： 数据元素之间除了“属于同一集合”的关系外，别无其他关系
- 线性结构： 数据元素之间存在一对一的关系
- 树形结构： 以分支关系定义的层次结构，数据元素之间存在一对多的关系
- 图结构： 数据元素之间存在多对多的关系
常用的物理存储结构有那些？各有何优缺点？
- 顺序结构
优点：
1. 存储位置是顺序的，读取位置是随机的。
2. 存取速度快，空间利用率高。
3. 所需的磁盘寻道次数和寻道时间最少。
缺点：
1. 需要为每个文件预留若干物理块以满足文件增长的部分需要。
2. 不利于文件插入和删除。- 链式结构
优点：
1. 存储位置是随机的，读取位置是顺序的；。
2. 提高了磁盘空间利用率，不需要为每个文件预留物理块。
3. 有利于文件插入和删除。
缺点：
1. 存取速度慢，不适于随机存取。
2. 当物理块间的连接指针出错时，数据丢失。
3. 链接指针占用一定的空间，降低了空间利用率。
4. 需要更多的寻道次数和寻道时间。
评价算法时间运行效率的方法有那些？各有何优缺点？
- 事后统计法
缺点：
1 . 必须把算法转换成可执行程序
2 . 时空开销的测算结果依赖于计算机的软硬件等环境因素- 事前分析估算法
优点：可以预先比较各种算法，以便均衡利弊从中选优