第二部分　章节题库

模块一　数据结构

第1章　绪　论

一、单项选择题

1每个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明存储位置的表，该存储方式是（　　）存储方式。

A．顺序

B．链接

C．索引

D．散列

【答案】C

【解析】根据索引的定义，除表本身以外，还需建立一个“索引表”，这个表指明存储位置加快结点的查找过程。

2在（　　）存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。

A．树形存储结构

B．链式存储结构

C．索引存储结构

D．散列存储结构

【答案】D

【解析】散列存储结构中是根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置。而树形存储结构、链式存储结构和索引存储结构中关键字在结构中的相对位置是随机的。

3以下属于逻辑结构的是（　　）。

A．顺序表

B．哈希表

C．有序表

D．单链表

【答案】C

【解析】数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，与数据元素本身的形式、内容、相对位置、所含结点个数都无关。顺序表、哈希表、单链表都涉及到数据的存储结构，有序表是指表中数据有序，与逻辑结构无关。

4以下与数据的存储结构无关的术语是（　　）。

A．循环队列

B．链表

C．哈希表

D．栈

【答案】D

【解析】数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构，它们是数据的两种最基本的存储结构。ABC三项，都属于链式存储结构。D项，栈则是指从应用的角度来说的一种后进先出的线性表结构，与具体的存储结构无关。

5在数据结构中，与所使用的计算机无关的是数据的（　　）结构。

A．逻辑

B．存储

C．逻辑和存储

D．物理

【答案】A

【解析】物理结构又称存储结构。逻辑结构描述的是数据元素之间的关系，与所使用的计算机无关，而存储结构是逻辑结构在计算机中的表示，与具体使用的计算机有关。

6数据结构是具有（　　）的数据元素的集合。

A．性质相同

B．特定关系

C．相同运算

D．数据项

【答案】B

【解析】数据结构由数据元素集合和数据元素关系两部分组成。

7以下说法正确的是（　　）。

A．数据结构的逻辑结构是指数据的各数据项之间的逻辑关系。

B．数据元素是数据结构的最小单位。

C．数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。

D．判断某个算法是否容易阅读是算法分析的任务之一。

【答案】C

【解析】A项，数据结构的逻辑结构是指数据的各数据元素之间的逻辑关系，而不是数据项之间的逻辑关系。B项，数据元素是数据结构的基本单位，数据结构的最小单位是数据项。D项，算法分析是一个软件的验证确认任务，用于保证选择的算法是正确的、合适的和稳定的，并且满足所有精确性、规模和时间方面的要求，保证产品高质量高效率的运行。容易阅读是增加算法的可读性，不是算法分析的任务。

8数据的存储结构是指（　　）。

A．数组类型

B．指针类型

C．数据之间的逻辑关系

D．数据之间的物理关系

【答案】D

【解析】数据的存储结构就是物理结构，指数据之间的物理关系。

9在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（　　）。

A．数据的处理方法

B．数据元素的类型

C．数据元素之间的关系

D．数据的存储方法

【答案】C

【解析】在存储数据时，需要存储数据元素的值和数据元素之间的关系。

10在计算机的存储器中表示时，各元素的物理地址和逻辑地址的相对顺序相同并且是连续的称之为（　　）。

A．逻辑结构

B．顺序存储结构

C．链式存储结构

D．以上都对

【答案】B

【解析】顺序存储结构是一种直接映射。这种结构把逻辑上相邻的元素存储在物理位置上相邻的存储单元里，直接反映数据元素之间的逻辑关系。

11下面术语中，与数据的存储结构无关的是（　　）。

A．循环队列

B．栈

C．散列表

D．单链表

【答案】B

【解析】只有栈是逻辑结构，其他选项都是存储结构（或物理结构）。

12可以用（　　）定义一个完整的数据结构。

A．数据元素

B．数据对象

C．数据关系

D．抽象数据类型

【答案】D

【解析】抽象数据类型描述了数据的逻辑结构和抽象运算，构成了一个完整的数据结构定义。

13可以用（　　）、数据关系和基本操作集定义一个完整的抽象数据类型。

A．数据元素

B．数据对象

C．原子类型

D．存储结构

【答案】B

【解析】抽象数据类型可用（数据对象，数据关系，基本操作集）三元组来表示。

14下面程序段中，执行S语句的次数为（　　）。

A．n²

B．n²/2

C．n（n＋1）

D．n（n＋1）/2

【答案】D

【解析】i的变化范围是从1到n，对于每个已确定值的i，j的变化范围是从1到i，相当于求一个公差为1的等差数列1，2，…，n的前n项和，即为n（n＋1）/2。

15算法的时间复杂度取决于（　　）。

A．问题的规模

B．待处理数据的初态

C．A和B

D．与A和B无关

【答案】C

【解析】算法的时间复杂度是问题规模n的函数，它既取决于待处理数据的多少，即问题的规模；又取决于待处理数据的存储状态和存储形式等，即待处理数据的初态。

16下面说法错误的是（　　）。

（1）算法原地工作的含义是指不需要任何额外的辅助空间。

（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2ⁿ）的算法。

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。

（4）同一个算法，实现语言的级别越高，执行效率就越低。

A．（1）

B．（1）、（2）

C．（1）、（4）

D．（3）

【答案】C

【解析】（1）项，原地工作不是不需要额外空间，而是额外空间相对于问题的规模（输入数据量）来说是个常数，那么我们就称之为原地工作。（4）项，这个结论不是绝对的，要看具体情况而定，一般情况下是这样的。

17在顺序表中删除一个元素的时间复杂度为（　　）。

A．O（1）

B．O（logn）

C．O（n）

D．O（n²）

【答案】C

【解析】删除顺序表中第i个元素，将顺序表第i个元素以后元素均向前移动一个位置，因此时间复杂度为O（n）。

18分析以下程序段时间复杂度（　　）。

A．O（1）

B．O（log n）

C．O（n）

D．O（n²）

【答案】D

【解析】在考虑程序段的时间复杂度时，可以用算法中的基本操作重复执行的频度作为度量标准。本程序段中的基本操作应选取为语句④，所以该算法的时间复杂度＝2n²＋n＝O（n²）。

19（　　）不是算法的基本特性。

A．可行性

B．长度有限

C．在规定的时间内完成

D．确定性

【答案】B

【解析】算法的5个重要特性：①确定性；②有穷性；③可行性；④输入；⑤输出。C项指的是有穷性，而有穷性并不是指长度有限，而是指执行的时间是有限的。

20某算法的时间复杂度为O（n²），表明该算法的（　　）。

A．问题规模是n²

B．执行时间等于n²

C．执行时间与n²成正比

D．问题规模与n²成正比

【答案】C

【解析】T（n）＝O（n²）表示T（n）＝m×n²（m为正常量），其问题规模仍为n而不是n²。

注意：算法时间复杂度是问题规模n的函数，记为T（n）＝O（f（n）），表示T（n）＝cf（n），其中c为正常量，所以，T（n）的增长率与f（n）的增长率相同。

21一个算法的执行时间为T（n）＝（3n²＋2nlog₂n＋4n－7）/（10n），其时间复杂度为（　　）。

A．O（3n²）

B．O（2nlog₂n）

C．O（3n²/10）

D．O（n）

【答案】D

【解析】当n足够大时，T（n）→3n/10＝O（n）。

22以下有关算法的说法错误的是（　　）。

I．算法原地工作的含义是指不需要任何额外的辅助空间；

II．在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法；

III．所谓最坏时间复杂度是指最坏情况下估算算法执行时间的一个上界；

IV．同一个算法，实现语言的级别越高，执行效率就越低。

A．I

B．I和II

C．I和IV

D．III

【答案】C

【解析】算法原地工作的含义是指算法的空间复杂度为O（1），同一个算法实现语言的级别越高执行效率并不一定越低。

23求解Hanoi问题时，若初始有5个圆盘，则移动圆盘的次数是（　　）。

A．7

B．15

C．31

D．5

【答案】Ｃ

【解析】求解Hanoi问题时，对于n个圆盘，有T（n）＝2^n－1。

24以下算法的时间复杂度为（　　）。

A．O（n）

B．O（n²）

C．O（nlog₂n）

D．O（log₂n）

【答案】D

【解析】基本运算是语句i＝i×2，设其执行时间为T（n），则有：2^T（n）≤n，即T（n）≤log₂n＝O（log₂n）。

25有以下算法，其时间复杂度为（　　）。

A．O（n）

B．O（nlog₂n）

C．O（n²）

D．O（n³）

【答案】C

【解析】基本运算是语句x＋＋，用它的执行次数T（n）度量算法的时间复杂度，有：

26有以下算法，其时间复杂度为（　　）。

A．O（n）

B．O（nlog₂n）

C．O（）

D．O（）

【答案】C

【解析】基本运算是语句i＋＋，设其执行次数为T（n），用T（n）来衡量算法的时间复杂度。则有：T（n）×T（n）×T（n）≤n，即T（n）³≤n；所以有：

27以下算法中加下划线语句的执行次数为（　　）。

A．n（n＋1）

B．n

C．n＋1

D．n²

【答案】A。

【解析】m＋＋语句的执行次数为：

二、综合题

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O（n）的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

答：（1）题目思路解析：在算法中设立三个指针，其中，j表示当前元素，i以前的元素全部为红色，k以后的元素全部为蓝色，这样就可以根据j的颜色，把其交换到序列的前部或者后部。

（2）算法如下：