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

一、简述题(共2小题，每小题10分，共20分)
1.数据结构研究的内容是什么?给出抽象数据类型的定义。
2.顺序存储结构的主要特点?链式存储结构的主要特点?
二、哈夫曼(huffman)树的应用(共3小题，每小题10分，共30分)
假设某种传输中，字母a的使用频率为30，字母b的使用频率为35，字母c的使用频率为40，字母d的使用频率为45，字母e的使用频率为50，使用哈夫曼树设计一种编码，使数据传输量最少。
1. 请画出哈夫曼树。
2. 按照左0，右1的规则，给出字母a,b,c,d,e的编码。
3. 如果接受的二进制串为“110111000110”，译码出来的信息是什么?
三、排序问题(共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.按照IEEE 754标准，请将十进制数-27/64转换成32位的浮点数的二进制存储格式。
2.设有一个具有20位地址和32位字长的存储器，请问：
(1)该存储器能存储多少个字节的信息?(5分)
(2)如果存储器由256K×8位SRAM组成，需要多少片?(5分)
(3)需要多少位地址作芯片选择?(5分)
六、分析题(20分)
运算器数据通路如下图所示，期中ALU为算术逻辑单元，SA、SB为暂存器。4个通用寄存器的读、写控制功能如下表所示。