408-2012

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

1.求整数 n（n>=0）阶乘的算法如下其时间复杂度是______。

int fact(int n){
    if(n<=1){
        return 1;
    }
    return n*fact(n-1);
}

A.O( $\log_{2}n$ ) B.O(n) C.O( $n\log_{2}n$ ) D.O(n^2)

解答：B

2.已知操作符包括"+"、"-"、"*"、"/"、"(" 和 ")" 。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是_____。

A.5 B.7 C.8 D.11

解答：A

a+b ，+ 入栈；

a+b-a，+ 出栈，-入栈；栈-

a+b-a*(( ，*(( 入栈栈-*((

a+b-a*((c+d，+入栈栈-*((+

a+b-a*((c+d) ,+( 出栈栈 -*(

a+b-a*((c+d)/e，/ 入栈栈 -*(/

a+b-a*((c+d)/e-f，/出栈，-入栈，栈 -*(-

a+b-a*((c+d)/e-f)+，-*(-出栈，+入栈，栈+

a+b-a*((c+d)/e-f)+g ，+出栈

由上可治，栈中操作符个数最多为 5。

3.若一颗二叉树的前序遍历序列为 a,e,b,d,c，后续遍历为 b,c,d,e,a，则根节点的孩子节点______。

A.只有 e B.e,b C.e.c D.无法确定

解答: A

只有以下两种二叉树或其对称二叉树四种可能,故选A

4.若平衡二叉树高度为 6,且所有非叶节点的平衡因子均为 1,则该平衡二叉树的节点总数为______.

A.10 B.20 C.32 D.33

解答:B

某节点的左子树与右子树的高度差为其平衡因子.

高度为 1 时,总结点数 f(1)=1

高度为 2 时,总结点数 f(2)=2

高度为 3 时,总结点数为f(3)= f(2)+f(1)+1=2+1+1=4

高度为 4 时,总结点数为 f(4)=f(3)+f(2)+1=4+2+1=7

高度为 5 时,总结点数为 f(5)=f(4)+f(3)+1=7+4+1=12

高度为 6 时,总节点数为 f(6)=f(5)+f(4)+1=12+7+1=20,选B

5.对有 n 个节点, e 条边且使用邻接表存储的有向图进行广度优先遍历,其算法复杂度是____.

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

解答:C

最多遍历 n个节点, e条边,故选C

6.若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为 0,则关于该图拓扑排序的结论是____.

A.存在,且唯一 B.存在,且不唯一 C.存在,可能不唯一 D.无法确定是否存在

解答:C

矩阵中主对角线以下的元素均为 0 -> 该有向图中不存在环.无法确定是否唯一.

7.如下图所示的有向带权图,若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是 b,第二条最短路径的目标顶点是c ,后续得到的其余各最短路径的目标顶点依次是____.

A.d,e,f B.e,d,f C.f,d,e D.f,e,d

解答: C

	b	c	d	e	f
a	2(min)	5
a		3(min)	5
a			5	7	4(min)
a			5(min)	7
a				6(min)

8.下列关于最小生成树的叙述中,正确的是_____.

I 最小生成树的代价唯一

II 所有权值最小的边一定会出现在所有的最小生成树中

III 使用普里姆(Prime)算法从不同顶点开始得到的最小生成树一定相同

IV 使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同

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

解答:A

最小生成树:一个有 n 个节点的连通图的极小连接子图 (n 个节点, n-1 条边),且包含原图中的所有节点,并且有保持图连通的最少边.

克鲁斯卡尔算法:从权值最小的边开始逐个判断是否保留.

普利姆算法:这个节点判断是否保留.

I 最小生成树的代价一定唯一,总是选择权值最小的边

II 权值最小的边不一定会出现在最小生成树中,若环中的边均为权值最小的边,至少有一条边会被舍去

III N 个节点构成环,N-1条边权值相等时有 N-1 棵不同的最小生成树

IV 二者得到的最小生成树可能相同(最小生成树唯一)也可能不同(最小生成树不唯一时间可能不同)

9.已知一棵三阶 B-树,如下图所示.删除关键字 78 得到一棵新的新 B- 树, 其最右节点中的关键字是_____.

A.60 B.60,62 C.62,65 D.65

解答 :D

65 移动到 78 的位置,62移动到65的位置.

10.在内部排序过程中,对尚未确定最终位置的所有元素进行一遍处理成为一趟排序.下列排序方法中,每一趟排序结束至少都能确定一个元素最终位置的是______.

I 简单选择排序 II 希尔排序 III 快速排序 IV.堆排序 V.二路归并排序

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

解答:A

简单选择排序,每次至少确定最大或最小的元素位置

希尔排序:希尔排序也叫缩小增量排序。假设初始增量（下标值相差固定值）为 x ，第一次对子序列 0，x，2x.....，子序列 1，1+x，1+2x,...... 子序列 2，2+x，2+2x,....... ...... 子序列 x-1, 2x-1,3x-1...... 进行排序，然后将初始增量变小进行再排序，直至最后初始增量变为 1.第一趟可能无法确定一个元素的位置

快速排序:每次至少确定选取的基准元素的位置.

堆排序:每次都是获取最大堆根节点并使堆重新变为最大堆的过程.每次获得最大元素

二路归并排序:将其划分为 n 组列表,每组两个元素.使列表有序后两两合并.

11.对一待排序序列分别进行折半插入排序和直接插入排序,两者之间可能的不同之处是_____.

A.排序的总趟数 B.元素的移动次数

C.使用辅助空间的数量 D.元素之间的比较次数

解答:D
插入排序:将元素不断插入前面已经排序好的序列时使用顺序查找法.

折半插入排序:将元素不断插入千米那已经排序好的序列时使用折半查找法确定该元素所在位置

12.假定基准程序 A 在某计算机上的运行时间为 100秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。若 CPU 速度提高 50%，I/O 速度不变，则运行基准程序 A 的所耗费的时间为_____。

A.55s B.60s C.65s D.70s

解答： D

CPU 速度提高 50%，速度变为原来的 1.5 倍，时间变为原来的 2/3 倍。原来为 90s，现在是 90*2/3=60 秒，总耗费时间为 70s。

13.假设编译器规定 int 型和 short 型长度分别为 32 位和 16 位，执行下列 C 语言语句：

unsigned short x=65530;
unsigned int y=x;

得到 y 的机器数是_____。

A.0000 7FFAH B.0000 FFFAH C.FFFF 7FFAH D.FFFF FFFAH

解答：B

65530D=65535D-5D=FFFFH-0005H=FFFAH

无符号整数没有符号位，因此不需要扩展。

14. float 类型（即 IEEE 754 单精度浮点数格式）能表示的最大正整数是_____。

A.2^126-2^103 B.2^127-2^104 C.2^127-2^103 D.2^128-2^104

解答：D

IEEE 754 单精度浮点数由三部分组成，符号码（1位）+ 阶码（8 位）+ 尾数（23位），因此能表达的最大值为 0111 1111 1111 1111 1111 1111 1111 1111B，即 1.11111111111111111111111B* 2^（1111 1111B）=1.11111111111111111111111B*2^127D= (10B-0.00000000000000000000001B+)*2^127D=2^128B-2^(-23)D*2^127D=2^128D-2^104D.

15.某计算机存储器按字节编址，采用小端方式存储数据。假定编译器规定 int 型和 short 型长度分别为 32 位和 16 位，并且数据按边界对齐存储。某 C 语言程序段如下：

struct{
    int a;
    char b;
    short c; 
}record;
record.a=273;

若 record 变量的首地址为 0xC008，则地址 0xC008 中的内容和 record.c 的地址分别是_____。

A.0x00、0xC00D B.0x00、0xC00E C.0x11、0xC00D D.0x11、0xC00E

解答：

读取数据时从低位到高位读取。

小端方式存放数据：数据的低位存放在地址空间，数据的高位存放在高地址空间。

数据按边界对齐存储，数据项仅仅能存储在地址是数据项大小的整数倍的内存位置上。

273D=0000 0111H ，record.a 的地址分配时 0xC008为 11H ，0xC009为01H，其余为全0。

record.a 的地址为 0xC008，a的大小为 32位即4个字节，因此record.b的起始地址位 0xC00CH；数据按边界对齐存储，b 的大小虽然是 1 个字节但 0xC00D 不是 record.c 大小 2 个字节的整数倍，record.c 后移，因此 record.c 的起始地址是 0xC00EH。

16.下列关于闪存(Flash Memory)的叙述中，错误的是_______。

A.信息可读可写，并且读、写速度一样快

B.存储元由 MOS 管组成，是一种半导体存储器

C.掉电后信息不丢失，是一种非易失性存储器

D.使用随机访问方式，可替代计算机外部存储器

解答：A

闪存主要用于一般性数据存储，以及在计算机与其他数字产品间交换传输数据，如存储卡与U盘。

A项，闪存可读可写，但写入时必须先擦除原有数据，因此写的速度比读慢。

17.假设某计算机按字编址，Cache 有 4 个行，Cache 和主存之间交换的块大小为 1 个字。若 Cache 的内容初始为空，采用 2 路组相联映射方式和 LRU 替换策略。访问的主存块依次是 0，4，8，2，0，6，8，6，4，8时，命中的次数是_______。

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

解答：A

LRU （Least Recently used）替换策略即最近最少使用。

Cache 4行，采用 2 路组相联映射方式，因此每组两个，访问的主存都在映射到同一组中。根据 LRU 策略，命中 1 次。

此题存异，唐朔飞版教材与蒋本珊教材中并不一致，当年采用蒋版，如今应采用唐版

18.某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微指令，构成 5 个互斥类，分别包含 7，3，12，5，和 6 个微指令，则操作控制字段至少有______。

A.5 位 B.6 位 C.15 位 D.33 位

解答：C

字段直接编码法：将微指令控制字段划分为若干个子字段，每个子字段内的微命令进行同一编码，需要留出状态表示无命令。

5 个互斥类，分别包含 7，3，12，5，和 6 个微指令，则各需要 3，2，4，3，3 位，因此总共需要至少 15 位。

19.某同步总线的时钟频率为 100MHz，宽度为 32 位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次 "主存写" 总线事务传输 128 位数据所需要的时间至少是____。

A.20ns B.40ns C.50ns D.80ns

解答：C

突发（猝发）传输方式：可以连续传输地址连续的数据。

时钟频率为 100MHz，则一个时钟周期为 1/100M s=10^(-8)s= 10ns

传送地址需要 1 个时钟周期；总线宽度为 32 位，需要传输 128 位数据，因此传输数据需要至少 128/32=4 个时钟周期。因此总的时钟周期至少为 5 个即至少需要 40ns

20.下列关于 USB 总线特性的叙述中，错误的是______。

A.可实现外设的即插即用和热插拔

B.可通过级联方式连接多台外设

C.是一种通信总线，连接不同外设

D.同时可传输两位数据，数据传输率高

解答：D

热插拔即带电插拔，在不关闭电源和系统的情况下插入或拔出外设。

级联方式：将两个以上的设备通过某种方式连接起来以达到扩容的效果。

USB 总线是串行总线，一次只能发送一位。因此 D 错误。

21.下列选项中，在 I/O 总线的数据线上传输的信息包括_____。

I.I/O 接口中的命令字 II.I/O 接口中的状态字 III.中断类型号

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

解答：D

I/O 接口与 CPU 之间的 I/O 总线有数据线、控制线和地址线。其中控制线和地址线只传输 CPU 的信息给 I/O 接口。故 I/O 接口的命令字，状态字和中断类型号均有数据线传输给 CPU。

22.响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括_____。

I.关中断 II.保存通用寄存器内容 III.形成中断服务程序入口地址并送 PC

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

解答：B。

中断处理过程为：关中断-保存断点-识别中断源-保护现场-中断事件处理-恢复现场-开中断-中断返回。前三者由硬件（即中断隐指令）完成，与中断服务程序无关。

23.下列选项中，不可能在用户态发生的时间是_____。

A.系统调用 B.外部中断 C.进程切换 D.缺页

解答：C

A.系统调用是操作系统提供给用户程序的接口，发生在用户态，被调用程序在在核心态下执行。

B.外部调用发生在用户态，执行在核心态度

C.进程切换属于系统调用执行过程中的事件，只能发生在核心态。

D.缺页产生后，在用户态发生缺页中断，然后进入核心态执行缺页中断服务程序。

24.中断处理和子程序调用都要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的寄存器是______。

A.程序计数器 B.程序状态字寄存器 C.通用数据寄存器 D.通用地址寄存器

解答：B

子程序调用只需保存断点，即程序计数器PC的位置。

中断处理会保存程序计数器 PC 和程序状态字寄存器 PSW 的内容。

子程序调用和中断处理都不会保存通用数据寄存器和通用地址寄存器的内容。

25.下列关于虚拟存储器的叙述中，正确的是______。

A.虚拟存储只能基于连续分配技术

B.虚拟存储只能基于非连续分配技术

C.虚拟存储容量只受外存容量限制

D.虚拟存储容量只受内存容量限制

解答：B

虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

虚拟存储的三种实现方式：请求分页式存储管理、请求分段存储管理和请求段页式存储管理。

若虚拟存储器采用连续分配技术，会有相当一部分内存空间处于暂时或长时间的空闲状态，，造成内存资源的浪费，因此虚拟存储只能基于非连续分配技术。

虚拟存储器最大容量有 CPU 地址长度决定，实际容量为内存容量与外存容量之和。

26.操作系统的 I/O 子系统通常由四个层次构成，每一层明确定义了与邻近层次的接口，其合理的层次组织排列顺序是______。

A.用户级 I/O 软件，设备无关软件，设备驱动程序，中断处理程序

B.用户级 I/O 软件，设备无关软件，中断处理程序，设备驱动程序

C.用户级 I/O 软件，设备驱动程序，设备无关软件，中断处理程序

D.用户级 I/O 软件，中断处理程序，设备无关软件，设备驱动程序

解答：A

设备管理软件一般分为 4 个层次：用户层，与设备无关的系统调用处理层、设备驱动程序以及中断处理程序，因此选 A。

27.假设五个进程 P0，P1，P2，P3，P4，共享三类资源R1，R2，R3，这些资源总数分别为 18、6、22。T0 时刻的资源分配情况如下所示，此时存在的一个安全序列为______。

进程	已分配资源			资源最大需求
进程	R1	R2	R3	R1	R2	R3
P0	3	2	3	5	5	10
P1	4	0	3	5	3	6
P2	4	0	5	4	0	11
P3	2	0	4	4	2	5
P4	3	1	4	4	2	6

A.P0，P2，P4，P1，P3 B.P1，P0，P3，P4，P2

C.P2，P1，P0，P3，P4 D.P3,P4,P2,P1,P0

解答:D

T0 时刻, R1 剩余 2, R2 剩余 3, R3 剩余 3.

A 项, 全部分配给 P0 后, P0 无法完成, 不安全

B 项, P1 顺利完成,此时 R1 : 6, R2:3 , R3:6

全部分配给 P0 后, P0 无法完成,不安全

C 项,全部分配给 P2 后,P2 无法完成,不安全

D 项, P3 顺利完成,此时: R1:4; R2;3;R3:7 此时任选一项均可顺利完成.

28.若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据,则下列关于此过程的叙述中,正确的是____.

I.若该文件的数据不在内存中,则该进程进入睡眠等待状态

II.请求 read 系统调用会导致 CPU 从用户态切换到核心态

III.read 系统调用的参数应包含文件的名称

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

解答:A

I.当所读写的文件不在内存时,产生中断,原进程进入阻塞状态,知道所需数据调入内存后,才被唤醒.

II.系统调用会导致 CPU 从用户态切换到核心态

III.要读一个文件,首先使用 open 系统调用打开该文件( 参数包含文件的路径名和文件名),然后 read 使用 open 返回的文件描述符确定读取那个文件的内容.

read 的功能是试图从 fd 所指示的文件中读入n 个字节的数据,并将其传送到由指针buf 所指示的缓冲区中.因此 read 要求用户提供以下三个参数:1.文件描述符号qd 2. buf缓冲区首地址 3.传送的字节数n

29.一个多道批处理系统中仅有 P1 和 P2 两个作业, P2 比 P1 晚 5ms 到达,他们的计算和 I/O 操作顺序如下:

P1:计算 60ms, I/O 80ms,计算 20ms

P2:计算 120ms,I/O 40ms,计算 40ms

若不考虑调度和切换时间,则完成这两个作业需要的时间至少是_____.

A.240ms B.260ms C.340ms D.360ms

解答:B

多道批处理系统:内存中存放多道程序,到某道程序因某种原因如 I/O 请求而放弃CPU 时,操作系统调度另一程序运行.

0ms 时,p1 到达,开始计算

5ms 时,p2 到达,p1继续计算

60ms 时,p1执行完毕,开始 I/O, p2 开始计算.

140ms 时,p1 I/O 结束,p2 继续计算.

180ms 时,p2计算结束,开始 I/O;P1 开始计算

200ms 时,p1 计算结束,运行完成.p2 继续I/O

220ms 时,p2 I/O 结束,开始计算.

260ms 时,p2计算结束,运行完成.

因此至少需要260ms

30.若某单处理器多进程系统中有多个就绪态进程,则下列关于处理机调度的叙述中,错误的是_____.

A.在进程结束时能进行处理机调度.

B.创建新进程后能进行处理机调度

C.在进程处于临界区时不能进行处理机调度

D.在系统调用完成并返回用户态时不能进行处理机调度

解答:C

处理机调度:从就绪进程中按一定算法选择一个进程并将处理机分配给他运行,以实现进程的并发执行.

临界区:每个资源访问临界资源的那段程序称为临界区

C.进程处于临界区,说明进程正在占用处理机,只要不对临界资源造成破坏,不影响处理机调度

31.下列关于线程和进程的叙述中,正确的是____.

A.不管系统是否支持线程,进程都是资源分配的基本单位

B.线程是资源分配的基本单位,进程是调度的基本单位

C.系统级线程和用户级线程的切换需要内核的支持

D.同一进程的各个线程拥有各自不同的地址空间.

解答:A

B.进程是资源分配的基本单位,线程是调度的基本单位

C.在用户级线程中,有关线程管理的所有工作都由应用程序完成,与内核无关

D.同一进程的各个线程共享进程的地址空间.

32.下列选项中,不能改善磁盘设备 I/O 性能的是____-.

A.重排 I/O 请求次序 B.在一个磁盘上设立多个分区

C.预读与滞后写 D.优化文件物理块分布

解答:B

提前读:把要读的数据提前放到内存中,要用的时候直接从内存取

滞后写:把要写的数据先放在内存中,等积累多了再一次写到内存中.

A 项与 D 项:可以更快地找到所有目标文件,因此可以改善磁盘设备的 I/O 性能

C 项可以减少读和写的切换次数,因此可以改善磁盘设备的 I/O 性能,若存在重复性和阵发性 I/O 进程,效果尤为明显.

B 项与改善磁盘设备的 I/O 性能无多大关系,反而会提高处理的复杂度并且会降低磁盘的利用率

33.在 TCP/IP 体系结构中，直接为 ICMP 提供服务的是______.

A.PPP B.IP C.UDP D.TCP

解答：B

ICMP（International Control Message Protocal）互联网控制消息协议，主要功能有两个：一是确认 IP 包是否能够成功到达目标地址，第二个功能是进行网络诊断。

PPP （Point to Point Protocal）协议，点对点协议，主要用于在全双工的同异步链条上进行点到点的传输。PPP 协议是链路层协议，为网络层提供服务。

ICMP 报文作为数据字段封装在 IP 分组中，因此 IP 协议直接为 ICMP 协议提供服务。

34.在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是_____。

A.机械特性 B.功能特性 C.过程特性 D.电气特性

解答：C

机械特性规定实际物理连接细节。

功能特性规定每条交换电路需完成的功能。

过程特性定义各条物理线路的工作过程和时序关系。

电气特性规定了使用的编码（必须用相同的电压来描述相同的状态，必须使用相同宽度的信号比特）

35.以特网的 MAC 协议提供的是______。

A.无连接不可靠的协议 B.无连接可靠的服务

C.有连接不可靠的协议 D.有连接可靠的协议

解答：A

MAC （multiple access control protocal）协议，多路访问控制协议，用于在共享介质（如以太网）中控制网络设备之间的访问。是数据链路层协议。

36.两台主机直接的数据链路层采用后退 N 帧协议（GBN）传输数据，数据传输速率为 16kbps，单向传播时延为 270ms，数据帧长度范围是 128-512 字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率到达最高，帧序号的比特数至少为______。

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

解答：B

本题等价于从发送第一个帧开始到收到这个帧的第一个确认帧最多可以发送多少帧，要尽可能多地发送帧，则帧长尽可能的短，即帧长为 128 B。

数据传输速率为16kbps，128B=128*8b，发送到信道上需要 128*8/（16*1000） s=64ms，单项传播时延为270ms，接受方接受需要 64ms，因此一个来回需要 64+2*270+64=128+540= 668ms. 最多发送 668/64=10.4275 个帧，取 10，需要 4 个比特来表示。因此选 B

37.下列关于 IP 路由器功能的描述中，正确的是_____。

I.运行路由协议，设置路由表

II.检测到拥塞时，合理丢弃 IP 分组

III.对收到的 IP 分组头部进行差错校验，确保传输的 IP 分组不丢失

IV.根据收到的 IP 分组的目的 IP 地址,将其转发到合适的输出路线上

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

解答:C

对于 III , 路由器会对收到的 IP 分组头部进行差错校验,但并不保证传输的 IP 分组不丢失

38.ARP 协议的功能是______

A.根据 IP 地址查询 MAC 地址 B.根据 MAC 地址查询 IP 地址

C.根据域名查询 IP 地址 D.根据 IP 地址查询域名

解答:A

ARP (Address Resolution Protocol) 地址解析协议,功能是网络层的 IP 地址解析为数据链路层的 MAC 地址.

39.某主机的 IP 地址是 180.80.77.55, 子网掩码为 255.255.252.0.若该主机向其所在子网发送广播分组,则目的地址可以是_____.

A.180.80.76.0 B.180.80.76.255 C.180.80.77.255 D.180.80.79.255

解答:D

180.80.01001101.55

255.255.11111100.00000000

将 IP地址后10位全置为 1 即可,即180.80.01001111.255 -> 180.80.79.255

40.若用户 1 和用户 2 之间发送和接受电子邮件的过程如下图所示,则图中 1,2,3 阶段分别使用的应用层协议可以是______.

A.SMTP,SMTP,SMTP B.POP3,SMTP,POP3

C.POP3,SMTP,SMTP D.SMTP,SMTP,POP3

解答:D

SMTP 采用主动发送的通信方式,在用户代理向邮件服务器及邮件服务器之间发送邮件,SMTP 发送端主动将邮件发送到接收端; POP3 采用先请求在接收的模式,当用户读取邮件时,向服务器发送请求,服务器再将邮件发送给用户.

二、综合应用题

41.设有 6 个有序表 A、B、C、D、E、F，分别含有10，35，40，50，60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成一个升序表，并在最坏情况下比较的总次数达到最少。请回答一下问题：

（1）给出完整的合并过程，并求出最坏情况下的比较总次数。

（2）根据你的合并过程，描述 N（N>=2）个不等长升序表的合并策略并说明理由。

解答：（1）a.合并表 A 和表 B 生成表 G，含有 45 个元素，最坏情况下需要比较 44 次

b.合并表 G 和表 C 生成表 H，含有 85 个元素，最坏情况下需要比较 84 次

c.合并表 D 和表 E 生成表 I，含有 110 个元素，最坏情况下需要比较 109 次

d.合并表 I 和表 H 生成表 J，含有 195 个元素，最坏情况下需要比较 194 次

e.合并表 J 和表 F 生成表 K，含有 395 个元素，最坏情况下需要比较 394 次

最坏情况下需要比较 45+85+110+195+395-5=825次

（2）合并策略：对于 N（N>=2）个待合并不等长升序表，每次取出元素个数最少的两个表进行合并，将生成的新表重新加入待合并升序表中，重复此操作直至待合并不等长升序表数量为 1 即可。

理由：在最坏情况下，长度为 a 的表和长度为 b 的表需要比较 a+b-1 次，是基于两表长度的，因此每次选择长度最小的表可使总的合并次数最少。

42.假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，"loading" 和 "being" 的存储映像如下图所示。

设 str1 和 str2 分别指向两个单词所在单链表的头节点，链表节点结构为 data | next，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向的两个链表共同后缀的起始位置(如图中子符 i 所在节点的位置 p)。要求：

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

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

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

解答：（1）首先获得两单链表的长度 l1 和 l2，然后将两链表末端对齐，开始比较。

（2）

class Solution{
    public int getStartPos(Node str1, Node str2){
        //获取两单词长度
        int l1=getLength(str1);
        int l2=getLength(str2);
        //末尾对齐    
        if(l1>l2){
            for(int i=0;i<l1-l2;i++){
                l1=l1.next;
            }
        }else{
            for(int i=0;i<l2-l1;i++){
                l2=l2.next;
            }
        }
        //寻找相等位置
        while(str1!=null && str1.next!=str2.next){
            str1=str1.next;
            str2=str2.next;
        }
        return str1;
    } 
    public int getLength(Node node){
        int res=0;
        while(node!=null){
            node=node.next;
            res++;
        }
        return res;
    }
}

（3）时间复杂度为O(m+n)

43.假定某计算机的 CPU 主频为 80MHz，CPI 为 4，平均每条指令访存 1.5 次，主存与 Cache 之间交换块的大小为 16B，Cache 的命中率为 99%，存储器的总线宽度为 32 位。请回答一下问题：

（1）该计算机的 MIPS 数是多少？平均每秒 Cache 缺失的次数是多少？在不考虑 DMA 传送的情况下，主存带宽至少达到多少才能满足 CPU 的访存要求？

（2）假定 Cache 缺失的情况下访问主存时，有 0.0005% 的缺页率，则 CPU 平均每秒产生多少次缺页异常？若页面大小为 4KB，每次缺页都需要访问磁盘，访问磁盘时 DMA 传送采用周期挪移方式，磁盘 I/O 接口的数据缓冲寄存器为 32 位，则磁盘 I/O 接口平均每秒发出的 DMA 请求次数至少是多少？

（3）CPU 和 DMA 同时要求使用存储器总线时，哪个优先级更高？为什么？

（4）为了提高性能，主存采用四体低位交叉存储模式，工作时每 1/4 个周期启动一个体。若每个体的存储周期为 50ns，则该主存能提供的最大带宽是多少？

知识点：

主频：一秒钟的时钟脉冲数，为时钟周期的倒数。

CPI （circle per instruction）：执行一条指令所需要的时钟周期数。

MIPS（million instructions per second）：每秒执行多少百万条指令。

带宽：单位时间内所能传输的数据总量。

DMA 数据传送方式：I/O 设备和存储器间的直接数据交换。

DMA 数据传送的周期挪用方式：当 I/O 设备没有 DMA 请求时，CPU 按程序要求访问内存，一旦 I/O 设备有 DMA 请求，则 I/O 设备挪用一个或几个周期。

低位交叉编址：将程序连续存放在相邻体中。（假设有四个体，低位交叉编址类似于第一行存放在体1，第二行存放在体2，第三行存放在体 3，第四行存放在体 4，第五行存放在体 1；高位交叉编址第1，2，3，4......按序存放在体 1 中，直至体 1放满，然后依次存放于体 2，3，4......）

解答：（1）该计算机的 MIPS 为 80M/4/10^6=20。

平均每秒 Cache 缺失的次数为 20*10^6*1.5*1%=300000 次

当 Cache 缺失时，CPU 访问主存，主存和 Cache 间以块为传送单位，块的大小为 16B，因此主存带宽至少达到 16B*300000/s=4.8MB/s

（2）CPU 平均每秒产生 300000*0.0005%=1.5 次缺页异常

存储器总线宽度为 32 位，因此每传送 32 位数据，I/O 接口发送一次 DMA 请求。因此磁盘 I/O 接口平均每秒发出的 DMA 请求次数至少为 1.5*4KB/32b=6*1024*8/32=1.5*1024=1536 次

（3）DMA 的优先级更高。因为若 DMA 请求得不到响应，磁盘缓冲寄存器内的数据可能会丢失。

（4）总线宽度是 32 位,每 1/4 个周期启用一个体,则每个周期启用四个体,传输 4*32 位即 16B 的数据,一个周期时长位 50ns,因此主存所能提供的最大带宽为 16B/50ns=320MB/s

44.某 16 位计算机中,带符号整数用补码表示,数据 Cache 和指令 Cache 分离.下表给出了指令系统中的部分指令格式,其中 Rs 和 Rd 表示寄存器, mem 表示存储单元地址, (x) 表示寄存器 x 或存储单元 x 的内容.

该计算机采用 5 段流水方式执行指令,各流水段分别是取指(IF),译码/读寄存器(ID),执行/计算有效地址(EX),访问存储器(M)和结果写回寄存器(WB),流水线采用"按序发射,按序完成"方式,没用采用转发技术处理数据相关,并且同一个寄存器的读和写操作不能在同一个时钟周期内进行.请回答一下问题:

(1)若 int 型变量 x 的植为 -513,存放在寄存器 R1 中,则执行指令 "SHR R1" 后,R1的内容是多少?(用 16 进制表示)

(2)若某个时间段内,有连续的四条指令进入流水线,其执行过程中没有发生任何阻塞,则执行这四条指令所需的时钟周期数是多少?

(3)若高级语言程序中某赋值语句为 x=a+b.x,a,b 均为 int 型变量,他们的单元存储地址分别表示为 [x],[a],[b].该语句对应的指令序列及其在指令流水线中的执行过程如下图所示.

则这四条指令执行过程中, I3 的 ID 阶段和 I4 的 IF阶段被阻塞的原因各是什么?

知识点:

转发技术:在运算完成后,不写回寄存器而是直接将其送往下一指令的输入段,称为旁路或转发.

解答: (1) -513的二进制表示为 1111 1101 1111 1111B,执行指令后变为 1111 1110 1111 1111B 即 FEFFH

(2) 因为未发生阻塞,所以每个流水段完成后可以直接执行下一条执行的该流水段,因此一共需要 8 个时钟周期.

(3)I3 的ID 阶段被阻塞的原因I3 与 I1,I2 存在数据相关,需等I1, I2 将数据写回寄存器后, I3 才能读寄存器内容.

I4 的 IF 阶段被阻塞的原因是 I3 的 ID 阶段被阻塞.

45.某请求分页系统的局部页面置换策略如下：系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有访问过的页框将被系统回收，并放入空闲页框链尾，其中内容在下一次分配前不被清空。若发生缺页时，如果该页页被使用过且还在空闲页框链表中，那么重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。

假设不考虑其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中的页框号依次为 32，15，21，41。进程 P 依次访问的 <虚拟页号，访问时刻>是 <1,1>,<3,2>,<0,4>,<0,6>,<1,11>,<0,13>,<2,14>,请回答一下问题：
（1）访问<0,4>时，对应的页框号是多少？说明理由。

（2）访问<1,11>时，对应的页框号是多少？说明理由。

（3）访问<2,14>时，对应的页框号是多少？说明理由。

（4）该策略是否适合于时间局部性好的程序？说明理由

知识点：

解答：（1）访问<1,1>时，驻留集为空，且该页不在空闲页框链表中，因此对应页框号为 32。此时驻留集为虚拟页号 1 对应页框 32。空闲页框链表为 15，21，41

访问<3,2>时，页 3 不在驻留集及空闲页框链表中，因此对应页框号为 15。此时驻留集中为虚拟页号 1对应页框 32，虚拟页号 3 对应页框 15。空闲页框链表为 21，41

访问<0,4>时，页 0 不在驻留集及空闲页框链表中，因此对应页框号为21。此时驻留集中为虚拟页号 1对应页框 32，虚拟页号 3 对应页框 15，虚拟页 0 对应页框号 21。空闲页框链表为 41。

综上所述，对应页框号为 21。

（2）在时刻五，扫描驻留集，无被收回页框。

访问<0,6>时，页 0 在驻留集中。

在时刻 10 ，扫描驻留集，页框32，15被收回并添加至空闲页框链尾。此时驻留集中为虚拟页 0 对应页框号 21。空闲页框链表为 41，32（1），15（3）.

访问<1,11>时，页 1 在空闲页框链表中，重新放回驻留集。此时此时驻留集中为虚拟页 0 对应页框号 21，虚拟页号 1对应页框 32。空闲页框链表为 41，15（3）。

综上所述，页1对应页框号为 32。

（3）访问<0,13>时，页0 在驻留集中。

访问<2,14>时，页 2 不在驻留集及空闲页框链表中，因此对应页框号为 41.

（4）合适。程序的时间局部性越好，未清空的页框被取回可能性越高，该策略的优势越明显。

46.某文件系统的最大容量为 4TB（1TB=2^40B），以磁盘块为基本分配单位。磁盘块大小为 1KB，文件控制块 FCB 包含一个 512B 的索引表区。请回答一下问题：

（1）假设索引表区采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中的块号至少占多少字节？可支持单个文件最大长度是多少？

（2）假设索引表区采用如下结构：第 0~7 字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占 6B，块数占 2B；剩余 504 字节采用直接索引结构，一个索引项占 6B，那么可支持的单个文件最大长度是多少字节？为使单个文件长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。

知识点：
解答：（1）文件系统最大容量为 2^42B，磁盘块大小为 2^10B，因此有 2^42/2^10=2^32 个磁盘块。以磁盘块为基本分配单位，因此需要至少 32/8=4 个字节来存放块号。

索引表区为 512B，单个块号长度为 4B，因此一共可以存放 512B/4B=128 个块的地址。因此可支持的单个文件最大长度为 128*1KB=128KB。

（2）块数占 2B，最多表示 2*16 个块；504 字节采用直接索引结构，一个索引占 6B，因此最多有 504B/6B=84 个索引，即最多表示 84 个块。因此单个文件的最大长度为 2^16KB+84KB。

为使单个文件长度最大，单个文件长度因接近 4TB即 2^40B,那么块数应该尽可能大，又因为至少需要 4B 来存放块号，此时前 8 个字节应该用 4 个字节存放起始块号，4个字节存放块数。

47.主机 H 通过快速以太网连接 Internet，IP 地址为 192.168.0.8，服务器 S 的 IP 地址为 211.68.71.80。H 和 S 使用 TCP 通信时，在 H 上捕获的其中 5 个 IP 分组如题 47-a 表所示。

回答下列问题：

（1）题 47-a 表中的 IP 分组中，哪几个是由 H 发送的？哪几个完成了 TCP 连接建立过程？哪几个在通过快速以太网传输时进行了填充？

（2）根据题 47-a 表中的 IP 分组，分析 S 已经收到的应用层数据数据字节数是多少？

（3）若题 47-a 表中的某个 IP 分组在 S 发出时的前 40 个字节如题 47-b 表所示，则该 IP 分组到达 H 时经过了多少个路由器？

解答：（1）主机 H 的IP 地址为 192.168.0.8 即 c0.a8.00.08，因此编号为 1，3，4 的分组由 H 发送。

编号为 1 的分组，SYN=1，ACK=0；编号为 2 的分组，SYN=1，ACK=1；编号为 3 的分组，SYN=0，ACK=1；编号为 4 的分组，SYN=1，ACK=1；编号为 5 的分组，SYN=1，ACK=1。根据 TCP 建立连接过程中会产生 3 个报文：

a. H 向 S 发送 SYN=1，ACK=0

b. S 向 H 发送，SYN=1，ACK=1

c. H 向 S 发送，SYN=0，ACK=1

由 H 发送的报文只有 1，3，4，SYN 和 ACK 符合要求的只有 1，4。由 S 发送的报文 SYN=1，ACK=1，2，5斗符合要求，但是 a 报文即编号为 1 的报文序列号为 84 6b 41 c5H，因此b 报文的确认号应为84 6b 41 c6H，只有 2 满足要求。

综上所述，编号为 1，2，4 的报文完成了TCP 建立的过程。

快速以太网中有效数据帧的长度至少为 48(30H)B，因此编号为 3，5 的数据帧需要填充。

（2）根据编号为 3 的报文，发送数据的起始序列号为 84 6b 41 c6H。报文 4 由 H 发送，序列号为 84 6b 41 c6H. 报文 5 由 S 发送，确认号为 84 6b 41 d6H。84 6b 41 d6H- 84 6b 41 c5H = 10H ，因此 S 至少收到了 16 个字节的数据。

（3）根据标志、片偏移及该分组来自 S 可知，该分组与编号为 5 的报文相对应。该分组发出时的 TTL 为 40H，H 收到时 TTL 为 31H，40H-31H=15，因此经过了 15 个路由器。