2021年湖北汽车工业学院814计算机基础硕士学位研究生入学考试试题（B卷）

一、简述题(共2小题，每小题10分，共20分)
1.算法的5个重要特性是什么?
2.好的算法应达到的4个主要目标是什么?
二、哈夫曼(Huffman)树的应用(共3小题，每小题10分，共30分)
在打字系统中，数字1的出现频率21，数字2的出现频率31，数字3的出现频率41，数字4的出现频率51，数字5的出现频率61，使用哈夫曼树设计一种编码，使得存储量最少。
1. 请画出哈夫曼树。
2. 按照左0，右1的规则，给出数字1,2,3,4,5的编码。
3. 如果接受的二进制串为“101001000111”，译码出来的信息是什么?
三、排序问题(共30分)
1.写出小根堆的定义。(5分)
2.利用小根堆对1，9，12，8，10，11从小到大的排序(把序列看成完全二叉树)，画出排序过程的每一步。(25分)
四、树的遍历(共2小题，每小题10分，共20分)
1.简述二叉树的中序遍历的算法。
2.用C语言描述该算法的递归实现。
树的结点定义：
typedef struct BTNode
char data;
struct BTNode *Lchild;
struct BTNode *Rchild;
} *Btree;
访问结点的函数为： vt(char ch),可直接使用。
五、计算题(共2小题，每小题15分，共30分)
1.有一个4级线性流水线，每个过程所需的时间分别为：τ1=40ns，τ2=60ns，τ3=60ns，τ4=50ns，缓冲寄存器L的延时为τi=10ns，求此4级流水线的加速比。
2. 假设主存容量16M×32位，Cache容量64K×32位，主存与Cache之间以每块4×32位大小传送数据，请确定直接映射方式的有关参数，并画出主存地址格式。
六、分析题(20分)
某16位机器所使用的指令格式和寻址方式如下图所示，该机有两个20位基址寄存器，四个16位变址寄存器，十六个16位通用寄存器。指令汇编格式中的S(源)，D(目标)都是通用寄存器，M是主存中的一个单元。三种指令的操作码分别是：
MOV(OP)=(0A)H， MOV是传送指令;
STO(OP)=(1B)H， STO为存数指令;
LAD(OP)=(3C)H， LAD为取数指令。