问答题一个Spooling系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据，进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位，这些数据块均存储在同一个磁盘上，因此，Spooling系统的数据块通信原语保证始终满足：I+O≤max。其中，max为磁盘容量(以该数据块为单位)，I为磁盘上输入数据块总数，O为磁盘上输出数据总数。 该Spooling系统运行时： (1)只要有输入数据，进程I终究会将它放入输入缓冲区； (2)只要输入缓冲区有数据块，进程P终究会输入、处理并产生结果数据写到输出缓冲区； (3)只要输出缓冲区有数据块，进程O终究会输出它。 请说明该Spooling系统在什么情况下死锁，并说明如何修正约束条件(1)避免死锁，同时仍允许输入数据块和输出数据块存储在同一个磁盘上。
问答题试编写一个非递归算法．实现求以二叉链表存储的二叉树中q结点的祖先。
问答题根据你的合并过程，描述n(n≥2)个不等长升序表的合并策略，并说明理由。
问答题一台模型机共有7条指令，主频25MHz，各指令的使用频度与CPI如下表所示，该机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器(R-R)二地址类型，16位字长指令为寄存器一存储器(R-M)二地址变址类型(地址码范围在—128～127之间)。 (1)计算该机的MIPS速率。 (2)计算操作码的平均码长。 (3)设计该机的两种指令格式，标出各字段位数并给出操作码编码。 (4)该机允许使用多少个可编址的通用寄存器，多少个变址寄存器? (5)如何计算存储器有效地址? 指令字长 使用频率 执行一条指令的周期数CPI I1(8位) 35% 1 I2(8位) 25% 2 I3(8位) 20% 2 I4(16位) 10% 2 I5(16位) 5% 1 I6(16位) 3% 2 I7(16位) 2% 2
问答题
问答题假设二叉树采用二叉链表存储结构，设计一个算法求其指定的某一层k(k＞1)的叶子结点个数，要求：
问答题总线的一次信息传送过程大致分哪几个阶段?若采用同步定时协议，画出读操作的同步时序图。
问答题一个长度为L(L≥1)的升序序列S，处在第个位置的数称为S的中位数。例如，若序列S1=(11，13，15，17，19)，则S1的中位数是15，两个序列的中位数是含它们所有元素在内的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则S1和S2的中位数是11。现有两个等长的升序序列A，B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：
问答题主机H通过快速以太网连接到某网络中，H与服务器S使用TCP通信时，在H上捕获的其中2个IP分组如题47-a表所示：题47-a表编号IP分组的前40字节内容(十六进制)1450000303a66400080063458c0a8055fc0a8055a041a00156d2a1c94000000007002ffff692800002450000301f4d400080064f71c0a8055ac0a8055f0015041a17292f2f6d2a1c957012ffff22bf0000请回答下列问题。(1)题47-a表中的IP分组中，是应用层哪种协议?主机H和服务器的IP地址分别是多少?(2)假如第三条报文是题47-b表中报文，请问这是正确的么?如果有错误，请给出正确的报文字段填充和原因，注意不考虑校验和字段。题47-b表3450000283a6740008006345fc0a8055ac0a8055f041a00156d2a1c9517292f2f5012ffff4f830000(3)第三条报文如果在网络中正确传输，需要填充的数据是多少?注：IP分组头和TCP段头结构分别如题47-a图、题47-b图所示。
问答题已知散列函数为H(key)=key%11，处理冲突的方法为二次探测法，探测的序列为：1，-1.4，-4，…，j2，-j2(j＜-m/2)：
当di＞O时，Hi=(H(key)+di)%m
当di＜0时，Hi=(H(key)+di+m)%m
散列表如下表所示，试回答下面的问题：
问答题已知长度为n(n＞1)的单链表，表头指针为L，结点结构由data和next两个域构成，其中data域为字符型。试设计一个在时间和空间两方面都尽可能高效的算法，判断该单链表是否中心对称(例如xyx、xxyyxx都是中心对称的)，要求：
问答题设某多道程序系统中有用户使用的内存1000M，打印机1台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计，采用最短剩余时间优先的进程调度算法，进程最短剩余时间相同时采用先来先服务的算法，进程调度时机选择在进程执行结束或新进程创建时，现有进程如下： 进程 创建时间 要求执行时间 要求内存 申请打印机 0 0 8 150M 1 1 4 4 300M 1 2 10 1 600M 0 3 11 20 200M 1 4 16 14 100M 0 假设系统优先分配内存低地址区域，且不允许移动，那么，求： (1)给出进程调度算法选中进程的次序，并说明理由。 (2)全部进程执行结束所用的时间是多少?
问答题同步传输方式和异步传输方式的特点各是什么?
问答题某路由器的IP地址是125.45.23.12，它在以太网上的物理地址为23-45-AB-4F-67-CD，它收到了一个分组，分组中的目的1P地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。(不包含硬件类型，协议类型，操作类型)(2)假定目的主机在以太网上的物理地址为AA-BB-A2-4F-67-CD，试给出目的主机发送的ARP响应分组中的各项目。(不包含硬件类型，协议类型，操作类型)(3)将问题1的结果封装成数据链路层的帧，试填充所有的字段。(4)将问题2的结果封装成数据链路层的帧，试填充所有的字段。注：ARP和以太网结构分别如题47-a，47-b图所示。
问答题若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?
问答题设一个没有设置快表的虚拟页式存储系统，页面大小为100字节。一个仅有460个字节的程序有下述内存访问序列(下标从0开始)：10、11、104、170、73、309、185、245、246、434、458、364，为该程序分配有2个可用页帧(Page frame)。试问：
问答题如果磁盘的每个磁道分成9个块，现有一文件有A、B、…、I共9个记录，每个记录的大小与块的大小相等，若磁盘转速为6000RPM，每读出一块后需要2.5ms的处理时间。若忽略其他辅助时间，且一开始磁头在即将要读A记录的位置，试问：
问答题什么是单重分组和双重分组跳跃进位链?一个按3，5，3，5分组的双重分组跳跃进位链(最低位为第0位)，试问大组中产生的是哪几位进位?与4，4，4，4分组的双重分组跳跃进位链相比，试问产生全部进位的时问是否一致?为什么?
问答题某公司网络拓扑图如下图所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1；R2的L0接口的IP地址是202.118.2.2，L1接口的IP地址是130.11.120.1，E0接口的IP地址是202.118.3.1；域名服务器的IP地址是202.118.3.2。R1和R2的路由表结构为：目的网络IP地址子网掩码下一跳IP地址接口
问答题下面有一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。
试判断这种方法是否正确。如果正确，请说明理由，如果不正确，举出反例(注：圈就是回路)。