2013 年 408 真题

选择题

选择题答案速对
No.AnsNo.AnsNo.AnsNo.AnsNo.Ans
1D2C3D4B5A
6C7C8D9C10A
11C12C13A14A15C
16A17D18C19B20B
21B22D23A24A25C
26A27C28B29D30B
31B32B33B34A35D
36B37A38B39B40A

数据结构

1

已知两个长度分别为 m 和 n 的升序链表,若将它们合并为一个长度为 m+n 的降序链表,则最坏情况下的时间复杂度是()

正确答案:D
两个升序链表合并,两两比较表中元素,每比较一次确定一个元素的链接位置(取较小元素,头插法)。当一个链表比较结束后,将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较,直到两个链表都到表尾,即每个元素都经过比较,时间复杂度为 $O(m+n)=O(\text{max}(m,n))$。
2

一个栈的入栈序列为 $1,2,3, \cdots, n$,其出栈序列是 $p_1, p_2, p_3, \cdots, p_n$,若 $p_2 = 3$,则 $p_3$ 可能取值的个数是()。

正确答案:C
本题考察 入栈出栈序列。显然,$3$ 之后的 $4,5,\cdots,n$ 都是 $p_3$ 可取的数(一直进栈直到该数入栈后马上出栈)。接下来分析 1 和 2:$p_1$ 只能是 $3$ 之前入栈的数(可能是 1 或 2),当 $p_1 = 1$ 时,$p_3$ 可取 $2$;当 $p_1 = 2$ 时,$p_3$ 可取 $1$,故 $p_3$ 可能取除 $3$ 之外的所有数,个数为 $n-1$。
3

若将关键字 1,2,3,4,5,6,7 依次插入到初始为空的平衡二叉树 T 中,则 T 中平衡因子为 0 的分支结点的个数是( )。

正确答案:D

利用 7 个关键字构建平衡二叉树 T,平衡因子为 0 的分支结点个数为 3,构建的平衡二叉树如下图所示。构造及调整的过程如下:

1
1
2
1
2
3
2
3
4
1
5
2
4
5
1
6
3
4
5
6
2
7
3
1
4
5
7
2
3
1
6
RR
RR
RR
RR
4

已知三叉树 T 中 6 个叶结点的权分别是 2,3,4,5,6,7,T 的带权(外部)路径长度最小是

正确答案:B

哈夫曼树 的思想推广到三叉树的情形。为了构成严格的三叉树,需添加权为 0 的虚叶结点,对于严格的三叉树 $(n_0 - 1) % (3-1) = u = 1 \ne 0$,需要添加 $m-u-1 = 3-1-1$ 个叶结点,说明 7 个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则,权为 0 的叶结点应离树根最远构造最小带权生成树的过程如下:

0
3
2
4
6
5
7
5
5
4
6
7
14
5
2
0
3
7
6
27
14
4
5
5
2
0
3

最小的带权路径长度为 $(2 + 3) \times 3 + (4 + 5) \times 2 + (6 + 7) \times 1 = 46$。

5

若 X 是后序线索二叉树中的叶结点,且 X 存在左兄弟结点 Y 。则 X 的右线索指的是( )。

正确答案:A
根据后序 线索二叉树 的定义,X 结点为叶子结点且有左兄弟,那么这个结点为右孩子结点,利用后序遍历的方式可知 X 结点的后序后继是其父结点,即其右线索指向的是父结点。
6

在任意一棵非空二叉排序树 T1 中,删除某结点 v 之后形成二叉排序树 T2 ,再将 v 插入 T2 形成二叉排序树 T3 。下列关于 T1 与 t3 的叙述中,正确的是( )。

I. 若 v 是 T1 的叶结点,则 T1 与 T3 不同

II. 若 v 是 T1 的叶结点,则 T1 与 T3 相同

III. 若 v 不是 T1 的叶结点,则 T1 与 T3 不同

IV. 若 v 不是 T1 的叶结点,则 T1 与 T3 相同

正确答案:C
在一棵 二叉排序树 中删除一个结点后再将此结点插入到二叉排序树中,如果删除的结点是叶子结点,那么在插入结点后,后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点,那么再插入这个结点后,后来的二叉树会发生变化,不完全相同。
7

设图的邻接矩阵 A 如下所示。各顶点的度依次是()

$$ A = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} $$

正确答案:C
邻接矩阵 A 为非对称矩阵,说明图是有向图,度为入度加出度之和。各顶点的度是矩阵中此结点对应的行(对应出度)和列(对应入度)的非零元素之和。
8

若对如下无向图进行遍历,则下列选项中,不是广度优先遍历序列的是()

a
b
e
f
g
c
d
h
正确答案:D
此题为送分题。只要掌握 DFSBFS 的遍历过程,便能轻易解决。逐个代入,手工模拟,选项 D 是深度优先遍历,而不是广度优先遍历。
9

下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中,加快其进度就可以缩短工程工期的是()

2
1
3
5
4
6
a = 3
c = 9
g = 6
d = 4
e = 6
f = 10
b = 8
h = 9
正确答案:C
找出 AOE 网的全部 关键路径 为 (b,d,c,g)、(b,d,e,h) 和 (b,f,h)。根据定义,只有关键路径上的活动时间同时减少时,才能缩短工期,即正确选项中的两条路径必须涵盖在所有关键路径之中。利用关键路径算法可求出图中的关键路径共有三条:(b,d,cg)、(b,d,e,h) 和 (b,f,h)。由此可知,选项 A 和 B 中并不能包含 (b,f,h) 这条路径,选项 C 中,并不能包含 (b,d,c,g) 和 (b,d,e,h) 这两条路径,只有 C 包含了所有的关键路径,因此只有加快 f 和 d 的进度才能缩短工期。
10

在一株高度为 2 的 5 阶 B 树中,所含关键字的个数最少是()

正确答案:A
对于 5 阶 B 树,根结点只有达到 5 个关键字时才能产生分裂,成为高度为 2 的 B 树,因此高度为 2 的 5 阶 B 树所含关键字的个数最少是 5。
11

对给定的关键字序列 110,119,007,911,114,120,122 进行基数排序,则第 2 趟分配收集后得到的关键字序列是

正确答案:C

基数排序 一般使用低位优先,即第 1 趟排序是按照个位数字的大小来排序的,第 2 趟排序是按照十位数字的大小进行排序的,排序的过程如下图所示。

110
119
007
911
114
120
122
110
120
911
122
114
007
119
110
120
911
114
007
119
e[0]
e[1]
e[4]
e[3]
e[2]
e[5]
e[8]
e[7]
e[6]
e[9]
911
110
e[0]
e[1]
e[4]
e[3]
e[2]
e[5]
e[8]
e[7]
e[6]
e[9]
122
122
110
114
007
119
007
110
911
114
119
110
122
分配:
收集:
分配:
收集:

组成原理

12

某计算机主频为 1.2GHz,其指令分为 4 类,它们在基准程序中所占比例及 CPI 如下表所示。

指令类型所占比例CPI
A50%2
B20%3
C10%4
D20%5

该机的 MIPS 数是( )。

正确答案:C
基准程序的 CPI= 2x0.5 + 3x0.2 + 4x0.1 + 5x0.2 = 3。计算机的主频为 1.2 GHz, 即 1200 MHz,故该机器的 MIPS = 1200/3= 400。
13

某数采用 IEEE754 单精度浮点数格式表示为 C6400000H,则该数的值是( )。

正确答案:A

IEEE 754 单精度浮点数格式为 C640 OOOOH, 二进制格式为 1100 0110 0100 0000 0000 0000 0000 0000, 转换为标准的格式为:

| 1(符号位) | 1000 1100(阶码) | 100 0000 0000 0000 0000 0000(尾数) |

数符 = 1 表示负数;阶码值为 1000 1100 - 0111 1111 = 0000 1101 = 13; 尾数值为 1.5(注意其有隐含位,要加 1)。因此,浮点数的值为 $-1,5 \times 2^{13}$。

14

某字长为 8 位的计算机中,已知整型变量 x、y 的机器数分别为 补[x]补=11110100 , 补[y]补=10110000 。若整型变量 z=2x+y/2,则 z 的机器数为( )。

正确答案:A
x*2,将 x 算术左移一位为 1 1101000;y/2,将 y 算术右移一位为 1 1011000, 均无溢出或丢失精度。补码相加为 1 1101000 + 1 1011000 = 1 1000000, 亦无溢出。
15

用海明码对长度为 8 位的数据进行检/纠错时,若能纠正一位错,则校验位数至少为( )。

正确答案:C
设校验位的位数为 k,数据位的位数为 n,海明码 能纠正一位错应满足下述关系: $2^k \ge n+k+1$。n = 8,当 k = 4 时, $2^4 (=16) > 8 + 4 + 1 (=13)$,符合要求,故校验位至少是 4 位。
16

某计算机主存地址空间大小为 256MB,按字节编址。虚拟地址空间大小为 4GB,采用页式存储管理,页面大小为 4KB,TLB(快表)采用全相联映射,有 4 个页表项,内容如下表所示。

则对虚拟地址 03FFF180H 进行虚实地址变换的结果是( )。

正确答案:A
按字节编址,页面大小为 4KB,页内地址共 12 位。地址空间大小为 4GB,虚拟地址共 32 位,前 20 位为页号。虚拟地址为 03FF F180H,故页号为 03 FFFH,页内地址为 180H。查找页标记 03FFFH 所对应的页表项,页框号为 0153H,页框号与页内地址拼接即为物理地址 0153180H。
17

假设变址寄存器 R 的内容为 1000H,指令中的形式地址为 2000H;地址 1000H 中的内容为 2000H,地址 2000H 中的内容为 3000H,地址,3000H 的内容为 4000H,则变址寻址方式下访问到的操作数是()。

正确答案:D
根据 变址寻址 的方法,变址寄存器的内容(1000H)与形式地址的内容(2000H)相加,得到操作数的实际地址(3000H), 根据实际地址访问内存,获取操作数 4000H。
18

某 CPU 主频为 1.03GHz,采用 4 级指令流水线,每个段的执行需要 1 个时钟周期。假定 CPU 执行了 100 条指令,在其执行过程中没有发生任何流水线阻塞,此时流水线的吞吐率为( )。

正确答案:C
采用 4 级流水执行 100 条指令,在执行过程中共用 4 + (100-1) =103 个时钟周期。CPU 的主频是 1.03GHz,也就是说每秒钟有 1.03G 个时钟周期。流水线的吞吐率为 $1.03G \times 100/103 = 1.0x10^9$ 条指令/秒。
19

下列选项中,用于设备和设备控制器(I/O 接口)之间互连的接口标准是( )。

正确答案:B
本题考察 常见总线标准,USB 是一种连接外部设备的 I/0 总线标准,属于设备总线,是设备和设备控制器之间的接口。而 PCI、AGP、PCI-E 作为计算机系统的局部总线标准,通常用来连接主存、网卡、视频卡等。
20

下列选项中,用于提高 RAID 可靠性的措施有( )。

I. 磁盘镜像

Ⅱ. 条带化

Ⅲ. 奇偶校验

Ⅳ. 增加 Cache 机制

正确答案:B
本题考察 RAID,RAID0 方案是无几余和无校验的磁盘阵列,而 RAID1~5 方案均是加入了冗余(镜像)或校验的磁盘阵列。条带化技术就是一种自动地将 IO 的负载均衡到多个物理磁盘上的技术,条带化技术就是将一块连续的数据分成很多小部分并把它们分别存储到不同磁盘上去。这就能使多个进程同时访问数据的多个不同部分但不会造成磁盘冲突,而且在需要对这种数据进行顺序访问的时候可以获得最大程度上的 I/0 并行能力,从而获得非常好的性能。故能够提高 RAID 可靠性的措施主要是对磁盘进行镜像处理和奇偶校验,其余选项不符合条件。
21

某磁盘的转速为 10000rpm,平均寻道时间是 6ms,磁盘传输速率是 20MB/s,磁盘控制器延时为 0.2ms,读取一个 4KB 的扇区所需的平均时间约为( )。

正确答案:B
磁盘转速是 10000rpm,转一圈的时间为 6ms,因此平均查询扇区的时间为 3ms,平均寻道时间为 6ms,读取 4KB 扇区信息的时间为 4KB/(20MB/s)=0.2ms,磁盘控制器延迟为 0.2ms,平均存取时间 为 3+6+0.2+0.2=9.4ms。
22

下列关于中断 I/O 方式和 DMA 方式比较的叙述中,错误的是( )。

正确答案:D
中断处理方式:在 I/O 设备输入每个数据的过程中,由于无须 CPU 干预,因而可使 CPU 与 I/O 设备并行工作。仅当输完一个数据时,才需 CPU 花费极短的时间去做些中断处理。因此中断申请使用的是 CPU 处理时间,发生的时间是在一条指令执行结束之后,数据是在软件的控制下完成传送的。而 DMA 方式与之不同。DMA 方式:数据传输的基本单位是数据块,即在 CPU 与 I/O 设备之间,每次传送至少一个数据块;DMA 方式每次申请的是总线的使用权,所传送的数据是从设备直接送入内存的,或者相反;仅在传送一个或多个数据块的开始和结束时,才需 CPU 干预,整块数据的传送是在控制器的控制下完成的。

操作系统

23

用户在删除某文件的过程中,操作系统不可能执行的操作是( )。

正确答案:A
此文件所在目录下可能还存在其他文件,因此删除文件时不能(也不需要)删除文件所在的目录,而与此文件关联的目录项和文件控制块需要随着文件一同删除,同时释放文件关联的内存缓冲区。
24

为支持 CD-ROM 中视频文件的快速随机播放,播放性能最好的文件数据块组织方式是( )。

正确答案:A
为了实现快速随机播放,要保证最短的查询时间,即不能选取链表和索引结构,因此 连续分配方案 最优。
25

用户程序发出磁盘 I/O 请求后,系统的处理流程是:用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中,计算数据所在磁盘的柱面号、磁头号、扇区号的程序是( )。

正确答案:C
计算磁盘号、磁头号和扇区号的工作是由 设备驱动程序 完成的。题中的功能因设备硬件的不同而不同,因此应由厂家提供的设备驱动程序实现。
26

若某文件系统索引结点 (inode) 中有直接地址项和间接地址项,则下列选项中,与单个文件长度无关的因素是( )。

正确答案:A
四个选项中,只有 A 选项是与单个文件长度无关的。索引结点 的总数即文件的总数,与单个文件的长度无关;间接地址级数越多、地址项数越多、文件块越大,单个文件的长度就会越大。
27

设系统缓冲区和用户工作区均采用单缓冲,从外设读入 1 个数据块到系统缓冲区的时间为 100,从系统缓冲区读入 1 个数据块到用户工作区的时间为 5,对用户工作区中的 1 个数据块进行分析的时间为 90(如下图所示)。

外设
系统缓冲区
用户工作区
100
5
90

进程从外设读入并分析 2 个数据块的最短时间是( )。

正确答案:C
单缓冲 中,数据块 1 从外设到用户工作区的总时间为 105,在这段时间中,数据块 2 没有进行操作。在数据块 1 进行分析处理 时,数据块 2 从外设到用户工作区的总时间为 105,这段时间是并行的。再加上处理数据块 2 的时间 90,总时间为 300,答案为 C。
28

下列选项中,会导致用户进程从用户态切换到内核态的操作是( )。

I. 整数除以零

II. sin() 函数调用

III. read 系统调用

正确答案:B
需要在系统 内核态 执行的操作是整数除零操作(需要中断处理)和 read 系统调用函数,sin() 函数调用是在用户态下进行的。
29

计算机开机后,操作系统最终被加载到(  )。

正确答案:D
此题为基本常识题,送分题。系统开机后,操作系统的程序会被自动加载到内存中的系统区,这段区域是 RAM。
30

若用户进程访问内存时产生缺页,则下列选项中,操作系统可能执行的操作是( )。

I. 处理越界错

II. 置换页

III. 分配内存

正确答案:B
用户进程访问内存时缺页会发生缺页中断。发生 缺页中断,系统会执行的操作可能是置换页面或分配内存。系统内没有越界的错误,不会进行越界出错处理。
31

某系统正在执行三个进程 $P_1$、$P_2$ 和 $P_3$,各进程的计算 (CPU) 时间和 I/O 时间比例如下表所示。

进程计算时间I/O 时间
$P_1$90%10%
$P_2$50%50%
$P_3$15%85%

为提高系统资源利用率,合理的进程优先级设置应为( )。

正确答案:B
为了合理地设置进程优先级,应该将进程的 CPU 时间和 I/0 时间做综合考虑,对千 CPU 占用时间较少而 I/O 占用时间较多的进程,优先调度能让 I/O 更早地得到使用,提高了系统的资源利用率,显然应该具有更高的优先级。
32

下列关于银行家算法的叙述中,正确的是( )。

正确答案:B
银行家算法 是避免死锁的方法,破坏死锁产生的必要条件是预防死锁的方法。利用银行家算法,系统处于安全状态时就可以避免死锁(即此时必然无死锁);当系统进入不安全状态后便可能进入死锁状态(但也不是必然)。

计算机网络

33

在 OSI 参考摸型中,下列功能需由应用层的相邻层实现的是( )。

正确答案:B
OSI 参考模型 中,应用层的相邻层是表示层。表示层是 OSI 七层协议的第六层。表示层的功能是表示出用户看得懂的数据格式,实现与数据表示有关的功能。主要完成数据字符集的转换、数据格式化和文本压缩、数据加密和解密等工作。
34

若下图为 10 BaseT 网卡接收到的信号波形,则该网卡收到的比特串是( )。

正确答案:A
需要了解 传输介质 的命名规则:10BaseT 即 10Mbps 的以太网,采用曼彻斯特编码,将一个码元分成两个相等的间隔,前一个间隔为低电平后一个间隔为高电平表示码元 1;码元 0 正好相反,也可以采用相反的规定。故对应比特串可以是 0011 0110 或 1100 1001。
35

主机甲通过 1 个路由器(存储转发方式)与主机乙互联,两段链路的数据传输速率均为 10Mbps,主机甲分别采用报文交换和分组大小为 10kb 的分组交换向主机乙发送 1 个大小为 8 Mb(1M= 106 )的报文。若忽略链路传播延迟、分组头开销和分组拆装时间,则两种交换方式完成该报文传输所需的总时间分别为( )。

正确答案:D
本题考察分组交换的 传输时间计算,不进行分组时,发送一个报文的时延是 8Mb / 10Mbps = 800s,采用报文交换时,主机甲发送报文需要一次时延,而报文到达路由器进行存储转发又需要一次时延,总时延为 800ms × 2 = 1600ms。进行分组后,发送一个报文的时延是 10kb / 10Mbps = 1ms,一共有 8Mb / 10kb = 800 个分组,主机甲发送 800 个分组需要 1ms × 800 = 800ms 的时延,而路由器接收到第一个分组后直接开始转发,即除了第一个分组,其余分组经过路由器转发不会产生额外的时延,总时延就为 800ms+1ms=801ms。
36

下列介质访问控制方法中,可能发生冲突的是( )。

正确答案:B
选项 A、C 和 D 都是信道划分协议,信道划分协议是静态划分信道的方法,肯定不会发生冲突。CSMA 全称是载波侦听多路访问协议,其原理是站点在发送数据前先侦听信道,发现信道空闲后再发送,但在发送过程中有可能会发生冲突。
37

HDLC 协议对 01111100 01111110 组帧后对应的比特串为( )。

正确答案:A
HDLC 协议 对比特串进行组帧时,HDLC 数据帧以位模式 0111 1110 标识每一个帧的开始和结束,因此在帧数据中凡是出现了 5 个连续的位“1”的时候,就会在输出的位流中填充一个“0”。因此组帧后的比特串为 0111 1100 0011 1110 10。
38

对于 100 Mbps 的以太网交换机,当输出端口无排队,以直通交换 (cut-through switching) 方式转发一个以太网帧(不包括前导码)时,引入的转发延迟至少是( )。

正确答案:B
直通交换 在输入端口检测到一个数据帧时,检查帧首部,获取帧的目的地址,启动内部的动态查找表转换成相应的输出端口,在输入与输出交叉处接通,把数据帧直通到相应的端口,实现交换功能。直通交换方式只检查帧的目的地址,共 6B,所以最短的传输延迟是 6 × 8bit / 100Mbps = 0.48μs。
39

主机甲与主机乙之间已建立一个 TCP 连接,双方持续有数据传输,且数据无差错与丢失。若甲收到 1 个来自乙的 TCP 段,该段的序号为 1913、确认序号为 2046、有效载荷为 100 字节,则甲立即发送给乙的 TCP 段的序号和确认序号分别是( )。

正确答案:B
本题考察 序列号和确认号,确认序号 ack 是期望收到对方下一个报文段的数据的第一个字节的序号,序号 seq 是指本报文段所发送的数据的第一个字节的序号。甲收到 1 个来自乙的 TCP 段,该段的序号 seq=1913、确认序号 ack=2046、有效载荷为 100 字节,表明到序号 1913+100-1=2012 为止的所有数据甲均已收到,而乙期望收到下一个报文段的序号从 2046 开始。故甲发给乙的 TCP 段的序号 seq1=ack=2046 和确认序号 ack1=seq+100=2013。
40

下列关于 SMTP 协议的叙述中,正确的是( )。

I. 只支持传输 7 比特 ASCII 码内容

II. 支持在邮件服务器之间发送邮件

III. 支持从用户代理向邮件服务器发送邮件

IV. 支持从邮件服务器向用户代理发送邮件

正确答案:A
SMTP协议用于用户代理向邮件服务器发送邮件,或在邮件服务器之间发送邮件。SMTP 协议只支持传输 7 比特的 ASCII 码内容。

解答题

数据结构

41

已知一个整数序列 $A=(a_0,a_1,…,a_{n−1})$ ,其中 $0 \le a_i < n$ $(0 \le i \lt n)$ 。

若存在 $a_{p_1} = a_{p_2} = \cdots = a_{p_m} = x$ 且 $m > n/2$ $(0 \le p_k \lt n, 1 \le k \le m)$ ,则称 $x$ 为 $A$ 的主元素。

例如 $A = (0,5,5,3,5,7,5,5)$,则 $5$ 为主元素;又如 $A = (0,5,5,3,5,1,5,7)$ ,则 $A$ 中没有主元素。

假设 $A$ 中的 $n$ 个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出 $A$ 的主元素。若存在主元素,则输出该元素;否则输出 $−1$ 。要求:

(1) 给出算法的基本设计思想。

(2) 根据设计思想,采用 C、C++ 或 Java 语言描述算法,关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

42

设包含 4 个数据元素的集合 S = { “do”, “for”, “repeat”, “while” },各元素的查找概率依次为: $p_1=0.35$,$p_2=0.15$,$p_3=0.15$,$p_4=0.35$ 。将 S 保存在一个长度为 4 的顺序表中,采用折半查找法,查找成功时的平均查找长度为 2.2 。请回答:

(1) 若采用顺序存储结构保存 S ,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?

(2) 若采用链式存储结构保存 S ,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?

组成原理

43

某 32 位计算机,CPU 主频为 800MHz,Cache 命中时的 CPI 为 4,Cache 块大小为 32 字节;主存采用 8 体交叉存储方式,每个体的存储字长为 32 位、存储周期是 40ns;存储器总线宽度为 32 位,总线时钟频率为 200MHz,支持突发传送总线事务。每次读突发传送总线事务的过程包括:送首地址和命令、存储器准备数据、传送数据。每次突发传送 32 字节,传送地址或者 32 位数据均需要一个总线时钟周期。请回答下列问题,要求给出理由或者计算过程。

(1) CPU 和总线的时钟周期各是多少?总线的带宽(即最大数据传输率)为多少?

(2) Cache 缺失时,需要用几个读突发传送总线事务来完成一个主存块的读取?

(3) 存储器总线完成一次读突发传送总线事务所需的时间是多少?

(4) 若程序 BP 执行过程中,共执行了 100 条指令,平均每条指令需要 1.2 次访存,Cache 缺失率是 5%,不考虑替换等开销,则 BP 的 CPU 执行时间是多少?

44

某计算机采用 16 位定长指令字格式,其 CPU 中有一个标志寄存器,其中包含进位/借位标志 CF、零标志 ZF 和符号标志 NF。假定为该机设计了条件转移指令,其格式如下:

0 0 0 0 0
15
11
C
Z
N
OFFSET
10
9
8
7
0

其中,00000 为操作码 OP;C、Z 和 N 分别为 CF、ZF 和 NF 的对应检测位,某检测位为 1 时表示需检测对应标志,需检测的标志位中只要有一个为 1 就转移,否则就不转移,例如,若 C=1,Z=0,N=1,则需检测 CF 和 NF 的值,当 CF=1 或 NF=1 时发生转移;OFFSET 是相对偏移量,用补码表示。转移执行时,转移目标地址为 (PC)+2+2×OFFSET;顺序执行时,下条指令地址为 (PC)+2。请回答下列问题。

(1) 该计算机存储器按字节编址,还是按字编址?该条件转移指令向后(反向)最多可跳转最多少条指令?

(2) 某条件转移指令的地址为 200CH,指令内容如下图所示,若该执行时 CF=0,ZF=0,NF=1,则该指令执行后 PC 的值是多少?若该指令执行时 CF=1,ZF=0,NF=0,则该指令执行后 PC 的值又是多少?请给出计算过程。

0 0 0 0 0
15
11
0
1
1
1 1 1 0 0 0 1 1
10
9
8
7
0

(3) 实现“无符号数比较小于等时转移”功能的指令中,C、Z 和 N 应各是什么?

(4) 以下是该指令对应的数据通路示意图,要求给出中部件①~③的名称或功能说明。

标志寄存器
OP
OFFSET
N
Z
C
符号扩展器
多路选择器
PC
2
加法器

操作系统

45

某博物馆最多可以容纳 500 人同时参观,有一个出入口,该出入口一次仅允许一个人通过。参观者的活动描述如下:

cobegin
参观者进程 i:
{
    ...
    进门;
    ...
    参观;
    ...
    出门;
    ...
}
coend

请添加必要的信号量和 P、V(或 wait( )、signal( ))操作,以实现上述过程中的互斥与同步。要求写出完整的过程,说明信号量的含义并赋初值。

46

某计算机主存按字节编址,逻辑地址和物理地址都是 32 位,页表项大小为 4 字节。请回答下列问题。

(1) 若使用一级页表的分页存储管理方式,逻辑地址结构为:

页号(20 位)
页内偏移量(12 位)

则页的大小是多少字节?页表最大占用多少字节?

(2) 若使用二级页表的分页存储管理方式,逻辑地址结构为:

页目录号(10 位)
页表索引(10 位)
页内偏移量(12 位)

设逻辑地址为 LA,请分别给出其对应的页目录号和页表索引的表达式。

(3) 采用 (1) 中的分页存储管理方式,一个代码段起始逻辑地址为 0000 8000H,其长度为 8KB,被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放,如下图所示(地址大小自下向上递增)。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号以及代码页面 2 的起始物理地址。

页框号 2
物理地址 2
页框号 1
物理地址 1
0020 0000H
页表
代码页面 1
代码页面 2
物理地址 3
0090 0000H

计算机网络

47

假设 Internet 的两个自治系统构成的网络如题 47 图所示,自治系统 AS1 由路由器 R1 连接两个子网构成;自治系统 AS2 由路由器 R2、R3 互联并连接 3 个子网构成。各子网地址、R2 的接口名、R1 与 R3 的部分接口 IP 地址如题 47 图所示。

153.14.5.128/25
194.17.20.128/25
194.17.21.0/25
194.17.20.0/25
153.14.5.0/25
R1
R2
S0
S1
E0
R3
153.14.3.2
194.17.24.2
AS1
AS2

请回答下列问题。

(1) 假设路由表结构如下表所示。

目的网络
下一跳
接口

请利用路由聚合技术,给出 R2 的路由表,要求包括到达题 47 图中所有子网的路由,且路由表中的路由项尽可能少。

(2) 若 R2 收到一个目的 IP 地址为 194.17.20.200 的 IP 分组,R2 会通过哪个接口转发该 IP 分组?

(3) R1 与 R2 之间利用哪个路由协议交换路由信息?该路由协议的报文被封装到哪个协议的分组中进行传输?