数据结构与算法 习题及解答 机械自考版 -第1--4章 绪论---数组、广义表和串.docx

第一章绪论

一、单项选择题

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(logn)

答案：C

基本概念。一般而言，算法的效率用算法时间复杂度进行衡量，算法效率从高到低依次是：常数阶O(1)，对数阶O(logn)，线性阶O(n)，线性对数阶O(nlogn)，多项式阶O(n2)，指数阶O(2n)。

9．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是________。

x=2;

while(xn/2)

x=2*x;

A．O(log2n) B．O(n) C．O(nlog2n) 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(nlog2n)

答案：A。

11．设计求斐波那契数列前n项的算法时，适宜使用的算法策略是________。

A．分治法 B．递推法 C．递归法 D．穷举法

答案：B。

参见本章算法设计题2的解答。

二、填空题

1．在数据结构与算法课程中，将所有能输入计算机并被计算机程序处理的符号集合称为__________。

答案：数据。

基本概念。

2．构成数据的基本单位是__________。

答案：数据元素。

基本概念。在数据结构课程中，数据元素是构成数据的基本单位，同时，也是作为一个整体进行研究。

3．数据元素及其关系在计算机内的存储方式称为数据的__________。

答案：存储结构。

数据的结构分为逻辑结构和物理结构。逻辑结构是指数据元素之间的逻辑关系，物理结构是指数据结构在计算机中的表示及存储方式。

数据的