问答题下图为某操作系统中文件系统的目录结构。请回答一下问题。
问答题任意给定1，2，…，n指定为一棵树的先根遍历序列；同时任意给定这n个数值(1，2，…，n)的一个排列p1，p2，…pn为这棵树的后根遍历序列。 (1)根据这样的先根遍历序列和后根遍历序列，是否都可以得到一棵树?如果能够，请简述理由(不要求形式化证明)。如果不能，请给出一个简单反例。 (2)如果能得到树，所得到的树是否唯一?如果能够，请简述理由(不要求形式化证明)。如果不能，请给出一个简单反例。
问答题某机的丰要部件如下图所示。(1)请补充各部件间的主要连接线，并注明数据流动方向。(2)拟出指令SUB(R1)，—(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作，源操作数地址和目的操作数地址分别在寄存器R1和R2中，目的操作数寻址方式为自减型寄存器间接寻址。其中：LA-A输入选择器，LB-B输入选择器，C、D-暂存器。
问答题说明你所设计算法的时间复杂度和空间复杂度。
问答题一个文件系统中有一个20MB大文件和一个20KB小文件，当分别采用连续分配、隐式链接分配方案时，每块大小为4096B，每块地址用4B表示，问：
问答题某微程序计算机具有12条微指令V1～V12，每条微指令所包含的微命令-信号如下表所示： 微指令 所包含的微指令 V1 a,d,e,n V2 h V3 a,h,j V4 a,b,c,d V5 a,e,f,j V6 a,b,k V7 a,f,g V8 a,d,e,i V9 a,b,k V10 a,h,l V11 a,b,k,m V12 a,e 表中，a～n分别对应14种不同的微命令，假设一条微命令长20位，其中操作控制字段为8位，控存容量为1K×20位。要求： (1)采用“不译法”与“分段直接编码法”混合设计此机微指令的操作控制字段格式，并为每个微命令分配编码； (2)采用“增量”与“下址字段”相结合的方式设计此机微指令的顺序控制字段格式，若要使微程序可在整个控存空间实现转移，则该微指令的顺序控制字段可直接表示出几个转移条件? (3)画出此机微指令的完整格式图，并标出每个具体字段所需的二进制位数。
问答题假设二叉树采用二叉链存储结构存储，设计一个算法，求出根结点到给定某结点之间的路径，要求：
问答题设x为真值，x
*
为绝对值，[-x
*
]
补
=[-x]
补
是否成立，为什么?
问答题一个系统采用段页式存储方式，有16位虚地址空间，每个进程包含两个段，并且一页大小为212字节。段表和页表如下表所示(所有的值为二进制，并且段长以页为单位)。下列哪些二进制虚地址会产生缺段中断或缺页中断?哪些二进制虚地址能转换为物理地址?如果可以转换，请写出物理地址。 (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
问答题已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。
问答题现有A，B两队人要过河，河上有船，但是每次只能乘坐4个人，并且每次乘客满员才能开船，到河对岸后空船返回。由于某种原因，过河时船上不能同时有三个A队人员、一个B队人员或者一个A队人员、三个B队人员的组合(即其他组合是安全的)。请编写程序，用PV操作正确解决A，B两队人过河的问题，并说明所设置的信号量及其初值。
问答题假设有12个初始归并段，其长度分别为85，68，62，9，18，60，20，3，6，8，44，30；现要进行4路外部归并排序，试画出表示归并过程的最佳归并树，并计算树的带权路径长度WPL。
问答题并发使得处理机的利用率得到提高，其主要原因是处理机与IO可以同时为多个进程服务，也即处理机与IO设备真正地并行。但是处理机的利用率提高并不是简单地将二个进程的处理机利用率相加，而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发，调度算法采用时间片轮转，时间片很小可以不计，忽略系统的开销，请分析以下问题： 假设每个进程的处理机的利用率为u1=20%。 (1)进程并发时，处理机的利用率与并发进程数的关系是什么? (2)假设某一计算机系统拥有20MB内存，以等额分区的方式实现了多道程序设计并运行，每个分区为4MB，其中操作系统占一个分区，请问此时处理机的利用率最大为多少? (3)假设为这个系统增加了16MB内存，系统有足够的并发度，此时处理机的利用率最大为多少?系统的吞吐量比(2)增加了多少? (4)在(3)的基础上继续增加16MB内存，此时处理机的利用率最大为多少?系统的吞吐量比(3)增加了多少?分析此时增加的内存是否合算?说明为什么。
问答题设有一系统在某时刻的资源分配情况如下表所列： 表 进程号 已分配资源 最大请求资源 剩余资源 P0 0，0，3，2 0，0，4，4 1，6，2，2 P1 1，0，0，0 2，7，5，0 P2 1，3，5，4 3，6，10，10 P3 0，3，3，2 0，9，8，4 P4 0，0，1，4 0，6，6，10 请回答：
问答题某机连接4台I／0设备，设备号分别为0、l、2、3。其中设备0的优先级最高，设备3的优先级最低。系统允许多重中断。 1．为了动态提高设备2和设备3的优先级，初始化时应如何设置对应的4位屏蔽字?请选择一个正确答案。2．若设备2的中断请求得到响应，CPU在设备2的中断服务程序中应如何设置新的屏蔽字?请选择一个正确答案。 设备号：0、1、2、3 屏蔽字：①0 0 0 0 ②0 0 1 1 ③1 1 0 0 ④1 1 1 1
问答题某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。
问答题某个页式存储管理系统，接收了一个大小一共7页的程序，其依次访问的页为：1，2，3，4，2，1，5，6，2，1，2，3，7。若分配给该程序的内存空间为4页，并一次预装入，请用先进先出(FIFO)调度算法和最近最少用(LRU)调度算法计算，程序执行时会产生多少次缺页中断?依次写出被淘汰的页号并计算缺页率。
问答题某请求页式存储管理，允许用户空间为32个页面(每页1KB)，主存为16KB。如果一个用户程序有10页长，且某时刻用户进程的页表如下表所示：
虚页号
物理页号
是否在TLB中
0
8
是
1
7
是
2
4
否
3
10
否
4
5
否
5
3
是
6
2
是
其他
not valid
问答题将关键字序列(7、8、11、18、9、14、30)散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组散列函数维：H(key)=(key×3)MOD T，处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。 问题：
问答题下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑，分取指周期、取第一操作数周期、取第二操作数周期、执行周期四个机器周期，每个机器周期有T0，T1，T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0，(R1)完成功能(R0)+((R1))→R0