1、二级公共基础知识-36 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：100.00)1.下列叙述中正确的是_。（分数：2.50）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间2.下列叙述中正确的是_。（分数：2.50）A.算法的复杂度包括时间复杂度与空间复杂度B.算法的复杂度是指算法控制结构的复杂程度C.算法的复杂度是指算法程序中指令的数量D.算法的复杂度是指算法所处理的数据量3.下列叙述中正确的是_。（分数：2.50）A.算法的时间复杂度与计算机的运行速度有关B.算法的时
2、间复杂度与运行算法时特定的输入有关C.算法的时间复杂度与算法程序中的语句条数成正比D.算法的时间复杂度与算法程序编制者的水平有关4.下列叙述中正确的是_。（分数：2.50）A.非线性结构可以为空B.只有一个根结点和一个叶子结点的必定是线性结构C.只有一个根结点的必定是线性结构或二叉树D.没有根结点的一定是非线性结构5.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(f，a)，(d，b)，(e，d)，(c，e)，(a，c) 该数据结构为_。（分数：2.50）A.线性结构B.循环队列C.循环链表D.非线性结构6.下列叙述中正确的是_。（分数：2.50）A.矩阵是非线性结构B.数
3、组是长度固定的线性表C.对线性表只能作插入与删除运算D.线性表中各元素的数据类型可以不同7.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数_。（分数：2.50）A.不同，但元素的存储顺序与逻辑顺序一致B.不同，且其元素的存储顺序可以与逻辑顺序不一致C.相同，元素的存储顺序与逻辑顺序一致D.相同，但其元素的存储顺序可以与逻辑顺序不一致8.下列叙述中正确的是_。（分数：2.50）A.能采用顺序存储的必定是线性结构B.所有的线性结构都可以采用顺序存储结构C.具有两个以上指针的链表必定是非线性结构D.循环队列是队列的链式存储结构9.下列叙述中正确的是_。（分数：2.50）A.在栈中，栈
4、顶指针的动态变化决定栈中元素的个数B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度10.设栈的顺序存储空间为 S(1:m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为_。（分数：2.50）A.0BmC.不可能D.m+111.设栈的存储空间为 S(1:m)，初始状态为 top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中退出一个元素后，栈顶指针 top 值为_。（分数：2.50）A.0B.m-1C.m+1D.产生栈
5、空错误12.下列处理中与队列有关的是_。（分数：2.50）A.二叉树的遍历B.操作系统中的作业调度C.执行程序中的过程调用D.执行程序中的循环控制13.设有栈 S 和队列 Q，初始状态均为空。首先依次将 A，B，C，D，E，F 入栈，然后从栈中退出三个元素依次入队，再将 X，Y，Z 入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为_。（分数：2.50）A.DEFXYZABCB.FEDZYXCBAC.FEDXYZCBAD.DEFZYXABC14.设循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。现经过一系列入队与退队操作后，fron
6、t=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为_。（分数：2.50）A.3B.1C.2D.5215.设循环队列的存储空间为 Q(1:m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为_。（分数：2.50）A.m-1B.m-2C.0D.116.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有_。（分数：2.50）A.节省存储空间B.插入与删除运算效率高C.便于查找D.排序时减少元素的比较次数17.在线性表的链式存储结构中，其存储空间一般是不连续的，并且_。（分数：2.5
7、0）A.前件结点的存储序号小于后件结点的存储序号B.前件结点的存储序号大于后件结点的存储序号C.前件结点的存储序号可以小于也可以大于后件结点的存储序号D.以上三种说法均不正确18.下列叙述中正确的是_。（分数：2.50）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C.循环链表是循环队列的链式存储结构D.循环链表是非线性结构19.下列叙述中正确的是_。（分数：2.50）A.带链栈的栈底指针是随栈的操作而动态变化的B.若带链队列的队头指针与队尾指针相同，则队列为空C.若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素D.不管是
8、顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的20.某带链栈的初始状态为 top=bottom=NuLL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为_。（分数：2.50）A.0B.1C.20D.不确定21.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为_。（分数：2.50）A.0B.1C.1 或 0D.不确定22.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=10，rear=5。该队列中的元素个数为_
9、。（分数：2.50）A.4B.5C.6D.不确定23.下列叙述中错误的是_。（分数：2.50）A.循环链表中有一个表头结点B.循环链表是循环队列的存储结构C.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点D.循环链表实现了空表与非空表运算的统一24.某棵树中共有 25 个结点，且只有度为 3 的结点和叶子结点，其中叶子结点有 7 个，则该树中度为 3 的结点数为_。（分数：2.50）A.6B.7C.8D.不存在这样的树25.度为 3 的一棵树共有 30 个结点，其中度为 3，1 的结点个数分别为 3，4。则该树中的叶子结点数为_。（分数：2.50）A.14B.15C.16D.不
10、可能有这样的树26.深度为 7 的二叉树共有 127 个结点，则下列说法中错误的是_。（分数：2.50）A.该二叉树是满二叉树B.该二叉树有一个度为 1 的结点C.该二叉树是完全二叉树D.该二叉树有 64 个叶子结点27.深度为 5 的完全二叉树的结点数不可能是_。（分数：2.50）A.15B.16C.17D.1828.某完全二叉树共有 256 个结点，则该完全二叉树的深度为_。（分数：2.50）A.7B.8C.9D.1029.在具有 2n 个结点的完全二叉树中，叶子结点个数为_。（分数：2.50）AnB.n+1C.n-1D.n/230.下列叙述中正确的是_。（分数：2.50）A.非完全二叉树
11、可以采用川页序存储结构B.有两个指针域的链表就是二叉链表C.有的二叉树也能用顺序存储结构表示D.顺序存储结构一定是线性结构31.有二叉树如下图所示： （分数：2.50）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH32.设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为_。（分数：2.50）A.JIHGFEDCBAB.DGHEBIJFCAC.GHIJDEFBCAD.ABCDEFGHIJ33.某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBEDA，则前序遍历序列为_。（分数：2.50）A.CBADEB.CBEDA
12、C.ABCDED.EDCBA34.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度(根结点在第 1 层)为_。（分数：2.50）A.2B.3C.4D.535.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为_。（分数：2.50）A.ABCDEFGHB.ABDHECFGC.HDBEAFCCD.HDEBFGCA36.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是_。（分数：2.50）A.前序序列B.中序序列C.
13、后序序列D.前序序列或后序序列37.设二叉树中共有 15 个结点，其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为_。（分数：2.50）A.4B.6C.15D.不存在这样的二叉树38.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为_。（分数：2.50）A.n/4BnC.3n/4D.(n+1)/239.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为_
14、。（分数：2.50）AnB.3n/4C.n/2D.n/440.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是_。（分数：2.50）A.在顺序存储的线性表中寻找最大项B.在顺序存储的线性表中进行顺序查找C.在顺序存储的有序表中进行对分查找D.在链式存储的有序表中进行查找二级公共基础知识-36 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：100.00)1.下列叙述中正确的是_。（分数：2.50）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法 C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间解析：解
15、析 算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。2.下列叙述中正确的是_。（分数：2.50）A.算法的复杂度包括时间复杂度与空间复杂度 B.算法的复杂度是指算法控制结构的复杂程度C.算法的复杂度是指算法程序中指令的数量D.算法的复杂度是指算法所处理的数据量解析：解析 算法复杂度是指算法在编
16、写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。3.下列叙述中正确的是_。（分数：2.50）A.算法的时间复杂度与计算机的运行速度有关B.算法的时间复杂度与运行算法时特定的输入有关 C.算法的时间复杂度与算法程序中的语句条数成正比D.算法的时间复杂度与算法程序编制者的水平有关解析：解析 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的
17、许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。4.下列叙述中正确的是_。（分数：2.50）A.非线性结构可以为空 B.只有一个根结点和一个叶子结点的必定是线性结构C.只有一个根结点的必定是线性结构或二叉树D.没有根结点的一定是非线性结构解析：解析 如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都
18、可以是空的数据结构。树只有一个根结点，但不论有几个叶子结点，树都是非线性结构。5.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(f，a)，(d，b)，(e，d)，(c，e)，(a，c) 该数据结构为_。（分数：2.50）A.线性结构 B.循环队列C.循环链表D.非线性结构解析：解析 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D；二是 D 上的关系，它反映了 D 中各数据元素之间的前后件关系，通常记为 R。即一个数据结构可以表示成 B=(D，R)。其中 B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设 a 与 b 是
19、 D 中的两个数据，则二元组(a，b)表示 a 是 b 的前件，b 是 a 的后件。本题中 R 中的根结点为 f，元素顺序为facedb，满足线性结构的条件。6.下列叙述中正确的是_。（分数：2.50）A.矩阵是非线性结构B.数组是长度固定的线性表 C.对线性表只能作插入与删除运算D.线性表中各元素的数据类型可以不同解析：解析 矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。7.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数_。（分数：2.50）A.不同，但元素的存储顺序与
20、逻辑顺序一致B.不同，且其元素的存储顺序可以与逻辑顺序不一致C.相同，元素的存储顺序与逻辑顺序一致 D.相同，但其元素的存储顺序可以与逻辑顺序不一致解析：解析 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。8.下列叙述中正确的是_。（分数：2.50）A.能采用顺序存储的必定是线性结构B.所有的线性结构都可以采用顺序存储结构 C.具有两个以上指针的链表必定是非线性结构D.循环队列是队列的链式存储结构解析：解析 所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存(按层次依次存放到数据元素中)，
21、但完全二叉树不属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。9.下列叙述中正确的是_。（分数：2.50）A.在栈中，栈顶指针的动态变化决定栈中元素的个数 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度解析：解析 在栈中，通常用指针 top 来指示栈顶的位置，用指针 bottom 指向栈底。栈顶指针 top 动态反应了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据结点的存储序号是不
22、连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。10.设栈的顺序存储空间为 S(1:m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为_。（分数：2.50）A.0BmC.不可能 D.m+1解析：解析 栈为空时，栈顶指针 top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=0，当栈满 top=m，无法继续入栈，top 值不可能为 m+1。11.设栈的存储空间为 S(1:m)，初始状态为 top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中退出一个元素后，栈顶
23、指针 top 值为_。（分数：2.50）A.0B.m-1C.m+1 D.产生栈空错误解析：解析 栈的顺序存储空间为 S(1:m)，初始状态 top=m+1，所以这个栈是 m 在栈底(也可理解为开口向下的栈)。经过一系列入栈与退栈操作后 top=m，则栈中有 1 个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到 m+1 的位置。12.下列处理中与队列有关的是_。（分数：2.50）A.二叉树的遍历B.操作系统中的作业调度 C.执行程序中的过程调用D.执行程序中的循环控制解析：解析 队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有“先进先
24、出”的特性，体现了“先来先服务”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。13.设有栈 S 和队列 Q，初始状态均为空。首先依次将 A，B，C，D，E，F 入栈，然后从栈中退出三个元素依次入队，再将 X，Y，Z 入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为_。（分数：2.50）A.DEFXYZABCB.FEDZYXCBA C.FEDXYZCBAD.DEFZYXABC解析：解析 栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。队列是指允许在一
25、端进行插入，而在另一端进行删除的线性表。将 A，B，C，D，E，F 入栈后，栈中元素为 ABCDEF，退出三个元素入队，队列元素为 FED，将 X，Y，Z 入栈后栈中元素为 ABCXYZ，退栈全部入队后，队列元素为FEDZYXCBA。14.设循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为_。（分数：2.50）A.3B.1C.2 D.52解析：解析 由初始状态为 front=rear=50 可知此时循环队列为空。经过一系列正常的入队和退队操作，由 front
26、=rear=1 可知队列空或者队列满，此后又可以正常地插入了两个元素，说明插入前队列为空，则插入后队列元素个数为 2。15.设循环队列的存储空间为 Q(1:m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为_。（分数：2.50）A.m-1B.m-2 C.0D.1解析：解析 在循环队列中，如果 rear-front0，则队列中的元素个数为 rear-front 个；如果 rear-front0，则队列中的元素个数为 rear-front+m。该题中 m-1m，即 rear-front0，则该循环队列中的元
27、素个数为(m-1)-m+m=m-1。此后从该循环队列中删除一个元素，则队列中的元素个数为 m-1-1=m-2。16.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有_。（分数：2.50）A.节省存储空间B.插入与删除运算效率高 C.便于查找D.排序时减少元素的比较次数解析：解析 线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。 类型 优点 缺点 顺序表 (1)可以随机存取表中的任意结点 (2)无需为表示结点间的逻辑关系额外增加存储空间 (1)插入和删除运算效率低 (2)存储空间不便于扩充 (3)不便于对存储空间的动态分配 链表 (1)在进行插入
28、和删除运算时，只需要改变指针即可，不需要移动元素 (2)存储空间易于扩充并且方便空间的动态分配 需要额外的空间(指针域)来表示数据元素之间的逻辑关系，存储密度比顺序表低 17.在线性表的链式存储结构中，其存储空间一般是不连续的，并且_。（分数：2.50）A.前件结点的存储序号小于后件结点的存储序号B.前件结点的存储序号大于后件结点的存储序号C.前件结点的存储序号可以小于也可以大于后件结点的存储序号 D.以上三种说法均不正确解析：解析 在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，因此前件结点的存储序号与后件结点的存储序号之间不存在
29、大小关系。18.下列叙述中正确的是_。（分数：2.50）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 C.循环链表是循环队列的链式存储结构D.循环链表是非线性结构解析：解析 结点中具有两个指针域的链表既可以是双向链表也可以是二又链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。19.下列叙述中正确的是_。（分数：2.50）A.带链栈的栈底指针是随栈的操作而动态变化的 B.若带链队列的队头指针与队尾指针相同，则队列为空C.若带链队列的队
30、头指针与队尾指针相同，则队列中至少有一个元素D.不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的解析：解析 由于带链栈利用的是计算机存储空间中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。20.某带链栈的初始状态为 top=bottom=NuLL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为_。（分数：2.50）A.0B.1 C.20D.不确定解析：解析 带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为 NULL；栈中只有一个元素时
31、，头指针和尾指针都指向这个元素。21.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为_。（分数：2.50）A.0B.1 C.1 或 0D.不确定解析：解析 带链队列空时，头指针和尾指针都为 NULL；队列中只有一个元素时，头指针和尾指针都指向这个元素。22.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=10，rear=5。该队列中的元素个数为_。（分数：2.50）A.4B.5C.6D.不确定 解析：解析 带链的队列使用了链表来表示队列，而链表中的元
32、素存储在不连续的地址中，因此当front=10，rear=5 时，不能确定队列中元素的个数。23.下列叙述中错误的是_。（分数：2.50）A.循环链表中有一个表头结点B.循环链表是循环队列的存储结构 C.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点D.循环链表实现了空表与非空表运算的统一解析：解析 循环链表是指在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由 NULL 改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。24.某棵树中共有 25 个结点，且只有度为 3 的结点和叶子结点，其中叶子结点有
33、 7 个，则该树中度为 3 的结点数为_。（分数：2.50）A.6B.7C.8D.不存在这样的树 解析：解析 根据题意，树中只有度为 3 的结点和叶子结点(7 个)，则度为 3 的结点有 25-7=18 个；又根据树中的结点数=树中所有结点的度之和+1，设度为 3 的结点数为 n，则 3n+1=25，得 n=8。两种方式得到的度为 3 的结点数不同，故不存在这样的树。25.度为 3 的一棵树共有 30 个结点，其中度为 3，1 的结点个数分别为 3，4。则该树中的叶子结点数为_。（分数：2.50）A.14B.15 C.16D.不可能有这样的树解析：解析 设叶子结点数为 n，则度为 2 的结点数
34、为 30-3-4-n=23-n，根据树中的结点数=树中所有结点的度之和+1，得 33+2(23-n)+14+0n+1=30，则 n=15。26.深度为 7 的二叉树共有 127 个结点，则下列说法中错误的是_。（分数：2.50）A.该二叉树是满二叉树B.该二叉树有一个度为 1 的结点 C.该二叉树是完全二叉树D.该二叉树有 64 个叶子结点解析：解析 满二叉树满足深度为 m 的二叉树最多有 2 m -1 个结点，本题中二叉树深度为 7 且有 127 个结点，满足 2 7 -1=127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第 k 层上有 2 k-1 结点，则该二叉树的叶子结
35、点数为 2 7-1 =64 个。满二叉树不存在度为 1 的结点。27.深度为 5 的完全二叉树的结点数不可能是_。（分数：2.50）A.15 B.16C.17D.18解析：解析 设完全二叉树的结点数为 n，根据深度为 k 的二叉树至多有 2 k -1 个结点，再根据完全二叉树的定义可知，2 k-1 -1n2 k -1。本题中完全二叉树的深度为 5，则 2 5-1 -1n2 5 -1，15n31。因此，结点数不能为 15。28.某完全二叉树共有 256 个结点，则该完全二叉树的深度为_。（分数：2.50）A.7B.8C.9 D.10解析：解析 根据完全二叉树的性质：具有 n 个结点的完全二叉树的
36、深度为log 2 n+1。本题中完全二叉树共有 256 个结点，则深度为log 2 256+1=8+1=9。29.在具有 2n 个结点的完全二叉树中，叶子结点个数为_。（分数：2.50）An B.n+1C.n-1D.n/2解析：解析 由二叉树的定义可知，树中必定存在度为 0 的结点和度为 2 的结点，设度为 0 结点有 a 个，根据度为 0 的结点(即叶子结点)总比度为 2 的结点多一个，得度为 2 的结点有 a-1 个。再根据完全二叉树的定义，度为 1 的结点有 0 个或 1 个，假设度 1 结点为 0 个，a+0+a-1=2n，得 2a=2n-1，由于结点个数必须为整数，假设不成立；当度为
37、 1 的结点为 1 个时，a+1+a-1=2n，得 a=n，即叶子结点个数为 n。30.下列叙述中正确的是_。（分数：2.50）A.非完全二叉树可以采用川页序存储结构B.有两个指针域的链表就是二叉链表C.有的二叉树也能用顺序存储结构表示 D.顺序存储结构一定是线性结构解析：解析 在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此 A 项错误，C 项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此 D 项错误。双向链表也有两个指针域，因此 B 项错误。31.有二叉树如下图所示： （分数：2.50）A.AB
38、DEGCFH B.DBGEAFHCC.DGEBHFCAD.ABCDEFGH解析：解析 前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故本题前序序列是 ABDEGCFH。 中序遍历首先遍历左子树，然后访问跟结点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟结点，最后遍历右子树。故本题的中序序列是 DBGEAFHC。 后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。故本题的后序序列是 DGEBHFCA。32.设二叉树的前序
39、序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为_。（分数：2.50）A.JIHGFEDCBAB.DGHEBIJFCA C.GHIJDEFBCAD.ABCDEFGHIJ解析：解析 二叉树的前序序列为 ABDEGHCFIJ，由于前序遍历首先访问根结点，可以确定该二叉树的根结点是 A。再由中序序列为 DBGEHACIFJ，可以得到结点 D、B、G、E、H 位于根结点的左子树上，结点C、I、F、J 位于根结点的右子树上。由于中序遍历和后序遍历都是先遍历左子树，故本题后序遍历首先访问 D 结点；再由后序遍历是最后访问根结点，故本题后序遍历最后访问的结点是根结点 A。采用排除
40、法可知，后续序列为 DGHEBIJFCA。33.某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBEDA，则前序遍历序列为_。（分数：2.50）A.CBADEB.CBEDAC.ABCDE D.EDCBA解析：解析 二叉树的后序遍历序列为 CBEDA，由于后序遍历最后访问根结点，可以确定该二叉树的根结点是 A。再由中序遍历序列为 CBADE，可以得到子序列(CB)一定在左子树中，子序列(DE)一定在右子树中。结点 C、B 在中序序列和后序序列中顺序未变，说明结点 B 是结点 C 的父结点；结点 D、E 在中序序列和后序序列中顺序相反，说明结点 D 是结点 E 的父结点。因此该二叉树的前序
41、遍历序列为 ABCDE。34.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度(根结点在第 1 层)为_。（分数：2.50）A.2B.3C.4 D.5解析：解析 二叉树的前序序列为 ABCDEFG，则 A 为根结点；中序序列为 DCBAEFG，可知结点 D、C、B 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上。另外，结点 B、C、D 在前序序列和中序序列中顺序相反，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。故二叉树深度为 4。35.某完全二叉树按层次输出(同一层从左到
42、右)的序列为 ABCDEFGH。该完全二叉树的前序序列为_。（分数：2.50）A.ABCDEFGHB.ABDHECFG C.HDBEAFCCD.HDEBFGCA解析：解析 完全二叉树的特点是除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。根据这一特点，再根据题意输出序列为 ABCDEFGH，可以得到该二叉树的结构如下： 36.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是_。（分数：2.50）A.前序序列B.中序序列 C.后序序列D.前序序列或后序序列解
43、析：解析 中序遍历的次序是先遍历左子树，再遍历根结点，最后遍历右子树。而在排序二叉树中，左子树结点值根结点值右子树结点值，要使对排序二叉树的遍历结果为有序序列，只能采用中序遍历。37.设二叉树中共有 15 个结点，其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为_。（分数：2.50）A.4B.6C.15 D.不存在这样的二叉树解析：解析 在具有 n 个结点的二叉树中，如果各结点值互不相同，若该二叉树的前序序列与中序序列相同，则说明该二叉树只有右子树，左子树为空，二叉树的深度为 n；若该二叉树的后序序列与中序序列相同，则说明该二叉树只有左子树，右子树为空，二叉树的深
44、度为 n。故本题中二叉树的深度为 15。38.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为_。（分数：2.50）A.n/4BnC.3n/4D.(n+1)/2 解析：解析 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为 n。则平均比较次数：(1+2+.+n)/n=(n(n+1)/2)/n=(n+1)/2。39.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在中，则出现在表中每个
45、位置上的可能性是相同的。则在平均情况下需要比较的次数大约为_。（分数：2.50）AnB.3n/4 C.n/2D.n/4解析：解析 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为 n。这是找到元素的情况。如果没有找到元素，则要比较 n 次。因此，平均需要比较：找到元素的情况 +未找到元素的情况 =(1+2+n)/n+ ，大约为40.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是_。（分数：2.50）A.在顺序存储的线性表中寻找最大项 B.在顺序存储的线性表中进行顺序查找C.在顺序存储的有序表中进行对分查找D.在链式存储的有序表中进行查找解析：解析 寻找最大项，无论如何都要查看所有的数据，与数据原始排列顺序没有多大关系，无所谓最坏情况和最好情况，或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找，都与要找的数据和原始的数据排列情况有关，最好情况是第 1 次查看的一个数据恰好是要找的数据，只需要比较 1 次；如果没有找到再查看下一个数据，直到找到为止，最坏情况下是最后一次查看的数据才是要找的，顺序查找和对分查找在最坏情况下比较次数分别是 n 和 log 2 n，平均情况则是“1最坏情况”的平均，因而是不同的。
