计算机二级公共试题
数据结构与算法核心真题
1. 算法
1. 下列叙述中正确的是
A）所谓算法就是计算方法
B）程序可以作为算法的一种描述方法
C）算法设计只需考虑得到计算结果
D）算法设计可以忽略算法的运算时间
B【解析】算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。
2. 下列关于算法的描述中错误的是
A）算法强调动态的执行过程，不同于静态的计算公式
B）算法必须能在有限个步骤之后终止
C）算法设计必须考虑算法的复杂度
D）算法的优劣取决于运行算法程序的环境
D【解析】算法设计不仅要考虑计算结果的正确性，还要考虑算法的时间复杂度和空间复杂度。
3. 下列叙述中正确的是
A）算法的复杂度包括时间复杂度与空间复杂度
B）算法的复杂度是指算法控制结构的复杂程度
C）算法的复杂度是指算法程序中指令的数量
D）算法的复杂度是指算法所处理的数据量
A【解析】算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和存资源
算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的存空间。
4. 下列叙述中正确的是
A）算法的时间复杂度与计算机的运行速度有关
B）算法的时间复杂度与运行算法时特定的输入有关
C）算法的时间复杂度与算法程序中的语句条数成正比
D）算法的时间复杂度与算法程序编制者的水平有关
B【解析】为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。
5. 下列叙述中正确的是
A）解决同一个问题的不同算法的时间复杂度一般是不同的
B）解决同一个问题的不同算法的时间复杂度必定是相同的
C）对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定相同
D）对同一批数据作不同的处理，如果数据存储结构相同，不同算法的时间复杂度肯定相同
A【解析】解决同一个问题的不同算法的时间复杂度，可能相同也可能不相同。算法的时间复杂度与数据存
储结构无关，对同一批数据作同一种处理或者不同处理，数据存储结构相同或者不同，算法的时间复杂度都可能相同或者不同。
6. 下列叙述中正确的是
A）算法的空间复杂度是指算法程序中指令的条数
B）压缩数据存储空间不会降低算法的空间复杂度
C）算法的空间复杂度与算法所处理的数据存储空间有关
D）算法的空间复杂度是指算法程序控制结构的复杂程度
C【解析】算法的空间复杂度是指算法在执行过程中所需要的存空间。算法执行期间所需的存储空间包括3
个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。
7. 为了降低算法的空间复杂度，要求算法尽量采用原地工作（inplace）。所谓原地工作是指
A）执行算法时不使用额外空间
B）执行算法时不使用任何存储空间
C）执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化
D）执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小的变化而变化）
D【解析】对于算法的空间复杂度，如果额外空间量相对于问题规模（即输入数据所占的存储空间）来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。
8. 下列叙述中正确的是
A）算法的复杂度与问题的规模无关
B）算法的优化主要通过程序的编制技巧来实现
C）对数据进行压缩存储会降低算法的空间复杂度
D）数值型算法只需考虑计算结果的可靠性
C【解析】在许多实际问题中，为了减少算法所占的存储空间，通产采用压缩存储技术，以便尽量减少不必要的额外空间。
2. 数据结构的基本概念
9. 下列叙述中正确的是
A）数据的存储结构会影响算法的效率
B）算法设计只需考虑结果的可靠性
C）算法复杂度是指算法控制结构的复杂程度
D）算法复杂度是用算法中指令的条数来度量的
A【解析】采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构很重要。
10. 下列叙述中错误的是
A）数据结构中的数据元素可以是另一数据结构
B）数据结构中的数据元素不能是另一数据结构
C）空数据结构可以是线性结构也可以是非线性结构
D）非空数据结构可以没有根结点
B【解析】数据元素是一个含义很广泛的概念，它是数据的“基本单位”，在计算机中通常作为一个整体进行考虑和处理。数据元素可以是一个数据也可以是被抽象出的具有一定结构数据集合，所以数据结构中的数据元素可以是另一数据结构。满足有且只有一个根结点并且每一个结点最多有一个前件，也最多有一个后件的非空的数据结构认为是线性结构，不满足条件的结构为非线性结构。空数据结构可以是线性结构也可以是非线性结构。非空数据结构可以没有根结点，如非性线结构“图”就没有根结点。
11. 下列叙述中正确的是
A）非线性结构可以为空
B）只有一个根结点和一个叶子结点的必定是线性结构
C）只有一个根结点的必定是线性结构或二叉树
D）没有根结点的一定是非线性结构
A【解析】如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都可以是空的数据结构。树只有一个根结点，但不论有几个叶子结点，树都是非线性结构。
12. 下列叙述中错误的是
A）向量是线性结构
B）非空线性结构中只有一个结点没有前件
C）非空线性结构中只有一个结点没有后件
D）具有两个以上指针域的链式结构一定属于非线性结构
D【解析】双向链表每个结点有两个指针，一个为左指针，用于指向其前件结点；一个为右指针，用于指向其后件结点，再加上头指针，具有两个以上的指针，但双向链表属于线性结构。非空线性结构中第一个结点没有前件，最后一个结点无后件，其余结点最多有一个前件，也最多有一个后件。向量也满足这个条件，属于线性结构。
13. 设数据结构B=(D,R) ，其中
D={a,b,c,d,e,f}
R={(f,a),(d,b),(e,d),(c,e),(a,c)}
该数据结构为
A) 线性结构
B) 循环队列
C) 循环链表
D) 非线性结构
A【解析】数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D;二是D上的关系，它反映了D
中各数据元素之间的前后件关系，通常记为R。即一个数据结构可以表示成B=(D,R)。其中B表示数据结
构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设a与b是D中的两个
数据，则二元组(a,b )表示a是b的前件，b是a的后件。本题中R中的根结点为f，元素顺序为 f T a T CThd T b，满足线性结构的条件。
14. 设数据集合为D={1,2,3,4,5}。下列数据结构B=(D,R)中为非线性结构的是
A) R={(2,5),(5,4),(3,1),(4,3)}
B) R={(1,2),(2,3),(3,4),(4,5)}
C) R={(1,2),(2,3),(4,3),(3,5)}
D) R={(5,4),(4,3),(3,2),(2,1)}
C【解析】A项中，R={(2,5),(5,4),(3,1),(4,3)} ，2为根结点，元素顺序为2^5^4^3^1,属于线性结
构；同理B项1为根结点，元素顺序为1T2T3T4T5， D项5为跟结点，元素顺序为5^4^3^2^1，均为线性结构。C 项中，元素3有两个前件，属于非线性结构。
3．线性表及其顺序存储结构
15. 下列叙述中正确的是
A) 矩阵是非线性结构
B) 数组是长度固定的线性表
C) 对线性表只能作插入与删除运算
D) 线性表中各元素的数据类型可以不同
B【解析】矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。
16. 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数
A不同，但元素的存储顺序与逻辑顺序一致
B) 不同，且其元素的存储顺序可以与逻辑顺序不一致
C) 相同，元素的存储顺序与逻辑顺序一致
D) 相同，但其元素的存储顺序可以与逻辑顺序不一致
C【解析】在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。
17. 下列叙述中正确的是
A）能采用顺序存储的必定是线性结构
B）所有的线性结构都可以采用顺序存储结构
C）具有两个以上指针的链表必定是非线性结构
D）循环队列是队列的链式存储结构
B【解析】所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树
也能用数组保存（按层次依次存放到数据元素中），但完全二叉树不属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。
4. 栈和队列
18. 下列叙述中正确的是
A）在栈中，栈顶指针的动态变化决定栈中元素的个数
B）在循环队列中，队尾指针的动态变化决定队列的长度
C）在循环链表中，头指针和链尾指针的动态变化决定链表的长度
D）在线性链表中，头指针和链尾指针的动态变化决定链表的长度
A【解析】在栈中，通常用指针top来指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反应了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。
19. 设栈的顺序存储空间为S（1:m），初始状态为top=0 。现经过一系列正常的入栈与退栈操作后，top=m+1，
则栈中的元素个数为
A）0
B）m
C）不可能
D）m+1
C【解析】栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=0，当栈满时top=m，无法继续入栈，top值不可能为m+1
20. 设栈的存储空间为S（1:50），初始状态为top=-1 。现经过一系列正常的入栈与退栈操作后，top=30 ，则栈中的元素个数为
A）20
B）19
C）31
D）30
D【解析】栈的初始状态为top=-1表示栈为空（没有规定栈中栈底必须是0），经过一系列正常的入栈与
退栈操作后top=30 ，则空间（1:30 ）中插入了元素，共30 个。
21. 设栈的顺序存储空间为S(1:m)，初始状态为top=m+1，则栈中的数据元素个数为
A) top-m+1
B) m-top+1
C) m-top
D) top-m
B【解析】栈的初始状态top=m+1，说明栈空时top=m+1 ( m在栈底，1是开口向上的)，入栈时栈顶指针是减操作(top=top-1 )，退栈时栈顶指针是加操作(top=top+1 )。本题可以假设栈中有x个元素，当x=0 时，也就是栈中没有元素，则top=m+1 ；当x=m时，也就是栈满，则top=1，由此可以得出top=m+1-x，继
而得出x=m-top+1 。
22. 设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，
则栈中的元素个数为
A) 1
B) m
C) m+1
D) 不可能
D【解析】栈的初始状态为top=m+1，说明栈空时top=m+1，入栈时栈顶指针是减操作(top=top-1 )，退栈时栈顶指针是加操作(top=top+1 )。栈满时top=1，说明栈中不能再进行入栈操作，top=0的情况不会出
现。
23. 设栈的存储空间为
S(1:m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=1。现又要将一
个元素进栈，栈顶指针top值变为
A) 0
B) 发生栈满的错误
C) m
D) 2
B【解析】栈的初始状态为top=m+1，说明栈空时top=m+1，入栈时栈顶指针是减操作(top=top-1 )，退栈时栈顶指针是加操作(top=top+1 )。栈满时top=1，说明栈中不能再进行入栈操作("上溢”错误)。
24. 设栈的存储空间为
S(1:m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中
退岀一个元素后，栈顶指针top值为
A) 0
B) m-1
C) m+1
D) 产生栈空错误
C【解析】栈的顺序存储空间为S(1:m)，初始状态top=m+1，所以这个栈是m在栈底，1是开口向上的。经
过一系列入栈与退栈操作后top=m，则栈中有1个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到m+1的位置。
25. 设栈的存储空间为S(1:50) ，初始状态为top=51 。现经过一系列正常的入栈与退栈操作后，top=20 ，则栈中的元素个数为
A) 31
B) 30
C) 21
D) 20
A【解析】栈的初始状态top=51，故本栈是51在栈底，入栈时栈顶指针是减操作(top=top-1 )，退栈时栈顶指针是加操作( top=top+1 )。当top=20 时，元素存储在(20:50) 空间中，因此共有50-20+1=31 个元素。
26. 下列处理中与队列有关的是
A) 二叉树的遍历
B) 操作系统中的作业调度
C) 执行程序中的过程调用
D) 执行程序中的循环控制
B【解析】队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有“先进先出”的特性，体现了“先来先服务”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入存分配资源并将新创建的进程插入就绪队列的过程。执行程序中的过程调用一般指函数调用，需要调用时候转入被调用函数地址执行程序，与队列无关。执行程序中的循环控制是指算法的基本控制结构，包括对循环条件的判定与执行循环体，与队列无关。二叉树是一个有限的结点集合，二叉树的遍历是指不重复地访问二叉树中的所有结点，与队列无关。
27. 设有栈S和队列Q初始状态均为空。首先依次将
A,B,C,D,E,F入栈，然后从栈中退出三个元素依次入
队，再将X,Y,Z 入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为
A) DEFXYZABC
B) FEDZYXCBA
C) FEDXYZCBA
D) DEFZYXABC
B【解析】栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将A,B,C,D,E,F入栈后，栈中元素为ABCDEF退出三个元素入队, 队列元素为FED,将X,Y,Z入栈后栈中元素为ABCXYZ退栈全部入队后，队列元素为FEDZYXCBA
28. 下列叙述中正确的是
A) 循环队列是顺序存储结构
B) 循环队列是链式存储结构
C) 循环队列空的条件是队头指针与队尾指针相同
D) 循环队列的插入运算不会发生溢出现象
A【解析】循环队列是队列的一种顺序存储结构。在循环队列中，在队列满和队列为空时，队头指针与队尾指针均相同；当需要插入的数据大于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象。
29. 下列叙述中正确的是
A) 在循环队列中，队尾指针的动态变化决定队列的长度
B) 在循环队列中，队头指针和队尾指针的动态变化决定队列的长度
C) 在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度
D) 在带链的栈中，栈顶指针的动态变化决定栈中元素的个数
B【解析】在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。带链的栈和带链的队列均采用链式存储结构，而在这种结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。
30. 循环队列的存储空间为Q(1:50) ，初始状态为front=rear=50 。经过一系列正常的入队与退队操作后，