1、计算机专业（基础综合）模拟试卷 81 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 根据使用频率为 5 个字符设计的赫夫曼编码不可能是( )。（A）000，001，010，011，1（B） 0000，0001，001，01，1（C） 000，001，01，10，11（D）00，100，101，110，1112 在分时操作系统中，进程通常采用( )算法。（A）先来先服务（B）最高优先级（C）时间片轮转（D）随机3 下面包含在 TCP 头中而不包含在 UDP 头中的信息是( )。（A）目标端口号 （B）序号 （
2、C）源端口号 （D）校验号4 n+1 位的定点小数，其补码表示范围是( ) 。（A）-1x1-2 -n（B）一 1x12 -n（C）一 1x12 -n（D）一 1x12 -n5 TCP 是采用 ( )来控制流量的。（A）设定拥塞窗I（B） TCP 首部中的接收窗口（C）设定拥塞阀值（D）通过标志位来通知6 CPU 在中断周期要完成的任务不包括( )。（A）保护断点（B）关中断（C）保护现场（D）向量地址送 PC7 驱动调度算法中，( ) 算法可能会随时改变移动臂的运动方向。（A）电梯调度（B）最短寻找时间优先（C）扫描（D）单向扫描8 关于 FTt的工作过程，下面说法错误的是( )。（A）在传
3、输数据前，FTP 服务器用 TCP 21 端口与客户端建立连接（B）建立连接后，FTP 服务器用 TCP 20 端口传输数据（C）数据传输结束后，FTP 服务器同时释放 21 和 20 端口（D）FTP 客户端的端口是动态分配的9 在常用的描述二叉排序树的存储结构中，关键字值最大的结点是( )。（A）左指针一定为空 （B）右指针一定为空（C）左右指针均为空 （D）左右指针均不为空10 已知 8 个数据元素为(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为( )。（A）4（B） 5（C） 6（D）711 在计算机体系结构中，cPU 内部
4、包括程序计数器 PC、存储器数据寄存器 MI)R、指令寄存器 IR 和存储器地址寄存器 MAR 等。若 CPU 要执行的指令为：MOV R0，#100(即将数值 100 传送到寄存器 R0 中)，则 CPU 首先要完成的操作是( )。（A）100R0 （B） 100MDR （C） PCMAR （D）PCIR12 中断向量表中保存的是( )。（A）被中断程序的返回地址 （B）中断服务程序入口地址（C）中断优先级 （D）中断源编码13 下列叙述正确的个数是( )。(1)m=2 的平衡 m 路查找树是 AVL 树(2)m=3 的平衡 m 路查找树是 23 树(3)m=2 的平衡 m 路查找树的叶结点
5、不一定在同一层(4)m 阶 B 一树的叶结点必须在同一层(5)m 阶 B 一树是平衡 m 路查找树(6)平衡 m 路查找树不一定是 B 一树（A）3（B） 4（C） 5（D）614 下列叙述中，不符合 m 阶 B-树定义要求的是( )。（A）根节点最多有 m 棵子树（B）所有叶结点都在同一层上（C）各结点内关键字均升序或降序排列（D）叶结点之间通过指针链接15 时间片轮转调度算法是为了( )。（A）多个终端能得到系统的及时响应 （B）使系统变得高效（C）优先级较高的进程得到及时响应 （D）需要 cPU 时间最少的进程最先做16 操作系统中为实现多道程序并发，对内存管理可以有多种方式，其中代价最
6、小的是( )。（A）分区管理（B）分页管理（C）分段管理（D）段页式管理17 磁臂驱动调度算法中，能够随时改变磁头运动方向的算法是( )。（A）电梯调度算法 （B）扫描算法（C）循环察看算法 （D）最短寻道距离优先算法18 如果二叉树 T2 是由有序树 T1 转换而来的二叉树，那么 T1 中结点的先序就是T2 中结点的( )。（A）先序（B）中序（C）后序（D）层次序19 某指令系统有 200 条指令，对操作码采用固定长度二进制编码，最少需要用( )位。（A）4（B） 8（C） 16（D）3220 下列哪些存储分配方案可能使系统抖动( )。I动态分区分配 简单页式 虚拟页式 简单段页式 V简单
7、段式虚拟段式（A）I 和 I（B） 和（C） V 和（D）和21 适合多道程序运行的存储管理方法中，存储保护主要是( )。（A）防止一个进程占用一个分区（B）防止非法访问磁盘文件（C）防止非法访问临界区（D）防止各道进程相互干扰22 在页式虚拟管理系统中，假定驻留集为 m 个页帧 (初始所有页帧均为空)，在长为 p 的引用串中具有 n 个不同页号(nm)，对于 FIFO、LRU 两种页面替换算法，其缺页中断的次数的范围分别为( )。（A）m ，p和n，p（B） m，n和n ，p（C） n，p 和m ，n（D）n ，p和n，p23 将有关二叉树的概念推广到三叉树，则一棵有 244 个结点的完全三
8、叉树的高度是( )。（A）4（B） 5（C） 6（D）724 设用数组 A1，n 作为两个栈 S1、S2 的共用存储空间，对任一个栈，只有当数组 A1，n 全满时才不作人栈操作，则分配这两个栈空间的最佳方案是( )。（A）S1 的栈底位置设为 1，S2 的栈底位置设为 n（B） S1 的栈底位置设为 n2，S2 的栈底位置设为 n2+1（C） S1 的栈底位置设为 1，S2 的栈底位置设为 n2（D）S1 的栈底位置设为 n2，S2 的栈底位置设为 125 下列说法中，正确的是( )。利用孩子兄弟链存储树，根结点的右指针指向最左孩子树的后根遍历序列等同于该树对应的二叉树的前序遍历序列若一个具有
9、 N 个顶点、K 条边的无向图是一个森林(且 NK)，则森林中必有 NK 棵树（A）仅、（B）仅 、（C）仅 （D）、26 两个网段在物理层进行互联时要求( )。（A）数据传输率和数据链路层协议都不相同（B）数据传输率和数据链路层协议都相同（C）数据传输率相同，数据链路层协议可不同（D）数据传输率可不同，数据链路层协议相同27 完全二叉树高度为 h，则最左边的叶子结点序号为( )。（A）2 h-1+1（B） 2h-1（C） 2h+11（D）2 h+128 某公司获得了一个 IP 地址段，在不分子网的情况下，最多可以容纳 65 534 个主机，那么这个地址属于( )。（A）A 类地址（B） B
10、类地址（C） C 类地址（D）D 类地址29 若 n+1 位数的二进制整数为 X=X，X 1，X n，X 移码数值的取值范围是( )。（A）-2nX2 n（B） -2n-1X2 n（C） -2n-1X2 n（D）-2 nX2 n-130 将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是( )。I父子关系兄弟关系u 的父结点与 v 的父结点是兄弟关系（A）只有（B） I 和（C） I 和（D）I、和31 4 片 74181ALU 和 1 片 74182CLA 器件相配合，具有( )进位传递功能。（A）串行进位（B）组内
11、并行进位，组间并行进位（C）组内并行进位，组间串行进位（D）组内串行进位，组间并行进位32 由于 CPU 内部的操作速度较快，而 CPU 访问一次主存所花的时间较长，因此机器周期通常用( ) 来规定。（A）主存中读取一个指令字的最短时间（B）主存中读取一个数据字的最长时间（C）主存中写入一个数据字的平均时间（D）主存中取一个数据字的平均时间33 某文件系统专用于影视多媒体应用，数据存放在光盘，则合理的文件物理存储格式应为( )。（A）顺序存储（B）链式存储（C）索引式存储（D）BST 树34 一个广域网信道的比特率是 4Kbps，传播延迟为 20 毫秒，若确保停一等协议至少 50的效率，那么帧
12、的大小至少是( )。（A）大于 160bit（B）大于 150bit（C）大于 140bit（D）大于 130bit35 下列选项中，用于提高 RAID 可靠性的措施有I磁盘镜像条带化奇偶校验增加 cache 机制（A）仅 I、（B）仅 I、（C）仅 I、和（D）仅、和36 用户在删除某文件的过程中，操作系统不可能执行的操作是（A）删除此文件所在的目录（B）删除与此文件关联的目录项（C）删除与此文件对应的文件控制块（D）释放与此文件关联的内存缓冲区37 中断处理和子程序凋用都需要压栈以保护现场，中断处理一定会保存而子程序凋用不需要保存其内容的是（A）程序计数器（B）程序状态字寄存器（C）通用数
13、据寄存器（D）通用地址寄存器38 以太网的 MAC 协议提供的是（A）无连接不可靠服务（B）无连接可靠服务（C）有连接不可靠服务（D）有连接可靠服务39 则需要上述规格的 ROM 芯片数和 RAM 芯片数分别是（ ）40 有两个并发执行的进程 P1 和 P2，共享初值为 1 的变量 x。p1 对 x 加 1，P2 对x 减 1。加 1 和减 1 操作的指令序列分别如下所示。加 1 操作减 1 操作loadR1，x取 x 到寄存器 R1 中 loadR2，xincR1decR2storex，R1将 R1 的内容存入 xstorex，R2 两个操作完成后，x 的值_ 。（A）可能为一 1 或 3（
14、B）只能为 1（C）可能为 0、1 或 2（D）可能为一 1、0、1 或 2二、综合应用题41-47 小题，共 70 分。41 假设路由器 R 存在两个接口，接口 R1 连接标准局域网，接口 R2 连接限制最大传输单元(MTU) 的局域网，现在一个 IP 数据包从接口 R1 转发到接口 R2，从 R2链路上截获两个数据包的 IP 报头，如表 13 所列，请回答如下问题：(1)接口R2 的最大传输单元是多少?(2) 所传输的 IP 数据包的数据大小是多少?分为了几个 IP分片?(3)根据截获的 IP 报头，请填充没有截获的数据报，注意不包含头部校验和。注：IP 分组头结构分别如图 13 所示。4
15、2 在某一个单处理机的系统中，外接了一台打印机，一台输入设备。当前在系统中有二个进程 P0、P1 已经就绪，进程 P0 首先获得处理机运行，调度算法为先来先服务，进程 P0、P1 的运行要求是这样的：P0：计算 100ms，打印信息 200ms，继续计算 100ms，打印信息 200ms，结束。P1：计算 100ms，输入数据 150ms，继续计算 200ms，结束。请用甘特图画出它们的运行轨迹，并说明：进程 PO、P1 在运行时有无等待? 若有，请指出时间区间。计算处理机的利用率。43 某微机的寻址范围为 64 KB，其存储器选择器信号为 M，接有 8 片 8 KB 的存储器，试完成下列问题
16、。(1)画出选片译码逻辑图。(2)写出每片 RAM 的寻址范围。(3)如果运行时发现不论往哪片存储器存放 8KB 数据，以 4000H 起始地址的存储芯片都有与之相同的数据，分析故障原因。(4)如果运行时发现以 0000H 为起始地址的一片存储芯片不能读写，分析故障原因。(5)若发现译码器中的地址线 A13与 CPO 断线，并搭接到低电平，问后果如何?(6)如果发现只能对第 14 片 RAM 进行读写，试分析故障原因。44 处理一次缺页的平均时间为 108 ns(已含更新 TLB 和页表的时间)，进程的驻留集大小固定为 2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设：TLB 初始为
17、空；地址转换时先访问 TLB，若 TLB 未命中，再访问页表(忽略访问页表之后的 TLB 更新时间)； 有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问： (1)依次访问上述三个虚地址，各需多少时间?给出计算过程。 (2)基于上述访问序列，虚地址 1565H 的物理地址是多少? 请说明理由。45 已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序 (key1key2keyn)
18、。(2)关键字自大到小逆序 (key1key2keyn)。(3)奇数关键字顺序有序，偶数关键字顺序有序(key1key3 ，key2key4)。(4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key1key2 keym，keym+1keym+2)keyn，m 为中间位置)。46 某计算机字长为 16 位，采用 16 位定长指令字结构，部分数据通路结构如图 A-2 所示，图中所有控制信号为 1 时表示有效、为 O 时表示无效。例如，控制信号MDRinE 为 1 表示允许数据从 DB 打入 MDR，MDRin 为 l 表示允许数据从内总线打入 MDR。假设 MAR 的输出一直处于
19、使能状态。加法指令“ADD(R1)，R0”的功能为(R0)+(R1)一(R1)，即将 R0 中的数据与 R1 的内容所指主存单元的数据相加，并将结果送入 R1 的内容所指主存单元中保存。表 A-1 给出了上述指令取指和译码阶段每个节拍(时钟周期) 的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。46 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。47 在连续、链式、索引三种文件的数据块组织方式中，哪种更合适?要求说明理由。为定位文件数据块，需要 FCB 中设计哪些相关描述字段?48 为快速
20、找到文件，对于 FCB，是集中存储好，还是与对应的文件数据块连续存储好?要求说明理由。计算机专业（基础综合）模拟试卷 81 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 赫夫曼树中只有度为 O 或 2 的结点，由 D 选项可以画出对应的二叉树，如图 1-7 所示。 由赫夫曼树的性质可知，树中不应该含度为 1 的结点，因此D 选项不可能。2 【正确答案】 C【试题解析】 分时操作系统将系统处理机时间与内存空间进行时间上的分割，每个时间段称为一个时间片，每个用户依次轮流使用时间片。由
21、于时间间隔很短，每个用户的感觉就像他独占计算机一样。3 【正确答案】 B【试题解析】 本题主要考查 TCP 报文段和 UDP 报文段结构，TCP 数据报和UDP 数据报都包含目标端口、源端口、校验号。但是由于 UDP 是不可靠的传输，故数据报不需要编号，所以不会有序号这一字段，而 TCP 是可靠的传输，故需要设置序号这一字段，答案是 B。归纳总结 注意 UDP 数据报有两个字段：数据字段和首部字段。首部字段有 8 个字节，由 4 个字段组成，每个字段都是两个字节(牢记)：(1)源端口，即源端口号(端口号用 16bit 来表示，故需要 2 字节长度)。(2)目的端口，即目的端口号。(3)长度，即
22、 UDP 用户数据报的长度 (尽管有 2 字节来描述 UDP 数据报的长度，但是一般来说 UDP 协议限制其应用程序数据为 512 字节或更小)。(4)检验和，即检测 UDP 用户数据报在传输中是否有错(既检验首部又检验数据部分)。而 TCP 报文段也分为首部和数据两部分，TCP 的全部功能也都体现在首部的各个字段中，其中源端口和目的端口的意义和 UDP 是一致的。4 【正确答案】 A【试题解析】 各种编码下的数值范围总结如表 26 所示。5 【正确答案】 B【试题解析】 TCP 首部中的接收窗口是用来标识接收方的缓冲能力的，避免快速的发送方淹没慢速的接收方。6 【正确答案】 C【试题解析】
23、保护现场包括保护断点和保护 CPU 内其他相关寄存器的内容，其中包括断点的任务在中断周期由中断隐指令完成，保护其他寄存器内容的任务由中断服务程序完成，而不是在中断周期由中断隐指令完成，选 C。7 【正确答案】 B【试题解析】 最短寻找时间优先可能根据新的请求做出方向改变。8 【正确答案】 C【试题解析】 本题考查 FTP 的工作原理，FTP 使用两条 TCP 连接完成文件传输，一条是控制连接，另一条是数据连接。平时 FTP 服务器总在端口 21 上等待客户的连接请求，当用户需要传输文件时，FTP 客户与 FTP 服务器的端口 21 建立一个控制连接，用来传送客户的命令和服务器的响应。当客户在控
24、制连接上发出数据传输命令时，服务器在另一个端口上主动与客户建立一条数据连接，然后在数据连接上传输文件。当一个文件传输结束时，关闭数据连接。如果用户请求另一个文件的传输，则服务器和客户再建立一个数据连接，用于传输新的文件。虽然数据连接频繁地建立和释放，但控制连接在整个会话期间一直保持，直到客户与服务器通信结束为止，因此答案为 C。9 【正确答案】 B【试题解析】 在二叉排序树的存储结构中，每个结点由三部分构成，其中左(或右)指针指向比结点的关键值小(或大)的结点。关键字值最大的结点位于二叉排序树的最右位置上，因此它的右指针一定为空。10 【正确答案】 B【试题解析】 根据二叉排序树插入结点算法，
25、将上述 8 个数据元素按照依次插入结点的方法构造出一棵二叉排序树后，该树的最大层次为 5，故该树的深度为 5。11 【正确答案】 C【试题解析】 无论运行什么类型的指令，CPU 首先需要取指令，取指令阶段的第一个操作就是将指令地址(程序计数器 PC 中的内容)送往存储器地址寄存器。归纳总结 取指周期完成的微操作序列是公共的操作，与具体指令无关，取指公操作如下：(1)将程序计数器 PC 中的内容送至存储器地址寄存器 MAR，记作(PC)MAR；(2)向主存发读命令，记作 Read；(3)从主存中取出的指令送到存储器数据寄存：器 MDR，记作 M(MAR)MDR；(4)将 MDR 的内容送至指令寄
26、存器 IR 中，记作(MDR)IR；(5)将 PC 的内容递增，为取下一条指令做好准备，记作(PC)1PC 。解题技巧 题干中虽然给出了一条具体的指令“MOV RO，#100”，实际上 CPU 首先要完成的操作是取指令，与具体指令是没有关系的。12 【正确答案】 B【试题解析】 中断向量表是用来存放中断服务程序的人口地址的。归纳总结 许多计算机中在主存的特定位置设置有中断向量表，在中断向量表的相关单元中存放着各级中断服务程序的入口地址。中断源给出的向量地址是中断向量表的指针，也就是中断服务程序入口地址的地址。由向量地址指向一个中断向量表，从中断向量表的相应单元中再取出中断服务程序的入口地址。1
27、3 【正确答案】 D【试题解析】 参见 B-树定义。14 【正确答案】 D15 【正确答案】 A【试题解析】 本题考查进程的时间片轮转调度算法。时间片轮转的主要目的是使得多个交互的用户能够及时得到响应，使得用户以为“独占”计算机在使用。因此它并没有偏好，也不会对特殊进程特殊服务。时间片轮转增加了系统开销，所以不会使得系统高效运转，吞吐量和周转时间均不如批处理优。但是其较快速的响应时间使得用户能够与计算机进行交互，改善了人机环境，满足用户需求。16 【正确答案】 A【试题解析】 本题考查实现各种存储管理的方法。为实现多道出现并发，系统必须将多个程序调入内存，让多个进程竞争 CPU 和外设，使得计
28、算机能高效地运转。多个程序调入内存会存在越界，溢出等多种问题。为解决这些问题，存储管理采用了分区法，分页法，分段法和段页式等多种技术，而实现分页、分段和段页式存储管理都需要特殊的硬件支持(例如带地址加法器的 CPU 等)，因而代价较高。分区存储是实现多道程序并发的最简单易行而又代价最低的方法，这种方法特别适合嵌入式系统或移动设备的操作系统中实现多道并发。17 【正确答案】 D【试题解析】 本题考查磁臂调度算法。了解每一种磁臂调度算法后对该题就应该有比较清晰的认识，例如，最短寻道时间优先算法是找离得最近的磁道去服务，那么它随时会改变方向；而电梯调度算法在一次单向运动过程中服务所有经过的磁道的请求
29、，直到该方向没有磁道需要访问了才改变方向，到达另一个方向的最远的需要服务的磁道后再返回；扫描调度算法非常类似电梯调度算法，区别是扫描算法不管有没有用户请求访问磁道，均会移到磁道两端的终点。循环察看是电梯调度算法的改进，它只进行单向服务，到最远端的服务磁道结束后立即返回另一端的第一个需要服务的磁道，返程途中不寻道，以保证对不同分布磁道的访问具有公平性。18 【正确答案】 A【试题解析】 一般树中一个结点的孩子是无序的，所谓有序树是指树中任一结点的孩子是有序的。由树转换成二叉树的过程可知本题答案为 A。19 【正确答案】 B【试题解析】 因 128=272002 8=256，故采用定长操作码时，至
30、少需 8 位。20 【正确答案】 D【试题解析】 “抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其它页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上。对换的信息量过大，内存容量不足不是引起系统抖动现象的原因，而选择的置换算法不当才是引起抖动的根本原因，例如，先进先出算法就可能会产生抖动现象。本题中只有虚拟页式和虚拟段式才存在换入换出的操作，简单页式和简单段式因已经全部将程序调入内存，因此不需要置换，也就没有了抖动的现象。故正确答案为 D。21 【正确答案】 D【试题解析】 本题考查存储保护的目的。在多道程序设计的环境中，要保证各道进程只能在自己的存储区中
31、活动，不能对别的程序产生干扰和破坏，尤其不能破坏操作系统的核心区。因此，必须对存储的信息采取各种保护措施，其目的是防止各道进程相互之间的干扰，甚至破坏。一个分区一般只分给一个进程独占使用，即使有空闲的空间，若是内碎片则一般也不能分给其它进程使用。磁盘和临界区访问不属于存储管理的范围。22 【正确答案】 D【试题解析】 缺页中断的原因是当前访问的页不在内存中，需将该页调入主存。此时不管主存是否已满(已满则先调出一页)，都要发生一次缺页中断。即无论怎么安排，n 个不同的页号在首次进入主存时必须要发生一次缺页中断，总共发生 n 次，这就是缺页中断的下限。虽然不同页号数位 n，小于或等于总长度 p(访
32、问串可能会有一些页重复出现)，但驻留集 m=05，解出 n=160；故选 A。35 【正确答案】 B【试题解析】 能够提高 RAID 可靠性的措施主要是对磁盘进行镜像处理和进行奇偶校验。其余选项不符合条件。36 【正确答案】 A【试题解析】 删除文件不需要删除文件所在的目录，而文件的关联目录项和文件控制块需要随着文件一同删除，同时释放文件的关联缓冲区。37 【正确答案】 B【试题解析】 中断处理一定会保存程序状态字寄存器中的内容，而子程序调用不需要保存其内容。38 【正确答案】 A【试题解析】 以太网的 MAC 提供的是无连接的不可靠的服务。39 【正确答案】 D40 【正确答案】 C【试题解
33、析】 考查进程的并发执行。将 P1 中 3 条语句变为 1，2，3，P2 中 3 条语句编为 4，5，6。则依次执行 1，2，3，4，5 得结果 1，依次执行1，2，4，5，6，3 得结果 2，执行 4，5，1，2，3，6 得结果 0。结果一 1 不可能得出。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 (1)接口：R2 的最大传输单元是 100 字节。(2)所传输的 IP 数据包大小是 308 字节，分为了 4 个 IP 分片。(3)没有截获的数据包是中间的两个 IP 分片：第二个分片：45 00 00 64 00 1e 20 0a ff 01 18 1d c0 a8 0
34、1 01 c0 a8 01 02第三个分片：45 00 00 64 00 1e 20 14 ff 01 18 13 c0 a8 01 01 c0 a8 01 0242 【正确答案】 根据题意，画出甘特图如下：从运行的时序甘特图上可以看出：处理机在 200ms 到 300ms 之间是空闲的。因此，处理机的利用率可以计算出为：(200300)600833。进程 P0 运行过程中无等待现象，进程 P1有等待现象，等待区间为 350400ms 之间。【试题解析】 本题考查进程调度的过程。解决这类题目的关键在于画出进程运行的时序图，若用条形来表示这种时序图就称为甘特图，然后再对其进行分析。绘图和分析过程
35、中要注意题目适用的调度算法，先来先服务最简单，按先来后到的次序进行调度，被调度的进程一般会占有处理机运行直到自己主动放弃；短进程优先算法在选取调度的进程时需要知道进程的预计执行时间，根据进程表里填写的进程预计执行时间，选取最短的进程调度其运行；高优先级优先的调度算法是根据进程表内赋予的优先级来调度，当然，优先级的确定可以有各种方法，可以在创建时确定，也可以根据程序的紧急程度确定，还可以根据收费多少确定，所以优先级的确定有许多灵活性，现行大部分操作系统均会采用高优先级优先的调度算法；时间片轮转的调度算法是由硬件时钟确定每一个进程占用处理机的时间的，进程按先来先服务排队，调度器调度进程队列中最先的
36、进程运行，若分配的时间未到进程就主动放弃处理机，则会引起下一次调度，若分配的时间到，则不管进程是否运行完成，必须立即强制地出让处理机。在以上描述的各种调度算法既可以单独使用，也可以组合使用。不管采用什么算法，能否抢先是另一个调度的非常重要的因素，为适应不同用户的需求，也为改善计算机的性能，现代许多操作系统均采用抢先式调度算法，抢先式调度不能单独实施，一定是与上述各种调度算法相结合。处理机的调度相对较复杂，而 IO 的调度就简单了，为保证安全，一般 IO 设备是不能抢夺的，一旦分配，则一定是使用到进程主动放弃。43 【正确答案】 (1)选片译码逻辑如图 75 所示。 (2)8 片RAM 的寻址范
37、围分别是：0000H1 FFFH、2000H3FFFH 、4000 H5FFFH、 6000H7FFFH、8000H9FFFH、A000H BFFFH 、COOOHDFFFH 和 EOOOHFFFFH。 (3)说明译码器有误， 输出始终为低。因该输出接至第3 片 RAM 的 端，该片对应的地址范围是 4000H5FFFH，故不论往哪片 RAM存放 8K 数据，该存储芯片始终被选中，所以都有与之相同的数据。 (4)说明 Y0 输出始终为高。因 RAM 的片选信号是低电平有效，故用 Y0 作片选信号的存储芯片(对应 0000H1FFFH 地址范围 )不能读写，而其他芯片可以读写。 (5) 若发现
38、A13 与CPU 断线，并搭接到低电平的故障，则 信号均不可能输出 0，故第2、4、6、8 片 RAM 始终不被选中。 (6)说明译码器的 C 输入端始终为低，可以检查一下 A15 是否搭接到低电平上。44 【正确答案】 (1)根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为 4 KB，即 212，则得到页内位移占虚地址的低 12位，页号占剩余高位。可得三个虚地址的页号 P 如下(十六进制的一位数字转换成4 位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号)：2362H：P=2，访问快表 10 ns，因初始为空，访问页表 100 ns 得到页框号，
39、合成物理地址后访问主存 100 ns，共计 10 ns+100 ns+100 ns=210 ns。1565H：P=1 ，访问快表 10 ns，落空，访问页表 100 ns 落空，进行缺页中断处理 108 ns，合成物理地址后访问主存 100 ns，共计 10 ns+100 ns+108 ns+100 ns318 ns。25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费 10 ns 便可合成物理地址，访问主存 100 ns，共计 10 ns+100 ns=110 ns。(2)当访问虚地址 1565H 时，产生缺页中断，合法驻留集为 2，必须从页表中淘汰一个页面，根据题目的置换
40、算法，应淘汰 0 号页面，因此 1565H 的对应页框号为101H。由此可得 1565H 的物理地址为 101565H。45 【正确答案】 依题意，取各种情况下的比较次数即为最少比较次数。(1)在这种情况下，插入第 i 个(2in)元素的比较次数为 1，因此，总的比较次数为 1+1+1+1=n-1。(2)在这种情况下，插入第 i 个(2in)元素的比较次数为 i，因此，总的比较次数为 2+3+4+n=(n-1)(n+2)2。(3)在这种情况下，比较次数最少的情况是所有纪录关键字均按升序排列，这时，总的比较次数为 n-1。(4)在这种情况下，后半部分元素的关键字均大于前半部分元素的关键字时需要比
41、较次数最少，此时前半部分的比较次数=m-1 ，后半部分的比较次数 =(n-m-1)*(n-m+2)2，因此，总的比较次数为 m-1+(n-m-1)(n-m+2)2=(n-2)(n+8)8(假设 n偶数，m=n 2)。46 【正确答案】 一条指令的执行过程通常由取指、译码和执行 3 个步骤完成，本题中取指用 3 个节拍、译码用 1 个节拍，执行加法运算并把结果写入主存如何完成呢?包括划分执行步骤、确定完成的功能、要提供的控制信号，这是本题要测试的内容。为回答这个问题，首先要看清图 A-2 中给出的部件组成情况和信息传送的路径。要完成的功能是(R0)+(R1)(R1)，从图 A-2 中看到：1)R
42、0、Rl 都有送自己内容到内总线的路径，控制信号分别是 R00ut 和 Rlout。2)ALu 加运算，2 个数据由工作寄存器 A 和内总线提供，控制信号是 Add；A 只接收内总线的内容，控制信号是 Ain；结果需存 AC，控制信号是 ACin：AC 的内容可送内总线，控制信号是 ACout。3)PC 可接收内总线的内容，还可增 1，控制信号是 PCin 和 PC+1，PC的内容可送内总线，控制信号是 PCout。4)指令寄存器 IR 可接收内总线的内容，控制信号是 IRin。5)读写存储器时，地址由 MAR 经 AB 提供，MAR 只接收总线上的信息，控制信号是 MARin。6)读存储器，
43、提供读命令 MemR，并通过 DB送入 MDR，控制信号是 MDRinE；MDR 的内容可送入总线，控制信号是MDRout。7)写存储器，提供写命令 MemW，数据由 MDR 通过 DB 送到存储器的数据引脚，控制信号是 MDRoute.然后是划分执行步骤、确定每步完成的功能、需要提供的控制信号。这是由指令应完成的功能、计算机硬件的实际组成情况和信息传送的可用路径共同决定的，基本原则是步骤越少越好。硬件电路要能支持，可以有多种方案，解题时应参照以给出的答题格式，即取指和译码阶段的表 A-1 的内容，但不必把表已有的内容再抄一遍。划分指令执行步骤、确定每步完成的功能、给出需要提供的控制信号：请注
44、意，(R0)+(R1)表示：R0 寄存器的内容与 R1 作地址从主存中读出来的数据完成加法运算；而一(R1)表示把 R1 的内容作为主存储器的地址完成写主存操作。为防止出现误解，题中还特地对此作了文字说明。这条指令的功能是先到主存储器取一个数，之后运算，再将结果写回主存储器。1)执行相加运算，需把存储器中的数据读出，为此首先送地址，将 R1 的内容送 MAR，控制信号是 Rlout、MARin 。 2)启动读主存操作，读出的内容送入 MDR，控制信号是MemR、MDRinE。还可同时把 R0 的内容经内总线送入 A，用到的控制信号是R00ut、 Ain。3)执行加法运算，即 A 的内容与 MD
45、R 的内容相加，结果保存到AC，控制信号是 MDRout、Add、Acin。4)要把 AC 的内容写入主存，由于 R1 的内容已经在 MAR 中，地址已经有了，但需要把写入的数据(已经在 AC 中)经内总线送入 MDR，控制信号是 ACout、MDRin 。5)给 m 写主存的命令，把 MDR 的内容经 DB 送存储器的数据线引脚，执行写操作，控制信号是 MDRoutE、MemW 。这几个步骤是有先后次序的，前面的完成了，下一步才可以执行，也保证了不会产生硬件线路的冲突。请注意，使用最为频繁的是内总线，它在任何时刻只能接收一个输入数据，并且向内总线发送信息的电路只能以三态门器件连接到内总线，5
46、 个向内总线发送信息的控制信号(ACout、PCout、R00ut、R10ut 、MDRout) 最多只能有一个为 1，其他 4 个必须全为 0，或者 5 个全为 0。仔细看一下，发现可以把第2)个步骤的操作划分到两个步骤中完成。一个步骤中安排 MDR 接收从存储器中读出的内容，到另外一个步骤实现 R0 的内容送入 A，这多用了一个操作步骤，指令的执行速度会变慢。有些解题者在写存储器之前，还会再执行一次把 R1 的内容送MAR，尽管无此必要，但不属于原理上的错误。当然还可以有其他的设计结果解题时这些叙述内容不必写出来(这里写出这些内容是希望帮助大家领会本题要测试的知识点和指令的执行过程)，直接
47、按照已经给出的表格的形式、按照提供的填写办法把设计的表格及其内容填好就可以了。请注意，题目表格内容(告诉你答题的格式和答题内容的表达方式)与你答题的表格内容合在一起才是这条指令的完整的执行过程，千万不要产生任何错觉。参考答案一见表 A-4。“A 一(R0)” 也可在 C7：“AC 一(MDR)+(A)”之前单列的一个时钟周期内执行。参考答案二见表 A-5。47 【正确答案】 在磁盘中连续存放(采取连续结构)，磁盘寻道时间更短，文件随机访问效率更高；在 FCB 中加入的字段为： 或者。48 【正确答案】 将所有的 FCB 集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问 FCB 对应的块，可减少磁头移动和磁盘 IO 访问次数。
