已选分类
工学计算机科学与技术
试题题型
问答题在实现文件系统时，一般为加快文件目录的检索速度，可利用“文件控制块部分装入”的方法。假设目录文件(即文件控制块)存放在磁盘上，磁盘的每个盘块为512B，每个目录项占128B，其中文件名占11B。为提高检索速度，通常将目录项分解成两部分，第一部分(包括文件名和文件内部号)占16B，第二部分(包括文件内部号和文件其他描述信息)占122B。假设某一目录共有254个目录项(文件控制块)，试分别给出前、后二种方法查找该目录文件某一目录项的平均访问磁盘次数。
问答题一个文件系统中有一个20MB大文件和一个20KB小文件，当分别采用连续分配、隐式链接分配方案时，每块大小为4096B，每块地址用4B表示，问：
问答题
问答题在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制块分解法”。假设目录文件存放在磁盘上，每个盘块有512字节。文件控制块占64字节，其中文件名占8个字节。通常将文件控制块分解成两部分，第一部分占16字节(包括文件名和文件内部号)，第二部分占48字节(包括文件内部号和文件其他描述信息)。
问答题某机的丰要部件如下图所示。(1)请补充各部件间的主要连接线，并注明数据流动方向。(2)拟出指令SUB(R1)，—(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作，源操作数地址和目的操作数地址分别在寄存器R1和R2中，目的操作数寻址方式为自减型寄存器间接寻址。其中：LA-A输入选择器，LB-B输入选择器，C、D-暂存器。
问答题某微程序计算机具有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)画出此机微指令的完整格式图，并标出每个具体字段所需的二进制位数。
问答题大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小为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)为例加以说明。
问答题假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上个结点的值。
问答题实现一个经典的“读者-写者”算法时，若当前临界区中有读者访问，写者再来时必须在临界区外面等候，如果其后读者源源不断地到达，按策略他们均可以进入临界区，始终保持临界区中有读者访问，那么写者可能长时间不能进入临界区而形成饥饿。为解决此类问题，我们修改访问策略，要求当写者到达时，写者具有优先权。具体说，写者到达后，已经在临界区内的读者继续读取直到结束，而后来的读者就不能进入临界区。等所有的读者离开临界区以后让写者先进去访问，然后等写者离开后再允许读者进入临界区。这所谓“写者优先读者-写者”问题。请用信号量和PV操作来描述这一组进程的工作过程。
问答题一个网络的拓扑结构如题47-a图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用链路状态路由算法求出从结点A到所有其他结点的最短路由，给出计算过程，最小路径图以及下一跳路由。
问答题任意给定1，2，…，n指定为一棵树的先根遍历序列；同时任意给定这n个数值(1，2，…，n)的一个排列p1，p2，…pn为这棵树的后根遍历序列。 (1)根据这样的先根遍历序列和后根遍历序列，是否都可以得到一棵树?如果能够，请简述理由(不要求形式化证明)。如果不能，请给出一个简单反例。 (2)如果能得到树，所得到的树是否唯一?如果能够，请简述理由(不要求形式化证明)。如果不能，请给出一个简单反例。
问答题设x为真值，x
*
为绝对值，[-x
*
]
补
=[-x]
补
是否成立，为什么?
问答题已知数组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
，写出各中断源的屏蔽字。
问答题在下列情况下，计算传送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个分组。
问答题下图为某操作系统中文件系统的目录结构。请回答一下问题。
问答题说明你所设计算法的时间复杂度和空间复杂度。
问答题假设二叉树采用二叉链存储结构存储，设计一个算法，求出根结点到给定某结点之间的路径，要求：