强化习题

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

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

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

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

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

【答案】D

【解析】逻辑数据结构，是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。一种数据的逻辑结构根据需要可以表示成多种存储结构，采用不同的存储结构，其数据处理的效率是不同的。答案选择D选项。

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

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

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

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

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

【答案】B

【解析】线性结构常用存储结构为：①顺序存储结构，物理上连续存储，空间位置隐含逻辑位置；②链式存储结构，存储上不连续，通过指针相连。在链式存储方式中，每个结点包含存放数据的数据域和存放指针的指针域。所以链式存储结构所需的存储空间一般要多于顺序存储结构。答案选择B选项。

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

A．循环队列

B．栈

C．队列

D．二叉树

【答案】B

【解析】栈和队列都是操作受限的线性表：栈只能在栈顶插入和删除元素，按照“先进后出”的原则组织数据；队列只能在队头删除元素，在队尾插入元素，按照“先进先出”的原则组织数据。B项，栈，按照“先进后出”的原则组织数据。A项，循环队列是队列的一种特殊形式，按照“先进先出”的原则组织数据；C项，队列，按照“先进后出”的原则组织数据。D项，二叉树属于非线性结构。答案选择B选项。

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

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

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

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

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

【答案】B

【解析】队列是一种“先进先出”的特殊线性表。队列的顺序存储结构一般采用循环队列的形式。循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，定义两个游标：指向队头的游标（front）、指向队尾的游标（rear）。答案选择B选项。

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

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

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

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

D．以上说法均不正确

【答案】C

【解析】线性表的链式存储结构称为线性链表。线性链表的存储空间可以不连续，其存储顺序和逻辑顺序也不一定一致。线性链表一般用结点描述：结点=数据域+指针域。进行插入和删除时，只需改变指针的指向，而不需要移动表中元素。答案选择C选项。

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

A．4

B．10

C．6

D．16

【答案】D

【解析】根据二叉树的性质3：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个，所以度为2的结点数为4个，那么25-5-4=16即为度为1的结点数。答案选择D选项。

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

A．ABCDE

B．ECABD

C．EACDB

D．CDEAB

【答案】C

【解析】后序遍历最后遍历到根结点，所以E为根结点。中序遍历根结点在左右子树之间，所以B为二叉树的右子树，CAD为左子树。同理，在CAD分支中，D为CA的父结点，C为D的左孩子，A为D的右孩子。根据所得树的形状，可得前序遍历为EACDB。答案选择C选项。

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

A．1

B．2

C．3

D．4

【答案】C

【解析】二分法查找法不断的将序列分为可能包含和必然不包含的两部分，本题流程为：①将60与中间的元素55进行比较，60>55，所以60不可能在前4个元素中；②第二次将60与中间的元素70进行比较，60<70，所以60不可能在后2个元素中；③第三次将60与中间元素60比较，这时查找成功。答案选择C选项。

9下列排序方法中，最坏情况下比较次数最少的是（　　）。

A．冒泡排序

B．简单选择排序

C．直接插入排序

D．堆排序

【答案】D

【解析】冒泡排序，简单选择排序和直接插入排序在最坏情况下的比较次数都是O(n²)，而堆排序为O(nlog₂n)。答案选择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

【答案】B

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

关键码值B在序列中的序号是3。答案选择B选项。