银符考试题库-在线练习-考研计算机学科专业基础综合模拟90

考研计算机学科专业基础综合模拟90

一、单项选择题
下列每题给出的四个选项中，只有一个选项最符合试题要求。

1. 某个磁盘系统采用最短寻道时间优先(SSTF)磁盘调度算法，假设有一个请求柱面读写磁盘请求队列如下：7、136、58、100、72，当前磁头位置是80柱面。请问，磁盘总移动距离是______。

A.80
B.136
C.229
D.244

A B C D

[解析] 下表所示是磁盘移动距离。

磁盘移动距离
当前磁道位置	7	58	72	100	136	移动
80			-8	+20		-8
72		14	√	+28		14
58	-51	√	√	+42		+42
100	97	√	√	√	+36	+36
136	129	√	√	√	√	129

根据SSTF磁盘调度算法，相应请求顺序为72、58、100、136、7。因此，总的移动距离是8+14+42+36+129=229。此类问题的做法是：按照请求磁道的大小顺序排列，然后算出两个方向上最近磁道的距离，决定磁头的移动方向即可。

2. 一个用于发送二进制信号的3kHz信道，其信躁比为20dB，则可以获得的最大数据率是______。

A.6kbit/s
B.6.66kbit/s
C.19.98kbit/s
D.20kbit/s

A B C D

[解析] 20=10log₁₀100，香农极限是3log₂(1+100)=3log₂101=3×6.66=19.98kbit/s，奈奎斯特极限是6kbit/s，因此瓶颈是奈奎斯特极限，故最大数据速率是6kbit/s。

3. 多用户系统有必要保证进程的独立性，保证操作系统本身的安全，但为了向用户提供更大的灵活性，应尽可能少地限制用户进程。下面列出的各操作中，______是必须加以保护的。

A.从内核(kernel)模式转换到用户(user)模式
B.从存放操作系统内核的空间读取数据
C.从存放操作系统内核的空间读取指令
D.打开定时器

A B C D

[解析] 本题考查用户态与核心态。打开定时器属于时钟管理的内容，对时钟的操作必须加以保护，否则，一个用户进程可以在时间片还未到之前把时钟改回去，从而导致时间片永远不会用完，那么该用户进程就可以一直占用CPU，这显然不合理。从用户模式到内核模式是通过中断实现的，中断的处理过程很复杂，需要加以保护，但从内核模式到用户模式则不需要加以保护。读取操作系统内核的数据和指令是静态操作，显然无需加以保护。

4. 下列关于各种寻址方式获取操作数快慢的说法中，正确的是______。
Ⅰ．立即寻址快于堆栈寻址 Ⅱ．堆栈寻址快于寄存器寻址
Ⅲ．寄存器一次间接寻址快于变址寻址 Ⅳ．变址寻址陕于一次间接寻址

A.Ⅰ和Ⅳ
B.Ⅱ和Ⅲ
C.Ⅰ、Ⅲ和Ⅳ
D.Ⅲ和Ⅳ

A B C D

[解析] 本题考查各种寻址方式的原理。因此访问寄存器的速度通常访问主存的数十倍，因此获取操作数快慢主要取决于寻址方式的访存次数。立即寻址操作数在指令中，不需要任何访问寄存器或内存，取数最快，Ⅰ正确。堆栈寻址可能是硬堆栈(寄存器)或软堆栈(内存)，采用软堆栈时比寄存器寻址慢，Ⅱ错误。寄存器一次间接寻址先访问寄存器得到地址，然后再访问主存；而变址寻址访问寄存器IX后，还要将A和(IX)相加(相加需要消耗时间)，在根据相加的结果访存，显然后者要慢一点，Ⅲ错误。一次间接寻址需要两次访存，显然慢于变址寻址，Ⅳ正确。

5. 假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为______。

A.O(n)
B.O(e)
C.O(n+e)
D.O(ne)

A B C D

[解析] 考查邻接表的性质。和顶点v相关的边包括出边和入边，对于出边，只需要遍历v的顶点表即可；对于入边，则需要遍历整个邻接表。删除与某顶点v相关的所有边过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n-1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

6. 在DMA方式下，数据从内存传送到外设经过的路径是______。

A.内存→数据总线→外设
B.内存→数据总线→DMA→外设
C.内存→CPU→数据总线→外设
D.外设→内存

A B C D

[解析] 本题考查DMA的数据传送方式。在DMA方式下，数据传送不需要经过CPU，但需要经过DMA控制器中的数据缓冲寄存器。DMA控制器中的数据缓冲寄存器用来暂存每次传送的数据。输入时，数据由外设(如磁盘)先送往数据缓冲寄存器，再通过数据总线送到主存。反之，输出时，数据由主存通过数据总线送到数据缓冲寄存器，然后再送到外设。

7. 某端口的IP地址为172.16.7.131/26，则该IP地址所在网络的广播地址______。

A.172.16.7.191
B.172.16.7.129
C.172.16.7.255
D.172.16.7.252

A B C D

[解析] 本题考查特殊的IP地址。几类重要的特殊地址如下：

特殊地址	Net-id	Host-id	源地址或目的地址
网络地址	特定的	全0	都不是
直接广播地址	特定的	全1	目的地址
受限广播地址	全1	全1	目的地址
这个网络上的主机	全0	全0	源地址
这个网络上的特定主机	全0	特定的	源地址
环回地址	127	任意	源地址或目的地址

网络的广播地址就是将主机位全部置为1；/26表示32位IP地址中前26都是网络号，最后6位是主机号。131的二进制形式为10000011。根据广播地址的定义，主机段全1即为广播地址，即10111111，转换为十进制为191，故广播地址为172.16.7.191。

8. 流水线中有3类数据相关冲突：写后读相关、读后写相关、写后写相关。那么下列3组指令中存在读后写相关的是______。
Ⅰ：I1 SUB R1,R2,R3; (R2)-(R3)→R1
I2 ADD R4,R5,R1; (R5)+(R1)→R4
Ⅱ：I1 STA M,R2; (R2)→M,M为主存单元
I2 ADD R2,R4,R5; (R4)+(R5)→R2
Ⅲ：I1 MUL R3,R2,R1; (R2)×(R1)→R3
I2 SUB R3,R4,R5; (R4)-(R5)→R3

A.仅Ⅰ、Ⅲ
B.仅Ⅱ
C.仅Ⅱ、Ⅲ
D.Ⅰ、Ⅱ、Ⅲ

A B C D

[解析] Ⅰ：I1指令运算结果应先写入R1，然后在指令I2中读出R1的内容。由于I2指令进入流水线，使得I2指令在I1指令写入R1前就读出R1的内容，发生“写后读相关”。
Ⅱ：I1指令应先读出R2的内容并存入存储单元M中，然后I2指令将运算结果写入R2中。但由于I2指令进入流水线，使得I2指令在I1指令读出R2之前就写入R2，发生“读后写相关”。
Ⅲ：I2指令应该在I1指令写入R3之后，再写入R3。现由于I2指令进入流水线，如果I2指令减法运算在I1指令的乘法运算之前完成，使得I2指令在I1指令写入R3之前就写入R3，导致R3内容错误，发生“写后写相关”。

9. 从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是______。

A.二叉排序树
B.大顶堆
C.小顶堆
D.平衡二叉树

A B C D

[解析] 考查二叉排序树、大顶堆、小顶堆、平衡二叉树的性质。二叉排序树中的任一结点x大于其左孩子，小于其右孩子，从二叉排序树的任一结点出发到根结点，只要路径中存在左子树关系则必不满足题中降序的条件。同理，平衡二叉树也不满足。小顶堆中的任一结点x均小于左右孩子，因此从任一结点到根的路径上的结点序列必然是降序的。大顶堆刚好相反。
注意：堆存储在一个连续的数组单元中，它是一棵完全二叉树。
二叉排序树和小顶堆的共同部分。当且仅有一个左孩子时。

10. 传输一幅分辨率为640像素×480像素，6.5万色的照片(图像)，假设采用数据传输速度为56kb/s，大约需要的时间是______。

A.34.82s
B.42.86s
C.85.71s
D.87.77s

A B C D

[解析] 本题考查图像存储空间的计算。首先计算出每幅图的存储空间，然后除以数据传输率，就可以得出传输一幅图的时间。图像的颜色数为65536色，意味着颜色深度为log₂65536=16(即用16位的二进制数表示65536种颜色)，则一幅图所占据的存储空间为640×480×16=4915200b。数据传输速度为56kb/s，则传输时间=4915200b/(56×10³b/s)=87.77s。
注意：图片的大小不仅与分辨率有关，还与颜色数有关，分辨率越高、颜色数越多，图像所占的空间就越大。

11. 某计算机采用4级中断，优先级从高到低分别为1、2、3、4。若将优先级的顺序修改为3、1、2、4，则此时1、2、3、4级的中断屏蔽字分别为______。

A.1111、0111、0011、0001
B.1101、0101、1111、0001
C.1101、0101、1011、0001
D.1101、1010、1111、0001

A B C D

[解析] 修改之后的优先级是3、1、2、4，表示3号的优先级最高，它可以抢占任何级别的中断处理，故3的屏蔽字是1111；1号其次，表示除了3号不能抢占，其余的都可以抢占，故1的屏蔽字为1101；依次类推，2号中断屏蔽字为0101，4号中断屏蔽字为0001。
记忆：谁比我厉害，我的屏蔽字那一位就是0，我比谁厉害，我的屏蔽字那一位就是1。

12. 设信道带宽为4kHz，信噪比为30dB，按照香农定理，信道的最大数据速率约等于______。

A.10kb/s
B.20kb/s
C.30kb/s
D.40kb/s

A B C D

[解析] 本题考查香农定理的应用。在一条带宽为WHz、信噪比为S/N的有噪声信道的最大数据传输率Vmax为Wlog₂(1+S/N)bps。
先计算信噪比S/N：由30db=10log₁₀S/N，得log₁₀S/N=3，所以S/N=10³=1000。
计算Vmax：Vmax=Wlog₂(1+S/N)bps=4000log₂(1+1000)bps≈4000×9.97bps＜40Kbps。

13. 若定点整数64位，含1位符号位，补码表示，则所能表示的绝对值最大负数为______。

A.-2⁶⁴
B.-(2⁶⁴-1)
C.-2⁶³
D.-(2⁶³-1)

A B C D

[解析] 字长为64位，符号位为1位，则数值位为63位。当表示负数时，数值位全0对应的负数绝对值最大，为-2⁶³。

14. 一棵m阶非空B+树，每个结点最多的关键字数为______。

A.m/2
B.m-1
C.m
D.m+1

A B C D

[解析] 注意B+与B-树的区别。在B+树中，每个结点的子树个树与关键字个数相同。

15. 双端口存储器在______情况下会发生读/写冲突。

A.左端口与右端口的地址码不同
B.左端口与右端口的地址码相同
C.左端口与右端口的数据码相同
D.左端口与右端口的数据码不同

A B C D

[解析] 每个端口都有一套独立的读写系统，因此只有请求同一地址时才会发生冲突。

16. 一个信道每1/8s采样一次，传输信号共有8种变化状态，则最大的数据传输率是______。

A.16bit/s
B.24bit/s
C.32bit/s
D.48bit/s

A B C D

[解析] 由每1/8s采样一次可知，采样频率为8Hz。由采样定理可知，采样频率要大于等于有效信号最高频率的两倍，故信号频率小于等于4Hz。其次，传输信号共有8种变化状态，由奈奎斯特定理可得：最大数据传输速率=2Hlog₂v=2×4×log₂8bit/s=24bit/s，故选B选项。

17. 临界区是指并发进程访问共享变量段的______。

A.管理信息
B.信息存储
C.数据
D.代码程序

A B C D

[解析] 本题考查对临界区的理解。所谓临界区，并不是指临界资源，例如共享的数据、代码或硬件设备等，而是指访问这些临界资源的那段代码程序，例如PV操作、加减锁等。操作系统中对临界区的访问关心的就是临界区的操作过程，对临界资源作何具体操作是应用程序的事，操作系统并不关心。

18. 设有一个二维数组A[m][n]在存储中按行优先存放(数组的每一个元素占一个空间)，假设A[0][0]的存放位置在780，A[4][6]的存放位置在1146，则A[6][20]在______位置。

A.1342
B.1336
C.1338
D.1340

A B C D

[解析] 由Loc(4,6)=Loc(0,0)+(4×n+6)×1=780+(4×n+6)=1146，n=(1146-780-6)/4=90，则可计算Loc(6,20)=Loc(0,0)+(6×90+20)×1780+560=1340。

19. 以下给出的事件中，无须异常处理程序进行中断处理的是______。

A.缺页故障
B.访问Cache缺失
C.地址越界
D.除数为0

A B C D

[解析] 缺页会导致缺页中断，缺页中断是指要访问的页不在主存，现行程序无法往下走，需要操作系统采用缺页处理程序将其调入主存后再进行访问；地址越界就是在采取地址访问时，由于不注意导致访问的地址超过了所允许访问的地址空间，这种操作肯定会导致结果错误，所以是非法操作，产生异常；除数为0这是不合法的，因此要终止现行程序，产生异常；而访问Cache缺失仅仅说明要访问的内容不在Cache，但程序还可以继续进行下去(比如程序可以到主存中去找需要的内容)。所以答案为B
总结：需不需要异常或中断处理程序进行处理就看现行程序当前能不能继续往下走，若能，则不需要，反之，则需要。

20. 对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是______。

A.05，46，13，55，94，17，42
B.05，13，17，42，46，55，94
C.42，13，94，05，55，46，17
D.05，13，46，55，17，42，94

A B C D

[解析] 考查基数排序。基数排序有MSD和LSD两种，且基数排序是稳定的。答案要符合LSD或MSD，且要在排序后相等元素的相对位置不变，即符合稳定性的要求。对于A，不符合LSD和MSD。对于B，符合MSD，但是对于42、46对于关键字4它们的相对位置发生了变化。对于D，不符合LSD和MSD。所以选C。

21. 计算机系统的层次结构，下列五个级别机器由下到上的顺序是______。
Ⅰ．机器语言机器 Ⅱ．汇编语言机器
Ⅲ．高级语言机器 Ⅳ．微程序控制机器
Ⅴ．操作系统机器

A.Ⅰ→Ⅱ→Ⅲ→Ⅳ→Ⅴ
B.Ⅳ→Ⅰ→Ⅴ→Ⅱ→Ⅲ
C.Ⅲ→Ⅱ→Ⅴ→Ⅰ→Ⅳ
D.Ⅴ→Ⅳ→Ⅲ→Ⅱ→Ⅰ

A B C D

[解析] 现代计算机系统是一个硬件与软件组成的综合体，可以把它看成按功能划分的多级层次结构。计算机系统的多层次结构，如下图所示。层次结构由高到低的次序分别是：应用语言机器级、高级语言机器级、汇编语言机器级、操作系统机器级、传统机器级、微程序机器级。对每一个机器级的用户来说，都可以将此机器看成是一台独立的使用自己特有的“机器语言”的机器。

22. 用74181和74182芯片构成小组内并行进位，小组间并行进位，大组间串行进位的32位ALU，需要74182芯片的片数为______。

A B C D

[解析] 74181是内部并行进位的4位ALU芯片，74182是4位先行进位芯片，故4片74181和1片74182可构成小组内并行进位，小组间并行进位的16位ALU；且题目要求构成小组内并行进位，大组内串行进位的32位ALU，故只需将2个前述16位ALU串联即可，共需2片74182芯片，选C。

23. 在平均往返时间(RTT)为20ms的快速以太网上运行TCP/IP协议，假设TCP的最大窗口尺寸为64KB，则此时TCP协议所能支持的最大数据传输率是______。

A.3.2Mbit/s
B.12.8Mbit/s
C.25.6Mbit/s
D.51.2Mbit/s

A B C D

[解析] 因为TCP/IP的最大窗口尺寸/数据传输率≥往返时间(RTT)，即64KB×8×10³/C≥20ms×10^-3ms，所以C≤25.6Mbit/s。
补充：在运行CSMA/CD的以太网上，发送的时延必须要大于等于平均往返时延(RTT)，这样才能及时监测到是否与其他站点发生冲突，并及时停止发送保证所传输的数据的完整性和正确性。

24. 假设初始为空的散列表的地址空间为(0…10)，散列函数为H(key)=key rood 11，采用线性探测再散列法处理冲突，若依次插入关键字37、95、27、14、48，则最后一个关键字值48的插入位置是______。

A B C D

[解析] 首先通过散列函数H(key)=key rood 11的计算得知，37、95、27、14分别插入到散列表中的4、7、5、3的位置。而48 mod 11=4，但是此时4已经有元素了，根据线性探测再散列法处理冲突的原则，依次探测位置4的下一个地址，直到此地址为空，发现6为空则插入，故选C选项。
平方探测法的原理是设发生冲突的地址为d，则平方探测法的探测序列为d+1²，d-1²，d+2²，d-2²，…。位置4不空时，下一个探测的位置应该为5，发现又不空，则下一个探测的位置应该是3，发现又不空。接着再探测位置8，发现为空，将元素插入，故选D选项。
平方探测法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

25. 下列关于文件控制块的说法中，错误的个数为______。
Ⅰ．文件控制块就是文件目录项
Ⅱ．文件控制块是在执行open(打开)系统调用时建立的
Ⅲ．一个文件可以对应有多个文件控制块
Ⅳ．文件控制块通常含有3类信息：基本信息、存取控制信息及使用信息

A B C D

[解析] 文件控制块与文件一一对应(Ⅲ错误)，创建文件时建立对应的文件控制块，而不是打开文件时创建的(Ⅱ错误)。把文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项(Ⅰ正确)。在文件控制块中，通常含有3类信息，即基本信息、存取控制信息及使用信息(Ⅳ正确)。
所以Ⅰ、Ⅳ正确，Ⅱ、Ⅲ错误。错误的个数为2，所以选B

26. 已知[X/2]_补=C6H，计算机的机器字长为8位二进制数编码，则[X/4]_补为______。

A.8CH
B.18H
C.E3H
D.F1H

A B C D

[解析] 对某个数据进行乘2运算，相当于对该数据二进制数进行不带符号位左移一位的运算；对某个数据进行除2运算，相当于对该数据二进制数进行不带符号位右移一位的运算。本题中，由于[X/2]_补=C6H=(11000110)₂，所以求解[X/4]_补时，则需将(11000110)₂进行不带符号位右移一位的运算，其结果是(11100011)₂=E3H。如果此题是求[X]_补则需将(11000110)₂进行不带符号位左移一位的运算，其结果是(10001100)₂=8CH。

27. 在具有n个结点的顺序表中，算法的时间复杂度是O(1)的操作是。

A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
B.在第i个结点后插入一个新结点(1≤i≤n)
C.删除第i个结点(1≤i≤n)
D.将n个结点从大到小排序

A B C D

[解析] 顺序表是随机存取结构，选项A中实质是查找第i个结点和第i—1个结点，因此时间复杂度为O(1)；选项B和C插入和删除都需要移动元素，时间复杂度为O(n)；选项D是排序问题，时间复杂度是O(n)～O(n²)。

28. 按照IEEE754标准规定的32位浮点数(41A4C000)₁₆对应的十进制数是______。

A.4.59375
B.-20.59375
C.-4.59375
D.20.59375

A B C D

[解析] 先将给定的数据转化为二进制，然后根据IEEE754标准规定，画出结果中各个位的范围，并确定偏置值为127，因为是32位浮点数，至此可以得出以下结果：

结果大于16，因此本题选D。

29. 堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶元素。设给定序列{48，62，35，77，55，14，

，98}，若在堆排序的第一阶段将该序列建成一个堆(大根堆)，那么交换元素的次数为______。

A B C D

[解析] 考查初始堆的构造过程。首先对以第

个结点为根的子树筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，直到筛选到根结点。序列{48，62，35，77，55，14，

，98}建立初始堆的过程如下所示：

如图所示，(a)调整结点77，交换1次；(b)调整结点35，不交换；(c)调整结点62，交换2次；(d)调整结点48，交换3次。所以上述序列建初始堆，共交换元素6次。

30. 现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是______。

A.2
B.3
C.4
D.不必拆分

A B C D

[解析] 本题考查IP分片的原理和应用。这里以太网帧头为18B，IP头为20B，因此最大数据载荷是1480B，3000B的数据必须进行分片，3000=1480+1480+40共3片，因此答案是B。

31. 假定有一个请求分页存储管理系统，测得系统各相关设备的利用率如下：CPU利用率为10%，磁盘交换区为99.7%，其他I/O设备为5%。试问：下面措施中将可能改进CPU利用率的是______。
Ⅰ．增大内存的容量 Ⅱ．增大磁盘交换区的容量
Ⅲ．减少多道程序的道数 Ⅳ．增加多道程序的道数
Ⅴ．使用更快速的磁盘交换区 Ⅵ．使用更快速的CPU

A.Ⅰ、Ⅱ、Ⅲ、Ⅳ
B.Ⅰ、Ⅲ
C.Ⅱ、Ⅲ、Ⅴ
D.Ⅱ、Ⅵ

A B C D

[解析] Ⅰ正确。增大内存可使每个程序得到更多的页面，能减少缺页率，因而减少换入和换出过程，可提高CPU利用率。
Ⅱ错误。因为系统实际已处于频繁的换入和换出过程中，不是因为磁盘交换区容量不够，因此增大磁盘交换区的容量无用。
Ⅲ正确。因为从给定的条件中可看出磁盘交换区的利用率为99.7%，说明系统现在已经处于频繁的换入和换出过程中，可减少主存中的程序。
Ⅳ错误。系统处于频繁的换入和换出过程中，再增加主存中的用户进程数，只能导致系统的换入和换出更频繁，使性能更差。
Ⅴ错误。因为系统现在处于频繁的换入和换出过程中，即使采用更快的磁盘交换区，其换入和换出频率也不会改变，因此采用V的做法没用。
Ⅵ错误。系统处于频繁的换入和换出过程中，CPU处于空闲状态，利用率不高，提高CPU的速度无济于事。
综上所述，本题选B。

32. RIP和OSPF协议分别使用哪个协议进行传输______。

A.TCP和IP
B.UDP和IP
C.TCP和UDP
D.都用IP

A B C D

[解析] 概念题，选B。

33. 在IP数据报的传递过程中，IP数据报报头中保持不变的域是______。

A.标识和片偏移
B.标志和头部校验和
C.标识和目的地址
D.标志和生存周期

A B C D

[解析] 本题考查IPv4报文格式和传输特性。在数据报传递过程中，如果遇到长度超过网络MTU的时候，必须分片。因此，片偏移和标志是变化的，生存时间是随着数据报传递发生变化的。对于校验和，每经过一个结点都要进行重新计算，因此只有目的地址和标识是不变的。注意：标识是一个计算器，即使发生分片的情况下，其会把这个值复制到分片后的标识字段，因此答案为C。

34. 一个信道的比特率是4kbit/s，传播延迟是20ms，那么帧的大小______时，停-等协议才有至少50%的效率。

A.帧大于80bit
B.帧大于160bit
C.帧小于80bit
D.帧小于160bit

A B C D

[解析] 当发送1帧的时间等于信道传播延迟的2倍时，信道利用率是50%，也就是说，当发送一帧的时间等于来回路程的传播延迟时，效率是50%。由于20ms×2=40ms，现在发送速率是4000bit/s，即发送1bit需要0.25ms，40ms/(0.25ms/bit)=160bit。

35. 下列进程调度算法中，综合考虑进程等待时间和执行时间的是______。

A.时间片轮转调度算法
B.短进程优先调度算法
C.先来先服务调度算法
D.高响应比优先调度算法

A B C D

[解析] 响应比=(等待时间+执行时间)/要求服务的时间。

36. 在IP分组的传输过程中，以下IP分组首部中的字段保持不变的是______。
Ⅰ．总长度
Ⅱ．头部检验和
Ⅲ．生存时间
Ⅳ．源IP地址

A.仅Ⅰ、Ⅱ、Ⅳ
B.仅Ⅳ
C.仅Ⅰ、Ⅲ、Ⅳ
D.仅Ⅱ、Ⅳ

A B C D

[解析] Ⅰ：当IP分组的长度超过该网络的最大分组传输单元时，需要分片，此时总长度将改变，故Ⅰ错误。
   Ⅱ：IP分组每经过一个跳段都会改变其头部检验和，故Ⅱ错误。
   Ⅲ：这个比较容易判断，生存时间是不断在减少的，比如使用RIP协议，每经过一个路由器，生存时间减1，故Ⅲ错误。
   Ⅳ：其实这个问题很多考生都有疑问，如果在题目没有说明NAT的情况下，到底要不要考虑NAT?个人认为还是不要考虑，因为一些经典教材的习题以及各大名校的考研试题中都不考虑。
   注意：如果题目没有说明考虑NAT，可以认为源IP地址和目的IP地址都不可以改变，否则是可以改变的。

37. 以下叙述不正确的是______。

A.后序线索二叉树是不完善的，要对它进行遍历，不需使用栈
B.任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈
C.任何一棵二叉树都可以不用栈实现先序线索树的先序遍历
D.任何一棵二叉树都可以不用栈实现中序线索树的中序遍历

A B C D

[解析] 任何一棵二叉树，在进行前序遍历、中序遍历、后序遍历时，都不需要使用栈。

38. 在共享介质的以太网中，采用的介质访问控制方法是______。

A.并发连接
B.CSMA/CD
C.时间片
D.令牌

A B C D

[解析] CSMA/CD是共享介质的以太网中最经典，最常使用的方法。

39. 为协调计算机系统各部件工作，需______提供统一的时钟标准。

A.总线缓冲器
B.总线控制器
C.时钟发生器
D.操作命令产生器

A B C D

[解析] A项总线缓冲器是起缓冲作用的，是时钟信号的受动者。B项总线控制器，主要判决总线的使用情况，也是在时钟信号的控制下工作。D项操作命令产生器，是对指令解码后，产生具体控制信号的部件，它也是时钟信号的受动者。计算机系统的时钟信号的源头是时钟发生器。

40. 信息在外存空间的排列也会影响存取等待时间。考虑几个逻辑记录A、B、C、...、J，它们被存放于磁盘上，每个磁道存放10个记录，安排如表1所示。

表1 每个磁道存放10个记录
物理块	1	2	3	4	5	6	7	8	9	10

逻辑记录	A	B	C	D	E	F	G	H	I	J

假定要经常顺序处理这些记录，磁道旋转速度为20ms/r，处理程序读出每个记录后花4ms进行处理。考虑对信息的分布进行优化，如表2所示，相比之前的信息分布，优化后的时间缩短了______。

表2 优化后磁道存放的10个记录
物理块	1	2	3	4	5	6	7	8	9	10
逻辑记录	A	H	E	B	I	F	C	J	G	D

A.60ms
B.104ms
C.144ms
D.204ms

A B C D

[解析] 题中磁盘旋转速度为20ms/r，每个磁道存放10个记录，因此读出一个记录的时间为20/10ms=2ms。
1)对于第一种记录分布的情况，读出并处理记录A需要6ms，则此时读写磁头已转到记录D的开始处，因此为了读出记录B，必须再转一圈少两个记录(从记录D到记录B)。后续8个记录的读取及处理与此相同，但最后一个记录的读取与处理只需6ms。于是，处理10个记录的总时间为9×(2+4+16)ms+(2+4)ms=204ms。
2)对于第二种记录分布的情况，读出并处理记录A后，读写磁头刚好转到记录B的开始处，因此立即就可读出并处理，后续记录的读取与处理情况相同。共选择2.7圈。最后一个记录的读取与处理只需6ms。于是处理10个记录的总时间为20×2.7+6ms=60ms。
综上，信息分布优化后，处理的时间缩短了204ms-60ms=144ms。

二、综合应用题
本大题共70分。
试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。

1. 给出算法的基本设计思想以及结点和邻接表的定义。

基本设计思想：若存在这样的顶点，该顶点到其他任一结点都有一条有向路，又因为该有向图是无环路的，那么该顶点到这些结点之间的路构成一棵树，此树上的结点数应该等于该图的结点数。若不等于(小于)，则不存在这样的结点。因此，从任意结点开始，遍历此图(深度优先或者是广度优先均可)，若visited的结点数等于图的结点数，则存在，否则不存在。结点和邻接表定义如下：
Struct node
{
int adjvex;
node ^*next;
};//结点的定义
struct g
{
vertexttype data;
node ^*firstarc;
}typedef g ADJLIST;//邻接表的定义

2. 根据设计思想，采用C、C++语言描述算法，关键之处给出注释。

算法实现如下：
方法一：广度优先遍历(使用队列)
int rbfs(ADJLIST g,int vi)
{
int i,count,yes;
yes=0;
count=1;
queue Q;
for(int i=0;i＜n;i++)visited[i]=0;//初始化访问标记数组
enqueue(vi,Q);
visited[vi]=1;//初始化
while(!empty(Q)&&!yes)
{
int w=Q.front;
p=g[w].firstarc;
while(p!=NULL&&!yes)
{
W=P-＞adjdata;
if(visited[w]=0)
{
visited[w]=1;
count++;
enqueue(W,Q);
}
else p=p-＞next;
}
}
if(count==n)//n为该有向图中结点的总数
yes=1;
return yes;
}
方法二：深度优先遍历(使用栈)
int rdfs(ADJLIST g,int vi)
{
int i,count,yes;
yes=0;
count=1;
stack s;
for(int i=0;i＜n;i++)visited[i]=0;//初始化访问标记数组
push(vi,s);
visited[vi]=1;//初始化
while(!empty(s)&&yes==0)
{
int w=top(s);
p=g[w].firstarc;
while(p!=NULL&&visited[p-＞adjdata])
{
p=p-＞next;
if(p==NULL)pop(s);
elSe
{
w=p-＞adjdata;
visited[w]=1;
count++;
push(w,s);
}
}
}
if(count==n)//n为该有向图中的结点数
yes=1;
return yes;
{

3. 说明你所设计算法的时间复杂度。

时间复杂度分析：无论是采用深度优先遍历还是广度优先遍历，可知每个结点均访问了一次，因此时间复杂度为O(n)。

以下是计算两个向量点积的程序段：
float dotproduct(float x[8],float y[8])
{
float sum=0;
int i;
for(i=0;i＜8;i++)
sum+=x[i]*y[i];
return sum;
}

4. 假定该段程序运行的计算机的数据Cache采用直接映射方式，其容量为32B，每个主存块大小为16B假定编译程序将变量sum和j分配给寄存器，数组x存放在00000000H开始的32B的连续存储区中，数组y则紧跟在x后进行存放。试计算该程序数据访问的命中率。

命中率为0。

5. 将上述第一小题中的数据Cache改用2-路组相联映射方式，块大小改为8B，其他条件不变，则该程序数据访问的命中率是多少?

命中率为50%。

6. 在上述第一小题中条件不变的情况下，如果将数组x定义为float[12]，则数据访问的命中率又是多少?

命中率75%。

求解下面有向图的有关问题。

7. 判断此有向图是否有强连通分量?若有请画出。

此图的强连通分量有两个，分别是(v1，v3)，(v3，v4)如图1所示：

图1 强连通分量

8. 画出此图的十字链表存储结构。

十字链表表示如图2所示：

图2 十字链表表示

9. 简述基于图的深度优先搜索策略，并判别一个以邻接表存储的有向图是否存在顶点v_i到顶点v_j的路径的基本步骤。

将起始结点入栈并标记，将与此结点相邻的结点依次入栈并标记，如果相邻结点有目标结点j则输出成功，否则出栈一个结点，将与此结点相邻的结点依次入栈并标记，直到栈空，返回失败。

在某页式管理系统中，假定主存为64KB，分成16块，块号为0、1、2、…、15。设某进程有4页，其页号为0、1、2、3，被分别装入主存的第9、0、1、14块。
试问：

10. 该进程的总长度是多少?

总长度为：(64KB/16)×4=16KB

11. 写出该进程每一页在主存中的起始地址。

页面大小为4KB(2¹²B)，则页内地址有12位。
主存有16(2⁴)块，因此块号4位。
每一页在主存中的起始地址为：

0	9	9000H
1	0	0000H
2	1	1000H
3	14	E000H

12. 若给出逻辑地址[0，0]、[1，72]、[2，1023]、[3，99]，请计算出相应的内存地址(方括号内的第一个数为页号，第二个数为页内地址，题目中的数字均为10进制)。

[0，0]

9000H

[1，72]

0048H

[2，1023]

13FFH

[3，99]

E063H

某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如下所示，所有的数字均为十进制，每一项的起始编号是0，并且所有的地址均按字节编址，每页的大小为1024字节。

逻辑页号	存在位	引用位	修改位	页框号
0	1	1	0	4
1	1	1	1	3
2	0	0	0	-
3	1	0	0	1
4	0	0	0	-
5	1	0	1	5

13. 将下列逻辑地址转换为物理地址，写出计算过程，对不能计算的说明为什么?
0793，1197，2099，3320，4188，5332

根据题意，每页1024字节，地址又是按字节编址，计算逻辑地址的页号和页内偏移量，合成物理地址如下表所示。

逻辑地址	逻辑页号	页内偏移超	负框号	物理地址
0793	0	793	4	4889
1197	1	173	3	3245
2099	2	51	--	缺页中断
3320	3	248	1	1272
4188	4	92	--	缺页中断
5332	5	212	5	5332

以逻辑地址0793为例，逻辑页号为0793/1024=0，在页表中存在，页内偏移量为0793%1024=793，对应的页框号为4，故物理地址为4×1024+793=4889。

14. 假设程序欲访问第2页，页面置换算法为改进的CLOCK算法，请问该淘汰哪页?页表如伺修改?页表修改后第一小问中地址的转换结果是否改变?变成多少?

第2页不在内存，产生缺页中断，根据改进CLOCK算法，第3页为没被引用和没修改的页面，故淘汰。新页面进入，页表修改如下：

逻辑页号	存在位	引用位	修改位	页框号
1	1	1	0	4
1	1	1	1	3
2	0→1	0→1	0	—→1	稠入
3	1→0	0	0	1→—	淘汰
4	0	0	0	--
5	1	0	1	5

因为页面2调入是为了使用，所以页面2的引用位必须改为1。地址转换变为如下表：

逻辑地址	逻辑页号	页内偏移量	页框号	物理地址
0793	0	793	4	4889
1197	1	173	3	3245
2099	2	51	1	1075
3320	3	248	—	缺页中断
4188	4	92	—	缺页中断
5332	5	212	5	5332

[解析] 本题考查逻辑地址到物理地址的转换、页面置换等。地址转换过程一般是先将逻辑页号取出，然后查找页表，得到页框号，将页框号与页内偏移量相加，即可获得物理地址，若取不到页框号，那么该页不在内存，于是产生缺页中断，开始请求调页。若内存有足够的物理页面，那么可以再分配一个新的页面，若没有页面了，就必须在现有的页面之中找到一个页，将新的页与之置换，这个页可以是系统中的任意一页，也可以是本进程中的一页，若是系统中的一页，则这种置换方式称为全局置换，若是本进程的页面，则称为局部置换。置换时为尽可能地减少缺页中断次数，可以有多种算法来应用，本题使用的是改进的CLOCK算法，这种算法必须使用页表中的引用位和修改位，由这2位组成4种级别，没被引用和没修改的页面最先淘汰，没引用但修改了的页面其次，再者淘汰引用了但是没修改的页面，最后淘汰既引用又修改的页面，当页面的引用位和修改位相同时，随机淘汰一页。

假定硬盘传输数据以32位的字为单位，传输速率为1MB/s。CPU的时钟频率为50MHz。

15. 采用程序查询的输入输出方式，假定不能使数据丢失，求传输程序运行期间占用CPU的时间比率。

采用程序查询的输入输出方式，程序查询方式中，CPU一直不停地循环询问外设的状况，而为了避免数据丢失，不能切换到其他进程，所以CPU的占用率为100%。

16. 采用中断方法进行控制，每次传输的开销(包括中断处理)为100个时钟周期。求CPU为传输硬盘数据花费的时间比重。

采用中断方法进行控制，每传送一个字需要的时间为：(32b/8)÷1MB/s=4ps。
CPU时钟周期为：1/50MHz=0.02gs。
得到时间比重为：100×0.02/4=50%。

17. 采用DMA控制器进行输入输出操作，假定DMA的启动操作需要1000个时钟周期，DMA完成时处理中断需要500个时钟周期。如果平均传输的数据长度为4KB(此处，1MB=1000KB)，问在硬盘工作的一次传输中，处理器将用多少时间比重进行输入输出操作，忽略DMA申请使用总线的影响。

采用DMA控制器进行输入输出操作，平均传输的数据长度为4KB，传送的时间为：4KB÷1MB/s=4ms。上问可知CPU时钟周期为：1/50MHz=0.02gs=0.00002ms。启动与完成操作共占用的CPU时间为：0.00002ms×1500=0.03ms
总耗时为：启动时间+传输时间+完成处理中断时间=4ms+0.00002×1500=4.03ms
在DMA传输的过程中，CPU不需要进行操作，所以CPU为传输硬盘数据花费的时间比重为：CPU时间/总时间=0.03ms/4.03ms=0.74%。

[解析] 本题考查计算机的性能指标和I/O方式。首先计算每次传输过程的平均时间，然后根据程序查询、中断和DMA方式的特点计算外设I/O的时间占整个CPU时间的百分比。

考虑某路由器具有下列路由表项：

网络前缀	下一跳
142.150.64.0/24	A
142.150.71.128/28	B
142.150.71.128/30	C
142.150.0.0/16	D

18. 假设路由器接收到一个目的地址为142.150.71.132的IP分组，请确定该路由器为该IP分组选择的下一跳，并解释说明。

在使用CIDR时会有多个匹配结果，应从匹配结果选择具有最长网络前缀的路由。首先142.150.0.0/16和142.150.71.132是相匹配的，前面16位相同，下面分析其他项：
①142.150.64.0/24和142.150.71.132不匹配，因为前24位不相同。
②142.150.71.128/28和142.150.71.132的前24位是匹配的，只需看后面4位是否一样，128的二进制为1000 0000，132的二进制为1000 0100，前4位相同，故匹配了28位。
③142.150.71.128/30和142.150.71.132的前24位是匹配的，但后面的6位中第6位不一样，故不匹配。
因此，根据最长网络前缀的匹配原则，应根据第2个路由表项转发，下一跳路由为B。

19. 在上面的路由器由表中增加一条路由表项，该路由表项使以142.150.71.132为目的地址的IP分组选择“A”作为下一跳，而不影响其他目的地址的IP分组转发。

欲达到题目的要求，只需构造一个网络前缀和该地址匹配32位就行了，即针对142.150.71.132的特定主机路由，增加的表项为：网络前缀142.150.71.132/32、下一跳A。

20. 在上面的路由表中增加一条路由表项，使所有目的地址与该路由表中任何路由表项都不匹配的IP分组被转发到下一跳“E”。

增加1条默认路由：网络前缀0.0.0.0/0、下一跳E。

21. 将142.150.64.0/24划分为4个规模尽可能大的等长子网，给出子网掩码及每个子网的可分配地址范围。

要划分成4个规模尽可能大的子网，则需要从主机位中划出2位作为子网位(2²=4，CIDR广泛使用之后允许子网位可以全0和全1)。
各子网地址分别为：142.150.64.0000 0000；142.150.64.0100 0000；142.150.64.1000 0000；142.150.64.1100 0000。子网掩码应该为255.255.255.192。可分配地址范围需将主机号中全0和全1的都去掉。因此各子网的地址分配方案如下：
子网地址：142.150.64.0/26 地址范围：142.150.64.1～142.150.64.62
子网地址：142.150.64.64/26 地址范围：142.150.64.65～142.150.64.126
子网地址：142.150.64.128/26 地址范围：142.150.64.129～142.150.64.190
子网地址：142.150.64.192/26 地址范围：142.150.64.193～142.150.64.254

一、单项选择题

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

二、综合应用题

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

深色：已答题浅色：未答题