问答题
问答题试比较主存、辅存、缓存、控存、虚存。
问答题下图是三个计算机局域网A，B和C，分别包含10台，8台和5台计算机，通过路由器互联，并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LANA和LANB共用一个C类IP地址(网络地址为202.38.60.0)，并将此IP地址中主机地址的高两位作为子网编号。A网的子网编号为01，B网的子网编号为10。主机号的低6位作为子网中的主机编号。C网的IP网络号为202.36.61.0。请回答如下问题：
问答题在数组中，某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如，在数组{2，4，1，16，7，5，11，9}中，数对之差的最大值是11，是16减去5的结果。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度。
问答题一台设置为IP地址自动获取的主机H接入到仅有一台服务器的局域网络中，在H上截获到如下表所列的两个以太网数据帧前48个字节的十六进制报文，请参考表中的数据回答如下问题：表编号以太网数据帧前48个字节的十六进制报文1ffffffffffff5078 lc190f76080045000148006f00008011 393700000000ffffffff004400430134 efab01010600910c2ffffffffffff5078 1c19044a080045000240693200008011 08d5c0a805feffffffff00430044022c 2aab02010600910c注：以太网帧、IP分组头和UDP段头结构分别如图(a)、图(b)和图(c)所示。
问答题假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空间状态。
问答题已知某8位机的主存采用半导体存储器，其地址码为18位，采用4K×4位的静态RAM芯片组成该机所允许的最大主存空间，并选用模块板形式，问： (1)若每个模块板为32K×8位，共需几个模块板? (2)每个模块板内共有多少片RAM芯片? (3)主存共需要多少RAM芯片?CPU如何选择各模块板?如何选择具体芯片(说明选用的器件及地址码的分配)?
问答题设某机中，CPU的地址总线A
15
～A
0
，数据总线D
7
～D
0
(A
0
、D
0
为最低位)。存储器地址空间为3000H～67FFH。其中3000H～4FFFH为ROM区，选用4K×2的ROM芯片；5000H～67FFH为RAM区，选用2K×4的SRAM芯片。请问：
问答题
问答题已知数组A[1..n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。
问答题某机有五个中断源L
0
，L
1
，L
2
，L
3
，L
4
，按中断响应的优先次序由高向低排序为L
0
→L
1
→L
2
→L
3
→L
4
，现要求中断处理次序改为L
1
→L
3
→L
4
→L
0
→L
2
，写出各中断源的屏蔽字。
问答题大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小为512B，有一个文件，包含了590个逻辑记录，每个记录占255B；其中，为检索方便，采用成组法存储，在每个物理块上只存放2个记录。文件A在该文件目录中的位置如下图所示。此树形文件目录结构由根目录结点和作为文件中间的目录结点以及作为信息文件的叶子结点组成，每个目录项占127B，每个物理块存放4个目录项。根目录的内容常驻内存。(1)若文件采用隐式链接文件结构，设每块的连接字占4B，存放在每个物理块的尾部。如果要将文件A读入内存，至少要读取几次硬盘?为什么?(2)若文件采用连续文件结构，如果要将文件A的逻辑记录号为480的记录读入内存，至少要读取几次硬盘?为什么?
问答题某机字长32位，CPU内有32个32位的通用寄存器，设计一种能容纳64种操作的指令系统，设指令字长等于机器字长。 (1)如果主存可直接或间接寻址，采用寄存器—存储器型指令，能直接寻址的最大存储空间是多少?画出指令格式。 (2)如果采用通用寄存器作为基址寄存器，则上述寄存器—存储器型指令的指令格式有何特点?画出指令格式并指出这类指令可访问多大的存储空间?
问答题对于一个堆栈、若其入栈序列为1，2，3，……，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1，2，3，……，n)/输出序列对应一种二叉树形态的方法，并以入栈序列1，2，3(即n=3)为例加以说明。
问答题在实现文件系统时，一般为加快文件目录的检索速度，可利用“文件控制块部分装入”的方法。假设目录文件(即文件控制块)存放在磁盘上，磁盘的每个盘块为512B，每个目录项占128B，其中文件名占11B。为提高检索速度，通常将目录项分解成两部分，第一部分(包括文件名和文件内部号)占16B，第二部分(包括文件内部号和文件其他描述信息)占122B。假设某一目录共有254个目录项(文件控制块)，试分别给出前、后二种方法查找该目录文件某一目录项的平均访问磁盘次数。
问答题在下列情况下，计算传送1000KB文件所需要的总时间，即从开始传送时起直到文件的最后一位到达目的地为止的时间。假定往返时间RTT是100ms，一个分组是1KB(即1024字节)的数据，在开始传送整个的文件数据之前进行的起始握手过程需要2RTT的时间。 (1)带宽是1.5Mbps，数据分组可连续发送； (2)带宽是1.5Mbps，但在结束发送每一个数据分组之后，必须等待一个RTT才能发送下一个数据分组； (3)带宽是无限大的值，即我们取发送时间为0，并且在等待每个RTT后可发送多达20个分组； (4)带宽是无限大的值，在紧接起始握手后我们可以发送一个分组，此后，在第一次等待RTT，后可发送21个分组，在第二次等待RTT后可发送22个分组……在第n次等待RTT后可发送2n个分组。
问答题假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上个结点的值。
问答题在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制块分解法”。假设目录文件存放在磁盘上，每个盘块有512字节。文件控制块占64字节，其中文件名占8个字节。通常将文件控制块分解成两部分，第一部分占16字节(包括文件名和文件内部号)，第二部分占48字节(包括文件内部号和文件其他描述信息)。
问答题实现一个经典的“读者-写者”算法时，若当前临界区中有读者访问，写者再来时必须在临界区外面等候，如果其后读者源源不断地到达，按策略他们均可以进入临界区，始终保持临界区中有读者访问，那么写者可能长时间不能进入临界区而形成饥饿。为解决此类问题，我们修改访问策略，要求当写者到达时，写者具有优先权。具体说，写者到达后，已经在临界区内的读者继续读取直到结束，而后来的读者就不能进入临界区。等所有的读者离开临界区以后让写者先进去访问，然后等写者离开后再允许读者进入临界区。这所谓“写者优先读者-写者”问题。请用信号量和PV操作来描述这一组进程的工作过程。
问答题一个网络的拓扑结构如题47-a图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用链路状态路由算法求出从结点A到所有其他结点的最短路由，给出计算过程，最小路径图以及下一跳路由。