408-2018

一、单项选择题（2 分/题）

1.若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作：

（1）从 S1 中依次弹出两个操作数 a 和 b

（2）从 S2 中弹出一个运算符 op

（3）执行相应的运算 b op a

（4）讲计算结果压入 S1 中

假定 S1 中的操作数依次是 5，8，3，2（2 在栈顶），S2 中的运算符依次是 *，-，+（+ 在栈顶）。调用 3 次 F() 后，S1 栈顶保存的值是_____.

A.-15 B.15 C.-20 D.20

解答：B

对应计算式为 5*(8-(3+2))=5*3=15.

2.现有队列 Q 和栈 S，初始时 Q 中的元素依次是1，2，3，4，5，6（1 在队头），S 为空。若仅允许以下三种操作：（1）出队并输出出队元素（2）出队并将出队元素入栈（3）出栈并输出出栈元素，则不能得到的输出序列为______

A.1,2,5,6,4,3 B.2,3,4,5,6,1 C.3,4,5,6,1,2 D.6,5,4,3,2,1

解答：C

A,1 出队，2出队，3出队入栈，4出队入栈，5 出队，6出队，4出栈，3出栈

B.1出队入栈，2,3,4,5,6 依次出队，1 出栈

C.1 出队入栈，2出队入栈，3，4，5，6 出队，此时栈顶为 2，非 1 ，不能得到该序列

D.1,2,3,4,5,6 出队入栈， 6，5，4，3，2，1 出栈

3.设有一个 12*12 的对称矩阵 M，其上三角部分的元素 m(i,j)（1<=i<=j<=12）按行优先存入 C 语言的一维数组 N 中，元素 m(6*6) 在 n 中的下标为_____.

A.50 B.51 C.55 D.66

解答：A

第 i 行需存储 12-i 个元素

12+11+10+9+8+1-1=20+20+10=50

4.设一颗非空完全二叉树 T 的所有叶节点均位于同一层，且每个非叶节点都有两个子节点。设 t 有 k 个叶节点，则 T 的节点总数为_____.

A.2k-1 B.2k C.k^k D.2^k-1

解答：A

若 k为 1，则总共有 1 个节点，排除B

若 k 为 2，则共有 3 个节点，排除C

若 k 为 4，则共有 1+2+4=7 个节点，排除 D

故选 A

5.已知字符集{a,b,c,d,e,f}，若各字符出现的分别为 6，3，8，2，10，4，则对应字符集中各字符的曼哈顿编码为______.

A.00,1011,01,1010,11,100 B.00,100,110,000,0010,01

C.10,1011,11,0011,00,010 D.0011,10,11,0010,01,000

解答：A

首先选择 b 和 d，因此 b和 d 长度一致，前缀一致，排除 B，C，D。选A

6.已知二叉树排序树如下所示，元素之间应满足的大小关系是_____.

A.x1<x2<x5 B.x1<x4<x5 C.x3<x5<x4 D.x4<x3<x5

解答：C

二叉排序树任意节点右子树上任一节点值大于该节点值，任意节点左子树上任一节点的值小于该节点的值。

A.x5<x2 B.x5<x4 C正确

7.下列选项中，不是如下有向图的拓扑排序的是_______.

A.1,5,2,3,6,4 B.5,1,2,6,3,4 C.5,1,2,3,6,4 D.5,2,1,6,3,4

解答：D

D 项 1 应当在 2 前面

8.高度为 5 的 3 阶 B 树含有的关键字数量至少是_____.

A.15 B.31 C.62 D.242

解答：B

3 阶 B 树除根节点外每个节点至少有 3/2=1 个关键字，皆取最小值时为二叉树。又因为 B 树所有叶节点均在同一层，因此该二叉树为满二叉树，此时有 2^5-1=31 个关键字。

9.现有长度为 7 、初始为空的散列表 HT，散列函数为 H(k)=k%7，用线性再探测散列法解决哈希冲突，将关键字 22，43，15 依次插入 HT 中后，查找成功的平均查找长度为_____.

A.1.5 B.1.6 C.2 D.

解答：C

22%7=1，43%7=1，15%7=1，因此查找长度分别为 1，2，3，平均查找长度为 (1+2+3)/3=2。

10.对初始数据序列(8,3,9,11,2,1,4,7,5,10,6)进行希尔排序。若第一趟排序结果为(1,3,7,5,2,6,4,9,11,10,8)，第二趟排序结果为(1,2,6,4,3,7,5,8,11,10,9)。则两趟排序采用的增量(间隔)依次为_____.

A.3,1 B.3,2 C.5,2 D.5,3

解答：D

第一趟，间隔为 3 时1，5，4 并不有序，故间隔为 5

第二趟，间隔位 2 时 1，6，3，并不有序，故间隔位 3

希尔排序增量缩小时并不递减 1 .

11.在将数据序列 (6,1,5,9,8,4,7) 建成大根堆时，正确的序列变化过程是______.

A.6,1,7, 9, 8, 4, 5 -> 6, 9, 7, 1, 8, 4, 5 ->9, 6, 7, 1, 8, 4, 5 -> 9, 8, 7, 1, 6, 4, 5

B.6, 9, 5, 1, 8, 4, 7 -> 6, 9, 7, 1, 8, 4, 5 -> 9, 6, 7, 1, 8, 4, 5 -> 9, 8, 7, 1, 6, 4, 5

C.6, 9, 5, 1, 8, 4, 7 -> 9, 6, 5, 1, 8, 4, 7 -> 9, 6, 7, 1, 8, 4, 5 -> 9, 8, 7, 1, 6, 4, 5

D.6, 1, 7, 9, 8, 4, 5 -> 7, 1, 6, 9, 8, 4, 5 -> 7, 9, 6, 1, 8, 4, 5 -> 9, 7, 6, 1, 8, 4, 5 -> 9, 8, 6, 1, 7, 4, 5

解答：A

建立好二叉堆后，从下往上，从右往左遍历。

6,1,5,9,8,4,7 7 与 5 交换

6,1,7,9,8,4,5 9 和 1 交换 ;6,9,7,1,8,4,5 9 和 6 交换

9,6,7,1,8,4,5 6 和 8 交换

9,8,7,1,6,4,5

12.冯诺伊曼结构计算机中数据采用二进制编码表示，其主要原因是______

I.二进制运算规则简单

II.制造两个稳态的物理器件较容易实现

III.便于用逻辑门电路实现算术运算

A.I,II B.I,III C.II,III D.I,II,III

解答：D

13.假定带符号整数采用补码表示，若 int 型变量 x 和 y 的机器数分别是 FFFF FFDFH 和 0000 0041H，则 x，y 的值以及 x-y 的机器数分别是______.

A.x=-65, y=41,x-y 的机器数溢出

B.x=-33,y=65,x-y 的机器数为 FFFF FF9DH

C.x=-33,y=65,x-y 的机器数为 FFFF FF9EH

D.x=-65,y=41,x-y 的机器数为 FFFF FF96H

解答：C

y 的值为 4*16+1=65，故 x 的值为 -33，x-y 的值为 -33-65=-98

98 的二进制表示为 0110 0010B，其补码为 1001 1110B 即 FFFF FF9EH。

综上，选 C

14.IEEE 754 单精度浮点格式表示的数中，最小的规格化正数是_____.

A.1.0*2^(-126) B.1.0*2^(-127) C.1.0*2^(-128) D.1.0*2^(-149)

解答：A

IEEE 754 单精度浮点格式中阶码部分占 8 位，能表示的范围是 1~254，偏置常数位 127，因此实际表示范围是 -126（1-127）~127（254-127），选A

阶码全 0，尾数全0，为 0

阶码全 0，尾数不全 0，非规格化数（取消隐含 1 规则）

阶码全 1 ，尾数全 0，表示无穷或负无穷

阶码全 1，尾数不全 0，无效数

15.某 32 位计算机按字节编址，采用小端（Litte Endian）方式。若语句 “int i=0；”对应指令的机器代码是 “C7 45 FC 00 00 00 00”，则语句 "int i=-64;" 对应的机器代码是_____.

A.C7 45 FC C0 FF FF FF B.C7 45 FC 0C FF FF FF

C.C7 45 FC FF FF FF C0 D.C7 45 FC FF FF FF 0C

解答：A

64 对应二进制为 0100 0000，因此 -64 对应二进制为 1100 0000，即 C0H，即FF FF FF C0，采用小端方式，因此低位数据存放在低位地址。

16.整数 x 的机器数 1101 1000，分别对 x 进行逻辑右移 1 位和算术右移 1 位，得到的机器数分别是_______。

A.1110 1100 ， 1110 1100 B.0110 1100，1110 1100

C.1110 1100， 0110 1100 D.0110 1100，0110 1100

解答：B

算术右移左边补符号位，逻辑右移左边补 0.

17.假设 DRAM 芯片中存储阵列的行数为 r，列数为 c，对于一个 2K*1 位的 DRAM 芯片，为保证其地址引脚数最少，并尽量减小刷新开销，则 r，c 的取值分别是_____.

A.2048、1 B.64、32 C.32、64 D.1、2048

解答：C

DRAM（Dynamic Random Access Memery），动态随机存取存储器。

DRAM 采用行列地址线复用技术（寻址时，先发送行地址，再发送列地址），因此要求行地址和列地址尽可能接近（地址线数量为二者之和），因此答案再BC中。

DRAM 按行刷新，因此行数 r 较少，刷新开销较小，选 C

18.按字节编址的计算机中，某 double 型数组 A 的首地址为 2000H，使用变址寻址和循环结构访问数组 A，保存数组下标的编址寄存器初值为 0，每一循环取一个数组元素，其偏移地址为变址值乘以 sizeof(double) ，取完后变址寄存器内容自动加一。若某次循环所取元素的地址为 2100H，则进入该次循环的变址寄存器内容是______.

A.25 B.32 C.64 D.100

解答：B

double 占 64 位，即 8B，按字节变址，因此每次后移 8 个地址，即 2000H+8H*x=2100H，x=32，选 B

19.减法指令“sub R1，R2，R3”的功能位 “(R1)-(R2)->R3”，该指令执行后将生成进位/借位标志 CF 和溢出标志 OF。若 (R1)=FFFF FFFFH, (R2)=FFFF FFF0H,则该减法指令执行后，CF 与 OF 的值分别是______.

A.CF=0,OF=0 B.CF=1,OF=0 C.CF=0,OF=1 D.CF=1,OF=1

解答：A

[R1]补-[R2]补=[R1]补+[-R2]补= FFFF FFFFH+0000 0010H= 1 0000 000FH，产生进位与溢出。

R1>R2，所以借位标志为0。

最高位产生的进位为 1，次高为产生的进位也为 1，因此溢出标志为 0（当最高位进位与次高位进位的值不相同时才产生溢出）.

20.若某计算机最复杂的指令需要完成 5 个子功能，分别由功能部件 A~E 实现，各功能部件所需时间分别位 80ps,50ps,50ps,70ps 和 50ps，采用流水线方式执行指令，流水段寄存器延时位 20ps，则 CPU 时钟周期至少为______.。

A.60ps B.70ps C.80ps D.100ps

解答：D

指令流水线每个流水段的时间单位为时钟周期，取其中最大的80ps，因为流水段起存其延时为 20ps，因此时钟周期至少为 100ps

21.下列选项中，可提高同步总线数据传输率的是_____.

I.增加总线宽度 II.提高总线工作频率

III.支持突发传输 IV.采用地址/数据线复用

A.I,II B.I,II,III C.III,IV D.I,II,III,IV

解答：B

同步总线：所有的互联的部件或设备使用同一个时钟（同步时钟），在规定的时钟节拍内进行规定的总线操作。

总线宽度增加，单次传输数据增加，数据传输率提高。

总线工作频率增加，数据传输率提高。

突发传输。突发是指在同一行中相邻的存储单元连续进行数据传输的方式，连续传送的周期数称为就是突发长度。在突发传输模式下，多个单元数据当作一个单元（相当于一个数据块）来传送，从而提高了传输效率。

地址/数据复用技术：地址线和数据线是相同的数据线，减少了线的数量，但传输效率并未提高。

22.下列关于外部 I/O 中断的叙述中，正确的是______.

A.中断控制器按所接收中断请求的先后次序进行中断优先级排序

B.CPU 响应中断时，通过执行中断隐指令完成通用寄存器的保护

C.CPU 只有在处于中断允许状态时，才会相应外部设备的中断请求。

D.有中断请求时，CPU 立刻暂停当前指令执行，转去执行中断服务程序

解答：C

A 错误，根据中断字的优先级排序

B 错误，中断隐藏指令完成关中断，保存端点，中断服务程序寻址。其余由中断服务程序完成

C 正确。

D 有中断请求时，若处于关中断状态，不会暂停当前指令执行。

23.下列关于多任务操作系统的叙述中，正确的是_____.

I.具有并发和并行的特点 II.需要实现对共享资源的保护

III. 需要运行在多 CPU 的平台上

A.I B.II C.I,II D.I,II,III

解答：C

并发：一个处理器同时处理不同的任务。

并行：多个处理器同时处理不同的任务。

III，CPU 多是多核的，单个CPU 即可满足要求。

24.某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为 1us。在 T 时刻就绪队列中有 3 个进程 P1，P2 和 P3，其在就绪队列中的等待时间，需要的CPU 时间和优先权如下标所示。

进程	等待时间	需要的 CPU 时间	优先权
P1	30us	12us	10
P2	15us	24us	30
P3	18us	36us	20

若优先权值大的进程优先获得 CPU ，从 T 时刻起系统开始进程调度，系统的平均周转时间为_____.

A.54us B.73us C.74us D.75us

解答：D

周转时间=作业完成时刻-作业到达时刻。

假设 T 时刻为0 ，则作业到达时刻依次为 p1(-30us)，P2(-15us)，P3(-18us)，进程执行顺序为 P2->P3->P1，作业完成时刻分别为 P2(25us)，P3(26us+36us=62us)，P1(63us+12us=75us)，因此周转时间分别为 P1(105us)，P2(40us)，P3(80us)，平均周转时间=（105+40+80）/3=225/3=75us

25.属于同一进程的两个线程 thread1 和 thread2 并发执行，共享初值为 0 的全局变量 x，thread 1 和 thread 2 实现对全局变量 x 加 1 的机器级代码描述如下。

//thread1
mov R1,x;    //(x)->R1
inc R1;      //(R1)+1->R1
mov x,R1;    //(R1)->x


//thread2
mov R2,x;    //(x)->R2
inc R2;      //(R2)+1->R2
mov x,R2;    //(R2)->x

在所有可能的指令执行序列中，使 x 的值为 2 的序列个数是_____.

A.1 B.2 C.3 D.4

解答：B

一个线程在另一个线程写回 x 后进行取数即可，故有两种序列，先执行 thread1，再执行 thread 2 或者先执行 thread2，在执行thread1.

26.假设系统中有 4 个同类资源，进程 P1，P2 和 P3 需要的资源数分别是 4，3 和 1，P1 ，P2 和 P3 申请到的资源数分别为 2，1 和 0，则执行安全性检测的算法是____.

A.不存在安全序列，系统处于不安全状态

B.存在多个安全序列，系统处于安全状态

C.存在唯一安全序列P3，P1，P2，系统处于安全状态

D.存在唯一安全序列 P3，P2，P1，系统处于安全状态

解答：A

不存在安全序列，P1和P2形成死锁。

27.下列选项中，可能导致当前进程 P 阻塞的事件是_____.

I.进程 P 申请临界资源

II.进程 P 从磁盘读数据

III.系统将 CPU 分配给高优先权的进程

A.I B.II C.I，II D.I,II，III

解答：C

I,II 可能导致 P 阻塞。III 会导致进程进入就绪态。

28.若 x 是管程内的条件变量，则当进程执行 x.wait() 时的操作时所做的工作是______.

A.实现对变量 x 的互斥访问

B.唤醒一个在 x 上阻塞的进程

C.根据 x 的值判断该进程是否进入阻塞状态

D.阻塞该进程，并将其插入 x 的阻塞队列

解答：D

管程：管理共享变量及对共享变量的操作过程，让他们支持并发。wait() 阻塞，signal()唤醒。

29.当定时器产生时钟中断后，由时钟中断服务程序更新的内容是______.

I.内核中时钟变量的值

II.当前进程占用的 CPU 时间

III.当前进程在 CPU 中的剩余执行时间

A.I,II B.II,III C.I,III D.I,II,III

解答：D

时钟中断由硬件或操作系统自动触发的中断事件，这种中断事件通常按照一定的时间间隔触发如每秒钟一次或每分钟一次。时钟中断的主要工作是处理和时间有关的信息及决定是否执行调度程序，包括系统时间，进程的时间片，延时，使用 CPU 的时间，各种定时器。故选D。

30.系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求，这种现象称为磁臂黏着。下列磁盘调度算法钟，不会导致磁臂黏着现象的是_____.

A.先来先服务算法（FCFS） B.最短寻道时间优先（SSTF）

C.扫描算法（SCAN） D.循环扫描算法（CSAN）

解答：A

扫描算法，电梯算法。

循环扫描算法，单向扫描。

B，C，D 当某个磁道有大量的访问请求时，会产生磁臂黏着。

31.下列优化方法中，可以提高文件访问速度的是_____.

I.提前读 II.为文件分配连续簇

III.滞后写 IV.采用磁盘高速缓存

A.I,II B.II,III C.I,III,IV D.I,II,III,IV

解答：D

32.下列同步方法中，可以实现让权等待的是_______.

A. PeterSon 方法 B.swap 指令 C.信号量方法 D.TestAndSet 指令

解答：C

让权等待：当进程在等待资源时，让出当前 CPU 控制权，操作进程将该进程放入等待序列。

PeterSon 方法，不会让出 CPU 控制权，会一直等待资源。

//Pi 进程
flag[i]=true;    //flag[i] 为true 表示 Pi 想进入临界区
turn=j;          //变量 turn 表示哪个进程可以进入其临界区，如果 turn==j，表示只 Pj 在临界区运行
while(flag[j] && turn==j)    //Pj 想要访问临界区并且只 Pj 在临界区运行，一直等待
    ; 
访问临界区
flag[i]=false;    // 运行结束，不想进入临界区了
执行剩余代码


//Pj进程
flag[j]=true;
turn=i;
while(flag[i] && trun==i)
    ;
访问临界区
flag[j]=false;
执行剩余代码

swap 指令即交换指令，将两个操作数寄存器的内容中进行交换，一般由硬件实现，不能实现让权等待。

信号量方法，wait() 会让出 CPU 控制权，等待被 signal() 唤醒。

TestAndSet 是一条原子指令，通常用于实现并发控制。他接收一个布尔变量 lock 作为参数，读取变量的当前值，然后将该变量的值设置为 true。在进程访问临界区之前，可以利用 TestAndSet 指令检查和修改标志 lock。如果有进程在临界区，其他进程会重复检查这个标志，知道所有进程都退出临界区。TestAndSet 指令由硬件实现，不能实现让权等待。

33.下列 TCP/IP 应用层协议中，可以使用传输层无连接协议的是______.

A.FTP B.DNS C.SMTP D.HTTP

解答：B

FTP：文件传输协议，基于 TCP 协议

DNS：基与UPD。

SMTP：用于传输邮件，采用 TCP 协议

HTTP：用于传输网页文件，词用TCP协议

34.下列选项中，不属于物理层接口规范定义范畴的是_____.

A.接口形状 B.引脚功能 C.物理地址 D.信号电平

解答：C

物理地址即 MAC 地址，是数据链路层的范畴。

35.IEEE 802.11 无限局域网的 MAC 协议 CSMA/CA 进行信道预约的方法是____.

A.发送确认帧 B.采用二进制指数退避

C.使用多个 MAC 地址 D.交换 RTS 与 CTS 帧

解答：D

发送确认帧主要是为了保证数据传输的准确性。

二进制指数退避是 CSMA/CD 的一种冲突处理方法。

使用多个 MAC 地址与信道预约无关联。

CSMA/CA 协议使用交换 RTS（Request To Send 请求发送帧）与 CTS（Clear To Send 允许发送帧）的方法来进行信道预约。当一台主机想要发送数据时，会先向无线站点发送一个 RTS 帧说明本次要发送的数据和相应时间。无线站点收到该帧后，会广播一个 CTS 帧，在表明允许发送的同时，禁止其余主机在相应的时间发送信息，从而预约信道，避免冲突。

36.主机甲采用停-等协议向主机乙发送数据，数据的传输速率是 3kbps，单向传播时延是200ms，忽略确认帧的传输延时，当信道利用率为 40% 时，数据帧的长度为____.

A.240b B.400b C.480b D.800b

解答：D

假设数据帧的长度为 x b，则其传输延时为 (x/3)ms，单向传播时延为 200ms，忽略传输时延，因此信道利用率为 (x/3)/(x/3+200+200)=0.4 ，解的x=800b

37.路由器 R 通过以太网交换机 S1 和 S2 连接两个网络，R 的接口、主机 H1 和主机 H2 的 IP 地址与 MAC 地址如下所示。若 H1 向 H2 发送 1 个 IP 分组 P，则 H1 发出的封装 P 的以太网的目的 MAC 地址、H2 收到的封装 P 的以太网帧的源 MAC 地址分别是 ______.

A.00-1a-2b-3c-4d-62,00-1a-2b-3c-4d-52

B.00-1a-2b-3c-4d-62 00-1a-2b-3c-4d-61

C.00-1a-2b-3c-4d-51 00-1a-2b-3c-4d-52

D.00-1a-2b-3c-4d-51 00-1a-2b-3c-4d-61

解答：D

IP 分组中的源 MAC 地址位当前发送该分组的 MAC 地址，目的 MAC 地址为下一跳的 MAC 地址。

38.某路由表中有转发接口相同的 4 条路由表项，其目的网络地址分别为 35.230.32.0/21，35.230.40.0/21，35.230.48.0/21，35.230.56.0/21，则该 4 条路由聚合后的目的网络地址为_____.

A.35.230.0.0/19 B.35.230.0.0/20 C.35.230.32.0/19 D.35.230.32.0/20

解答：C

第三段的二进制表示分别为 00100000，00101000，00110000，00111000，最长公共前缀为 001，因此聚合后的网络地址为 35.230.32.0/19

39.UDP 协议实现分用（demultiplexing）时所依据的头部字段是______.

A.源端口号 B.目的端口号 C.长度 D.校验和

解答:B

传输层分用的定义：接收方的传输层剥去报文首部后，能把这些数据正确地交付到目的进程。

端口号是传输层服务访问点，用来表示主机中的应用程序。源端口号在对面回信时使用，目的端口号在终点交付报文时使用。

40.无需转换即可由 SMTP 协议直接传输的是______.

A.JPEG 图像 B.MPEG 视频 C.EXE 文件 D.ACSII文本

解答：D

二、综合应用题

41.（13 分）给定一个含 n （n>=1）个整数所组成的数组，请设计一个时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是 1；整数{1，2，3} 中未出现的最小正整数是 4。要求：

（1）给出算法的基本设计思想

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

（3）说明你所设计算法的时间复杂度与空间复杂度。

解答：（1）开辟一个大小为 n 的数组 cnt，其中 cnt[i] 表示原数组中 i+1 的个数。然后遍历数组，忽略小于等于0 的元素及大于 n 的元素，对于其余元素计数，然后遍历 cnt，其中第一个值为 0 的数字即为所求。

（2）

class Solution{
public:
   int getMinPositiveNum(vector<int>& nums){
       int n=nums.size();
       vector<int> cnt(nums.size(),0);
       for(int num:nums){
           if(num<=0 || num>n){
                continue;    
           }
           cnt[num-1]++;     
       }
       for(int i=0;i<n;i++){
           if(cnt[i]==0){
               return i+1;     
           }
       }
       return n+1;
   }
}

（3）遍历所给数组及cnt 数组各一次，且两次遍历时内部操作均为 O(1) 级别，因此时间复杂度为 O(n)；因为需要额外开辟大小为 n 的空间，因此空间复杂度为 O(n)。

42.（12 分）拟建立一个光通信骨干网络连通 BJ，CS，XA，QD，JN，NJ，TL 和 WH 等八个城市，题 42 图中无向边上的权值表示两个城市之间备选光纤的铺设费用。

请回答下列问题。

（1）仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示），并计算相应方案的总费用

（2）题 42 图可能采用图的哪种存储结构？给出求解问题（1）的算法的名称。

（3）假设每个城市采用一个路由器按（1）所得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL=5 的 IP 分组，则 H2 是否可以收到该分组？

解答：

（1）情况一：

情况二：

总费用为 2+3+2+2+2+3+2=16

（2）邻接矩阵，普里姆算法

（3）情况一时，TL 和 BJ 间的最短距离为 1，可以送达。

情况二时，TL 和 BJ 间最短距离为 5，不可送达。

43.（8分）假定计算机的主频为 500MHz，CPI 为 4。现有设备 A 和 B，其数据传输率分别为 2MB/s 和 40MB/s，对应的 I/O 接口中各有一个 32 位的数据缓冲存储器。请回答以下问题，要求给出计算过程。

（1）若设备 A 采用定时查询 I/O 方式，每次输入/输出都至少执行 10 条指令。设备 A 最多间隔多长时间查询一次才能不丢失数据？CPU 用于设备 A 输入/输出的时间占 CPU 总时间的百分比至少是多少？

（2）在中断 I/O 方式下，若每次中断响应和中断处理的总时钟周期数至少为 400，则设备 B 能否采用中断 I/O 方式？为什么？

（3）若设备 B 采用 DMA 方式，每次 DMA 传送的数据块大小为 1000B，CPU 用于 DMA 预处理和后处理的总时钟周期数为 500，则 CPU 用于设备 B 输入/输出的时间占 CPU 总时间的百分比最多是多少？

知识点：

定时I/O 查询：在规定时间间隔内进行 I/O 操作查询。

中断 I/O 查询：当外部设备需要与主机进行信息交换时，向主机发送一个中断信号，主机在接收到中断信号后暂停当前工作，转去处理外部设备的请求。

解答：（1）对应 I/O 接口中的数据缓冲存储器大小为 32 位即 4B，数据传输速率位 2MB/s，因此至少需要每隔 4B/2MB s=2us（传输 4B 数据的时间）查询一次，否则数据缓冲存储器中的数据可能丢失。

需要每隔 2us 查询一次，因此每秒需查询 1/2us=5*10^5 次，每次执行 10 条指令，CPI 为 4，因此每秒钟用于输入/输出的时钟周期数为 5*10^5 *10*4=20*10^6，计算机主频为500Mhz，故CPU 用于设别 A 输入/输出的时间占 CPU 总时间的 20/500=1/25=4%

（2）设备 B 传输 4B 数据所花费的时间为 4B/40MB/s= 0.1us，单次中断响应和中断处理所花费的时间为 400/500MHz=0.8us，因准备数据时间小于中断响应和中断处理时间，因此数据会被刷新，造成丢失，因此设备 B 不能采用中断 I/O 方式。

（3）CPU 用于DMA预处理和后处理的所耗费的时间为 500/500Mhz=1us，单次 DMA 传送1000B的数据，因此 1s 需要进行 40MB/1000B=4*10^4 次DMA 传送，因此 1s 内 CPU 用于 DMA预处理和后处理的时间为 40ms，因此 CPU 用于设备 B 输入/输出的时间占 CPU 总时间的百分比最多为 40ms/1s=4%

44.（15 分）某计算机采用页式虚拟存储管理方式，按照字节编址。CPU 进行存储访问过程如题 44 图所示。

根据题 44 图回答问题。

（1）主存物理地址占多少位？

（2）TLB 采用什么映射方式？TLB 是采用 SRAM 还是 DRAM 实现？

（3）Cache 采用什么映射方式？若 Cache 采用 LRU 替换算法和回写（write back）策略，则 Cache 每行中除数据（Data），Tag 和有效位外，还应有哪些附加位？Cache 的总容量是多少？Cache 中有效位的作用是什么？

（4）若 CPU 给出的虚拟地址是 0008 C040H，则对应的物理地址是多少？是否在Cache 中命中？说明理由。若 CPU 给出的虚拟地址是 0007 C260H，则该地址所在主存块映射到的 Cache 组号是多少？

知识点：SRAM 静态随机存取存储器，只要通电数据就可保存，读写速度相对较快；DRAM 动态随机存取存储器，需要定期刷新，读写速度相对较慢。

LRU 替换算法。

Cache 总容量=数据总容量+标记项总容量。

解答：（1）主存物理地址由实页号和页内地址组成，实页号 16 位，业内地址 12 位，因此主存物理地址由 16+12=28 位。

（2）图中与TLB 每一行逐个比较，因此为全相联映射。SRAM.

（3）在 Cache 中，根据主存地址与 Cache 中的两行进行比较，因此采用的是二路组相联映射。

采用 LRU 替换算法，是二路组相联，因此一位 LRU 标志最近使用的是组内哪一行即可，因此只需一位。采用回写策略，因此需要一位赃位标志是否需要更新对应数据。

Cache 中共有 2^3=8 组，每组 2 行（二路组相连），每行有 2^5 字节（按字节编址，偏移地址有 5 位），因此数据总容量为 8*2*2^5B=2^9B。主存物理地址中的标记位有 20位，有额外的 1 位有效位，1 位 LRU 位，1位脏位，因此 Cache 中的标记位有 23 位，Cache 有 16 行，因此标记项总容量为 23*16b。因此 Cache 总容量为 2^9B+23*16b=2^12b+23*16b=4464b

有效位用来表示该行数据是否有效。

（4）虚拟地址为 0008 C040H，高 20位 0 008C为虚页号，在TLB 表中找到对应实页号为 0004H，低 12 位 040H 为页内地址，因此主存物理地址为 000 4040H。

Cache 未命中，虚拟地址 000 4040H 中组号为 010 即 2 ，该组内有对应实页号，但有效位不为 1，因此未命中。

虚拟地址 0007 C260H 低 12 位 260H 为页内地址，后八位对应二进制为 0110 0000B，前 3 位为组号，因此对应组号为 3.

45.（8 分）请根据题 44 图给出的虚拟存储管理方式，回答以下问题：

（1）某虚拟地址对应的页目录号为 6，在相应的页表中对应的页号为 6，页内偏移量为 8，该虚拟地址的十六进制表示是多少？

（2）寄存器 PDRB 用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDRB 的内容是否会发生改变？说明理由。同一进程切换时，PDRB 的内容是否会发生变化？

（3）为了支持改进的 CLOCK 置换算法，需要在页表项中设置哪些字段？

知识点：

解答：（1）由图可知，虚拟地址高 20 位为虚页号，低 12 位为页内地址。虚页号由页目录号和页号两部分组成，各 10 位，因此虚拟地址用二进制表示为 0000 0001 1000 0000 0110 0000 0000 1000B 即 0180608H

（2）物理地址。在进程切换时，PDRB 得内容会发生改变，因为不同进程的页目录起始地址不同。同一进程的页目录起始地址相同，因此同一进程切换时，不发生变化。

（3）需要设置访问字段（使用位）和脏位（写回位）。

46.（8分）某文件系统采用索引节点存放文件的属性和地址信息，簇大小为 4KB。每个文件索引节点占 64B，有 11 个地址项，其中直接地址项 8 个，一级、二级和三级间接地址项各一个，每个地址项长度为 4B。请回答以下问题：

（1）该文件系统能够支持的最大文件长度是多少？（给出计算表达式即可）

（2）文件系统用 1M（1M=2^20）个簇存放文件索引节点，用 512M 个簇存放文件数据。弱一个图像文件的大小为 5600B，则该文件系统最多能存放多少个图像文件？

（3）若文件 F1 的大小为 6KB，文件 F2 的大小为 40KB，则文件系统获取 F1 和 F2 最后一个簇号的时间是否相同？为什么？

解答：（1）直接地址项 8 个，每个簇大小为 4KB，因此 8 个直接地址项能支持的最大长度为 8*4KB；每个簇的大小为 4KB，每个地址项长度为 4B，因此每个簇可以存放 4KB/4B=1024 个地址项，因此一级间接地址能支持的最大长度为 1024*4KB，二级间接地址能支持的最大长度为 1024*1024*4KB，三级间接地址能支持的最大长度为 1024*1024*1024*4KB。

综上所述，该文件系统能够支持的最大文件长度为 (2^5+2^12+2^22+2^32)KB

（2）文件系统使用 1M 个簇存放文件索引节点，单个簇大小为 4KB，每个索引节点占 64B，因此该文件系统功能存放 1M*4KB/64B= 64M 个索引节点；使用 512M 个簇存放数据文件，单个图像大小为 5600B，因此一共可以存放 512M*4KB/5600B=512*1024/1400M>64M 个图像文件。因能存放的图像文件数量受限于索引节点数量，因此该文件系统最多能存放 64M 个图像文件。

（3）文件 F1 的大小为 6KB，使用两个簇即可保存，因此只需使用两个地址项；文件 F2 的大小为 40KB，而文件系统中直接地址项只有 8 个（4Kb*8=32KB<40KB），因此需要使用到 1 个一级间接地址。故文件系统获取 F1 和 F2 最后一个簇号的时间不相同。

47.（7分）某公司的网络如题 47 图所示。IP 地址空间 192.168.1.0/24 被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了 IP 地址，销售部子网的 MTU=1500B，技术部子网 MTU=800B。

请回答下列问题：

（1）销售部子网的广播地址是多少？技术部子网的子网地址是多少？若每个主机仅分配一个 IP 地址，则技术部子网还可以连接多少台主机？

（2）假设主机 192.168.1.1 向主机 192.168.1.208 发送一个长度为 1500B 的 IP 分组，IP 分组头部长度为 20 B，路由器在通过接口 F1 转发该 IP 分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP 分片封装数据的字节数是多少？至少需要分为几个片？每个分片的偏移量是多少？