1、考研计算机学科专业基础综合-5-1 及答案解析(总分：149.97，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.关于线性表的顺序存储结构和链式存储结构的描述正确的是_。线性表的顺序存储结构优于其链式存储结构链式存储结构比顺序存储结构可更方便地表示各种逻辑结构如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构顺序存储结构和链式存储结构都可以进行顺序存储 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.2.相对于单向链表，使用双向链表存储线性表，其优点是_。提高查找速度 节约存储空间 数据的插入和删除更快速 A.仅 B.仅、 C
2、.仅 D.仅、（分数：2.00）A.B.C.D.3.下列关于二叉树的说法中，错误的是_。 A.在二叉树的后序序列中最后一个结点一定是二叉树的根结点 B.在二叉树的中序序列中最后一个结点一定是二叉树的一个叶结点 C.在二叉树的前序序列中最后一个结点一定是二叉树的一个叶结点 D.在二叉树的层序序列中最后一个结点一定是二叉树的一个叶结点（分数：2.00）A.B.C.D.4.设一棵二叉树是由森林转换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点个数为_。 A.n-1 B.n C.n+1 D.n+2（分数：2.00）A.B.C.D.5.若某完全二叉树的结点个数为 100，则第 60 个结
3、点的度为_ A.0 B.1 C.2 D.不确定（分数：2.00）A.B.C.D.6.如果二叉树中结点的先序序列是ab，中序序列是ba，则_。 A.结点 a 和结点 b 分别在某结点的左子树和右子树中 B.结点 b 在结点 a 的右子树中 C.结点 b 在结点 a 的左子树中 D.结点 a 和结点 b 分别在某结点的两棵非空子树中（分数：2.00）A.B.C.D.7.已知一棵 5 阶 B 树有 53 个关键字，并且每个结点的关键字都达到最少状态，则它的深度是_。 A.3 B.4 C.5 D.6（分数：2.00）A.B.C.D.8.设图 G=(V，E)，其中：V=V0，V 1，V 2，V 3)E=
4、(V0，V 1)，(V 0，V 2)，(V 0，V 3)，(V 1，V 3)则从顶点 v0 开始对图 G 的深度优先遍历序列总共有_种。 A.3 B.4 C.5 D.2（分数：2.00）A.B.C.D.9.下列说法中正确的是_。对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为 50顺序查找法只适合于顺序存储结构，不适合于链式存储结构折半查找过程所对应判定树是一棵完全二叉树理想情况下，散列表的平均比较次数可达到 1 次 A.、 B.、 C.、 D.、（分数：2.00）A.B.C.D.10.用某种排序方法对线性表24，88，21，48，15，27，69，35，20进行排序时，元
5、素序列的变化情况如下：(1)24，88，21，48，15，27，69，35，20 (2)20，15，21，24，48，27，69，35，88(3)15，20，21，24，35，27，48，69，88 (4)15，20，21，24，27，35，48，69，88所采用的排序方法是： A.快速排序 B.选择排序 C.希尔排序 D.归并排序（分数：2.00）A.B.C.D.11.假设在磁盘上存放有 375000 个记录，做 5 路平衡归并排序，内存工作区能容纳 600 个记录，为把所有记录都排好序，需要作_趟归并排序。 A.3 B.4 C.5 D.6（分数：2.00）A.B.C.D.12.假定有两个带
6、符号整数 x、y 用 8 位补码表示，x=63，y=-31，则 x-y 的机器数及其相应的溢出标志 OF分别是_。 A.5DH、0 B.5EH、0 C.5DH、1 D.5EH、1（分数：2.00）A.B.C.D.13.十进制数-5 基于单精度浮点数 IEEE 754 标准的编码是_。(注：单精度浮点数 IEEE 754 格式为符号位 1 位、尾数 23 位、阶码 8 位，且阶码用移码表示) A.(C0A00000)16 B.(81D00000)16 C.(41500000)16 D.(01D00000)16（分数：2.00）A.B.C.D.14.在虚拟存储器中，当程序正在执行时，由_完成地址映
7、射。 A.程序员 B.操作系统 C.硬件 D.装入程序（分数：2.00）A.B.C.D.15.下列_措施可以提高 Cache 命中率。提高相联度设置替换缓存保存刚被替换的块通过编译优化改善程序的访存局部性 A.仅、 B.仅、 C.仅、 D.、和（分数：2.00）A.B.C.D.16.假设某计算机采用小端方式存储，按字节编址。一维数组 a 有 100 个元素，其类型为 float，存放在地址 C000 1000H 开始的连续区域中，则最后一个数组元素的最高有效位(MSB)所在的地址应为_。 A.C000 1396H B.C000 1399H C.C000 118CH D.C000 118FH（分
8、数：2.00）A.B.C.D.17.某机器中有 16 个寄存器，假设机器字长为 12 位，下列_指令可以使用单字长指令来实现。4 条三寄存器指令 255 条单寄存器指令 16 条 0 寄存器指令 A.仅、 B.仅、 C.仅、 D.仅（分数：2.00）A.B.C.D.18.在一条无条件跳转指令的指令周期内，程序计数器(PC)的值被修改了_次。(注：指令均为单字长指令，且按字寻址) A.1 B.2 C.3 D.不能确定（分数：2.00）A.B.C.D.19.下列关于多核处理器说法中，正确的是_。多核表明一个处理器拥有多个芯片维持 Cache 一致性为其主要技术之一多核之间共享一个统一地址空间 A.
9、仅、 B.仅、 C.仅、 D.、和（分数：2.00）A.B.C.D.20.假设计算机系统中软盘以中断方式与 CPU 进行数据交换，主频为 50MHz，传输单位为 16 位，软盘的数据传输率为 50kB/s。若每次数据传输的开销(包括中断响应和中断处理)为 100 个时钟周期，则软盘工作时 CPU 用于软盘数据传输的时间占整个 CPU 时间的百分比是_。 A.0% B.5% C.1.5% D.15%（分数：2.00）A.B.C.D.21.某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总线判优控制，则该机为实现总线判优控制需要的控制线数为_。 A.3 B.16 C.5 D.无法确定（
10、分数：2.00）A.B.C.D.22.下列说法中，错误的是_。程序中断过程是由硬件和中断服务程序共同完成的每条指令的执行过程中，每个总线周期要检查一次有无中断请求检测有无 DMA 请求，一般安排在一条指令执行过程的末尾中断服务程序的最后指令是无条件转移指令 A.仅、 B.仅、 C.仅、 D.、（分数：2.00）A.B.C.D.23.下列说法中，正确的有_。清除内存、设置时钟都是特权指令，只能在内核态(系统态、管态)下执行用零作除数将产生中断用户态到内核态的转换是由硬件完成的在中断发生后，进入中断处理的程序可能是操作系统程序，也可能是应用程序 A.仅、 B.仅、 C.仅、 D.、（分数：2.00
11、）A.B.C.D.24.支持多道程序设计的操作系统在运行过程中，会不断选择新进程来运行，以共享 CPU 资源，但是下面_不是操作系统选择新进程的直接原因。 A.运行进程的时间片用完 B.运行进程出错 C.运行进程等待某个事件的发生 D.有新的进程被创建进入就绪队列（分数：2.00）A.B.C.D.25.下列_调度算法不适合交互式操作系统。 A.高响应比优先 B.高优先级优先 C.时间片轮转 D.先来先服务（分数：2.00）A.B.C.D.26.关于临界问题的一个算法(假设只有进程 P0和 P1可能会进入该临界区)如下(i 为 0 或 1)：repeatretry:if(turn!=-1) tu
12、rn=i;if(turn!=i) go to retry;turn=-1;临界区;turn=0;其他区域;until false;该算法_。 A.不能保持进程互斥进入临界区，会出现“饥饿” B.不能保持进程互斥进入临界区，不会出现“饥饿” C.保证进程互斥进入临界区，会出现“饥饿” D.保证进程互斥进入临界区，不会出现“饥饿”（分数：2.00）A.B.C.D.27.设 m 为同类资源数，n 为系统中并发进程数。当 n 个进程共享 m 个互斥资源时，每个进程最大需求为w，则下列情况会出现系统死锁的是_。 A.m=2，n=1，w=2 B.m=2，n=2，w=1 C.m=4，n=3，w=2 D.m=
13、4，n=2，w=3（分数：2.00）A.B.C.D.28.下列关于页式存储说法中，正确的是_。在页式存储管理中，若关闭 TLB，则每当访问一条指令或存取一个操作数时都要访问两次内存页式存储管理不会产生内部碎片页式存储管理当中的页面是为用户所感知的页式存储方式可以采用静态重定位 A.仅、 B.仅、 C.仅 D.、（分数：2.00）A.B.C.D.29.有一个矩阵为 100200，即 a100200。在一个虚拟系统中，采用 LRU 算法。系统分给该进程 5 个页面来存储数据(不包含程序)，设每页可存放200 个整数，该程序要对整个数组初始化，数组存储时是按行存放的。试计算下列两个程序各自的缺页次数
14、(假定所有页都以请求方式调入)。程序一：for(i=0;i=99;i+)for(j=0;j=199;j+)Aij=i*j;程序二：for(j=0;j=199;j+)for(i=0;i=99;i+)Aij=i*J; A.100，200 B.100，20000 C.200，100 D.20000，100（分数：2.00）A.B.C.D.30.当数据(1)很少修改并且以随机顺序频繁地访问时(变长记录文件)(2)频繁地修改并且相对频繁地访问文件整体时(变长记录文件)(3)频繁顺序地访问文件元素(定长记录文件)依次从访问速度、存储空间的使用和易于更新(添加/删除/修改)这几个方面考虑(访问速度最优先考虑
15、，其次是存储开销，再次是易于更新)，为了达到最大效率，你将分别选择_文件组织。顺序文件 索引文件 索引顺序文件 A.、 B.、 C.、 D.、（分数：2.00）A.B.C.D.31.某文件系统采用多级索引的方式组织文件的数据存放，假定在文件的 i_node 中设有 13 个地址项，其中直接索引 10 项，一次间接索引项 1 项，二次间接索引项 1 项，三次间接索引项 1 项。数据块大小为4KB，磁盘地址用 4B 表示，请问这个文件系统允许的最大文件长度约为_。 A.1T B.2T C.3T D.4T（分数：2.00）A.B.C.D.32.下列有关通道技术的叙述中，不正确的是_。通道可视为一种软
16、件，其作用是提高了 CPU 的利用率编制好的通道程序是存放在主存储器中的通道又称 I/O 处理机，它用于实现 CPU 与 I/O 设备之间的信息传输通道程序是由一系列通道指令组成的 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.33.通过 IEEE 802.3 局域网传送 ASCII 码信息“Good morning!”，若封装成一个 MAC 帧，则该帧的数据字段的有效字节为_，需要填充_个字节。 A.12、34 B.13、34 C.13、33 D.12、33（分数：2.00）A.B.C.D.34.在异步通信中，每个字符包含 1 位起始位、7 位数据位、l 位奇偶位和
17、 2 位终止位，若每秒传送 100 个字符，采用 4 相位调制，则码元速率为_。 A.50 波特/s B.500 波特/s C.550 波特/s D.1100 波特/s（分数：2.00）A.B.C.D.35.假设有一个 12 位的海明码(采用偶校验编码，且最多只有 1 位发生错误)，其十六进制的值为 ACFH，请问原来的值是_。 A.EFH B.AFH C.4FH D.BFH（分数：2.00）A.B.C.D.36.下列说法中，错误的是_。0.0.0.0 不能作为目的 IP 地址100255255255 不能作为源 IP 地址255255255255 可作为目的 IP 地址127001 既可以作
18、为目的 IP 地址，也可以作为源 IP 地址 A.仅 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.37.设有下面 4 条路由：172.18.129.0/24、172.18.130.0/24、172.18.132.0/24 和 172.18.133.0/24，如果进行路由聚合，能覆盖这 4 条路由的地址是_。 A.172.18.128.0/21 B.172.18.128.0/22 C.172.18.130.0/22 D.172.18.132.0/23（分数：2.00）A.B.C.D.38.在下列地址中，属于子网 86.32.0.0/12 的地址是_。86.33.224.123
19、86.79.65.126 86.68.65.216 A.仅 B.仅、 C.仅、 D.仅（分数：2.00）A.B.C.D.39.下列说法中，错误的是_。TCP 不支持广播服务如果用户程序使用 UDP 协议，则应用层必须承担数据传输的可靠性UDP 数据报首部包含 UDP 源端口、UDP 目的端口、UDP 数据报首部长度和校验和TCP 协议采用的滑动窗口协议能够解决拥塞控制问题 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.40.下列说法中，错误的是_。在 FTP 协议中，使用数据连接传输用户名和密码FTP 协议既可以使用 TCP，也可以使用 UDP，因为 FTP 本身具备
20、差错控制能力SMTP 协议不但可以传输 ASCII 码数据，还可以传送二进制数据在万维网中，使用 URL 来表示在因特网上得到的资源位置 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.二、B综合应用题/B(总题数：7，分数：70.00)对给定的有 7 个顶点 v1，v2，v7 的有向图的邻接矩阵如下表所示。 B邻接矩阵/B 2 5 3 2 8 1 3 5 5 3 9 5 （分数：10.00）(1).画出该有向图；（分数：2.50）_(2).画出其邻接表；（分数：2.50）_(3).从 v1 出发到其余各项点的最短路径长度；（分数：2.50）_(4).若将图看成 AOE
21、 网，列出其关键活动及相应的有向边i，j，w，i，j 为顶点，w 为权值，试问其关键路径的长度是多少?（分数：2.50）_输入一个按升序排序过的整数数组(1、2、4、7、11、15)以及一个整数数字15，我们可以从该数组中找到两个数字，即 4 和 11，使得 4+11=15。请实现一个时间上尽可能高效率的算法，当输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：（分数：12.99）(1).给出算法的基本设计思想。（分数：4.33）_(2).根据设计思想，采用 C 或 C+或
22、Java 语言描述算法，关键之处给出注释。（分数：4.33）_(3).说明你所设计算法的时间复杂度。（分数：4.33）_某高级语言程序中的一个 while 语句为“while(savei=k)i+=1;”，若对其编译时，编译器将 i 和 k 分别分配在寄存器 s3 和 s5 中，数组 save 的基址存放在 s6 中，则生成的 MIPS 汇编代码如下：loop: sll t1,s3,2 #Rt1Rs32,即 Rt1=i*4add t1,t1,s6 #Rt1Rt1+Rs6,即 Rt1=Address of saVeilw t0,0(t1) #Rt0MRt1+0，即 Rt0=saveibne t0
23、,s5,exit #if Rt0Rs5 then goto exitaddi s3,s3,1 #Rs3Rs3+1,即 i=i+1j loop #goto loopexit;假设从 loop 处开始的指令序列存放在内存 80000 处，则上述循环对应的 MIPS机器码如下图所示。（分数：10.98）(1).MIPS 的编址单位是多少?数组 save 每个元素占几个字节?（分数：1.83）_(2).为什么指令“sll t1，s3，2”能实现 4*i 的功能?（分数：1.83）_(3).t0 和 s6 的编号各为多少?（分数：1.83）_(4).指令“i loop”的操作码是什么?(用二进制表示)（
24、分数：1.83）_(5).标号 exit 的值是多少?如何根据指令计算得到?（分数：1.83）_(6).标号 loop 的值是多少?如何根据指令计算得到?（分数：1.83）_假设某计算机的主存地址空间大小为 64KB，采用字节编址方式。其 Cache 数据区容量为 4KB，采用 4 路组相联映射方式、LRU 替换和回写(write back)策略，块大小为 64B，并且每块设置了 1 位有效位。请问：（分数：12.00）(1).主存地址字段如何划分?要求说明每个字段的含义、位数和在主存地址中的位置。（分数：4.00）_(2).该 Cache 的总容量有多少位?（分数：4.00）_(3).若 C
25、ache 初始为空，CPU 依次从 0 号地址单元顺序访问到 4344 号单元，重复按此序列共访问 16 次。若 Cache 命中时间为 20ns，主存存取时间为 200ns，试估计 CPU 访存的平均时间。（分数：4.00）_在下列代码中，有 3 个进程 P1、P2 和 P3，它们使用了字符输出函数 putc 来进行输出(每次输出一个字符)，并使用了两个信号量 L 和 R 来进行进程间的同步。请问：semaphore L=3,R=0; /*初始化*/*进程 P1*/ /*进程 P2*/ /*进程 P3*/while(1) while(1) while(1) P(L); P(R); P(R);
26、putc(C); putc(A); putc(D);V(R); putc(B); V(R);（分数：8.00）(1).这组进程在运行时，最后打印出来了多少个“D”字符?（分数：2.00）_(2).当这组进程在运行的时候，在何种情形下，打印出来的字符“A”的个数是最少的，最少的个数是多少?（分数：2.00）_(3).当这组进程在运行的时候，“CABABDDCABCABD”是不是一种可能的输出序列，为什么?（分数：2.00）_(4).当这组进程在运行的时候，“CABACDBCABDD”是不是一种可能的输出序列，为什么?（分数：2.00）_某操作系统支持页式虚拟存储管理，其中央处理器的周期是 1s。
27、当不是处于同一页面时，访问另一个页面耗时 1s。一个页面含 1K 字。使用磁盘作为外存，其转速为 3000r/min，传输率 1M 字/s。还测得下列数据：磁盘平均寻道时间为 19ms，1%的指令要访问不处于同一页面的其他页面内容，这当中，80%的被访问页已经在内存中。需要新页面时，50%的被换出页面已经修改过了。（分数：7.00）(1).如果磁盘设备要连续传输 10K 字的数据，请计算出平均情况下总的访问时间。（分数：3.50）_(2).请计算该系统的有效指令时间，假设系统只有一个 CPU，而且它在磁盘传输数据时是空闲的。(假设逻辑相邻的页面在磁盘上都不相邻。)（分数：3.50）_某单位有
28、1 个总部和 6 个分部，各个部门都有自己的局域网。该单位申请了 6个 C 类 IP 地址 202.115.10.0/24202.115.15.0/24，其中总部与分部 4 共用一个 C 类地址。网络采用 R1R7 共 7 台路由器，采用动态路由协议 OSPF，并划分了 3 个 OSPF 区域。网络拓扑图如下图所示，路由器的 IP 地址分配表如下表所示。试问： （分数：9.00）(1).请指出本网中哪个区域为主干区域，以及指出主干区域中的区域边界路由器及区域内路由器。（分数：3.00）_(2).R3 路由器各端口 IP 地址如何设置?（分数：3.00）_(3).如部门 4 共有 110 台计算
29、机，通过交换机连接路由器 R5 接入网络。其中一台计算机 IP 地址为202.115.13.5，试给出其子网掩码和网关地址。（分数：3.00）_考研计算机学科专业基础综合-5-1 答案解析(总分：149.97，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.关于线性表的顺序存储结构和链式存储结构的描述正确的是_。线性表的顺序存储结构优于其链式存储结构链式存储结构比顺序存储结构可更方便地表示各种逻辑结构如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构顺序存储结构和链式存储结构都可以进行顺序存储 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A
30、.B. C.D.解析：解析 ：线性表的两种存储结构各有优缺点，顺序存储结构支持随机存储，对于表内任意元素的存取具有较高的效率，这一点优于链式存储结构；链式存储结构不需要一次性分配所有空间给线性表，即支持动态存储，这一点优于顺序存储结构，故错误。 ：比如树和图等逻辑结构一般都是使用链式存储结构更为方便，故正确。 ：链式存储应该更适合频繁使用插入和删除操作的线性表，因为不需要移动元素，仅需要修改指针即可；而线性存储可能需要大量移动元素，故错误。 ：顺序存储结构既可以随机存储也能顺序存储；链式存储结构只能顺序存储。 综上所述，、正确。 补充：随机存储和顺序储存的差别是什么? 随机存储：意思是用户想找
31、第几个结点都可以直接使用下标找到，比如数组。 顺序存储：意思是用户想找任何一个结点都必须从第一个结点按顺序数过去。2.相对于单向链表，使用双向链表存储线性表，其优点是_。提高查找速度 节约存储空间 数据的插入和删除更快速 A.仅 B.仅、 C.仅 D.仅、（分数：2.00）A.B.C. D.解析：解析 在双向链表中的查找仍然是顺序查找，故查找速度并没有提高；双向链表中有两个指针域，所以不但不能节约存储空间，相比单链表，还增加了空间；既然增加了空间，那必须是以空间来换取时间，导致的结果就是数据的插入和删除将会更快速。3.下列关于二叉树的说法中，错误的是_。 A.在二叉树的后序序列中最后一个结点一
32、定是二叉树的根结点 B.在二叉树的中序序列中最后一个结点一定是二叉树的一个叶结点 C.在二叉树的前序序列中最后一个结点一定是二叉树的一个叶结点 D.在二叉树的层序序列中最后一个结点一定是二叉树的一个叶结点（分数：2.00）A.B. C.D.解析：解析 A：后序遍历遵循 LRT，所以最后的一个结点肯定是该二叉树的根结点，故 A 选项正确； B：中序遍历遵循 LTR，所以如果该根结点是右子女为空指针的话，就有可能最后访问的结点不是叶结点，例如： * 最后访问的是根结点，而根结点此时不是叶结点，故 B 选项错误； C：前序遍历遵循 TLR，所以最后访问的结点一定叶结点。因为如果当前的结点不是叶结点，
33、遍历算法会继续遍历它的子结点，直到该结点没有子结点，也就是说，该结点是叶结点才会停止，故 C 选项正确； D：层序遍历是按照二叉树结点的序号来访问的，所以最后一个结点一定是叶结点，故 D 选项正确。4.设一棵二叉树是由森林转换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点个数为_。 A.n-1 B.n C.n+1 D.n+2（分数：2.00）A.B.C. D.解析：解析 首先，对于一棵树来讲，每个非终端结点(除了树的根结点)转换成二叉树后都对应一个无右孩子的结点，因为一个非终端结点至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子。为什么要除去根结点?因为根结点
34、比较特殊，树转换成二叉树之后，根结点本身也将会没有右孩子。所以对于一棵具有 n 个非终端结点的树来讲，将其转换成二叉树之后，二叉树中无右孩子的结点个数为 n+1 个。其实，此时已经可以选出答案了，因为一棵树也可以算是一个森林。 如果一个森林有多棵树(假设有 x 棵)，我们先把所有树的根结点拿出来。除根结点之外的非终端结点(n-x 个)转换成二叉树之后都是对应一个无右孩子的结点，可得到 n-x 个无右孩子的结点。但是，x 个根结点是不是就对应 2x 个无右孩子的结点?显然不是，因为下一棵数将会成为上一棵树根结点的右孩子(见下图)，所以只有森林的最后一棵树的根结点才会变成无右孩子的结点，故 x 个
35、根结点将会得到 x+1 个无右孩子的根结点，所以一共可以得到 n-x+(x+1)=n+1 个无右孩子的根结点。 * 从图中可以看出，三棵树的根结点 A、E、G 转换成二叉树之后，只有最后一棵树的根结点 G 是没有右孩子的。 综上分析，二叉树中无右孩子的结点个数为n+1 个，故选 C 选项。5.若某完全二叉树的结点个数为 100，则第 60 个结点的度为_ A.0 B.1 C.2 D.不确定（分数：2.00）A. B.C.D.解析：解析 完全二又树的结点个数为偶数，说明有 1 个度为 1 的结点。设 ni 为度是 i 的结点的个数，那么就有：n0+n2+1=100，n0=n2-1，解得：n0=5
36、5，n2=54；又因为完全二叉树的编号是先度为 2 的结点，然后度为 1 的结点，最后才是叶子结点，即 154 是度为 2 的结点，55 是度为 1 的结点，56100 是度为0 的结点。因此，第 60 个结点为度为 0 的结点。6.如果二叉树中结点的先序序列是ab，中序序列是ba，则_。 A.结点 a 和结点 b 分别在某结点的左子树和右子树中 B.结点 b 在结点 a 的右子树中 C.结点 b 在结点 a 的左子树中 D.结点 a 和结点 b 分别在某结点的两棵非空子树中（分数：2.00）A.B.C. D.解析：解析 先序序列是ab，则 a 和 b 结点的 3 种情况如图 1 所示。中序序
37、列是ba，则 a和 b 结点的 3 种情况如图 2 所示。图 1 和图 2 相交的图即为答案。*图 1 a 和 b 结点的 3 种情况(一)*图 2 a 和 b 结点的 3 种情况(二)由图 1 和图 2 可知，故选 C 选项。7.已知一棵 5 阶 B 树有 53 个关键字，并且每个结点的关键字都达到最少状态，则它的深度是_。 A.3 B.4 C.5 D.6（分数：2.00）A.B.C. D.解析：解析 根据 B 树定义，m 阶 B 树除根之外所有的非终端结点至少有*个结点，即 3 个，而根结点最少有两个结点，在每个结点的关键字是最少状态时，5 层的满树结点的关键字为2+32+323+3233
38、53，而 4 层满树结点关键字为 2+32+32353，故深度为 5。总结：一棵 m 阶的 B-树是满足下列性质的 m 叉树：(1)树中的每个结点至多有 m 棵子树；(2)若根结点不是叶子结点，则至少有两棵子树；(3)除根之外的所有非终端结点至少有*棵子树；(4)所有的非终端结点中包含下列信息数据：(n，A 0，K 1，A 1，K 2，K n，A n)，其中 Ki为关键字，A i为指向子树根结点的指针，且指针 Ai-1所指子树中所有结点的关键字均小于 Ki，A n所指子树中所有关键字结点均大于 Kn，n 为关键字的个数。(5)所有的叶子结点都出现在同一层次上，并且不带信息。8.设图 G=(V，E)，其中：V=V0，V 1，V 2，V 3)E=(V0，V 1)，(V 0，V 2)，(V 0，V 3)，(V 1，V 3)则从顶点 v0 开始对图 G 的深度优先遍历序列总共有_种。 A.3 B.4 C.5 D.2（分数：2.00）A.B. C.D.解析：解析 此题的图为： * 深度优先遍历的序列有 4 个： *9.下列说法中正
