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