一、单项选择题1. 在一单道批处理系统中，一组作业的提交时间和运行时间如下表所示。请问3种作业调度算法的平均周转时间是______。
作业提交时间和运行时间表
|
| 作业 | 提交时间 | 运行时间 |
| 1 | 8.0 | 1.0 |
| 2 | 8.5 | 0.5 |
| 3 | 9.0 | 0.2 |
| 4 | 9.1 | 0.1 |
(1)先来先服务(2)短作业优先(3)响应比高者优先
- A.0.5、0.875、0.825
- B.0.85、0.875、0.625
- C.0.85、0.675、0.825
- D.0.5、0.675、0.625
A B C D
C
[解析] FCFS(先来先服务)和SJF(短作业优先)算法大家应该都很熟悉，这里不多解释。
高响应比优先算法的优先级=(等待时间+运行时间)/运行时间
周转时间=结束时间-提交时间=等待时间+运行时间=响应时间(仅在某些情况下成立，后面会讨论)
(1)FCFS(见下表)
作业执行顺序为1、2、3、4
|
| 作业 |
提交时间 |
运行时间 |
开始时间 |
完成时间 |
| 1 |
8.0 |
1.0 |
8.0 |
9.0 |
| 2 |
8.5 |
0.5 |
9.0 |
9.5 |
| 3 |
9.0 |
0.2 |
9.5 |
9.7 |
| 4 |
9.1 |
0.1 |
9.7 |
9.8 |
该算法最简单，根据FCFS原则，作业执行顺序为1、2、3、4。
T=(1.0+1.0+0.7+0.7)/4=0.85
(2)SJF(见下表)
作业执行顺序为1、3、4、2
|
| 作业 |
提交时间 |
运行时间 |
开始时间 |
完成时间 |
| 1 |
8.0 |
1.0 |
8.0 |
9.0 |
| 2 |
8.5 |
0.5 |
9.3 |
9.8 |
| 3 |
9.0 |
0.2 |
9.0 |
9.2 |
| 4 |
9.1 |
0.1 |
9.2 |
9.3 |
过程说明：作业1提交时，没有其他作业，故作业1马上开始运行，直到完成，此时有两个进程都在就绪队列，即作业2和作业3。根据SJF，选择作业3运行，直到完成，此时仍有两个进程在就绪队列，即作业2和作业4。根据SJF，选择作业4运行，直到完成，最后作业2运行，完成。
T=(1.0+1.3+0.2+0.2)/4=0.675
(3)高响应比(见下表)
作业执行顺序
|
| 作业 |
提交时间 |
运行时间 |
开始时间 |
完成时间 |
| 1 |
8.0 |
1.0 |
8.0 |
9.0 |
| 2 |
8.5 |
0.5 |
9.0 |
9.5 |
| 4 |
9.0 |
0.2 |
9.6 |
9.8 |
| 3 |
9.1 |
0.1 |
9.5 |
9.6 |
作业1提交时，没有其他作业，故作业1马上开始运行，直到完成，此时有两个进程都在就绪队列，即作业2和作业3。此时作业2响应比为(0.5+0.5)/0.5=2，作业3响应比为(0+0.2)/0.2=1，根据响应比高者优先，选择作业2执行，直到完成，此时仍有两个进程在就绪队列中，即作业3和作业4。作业3响应比为(0.5+0.2)/0.2=3.5，作业4响应比为(0.4+0.1)/0.1=5，根据响应比高者优先，选择作业4执行，直到完成，最后作业3运行，完成。
T=(1.0+1.0+0.8+0.5)/4=0.825
关于响应时间和周转时间的关系如下：
响应时间：从提交第一个请求到产生第一个响应所用时间。(这个定义不好理解)
周转时间：从作业提交到作业完成的时间间隔。
如果大家多做几道这样的题会发现，这两个时间经常是相等的，即等待时间+运行时间。但既然有两个定义，就肯定有区别之处。之所以相等的原因是，这些题目太老了，这些题目中大都有个前提，“批处理系统中”，当产生第一次响应时，就是作业完成了。但在分时系统中，时间片结束后，就认为产生了第一个响应。
9. 生产者进程和消费者进程代码如下。生产者进程有一个局部变量nextProduced，以存储新产生的新项：
while(1){
/*produce an item in nextProduced*/
while((in+1) % BUFFER SIZE==out); /*do nothing*/
buffer[in]=nextProduced;
in=(in+1) % BUFFER SIZE;
}
消费者进程有一个局部变量nextConsumed，以存储所要使用的项：
while(1){
while(in==out); /*do nothing*/
nextConsumed=buffer[out];
out=(out+1) % BUFFER SIZE;
/*consume the item in nextConsumed*/
}
当in==out和(in+1)%BUFFER_SIZE==out条件成立的时候，缓冲区中item数目各是______。
- A.0，BUFFER_SIZE
- B.0，BUFFER_SIZE-1
- C.BUFFER_SIZE-1，0
- D.BUFFER_SIZE，0
A B C D
B
[解析] 通过阅读代码可知，变量in指向缓冲区中下一个空位，变量out指向缓冲区中的第一个非空位。BUFFER_SIZE是缓冲区最大能容纳的item数目。buffer中，非空的位置范围是[out，in-1]或者[out，BUFFER_SIZE-1]∪[0，in-1]，即有如图所示的两种情况。
当in==out时，前一个操作肯定是运行了消费者进程(out追上了in)，因为生产者进程中，当遇到(in+1)%BUFFER_SIZE==out时就忙等，即生产进程无法使in==out，所以此时缓冲区中item数目应该是0。
当(in+1)%BuFFER_SIZE==out时，即in差一个空位就追上out了，此时缓冲区中item数目应该是BUFFER_SIZE-1。
所以本题正确答案是B选项。
10. 下列关于DRAM和SRAM的说法中，错误的是______。
Ⅰ．SRAM不是易失性存储器，而DRAM是易失性存储器
Ⅱ．DRAM比SRAM集成度更高，因此读写速度也更快
Ⅲ．主存只能由DRAM构成，而高速缓存只能由SRAM构成
Ⅳ．与SRAM相比，DRAM由于需要刷新，所以功耗较高
- A.Ⅱ、Ⅲ和Ⅳ
- B.Ⅰ、Ⅲ和Ⅳ
- C.Ⅰ、Ⅱ和Ⅲ
- D.Ⅰ、Ⅱ、Ⅲ和Ⅳ
A B C D
D
[解析] 本题考查SRAM和DRAM的区别。SRAM和DRAM的差别在于DRAM时常需要刷新，但是SRAM和DRAM都属于易失性存储器，掉电就会丢失，Ⅰ错误。SRAM的集成度虽然更低，但速度更快，因此通常用于高速缓存Cache，而DRAM则是读写速度偏慢，集成度更高，因此通常用于计算机内存，Ⅱ错误。主存可以用SRAM实现，只是成本高且容量相对小，Ⅲ错误。和SRAM相比，DRAM成本低、功耗低、但需要刷新，Ⅳ错误。
注意：SRAM和DRAM的特点见下表。
| SRAM |
非破坏性读出，不需要刷新。断电信息即丢失，属易失性存储器。存取速度快，但集成度低，功耗较
大，常用于Cache。 |
|
|
| DRAM |
破坏性读出，需要定期刷新。断电信息即丢失，属易失性存储器。集成性高、位价低、容量大和功耗
低。存取速度比SRAM慢，常用于大容量的主存系统。 |
|
|
二、综合应用题1. 下图是3个计算机局域网A，B和C，分别包含10台，8台和5台计算机，通过路由器互联，并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LAN A和LAN B共用一个C类IP地址(网络地址为202.38.60.0)，并将此IP地址中主机地址的高两位作为子网编号。A网的子网编号为01，B网的子网编号为10。主机号的低6位作为子网中的主机编号。C网的IP网络号为202.36.61.0。请回答如下问题：
(1)为每个网络中的计算机和路由器的端口分配IP地址；
(2)写出三个网段的子网掩码；
(3)列出路由器的路由表；
(4)LAN B上的一台主机要向B网段广播一个分组，请填写此分组的目的地址；
(5)LAN B上的一台主机要向C网段广播一个分组，请填写此分组的目的地址。
本题主要考查网络设备路由器地址分配的一般原则、路由表的原理、子网划分和子网掩码。首先要根据题意给出LANA和LANB的子网，这里A网的子网编号为01，也就是202.38.60.01000000，即202.38.60.64，因此一般选择该网络最小的地址分配给路由器的a接口，也就是202.38.60.01000001，即202.38.60.65，子网掩码为255.255.255.192。
同理B网的子网编号为10，202.38.60.10000000，即202.38.60.128，b接口的地址为202.38.60.10000001，即202.38.60.129，子网掩码是255.255.255.192。对于C网，c接口的地址为202.38.61.1，掩码为255.255.255.0。前3个问题就可以求解了，针对问题4、5，也就是子网的广播地址，对于B网段，其广播地址为202.38.60.10111111，即202.38.60.191，对于C网段，就是标准的202.38.61.255。
(1)路由器端口的IP地址，如下表所示：
| 端口 |
IP地址 |
子网掩码 |
| a |
202.38.60.65 |
255.255.255.192 |
| b |
202.38.60.129 |
255.255.255.192 |
| c |
202.38.61.1 |
255.255.255.0 |
| d |
61.60.21.80 |
255.0.0.0 |
(2)各个网段的子网掩码，如下表所示：
| 网络名 |
网络地址 |
子网掩码 |
| A |
202.38.60.64 |
255.255.255.192 |
| B |
202.38.60.128 |
255.255.255.192 |
| C |
202.38.61.0 |
255.255.255.0 |
(3)路由器的路由表，如下表所示：
| 目的网络地址 |
子网掩码 |
下一条地址 |
接口 |
| 202.38.60.64 |
255.255.255.192 |
直连 |
a |
| 202.38.60.128 |
255，255。255.192 |
直连 |
b |
| 202.38.61.0 |
255.255.255.0 |
直连 |
c |
| 61.0.0.0 |
255.0.0.0 |
直连 |
d |
| 0.0.0.0 |
0.0.0.0 |
61.60.21.80 |
d |
(4)202.38.60.191。
(5)202.38.61.255。
2. 开始运行后，CPU有无空闲等待?若有，在哪段时间内等待?计算CPU的利用率。
由甘特图可知，CPU存在空闲等待，等待现象发生在A运行100ms～150ms时间段。在此时间段内，进程A忙于打印信息，进程B忙于输入数据，两者都进入阻塞状态，从而CPU空闲。从图中可知，A，B进程总的运行时间为300ms。A使用CPU时间为50+50=100ms；B使用CPU为50+100=150ms。所以CPU利用率为(100+150)/300≈83.3%。
3. 进程A运行时有无等待现象?若有，在什么时候发生等待现象?
4. 进程B运行时有无等待现象?若有，在什么时候发生等待现象?
进程B存在等待现象，首次等待发生在A运行后0～50ms时间段内，第二次等待发生在A运行后180～200ms时间段内。
5. 写出主存与缓存的地址格式(标明各字段名称与位数)。
主存按字节编址，块大小为64B=2
6B，故字块内地址6位；缓冲共分8(=2
3)组，故组地址3位；Cache地址格式如下表所示：
主存容量为1MB，故主存地址为20位，主存地址格式中主存字块标记位数为20-3-6=11位，主存地址格式如下表所示：
| 主存字块标记(11位) |
组地址(3位) |
字块内地址(6位) |
6. 假定Cache的存取周期为20μs，命中率为0.95，希望采用Cache后的加速比大于10。那么主存储器的存取速度应大于多少?(访存时CPU同时访问Cache和主存，如Cache命中则中断主存访问)
设主存存取周期为T，则Cache主存系统的平均存取时间T1为：
T1=20μs×0.95+T×(1-0.95)
根据题意，希望Cache的加速比大于10，则应满足T＞10T1，代入上式解得：
T＞380μs，即要求主存储器的存取周期应大于380μs。
7. 一个系统采用段页式存储方式，有16位虚地址空间，每个进程包含两个段，并且一页大小为2
12字节。段表和页表如下表所示(所有的值为二进制，并且段长以页为单位)。下列哪些二进制虚地址会产生缺段中断或缺页中断?哪些二进制虚地址能转换为物理地址?如果可以转换，请写出物理地址。
(1)0001010001010111(提示：产生缺段中断，或缺页中断?)
(2)1110010011111111(提示：转换后的物理地址是什么?)
(3)1111010011000111(提示：产生缺段中断，或缺页中断?)
(4)0011001011000111(提示：转换后的物理地址是什么?)
(5)请问该系统最大物理内存是多少?
| 段表 |
| 段号 | 段长 | 页表地址 |
| 0 | 111 | 指向页表0的指针 |
| 1 | 110 | 指向页表1的指针 |
| 页表0 |
| 页号 | 存储块 | 状态 |
| 000 | 101011 | 1 |
| 001 | 001010 | 0 |
| 010 | 001011 | 1 |
| 011 | 100110 | 1 |
| 100 | 001100 | 0 |
| 101 | 110110 | 1 |
| 110 | 111010 | 0 |
| 111 | 011101 | 0 |
| 页表1 |
| 页号 | 存储块 | 状态 |
| 000 | 010100 | 0 |
| 001 | 110101 | 1 |
| 010 | 110100 | 0 |
| 011 | 011001 | 0 |
| 100 | 110011 | 1 |
| 101 | 001001 | 0 |
| 110 | 000101 | 1 |
| 111 | 100010 | 1 |
由题意可得逻辑地址各字段为：
(1)
段号为0，页号为001，查看页表0中的001号页的状态，其状态为0，说明此页尚未调入内存。故发生缺页中断。
(2)
段号为1，页号为110，段表长度为6，查看页表1中的110号页的状态，其状态为1，说明此页面已调入内存。则相应的物理地址为：000101010011111111
(3)
段号为1，页号为111，段表长度为6，发生越界。所以发生缺页中断。
(4)
段号为0，页号为111，查看页表0中的011号页的状态，其状态为1，说明此页面已调入内存。则相应的物理地址为：100110010011111111。
(5)由题可见，内存最多可以放8页，每页2
12字节，故系统最大物理内存是2
3×2
12=2
15=32K。
普通文件的文件控制块组织如图2所示，其中，每个磁盘地址占2个字节，前10个地址直接指示该文件前10页的地址。第11个地址指示一级索引表地址，一级索引表中每个磁盘地址指示一个文件页地址；第12个地址指示二级索引表地址，二级索引表中每个地址指示一个一级索引表地址；第13个地址指示三级索引表地址，三级索引表中每个地址指示一个二级索引表地址。请问：
8. 一个普通文件最多可有多少个文件页?
因为磁盘块大小为512B，所以索引块大小也为512B，每个磁盘地址大小为2B。因此，一个一级索引表可容纳256个磁盘地址。同样，一个二级索引表可容纳256个一级索引表地址，一个三级索引表可容纳256个二级索引表地址。这样，一个普通文件最多可有文件页数为10+256+256×256+256×256×256=16843018页。
9. 若要读文件J中的某一页，最多启动磁盘多少次?
由图可知，目录文件A和D中的目录项都只有两个，因此这两个目录文件都只占用一个物理块。要读文件J中的某一页，先从内存的根目录中找到目录文件A的磁盘地址，将其读入内存(已访盘1次)。然后从目录A中找出目录文件D的磁盘地址并将其读入内存(已访盘2次)。再从目录D中找出文件J的文件控制块地址并将其读入内存(已访盘3次)。在最坏情况下，该访问页存放在三级索引下，此时需要一级一级地读三级索引块才能得到文件J的地址(已访盘6次)。最后读入文件J中的相应页(共访盘7次)。所以，若要读文件J中的某一页，最多启动磁盘7次。
10. 若要读文件W中的某一页，最少启动磁盘多少次?
由图可知，目录文件C和U的目录项较多，可能存放在多个链接在一起的磁盘块中。在最好情况下，所需的目录项都在目录文件的第一个磁盘块中。先从内存的根目录中找到目录文件C的磁盘地址读入内存(已访盘1次)。在C中找出目录文件I的磁盘地址读入内存(已访盘2次)。在I中找出目录文件P的磁盘地址读入内存(已访盘3次)。从P中找到目录文件U的磁盘地址读入内存(已访盘4次)。从U的第一个磁盘块中找出文件W的文件控制块地址读入内存(已访盘5次)。在最好情况下，要访问的页在文件控制块的前10个直接块中，按照直接块指示的地址读文件W的相应页(已访盘6次)。所以，若要读文件W中的某一页，最少启动磁盘6次。
11. 就上一小题而言，为最大限度减少启动磁盘的次数，可采用什么方法?此时，磁盘最多启动多少次?
为了减少启动磁盘的次数，可以将需要访问的W文件挂在根目录最前面的目录项中。此时，只需读内存中的根目录就可以找到W的文件控制块，将文件控制块读入内存(已访盘1次)，最差情况下，需要的W文件的那个页挂在文件控制块的三级索引下，那么读3个索引块需要访问磁盘3次(已访盘4次)得到该页的物理地址，再去读这个页即可(已访盘5次)。此时，磁盘最多启动5次。
[解析] 本题考查文件目录的结构。
12. 判断此有向图是否有强连通分量?若有请画出。
此图的强连通分量有两个，分别是(v1，v3)，(v3，v4)如图1所示：
图1 强连通分量
13. 画出此图的十字链表存储结构。
十字链表表示如图2所示：
图2 十字链表表示
14. 简述基于图的深度优先搜索策略，并判别一个以邻接表存储的有向图是否存在顶点v
i到顶点v
j的路径的基本步骤。
将起始结点入栈并标记，将与此结点相邻的结点依次入栈并标记，如果相邻结点有目标结点j则输出成功，否则出栈一个结点，将与此结点相邻的结点依次入栈并标记，直到栈空，返回失败。
15. 设记录的关键字(key)集合：K={24，15，39，26，18，31，05，22}，请回答：
依次取K中各值，构造一棵二叉排序树(不要求平衡)，并写出该树的前序、中序和后序遍历序列。
设Hash表表长m=16，Hash函数H(key)=(key)%13，处理冲突方法为“二次探测法”，请依次取K中各值，构造出满足所给条件的Hash表；并求出等概率条件下查找成功时的平均查找长度。
将给定的K调整成一个堆顶元素取最大值的堆(即大根堆)。
(1)将关键字{24，15，39，26，18，31，05，22}依次插入构成的二叉排序树如下：
先序遍历序列：24，15，05，18，22，39，26，31
中序遍历序列：05，15，18，22，24，26，31，39
后序遍历序列：05，22，18，15，31，26，39，24
(2)各关键字通过Hash函数得到的散列地址如下表。
| 关键字 |
24 |
15 |
39 |
26 |
18 |
31 |
05 |
22 |
| 散列地址 |
11 |
2 |
0 |
0 |
5 |
5 |
5 |
9 |
|
Key=24、15、39均没有冲突，H0(26)=0，冲突，H
1(26)=0+1=1，没有冲突；Key=18没有冲突，H0(31)=5，冲突，H1(31)=5+1=6，没有冲突；H0(05)=5，冲突，H1(05)=5+1=6，冲突，H2(05)=5-1=4，没有冲突，Key=22没有冲突故各个关键字的存储地址如下表所示。
| 地址 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
| 关键字 |
39 |
26 |
15 |
|
05 |
18 |
31 |
|
|
22 |
|
24 |
|
|
|
|
没有发生冲突的关键字，查找的比较次数为1，发生冲突的关键字，查找的比较次数为冲突次数+1，因此，等概率下的平均查找长度为：
ASL=(1+1+1+2+1+2十3+1)/2=1.5欠
(3)首先对以26为根的子树进行调整，调整后的结果如图b所示；对以39为根的子树进行调整，调整后的结果如图c所示；再对以15为根的子树进行调整，调整后的结果如图d所示；最后对根结点进行调整，调整后的结果如图e所示。
深色：已答题 浅色：未答题