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

一、应用题

1． 某16位计算机中，带符号整数用补码表示，数据Cache 和指令Cache 分离。题表给出了指令系统中部分指令格式，其中Rs 和Rd 表示寄存器，mem 表示存储单元地址，（X ）表示寄存器X 或存储单元X 的内容。

表 指令系统中部分指令格式

该计算机采用5段流水方式执行指令，各流水段分别是取指（IF ）、译码/读寄存器（ID ）、执行/计算有效地址（EX ）、访问存储器（M ）和结果写回寄存器（WB ）, 流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。

（1）若int 型变量x 的值为-513, 存放在寄存器R1中，则执行指令“SHR R1”后，R1的内容是多少？（用十六进制表示）

（2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？

（3）若高级语言程序中某赋值语句为

址分别表示为和b 均为int 型变量，它们的存储单元地该语句对应的指令序列及其在指令流水线中的执行过程如题图所示。则这4条指令执行过程中，的ID 段和的IF 段被阻塞的原因各是什么？

图 指令序列及其执行过程示意图

（4）若高级语言程序中某赋值语句为x 和a 均为unsigned int 类型变量，它们的存

储单元地址分别表示为

【答案】

（1）x 的机器码为

1110 1111 1111B, 即指令执行后

（2）至少需要则执行这条语句至少需要多少个时钟周期? 要求模仿题图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。 即指令执行前（Rl ） =FDFFH, 右移lwei 后为1111 个时钟周期数。

（3）的ID 段被阻塞的原因：因为

与和都存在数据相关，需等到和将结果写回寄存器后，才能读寄存器内容，所以的ID 段被阻塞。

的IF 段被阻塞的原因：因为14的前一条指令在ID 段被阻塞，所以，的IF 段被阻塞。

（4）对应的指令序列为：

这5条指令在流水线中的执行过程如下图所示，执行 语句最少需要17个时钟周期。

2． 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。

【答案】循环单链表若只设头指针，则出队操作时间复杂度是

是若只设尾指针，则出队和入队操作时间复杂度都是

列，设置一个尾指针更合适。

3． 某文件系统空间的最大容量为4TB 而如对操作时间复杂度

因此，用循环单链表来实现队 以磁盘块为基本分配单位，磁盘块大小为1KB 。文件控制块（FCB ）包含一个512B 的索引表区。请回答下列问题。

（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？

（2）假设索引表区采用如下结构：第0〜7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B ，块数占2B ; 剩余504字节采用直接索引结构，一个索引项占6B ，则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理 值并说明理由。

【答案】

（1）文件系统存储空间共有块数可存放

（2） 为表示个块号，索引表项占512B 个索引项，每个索引项对应一个磁盘块，故最大文件长度：块号占6字节，块数占2字节的情形下，最大文件长度

：

理由：合理的起始块号和块数所占字节数分别为

块数占4B 或以上，就可表示4TB 大小的文件长度，达到文件系统的空间上限。

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

【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，

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

列。

（2）最低位优先

先对最低位关键字

位关键字

序列参加排序，

但对法 进行排序，然后对高一级关键字进行排序，依次重复，直至对最高进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。

5． 在堆排序、快速排序和合并排序中：

（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？

（3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？

（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？

【答案】（1）应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 （2）应选取归并排序方法

（3）应选取快速排序方法

（4）应选取堆排序方法

6． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。

（1）试问这种二叉树的结点总数是多少？

（2）试证明 。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。

【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。