第一章测试

1. 在数据结构中， 从逻辑上可以把数据结构分成( ) 。

A:动态结构和静态结构 B:紧凑结构和非紧凑结构 C:线性结构和非线性结构 D:

内部结构和外部结构

答案:线性结构和非线性结构

2. 算法分析的两个主要方面是( ) 。

A:时间复杂度和空间复杂度 B:数据复杂性和程序复杂性 C:可读性和文档性 D:

正确性和简单性

答案:时间复杂度和空间复杂度

3. 计算机算法必须具备输入、 输出和( ) 等 5个特性。

A:易读性、 稳定性和安全性 B:确定性、 有穷性和稳定性 C:可行性、 确定性

和有穷性 D:可行性、 可移植性和可扩充性

答案:可行性、 确定性和有穷性

4. 数据结构是研究数据的( ) 以及它们之间的相互关系。

A:物理结构， 逻辑结构 B:理想结构， 物理结构 C:抽象结构， 逻辑结构 D:理

想结构， 抽象结构

答案:物理结构， 逻辑结构

5. 数据结构中， 与所使用的计算机无关的是数据的( ) 结构。

A:逻辑 B:物理 C:物理和存储 D:存储

答案:逻辑

6. 组成数据的基本单位是( ) 。

A:数据项 B:数据变量 C:数据元素 D:数据类型

答案:数据元素

7. 设数据结构 A=(D， R)， 其中D={1， 2， 3， 4}， R={r}， r={<1， ……此处隐藏16375个字…… 入排序的空间复杂度为 O(1)。 B:堆排序的空间复杂度为 O(n)。 C:

归并排序的空间复杂度为 O(n),需要附加两倍的存储开销。 D:快速排序附加

存储开销为 O(log 2 n)。

答案:堆排序的空间复杂度为 O(n) 。

5. 以下时间复杂性不是 O(nlog 2 n)的排序方法是( )。

A:堆排序 B:二路归并排序 C:直接插入排序 D:快速排序

答案:直接插入排序

6. 在文件局部有序或文件长度较小的情况下， 最佳的排序方法是( ) 。

A:直接选择排序 B:直接插入排序 C:冒泡排序 D:归并排序

答案:冒泡排序

7. 对于大文件的排序要研究在外设上的排序技术， 即 ( ) 。

A: B:内排序法 C:快速排序法 D:交叉排序法

答案 外排序法

8. 排序的目 的是为了 以后对已排序的数据元数进行( ) 操作。

A:分类 B:合并 C:查找 D:打印输出

答案:查找

9. 当初始序列已按健值有序时， 用直接插入算法进行排序， 需要比较的次数为

( ) 。

A:log 2 n B:2log 2 n C:Dn 2 D:n-1

答案:n-1

10. 快速排序在最坏的情况下的时间复杂度是( ) 。

A:O(nlog 2 n) B:O(log 2 n) C:O(n 3 ) D:O(n 2 )

答案:O(n 2 )