1.2 历年试题解析
试题1
下列链表中，其逻辑结构属于非线性结构的是（ ）。
A.循环链表
B.双向链表
C.带链的栈
D.二叉链表
【分析】循环链表、双向链表、带链的栈都是线性结构，二叉链表是非线性结构二叉树的链式存储结构，所以选D。
【答案】D
试题2
设循环队列的存储空间为Q(1：35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为（ ）。
A.16
B.20
C.0或35
D.15
【分析】在循环队列中，当头指针=尾指针时，有两种情况，一个是队空状态，一个是队满状态。该循环队列的初始状态是队头指针=队尾指针=35，经过一系列入队与退队运算后，队头指针和队尾指针都发生了变化，但还是队头指针等于队尾指针，队空时，循环队列中的元素个数是0，队满时，元素个数是循环队列的最大空间35。
【答案】C
试题3
下列关于栈的叙述中，正确的是（ ）。
A.栈顶元素一定是最先入栈的元素
B.栈操作遵循先进后出的原则
C.栈底元素一定是最后入栈的元素
D.以上三种说法都不对
【分析】栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的这一端称为栈顶，不允许插入与删除的另一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。
【答案】B
试题4
下列叙述中正确的是（ ）。
A.循环队列是队列的一种链式存储结构
B.循环队列是一种逻辑结构
C.循环队列是队列的一种顺序存储结构
D.循环队列是非线性结构
【分析】循环队列是一种顺序存储的线性结构。
【答案】C
试题5
下列叙述中正确的是（ ）。
A.栈是一种先进先出的线性表
B.队列是一种后进先出的线性表
C.栈与队列都是非线性结构
D.以上三种说法都不对
【分析】栈和队列都是线性结构，所以选项C错误；栈是一种先进后出的线性表，故选项A错误；队列是一种先进先出的线性表，故选项B错误，所以选D。
【答案】D
试题6
一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为（ ）。
A.4
B.16
C.10
D.6
【分析】由二叉树的性质3可知，度为0的结点数（即叶子结点数）总是比度为2的结点多一个，此题中叶子结点数为5，所以度为2的结点数为4，二叉树的总结点数=叶子结点数+度为1的结点数+度为2的结点数，所以此题度为1的结点数为25-5-4=16。
【答案】B
试题7
下列叙述中正确的是（ ）。
A.算法的效率只与问题的规模有关，而与数据的存储结构无关
B.算法的时间复杂度是指执行算法所需要的计算工作量
C.数据的逻辑结构与存储结构是一一对应的
D.算法的时间复杂度与空间复杂度一定相关
【分析】根据算法时间复杂度和空间复杂度的定义可知，算法的时间复杂度就是执行该算法所需要的计算工作量，算法所执行的基本运算次数与问题的规模有关；而算法的空间复杂度就是执行该算法所需要的内存空间。通常用时间复杂度和空间复杂度来衡量算法的效率，但是算法的时间复杂度与空间复杂度并不一定相关。数据的逻辑结构是指各个数据元素之间的逻辑关系，反映人们对数据含义的理解，与数据的存储结构没有关系，是独立于计算机的。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。
【答案】B
试题8
下面对队列的叙述正确的是（ ）。
A.队列属于非线性表
B.队列按“先进后出”原则组织数据
C.队列在队尾删除数据
D.队列按“先进先出”原则组织数据
【分析】队列是限定了插入和删除操作的线性表，它只允许在表的一端进行插入操作，而在另外一端进行删除操作。在队列中，允许插入元素的一端称为队尾，允许删除元素的一端称为队头。队列按照“先进先出”的原则组织数据，因此又称为“先进先出”的线性表。
【答案】D
试题9
对图1-40的二叉树进行前序遍历的结果为（ ）。
图1-40 二叉树
A.DYBEAFCZX
B.YDEBFZXCA
C.ABDYECFXZ
D.ABCDEFXYZ
【分析】前序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则1）访问根结点；2）前序遍历左子树；3）前序遍历右子树。根据题目可知，该二叉树前序遍历的结果是：ABDYECFXZ。
【答案】C
试题10
某二叉树中有n个度为2的结点，则该二叉树中的叶子结点为（ ）。
A.n+1
B.n-1
C.2n
D.n/2
【分析】根据二叉树的性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。本题中度为2的结点数为n，故叶子结点数为n+1个。
【答案】A
试题11
下列叙述正确的是（ ）。
A.算法就是程序
B.设计算法时只需要考虑数据结构的设计
C.设计算法时只需要考虑结果的可靠性
D.以上三种说法都不对
【分析】算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。程序（program）是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。因此，算法不等于程序。因为每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列，所以设计算法时，不仅要考虑算法中对数据的运算和操作，同时还要考虑算法的控制结构。一个算法的功能不但取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。
【答案】D
试题12
下列关于线性链表的叙述中，正确的是（ ）。
A.各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C.进行插入与删除时，不需要移动表中的元素
D.以上三种说法都不对
【分析】线性表是一个线性结构，它是一个含有n≥0个结点的有限序列。线性表的链式存储称为线性链表，指的是用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。链表是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。在线性链表中插入或删除一个元素，不需要移动表中的数据元素，只需要改变被插入或删除元素所在结点及其前后结点的指针域即可。
【答案】C
试题13
下列关于二叉树的叙述中，正确的是（ ）。
A.叶子结点总是比度为2的结点少一个
B.叶子结点总是比度为2的结点多一个
C.叶子结点数是度为2的结点数的两倍
D.度为2的结点数是度为1的结点数的两倍
【分析】根据二叉树的性质，对于任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。
【答案】B
试题14
下列关于栈的叙述正确的是（ ）。
A.栈顶元素最先能被删除
B.栈顶元素最后才能被删除
C.栈底元素永远不能被删除
D.以上三种说法都不对
【分析】栈是限定只在一端进行插入与删除的特殊线性表。允许进行插入和删除操作的一端称为栈顶（top），另一端为栈底（bottom）。栈底固定，而栈顶浮动。栈按照“后进先出”的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据时，从栈顶开始弹出数据（最后一个进入的数据被第一个读出来）。因此，栈顶的元素最先被删除。
【答案】A
试题15
下列叙述中正确的是（）。
A.有一个以上根结点的数据结构不一定是非线性结构
B.只有一个根结点的数据结构不一定是线性结构
C.循环链表是非线性结构
D.双向链表是非线性结构
【分析】线性结构指的是数据元素之间存在“一对一”线性关系的数据结构，这样的结构中只有一个根结点，如循环链表和双向链表。非线性结构指的是数据元素之间存在“一对一”非线性关系的数据结构，这样的结构中可能有一个根结点，如树形结构，也可能有多个根结点，如网状结构。
【答案】B
试题16
某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）（ ）。
A.3
B.4
C.6
D.7
【分析】叶子结点个数=度为2的结点个数+1。在此题中，叶子结点个数为1，说明度为2的结点数为0，即二叉树中不存在度为2的结点，只有度为1的结点和叶子结点，那么此二叉树就是一棵单分支树，树中结点个数即为树的深度。
【答案】D
试题17
下列叙述中正确的是（ ）。
A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D.上述3种说法都不对
【分析】顺序存储结构是存储结构类型中的一种，该结构把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构借助于计算机程序设计语言的数组来描述。顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用于存放结点的数据，而结点之间的逻辑关系没有占用额外的存储空间。
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储数据外，还需要存储一个到多个指针，而顺序存储不需要存储地址，所以从存储大小来看，自然是链表占空间大，不过访问灵活链表有很大的优势。
【答案】B
试题18
下列叙述中正确的是（ ）。
A.在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
D.上述3种说法都不对
【分析】栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称“后进先出”表，因此，在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化。
【答案】C
试题19
下列叙述中正确的是（ ）。
A.对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)
C.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)
D.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)
【分析】对长度为n的有序链表进行查找，最坏情况是从最小值开始查找最大值（或从最大值开始查找最小值），这个过程需要比较的次数为n，故选项A正确。对分查找只能针对随机存取的有序表进行，而有序链表只能进行顺序存取，不能进行随机存取，因此在有序链表上不能进行对分查找，故B、C、D选项都错误。
【答案】A
试题20
算法的时间复杂度是指（ ）。
A.算法的执行时间
B.算法所处理的数据量
C.算法程序中的语句或指令条数
D.算法在执行过程中所需要的基本运算次数
【分析】所谓算法的时间复杂度，是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，一个算法的工作量不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
【答案】D
试题21
下列数据结构中，属于非线性结构的是（ ）。
A.循环队列
B.带链队列
C.二叉树
D.带链栈
【分析】线性结构满足两个条件：有且仅有一个根结点；每个结点最多有一个直接前驱，也最多有一个直接后继。栈和队列均满足这两个条件，属于线性结构。二叉树属于非线性结构，因为除了叶子结点外，其他每个结点都可以有两个直接后继，不满足线性结构的条件。
【答案】C
试题22
下列数据结构中，能按照“先进后出”原则存取数据的是（ ）。
A.循环队列
B.栈
C.队列
D.二叉树
【分析】栈是一种特殊的线性表，其插入或者删除运算都在表的一端进行，即按照“先进后出”原则存取数据。
【答案】B
试题23
对于循环队列，下列叙述中正确的是（ ）。
A.队头指针是固定不变的
B.队头指针一定大于队尾指针
C.队头指针一定小于队尾指针
D.队头指针可以大于队尾指针，也可以小于队尾指针
【分析】在循环队列中用队尾指针（rear）指向队列中的队尾元素，用队头指针（front）指向队头元素的前一个位置。在循环队列结构中，一般情况下rear>front。当存储空间的最后一个位置已被使用，而要进行入队操作时，只要存储空间的第一个位置空闲，便可将元素加入第一个位置，即存储空间的第一个位置为队尾，此时便有front>rear。
【答案】D
试题24
算法的空间复杂度是指（ ）。
A.算法在执行过程中所需要的计算机存储空间
B.算法所处理的数据量
C.算法程序中的语句或指令条数
D.算法在执行过程中所需要的临时工作单元数
【分析】算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间。
【答案】A
试题25
下列叙述中正确的是（ ）。
A.栈是“先进先出”的线性表
B.队列是“先进后出”的线性表
C.循环队列是非线性结构
D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
【分析】栈是限定仅在表尾进行插入和删除操作的线性表，又称为“后进先出”的线性表。队列是限定了插入和删除操作的线性表，又称为“先进先出”的线性表。循环队列是队列的顺序存储结构。线性表（无论有序还是无序）既可以采用顺序存储结构，也可以采用链式存储结构。
【答案】D
试题26
支持子程序调用的数据结构是（ ）。
A.栈
B.树
C.队列
D.二叉树
【分析】栈是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表；队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种操作受限的线性表；二叉树是有限元素的集合，该集合或者为空，或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。这里只有栈支持子程序调用。
【答案】A
试题27
某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（ ）。
A.10
B.8
C.6
D.4
【分析】在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。本题中度为2的结点数为5，故叶子结点数为5+1=6个。
【答案】C
试题28
下列排序方法中，最坏情况下比较次数最少的是（ ）。
A.冒泡排序
B.简单选择排序
C.直接插入排序
D.堆排序
【分析】对于长度为n的线性表，在最坏情况下，快速排序所需要的比较次数为n*(n-1)/2；冒泡排序所需要的比较次数为n*(n-1)/2；直接插入排序所需要的比较次数为n*(n-1)/2；堆排序所需要的比较次数为O(nlog2n)。
【答案】D
试题29
一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A.12345ABCDE
B.EDCBA54321
C.ABCDE12345
D.54321EDCBA
【分析】栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。这表明栈的运算规则是“先进后出”或称“后进先出”。在栈顶进行插入运算，称为进栈（或入栈），在栈顶进行删除运算，称为退栈（或出栈）。本题中，依次进栈，即依次插入元素1、2、3、4、5、A、B、C、D、E，依次出栈，即依次删除元素，根据栈“先进后出”的规则，应该以倒序出栈，即元素出栈顺序为EDCBA54321。
【答案】B
试题30
下列叙述中正确的是（ ）。
A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D.循环队列中元素的个数是由队头指针和队尾指针共同决定的
【分析】所谓循环队列，就是将队列存储空间的最后一个位置绕到第1个位置，形成逻辑上的环状空间，供队列循环使用。循环队列的头指针front指向队列第一个元素的前一位置，队尾指针rear指向队列最后一个元素，循环队列的动态变化需要头尾指针共同反映。因为循环队列的长度是(rear-front+MaxSize)%MaxSize，所以循环队列的长度由队头和队尾指针共同决定。
【答案】D
试题31
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。
A.O(n)
B.O(n2)
C.O(log2n)
D.O(nlog2n)
【分析】二分法检索要求线性表结点按关键值排序，且以顺序方式存储。在查找时，应与表的中间位置上结点的关键值比较，若相等则检索成功；否则根据比较结果确定下一步在表的前半部分或后半部分继续进行。二分法检索的效率比较高，设线性表有n个元素，则最多的检索次数为大于log2n的最小整数，最少的检索次数为1。
【答案】C
试题32
下列叙述中正确的是（ ）。
A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的
B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构
C.顺序存储结构能存储有续表，链式存储结构不能存储有序表
D.链式存储结构比顺序存储结构节省存储空间
【分析】顺序存储结构就是用一组地址连续的存储单元依次存储该线性表中的各个元素；链式存储结构中各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。两者都可以存储线性的、有序的逻辑结构。顺序结构使用的是连续物理空间，链式结构可以使用零散的物理空间存储，链式结构更灵活，不存在哪个更节约空间的说法。
【答案】A