1、姓名： 报考专业： 准考证号码： -密封线内不要写题-机密启封前 2021年攻读硕士学位研究生入学考试试题科目名称： 计算机基础 （A卷B卷）科目代码：814 考试时间：3小时 满分150分注意：本试题共六道大题，共3页；所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题和答题纸一同装入试卷袋密封交回。一、简述题（共2小题，每小题10分，共20分）1算法的5个重要特性是什么？2好的算法应达到的4个主要目标是什么？二、哈夫曼（Huffman）树的应用（共3小题，每小题10分，共30分）在打字系统中，数字1的出现频率21，数字2的出现频率31，数字3的出现频率41，数字4的出现
2、频率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
3、; 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. 假设主存容量16M32位，Cache容量64K32位，主存与Cache之间以每块432位大小传送数据，请确定直接映射方式的有关参数，并画出主存地址格式。六、分析题（20分）某16位机器所使用的指令格式和寻址方式如下图所
4、示，该机有两个20位基址寄存器，四个16位变址寄存器，十六个16位通用寄存器。指令汇编格式中的S（源），D（目标）都是通用寄存器，M是主存中的一个单元。三种指令的操作码分别是： MOV（OP）=（0A）H， MOV是传送指令；STO（OP）=（1B）H， STO为存数指令；LAD（OP）=（3C）H， LAD为取数指令。15 10987430OP目标MOV S，D源 15 10987430OP基址源STO S，M变址位移量15 10987430OP目标LAD M，D 20位地址 问下列情况下每个十六进制指令字分别代表什么指令，并填空。 （1）（2828)H 代表_指令；该指令为： _字长指令， _地址指令， _型指令。 （2）（F0D4)H (2021)H 代表_指令；该指令为： _字长指令， _地址指令， _型指令。第 3 页 共 3 页
