计算机二级选择题答案
考点1答案：数据结构与算法
（1）B）【解析】算法的时间复杂度是指算法在计算机内执行时所需时间的度量；与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。
因此，选项B）的说法是正确的。
（2）D）【解析】时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法在运行过程中临时占用所需存储空间大小的度量。
人们都希望选择一个既省存储空间、又省执行时间的算法。
然而，有时为了加快算法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和数据，又不得不牺牲运行时间。
时间和空间的效率往往是一对矛盾体，很难做到两全。
但是，这不适用于所有的情况，也就是说时间复杂度和空间复杂度之间虽然经常矛盾，但是二者不存在必然的联系。
因此，选项A）、B）、C）的说法都是错误的。
故本题的正确答案是D）。
（3）C）【解析】数据处理的最小单位是数据项；由若干数据项组成数据元素；数据是指能够被计算机识别、存储和加工处理的信息载体；数据结构是指数据之间的相互关系和数据运算。
（4）D）【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。
而采用不同的存储结构，其数据处理的效率是不同的。
故本题答案为D）。
（5）C）【解析】数据结构概念一般包括数据的逻辑结构、存储结构及数据上的运算集合等。
数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，而不管它在计算机中的存储形式。
（6）A）【解析】数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：①数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；②在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；③对各种数据结构进行的运算。
（7）A）【解析】根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构，又称线性表。
所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。
（8）D）【解析】线性表可以为空表；第一个元素没有直接前件，最后一个元素没有直接后件；线性表的定义中，元素的排列并没有规定大小顺序。
（9）A）【解析】如果一个非空的数据结构满足下列两个条件：第一，有且只有一个根结点；第二，每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。
线性结构又称线性表。
（10）B）【解析】顺序存储结构中，数据元素存放在一组地址连续的存储单元中，每个数据元素地址可通过公式LOC(a i)=LOC(a1)+(i-1)L计算得到，从而实现了随机存取。
对于链式存储结构，要对某结点进行存取，都得从链的头指针指向的结点开始，这是一种顺序存取的存储结构。
（11）D）【解析】栈是限定在一端进行插入与删除的线性表。
栈是按照“先进后出”的或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。
（12）B）【解析】本题考查的是栈。
栈是一种特殊的线性表，线性表可以顺序存储，也可以链式存储，而栈是一种线性表，也可以采用链式存储结构。
故本题答案为B）。
（13）B）【解析】本题主要考查对于栈的理解。
栈是限定在一端进行插入与删除的线性表。
在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。
栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素，即栈是按照“先进后出”或“后进先出”的原则组织数据的。
（14）A）【解析】和线性表类似，栈也有两种存储方法，一是顺序栈，二是链式栈。
栈的顺序存储结
构是利用一组地址连续的存储单元一次存储自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素的位置，由于栈的操作是线性表操作的特例，相对而言，链式栈的操作更易于实现。
（15）B）【解析】由栈“后进先出”的特点可知：A）中e1不可能比e2先出，C）中e1不可能比e2先出，D）中栈是先进后出的，所以不可能是任意顺序。
B）中出栈过程如下图所示：
（16）B）【解析】栈操作原则上“后进先出”，栈底至栈顶依次存放元素A、B、C、D，则表明这4个元素中D是最后进栈，B、C处于中间，A最早进栈，所以出栈时一定是先出D，再出C，最后出A。
（17）C）【解析】队列是一种操作受限的线性表。
它只允许在线性表的一端进行插入操作，另一端进行删除操作。
其中，允许插入的一端称为队尾（rear），允许删除的一端称为队首（front）。
队列具有先进先出的特点，它是按“先进先出”的原则组织数据的。
（18）C）【解析】考查栈和队列概念的掌握。
栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。
二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的线性表。
（19）A）【解析】本题考查的是线性单链表、双向链表与循环链表的结构及其基本运算。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
故本题答案为A）。
（20）A）【解析】链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。
故链式存储结构下的线性表便于插入和删除操作。
本题答案为A）。
（21）A）【解析】将题中所述的树用图形表示即可得到叶子结点的数目，另外还可用公式n0<=1n2+2n3+3n4+…
+1来计算，其中n0表示叶子结点；1n2中的n2表示度为2的结点。
此题中度为1的结点有4个；度为2的结点有2个；度为3的结点有1个；度为4的结点有1个，计算过程如下：
n0=1n2+2n3+3n4+…+1
n0=1×2+2×1+3×1+1
n0=8
（22）D）【解析】具有3个结点的二叉树有以下的几种形态：
（23）D）【解析】本题考查了二叉树的基本概念。
在二叉树中，叶子节点的度是1；当该二叉树为空
树时，根节点的度为0；为非空树时，根节点的度最大为2。
（24）B）【解析】本题考查二叉树的遍历。
所谓二叉树的前序遍历(DLR)是指在访问根结点、遍历左
子树与遍历右子树这3者中，首先访问根结点，然后遍历左子树，最后遍历右子树，并且，在遍历左右子树
时，上述规则同样适用，即“根→左→右”，故该二叉树的前序遍历结果为“ATBZXCYP”。
（25）D）【解析】前序遍历的第一个结点a为树的根结点；中序遍历中a的左边的结点为a的左子树，a
右边的结点为a的右子树；再分别对a的左右子树进行上述两步处理，直到每个结点都找到正确的位置。
（26）B）【解析】对有序线性表进行顺序查找，首先用被查找的数据和线性表的第一个数据元素进行。
