【考研类试卷】考研计算机学科专业基础综合-2-2及答案解析.doc

1、考研计算机学科专业基础综合-2-2 及答案解析(总分：149.98，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是_。order(int j,int m)int i,temp;if(jm)for(i=j;i=n;i+)if(aiaj)temp=ai;ai=aj;aj=temp;j+;order(j,m); /递归调用 A.O(n) B.O(nlog2n) C.O(n2) D.O(n3)（分数：2.00）A.B.C.D.2.在顺序表的动态存储定义中需要包含的数据成员是_。数组指针*data 表中元素个数

2、 n表的大小 maxSize 数组基址 base A.、 B. 、 C.、 D.全都需要（分数：2.00）A.B.C.D.3.向一个栈顶指针为 head 的带头结点的链栈中插入指针 L 所指的结点时，应该执行_。 A.headnext=L B.Lnext=bead C.Lnext=head：headnext=L D.Lnext=headnext；headnext=L（分数：2.00）A.B.C.D.4.栈 S 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4，a5 和 a6 依次通过 S 栈，一个元素出栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3，a4，a2，a1，a5，a

3、6，则栈 S 至少应该容纳_个元素。 A.6 B.4 C.3 D.2（分数：2.00）A.B.C.D.5.某平衡二叉树的树高为 3，其根结点 A 左孩子的平衡因子为-1，右孩子的度为 0。在该平衡二叉树中插入一个结点后造成了不平衡，则应该进行_型旋转以使其平衡。 A.LL 或者 RL B.LR 或者 LL C.RL 或者 RR D.RR 或者 LL（分数：2.00）A.B.C.D.6.在由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为 30、10、20、5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为_。 A.64 B.29 C.30 D.4（分数：2

4、.00）A.B.C.D.7.一棵三叉树中，已知度为 3 的结点个数等于度为 2 的结点数，且树中叶子结点的数目为 13，则度为 2的结点数目为_。 A.4 B.2 C.3 D.5（分数：2.00）A.B.C.D.8.用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为_。 A.5 B.6 C.8 D.9（分数：2.00）A.B.C.D.9.下列关于 AOE 网的叙述中，错误的是_。 A.关键活动延期完成必定影响整个工程的完成时间 B.关键路径是 AOE 网中从起点到终点的最短路径 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.一个 AOE 网的关键路径可以有多条

5、（分数：2.00）A.B.C.D.10.为提高查找效率，对有 65025 个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行_次关键字比较。 A.10 B.14 C.20 D.21（分数：2.00）A.B.C.D.11.对于序列(32，47，12，8，2，19，30)，其堆顶元素最小的初始堆是_。 A.(2，8，12，32，47，19，30) B.(2，8，12，19，30，32，47) C.(2，12，8，32，19，47，30) D.(2，12，8，30，19，32，47)（分数：2.00）A.B.C.D.12.CPU 的 CPI 与下列哪个因素无关?_。时钟频率

6、 系统结构 指令集 A.仅、 B.仅、 C.仅、 D.、和（分数：2.00）A.B.C.D.13.设某浮点机采用规格化浮点数表示，阶码用移码表示(最高位代表符号位)，尾数用补码表示。下列规格化浮点数中哪个数最大_。 A.1111111，1.000000 B.0011111，1.011101 C.1000001，0.111101 D.0111111，0.100010（分数：2.00）A.B.C.D.14.有一主存-Cache 层次的存储器，其主存容量为 1MB(按字节编址)，Cache 容量为 16KB，每字块有 8 个字，每字为 32 位，采用直接地址映像方式。若主存地址为 35301H，且

7、CPU 访问 Cache 命中，则在 Cache的第_号字块(Cache 字块号从 0 开始)。 A.152 B.153 C.154 D.151（分数：2.00）A.B.C.D.15.下列的说法正确的是_。高位多体交叉存储器能很好地满足程序的局部性原理高位四体交叉存储器可能在一个存储周期内连续访问 4 个模块双端口存储器可以同时对同一区间、同一单元进行写操作 A.仅、 B.仅、 C.仅 D.仅（分数：2.00）A.B.C.D.16.地址总线为 A15(高位)A 0(低位)，若用 1K4 位的存储芯片组成 4KB 的存储器，地址总线的高位做片选信号，则以下说法正确的是_。加在各存储芯片上的地址线

8、是 A11A 0加在各存储芯片上的地址线是 A9A 0一共需要使用 8 片 1K4 位的存储芯片一共需要使用 4 片 1K4 位的存储芯片 A.、 B.、 C.、 D.、（分数：2.00）A.B.C.D.17.下列说法正确的是_。某加法指令，在指令的地址码中给出了存储器地址，则此指令在执行周期一定访问存储器零地址双操作数指令不需要指出操作数地址在一地址格式的指令中，只有一个操作数 A.仅、 B.仅、 C.仅、 D.、和（分数：2.00）A.B.C.D.18.指令系统中采用不同寻址方式的目的主要是_。 A.实现存储程序和程序控制 B.缩短指令长度，扩大寻址空间，提高编程灵活性 C.可以直接访问外

9、存 D.提供扩展操作码的可能性并降低指令译码难度（分数：2.00）A.B.C.D.19.下列说法正确的是_。微程序控制方式和硬布线方式相比较，前者可以使指令的执行速度更快若采用微程序控制方式，则可用 PC 取代 PC控制存储器可以用 ROM 实现指令周期也称为 CPU 周期 A.、 B.、 C.只有 D.、（分数：2.00）A.B.C.D.20.假定采用相对寻址方式的转移指令占两个字节，第一字节是操作码，第二字节是相对位移量(用补码表示)。取指令时，每次 CPU 从存储器取出一个字节，并自动完成 PC+1 的操作。假设执行到某转移指令时(即取指令前)，PC 的内容为 200CH，该指令的转移目

10、标地址为 1FBOH，则该指令第二字节的内容应为_。 A.5CH B.5EH C.A2H D.A4H（分数：2.00）A.B.C.D.21.下列关于总线仲裁方式的说法中，正确的是_。计数器定时查询方式下，有一根总线请求(BR)线和一根设备地址线，如果每次计数器从 0 开始计，则设备号大的优先级高计数器定时查询方式下，有一根总线请求(BR)线和一根设备地址线，如果每次计数器从当前设备开始计，则设备号小的优先级高分布式仲裁控制逻辑分散在总线各部件中，不需要中央仲裁器 A.仅、 B.仅 C.仅、 D.仅和（分数：2.00）A.B.C.D.22.设 CPU 与 I/O 设备以中断方式进行数据传送。当

11、CPU 响应中断时，该 I/O 设备接口控制器送给 CPU 的中断向量表(中断向量表存放中断向量)的指针是 0800H，0800H 单元中的值为 1200H，则该 I/O 设备的中断服务程序在主存中的入口地址为_。 A.0800H B.0801H C.1200H D.1201H（分数：2.00）A.B.C.D.23.在下列操作系统的各个功能组成部分中，一定需要专门硬件配合支持的是_。地址映射 进程调度中断系统 系统调用 A. B.、 C.、 D.、（分数：2.00）A.B.C.D.24.下列关于进程状态叙述正确的是_。一次 I/O 操作的结束，有可能导致一个进程由就绪变为运行一个运行的进程用完

12、了分配给它的时间片后，它的状态变为阻塞当系统中就绪进程队列非空时，也可能没有运行进程某个进程由多个内核线程组成，其中的一个线程被调度进入运行，有的继续留在就绪队列，有的被阻塞，则此时进程的状态是运行状态 A.、 B. C. D.全错（分数：2.00）A.B.C.D.25.考虑在单纯时间片轮转算法中，实现“优先级调度”，即优先级越高的进程一次分配时间片越多。有进程 A、B、C、D、E 依次几乎同时达到，其预计运行时间分别为 10、6、2、4、8，其优先级数分别是3、5、2、1、4，一个优先级数对应一个时间片。对于前一个进程时间片有剩余的情况，操作系统会调度下一个进程运行。这种情况下总响应时间和总

13、周转时间是_。(时间片为 1，忽略进程切换时间) A.30、112 B.30、122 C.47、112 D.47、122（分数：2.00）A.B.C.D.26.在某个十字路口，每个车道只允许一辆汽车通过。且只允许直行、左拐和右拐，如图所示。如果把各个方向的车看成进程，则需要对这些进程进行同步，那么这里临界资源个数应该为_。（分数：2.00）A.B.C.D.27.考虑一个由 4 个进程和一个单独资源组成的系统，当前的最大需求矩阵和分配矩阵如下：（分数：2.00）A.B.C.D.28.已知系统为 32 位实地址，采用 48 位虚拟地址，页面大小 4KB，页表项大小为 8B；每段最大为 4G。假设系

14、统使用纯页式存储，则要采用_，页内偏移为_位。 A.3 级页表，12 B.3 级页表，14 C.4 级页表，12 D.4 级页表，14（分数：2.00）A.B.C.D.29.某系统有 4 个页框，某个进程页面使用情况如下表所示。 B某个进程页面使用情况/B页号 装入时间 上次引用时间 R(读) M(修改)0 126 279 0 01 230 260 1 02 120 272 1 13 160 280 1 1请问采用 FIFO 置换算法将会替换的页的页号为_。 采用 LRU 置换算法将会替换的页的页号为_。 采用简单 CLOCK 置换算法将会替换的页的页号为_。 采用改进型 CLOCK 置换算法

15、将会替换的页的页号为_。 A.1、3、2、0 B.3、2、0、1 C.2、1、0、0 D.3、1、0、1（分数：2.00）A.B.C.D.30.下列关于目录结构的说法正确的有_。目录文件所存放的信息是所有子目录文件文件系统可以采用两级目录，这样主要是可以节省内存空间文件系统在创建一个文件时，为它创建一个文件目录有些操作系统将文件描述信息从目录项中分离出来，这样做是为了减少复制文件时的 I/O 信息量 A.、 B.、 C.、 D.全错（分数：2.00）A.B.C.D.31.某个磁盘系统采用最短寻道时间优先(SSTF)磁盘调度算法，假设有一个请求柱面读写磁盘请求队列如下：7、136、58、100、

16、72，当前磁头位置是 80 柱面。请问，磁盘总移动距离是_。 A.80 B.136 C.229 D.244（分数：2.00）A.B.C.D.32.一个典型的文本打印页面有 50 行，每行 80 个字符，假定一台标准的打印机每分钟能打印 6 页，向打印机的输出寄存器中写一个字符的时间很短，可忽略不计。如果每打印一个字符都需要花费 50gs 的中断处理时间(包括所有服务)，使用中断驱动 I/O 方式运行这台打印机，中断的系统开销占 CPU 的百分比为_。 A.2% B.5% C.20% D.50%（分数：2.00）A.B.C.D.33.关于 OSI 参考模型和 TCP/IP 模型在网络层和传输层提

17、供的服务，正确的是_。 A.OSI 模型在网络层提供无连接和面向连接服务，在传输层仅提供面向连接服务 B.TCP/IP 模型在网络层仅提供无连接服务，在传输层仅提供面向连接服务 C.OSI 模型在网络层和传输层均可提供无连接和面向连接服务 D.TCP/IP 模型在网络层提供无连接和面向连接服务，在传输层仅提供面向连接服务（分数：2.00）A.B.C.D.34.一个传输数字信号的模拟信道的信号功率是 0.62W，噪声功率是 0.02W，频率范围为 3.53.9MHz，该信道的最高数据传输速率是_。 A.1Mbit/s B.2Mbit/s C.4Mbit/s D.8Mbit/s（分数：2.00）A

18、.B.C.D.35.CSMA 协议可以利用多种监听算法来减小发送冲突的概率，下面关于各种监听算法的描述中，错误的是_。非坚持型监听算法有利于减少网络空闲时间1-坚持型监听算法有利于减少冲突的概率P-坚持型监听算法无法减少网络的空闲时间1-坚持型监听算法能够及时抢占信道 A.、 B.、 C.、 D.、（分数：2.00）A.B.C.D.36.下面的地址中，属于单播地址的是_。 A.10.3.2.255/24 B.172.31.129.255/18 C.192.168.24.59/30 D.224.100.57.211（分数：2.00）A.B.C.D.37.以下 IP 地址中，路由器不进行转发的有_

19、。10.1.32.7 192.168.32.2172.30.1.3 172.35.32.244 A.仅、 B.仅、 C.仅、 D.仅（分数：2.00）A.B.C.D.38.假如一台连接到网络上的计算机的网络配置为：IP 地址为 136.62.2.55，子网掩码为255.255.192.0，网关地址为 136.62.89.1。这台计算机在网络中不能与其他主机进行通信，可能是由_造成的。 A.子网掩码 B.网关地址 C.IP 地址 D.其他配置（分数：2.00）A.B.C.D.39.R1、R2 是一个自治系统中采用 RIP 路由协议的两个相邻路由器，R1 的路由表如表 1 所示，当 R1 收到R2

20、 发送的(V，D)报文(见表 2)后，R1 更新的 3 个路由表项中距离值从上到下依次为_。 B表 1 R1 的路由表/B目的网络 距离 路由10.0.0.0 0 直接20.0.0.0 7 R230.0.0.0 4 R2B表 2 R2 发送的报文/B目的网络 距离10.0.0.0 320.0.0.0 430.0.0.0 3 A.0、4、3 B.0、4、4 C.0、5、3 D.0、5、4（分数：2.00）A.B.C.D.40.TCP 是互联网中的传输层协议，TCP 协议进行流量控制的方式是_，当 TCP 实体发出连接请求(SYN)后，等待对方的_。 A.使用停止-等待 ARO 协议，RST B.

21、使用后退 N 帧 ARQ 协议，FIN、ACK C.使用固定大小的滑动窗口协议，SYN D.使用可变大小的滑动窗口协议，SYN、ACK（分数：2.00）A.B.C.D.二、B综合应用题/B(总题数：7，分数：70.00)设哈希函数为：H(key)=key mod 13，其中 key 为关键字，mod 为取模运算，试用关键字序列39，25，15，54，26，24，14，21，37，38构造哈希表。（分数：10.00）(1).用链地址法处理冲突，画出该哈希表的存储结构图，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。（分数：5.00）_(2).设表地址范围为 013，用线性探测再散列法

22、处理冲突，画出该哈希表的存储结构图，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。（分数：5.00）_输入一整数数组5，7，6，9，11，10，8，该整数序列为图所示的二又排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回 true，否则返回false。假设输入的数组的任意两个数字都互不相同。要求：（分数：12.99）(1).给出算法的基本设计思想。（分数：4.33）_(2).根据设计思想，采用 C、C+或 Java 语言描述算法，关键之处给出注释。（分数：4.33）_(3).说明你所设计算法的时间复杂度。（

23、分数：4.33）_某字长为 8 位的计算机中，带符号整数采用补码表示，x=-68，y=-80，x 和 y分别存放在寄存器 A 和 B 中，请回答下列问题(最终要求用十六进制表示二进制序列)。（分数：11.00）(1).寄存器 A 和 B 中的内容分别是什么?（分数：2.75）_(2).若 x 和 y 相加后的结果存放在寄存器 C 中，则寄存器 C 中的内容是什么?运算结果是否正确?此时，溢出标志 OF、符号标志 SF 和零标志 ZF 各是什么?加法器最高位的进位 Cn是什么?（分数：2.75）_(3).若 x 和 y 相减后的结果存放在寄存器 D 中，则寄存器 D 中的内容是什么?运算结果是否

24、正确?此时，溢出标志 OF、符号标志 SF 和零标志 ZF 各是什么?加法器最高位的进位 Cn是什么?（分数：2.75）_(4).若将加法器最高位的进位 Cn作为进位标志 CF，能否直接根据 CF 的值对两个带符号整数的大小进行比较?（分数：2.75）_假定一个计算机系统中有一个 TLB 和一个 L1 Data Cache。该系统按字节编址，虚拟地址 16 位，物理地址 12 位，页大小为 128B，TLB 为 4 路组相连，共有 16个页表项，L1 Data Cache 采用直接映射方式，块大小为 4B，共 16 行。在系统运行到某一时刻时，TLB、页表和 L1 Data Cache 中的部

25、分内容如图所示。（分数：12.00）(1).虚拟地址中哪几位表示虚拟页号?哪几位表示页内偏移量?虚拟页号中哪几位表示 TLB 标记?哪几位表示 TLB 索引?（分数：3.00）_(2).物理地址中哪几位表示物理页号?哪几位表示页内偏移量?（分数：3.00）_(3).主存(物理)地址如何划分成标记字段、行索引字段和块内地址字段?（分数：3.00）_(4).CPU 从地址 067AH 中取出的值为多少?说明 CPU 读取地址 067AH 中内容的过程。（分数：3.00）_在单 CPU 和两台输入/输出设备(I1，I2)的多道程序设计环境下，同时投入 3 个作业 J1、J2 和 J3 运行。这 3

26、个作业对 CPU 和输入/输出设备的使用顺序和时间如下所示。J1：I2(30ms)；CPU(10ms)；I1(30ms)；CPU(10ms)；I2(20ms)J2：I1(20ms)；CPU(20ms)：I2(40ms)J3：CPU(30ms)；I1(20ms)；CPU(10ms)：I1(10ms)假定 CPU、I1、I2 都能并行工作，J1 优先级最高，J2 次之，J3 优先级最低，优先级高的作业可以抢占优先级低的作业的 CPU，但不抢占 I1 和 I2。试求：（分数：6.99）(1).3 个作业从投入到完成分别需要的时间。（分数：2.33）_(2).从投入到完成的 CPU 利用率。（分数：2

27、.33）_(3).I/O 设备利用率。（分数：2.33）_下列程序实现了矩阵乘法。int A100150;int B150200;int C100200;for(i=0;i100;i+)for(j=0;j200;j+)for(k=0;k150;k+)Cij +=Aik*Bkj;假设矩阵 A 和矩阵 B 的初值已经初始化过，矩阵 C 初始化为 0，各矩阵均以页为单位连续存放(且假定是行优先存储)。又假定一个整数占用 1 个字，代码以及变量 i、j 和 k 存放在其他页面里，并且存取变量 i、j 和 k 时不存在缺页问题。主存初始为空，在请求分页存储管理中，页面淘汰算法为 FIFO。（分数：8.0

28、0）(1).作业分配 10 个页面，每个页面为 100 字，给矩阵 A、B 和 C 使用。问执行上面的程序时，缺页次数是多少?当执行完程序时，留在内存的 10 个页面各属于哪些矩阵?（分数：4.00）_(2).当作业分配两个页面，每个页面为 500 字，给矩阵 A、B 和 C 使用。问执行上面的程序时，缺页次数是多少?当执行完程序时，留在内存的 10 个页面各属于哪些矩阵?(注：c+=c+a*b 的执行顺序为：读 a、读b、计算 ab、读 c、计算 c+ab、写 c)（分数：4.00）_假设主机 1(在下图中网络 1 以太网上)是可以运行 IE 浏览器的某客户机，主机4(在下图中网络 3 以太

29、网上)为天勤论坛 Web 服务器(IP 地址为 202.197.11.5)，主机 5(在下图中网络 2 的 FDDI 主干网上)为天勤论坛 DNS 服务器，该 DNS 服务器上有天勤论坛 Web 站点的域名地址到 IP 地址解析。其中，路由器 1 以太网端口(a 端口)的 MAC 地址是 E3，IP 地址是 202.197.12.3，子网掩码是255.255.255.0；路由器 1 的 FDDI 端口(c 端口)的 MAC 地址是 F1，IP 地址是202.197.10.1，子网掩码是 255.255.255.0。路由器 2 的以太网端口(b 端口)的 MAC 地址是 E4，IP 地址是 20

30、2.197.11.4，子网掩码是 255.255.255.0；路由器 2 的 FDDI 端口(c 端口)的 MAC 地址是 F3，IP 地址是 202.197.10.2，子网掩码是 255.255.255.0，其他站点的 IP 地址和 MAC 地址如下图所示。试问：（分数：9.00）(1).为了使主机 1 能够通过域名访问天勤论坛 Web 服务器，主机 1 上的 IP 地址、子网掩码、默认网关 IP地址、DNS 服务器地址应该如何配置?（分数：3.00）_(2).假设主机 1 使用的 1234 的 UDP 端口与 DNS 服务器通信，使用的 1235 的 TCP 端口与 Web 服务器通信，请

31、写出主机 1 发给 DNS 服务器和 Web 服务器的 UDP 报文和 TCP 报文中的源端口号和目的端口号、IP 报文中的源 IP 地址和目的 IP 地址以及在 3 个物理网络中发送的 MAC 帧中的源 MAC 地址和目的 MAC 地址。（分数：3.00）_(3).的分析中，得出了什么结论?请阐述。（分数：3.00）_考研计算机学科专业基础综合-2-2 答案解析(总分：149.98，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是_。order(int j,int m)int i,temp;if(jm

32、)for(i=j;i=n;i+)if(aiaj)temp=ai;ai=aj;aj=temp;j+;order(j,m); /递归调用 A.O(n) B.O(nlog2n) C.O(n2) D.O(n3)（分数：2.00）A.B.C. D.解析：解析 order()函数是一个递归排序过程，设 T(n)是排序 n 个元素所需要的时间。在排序 n 个元素时，算法的计算时间主要花费在递归调用 order()上。第一次调用时，处理的元素序列个数为 n-1，也就是对余下的 n-1 个元素进行排序，所需要的计算时间应为 T(n-1)。又因为在其中的循环中，需要 n-1次比较，所以排序 n 个元素所需要的时间

33、为T(n)=T(n-1)+n-1，n1这样得到如下方程：T(1)=0T(n)=T(n-1)+n-1 n1求解过程为：T(n)=T(n-2)+(n-2)+(n-1)=T(n-3)+(n-3)+(n-2)+(n-1)=T(1)+1+2+n-1=0+1+2+n-1=n(n-1)/2=O(n2)2.在顺序表的动态存储定义中需要包含的数据成员是_。数组指针*data 表中元素个数 n表的大小 maxSize 数组基址 base A.、 B. 、 C.、 D.全都需要（分数：2.00）A.B.C. D.解析：解析 首先，表的大小和表的元素个数是肯定需要的。其次，在顺序表的动态存储定义中，它的存储空间是通过

34、执行 malloc 或 new 动态分配的，所以不包括数组基址。最后，数组的首地址需要数组指针 data 来存储。3.向一个栈顶指针为 head 的带头结点的链栈中插入指针 L 所指的结点时，应该执行_。 A.headnext=L B.Lnext=bead C.Lnext=head：headnext=L D.Lnext=headnext；headnext=L（分数：2.00）A.B.C.D. 解析：解析 此题表面上考查的是链栈的插入，其实与单链表的插入没有什么两样。既然是栈的插入，那么就是在栈顶进行操作，即考查的就是在单链表的头结点(指针 head 所指结点)后插入一个新的结点。该知识点在数据

35、结构高分笔记中已经详细地讲解过了，操作如图所示。 * 注意：和的顺序千万不可颠倒，否则将断链，导致操作失败。4.栈 S 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4，a5 和 a6 依次通过 S 栈，一个元素出栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3，a4，a2，a1，a5，a6，则栈 S 至少应该容纳_个元素。 A.6 B.4 C.3 D.2（分数：2.00）A.B.C. D.解析：解析 模拟一下入栈出栈过程，如下表。选取模拟过程中栈内元素个数最大的值，便为该题答案，因此本题选 C。 操作 栈 输出pusha1pusha1、a2pusha1、a2pop a1、a2

36、 a3pusha1、a2、a4 a3pop a1、a2 a3、a4pop a1 a3、a4、a2pop a3、a4、a2、a1pusha5 a3、a4、a2、a1pop a3、a4、a2、a1、a5pusha6 a3、a4、a2、a1、a5pop a3、a4、a2、a1、a5、a65.某平衡二叉树的树高为 3，其根结点 A 左孩子的平衡因子为-1，右孩子的度为 0。在该平衡二叉树中插入一个结点后造成了不平衡，则应该进行_型旋转以使其平衡。 A.LL 或者 RL B.LR 或者 LL C.RL 或者 RR D.RR 或者 LL（分数：2.00）A.B.C. D.解析：解析 由题意可知，树的结构如

37、图 1 所示。*图 1 某平衡二叉树由图 1 可知，插入一个结点造成根结点 A 的左孩子结点不平衡，说明这个结点一定是插在根结点 A 的左孩子的右孩子上，如图 2 所示。所以需要进行 RL 型或者 RR 型旋转。*图 2 插入一个结点后的二叉树6.在由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为 30、10、20、5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为_。 A.64 B.29 C.30 D.4（分数：2.00）A.B. C.D.解析：解析 当森林转换成二叉树后，根结点的左子树其实就是原来第一棵树除了根结点的所有结点，所以二叉树中根结点的左子

38、树中结点个数为 29，故选 B。7.一棵三叉树中，已知度为 3 的结点个数等于度为 2 的结点数，且树中叶子结点的数目为 13，则度为 2的结点数目为_。 A.4 B.2 C.3 D.5（分数：2.00）A.B. C.D.解析：解析 叶子结点的数目和结点的度数有一定的关系，一个度为 3 的结点可以使叶子结点数增加2，一个度为 2 的结点可以使叶子结点数增加 1，设度为 2 的结点的个数为 x，则叶子结点的个数相当于在根结点的基础上增加了 2x+x=3x，故 3x+l=13，解得 x=4。8.用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为_。 A.5 B.6 C.8 D

39、.9（分数：2.00）A. B.C.D.解析：解析 用下图可以表示表达式，图中顶点表示参与运算的一种操作数和运算符(注意是一种而不是一个)，用边来确定各种运算以及运算优先顺序。(A+B)*(A+B)/A)表达式中的运算符有 3 种，即“+”、“*”、“/”，操作数有 2 种，即“A”、“B”，因此图中顶点数至少为 5。图中 A 与 B 结合运算符“+”做运算，将所得结果与“A”结合运算符“/”做运算，上两步的结果再结合运算符“*”做运算得到最终结果。本题比较灵活，属于在掌握基础后的能力扩展。 *9.下列关于 AOE 网的叙述中，错误的是_。 A.关键活动延期完成必定影响整个工程的完成时间 B.

40、关键路径是 AOE 网中从起点到终点的最短路径 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.一个 AOE 网的关键路径可以有多条（分数：2.00）A.B. C.D.解析：解析 关键活动组成了关键路径。关键路径是从起点到终点的最长路径，关键路径长度代表整个工期的最短完成时间。关键活动延期完成，必将导致关键路径长度增加，即整个工期的最短完成时间增加，所以 A 正确。关键路径实际上是从源点到终点的最长路径，而非最短路径。这点很容易理解，因为整个工程的工期就是按照最长路径长度计算出来的，即等于该路径上所有活动的持续时间之和，所以 B 错误。只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的，所以 C 正确。关键路径并不唯一，可以有多条，所以 D 正确。 注意：关键路径算法是以拓扑排序为基础的；10.为提高查找效率