二、综合应用题给出如下图所示的有向图(结点旁边的数为结点的编号，即结点在图中的位置)。
有向图1. 试写出带入度域的邻接表；
与题中有向图对应的带入度域的邻接表如下图所示。
与题中有向图对应的带入度域的邻接表
2. 给出在此邻接表存储结构下，以h为起始结点的深度优先遍历序列和广度优先遍历序列，并写出遍历过程中所走过的边。
图的深度优先遍历序列为：h，g，e，d，a，b，f，c，遍历过程中所走过的边为：
＜h，g＞，＜g，e＞，＜e，d＞，＜h，a＞，＜a，b＞，＜b，f＞，＜f，c＞。
图的广度优先遍历序列为：h，g，a，e，b，d，f，c，遍历过程中所走过的边：
＜h，g＞，＜h，a＞，＜g，e＞，＜a，b＞，＜e，d＞，＜b，f＞，＜b，c＞。
3. VRAM的容量是多少?
VRAM存储器存储汉字的编码，因为一屏可显示32×12=384字，每个汉字的编码占2个字节，所以VRAM的容量=32×12×2B=768B。
4. 字符发生器(ROM)的容量是多少?
ROM存储器存储汉字的行点阵信息，因为总共可显示3000个汉字，每个汉字以11×16点阵组成，字间间隔一点，所以ROM的容量=3000×12×16=72000B。
5. 各计数器的位数分别是多少?时钟频率是多少?
排计数器：汉字可显示12排，根据帧回扫占扫描时间的20%，可求得回扫占3排时间，所以一共是15排，则排计数器需要4位。
行计数器：每个汉字点阵16行，两排字间隔4行，故一排汉字共用20行，行计数器需要5位。
字计数器：每排32个字，根据行回扫占扫描时间20%，可求得回扫为8个字时间，故共40个字，则字计数器需用6位。
点计数器：每个字的点阵是11列，加上间隔1点，共12点，故点计数器为4位。
这样时钟频率为：15×20×40×12×50Hz=7200000Hz=7.2MHz。
6. 在实现文件系统时，每个盘块为512B。假设目录文件存放在磁盘上，文件控制块占64B。为加快文件目录的检索速度，可利用“文件控制块分解法”。通常将文件控制块分解成两部分，第1部分占10B(包括文件名和文件内部号)，其中文件名占8B；第二部分占56B(包括文件内部号和文件其他描述信息)。
(1)假设某一目录文件共有254个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件中的某一文件控制块的平均访问磁盘次数。
(2)一般地，若目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号部分，请给出访问磁盘次数减少的条件。
(1)由于每个盘块为512B，某一目录文件共有254个文件控制块，每个文件控制块占64B。
采用分解法前：一个盘块可存放512/64=8个目录项，则254个文件控制块要占254/8=32个磁盘块。平均查找一个目录项需访问磁盘块数为其块数的一半：32/2=16个。
采用分解法后，将文件控制块分解成两部分，第1部分占10B(包括文件名和文件内部号)，第2部分占56B(包括文件内部号和文件其他描述信息)。一个盘块可存放512/10≈51个目录项。这样254个目录项要占254/51≈5个磁盘块。平均查找一个目录项需访问磁盘5/2≈3次，由文件内部标识可知文件控制信息所在的磁盘块号，再访问一次磁盘，得到文件控制信息。故共需3+1=4次访问磁盘。
(2)由分解法计算可知，若文件控制信息长度L占用的字节数大于文件名和文件内部号部分占用的字节数K两倍以上，即L＞2K时，采用分解法查找该目录文件中的某一文件控制块的平均访问磁盘次数将减少。这是因为分解后虽然占用两部分空间，但查找文件控制信息是通过计算得到的。故条件是n＞2m。
7. 一个2Mbit/s的网络，线路长度为1km，传输速度为20m/ms，分组大小为100B，忽略应答帧大小。如果采用简单停一等协议，问实际数据速率是多少?信道利用率是多少?如果采用滑动窗口协议，问最小序号位是多少?
发送延迟=(8×100)/(2×106)=0.4ms，传播延迟=(1000m)/(20m/ms)=50ms，1帧发送完后等待1个RTT，然后发送另一帧。
周期长度=0.4ms+50ms×2=100.4ms，1个周期内发送1帧。
实际数据速率=(8×100b/帧×1帧)/100.4ms=7968bit/s
信道利用率=7968bit/s/(2×106)bit/s=0.3984%
如果采用滑动窗口协议，可连续发送的帧的个数为
(周期长度)/(分组发送时间)=100.4ms/0.4ms=251＜256=28
所以，最小序号位为8位。
8. 画出选片译码逻辑图。
选片译码逻辑如下图所示。
选片译码逻辑
9. 写出每片RAM的寻址范围。
8片RAM的寻址范围分别是：0000H～1FFFH、2000H～3FFFH、4000H～5FFFH、6000H～7FFFH、8000H～9FFFH、A000H～BFFFH、C000H～DFFFH和E000H～FFFFH。
10. 如果运行时发现不论往哪片存储器存放8KB数据，以A000H为起始地址的存储芯片都有相同的数据，分析故障原因。
说明译码器有误，5输出始终为低，从而使第6片RAM始终被选中。
11. 若发现译码器中的地址线A
13与CPU断线，并搭接到高电平的故障，问后果如何?
若发现A13与CPU断线，并搭接到高电平的故障，则0、2、4、6信号均不会为0，故第1、3、5、7片RAM始终不被选中。
路由表12. 现收到5个分组，其目的IP地址分别为：①128.96.39.10；②128.96.40.20；③128.96.40.153；④192.4.153.17；⑤192.4.153.90。试分别计算其下一跳。
①目的IP地址128.96.39.10与子网掩码255.255.255.128相与得128.96.39.0，可见该分组经接口0转发。
②目的IP地址128.96.40.20与子网掩码255.255.255.128相与得128.96.40.0，经查路由表可知，该项分组经R2转发。
③目的IP地址128.96.40.153，与子网掩码255.255.255.128相与后得128.96.40.128，与子网掩码255.255.255.196相与后得128.96.40.128，经查路由表知，该分组转发选择默认路由，经R4转发。
④目的IP地址192.4.153.17，与子网掩码255.255.255.128相与后得192.4.153.0，与子网掩码255.255.255.196相与后得192.4.153.0，经查路由表知，该分组经R3转发。
⑤目的IP地址192.4.153.90，与子网掩码255.255.255.128相与后得192.4.153.0，与子网掩码255.255.255.196相与后得192.4.153.64，经查路由表知，该分组转发选择默认路由，经R4转发。
13. 路由协议的作用是什么?
路由协议用于路由器之间不断地交换路由信息，并根据收集到的信息，运行路由算法，优化更新路由，维持路由器有一个动态的优化的路由表。
14. 在什么情况下要选择多协议路由器?
路由器可以通过不同类型的网卡分别连接不同类型的局域网。如果互联的局域网高层采用了不同协议，这时就需要使用多协议路由器。
15. 假定磁盘传输数据以32位的字为单位，传输速率为1MB/s。CPU的时钟频率为50MHz。
(1)使用程序查询的输入输出方式，一个查询操作需要100个时钟周期，求CPU为I/O查询所花费的时间比率，假定进行足够的查询以避免数据丢失。
(2)用中断方式进行控制，每次传输的开销(包括中断处理)为100个时钟周期，求CPU为传输磁盘数据花费的时间比率。
(3)采用DMA控制进行输入输出操作，假定DMA的启动操作需要1000个时钟周期。 DMA完成时处理中断需要500个时钟周期，如果平均传输的数据长度为4KB，问在磁盘工作时处理器将用多少时间比率进行输入输出操作，忽略DMA申请使用总线的影响。
根据题意可知，每传送一个字需要4μs，CPU的时钟周期为0.02μs。
(1)程序查询的输入输出方式，一个查询操作需要100个时钟周期，而时钟周期=0.02μs，所以每个查询操作需要2μs，CPU为I/O查询所花费的时间比率为0.02×100/4=1/2=0.5。
(2)用中断方式法进行控制，每次传输的开销(包括中断处理)为100个时钟周期，而时钟周期=0.02μs，所以每次传输的开销时间=100×0.02=2μs，传送一个字的时间为4μs，CPU为传输磁盘数据花费的时间比率为0.02×100/4=1/2=0.5。
(3)采用DMA控制进行输入输出操作，平均传输的数据长度为4KB，根据数据传输率，传送时间4KB÷1 MB/s=4ms。又由于DMA的启动操作需要1000个时钟周期，即1000×0.02=20μs；DMA完成时处理中断需要500个时钟周期，即500×0.02=10μs。所以在磁盘工作时CPU为进行输入输出操作花费的时间比率为0.02×1500/4000=30/4000=0.0075。
深色：已答题 浅色：未答题