2020年全国计算机等级考试二级公共基础知识考题库及答案（超强）
第一章数据结构
一、选择题
（1）下列数据结构中，能用二分法进行查找的是
A）顺序存储的有序线性表B）线性链表
C）二叉链表
D）有序线性链表
【答案】A
【解析】二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表
中的元素按值非递减排列即从小到大．但允许相邻元素值相等的。选项A
正确。
（2）下列关于栈的描述正确的是
A）在栈中只能插入元素而不能删除元素
B）在栈中只能删除元素而不能插入元素
C）栈是特殊的线性表，只能在一端插入或删除元素
D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素
【答案】C
【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。
由此可见，选项A、选项B和选项D错误，正确答案是选项C。
（3）下列叙述中正确的是
A）一个逻辑数据结构只能有一种存储结构
B）数据的逻辑结构属于线性结构，存储结构属于非线性结构
fC）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率
D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
【答案】D【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。由此可见，选项D的说法正确。4算法执行过程中所需要的存储空间称为算法的A）时间复杂度B）计算工作量C）空间复杂度D）工作空间【答案】c【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。5下列关于队列的叙述中正确的是A）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是先进后出的线性表【答案】c【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。6设有下列二叉树：
A
fB
C
D
E
F
对此二叉树后序遍历的结果为A）ABCDEFB）BDAECFC）ABDCEFD）DBEFCA【答案】D
【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求后序遍历。其遍历顺序应该为：后序遍历左子树一后序遍历右子树一访问根结点。按照定r