数据结构（自考） 课后习题及解答.pdfVIP

第一章绪论

一、单项选择题

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

A.紧凑结构和非紧凑结构B.线性结构和非线性结构

C.内部结构和外部结构D.动态结构和静态结构

答案：Bo

从逻辑角度看，基本的数据结构包括4类，分别是集合、线性结构、树结构和图结构。

其中，树结构和图结构属于非线性结构。集合也可以使用线性结构表示。

2.数据元素可以细分为o

A.数据项B.字符C.二进制位D.数据记录

答案：Ao

根据定义，数据元索可以细分为数据项。字符和二进制位都是表示数据的具体单位选（

项B和C都不正确）。数据元素有时称为记录（选项D不正确）。

3.如果说线性结构中元素之间是一对一的关系，则树结构中元素之间的关系是。

A.一对一的B.一对多的C.多对多的D.不确定的

答案：Bo

线性结构中，每个元素有唯一的前驱和唯一的后继，所以对于每个元素而言，它对应唯

一的后继，形成一对一的关系。当然，首元素和尾元素除外。在树结构中，每个元素仅有唯

一的前驱，但可以有多个言继，所以是一对多的关系。当然，树中的根（最前面的元素）和

叶结点（后面的元素）除外。图结构中是多对多的关系，每个元素可以有多个前驱，也可以

有多个后继。

4.下列选项中，不属于数据结构常用存储方式的是。

A.顺序存储方式B.链式存储方式C.分布存储方式D.散列存储方式

答案：Co

数据结构课程中没有讨论分布存储方式，除了选项口给定的A、B和D以外，还讨论了

索引存储方式。这是数据结构中常用的4种存储方式.

5.算法分析要评估的两个主要方面是。

A.正确性和简明性B.时间复杂性和空间复杂性

C.可读性和可维护性D.数据复杂性和程序复杂性

答案：Bo

算法的正确性是必须的，简明性、可读性、可维护性等都不是算法要评估的内容选（项

A和选项C不正确），它们都属于算法应具备的众多特性中的内容。数据复杂性是数据本身

的状态，也不是算法要评估的，程序复杂性说得不明确选（项D不正确）。算法要评估的是

时间和空间复杂性。

6.下列选项中，定义抽象数据类型时不需要做的事情是。

A.给出类型的名字B.定义类型上的操作

C.实现类型上的操作D.用某种语言描述抽象数据类型

答案：Co

定义抽象数据类型时，需要给类型命名（选项A）,需要指明相关的操作有哪些选（项

B）,需要使用程序语言或是自然语言描述抽象数据类型选（项D）。在确定了存储结构之后

才能具体实现操作过程，所以在定义抽象数据类型阶段，不涉及这些操作的实现。

7.设〃是描述问题规模的非负整数，下面程序片段的时间复杂度是。

x=2;

while(xn/2)

x=2*x;

A.O(log2〃)B.0(〃)C.0(〃log2〃)D.O(/r)

答案：Ao

〃是输入规模。x从2开始，每次倍增，达到或超过n/2时倍增的次数与log2〃的大小相

当。

8.设〃是描述问题规模的非负整数，下列程序片段的时间复杂度是o

X=1;

while(n=(x+1)*(x+1))

x=x+l;

A.0(〃/)B.O(log2〃)C.0(n)D.0(nlogin)