二级公共基础知识分类模拟题46

二级公共基础知识分类模拟题46

单项选择题

1、下列叙述中正确的是______。

A．所谓算法就是计算方法 B．程序可以作为算法的一种描述方法

C．算法设计只需考虑得到计算结果 D．算法设计可以忽略算法的运算时间

2、下列叙述中正确的是______。

A．算法的复杂度包括时间复杂度与空间复杂度 B．算法的复杂度是指算法控制结构的复杂程度 C．算法的复杂度是指算法程序中指令的数量 D．算法的复杂度是指算法所处理的数据量

3、下列叙述中正确的是______。

A．算法的时间复杂度与计算机的运行速度有关

B．算法的时间复杂度与运行算法时特定的输入有关 C．算法的时间复杂度与算法程序中的语句条数成正比 D．算法的时间复杂度与算法程序编制者的水平有关

4、下列叙述中正确的是______。

A．算法的空间复杂度是指算法程序中指令的条数 B．压缩数据存储空间不会降低算法的空间复杂度

C．算法的空间复杂度与算法所处理的数据存储空间有关 D．算法的空间复杂度是指算法程序控制结构的复杂程度 5、为了降低算法的空间复杂度，要求算法尽量采用原地工作(in place)。所谓原地工作是指______。 A．执行算法时不使用额外空间 B．执行算法时不使用任何存储空间

C．执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化

D．执行算法时所使用的额外空间固定(即不随算法所处理的数据空间大小的变化而变化)

6、下列叙述中正确的是______。 A．非线性结构可以为空

B．只有一个根节点和一个叶子节点的必定是线性结构 C．只有一个根节点的必定是线性结构或二叉树 D．没有根节点的一定是非线性结构

7、设数据结构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．非线性结构

8、下列叙述中正确的是______。

A．矩阵是非线性结构 B．数组是长度固定的线性表

C．对线性表只能作插入与删除运算 D．线性表中各元素的数据类型可以不同

9、在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数______。 A．不同，但元素的存储顺序与逻辑顺序一致

B．不同，且其元素的存储顺序可以与逻辑顺序不一致 C．相同，元素的存储顺序与逻辑顺序一致

D．相同，但其元素的存储顺序可以与逻辑顺序不一致

10、下列叙述中正确的是______。

A．能采用顺序存储的必定是线性结构

B．所有的线性结构都可以采用顺序存储结构 C．具有两个以上指针的链表必定是非线性结构 D．循环队列是队列的链式存储结构

11、下列叙述中正确的是______。

A．在栈中，栈顶指针的动态变化决定栈中元素的个数 B．在循环队列中，队尾指针的动态变化决定队列的长度

C．在循环链表中，头指针和链尾指针的动态变化决定链表的长度 D．在线性链表中，头指针和链尾指针的动态变化决定链表的长度

12、设栈的顺序存储空间为S(1:m)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为______。

A．0 B．m C．不可能 D．m+1

13、设栈的存储空间为S(1:m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中退出一个元素后，栈顶指针top值为______。 A．0 B．m-1 C．m+1 D．产生栈空错误

14、设栈的存储空间为S(1:50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=20，则栈中的元素个数为______。 A．31 B．30 C．21 D．20

15、下列处理中与队列有关的是______。

A．二叉树的遍历 B．操作系统中的作业调度

C．执行程序中的过程调用 D．执行程序中的循环控制

16、设有栈S和队列Q，初始状态均为空。首先依次将A，B，C，D，E，F入栈，然后从栈中退出三个元素依次入队，再将X，Y，Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为______。

A．DEFXYZABC B．FEDZYXCBA C．FEDXYZCBA D．DEFZYXABC

17、下列叙述中正确的是______。 A．循环队列是顺序存储结构 B．循环队列是链式存储结构

C．循环队列空的条件是队头指针与队尾指针相同 D．循环队列的插入运算不会发生溢出现象

18、设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为______。 A．3 B．1 C．2 D．52

19、循环队列的存储空间为Q(1:40)，初始状态为front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为______。 A．14 B．15

C．40 D．39，或0且产生下溢错误

20、设循环队列的存储空间为Q(1:m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为______。 A．m-1 B．m-2 C．0 D．1

21、线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有______。 A．节省存储空间 B．插入与删除运算效率高 C．便于查找 D．排序时减少元素的比较次数

22、在线性表的链式存储结构中，其存储空间一般是不连续的，并且______。 A．前件节点的存储序号小于后件节点的存储序号 B．前件节点的存储序号大于后件节点的存储序号

C．前件节点的存储序号可以小于也可以大于后件节点的存储序号 D．以上三种说法均不正确

23、下列叙述中正确的是______。

A．节点中具有两个指针域的链表一定是二叉链表

B．节点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 C．循环链表是循环队列的链式存储结构 D．循环链表是非线性结构

24、带链的栈与顺序存储的栈相比，其优点是______。 A．入栈与退栈操作方便 B．可以省略栈底指针

C．入栈操作时不会受栈存储空间的限制而发生溢出 D．所占存储空间相同

25、下列叙述中正确的是______。

A．带链栈的栈底指针是随栈的操作而动态变化的

B．若带链队列的队头指针与队尾指针相同，则队列为空

C．若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素

D．不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的

26、某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为______。 A．0 B．1 C．20 D．不确定

27、某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为______。 A．0 B．1 C．10 D．不确定

28、某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为______。 A．0 B．1 C．1或0 D．不确定 29、某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=10，rear=5。该队列中的元素个数为______。 A．4 B．5 C．6 D．不确定

30、下列叙述中错误的是______。 A．循环链表中有一个表头节点 B．循环链表是循环队列的存储结构

C．循环链表的表头指针与循环链表中最后一个节点的指针均指向表头节点 D．循环链表实现了空表与非空表运算的统一

31、某棵树中共有25个节点，且只有度为3的节点和叶子节点，其中叶子节点有7个，则该树中度为3的节点数为______。 A．6 B．7

C．8 D．不存在这样的树

32、度为3的一棵树共有30个节点，其中度为3，1的节点个数分别为3，4。则该树中的叶子节点数为______。

A．14 B．15

C．16 D．不可能有这样的树

33、深度为7的二叉树共有127个节点，则下列说法中错误的是______。 A．该二叉树是满二叉树 B．该二叉树有一个度为1的节点 C．该二叉树是完全二叉树 D．该二叉树有64个叶子节点

34、深度为5的完全二叉树的节点数不可能是______。 A．15 B．16 C．17 D．18

35、某完全二叉树共有256个节点，则该完全二叉树的深度为______。 A．7 B．8 C．9 D．10

36、在具有2n个节点的完全二叉树中，叶子节点个数为______。 A．n B．n+1 C．n-1 D．n/2

37、下列叙述中正确的是______。z

A．非完全二叉树可以采用顺序存储结构 B．有两个指针域的链表就是二叉链表 C．有的二叉树也能用顺序存储结构表示 D．顺序存储结构一定是线性结构

38、有二叉树如下图所示：

则前序序列为______。

A．ABDEGCFH B．DBGEAFHC C．DGEBHFCA D．ABCDEFGH

39、设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为______。 A．JIHGFEDCBA B．DGHEBIJFCA C．GHIJDEFBCA D．ABCDEFGHIJ

40、某二叉树的中序遍历序列为CBADE，后序遍历序列为CBEDA，则前序遍历序列为______。 A．CBADE B．CBEDA C．ABCDE D．EDCBA

41、某二叉树的前序序列为ABCDEFG，中序序列为DCBAFFG，则该二叉树的深度(根节点在第1层)为______。

A．2 B．3 C．4 D．5

42、某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为______。

A．HGFEDCBA B．HFDBGECA C．ABCDEFGH D．ACEGBDFH

43、某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为______。

A．ABCDEFGH B．ABDHECFG C．HDBEAFCC D．HDEBFGCA

44、设非空二叉树的所有子树中，其左子树上的节点值均小于根节点值，而右子树上的节点值均不小于根节点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是______。 A．前序序列 B．中序序列

C．后序序列 D．前序序列或后序序列 45、设二叉树中共有15个节点，其中的节点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为______。 A．4 B．6

C．15 D．不存在这样的二叉树

46、在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为______。 A．n/4 B．n C．3n/4 D．(n+1)/2

47、在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。 A．n B．3n/4 C．n/2 D．n/4

48、下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是______。 A．在顺序存储的线性表中寻找最大项 B．在顺序存储的线性表中进行顺序查找 C．在顺序存储的有序表中进行对分查找 D．在链式存储的有序表中进行查找

49、线性表的长度为n。在最坏情况下，比较次数为n-1的算法是______。 A．顺序查找 B．同时寻找最大项与最小项 C．寻找最大项 D．有序表的插入

50、下列叙述中正确的是______。

A．二分查找法只适用于顺序存储的有序线性表 B．二分查找法适用于任何存储结构的有序线性表 C．二分查找法适用于有序循环链表

D．二分查找法适用于有序双向链表

答案:

单项选择题

1、B

[解析] 算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。 2、A

[解析] 算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。 3、B

[解析] 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。 4、C

[解析] 算法的空间复杂度是指算法在执行过程中所需要的内存空间。算法执行期间所需的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通产采用压缩存储技术，以便尽量减少不必要的额外空间。 5、D

[解析] 对于算法的空间复杂度，如果额外空间量相对于问题规模(即输入数据所占的存储空间)来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。 6、A

[解析] 如果一个非空的数据结构满足下列两个条件：①有且只有一个根节点；②每一个节点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都可以是空的数据结构。树只有一个根节点，但不论有几个叶子节点，树都是非线性结构。 7、A

[解析] 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R。即一个数据结构可以表示成B=(D，R)。其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设a与b是D中的两个数据，则二元组(a，b)表示a是b的前件，b是a的后件。本题中R中的根节点为f，元素顺序为f→a→c→e→d→b，满足线性结构的条件。 8、B

[解析] 矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。 9、C

[解析] 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。 10、B

[解析] 所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存(按层次依次存放到数据元素中)，但完全二叉树属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。 11、A

[解析] 在栈中，通常用指针top来指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。 12、C

[解析] 栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=0，当栈满top=m，无法继续入栈，top值不可能为m+1。 13、C

[解析] 栈的顺序存储空间为S(1:m)，初始状态top=m+1，所以这个栈是m在栈底(也可理解为开口向下的栈)。经过一系列入栈与退栈操作后top=m，则栈中有1个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到m+1的位置。 14、A

[解析] 栈的初始状态top=51，故本栈是51在栈底，入栈时栈顶指针是减操作(top=top-1)，退栈时栈顶指针是加操作(top=top+1)。当top=20时，元素存储在(20:50)空间中，因此共有50-20+1=31个元素。 15、B

[解析] 队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有“先进先出”的特性，体现了“先来先服务”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。 16、B

[解析] 栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将A，B，C，D，E，F入栈后，栈中元素为ABCDEF，退出三个元素入队，队列元素为FED，将X，Y，Z入栈后栈中元素为ABCXYZ，退栈全部入队后，队列元素为FEDZYXCBA。 17、A

[解析] 循环队列是队列的一种顺序存储结构。在循环队列中，在队列满和队列为空时，队头指针与队尾指针均相同；当需要插入的数据大于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象。 18、C

[解析] 由初始状态为front=rear=50可知此时循环队列为空。经过一系列正常的入队和退队操作，由front=rear=1可知队列空或者队列满，此后又可以正常地插入了两个元素，说明插入前队列为空，则插入后队列元素个数为2。 19、D

[解析] 当front=rear=15时可知队列空或者队列满，此后又退出一个元素，如果之前队列为空，退出操作会产生错误，队列里有0个元素；如果退出之前队列已满(40个元素)，执行退出后，队列里还有39个元素。 20、B

[解析] 在循环队列中，如果rear-front＞0，则队列中的元素个数为rear-front个；如果

rear-front＜0，则队列中的元素个数为rear-front+m。该题中m-1＜m，即rear-front＜0，则该循环队列中的元素个数为(m-1)-m+m=m-1。此后从该循环队列中删除一个元素，则队列中的元素个数为m-1-1=m-2。

21、B

[解析] 线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。

类型 优点 缺点 (1)可以随机存取表中的任意节点 (1)插入和删除运算效率低 (2)无须为表示节点间的逻辑关系(2)存储空间不便于扩充 顺序表 额外 (3)不便于对存储空间的动态分配 增加存储空间 (1)在进行插入和删除运算时，只需要 需要额外的空间(指针域)来表示数 改变指针即可，不需要移动元素 据元素之间的逻辑关系，存储密度 链表 (2)存储空间易于扩充并且方便空比顺序表低 间的 动态分配

22、C

[解析] 在线性表的链式存储结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致，因此前件节点的存储序号与后件节点的存储序号之间不存在大小关系。 23、B

[解析] 节点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。 24、C

[解析] 带链的栈就是用一个线性链表来表示的栈，线性链表不受存储空间大小的限制，因此入栈操作时不会受栈存储空间的限制而发生溢出(不需考虑栈满的问题)。 25、A

[解析] 由于带链栈利用的是计算机存储空间中的所有空闲存储节点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。 26、B

[解析] 带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个节点。栈为空时，头指针和尾指针都为NULL；栈中只有一个元素时，头指针和尾指针都指向这个元素。 27、D

[解析] 带链的栈使用了链表来表示栈，而链表中的元素存储在不连续的地址中，因此当top=10，bottom=20时，不能确定栈中元素的个数。 28、B

[解析] 带链队列空时，头指针和尾指针都为NULL；队列中只有一个元素时，头指针和尾指针都指向这个元素。 29、D

[解析] 带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当front=10，rear=5时，不能确定队列中元素的个数。 30、B

[解析] 循环链表是指在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点，最后一个节点的指针域的值由NULL改为指向表头节点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。 31、D

[解析] 根据题意，树中只有度为3的节点和叶子节点(7个)，则度为3的节点有25-7=18个；又根据树中的节点数=树中所有节点的度之和+1，设度为3的节点数为n，则3n+1=25，得n=8。两种方式得到的度为3的节点数不同，故不存在这样的树。

32、B

[解析] 设叶子节点数为n，则度为2的节点数为30-3-4-n=23-n，根据树中的节点数=树中所有节点的度之和+1，得3×3+2×(23-n)+1×4+0×n+1=30，则n=15。 33、B

[解析] 满二叉树满足深度为m的二叉树最多有2m-1个节点，本题中二叉树深度为7且有127个节点，满足27-1=127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第k层上有2k-1节点，则该二叉树的叶子节点数为27-1=64个。满二叉树不存在度为1的节点。 34、A

[解析] 设完全二叉树的节点数为n，根据深度为k的二叉树至多有2k-1个节点，再根据完全二叉树的定义可知，2k-1-1＜n≤2k-1。本题中完全二叉树的深度为5，则25-1-1＜n≤25-1，15＜n≤31。因此，节点数不能为15。 35、C

[解析] 根据完全二叉树的性质：具有n个节点的完全二叉树的深度为[log2n]+1。本题中完全二叉树共有256个节点，则深度为[log2256]+1=8+1=9。 36、A

[解析] 由二叉树的定义可知，树中必定存在度为0的节点和度为2的节点，设度为0节点有a个，根据度为0的节点(即叶子节点)总比度为2的节点多一个，得度为2的节点有a-1个。再根据完全二叉树的定义，度为1的节点有0个或1个，假设度1节点为0个，a+0+a-1=2n，得2a=2n-1，由于节点个数必须为整数，假设不成立；当度为1的节点为1个时，a+1+a-1=2n，得a=n，即叶子节点个数为n。 37、C

[解析] 在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此A项错误，C项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此D项错误。双向链表也有两个指针域，因此B项错误。 38、A

[解析] 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。故本题前序序列是ABDEGCFH。

中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。故本题的中序序列是DBGEAFHC。

后序遍历首先遍历左子树，然后遍历右子树，最后访问根节点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。故本题的后序序列是DGEBHFCA。 39、B

[解析] 二叉树的前序序列为ABDEGHCFIJ，由于前序遍历首先访问根节点，可以确定该二叉树的根节点是A。再由中序序列为DBGEHACIFJ，可以得到节点D、B、G、E、H位于根节点的左子树上，节点C、I、F、J位于根节点的右子树上。由于中序遍历和后序遍历都是先遍历左子树，故本题后序遍历首先访问D节点；再由后序遍历是最后访问根节点，故本题后序遍历最后访问的节点是根节点A。采用排除法可知，后续序列为DGHEBIJFCA。 40、C

[解析] 二叉树的后序遍历序列为CBEDA，由于后序遍历最后访问根节点，可以确定该二叉树的根节点是A。再由中序遍历序列为CBADE，可以得到子序列(CB)一定在左子树中，子序列(DE)一定在右子树中。节点C、B在中序序列和后序序列中顺序未变，说明节点B是节点C的父节点；节点D、E在中序序列和后序序列中顺序相反，说明节点D是节点E的父节点。因此该二叉树的前序遍历序列为ABCDE。 41、C

[解析] 二叉树的前序序列为ABCDEFG，则A为根节点；中序序列为DCBAEFG，可知节点D、C、B位于根节点的左子树上，节点E、F、G位于根节点的右子树上。另外，节点B、C、D在前序序列和中序序列中顺序相反，则说明这三个节点依次位于前一个节点的左子树上；节点E、F、G顺序未变，则说明这三个节点依次位于前一个节点的右子树上。故二叉树深度为4。 42、C

[解析] 二叉树的前序序列为ABDFHCEG，可以确定这个二叉树的根节点是A；再由中序序列

HFDBACEG，可以得到HFDB为根节点A的左子树，CEG为根节点A的右子树。同理依次对左子树HFDB

和右子树CEG进行同样的推理，得到该二叉树的结构如下：

该二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。 43、B

[解析] 完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。根据这一特点，再根据题意输出序列为ABCDEFGH，可以得到该二叉树的结构如下：

故此完全二叉树的前序序列为ABDHECFG。 44、B

[解析] 中序遍历的次序是先遍历左子树，再遍历根节点，最后遍历右子树。而在排序二叉树中，左子树节点值＜根节点值≤右子树节点值，要使对排序二叉树的遍历结果为有序序列，只能采用中序遍历。 45、C

[解析] 在具有n个节点的二叉树中，如果各节点值互不相同，若该二叉树的前序序列与中序序列相同，则说明该二叉树只有右子树，左子树为空，二叉树的深度为n；若该二叉树的后序序列与中序序列相同，则说明该二叉树只有左子树，右子树为空，二叉树的深度为n。故本题中二叉树的深度为15。 46、D

[解析] 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。则平均比较次数：(1+2+…+n)/n=(n(n+1)/2)/n=(n+1)/2。 47、B

[解析] 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。这是找到元素的情况。如果没有找到元素，则

要比较n次。因此，平均需要比较：找到元素的情况×+未找到元素的情况×=(1+2+…+n)/n×

+n×大约为。 48、A

[解析] 寻找最大项，无论如何都要查看所有的数据，与数据原始排列顺序没有多大关系，无所谓最坏情况和最好情况，或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找，都与要找的数据和原始的数据排列情况有关，最好情况是第1次查看的一个数据恰好是要找的数据，只需要比较1次；如果没有找到再查看下一个数据，直到找到为止，最坏情况下是最后一次查看的数据才是要找的，顺序查找和对分查找在最坏情况下比较次数分别是n和log2n，平均情况则是“1～最坏情况”的平均，因而是不同的。 49、C

[解析] 顺序查找要逐个查看所有元素，会比较n次。在最坏情况下，寻找最大项无论如何需要查看表中的所有元素，n个元素比较次数为n-1。同时寻找最大项和最小项，需要为判断较大值和较小值分别进行比较，会有更多的比较次数。有序表的插入最坏情况下是插入到表中的最后一个元素的后面位置，则会比较n次。 50、A

[解析] 二分查找法(又称对分查找法)只适用于顺序存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列(即从小到大，但允许相邻元素值相等)。