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个通用寄存器的读、写控制功能如下表所示。

读 控 制 写 控 制
R RA1 RA0 选择 W WA1 WA0 选择
1 0 0 R0 1 0 0 R0
1 0 1 R1 1 0 1 R1
1 1 0 R2 1 1 0 R2
1 1 1 R3 1 1 1 R3
0 × × 不读 0 × × 不写


阅读剩余
THE END