强化习题

1．下列叙述中正确的是（ ）。

A．一个逻辑数据结构只能有一种存储结构

B．逻辑结构属于线性结构，存储结构属于非线性结构

C．一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D．一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

2．下列叙述中正确的是（ ）。

A．线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的

B．线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

C．线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构

D．线性表的链式存储结构与顺序存储结构在存储空间的需求上没有可比性

3．下列数据结构中，能够按照“先进后出”原则存取数据的是（ ）。

A．循环队列

B．栈

C．队列

D．二叉树

4．下列叙述中正确的是（ ）。

A．循环队列是队列的一种链式存储结构

B．循环队列是队列的一种顺序存储结构

C．循环队列是非线性结构

D．循环队列是一种逻辑结构

5．下列关于线性链表的叙述中，正确的是（ ）。

A．各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致

B．各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空问必须连续

C．进行插入与删除时，不需要移动表中的元素

D．以上说法均不正确

6．一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为（ ）。

A．16

B．10

C．6

D．4

7．己知二叉树后序遍历序列是CDABE，中序遍历序列是CADEB，它的前序遍历序列是（ ）。

A．ABCDE

B．ECABD

C．EACDB

D．CDEAB

8．对有序线性表（23，29，34，55，60，70，78）用二分法查找值为60的元素时，需要比较次数为（ ）。

A．1

B．2

C．3

D．4

9．下列排序方法中，最坏情况下比较次数最少的是（ 2n。" /> ）。

A．冒泡排序

B．简单选择排序

C．直接插入排序

D．堆排序

10．设有关键码序列（Q，G，M，Z，A，N，B，P，X，H，Y，S，T，L，K，E），采用堆排序法进行排序，经过初始建堆后关键码值B在序列中的序号是（ ）。

A．1

B．3

C．7

D．9

【解析】 堆排序是一种选择排序的算法，它从建堆开始：首先将要排序的所有关键码放到一棵完全二叉树的各个结点中，然后，从i=[n／2]的结点Ki开始，逐步把以K[n/2]， K[n/2]-1，K[n/2]-2，……为根的子树排成堆，直到以K1为根的树排成堆，就完成了建堆过程。此题中，n=16，i=[16／2]=8，即从第8个结点开始，建堆完成后如下图所示：

关键码值B在序列中的序号是3。 4B8iItB3GHfo070VJr4FVd/WzhrK/2wArle7AlwDpiXKZ4mooqQtYLbnwH9slnmd