2024年4月30日发(作者：)

国家二级C语言（数据结构与运算）机试模拟试卷3

(题后含答案及

解析)

题型有：1. 选择题

选择题

1． 下列排序方法中，最坏情况下时间复杂度最小的是

A．冒泡排序

B．快速排序

C．堆排序

D．直接插入排序

正确答案：C

解析：根据上表可知选项C正确。 知识模块：数据结构与运算

2． 为了对有序表进行对分查找，则要求有序表

A．只能顺序存储

B．只能链式存储

C．可以顺序存储也可以链式存储

D．任何存储方式

正确答案：A

解析：有序表的对分查找条件是有序表为顺序存储。 顺序查找：①如果

线性表为无序表（即表中元素的排序是无序的），则无论是顺序存储结构还是链

式存储结构，都只能用顺序查找；②即使是有序线性表，如果采用链式存储结构，

也只能用顺序查找。分块查找（又称索引顺序查找）：分块有序表结构分为两部

分，①线性表本身采用顺序存储结构；②在建立一个索引表，在索引表中，对线

性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存

放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整

个线性表中的序号。显然索引表关于数据域是有序的。 知识模块：数据结构与

运算

3． 设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序

序列为

A．BCA

B．CBA

C．ABC

D．CAB

正确答案：C

解析：二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结

点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍

历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定

根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两

颗树，在按照上述方式递推出确定左子树的根和右子树。本题根据后序，可以确

定A为根结点；根据B在中序中的位置，可以确定A没有左子树，BC为A的

右子树，C为B的右子树。本题的具体二叉树如下：因此，这棵二叉树的前序是

ABC，选项C正确。 知识模块：数据结构与运算

4． 下列叙述中正确的是

A．存储空间不连续的所有链表一定是非线性结构

B．结点中有多个指针域的所有链表一定是非线性结构

C．能顺序存储的数据结构一定是线性结构

D．带链的栈与队列是线性结构

正确答案：D

解析：计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。

而数据在内存或磁盘中的存储，可以分为顺序存储和链式存储。数据的逻辑结构

与存储结构之间没有对应的关系。所以选项ABC都是错误的，栈和队列按照数

据的逻辑划分都是线性结构。 知识模块：数据结构与运算

5． 算法时间复杂度的度量方法是

A．算法程序的长度

B．执行算法所需要的基本运算次数

C．执行算法所需要的所有运算次数

D．执行算法所需要的时间

正确答案：B

解析：算法的时间复杂度：分析算法时，语句总执行次数T(n)是关于问题规

模n的函数，进而分析T(n)随n的变化情况并确定T(n)。算法的时间复杂度也就

是算法的时间量度，记作T(n)=O(f(n))。它表示问题输入规模n的增大，算法执

行时间的增长率和f(n)的增长率相同，因此称作渐近时间复杂度，也称作时间复

杂度。f(n)是问题规模n的某个函数。选项B正确。 知识模块：数据结构与运

算

6． 设循环队列为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队

与退队运算后，front=rear=1，则该循环队列中的元素个数为

A．1

B．2

C．m-1

D．0或m

正确答案：D

解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针

front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直

到队尾指针rear指向的位置之间，所有的元素为队列中的元素。在循环队列动态

变化过程中，当循环队列满时有front=rear，而当循环队列空时也有front=rear。

即在循环队列中，当front=rear时，不能确定是队列满、还是队列空。当front=rear=

１，要么队列为空，队列中的元素个数为0，要么队列为满，队列中元素个数为

m。选项D正确。 知识模块：数据结构与运算

7． 在最坏情况下

A．快速排序的时间复杂度比冒泡排序的时间复杂度要小

B．快速排序的时间复杂度比希尔排序的时间复杂度要小

C．希尔排序的时间复杂度比直接插入排序的时间复杂度要小

D．快速排序的时间复杂度与希尔排序的时间复杂度是一样的

正确答案：C

解析：按平均时间将排序分为四类：①平方阶(O(n2))排序：各类简单排序，

例如直接插入、直接选择和冒泡排序；②线性对数阶(O(nlog2n))排序：如快速排

序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔

排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排

序。 知识模块：数据结构与运算

8． 在深度为7的满二叉树中，度为2的结点个数为

A．64

B．63

C．32

D．31

正确答案：B

解析：因为在任意的二叉树中，度为0的结点（即叶子结点）总比度为2

的结点的个数多1个，而度为0的结点数n0=2m-1（其中m为二叉树的深度）。

本题的度为0的结点个数n0=27-1=26=64。因此，度为2的结点数n2=n0-1=63。

所以选项B正确。 知识模块：数据结构与运算

9． 设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列入

栈与退栈运算后，top=20，则当前栈中的元素个数为

A．30

B．20

C．m-19

D．m-20

正确答案：C

解析：根据题意，栈空间如下图所示。栈是向上增长的，每次压入一个元素，

栈的TOP指针向上移动一位。当压入第一个元素时，TOP指针指向m+1-1=m；

当压入第二个元素时，TOP指针指向m+1-2=m-1；......；以此类推，当压入第N

个元素时，TOP指针指向m+1-N=20；则N=m+1-20=m-19。因此选项C正确。 知

识模块：数据结构与运算

10． 算法空间复杂度的度量方法是

A．算法程序的长度

B．算法所处理的数据量

C．执行算法所需要的工作单元

D．执行算法所需要的存储空间

正确答案：D

解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的

度量，因此选项D正确。 知识模块：数据结构与运算

11． 设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队

与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最

坏情况下需要比较的次数为

A．4

B．6

C．m-5

D．m-6

正确答案：A

解析：初始状态为：front=rear=m，rear-front=0，此时队列为空。经过一系

列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾rear减队头front

等于5个元素。此时队列中有5个元素，而查找最大项至少要比较n-1次，就是

4次。因此选项A正确。 知识模块：数据结构与运算

12． 下列叙述中正确的是

A．循环队列属于队列的链式存储结构

B．双向链表是二叉树的链式存储结构

C．非线性结构只能采用链式存储结构

D．有的非线性结构也可以采用顺序存储结构

正确答案：D

解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。

例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。 知

识模块：数据结构与运算

13． 某二叉树中有n个叶子结点，则该二叉树中度为2的结点数为

A．n+1

B．n-1

C．2n

D．n/2

正确答案：B

解析：对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总

数为N2，则N0=N2+1；N2=N0-1。所以如果二叉树中有n个叶子结点，则该二

叉树中度为2的结点数为n-1。因此选项B正确。 知识模块：数据结构与运算

14． 下列叙述中错误的是

A．算法的时间复杂度与算法所处理数据的存储结构有直接关系

B．算法的空间复杂度与算法所处理数据的存储结构有直接关系

C．算法的时间复杂度与空间复杂度有直接关系

D．算法的时间复杂度与空间复杂度没有必然的联系

正确答案：C

解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间

复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结

构都有直接关系，但两者之间没有直接关系，因此选项C错误。 知识模块：数

据结构与运算

15． 设栈的顺序存储空间为S(0:49)，栈底指针bottom=49，栈顶指针top=30

（指向栈顶元素）。则栈中的元素个数为

A．30

B．29

C．20

D．19

正确答案：C

解析：在操作系统中，栈是向下生长的，如下图如示：所以当栈底指针

bottom=49，栈顶指针top=30时，栈中的元素个数为：栈底-栈顶+1=49-30+1=20。

因此选项C正确。 知识模块：数据结构与运算

16． 某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二

叉树的深度（根结点在第1层）为

A．2

B．3

C．4

D．5

正确答案：C

解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，可知A

为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的

右子树上；并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三

个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三

个结点依次位于前一个结点的右子树上。所以得到的二叉树为：所以这个二叉树

的深度为4。选项C为正确答案。 知识模块：数据结构与运算

17． 下列叙述中正确的是

A．存储空间连续的数据结构一定是线性结构

B．存储空间不连续的数据结构一定是非线性结构

C．没有根结点的非空数据结构一定是线性结构

D．具有两个根结点的数据结构一定是非线性结构

正确答案：D

解析：数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线

性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满

足以下两个条件：① 有且只有一个根结点；② 每一个结点最多有一个前件，也

最多有一个后件。根据这两个条件，可知选项A、B和C都不能判定是否是线性

结构。 知识模块：数据结构与运算

18． 下列叙述中正确的是

A．带链队列的存储空间可以不连续，但队头指针必须大于队尾指针

B．带链队列的存储空间可以不连续，但队头指针必须小于队尾指针

C．带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾

指针

D．以上三项都错误

正确答案：C

解析：带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可

比性，选项C正确。 知识模块：数据结构与运算

19． 设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队

与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最

坏情况下需要比较的次数为

A．5

B．6

C．m-5

D．m-6

正确答案：C

解析：在循环队列中元素的个数为“(rear-front+M)%M”，式中rear为队尾

指针，front为队首指针，M为存储容量，%为取余符号。对于找最小值的最坏

情况下的比较次数，为循环队列中元素值个数减一。所以对于这个题目来说初始

时元素个数为0；运算后，元素个数为m-5，找最小值的最坏情况下的比较次数

为m-5-1=m-6。 知识模块：数据结构与运算

20． 某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二

叉树的后序序列为

A．EFGDCBA

B．DCBEFGA

C．BCDGFEA

D．DCBGFEA

正确答案：D

解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，可知A

为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的

右子树上；并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三

个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三

个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的

形状如下：根据该二叉树，可得出后序遍历序列为：DCBGFEA，选项D正确。

知识模块：数据结构与运算

21． 下列叙述中正确的是

A．在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构

B．在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是

非线性结构

C．在链表中，如果每个结点有两个指针域，则该链表一定是线性结构

D．在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是

线性结构

正确答案：B 涉及知识点：数据结构与运算

22． 下列叙述中错误的是

A．在带链队列中，队头指针和队尾指针都是在动态变化的

B．在带链栈中，栈顶指针和栈底指针都是在动态变化的

C．在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的

D．以上三项都错误

正确答案：B

解析：栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈顶，

另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不

变的，选项C的说法正确，选项B的说法是错误的。队列是允许在队列的头和

尾都可以进行操作的线性表，所以在带链队列中，队头指针和队尾指针都是在动

态变化的选项A这一说法是正确的。 知识模块：数据结构与运算

23． 设数据元素的集合D={1,2,3,4,5}，则满足下列关系R的数据结构中为

线性结构的是

A．R={(1,2),(3,4),(5,1)}

B．R={(1,3),(4,1),(3,2),(5,4)}

C．R={(1,2),(2,3),(4,5)}

D．R={(1,3),(2,4),(3,5)}

正确答案：B

解析：把每个答案中的第一个元素集合取出来，例如A:(1,2)，先写下来就

是12，然后看后面的(3,4)，在(1,2)中找不到前驱和后继，只能和(1,2)暂时先并列，

然后是(5,1)，这里我们已经写过12了，那么5在1前面就是512，但是34要单

排，所以A就是两个根节点3和5，两个顺序是512,34。同理选项B是541,32；

选项C是：123和45；选项D是135,24所以选项B正确。 知识模块：数据结

构与运算

24． 下列叙述中正确的是

A．链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线

性结构

B．线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个

指针

C．线性表的链式存储结构中，每个结点只能有一个指向后件的指针

D．线性表的链式存储结构中，叶子结点的指针只能是空

正确答案：A

解析：在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针

域用于指向该节点的前一个或后一个结点，所以选项B、C、D说法错误。选项

A中，例如双向链表就具有两个指针，也属于线性结构，所以选项A正确。 知

识模块：数据结构与运算

25． 一个栈的初始状态为空，现将元素A、B、C、D、E依次入栈，然后

依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的

元素全部退出。则元素退队的顺序为

A．ABC

B．CBA

C．EDC

D．CDE

正确答案：C

解析：栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为E、

D、C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为E、D、

C，所以选项C正确。 知识模块：数据结构与运算

26． 某二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，则该二

叉树的深度（根结点在第1层）为

A．5

B．4

C．3

D．2

正确答案：B

解析：该二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，可知A

为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的

右子树上；并且结点B、C、D在中序序列和后序序列中顺序未变，则说明这三

个结点依次位于前一个结点的左子树上；结点E、F、G顺序颠倒，则说明这三

个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为4，

所以选项B正确。 知识模块：数据结构与运算

27． 下列叙述中正确的是

A．所谓算法就是计算方法

B．程序可以作为算法的一种描述方法

C．算法设计只需考虑得到计算结果

D．算法设计可以忽略算法的运算时间

正确答案：B

解析：算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，

算法就是计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选

项A和选项C不正确。程序的编制不可能优于算法的设计，但算法的描述可以

用程序、伪代码、流程图来描述，故选项B正确。算法要求执行过程中所需要

的基本运算次数和时间最少，即时间复杂度最低，所以选项D错误。 知识模块：

数据结构与运算