2012中国科学院大学考研真题之计算机原理.pdf
科目名称:计算机原理 第 1 页 共 3 页 中国科学院研究生院 2012年招收攻读硕士学位研究生入学统一考试试题 科目名称: 计算机原理 考生须知: 1本试卷满分为 150分,全部考试时间总计 180分钟。 2所有答案必须写在答题纸上,写在试题纸上或草稿纸上一律无效。 一、 填空题 (每空 2分,共 36分) 1. 计算机系统是一个由 _和 _组成的复杂的自动化设备。 2. 按总线的逻辑结构来说,总线可分为 _和 _。 3. 所谓定点格式,即 _。原理上讲,小数点位置固定在哪一位都可以,但是通常将数据表示成 _或_。 4. _系统不仅是硬件设计的依据,而且是软件设计的基础,是衡量计算机性能的一个重要 因素 。 5. 规格化的浮点数是指 _,使用 IEEE754 表示0.15625时,编码为 _, 编码为 (41360000)16的浮点数其十进制数值为 _。 6. 若按层次顺序给二叉树各结点从 0 开始编号,则含 n 个结点的完全二叉树中叶结点的最小编号是 _。 7. 后缀表达式 3 2 * 4 5 6 3 / * + 的值为 _,表达式 c*(b+2)+(2-a)/3对应的后缀表达式为 _。 8. n个顶点的连通图至少有 _条边。 9. 用链式存储结构实现二叉树,每个结点除数据域外还包含指向左右子结点的链接指针,在这种存储结构下, n 个结点的二叉树共有 _个指针域,其中 _个指针域存放了地址,而 _个指针域存放的是空指针。 二、 判断下列说法的正误,并纠正其 中错误的说法(每 小 题 3分,共 18分) 1. 在有向图中,所有结点的出度之和等于入度之和。 2. 从一个小根堆中查找具有给定键值的元素,在最坏情况下需要 lgn 次比较操作。 科目名称:计算机原理 第 2 页 共 3 页 3. Huffman树的结点个数一定是偶数。 4. 在一个包含 n 个元素的线性表中查找指定元素,采用折半查找比采用顺序查找所需时间少。 5. 线性表的逻辑顺序和物理顺序总是一致的。 6. 假设高度为 H的二叉树上只有度为 0和度为 2的 结点 ,则该二叉树结点数的最大值为 2H-1。 三、 简答题 (每小题 5分,共 30分) 1. 指令和数据都存放在内存中,计算机如何区分它们是指令还是数据? 2. 假设由 S、 E、 M 三个域组成的一个 32 位二进制数所表示的非 0 规格化浮点数 x,其真值表示为 x = (-1)S (1.M) 2E-128 ,则它所表示的规格化的最大 正 数、最小 正 数、最大负数、最小负数分别是多少? 3. 一种单地址指令格式如下所示: OP I X D 其中 I 为间接特征, X 为寻址模式, D 为形式地址。 I、 X、 D 组成该指令的操作数有效地址 E。设 R 为变址寄存器, R1为基址寄存器, PC 为程序计数器,请指出下表中的 (1)(6) 分别为何种寻址方式。 寻址方式 I X 有效地址 E (1) 0 00 E=D (2) 0 01 E=(PC)+D (3) 0 10 E=(R)+D (4) 0 11 E=(R1)+D (5) 1 00 E=(D) (6) 1 11 E=(R1)+D), D=0 4. ASCII 码是 7 位,如果设计主存单元字长为 32 位,指令字长为 12 位,是否合理?为什么? 5. 一个用高级语言编写的程序在计算机上运行时所消耗的时间一般取决于哪些因素?什么是算法的时间复杂度? 6. 画出和下列已知 访问 序列对应的 森林 : 森林 的先 序 次序访问序列为: NHMCLIBKDFJEAG; 森林 的 中 序 次序访问序列为: MCHLNBIFDJAGEK。 四、 ( 15分)某机字长 16位,使用 4片 74181组成 ALU,设最低位序号标注为第 0位。根据上述信息完成下列各题: 1. ( 5分)写出第 5位的进位信息 C6的逻辑表达式 ; 2. ( 5分)估算产生 C6所需的最长时间 ; 3. ( 5分) 估算最长求和 时间。 科目名称:计算机原理 第 3 页 共 3 页 五、 ( 15分)某机器中,已知配有一个地址空间为 0000H3FFFH的 ROM区域,现在再用一种 RAM芯片( 8K 8)形成 40K 16位的 RAM区域,起始地址为 6000H。假设 RAM芯片有 CS和 WE 信号控制端, CPU的地址总线为A15A0,数据总线为 D15D0,控制信号为 R/W(读 /写)、 MREQ (访存)。基于上述信息,请完成下列各题: 1. ( 7分)画出地址译码方案; 2. ( 8分)画出 ROM与 RAM同 CPU的连接图。 六、 ( 8 分)试编写算法,计算 i!2i (i=0,1, ,n-1) 的值并依次存入整数数组aMAXSIZE中。假设计算机中允许的最大整数为 MAXINT。 七、 ( 16 分)求证:若一棵二叉树的先序序列是 nuuu , 21 ,则其中序序列是nppp uuu , 21 当且仅当序列 n,2,1 可通过一个栈得到序列 nppp , 21 。 八、 ( 12 分)设有向图 G 采用邻接表方式存储,试设计一个算法,采用 广度优 先搜索 判断 图中是否存在由顶点 vi到顶点 vj的路径 ,若存在则将该路径打印出来。