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

一、应用题

1． 设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶树。要求从空树开始，每插入一个关键字，画出一棵树。

【答案】如图所示：

图

2． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？

【答案】不一定相邻。哈希地址为

的关键字，和为解决冲突形成的探测序列f 的

同义词，都争夺哈希地址i 。

3． 在树和树中查找关键字时，有什么不同？

【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。

树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关

字后，要继续查到最下层结点，得到查找成功与否的结论。另外，

键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

4． 设有正文AADBAACACCDACACAAD ，字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。

A :1, B :000，C :01，D :001。 【答案】字符A , B , C , D 出现的次数为9, 1, 5, 3。其哈夫曼编码如下：

5． 某计算机字长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 的存储单元的内容会改变，改变后的内容分别为

：

6． （1）对于有向无环图，叙述求拓扑有序序列的步骤；

（2）对于图1，写出它的四个不同的拓扑有序序列。

+对应的机器码为

该指令执行后，

条不同的指令；指令操作上占6

个通用寄存器；主存容

个存储单元，故MDR 和MAR 至少各

位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有

（逗号前为源操作数，逗号后为目的操作数）

对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变?

图1

【答案】（1）对有向图，求拓扑序列步骤为：

1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。 2）在图中删除该顶点及所有以它为尾的弧。

3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

（2）拓扑有序序列如图2:

图2 拓扑有序序列

7． 某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许个通过。参观者的活动描述如下：

参观者进程i :

进门；

参观;

出门；