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

一、应用题

1． 某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。请回答下列问题。

（1）若使用一级页表的分存储管理方式，逻辑地址结构为：

则页的大小是多少字节？页表最大占用多少字节？

（2）若使用二级页表的分存储管理方式，逻辑地址结构为：

设逻辑地址为LA ，请分别给出其对应的页目录号和表索引达式。

（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为00008000H ，其长度为8KB ，被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存0020 0000H 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。

【答案】

（1）因为页内偏移量是12位所以页大小为4KB 页表项数为页表索引可表示为：

表项，所以第8个页表项的物理地址=页表起始地

址

如下图所示。 该一级页表最大为

页表项的字节

数

（2）页目录号可表示为：

（3）代码页面1的逻辑地址为0000 8000H, 表明其位于第8个页处，对应页表中的第8个页

2． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？

【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。

3． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？

【答案】（1）最高位优先（MSD ）法

先对最高位关键字进行排序，将序列分成若干子序列，

每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字列。

（2）最低位优先先对最低位关键字位关键字

序列参加排序，

但对

法

进行排序，然后对高一级关键字

进行排序，依次重复，直至对最高

进行排序，按值不同再分成若干更小的子序列，依

次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序

排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个

排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序

时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。 4． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

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

阶稀疏矩阵A 有t 个非零元素，其三元组表示为

表示A 才有意义？ 的

个存储单元，用二维数组存储时占用

个单元，

只有当试问：非零元

5． 设

素的个数t 达到什么程度时用，共占用三元组表

元组）

时，用

【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数皿和非零元素个数tu （也算一个三

表示A 才有意义。解不等式得

6． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。

【答案】删除P 后