1、姓名： 报考专业： 准考证号码： -密封线内不要写题-机密启封前 2021年攻读硕士学位研究生入学考试试题科目名称：计算机基础 （A卷B卷）科目代码：814考试时间：3小时 满分150分注意：本试题共六道大题，共3页；所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题和答题纸一同装入试卷袋密封交回。一、简述题（共2小题，每小题10分，共20分）1数据结构研究的内容是什么？给出抽象数据类型的定义。2顺序存储结构的主要特点？链式存储结构的主要特点？二、哈夫曼（huffman）树的应用（共3小题，每小题10分，共30分）假设某种传输中，字母a的使用频率为30，字母b的使用频率为3
2、5，字母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 BTNod
3、e 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）如果存储器由256K8位SRAM组成，需要多少片？（5分）（3）需要多少位地址作芯片选择？（5分）六、分析题（20分）运算器数据通路如下图所示，期中ALU为算术逻辑单元，
4、SA、SB为暂存器。4个通用寄存器的读、写控制功能如下表所示。读 控 制写 控 制RRA1RA0选择WWA1WA0选择100R0100R0101R1101R1110R2110R2111R3111R30不读0不写ALUSASB4个通用寄存器（R0R3） + - （SA-SB） LDSA LDSB R RA0 RA1 W WA0 WA1 微指令格式中E代表一段微程序结束，转入公操作的控制信号。求：对于机器指令 ADD R3，R2 即(R3)+(R2) R2 完成微程序流程图，并用二进制代码写出微程序。取指微指令格式测试 RA1 RA0 WA1 WA0 R W LDSA LDSB + - ER3SA第 3 页 共 3 页
