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

一、应用题

1． 设某计算机的逻辑地址空间和物理地址空间均为64KB , 按字节编址。若某进程最多需要6页（Page ）数据存储空间，页的大小为1KB , 操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFrame ）。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。

当该进程执行到时刻260时，要访问的逻辑地址为17CAH 的数据，请回答下列问题：

（1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO ）置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程。

（3）若采用时钟（CLOCK ）置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示）

图

【答案】（1）由题可知计算机的逻辑地址空间和物理地址空间均为64KB=216B, 按字节编址，并且页的大小为IK=210, 故逻辑地址和物理地址的地址格式均为：

地址17CA=0001011111001010B，故可知其逻辑页号为000101B=5。

（2）根据FIFO 算法，需要替换出最早装入的页，故需置换0号页，将5号页装入7号页框中，所以物理地址为0001111111001010B=1FCAH。

（3）根据CLOCK 算法，如果当前指针所指页框的使用位为0, 则替换该页，否则将使用位清零，并将指针指向下一个页框，继续查找。由题可知，将从2号页框开始，前4次查找页框号的顺序为2、4、7、9, 并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位已经为0, 故将2号页框的页将5号装入2号页框，并将其对应使用位设置为1, 所以对应的物理地址为0000101111001010B=0BCAH。

2． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，

，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）

凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序

割成两部分：和和

且

将分然后再递归地将进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。本题解答如下：

初始序列：[28]，07，39，10，65，14，61，17，50，21

21移动：21，07，39，10，65，14，61，17，50，[]

39移动：21，07，[]，10，65，14，61，17，50，39

17移动：21，07，17，10，65，14，61，[]，50，39

65移动：21，07，17，10，[]，14，61，65，50，39

14移动：21，07，17，10，14，[28]，61，65，50，39

3． 某计算机字长16位，主存地址空间大小为128KB , 按字编址，采用单字长指令格式，指令各字段定义如下：

源操作数目的操作数

转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：

注：（X ）表示存储器地址X 或寄存器X 的内容。请回答下列问题：

（1）该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器（MAR ）和存储器数据寄存器（MDR ）至少各需要多少位？

（2）转移指令的目标地址范围是多少？

（3）若操作码0010B 表示加法操作（助记符为add ）, 寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H , 地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变?

改变后的内容是什么？

【答案】（1）指令操作码占4位，则指令系统最多可有

量为128KB ，计算机字长为16位，故主存有

需16位。

（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。 （3）汇编语句

寄存器

R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为

：

4． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。

【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。

第一趟：12，23，35，16，25，36， 19，21，16， 47

第二趟：12，16，23，35，16，25，36， 19，21，47

第三趟：12，16，23，16，25，35， 19，21，36， 47

第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47

第五趟：12，16，16，19，23，25，21，35， 36， 47

第六趟：12，16，16，19，21， 23，25，35， 36， 47

第七趟：12，16，16，19，21，23，25，35， 36， 47

+对应的机器码为该指令执行后，条不同的指令；指令操作上占6个通用寄存器；主存容个存储单元，故MDR 和MAR 至少各位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有