第一章测试
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 )
