当前位置：问答库＞考研试题

一、应用题

1． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：

2． 如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。

3． 给出模式串在KMP 算法中的next 和nextval 数组。

【答案】模式串的next 函数定义如下：

根据此定义，

可求解模式串

的next 和nextval 值如下：

4． 某计算机采用16位定长指令字格式，其CPU 中有一个标志寄存器，其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令，其格式如下：

其中，00000为操作码OP ; C、Z 和N 分别为CF 、ZF 和NF 的对应检测位，某测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则就不转移，例如，

若

OFFSET 是相对偏移则需检测CF 和NF 的值，当CF=1或NF=1时发生转移；

量，用补码表示。转移执行时，转移目标地址为为

请回答下列问题。

（1）该计算机存储器按字节编址，还是按字编址？该条件转移指令向后（反向）最多可跳转最多少条指令？

（2）

某条件转移指令的地址为200CH ，指令内容如下图所示，若该执行

时

则该指令执行后PC 的值是多少？若该指令执行时则该指令执行后PC 的值又是多少？请给出计算过程。

（3）实现“无符号数比较小于等时转移”功能的指令中，C 、Z 和N 应各是什么？ （4）以下是该指令对应的数据通路示意图，要求给出中部件①〜③的名称或功能说明。

顺序执行时，下条指令地址

【答案】

（1）因为指令长度为16位且下条指令地址为向后最多可跳转127条指令。

N=l, 故应根据ZF 和NF 的值来判断是否转移。（2）指令中C = 0, Z=l，当CF=0, ZF=0, NF=1时需转移。已知指令中偏移量为1110 0011B=E3H, 符号扩展后为FFE3H , 左移一位（乘2）后为FFC6H , 故PC 的值（即转移目标地址）为PC

的值为

（3）指令中的C 、Z 和N 应分别设置为法器：地址相加。

5． 对一个有t 个非零元素的

时不转移。

故编址单位是字节。

题中给出偏移量OFFSET 为8位补码，其范围为-128〜127, 故相对当前指令进行条件跳转，

（4）部件①指令寄存器：用于存放当前指令；部件②移位寄存器：用于左移一位；部件③加

矩阵，用的数组来表示，其中第0行的三个元素分

别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素

在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？

【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，

时间复杂度为

若使查找时间得到改善，可以建立索引，将各行行

号及各行第一个非零元素在数组B 中的位置（下标）放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中 顺序（或折半）查找该元素，这时时间复杂度为

6． 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次 创建新文件。请回答如下问题。

（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适? 要求说明理由。为定