2018年齐鲁工业大学理学院872数据结构考研核心题库
● 摘要
一、应用题
1． 某计算机采用16位定长指令字格式, 其CPU 中有一个标志寄存器, 其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令, 其格式如下:
其中, 00000为操作码OP ; C 、Z 和N 分别为CF 、ZF 和NF 的对应检测位, 某测位为1时表示需检测对应标志, 需检测的标志位中只要有一个为1就转移, 否则就不转移, 例如, 若C=1, Z=0, N=1, 则需检测CF 和NF 的值, 当CF=1或NF=1时发生转移; OFFSET 是相对偏移量, 用补码表示。
转移执行时,
转移目标地址为
顺序执行时,
下条指令地址为
请回答下列问题。
(1)该计算机存储器按字节编址, 还是按字编址？该条件转移指令向后(反向) 最多可跳转最多少条指令？
(2)某条件转移指令的地址为200CH , 指令内容如下图所示, 若该执行时CF=0, ZF=0, NF=1, 则该指令执行后PC 的值是多少？若该指令执行时CF=1, ZF=0Z, NF=0, 则该指令执行后PC 的值又是多少？请给出计算过程。
(3)实现“无符号数比较小于等时转移”功能的指令中, C 、Z 和N 应各是什么？
(4)以下是该指令对应的数据通路示意图, 要求给出中部件①〜③的名称或功能说明。 。 ;
图
【答案】(1)因为指令长度为16位且下条指令地址为
题中给出偏移量OFFSET 为8位补码, 其范围为
后最多可跳转127条指令。
(2)指令中C=0, Z=1, N=1, 故应根据ZF 和NF 的值来判断是否转移。当CF=0, ZF=0, NF=1时需转移。已知指令中偏移量为1110 0011B=E3H, 符号扩展后为FFE3H , 左移一位(乘2) 后为FFC6H , 故PC 的值(即转移目标地址) 为200CH+2+FFC6H=1FD4H当CF=1, ZF=0, NF=0时不转移。
PC 的值为200CH+2=200EH。
(3)指令中的C 、Z 和N 应分别设置为C=Z=1, N=0。
(4)部件①指令寄存器:用于存放当前指令; 部件②移位寄存器:用于左移一位; 部件③加法器:地址相加。
2． 如果两个串含有相等的字符，能否说它们相等？
【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同(即两串串值相等) 。
3． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时, 若有空座位, 则到取号机上领取一个号, 等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时, 通过叫号选取一位顾客, 并为其服务。顾客和营业员的活动过程描述如下:
, 故编址单位是字节。 , 故相对当前指令进行条件跳转, 向
请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 实现上述过程中的互斥与同步。要求写出完整的过程, 说明信号量的含义并赋初值。
【答案】(1)互斥资源:取机号, 故设一个互斥信号量mutex 。
(2)同步问题:顾客需要获得空座位等待叫号, 当营业员空闲时, 将选取一位顾客为其服务。空座位的有、无影响等待顾客数量, 顾客的有、无决定两营业员是否能开始服务。另外, 顾客获得空座位后, 需要等待叫号和被服务, 顾客与营业员就服务何时开始有同步关系。设信号量teller , customer 和mutex 初值分别为0, 0和1, 设waiting 为整型量, 表示排队的储户数量, 其初始为0, 表示顾客初始时为0, 最大不超过10(10把座椅) , 各进程的具体实现如下所示:
座椅数, 也是最多排队的储户数
定义信号量
等待储户的柜员资源
排队等待服务的储户数量
对排队机操作的互斥量
在座椅上休息等待的储户数
储户进程
先获得排队机
若还有座椅则取号
取号, 占用座椅等待叫号
告知系统储户加
1
释放排队机
等待柜员叫号
进入窗口被服务
若没有座椅了, 则不取号
不取号, 释放排队机
离开
并发调度无限循环