模拟试题2
(总分：150.00，做题时间：150分钟)
一、单项选择题(总题数：40，分数：80.00)
1.循环链表的主要优点是（ ）。 A.不再需要头指针了
B.已知某个结点的位置后， 能很容易找到它的直接前驱结点 C.在进行删除操作后， 能保证链表不断开 D.从表中任一结点出发都能遍历整个链表 √
头指针不能省略， 因为没有头指针就没有办法引用该链表了。 循环链表还是单链表， 要找到直接前驱结点， 必须至少循环遍历整个链表一次才行。 无论链表是不是循环的， 都能保证在删除时链表的不断开。 选项D 是正确选项， 因为循环链表首尾相接， 形成一个环， 从任何一个结点开始都能遍历整个链表。
2.在一个单链表中， 已知指针 p 指向其中的某个结点， 若在该结点前插入一个由指针 s 指向的结点， 则需执行（ ）。
A.s->next＝p->next； p->next＝ s； B.p->next＝s； s->next＝p；
C.r＝p->next； p->next＝s； s->next＝r； D.仅靠已知条件无法实现 √
由于单链表的单向性， 在某个结点前插入结点时， 必须有一个指针指向该结点的前驱结点。 所以仅靠此题己知条件无法实现所要求的插入。
3.在一个具有 n 个单元的顺序栈中， 假定以高端（即第 n-1 单元） 作为栈底， 以 top 为栈顶指针， 则当作出栈运算时， top 变化为（ ）。 A.top 不变 B.top＝0 C.top-- D.top++ √
注意此题中顺序栈的栈底是在高端， 出栈时 top 指针应当加 1。
4.假定在一棵二叉树中， 双分支结点数为 15 个， 单分支结点数为 30 个， 则叶子结点数为（ ） 个。 A.15 B.16 √ C.17 D.47
根据二叉树的性质， 叶子结点的个数取决于双分支结点数， 与单分支结点数无关。 对任何一棵二叉树 T， 如果其叶子结点数为 n0 ， 双分支结点数为 n2 ， 则 n0 = n2 + 1。
5.某非空二叉树（结点个数大于 1） 的先序序列和后序序列正好相反， 则该二叉树一定是（ ）。 A.完全二叉树
B.只有两个结点的二叉树 C.二叉排序树
D.任一结点只有一个孩子结点 √
6.若对 n 阶对称矩阵 A[1…n， 1…n]依次存放于一维数组 B[1…n（n+1） ／ 2]中， 则在 B 中确定 A ij （i＜j） 的位置 k 的关系为（ ）。 A.i×（i-1） ／ 2+j B.j×（j-1） ／ 2+i √ C.i×（i+1） ／ 2+j D.j×（j+1） ／ 2+i
只考虑 A 的下三角阵， 依照行序为主序是指先存完第 i 行的元素， 才能存储第 i+1 行的元素。 A ij（i＜j） 在第 i 行第 j 列， 因为 A 是对称的， A ij （i＜j） 也可看作是 A ji ， 第 j 行共有 j 个元素， 从第 1 行到第 j-1行共有 j×（j-1） ／ 2 个元素， 再加上第 j 行的 i 个元素就是 A ij 在 B[1…n（n+1） ／ 2]中的位置， 即 k＝ j×（j-1）／ 2+i。 7.在图中判断两个顶点是否相邻， 采用（ ） 存储结构效率最高。 A.邻接矩阵 √ B.邻接表 C.十字链表 D.邻接多重表
因为在邻接矩阵中， 可以利用数组的随机存储特性直接判断两个顶点是否相邻。
8.若采用链地址法构造哈希表， 哈希函数为 H（key） ＝key MOD 15， 则需（ ） 个链表。 A.17 B.15 √ C.13 D.任意
在链地址法中， 每个链表对应一个哈希地址。 本题有 15 个哈希值， 所以需要 15 个链表。 9.有一个长度为 12 的有序表， 按二分查找法对该表进行查找， 在表内各元素等概率情况下， 查找成功所需的平均比较次数为（ ）。 A.37／ 12 √ B.35／ 12 C.39／ 12 D.43／ 12
用二分法查找有序表， 相当于在一个完全二叉树中查找元素， 查找成功的比较次数相当于到查找结点的路径长度加 1。 12 个结点的完全二叉树前三层是满二叉树， 第四层有 5 个结点。 整棵树的查找比较次数总和为：1×1+2×2+4×3+5×4＝37。 在 12 个元素中， 查找某个元素的概率是 1/12。 因此， 查找成功所需的平均比较次数为 37／ 12。
10.若对 n 个元素进行堆排序， 则在初始建堆的过程中需要进行（ ） 次筛选。 A.1
B.[n／ 2] √ C.（n-1） ／ 2 D.n
11.已知定点小数 x 的反码为 1.X1X2 X3 ， 且 x＜-0.75， 则必有（ ）。 A.
X1 ＝0， X2 ＝0， X3 ＝1 B. X1 ＝1 C.
X1 ＝0， 且 X2 ， X3 不全为 0 D.
X1 ＝0， X2 ＝0， X3 ＝0 √
定点小数 x 是 8 位字长纯小数， 第一位为符号位， 小数点在第一位后面， 后七位为具体数值。x＜-0.75， 则可取 x＝-0.76， 得到 X1 ＝1， X2 ＝1， X3 ＝1， 取反 X1 ＝0， X2 ＝0， X3 ＝0。 可再取任意小于-0.75 的数， 取反码后均能得到 X1 ＝0， X2 ＝0， X3 ＝0。
12.设某浮点数共 12 位， 其中阶码含 1 位阶符共 4 位， 以 2 为底， 补码表示； 尾数含 1 位数符共 8 位， 补码表示， 规格化， 则该浮点数所能表示的最大正数是（ ）。 A. 2 B. 2 C. 2-1
887
D. 2-1 √
为使浮点数取正数最大， 可使尾数取正数最大， 阶码取正数最大。 尾数为 8 位补码（含符号位），正最大为 01111111， 为 1-2 。 阶码为 4 位补码（含符号位）， 正最大为 0111， 为 7。 所以， 最大正数为： （1-2 ） ×2 ＝2-1。
13.为了保证程序连续执行， CPU 中设置（ ） 给出下条指令地址。 A.时序电路 B.指令寄存器 C.程序计数器 √ D.地址加法器
程序计数器， 又称为指令计数器， 存放的是下一条指令的地址。 14.主存直接寻址时指令的地址段给出的是（ ）。 A.存放操作数地址的寄存器号 B.存放操作数的寄存器号 C.存放操作数的内容地址 √ D.以上都不是
直接寻址指令中的地址码直接给出操作数所在主存单元的地址。 CPU 取操作数时进行一次访问。 15.与本指令的地址有关的寻址方式是（ ）。 A.立即寻址 B.寄存器寻址 C.相对寻址 √ D.直接寻址
相对寻址的有效地址是将程序计数器 PC 的内容即当前指令的地址与指令字中的形式地址 A 相加而成， 所以与本指令的地址有关。
16.双端口存储器在（ ） 情况下会发生读／ 写冲突。 A.左端口与右端口的地址码不同 B.左端口与右端口的地址码相同 √ C.左端口与右端口的数据码相同 D.左端口与右端口的数据码不同
每个端口都有一套独立的读写系统， 因此只有请求同一地址时才会发生冲突。 17.为了便于实现多级中断， 保存现场信息最有效的方法是采用（ ）。
-7
7
7
-7
7
A.通用寄存器 B.堆栈 √ C.存储器 D.外存
多级中断中， 寄存器的个数很有可能不够用， 会造成覆盖上层中断的现场信息的错误。 用外存保存现场信息， 速度太慢。 常用的方法是用堆栈保存中断的现场信息， 堆栈后进先出的特点正好符合中断返回内层先返回外层后返回的要求。
18.CPU 响应中断时， 进入“中断周期”采用硬件方法保护并更新程序计数器 PC 内容， 而不是由软件完成，主要是为了（ ）。
A.能进入中断处理程序并能正确返回原程序 √ B.节省主存 C.提高处理机速度 D.易于编制中断处理程序
CPU 响应中断时， 在执行中断服务之前， 必须保存 CPU 的返回地址和 CPU 的现场信息。 若中断周期的任务由软件来完成， 则可能会被新到来的中断请求中断， 无法完成 CPU 现场信息的保存， 打乱了 CPU 的中断响应机制， 致使无法正确返回。
19.系统“抖动”现象的发生是由（ ） 引起的。 A.置换算法选择不当 √ B.交换的信息量过大 C.内存容量不足 D.请求页式管理方案
“抖动”现象表现为页面频繁换进换出内存， 这一般是由于页面置换算法不当造成的。
20.某计算机系统， 它的 FCB 占 64B， 一个磁盘块的大小为 1KB， 采用 1 级目录， 假定文件目录中有 3200个目录项， 则查找一个文件平均启动盘块的次数是（ ）。 A.50 B.100 √ C.54 D.200
一共 3200 个目录项， 则平均查找 1600 个能找到目标文件的目录项。 1600 个目录项（FCB） 占 1600×64B＝102400B。 一个磁盘块大小为 1KB＝1024B， 所以平均启动盘块数为 102400/1024＝100。 21.下面关于 RISC 指令系统的表述中， 不正确的是（ ）。 A.选取使用频率低的一些复杂指令， 指令条数多 √ B.指令长度不固定 C.指令条数多
D.只有取数／ 存数指令访问存储器
RISC 结构的最大特点是指令系统简单。 其设计原则是使计算机的结构更加简单、 更加合理， 使系统达到最高的有效速度。 RISC 技术的特点是： ①采用高效的流水线操作； ②指令格式的规格化和简单化； ③采用面向寄存器堆的指令； ④采用装入／ 存储指令结构。 根据以上特点可知， A 项表述错误。 22.在独立请求方式下， 若有 N 个设备， 则下列说法正确的是（ ）。 A.有一个总线请求信号和一个总线响应信号 B.有 N 个总线请求信号和 N 个总线响应信号 √ C.有一个总线请求信号和 N 个总线响应信号 D.有 N 个总线请求信号和一个总线响应信号
每一台设备均有一对总线请求线和总线同意线。 当设备需要使用总线时， 发送请求信号， 中心裁决器从请求总线的一组设备中按一定的优先次序选择一个。 23.下面关于并发性的定义中， 正确的是（ ）。 A.并发性是指若干事件在同一时刻发生 B.并发性是指若干事件在不同时刻发生
C.并发性是指若干事件在同一时间间隔内发生 √ D.并发性是指若干事件在不同时间间隔内发生
并发性是指如果任务都已经启动， 但都还没有完成。 它们是通过在 CPU 上交叉运行而引起的。 24.批处理系统的主要特点是（ ）。 A.CPU 利用率低 B.不能并发执行 C.缺少交互性 √ D.需要大量内存
多道批处理系统， 是指多道批处理操作系统中的作业调度程序从辅助存储器里的该批作业中选出若干合适的作业装入内存， 使它们不断地轮流占用 CPU 来执行， 并同时使用各自所需的外部设备。 批处理系统在处理作业时， 用户不能对作业进行修改和操作， 缺少交互性。
25.在下列操作系统的各个功能组成部分中， 不需要硬件的支持的是（ ）。 A.地址映射 B.时钟管理 C.进程调度 √ D.中断系统
地址映射需要了解物理地址和逻辑地址的关系， 时钟系统需要定时器定时， 中断系统也需要时钟的支持。 而进程调度只是一系列指令， 由操作系统的软件提供， 所以不需要硬件资源。 26.分页式虚拟存储管理系统中， 页面的大小与可能产生的缺页中断次数（ ）。 A.成正比 B.成反比 C.无关 √ D.成固定值
27.从用户角度看， 文件系统主要是实现（ ）。 A.文件保护 B.文件保密 C.文件共享 D.按名存取 √
从用户角度看，文件系统主要是实现“按名存取”。为了能正确地按名存取，文件系统应该具有如下功能。
・实现从逻辑文件到物理文件的转换。 ・有效地分配文件的存储空间
・建立文件目录，文件目录是实现按名存取的一种手段，一个好的目录结构既能方便检索又能保证文件的安全。
・提供合适的存取方法以适应各种不同的应用。 ・实现文件的共享、保护和保密。
・提供一组文件操作，为了保证文件系统能正确地存取和检索文件，用户必须按照一定的步骤使用文件，在计算机系统中，由文件系统提供一组文件操作供用户使用并规定用户使用文件操作的步骤。 28.某计算机系统中若同时存在五个进程， 则处于执行状态的进程最多可有（ ） 个。 A.0 个 B.1 个 √ C.4 个 D.5 个
微观上， 进程在 CPU 上是串行的， 所以一个处理机只能同时执行一个进程。 最少一个都不运行，比如死锁状态， 所以最多只能有 1 个。
29.在单处理机系统中， 有 10 个程序， 每个程序以单道方式运行时， 每个程序需要 10min 完成运行。 完成每个程序的运行需要的时间大于 100min。 若采用多道方式运行， 全部运行完成需要的总时间（ ）。 A.小于 10min
B.大于 10min， 但小于等于 100min √ C.大于 100min D.以上都不对
10 个程序以单道方式运行， 完成运行最优为 100min。 采用多道方式运行， 完成每个程序的运行需要的时间应该大于 10min。 因为多程序采用交叉方式运行， 必然要引起 CPU 的多次调度， 但利用一个或多个程序的输入、 输出来运行其他程序， 必然加快程序的完成。
30.进程 PA 不断地向管道写数据， 进程 PB 从管道中读数据并加工处理， 如图 1 所示。 如果采用 P、 V 操作来实现进程 PA 和进程 PB 间的管道通信， 并且保证这两个进程并发执行的正确性， 则至少需要（ ）。
A.1 个信号量， 信号量的初值为 0
B.2 个信号量， 信号量的初值为 0、 1 √ C.3 个信号量， 信号量的初值为 0、 0、 1 D.4 个信号量， 信号量的初值为 0、 0、 1、 1
要实现 PA 和 PB 之间的并发， 至少需要两个信号量， full 和 empty。 PA 写之前要先判断管道内是否为空（empty： 初值为 1， 表示初始为空）， PB 读数据之前要判断管道内是否有数据（full： 初值为 0， 表示初始管道内无数据）。
31.若有 4 个进程共享同一程序段， 每次允许 3 个进程进入该程序段， 用 P、 V 操作作为同步机制， 则信号量 S 的取值范围是（ ）。 A.4， 3， 2， 1， 0 B.3， 2， 1， 0， -1 √ C.2， 1， 0， -1， -2 D.1， 0， -1， -2， -3
允许 3 个进程同时进入该程序段， 所以 S 初值为 3， 每当有一个进程进入该程序段， S 的值减 1，即 S 会出现 2、 1、 0 三个值， 第四个进程进入时 S 减为-1， 该进程阻塞。
32.若 P、 V 操作的信号量 S 初值为 2， 当前值为-1， 则表示有（ ） 等待进程。 A.0 个 B.1 个 √ C.2 个 D.3 个
由 P、 V 操作可知， S 大于 0 时表示当前可用资源的数量； 当它的值小于 0 时， 其绝对值表示等待使用该资源的进程个数， 所以当前有 1 个等待进程。
33.在下列多路复用技术中， （ ） 具有动态分配时隙的功能。 A.同步时分多路复用 B.统计时分多路复用 √ C.频分多路复用 D.波分多路复用
频分多路复用和波分多路复用都不是基于时隙分割的。 同步时分多路复用是平均分配时间段给各个用户， 并不考虑当前用户是否需要。 统计时分多路复用是采用按需分配时隙的技术， 即动态的分配所需时隙， 以避免每帧中出现空闲的时间隙的现象。
34.在选择重传协议（SR） 中， 当帧的序号字段为 3bit， 且接收窗口与发送窗口尺寸相同时， 发送窗口的最大尺寸为（ ）。 A.2 B.4 √ C.6 D.8
设 n 为序号位数， Ws 为发送窗口大小， Wr 为接收窗口大小， 则选择重传的窗口大小应满足 3 个条件： Ws +Wr ＝2 ； Ws ＞＝Wr ； Ws ， Wr ＜＝2 。 由此， 可确定当帧的序号字段为 3bit， 且接收窗口与发送窗口尺寸相同时， 发送窗口的最大尺寸为 4。
35.在某 CSMA／ CA 网络上， 计算机 A 有 1 个 2 时槽的帧间间隔， 计算机 B 的帧间间隔是 6 时槽， 计算机 C 的帧间间隔是 4 时槽， 则具有最高优先级的设备是（ ）。 A.计算机 A √ B.计算机 B C.计算机 C
D.CSMA／ CA 中不能分配优先级
CSMA／ CA 基本上是一种 P 持续机制， 加上空闲时间管理。 当一个设备检测到传输介质空闲时，该设备在它可以竞争访问介质之前必须等待一个指定的帧间间隔时间， 帧间间隔也可以用于优先级传输。 如果一个设备被分配一个较小的帧间间隔值， 那么它就有更多的机会得到对传输介质的访问。 本题中计算机 A 的帧间间隔值最小， 因此， 具有最高的优先级。
36.网桥是用来连接同介质局域网的关键网络设备， 无须用户设置的网桥称为“透明网桥”形成环路时， 则（ ）。
A.可以有效提高网络的吞吐率 B.可以优化网络结构
C.会对网络产生巨大影响， 应避免出现 D.会影响网络， 可使用生成树协议解决 √
37.如果我们需要在路由表中设置一条默认路由， 那么目标地址应为______， 子网掩码应为______。（ ）
A.0.0.0.0； 0.0.0.0 √ B.127.0.0.0； 0.0.0.0 C.0.0.0.0； 1.0.0.0
D.255.0.0.0； 255.255.255.255
在路由协议中， 要表示默认路由时， 通常采用 0.0.0.0／ 0.0.0.0。
n
n-1
38.一个 TCP 连接使用 256kbit／ s 的链路， 其端到端延时为 128ms， 经测试发现吞吐量只有 128kbit／ s， 忽略 PDU 封装的协议开销以及接收方应答分组的发射时间， 则窗口大小为（ ）。 A.1024B B.8192B √ C.10KB D.128KB
来回路程的时延等于 128ms×2＝256ms。 设窗口值为 x 字节， 假定一次最大发送量等于窗口值， 且发射时间等于 256ms， 那么每发送一次都得停下来期待再次得到下一窗口的确认， 以得到新的发送许可。 这样，发射时间等于停止等待应答的时间， 结果， 测到的平均吞吐率就等于发送速率的一半， 即 128kbit／ s。
由以上分析可得： 8x／ （256×1000） ＝256×0.001。 解得： x＝256×1000×256×0.001／ 8＝256×32＝8192。 所以， 窗口值为 8192。
39.用户请求 FTP 服务器返回当前目录的文件列表时， 传输文件列表的连接是（ ）。 A.控制连接 B.数据连接 √ C.UDP 连接 D.应用连接
FTP 将文件列表看做是数据， 因此， 请求查看当前目录文件列表的命令在控制连接上传输， 而返回的文件列表内容是在数据连接上传输的。
40.HTTP 是一个无状态协议， 然而 Web 站点经常希望能够识别用户， 这时需要用到（ ）。 A.Web 缓存 B.Cookie √ C.条件 GET D.持久连接
Cookie 允许站点跟踪用户， Cookie 技术有 4 个组成部分： 在 HTTP 响应报文中有一个 Cookie 首部行； 在 HTTP 请求报文中有一个 Cookie 首部行； 在用户端系统中保留有一个 Cookie 文件， 由用户的浏览器管理；在 Web 站点有一个后端数据库。
二、综合应用题(总题数：7，分数：70.00)
给出如图 2 所示的有向图（结点旁边的数为结点的编号， 即结点在图中的位置）。
图2 有向图（分数：10）
(1).试写出带入度域的邻接表；（分数：5）
__________________________________________________________________________________________ 正确答案：(
与题中有向图对应的带入度域的邻接表如图 3 所示。
图3 与题中有向图对应的带入度域的邻接表 )
(2).给出在此邻接表存储结构下， 以 h 为起始结点的深度优先遍历序列和广度优先遍历序列， 并写出遍历过程中所走过的边。（分数：5）
__________________________________________________________________________________________ 正确答案：(
图的深度优先遍历序列为： h， g， e， d， a， b， f ， c， 遍历过程中所走过的边为： 图的广度优先遍历序列为： h， g， a， e， b， d， f， c， 遍历过程中所走过的边： 41.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT 中， 写出计算该算术表达式值的算法。 __________________________________________________________________________________________ 正确答案：( 以二叉树表示算术表达式， 根结点用于存储运算符。 若能先分别求出左子树和右子树表示的子表达式的值， 最后就可以根据根结点的运算符的要求， 计算出表达式的最后结果。 typedef struct node { ElemType data; float val; char optr; //只取‘+’， ‘-’， ‘*’， ‘/’ struct node *lchild， *rchild }BiNode,*BiTree; float PostEval（BiTree bt） // 以后序遍历算法求以二叉树表示的算术表达式的值 { float lv,rv; if（bt!＝null） { lv＝PostEval（bt->lchild） ; // 求左子树表示的子表达式的值 rv＝PostEval（bt->rchild） ; // switch（bt->optr） { case ‘+’ : value＝lv+rv; break; case ‘-’ : value＝lv-rv;break; case ‘*’ : value＝lv*rv;break; case ‘/’ : value＝lv/rv; } } return（value） ; } ) 假定磁盘传输数据以 32 位的字为单位， 传输速率为 1MB／ s。 CPU 的时钟频率为 50MHz。（分数：10） (1).使用程序查询的输入输出方式， 一个查询操作需要 100 个时钟周期， 求 CPU 为 I／ O 查询所花费的时间比率， 假定进行足够的查询以避免数据丢失。（分数：3） __________________________________________________________________________________________ 正确答案：( 根据题意可知， 每传送一个字需要 4μs， CPU 的时钟周期为 0.02μs。 程序查询的输入输出方式， 一个查询操作需要 100 个时钟周期， 而时钟周期＝0.02μs， 所以每个查 询操作需要 2μs， CPU 为 I／ O 查询所花费的时间比率为) (2).用中断方式进行控制， 每次传输的开销（包括中断处理） 为 100 个时钟周期， 求 CPU 为传输磁盘数据花费的时间比率。（分数：3） __________________________________________________________________________________________ 正确答案：( 用中断方式法进行控制， 每次传输的开销（包括中断处理） 为 100 个时钟周期， 而时钟周期＝0.02μs，所以每次传输的开销时间＝100×0.02＝2μs， 传送一个字的时间为 4μs。 CPU 为传输磁盘数据花费的时间比率为) (3).采用 DMA 控制进行输入输出操作， 假定 DMA 的启动操作需要 1000 个时钟周期。 DMA 完成时处理中断需要 500 个时钟周期， 如果平均传输的数据长度为 4KB， 问在磁盘工作时处理器将用多少时间比率进行输入输出操作， 忽略 DMA 申请使用总线的影响。（分数：4） __________________________________________________________________________________________ 正确答案：( 采用 DMA 控制进行输入输出操作， 平均传输的数据长度为 4KB， 根据数据传输率， 传送时间 4KB÷1MB／ s＝4ms。 又由于 DMA 的启动操作需要 1000 个时钟周期， 即 1000×0.02＝20μs； DMA 完成时 处理中断需要 500个时钟周期， 即 500×0.02＝10μs。 所以在磁盘工作时 CPU 为进行输入输出操作 花费的时间比率为) 某微机的寻址范围为 64KB， 其存储器选择器信号为 M， 接有 8 片 8KB 的存储器， 试完成下列问题。（分数：10） (1).画出选片译码逻辑图。（分数：2） __________________________________________________________________________________________ 正确答案：( 选片译码逻辑如图 4 所示。 ) (2).写出每片 RAM 的寻址范围。（分数：2） __________________________________________________________________________________________ 正确答案：( 8 片 RAM 的寻址范围分别是： 0000H～1FFFH、 2000H～3FFFH、 4000H～5FFFH、 6000H～7FFFH、8000H～9FFFH、 A000H～BFFFH、 C000H～DFFFH 和 E000H～FFFFH。 ) (3).如果运行时发现不论往哪片存储器存放 8KB 数据， 以 A000H 为起始地址的存储芯片都有相同的数据，分析故障原因。（分数：3） __________________________________________________________________________________________ 正确答案：( 说明译码器有误，) 输出始终为低， 从而使第 6 片 RAM 始终被选中。 (4).若发现译码器中的地址线 A 13 与 CPU 断线， 并搭接到高电平的故障， 问后果如何?（分数：3） __________________________________________________________________________________________ 正确答案：( 若发现 A 13 与 CPU 断线， 并搭接到高电平的故障， 则第 1、3、 5、 7 片 RAM 始终不被选中。 ) 信号均不会为 0， 故 42.设有 8 个进程 M1， M2， …， M8， 它们有如图 5 所示的优先关系， 试用 P、 V 操作实现这些进程间的同步。 图5 8 个进程的优先关系 __________________________________________________________________________________________ 正确答案：( 这是进程之间的同步问题。 M2、 M3 和 M4 必须在接收到 M1 的消息后才能运行。 同理， M6 必须在 M2和 M3 之后运行， M7 必须在 M4 和 M5 之后运行， M8 必须在 M3 和 M7 之后运行。 如何保证呢?需设置相应的信号量来保证： S12、 S13、 S14 分别用来制约 M2、 M3 和 M4 的运行； S26、 S36 用来制约 M6 的运行； S47、 S57用来制约 M7 的运行； S38、 S78 用来制约 M8 的运行。 各进程的制约关系如下： ) 有 5 个任务 A、 B、 C、 D、 E， 几乎同时到达， 预计它们的运行时间为 10、 6、 2、 4、 8 分钟， 其优先级分别为 3、 5、 2、 1 和 4， 这里 5 为最高优先级。 对于下列每一种调度算法， 计算其平均进程周转时间（进程切换开销可不考虑）。（分数：10） (1).先来先服务算法（按 A、 B、 C、 D、 E 的顺序）。（分数：3） __________________________________________________________________________________________ 正确答案：( 采用先来先服务算法时的执行情况， 如表 1 所示。 表1 FIFO 算法的执行情况 作业序号 A 运行时间 10 等待时间 0 周转时间 10 B C D E ) 6 2 4 8 平均周转时间 10 16 18 22 16 18 22 30 T=19.2（min） (2).优先级调度算法。（分数：3） __________________________________________________________________________________________ 正确答案：( 采用优先级调度算法时的执行情况， 如表 2 所示。 表2 优先级调度的执行情况 作业序号 运行时间 等待时间 周转时间 A B C D E ) (3). 时间片轮转调度算法。（分数：4） __________________________________________________________________________________________ 正确答案：( 采用时间片轮转调度算法（时间片为 2min） 的执行情况， 如表 3 所示。 表3 时间片轮转调度算法的执行情况 6 8 10 2 4 0 6 14 24 26 6 14 24 26 30 T=20（min） 平均周转时间 作业序号 运行时间 等待时间 周转时间 A B C D E ) 10 6 2 4 8 20 16 4 12 20 30 22 6 16 28 T=20.4（min） 平均周转时间 43.假定卫星信道的数据速率为 100kbit／ s， 卫星信道的单程（即从发送方通过卫星到达接收方） 传输时延为 250ms， 每个数据帧长均为 2000bit， 忽略误码、 确认字长、 首部、 处理时间等开销， 为达到传输的最大效率，帧的顺序号应为多少位?此时信道利用率是多少? __________________________________________________________________________________________ 正确答案：( RTT＝250×2ms＝0.5s。 1 个帧的发送时间＝2000bit／ 100kbit／ s＝20×10 s。 1 个帧发送完后经过 1 个单程延迟到达接收方， 再经过 1 个单程延迟发送方收到应答， 从而可以继续发送，理想的情况是此时窗口信息刚发送完或还没有发送完。 假设窗口值等于 x， 令（2000bit×x） /（100kbit/s） ＝20×10 s+RTT＝20×10 - 3 s+0.5s＝0.52s。 解得 x＝26。 若要取得最大信道利用率， 窗口值是 26 即可， 在此条件下可以不间断地发送帧， 故发送率保持在 100kbit／ s。 由于 16＜26＜32， 帧的顺序号应为 5 位。 在使用后退 N 帧协议的情况下， 最大窗口值是 31， 大于 26， 可以不间断地发送帧， 此时信道利用率是 100％。 ) -3 -3 因篇幅问题不能全部显示，请点此查看更多更全内容