问答题现有一个解决无向连通图的最小生成树的一种方法如下： 将图中所有边按权重从大到小排序为(e1，e2，…，em)； i=1； while(所剩边数＞=顶点数) 从图中删去ei； 若图不再连通，则恢复ei； i=i+1： 请问上述方法能否求得原图的最小生成树?若该方法可行，请证明之；否则请举例说明。
问答题某请求分页系统的局部页面置换策略如下： 系统从0时刻开始扫描，每隔36个时间滴答扫描一轮工作集(扫描时间忽略不计)，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的工作集中；否则，从空闲页框链表头部取出一个页框进行分配。 假设不考虑其他进程的影响和系统开销，初始时进程工作集为空。目前系统空闲页框链表中页框号依次为198、156、188、230。进程P依次访问的＜虚拟页号，访问时刻＞是：＜1，1＞、＜3，20＞、＜0，32＞、＜0，65＞、＜1，73＞、＜0，90＞、＜2，104＞。请回答下列问题。
问答题一台模型机共有7条指令，主频25MHz，各指令的使用频度与CPI如下表所列，该机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器(R-R)二地址类型，16位字长指令为寄存器-存储器(R-M)二地址变址类型(地址码范围在-128～127之间)。 表 指令字长 使用频率 执行一条指令的周期数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
问答题一个系统具有150存储单元，在T0时刻系统按下表所示分配给3个进程。 进程 最大需求 已分配 P1 70 25 P2 60 40 P3 60 45 对下列请求应用银行家算法分别分析判定是否安全? (1)第四个进程P4到达，最大需求60个存储单元，当前请求分配25个单元。 (2)第四个进程P4到达，最大需求50个存储单元，当前请求分配35个单元。 如果是安全的，请给出一个可能的安全序列；如果是不安全的，请说明理由。
问答题某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。 (1)画出选片译码逻辑图。 (2)写出每片RAM的寻址范围。 (3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存储芯片都有与之相同的数据，分析故障原因。 (4)如果运行时发现以0000H为起始地址的一片存储芯片不能读写，分析故障原因。 (5)若发现译码器中的地址线A13与CPU断线，并搭接到低电平的故障，问后果如何? (6)如果发现只能对第1～4片RAM进行读写，试分析故障原因。
问答题设某计算机有四级中断A、B、C、D，其硬件排队优先级次序为A>B>c>D。下表列出的是执行每级中断处理程序所需的时间：中断处理程序 所需时间 A 5us B 15us C 3us D 12us如果我们想以执行中断处理程序的时间作为确定中断优先级的尺度：时间越短优先级越高。(1)请指出如何为各级中断处理程序设置屏蔽码。(2)如果A、B、C、D分别在6us、8us、10us、Ous时刻发出中断请求，请画出CPU执行中断处理程序的序列。(3)基于上题，请计算上述四个中断处理程序的平均执行时间。
问答题设机器数字长为8位(含1位符号位)，设A=-87，B=53，计算[A±B]
补
，并还原成真值。
问答题一个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)全部进程执行结束所用的时间是多少?
问答题同步传输方式和异步传输方式的特点各是什么?