数据结构练习题和答案
一、单项选择题
1．在数据结构与算法中，从逻辑上可以把数据结构分为________。
A．紧凑结构和非紧凑结构 B．线性结构和非线性结构
C．内部结构和外部结构 D．动态结构和静态结构
答案：B。
从逻辑角度看，基本的数据结构包括4类，分别是集合、线性结构、树结构和图结构。其中，树结构和图结构属于非线性结构。集合也可以使用线性结构表示。
2．数据元素可以细分为________。
A．数据项 B．字符 C．二进制位 D．数据记录
答案：A。
根据定义，数据元素可以细分为数据项。字符和二进制位都是表示数据的具体单位（选项B和C都是错误的）。数据元素有时称为记录（选项D错误）。
3．如果说线性结构中元素之间是一对一的关系，则树结构中元素之间的关系是________。
A．一对一的 B．一对多的 C．多对多的 D．不确定的
答案：B。
线性结构中，除首元素和尾元素外，每个元素有唯一的直接前驱和唯一的直接后继，所以对于每个元素而言，它对应唯一的直接后继，形成一对一的关系。在树结构中，每个元素仅有唯一的直接前驱，但可以有多个直接后继，所以是一对多的关系。当然，树中的根（最前面的元素）和叶结点（后面的元素）除外。图结构中是多对多的关系，每个元素可以有多个直接前驱，也可以有多个直接后继。
4．在数据结构中，数据元素之间均为一个对一个的关系，称为________。
A．线性结构 B．树结构 C．图结构 D．集合结构
答案：A。
基本概念。具体说明请参见第一章第3题的答案。
5．下列选项中，不属于数据结构常用存储方式的是________。
A．顺序存储方式 B．链式存储方式 C．分布存储方式 D．散列存储方式
答案：C。
数据结构与算法课程中没有讨论分布存储方式，除了选项中给定的A、B和D以外，还讨论了索引存储方式。这是数据结构中常用的4种存储方式。
6．算法分析要评估的两个主要方面是________。
A．正确性和简明性 B．时间复杂度和空间复杂度
C．可读性和可维护性 D．数据复杂性和程序复杂性
答案：B。
算法的正确性是必须的，简明性、可读性、可维护性等都不是算法要评估的内容（选项A和选项C均错误），它们都属于算法应具备的众多特性中的内容。数据复杂性是数据本身的状态，也不是算法要评估的，程序复杂性说得不明确（选项D错误）。算法要评估的是时间复杂度和空间复杂度。
7．下列选项中，定义抽象数据类型时不需要做的事情是________。
A．给出类型的名字 B．定义类型上的操作
C．实现类型上的操作 D．用某种语言描述抽象数据类型
答案：C。
定义抽象数据类型时，需要给类型命名（选项A），需要指明相关的操作有哪些（选项B），需要使用程序语言或是自然语言描述抽象数据类型（选项D）。在确定了存储结构之后才能具体实现操作过程，所以在定义抽象数据类型阶段，不涉及这些操作的实现。
8．下列算法的时间复杂度中，算法效率最低的是________。
A．O(n) B．O(n2) C．O(2n) D．O(log n)
答案：C
基本概念。一般而言，算法的效率用算法时间复杂度进行衡量，算法效率从高到低依次是：常数阶O(1)，对数阶O(logn)，线性阶O(n)，线性对数阶O(nlogn)，多项式阶O(n2)，指数阶O(2n)。
9．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是________。
x=2;
while(x<n/2)
x=2*x;
A．O(log2n) B．O(n) C．O(n log2n) D．O(n2)
答案：A。
n是输入规模。x从2开始，每次倍增，达到或超过n/2时倍增的次数与log2n的大小相当。
10．设n是描述问题规模的非负整数，下列程序片段的时间复杂度是________。
x=1;
while(n>=(x+1)*(x+1))
x=x+1;
A．O(n1/2) B．O(log2n) C．O(n) D．O(n log2n)
答案：A。
11．设计求斐波那契数列前n项的算法时，适宜使用的算法策略是________。
A．分治法 B．递推法 C．递归法 D．穷举法
答案：B。