1、考研计算机学科专业基础综合-3-1 及答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.字长 16 位的补码定点小数的表示范围是( )。（分数：2.00）A.01-2 -15B.-(1-2-15)1-2 -15C.-11-2 -15D.-112.当向一棵 m 阶的 B 一树做插入操作时，若一个结点中的关键字个数等于( )，则必须分裂成两个结点，当向一棵 m 阶的 B-树做删除操作时，若一个结点中的关键字个数等于( )，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。（分数：2.00）A.m，m/2-2B.m-1，m/2-1C.m+l
2、，m/2D.m/2，m/2+13.设有 13 个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有( )个结点。（分数：2.00）A.13B.12C.26D.254.数据链路层采用了后退 N 帧(GBN)协议，发送方已经发送了编号为 07 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是( )。（分数：2.00）A.2B.3C.4D.55.一个 C 类地址，采用了 255.255.255.240 作为子网掩码，那么这个 C 类地址可以划分为( )个子网。（分数：2.00）A.16B.32C.64D.1286.测得一个以太网数据的波特率是 40Mbps，那么其数据
3、率是( )。（分数：2.00）A.10MbpsB.20MbpsC.40MbpsD.80Mbps7.同步通信比异步通信数据传输率高的原因是( )。（分数：2.00）A.同步通信不需要应答信号B.同步通信使用公共时钟进行同步C.同步通信中，通信双方的速度相近D.以上都包括8.传输线上的位流信号同步，应该属于下列 OSI 的( )层处理。（分数：2.00）A.物理层B.数据链路层C.网络层D.传输层9.补码定点小数除法中，被除数和除数应满足( )。（分数：2.00）A.0|被除数|除数|B.0|被除数|除数|C.0|除数|被除数|D.0|被除数|除数|10.IEEE754 标准浮点数的尾数采用( )
4、机器数形式。（分数：2.00）A.原码B.补码C.移码D.反码11.下列说法正确的是( )。（分数：2.00）A.取指周期一定等于机器周期B.指令字长等于机器字长的前提下，取指周期等于机器周期C.指令字长等于存储字长的前提下，取指周期等于机器周期D.取指周期与机器周期没有必然联系12.下列说法中错误的是( )。（分数：2.00）A.虚拟存储器的引入主要是为了解决主存容量的问题B.虚拟存储器通过页表来实现虚实地址的映射C.虚拟存储器是一个容量很大的逻辑模型，不是任何实际的存储器D.虚拟存储器完全由硬件实现13.已知 10 个数据元素为(54，28，16，34，73，62，95，60，23，43)
5、，按照依次插入结点的方法生成一棵二叉排序树后，查找值为 62 的结点所需比较的次数为( )。（分数：2.00）A.2B.3C.4D.514.UDP 的报文头部不包括( )。（分数：2.00）A.目的地址B.报文长度C.目的 UDP 端口D.源 UDP 端口15.下列说法中正确的是( )。（分数：2.00）A.微处理器的程序称为微程序B.微指令控制器的执行速度比硬布线控制器快C.存放微程序的控制存储器可用 ROM 或 EPROM 来实现D.在微程序控制器中，微指令使用机器指令来解释执行16.磁盘的平均存取时间是指平均寻道时间和平均等待时间之和。若磁盘的转速提高一倍则( )。（分数：2.00）A.
6、平均存取时间减半B.平均寻道时间减半C.平均等待时间减半D.以上都正确17.设高度为 H 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为( )。（分数：2.00）A.2*HB.2*H-1C.2*H+1D.H+118.在指令格式中，采用扩展操作码设计方案的目的是( )。（分数：2.00）A.缩短指令字长B.增加指令字长C.保持指令字长不变的基础上增加指令数量D.保持指令字长不变的基础上扩大指令寻址空间19.设文件 F1 的当前引用计数值为 1，先建立 F1 的符号链接(软链接)文件 F2，再建立 F1 的硬链接文件F3，然后删除 F1。此时，F2 和 F3 的引用
7、计数值分别是( )。（分数：2.00）A.0、1B.1、1C.1、2D.2、120.数据序列 F=2，1，4，9，8，10，6，20只能是下列排序算法中的( )的两趟排序后的结果。（分数：2.00）A.快速排序B.冒泡排序C.选择排序D.插入排序21.在含有 n 个关键字的大顶堆中，关键字最小的记录有可能存储在( )位置上。（分数：2.00）A.n/2B.n/2-1C.1D.n/2+222.如果 I/O 设备与存储设备间的数据交换不经过 CPU 来完成，则这种数据交换方式是( )。（分数：2.00）A.程序查询方式B.中断方式C.DMA 方式D.无条件存取方式23.把程序地址空间中使用的逻辑地
8、址变成内存中物理地址称为( )。（分数：2.00）A.加载B.物理化C.重定位D.逻辑化24.CPU 在中断周期要完成的任务不包括( )。（分数：2.00）A.保护断点B.关中断C.保护现场D.向量地址送 PC25.实时系统中的进程调度，通常采用( )算法。（分数：2.00）A.先来先服务B.时间片轮转C.抢占式的优先数高者优先D.响应比高者优先26.某虚存系统有 3 页初始为空的页框，若采用先进先出的页面淘汰算法，则在下列的页面需求提出时，会产生( )次缺页中断?设页面走向为：4 3 2 1 4 3 5 4 3 2 1 5。（分数：2.00）A.7B.8C.9D.1027.一个 FTP 的用
9、户发送了 LIST 命令来获取服务器的文件列表，这时候服务器应该通过( )端口来传输该列表。（分数：2.00）A.21B.20C.22D.1928.某机器采用四体低位交叉存储器，现分别执行下述操作：(1)读取 6 个连续地址单元中存放的存储字，重复 80 次；(2)读取 8 个连续地址单元中存放的存储字，重复 60 次。则(1)、(2)所花时间之比为( )。（分数：2.00）A.1:1B.2:1C.4:3D.3:429.设 A 是一个已有 10 个元素的栈，栈中依次是 A1，A2，A10，栈顶是 A10；B 是一个已有 10 个元素的循环队列，队列中元素依次为 B1，B2，B10，队头元素为
10、B1。A、B 均采用顺序结构，现要将栈中元素全部移入队列中，需( )次基本操作才能使得队列中元素与栈中元素交替排列，即 B 中排列后的元素为 B1，A1，B2，A2，B10，A10。(不必考虑存储空间)（分数：2.00）A.100B.1000C.50D.2030.在下列文件的物理结构中，( )不利于文件长度的动态增长。（分数：2.00）A.连续结构B.链接结构C.索引结构D.哈希结梅31.驱动调度算法中，( )算法可能会随时改变移动臂的运动方向。（分数：2.00）A.电梯调度B.最短寻找时间优先C.扫描D.单向扫描32.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈
11、S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是( )。（分数：2.00）A.1B.2C.3D.433.在顺序表中删除一个元素的时间复杂度为( )。（分数：2.00）A.O(1)B.O(log n)C.O(n)D.O(n2)34.下面关于虚拟存储器的论述中，正确的是( )。（分数：2.00）A.在段式系统中以段为单位管理用户的逻辑空间，以页为单位管理内存的物理空间；有了虚拟存储器才允许用户使用比内存更大的地址空间B.为了提高请求分页系统中内存的利用率，允许用户使用不同大小的页面C.为了能让更多的作业同时运行，通常只装入 10%30%的作业
12、即启动运行D.最佳适应算法是实现虚拟存储器的常用算法35.下面关于 Prim 算法和 Kruskal 算法的时间复杂度正确的是( )。（分数：2.00）A.Prim 算法的时间复杂度与网中的边数有关，适合于稀疏图B.Prim 算法的时间复杂度与网中的边数无关，适合于稠密图C.Kruaskal 算法的时间复杂度与网中的边数有关，适合于稠密图D.Kruskal 算法的时间复杂度与网中的边数无关，适合于稀疏图36.下列的网络协议中，( )的运输层协议是使用 TCP 的。（分数：2.00）A.TFTPB.DNSC.RIPD.TELNET37.下列地址中，不属于多播地址的是( )。（分数：2.00）A.
13、225.189.123.43B.239.14.68.89C.240.32.22.12D.224.0.0.25538.进程由就绪态转换为运行态是由( )引起的。（分数：2.00）A.中断事件B.进程状态转换C.进程调度D.为程序创建进程39.以下( )不是产生死锁的原因。 A资源共享 B并发执行的进程数太多 C系统资源不足 C进程推荐顺序非法（分数：2.00）A.B.C.D.40.冯诺依曼机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是( )。（分数：2.00）A.指令操作码的译码结果B.指令和数据的寻址方式C.指令周期的不同阶段D.指令和数据所在的存储单元二、B综合应用题/
14、B(总题数：5，分数：70.00)41.试编写一个建立带表头结点的双向循环链表的算法。（分数：10.00）_42.编写判定给定的二叉树是否是二叉排序树的函数。（分数：15.00）_43.设磁盘的扇区大小为 4KB，磁盘转速为 15000r/min，磁盘平均寻道时间为 4ms，最大数据传输速率为40MB/s，磁盘控制器开销时间为 1ms，计算读写一个扇区所需平均时间(不考虑 I/O 请求队列中的等待时间)。（分数：9.00）_44.一条双字长的取数指令(LDA)存于存储器的 200 和 201 单元，其中第一个字为操作码 OP 和寻址特征M，第二个字为形式地址 A。假设 Pc 当前值为 200，
15、变址寄存器 IX 的内容为 100，基址寄存器 BR 的内容为 200，存储器相关单元的内容如下表所示： 地址 201 300 400 401 500 501 502 700内容 300 400 700 501 600 700 900 401下表各列分别为寻址方式、该寻址方式下的有效地址及取数指令执行结束后累加器 AC 的内容，试补全下表。 寻址方式 有效地址 EA 累加器 AC 的内容立即寻址 300直接寻址间接寻址相对寻址变址寻址基址寻址先变址后间址（分数：12.00）_一个系统具有 150 个存储单元，在 T0 时刻系统按下表所示分配给 3 个进程。 进程 最大需求 已分配P1 70 2
16、5P2 60 40P3 60 45对下列请求应用银行家算法分别分析判定是否安全? （分数：24.00）(1).第 4 个进程 P4 到达，最大需求 60 个存储单元，当前请求分配 25 个单元。 （分数：3.00）_(2).第 4 个进程 P4 到达，最大需求 50 个存储单元，当前请求分配 35 个单元。 如果是安全的，请给出一个可能的进程安全执行序列；如果不是安全的，请说明理由。（分数：3.00）_(3).如果程序执行时遇到以下两个虚地址：0AC5H、1AC5H，试计算它们对应的物理地址。（分数：3.00）_(4).页表存放在主存中，对主存的一次存取需要 1.5 微秒，对 TLB 表的查找
17、时间忽略为 0，试问这两次访问共耗费多少时间?（分数：3.00）_(5).假设该局域网采用了以太网，需要达到 100Mbps 的数据传送率，那么线路的带宽最小为多少?（分数：3.00）_(6).一个 IP 包的源地址和目的地址分别是 192.168.48.19 和 192.168.48.21，为了发送该 IP 包，源主机应该先发送什么帧?（分数：3.00）_(7).该分组的以太网帧的源地址、目的地址和协议类型域各是什么?(用 16 进制表示)（分数：3.00）_(8).如果信号在网络中的传播速度是 200000km/s，那么该网络的最大长度应该为多少?（分数：3.00）_考研计算机学科专业基础
18、综合-3-1 答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.字长 16 位的补码定点小数的表示范围是( )。（分数：2.00）A.01-2 -15B.-(1-2-15)1-2 -15C.-11-2 -15 D.-11解析：表示定点小数时，补码可比原码、反码多表示一个-1，选 C。2.当向一棵 m 阶的 B 一树做插入操作时，若一个结点中的关键字个数等于( )，则必须分裂成两个结点，当向一棵 m 阶的 B-树做删除操作时，若一个结点中的关键字个数等于( )，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。（分数：2.00）A.m，
19、m/2-2 B.m-1，m/2-1C.m+l，m/2D.m/2，m/2+1解析：参见 B-树基本插入与删除操作。3.设有 13 个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有( )个结点。（分数：2.00）A.13B.12C.26D.25 解析：具有 n 个叶子结点的哈夫曼树共有 2*n-1 个结点。4.数据链路层采用了后退 N 帧(GBN)协议，发送方已经发送了编号为 07 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是( )。（分数：2.00）A.2B.3C.4 D.5解析：根据后退 N 帧协议，接收方的窗口为“1”，如果发送方收到了 3 号帧的确认
20、，则说明 0、1、2、3号帧都已经发送成功，所以只需要重发 4、5、6、7 号帧即可。5.一个 C 类地址，采用了 255.255.255.240 作为子网掩码，那么这个 C 类地址可以划分为( )个子网。（分数：2.00）A.16 B.32C.64D.128解析：先将子网掩码转换成二进制得到 1111 1111.11111 1111.1111 1111.1111000。C 类的主机号是 8 位的，现在用高 4 位来表示子网，因此可以得到 16 个子网。6.测得一个以太网数据的波特率是 40Mbps，那么其数据率是( )。（分数：2.00）A.10MbpsB.20Mbps C.40MbpsD.
21、80Mbps解析：以太网采用了曼彻斯特编码，意味着每发送一位就需要两个信号周期，那么波特率就是数据率的两倍，即波特率为 40Mbps、数据率为 20Mbps。7.同步通信比异步通信数据传输率高的原因是( )。（分数：2.00）A.同步通信不需要应答信号B.同步通信使用公共时钟进行同步C.同步通信中，通信双方的速度相近D.以上都包括 解析：A、B、C 三个选项都是同步通信数据传输率高于异步通信的原因，同步通信比异步通信数据传输率高正是这些原因综合作用的结果。8.传输线上的位流信号同步，应该属于下列 OSI 的( )层处理。（分数：2.00）A.物理层 B.数据链路层C.网络层D.传输层解析：物理
22、层涉及在通信信道上传输的原始数据位，在设计时需要保证传输线上的位流同步。9.补码定点小数除法中，被除数和除数应满足( )。（分数：2.00）A.0|被除数|除数|B.0|被除数|除数| C.0|除数|被除数|D.0|被除数|除数|解析：n 位补码定点小数的表示范围是-11-2 -(n-1)，故被除数的绝对值应小于等于除数的绝对值，否则结果会溢出；此外应避免被除数为 0，因为此时结果一定为 0，这个除法没有意义浪费了机器时间。10.IEEE754 标准浮点数的尾数采用( )机器数形式。（分数：2.00）A.原码 B.补码C.移码D.反码解析：IEEE754 标准浮点数的尾数采用原码表示，选 A。
23、11.下列说法正确的是( )。（分数：2.00）A.取指周期一定等于机器周期B.指令字长等于机器字长的前提下，取指周期等于机器周期C.指令字长等于存储字长的前提下，取指周期等于机器周期 D.取指周期与机器周期没有必然联系解析：指令字长一般取存储字长的整数倍，当指令字长等于存储字长时，取指周期可看作机器周期。12.下列说法中错误的是( )。（分数：2.00）A.虚拟存储器的引入主要是为了解决主存容量的问题B.虚拟存储器通过页表来实现虚实地址的映射C.虚拟存储器是一个容量很大的逻辑模型，不是任何实际的存储器D.虚拟存储器完全由硬件实现 解析：虚拟存储器的实现需要软硬件的共同支持，D 为错误选项。1
24、3.已知 10 个数据元素为(54，28，16，34，73，62，95，60，23，43)，按照依次插入结点的方法生成一棵二叉排序树后，查找值为 62 的结点所需比较的次数为( )。（分数：2.00）A.2B.3 C.4D.5解析：参考二叉排序树的建立。将这 10 个元素按照依次插入结点的方法生成一棵二叉排序树后，62 位于这棵二叉排序树的第三层，查找值为 62 的结点所需要的次数恰好是从二叉排序树的根到被查结点的树的深度。14.UDP 的报文头部不包括( )。（分数：2.00）A.目的地址 B.报文长度C.目的 UDP 端口D.源 UDP 端口解析：UDP 是传输层的协议，不需要包括目的地址
25、，寻址是网络层的功能。15.下列说法中正确的是( )。（分数：2.00）A.微处理器的程序称为微程序B.微指令控制器的执行速度比硬布线控制器快C.存放微程序的控制存储器可用 ROM 或 EPROM 来实现 D.在微程序控制器中，微指令使用机器指令来解释执行解析：A 选项所述显然错误；机器指令使用微指令构成的微程序来解释执行，D 错误；硬布线控制器的速度要比微程序控制器快，B 错误；微程序控制器根据其指令是否可以修改，分为静态微程序控制器和动态微程序控制器分别可用 ROM、EPROM 来实现。故 C 为正确选项。16.磁盘的平均存取时间是指平均寻道时间和平均等待时间之和。若磁盘的转速提高一倍则(
26、 )。（分数：2.00）A.平均存取时间减半B.平均寻道时间减半C.平均等待时间减半 D.以上都正确解析：磁盘平均等待时间=磁盘旋转-周所需时间/2=(1/转速)/2；故磁盘转速提高一倍，平均等待时间减半；但平均寻道时间与磁盘转速无关。故选 C。17.设高度为 H 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为( )。（分数：2.00）A.2*HB.2*H-1 C.2*H+1D.H+1解析：结点最少的情况如下图所示：除根结点层只有 1 个结点外，其余 H-1 层都有两个结点，因此结点总数为 2*(H-1)+1=2*H-1。18.在指令格式中，采用扩展操作码设计方
27、案的目的是( )。（分数：2.00）A.缩短指令字长B.增加指令字长C.保持指令字长不变的基础上增加指令数量 D.保持指令字长不变的基础上扩大指令寻址空间解析：扩展操作码技术使操作码的长度随着地址码个数的减少而增加，从而在保持指令字长不变的基础上增加指令数量。19.设文件 F1 的当前引用计数值为 1，先建立 F1 的符号链接(软链接)文件 F2，再建立 F1 的硬链接文件F3，然后删除 F1。此时，F2 和 F3 的引用计数值分别是( )。（分数：2.00）A.0、1B.1、1 C.1、2D.2、1解析：建立链按时，文件的引用数值相当于复制。20.数据序列 F=2，1，4，9，8，10，6，
28、20只能是下列排序算法中的( )的两趟排序后的结果。（分数：2.00）A.快速排序 B.冒泡排序C.选择排序D.插入排序解析：对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列不满足。21.在含有 n 个关键字的大顶堆中，关键字最小的记录有可能存储在( )位置上。（分数：2.00）A.n/2B.n/2-1C.1D.n/2+2 解析：大顶堆中关键字最小的记录只能在叶子结点上，不可能在小于或等于 n/2 的结点上。22.如果 I/O 设备与存储设备间的数据交换不经过 CPU 来完成，则这种数据交换方式是( )。（分数：2.00）A.程序查询方式B.中断方式C.
29、DMA 方式 D.无条件存取方式解析：在 DMA(直接内存存储)控制器控制下，外设直接与内存交换成批数据而不用 CPU 干预。故选 C。23.把程序地址空间中使用的逻辑地址变成内存中物理地址称为( )。（分数：2.00）A.加载B.物理化C.重定位 D.逻辑化解析：本题考查重定位的基本慨念。24.CPU 在中断周期要完成的任务不包括( )。（分数：2.00）A.保护断点B.关中断C.保护现场 D.向量地址送 PC解析：保护现场包括保护断点和保护 CPU 内其他相关寄存器的内容，其中包括断点的任务在中断周期由中断隐指令完成，保护其他寄存器内容的任务由中断服务程序完成，而不是在中断周期由中断隐指令
30、完成，选 C。25.实时系统中的进程调度，通常采用( )算法。（分数：2.00）A.先来先服务B.时间片轮转C.抢占式的优先数高者优先 D.响应比高者优先解析：实时系统为了满足用户实时交互以及对重要事件的迅速反应，所以采取抢占式的优先数高者优先。26.某虚存系统有 3 页初始为空的页框，若采用先进先出的页面淘汰算法，则在下列的页面需求提出时，会产生( )次缺页中断?设页面走向为：4 3 2 1 4 3 5 4 3 2 1 5。（分数：2.00）A.7B.8C.9 D.10解析：本题考查对在先进先出的淘汰算法缺页中断是如何发生的。27.一个 FTP 的用户发送了 LIST 命令来获取服务器的文件
31、列表，这时候服务器应该通过( )端口来传输该列表。（分数：2.00）A.21B.20 C.22D.19解析：FTP 中数据传输端口是 20，而文件的列表是通过数据连接来传输的。28.某机器采用四体低位交叉存储器，现分别执行下述操作：(1)读取 6 个连续地址单元中存放的存储字，重复 80 次；(2)读取 8 个连续地址单元中存放的存储字，重复 60 次。则(1)、(2)所花时间之比为( )。（分数：2.00）A.1:1B.2:1C.4:3 D.3:4解析：假设存储器的存取周期为 T，(1)的情况下，连续读取 6 个存储字需时 T+(6-1)(T/4)=2.25T，但存放连续字中第一个字的存储器
32、需到 3T 时间后才能进行下一轮读取，故(1)共需时 3T(80-1)+2.25T=239.75T；(2)的情况同理，一轮读取需时 T+(8-1)(T/4)=2.75T，但开始下一轮读取需 3T 时间后，故(2)共需时 3T(60-1)+2.75T-179.75T；综合上述分析，(1)、(2)所花时间之比约为 4:3。29.设 A 是一个已有 10 个元素的栈，栈中依次是 A1，A2，A10，栈顶是 A10；B 是一个已有 10 个元素的循环队列，队列中元素依次为 B1，B2，B10，队头元素为 B1。A、B 均采用顺序结构，现要将栈中元素全部移入队列中，需( )次基本操作才能使得队列中元素与
33、栈中元素交替排列，即 B 中排列后的元素为 B1，A1，B2，A2，B10，A10。(不必考虑存储空间)（分数：2.00）A.100 B.1000C.50D.20解析：操作如下： (1) 先将栈中所有元素出栈(10 次)，入队列(10 次)，栈为空，队列中的元素为B1，B2，B10，A10，A9，A1； (2) 将 B1，B2，B3，B10 出队列(10 次)，入队列(10 次)，则队列变为 A10，A2，A1，B1，B2，B10； (3) 将 A10，A9，A1 出队列(10 次)，入栈(10 次)，栈中自栈底至栈顶依次为 A10，A3，A2，A1，队列中剩下 B1，B2，B10； (4)
34、重复执行 10 次 Bi出队列(1 次)，入队列(1 次)，Ai 出栈(1 次)，入队(1 次)，则最终得至B1，A1，B2，A2，B10，A10。30.在下列文件的物理结构中，( )不利于文件长度的动态增长。（分数：2.00）A.连续结构 B.链接结构C.索引结构D.哈希结梅解析：连续结构不适合删除和插入操作，即不利于文件的动态增长。31.驱动调度算法中，( )算法可能会随时改变移动臂的运动方向。（分数：2.00）A.电梯调度B.最短寻找时间优先 C.扫描D.单向扫描解析：最短寻找时间优先可能根据新的请求做出方向改变。32.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进
35、入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是( )。（分数：2.00）A.1B.2C.3 D.4解析：33.在顺序表中删除一个元素的时间复杂度为( )。（分数：2.00）A.O(1)B.O(log n)C.O(n) D.O(n2)解析：删除顺序表中第 i 个元素，将顺序表第 i 个元素以后元素均向前移动一个位置。因此时间复杂度为O(n)。34.下面关于虚拟存储器的论述中，正确的是( )。（分数：2.00）A.在段式系统中以段为单位管理用户的逻辑空间，以页为单位管理内存的物理空间；有了虚拟存储器才允许用户使用比内存更大的地址空间
36、B.为了提高请求分页系统中内存的利用率，允许用户使用不同大小的页面 C.为了能让更多的作业同时运行，通常只装入 10%30%的作业即启动运行 D.最佳适应算法是实现虚拟存储器的常用算法 解析：35.下面关于 Prim 算法和 Kruskal 算法的时间复杂度正确的是( )。（分数：2.00）A.Prim 算法的时间复杂度与网中的边数有关，适合于稀疏图B.Prim 算法的时间复杂度与网中的边数无关，适合于稠密图 C.Kruaskal 算法的时间复杂度与网中的边数有关，适合于稠密图D.Kruskal 算法的时间复杂度与网中的边数无关，适合于稀疏图解析：Prim 算法的时间复杂度为 O(n2)，与网
37、中的边数无关，适合于稠密图；而 Kruskal 的算法复杂度为 O(elog e)，与网中的边数有关，适合于稀疏图。36.下列的网络协议中，( )的运输层协议是使用 TCP 的。（分数：2.00）A.TFTPB.DNSC.RIPD.TELNET 解析：其他三项都是使用 UDP 来传输的，只有 TELNET 是使用 TCP 的。37.下列地址中，不属于多播地址的是( )。（分数：2.00）A.225.189.123.43B.239.14.68.89C.240.32.22.12 D.224.0.0.255解析：多播地址的格式是 1110+28 位的多播地址。用 10 进制点分范围表示是 224.0
38、.0.0 到239.255.255.255。所以选项 C 不在这个范围之内。38.进程由就绪态转换为运行态是由( )引起的。（分数：2.00）A.中断事件B.进程状态转换C.进程调度 D.为程序创建进程解析：进程由就绪态转换为运行态是由进程调度引起的。39.以下( )不是产生死锁的原因。 A资源共享 B并发执行的进程数太多 C系统资源不足 C进程推荐顺序非法（分数：2.00）A.B. C.D.解析：A、C、D 都是产生死锁的原因，死锁与进程数的太多无关。40.冯诺依曼机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是( )。（分数：2.00）A.指令操作码的译码结果B.指令和
39、数据的寻址方式C.指令周期的不同阶段 D.指令和数据所在的存储单元解析：冯诺依曼机中根据指令周期的不同阶段来区分从存储器取出的是指令还是数据：取指周期取出的是指令；执行周期取出的是数据。此外，也可根据取数和取指令时的地址来源不同来区分：指令地址来源于程序计数器 PC；数据地址来源于地址形成部件。二、B综合应用题/B(总题数：5，分数：70.00)41.试编写一个建立带表头结点的双向循环链表的算法。（分数：10.00）_正确答案：()解析：用前插入法建立带头结点的双向循环链表。算法描述如下： DCLink* Created(int tag) int x; DCLink* p=NULL; /*建立
40、表头*/ DCLink* head=(DCLink*)malloc(sizeof(DLLink); head-next=head; head-prior=head; head-data=tag; /*插入数据*/ printf(“input X:/n“); scanf(“%d“,x); while(x!=tag) p=(DCLink*)malloc(sizeof(DLLink); /申请空间 p-data=x; /赋值 /*在表头部插入结点*/ p-next=head-next; head-next-prior=P; p-prior=head; head-next=P; scanf(“%d“,
41、x); return head; 42.编写判定给定的二叉树是否是二叉排序树的函数。（分数：15.00）_正确答案：()解析：判定二又树是否为二叉排序树是建立在二叉树中序遍历的基础上，在遍历中附设一指针 pre 指向树中当前访问结点的中序直接前驱，每访问一个结点就比较前驱结点 pre 与该结点是否有序。若遍历结束后各结点和其中序直接前驱结点均满足有序，则此二叉树即为二叉排序树，否则不是二叉排序树。 void BisortTree(Bitree*T,Bitree* pre,int flag) /*初始时 pre=NULL，flag=1，若结束时 flag=1。则此二叉树为排序二叉树*/ if(T
42、!=NULL) /遍历左子树 if(pre=NULL)/访问中序序列的第一个结点时，不需要比较 flag=1; pre=T; else/比较 T 与中序直接前驱 pre 的大小 if(pre-dataT-data)/pre 与 T 有序 flag=1; pre=T; else/pre与 T 无序 flag=0; BitsortTree(T-rchild,pre,flag); /遍历右子树 43.设磁盘的扇区大小为 4KB，磁盘转速为 15000r/min，磁盘平均寻道时间为 4ms，最大数据传输速率为40MB/s，磁盘控制器开销时间为 1ms，计算读写一个扇区所需平均时间(不考虑 I/O 请求
43、队列中的等待时间)。（分数：9.00）_正确答案：()解析：磁盘转速为 15000 转/分钟，即 250 转/秒，故其平均旋转等待时间为 (1/2)(1/250)=0.002s=2ms 读写一个扇区时，数据传输率为最大数据传输率，即 40MB/s，故读写一个扇区所需的数据传输时间为 4KB/(40MB/s)=0.0001s=0.1ms 根据题意，读写一个扇区的平均时间为 平均旋转等待时间+平均寻道时间+数据传输时间+磁盘控制器开销 =2ms+4ms+0.1ms+1ms=7.1ms44.一条双字长的取数指令(LDA)存于存储器的 200 和 201 单元，其中第一个字为操作码 OP 和寻址特征M
44、，第二个字为形式地址 A。假设 Pc 当前值为 200，变址寄存器 IX 的内容为 100，基址寄存器 BR 的内容为 200，存储器相关单元的内容如下表所示： 地址 201 300 400 401 500 501 502 700内容 300 400 700 501 600 700 900 401下表各列分别为寻址方式、该寻址方式下的有效地址及取数指令执行结束后累加器 AC 的内容，试补全下表。 寻址方式 有效地址 EA 累加器 AC 的内容立即寻址 300直接寻址间接寻址相对寻址变址寻址基址寻址先变址后间址（分数：12.00）_正确答案：()解析：补全后的表格如下： 寻址方式 有效地址 EA 累加器 AC 的内容立即寻址 300直接寻址 300 400间接寻址 400 700相对寻址 502 900变址寻址 400 700基址寻址 500 600先变址后间址 700 401一个系统具有 150 个存储单元，在 T0 时刻系统按下表所示分配给 3 个进程。 进程 最大需求 已分配P1 70
