二级公共基础知识数据结构与算法(三)模拟题

[模拟] 二级公共基础知识数据结构与算法(三)

单项选择题

第1题：

算法的空间复杂度是指______。

A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量

C.算法程序中的语句或指令条数

D.算法在执行过程中所需要的临时工作单元数 参考答案：A

一般来说，一个算法的空间复杂度是指执行该算法所需的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。 第2题：

下列数据结构中，属于非线性结构的是______。

A.循环队列 B.带链队列 C.二叉树 D.带链栈 参考答案：C

线性结构满足两个条件：有且只有一个根节点；每个节点最多有一个前件，也最多有一个后件。栈、队列都属于线性结构，栈是一种先进后出的线性结构，允许在栈顶进行插入或删除运算；队列则是一种先进先出的线性结构，允许在队尾进行捅入运算，而在队头进行删除运算。二叉树是一种非线性结构，因为除叶子节点，每个节点都有两个后件，不满足线性结构的条件。 第3题：

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

A.循环队列 B.栈 C.队列 D.二叉树 参考答案：B

第4题：

对于循环队列，下列叙述中正确的是______。

A.队头指针是固定不变的 B.队头指针一定大于队尾指针 C.队头指针一定小于队尾指针

D.队头指针可以大于队尾指针，也可以小于队尾指针 参考答案：D

1

第5题：

下列叙述正确的是______。

A.栈是“先进先出”的线性表 B.队列是“后进先出”的线性表 C.循环队列是非线性结构

D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 参考答案：D

栈是“先进后出”的线性表，而队列是“先进先出”的线性表，循环队列自然也是线性结构的，有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。 第6题：

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

A.冒泡排序

B.简单选择排序 C.直接插入排序 D.堆排序 参考答案：D

本题考查各种排序方法的时间复杂度，冒泡排序、简单选择排序、直接插入排序在最坏的情况下比较次数都是O(n2)，而堆排序的时间复杂度为O(nlog2n)，这也是堆排序的最大优点。 第7题：

某二叉树有5个度为2的节点，则该二叉树中的叶了节点是数是______。

A.10 B.8 C.6 D.4

参考答案：C

由二叉树的性质得知，对于一个非空的二叉树，叶子节点数等于度为2的节点数目＋1。 第8题：

支持子程序调用的数据结构是______。

A.栈 B.树 C.队列 D.二叉树 参考答案：D

在题目选项中，栈是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表；队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种操作受限的线性表；线性表是最简单、最常用的一种数据结构，是具有相同数据类型的n(n≥0)个数据元素组成的有限序列；二叉树是个有限元

2

素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。这里仅有二叉树是支持子程序调用的。 第9题：

在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是______。

A.O(n)

B.O(n²) C.O(log₂n) D.O(nlog₂n) 参考答案：C

二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素x与线性表的中间项进行比较，若中问项的值等于x，则说明查到；若小于中间项的值，则在线性表的前半部分以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较log₂n次。 第10题：

下列叙述中正确的是______。

A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C.顺序存储结构能存储有序表，链式存储结构不能存储有序表 D.链式存储结构比顺序存储结构节省存储空间 参考答案：A

在顺序存储结构中所有元素所占的存储空间是连续的，而在链式存储结构中，存储数据结构的存储空间可以不连续，因此选项A是正确的。线性表在计算机中的存放可以采用顺序存储结构，也可采用链式存储结构，顺序存储结构和链式存储结构都是既可用于线性结构，也可以用于非线性结构，因此选项B、C是错误的。采用链式存储结构，不仅要存储元素的值，元素间的逻辑关系还需要通过附设的指针字段来表示，因此，链式存储结构需要更多的存储空间。 第11题：

下列叙述中正确的是______。

A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 D.循环队列中元素的个数是由队头指针和队尾指针共同决定的 参考答案：D

循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环形空间。循环队列仍然是顺序存储结构，是队列常采用的形式，因此选项A错误。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队列排头元素的前一个位置。循环队列中的元素是动态变化的，每进行一次入队运算，对尾指针就进一；每进行一次出队运算，队头指针就进一。可见，由队

3

头指针和队尾指针一起反映队列中元素的动态变化情况，因此选项B、C是错误的。从队头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素，因此选项D是正确的。 第12题：

一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是______。

A.12345A2BCDE B.EDCBA54321 C.ABCDEl2345 D.54321EDCBA 参考答案：B

栈是按照“先进后出”的原则组织数据的，入栈的顺序为12345ABCDE，1为栈底元素最后出栈，E为栈顶元素最先出栈，因此出栈的顺序为EDCBA54321。 第13题：

算法的时间复杂度取决于______。

A.问题的规模

B.待处理的数据的初始状态 C.问题的困难度 D.A和B

参考答案：D

第14题：

计算机算法指的是______。

A.计算方法 B.调度方法 C.排序方法

D.解决某一问题的有限运算序列 参考答案：D

第15题：

下列叙述中正确的是______。

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

B.数据的逻辑结构属于线性结构，存储结构属于非线性结构

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

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

参考答案：D

第16题：

数据的存储结构是指______。

A.存储在外存中的数据 B.数据所占的存储空间量

4