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

一、应用题

1． 某16位计算机主存按字节编码。存取单位为16位；采用16位定长指令格式；CPU 采用单总线结构，主要部分如下图所示。图中为通用寄存器；T 为暂存器；SR 为移位寄存器，可实现直送（mov ）、左移一位（left ）、右移一位（right ） 3种操作，控制信号为Srop , SR的输

ALU 可实现直送A A 加 B （add ）A 减 B （sub ）A 与 B （and ）出信号Srout 控制；（mova ）、、、、

A 或 B （or ）、非 A （not ）、A 加 1 （inc ） 7 种操作，控制信号为

请回答下列问题。

（1）图中哪些寄存器是程序员可见的？为何要设置暂存器T?

（2）控制信号（4）端点和的位数至少各是多少？ （3）控制信号Srout 所控制部件的名称或作用是什么？ 中，哪些端点须连接到控制部件的输出端？

中相应的端点之间添加必要的连线。写出连（5）为完善单总线数据通路，需要在端点

线的起点和终点，以正确表示数据的流动方向。

（6）为什么二路选择器MUX 的一个输入端是2?

【答案】（1）图中程序员可见的寄存器有通用寄存器和程序计数器PC ; 当执行算术或逻辑操作时，由于ALU 本身是没有内部存储功能的组合电路，因此如要执行加法运算，被相加的两个数必须在ALU 的两个输入端同时有效，因此设置暂存器T 用于暂存数据总线发送的数据。

（2）ALUop 和SRop 的位数分别为3，2。

（3）Srout 所控制的部件是状态字寄存器，用来存放ALU 及CPU 的指令状态。

（4）须连接到控制部件的输出端端点有

（5）

（6）数据宽度是16位，以字节编址，输入端是2是为了增加地址获取ALU 的第二个操作数。

【解析】（1）程序员可见的寄存器包括：程序计数器、通用寄存器和状态寄存器。其他的IR 、MAR 和MDR 等 是CPU 的内部工作寄存器，对程序员不可见。

（2）ALU 中共有7种命令，用三位即可区别表示，SR 共有三种命令二位二进制即可表示。 （4）操作符命令，传输等都需要控制信号进行控制。

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

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

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

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

（2）证明：当i=l时，

成立。

设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公

，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为

3． 为什么文件的倒排表比多重表组织方式节省空间？

【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。

4． 某文件系统空间的最大容量为4TB 以磁盘块为基本分配单位，磁盘块大小为1KB 。文件控制块（FCB ）包含一个512B 的索引表区。请回答下列问题。

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

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

【答案】

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

（2） 为表示个块号，索引表项占512B 个索引项，每个索引项对应一个磁盘块，故最大文件长度：, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍块号占6字节，块数占2字节的情形下，最大文件长度

：

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

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

5． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

6． 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

（1）归并排序，每归并一次书写一个次序。

（2）快速排序，每划分一次书写一个次序。

（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

【答案】（1）2—路归并第一趟：18，29，25，47，12，58，10，51:

第二趟：18，25，29， 47，10，12，51，58;

第三趟：10，12，18，25，29，47，51，58

（2）快速排序第一趟：10，18，25，12，29，58，51，47;

第二趟：10，18，25，12，29，47，51，88;

第三趟：10，12，18，25，29，47，51，88

（3）堆排序

建大堆：58，47，51，29，18，12，25，10;

①51，47，25，29，18，12，10，58;

②47，29，25，10，18，12，51，58;

③29，18，25，10，12，47，51，58;

④25，18，12，10，29，47，51，58;

⑤18，10，12，25，29， 47，51，58;

⑥12，10，18，25，29，47，51，58;

⑦10，12，18，25，29， 47，51，58

7． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树；

（2）若查找元素54，需依次与哪些元素比较？

（3）若查找元素90，需依次与哪些元素比较？

（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

【答案】（1）判定树如图所示：