1、 第 1 页 共 2 页 姓 名 ： 报 考 专 业 ： 准 考 证 号 码 ： - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 密封线内不要写题- - - - - - - - - - - - - - - - - - - - - - - - - - - - 20202020 年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题 科目名称：计算机基础 （ A 卷 B 卷）科目代码：814 考试时间：3 小时 满分 150 分 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考
2、完后试题随答题纸交回。 一、一、简述题简述题（共（共 2 2 小题，每小题小题，每小题 1010 分，共分，共 2 20 0 分）分） 1、深度为 h=1 的二叉树至多有多少个结点，并给出简单证明。 2.具有 n=1 个结点的完全二叉树的深度是多少。并给出简单证明。 二、二、栈的应用栈的应用（2525 分）分） 1.给出栈的栈顶、栈底、空栈的定义。 （5 分） 2.给出判断空栈的算法(栈顶指针为 top)（5 分） 3 给出十进制转换成十六进制算法的 c 语言表述 （已知初始化栈函数 initstack(Stack *s)，判空栈的函数 Stackempty( Stack *s）返回值真或假，
3、入栈函数 push(Stack *s ,int e),出栈函数 pop( Stack *s, int *e)可以直接使用） 。 （15 分） 三、三、图的存储图的存储（30 分） 1.简述图的邻接表定义。 （5 分） 2.写出图 3-1 的邻接表（10 分） 3.给出利用数组存储邻接表的 c 语言形式描述（顶点数据类型 elemtype） （15 分） V1V5V3V4V236849 图图 3 3- -1 1 第 2 页 共 2 页 四、四、排序排序问题问题（2 25 5 分）分） 1.简述归并排序的算法思想。 （5 分） 2.简单论述使用二路归并排序方法对具有 n=1 个记录的文件的排序问题
4、。 （10 分） 3.给出序列（3,11,5,13,15,9,4）的二路归并过程（10 分） 五、计算题（五、计算题（共共 2 2 小题，每小题小题，每小题 1515 分，共分，共 3030 分分） 1.已知 X=-15，Y=+13，请用补码阵列乘法器计算 X Y。 2.在一个存储体系中，主存容量为 16MB，Cache 容量为 64KB，字长 1B，块大小为 4B，请确定直接映射方式的有关参数，并画出主存地址的格式。 六、分析题六、分析题（共共 2020 分分，共，共 8 8 空，每空空，每空 2.52.5 分分） 某 16 位机器所使用的指令格式和寻址方式如下页图所示，该机有两个 20 位
5、基址 寄存器，四个 16 位变址寄存器，十六个 16 位通用寄存器。指令汇编格式中的 S（源） ，D（目标）都是通用寄存器，M 是主存中的一个单元。三种指令的操作 码分别是： MOV（OP）=（0A）H， MOV 是传送指令； STO（OP）=（1B）H， STO 为存数指令； LAD（OP）=（3C）H， LAD 为取数指令。 15 10 9 8 7 4 3 0 OP 目标 源 15 10 9 8 7 4 3 0 OP 基址 源 变址 位移量 15 10 9 8 7 4 3 0 OP 目标 20 位地址 问下列情况下每个十六进制指令字分别代表什么指令，并填空。 （1） （2985)H 代表_指令；该指令为： _字长指令， _地址指令， _型指令。 （2） （6D3A)H (E2F0)H 代表_指令；该指令为： _字长指令， _地址指令， _型指令。 MOV S，D LAD M，D STO S，M
