北京中国科学院大学2013年考研计算机原理真题.doc

发布时间：2022-09-15 发布人：admin 分类：说明书资料大小：0.03M 资料格式：doc 举报版权申诉

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

文本预览

（北京）中国科学院大学 2013 年考研计算机原理真题中国科学院大学 2013 年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机原理考生须知： 1．本试卷满分为 150 分，全部考试时间总计 180 分钟。 2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。一、单选题（每空 3 分，共 45 分） 1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除一个元素，则采用最节省运算时间的存储方式是_____ 。 A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 2. 链表不具有的特点是 _____。 A. 插入、删除操作不需要移动元素 B. 可随机访问任一元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比 3. 设广义表 L=（（a，b，c）），则 L 的长度和深度分别是 _____。 A．1 和 1 B. 1 和 3 C. 1 和 2 D. 2 和 3 4. 在树的双亲表示法中，对树按层次编号，用数组进行存储，则下面说法不正确的是_____ 。 A. 兄结点的下标值小于弟结点的下标值 B. 所有结点的双亲可以找到

C. 任意结点的孩子信息可以找到 D. 下标值为 i 和 i+1 结点的关系是孩子和双亲 5. 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为_____ 。 A. 求一个顶点的邻接点 B. 求一个顶点的度 C. 深度优先遍历 D. 广度优先遍历 6. 含 n 个关键字的二叉排序树的平均查找长度主要取决于_____ 。 A. 关键字的个数 B. 树的形态 C. 关键字的取值范围 D. 关键字的数据类型 7. 下列排序算法中，其时间复杂度和记录的初始排列无关的是_____ 。 A. 折半插入排序 B. 堆排序 C. 快速排序 D. 冒泡排序 8. 在 Hash 函数 H(k)=k MOD m 中，一般来讲，m 应取 _____。 A. 奇数 B. 偶数 C. 素数 D. 充分大的数 9. 冯•诺依曼计算机体系结构的基本思想是：_____ 。 A. 存取独立 B. 存储程序 C. 流水处理 D. 并行处理 10. 某浮点数 x 按 IEEE754 标准表示其 16 进制存储格式为 (C1360000)16，则其十进制数值为_____ 。

A. 11.375 B. -11.375 C. -4.6875 D. 4.6875 11. _____ 方式访问存储器速度最慢。 A. 相对寻址 B. 寄存器间接寻址 C. 变址寻址 D. 先相对后间接寻址 12. 一片容量为 64k×8bit 的 SRAM 存储器芯片，地址范围从 0000H 到_____ 。 A. ffffH B. 7fffH C. 7ffffH D. fffffH 13. CPU 从主存中取出一条指令的时间为 m，执行这条指令的时间为 n，CPU 的指令周期是 _____。 A. m B. n C. m+n D. 时钟周期 14. CPU 从主存中读取一条指令字的最短时间称为_____ 。 A. 取址周期 B. 寻址周期 C. 指令周期 D. 机器周期 15. 在 Cache 和主存构成的二级存储体系中，Cache 的存取时间是 10ns，主存的存取时间为 100ns，如果希望平均存取时间不超过主存存取时间的 15%，则 Cache 的命中率至少为 _____ 。 A. 85% B. 5% C. 95% D. 15%

二、简答题（每小题 5 分，共 35 分） 1. 设有 5 个元素，其进栈次序为 A、B、C、D、E，在各种可能的出栈序列中，第一个出栈元素是 C 且第二个出栈元素是 D 的出栈序列有哪几个？ 2. 数组 A[-1..9,1..11]中，每个元素的长度为 32 位，从首地址 S 开始连续存放在主存储器中，主存储器字长为 16 位。求： 1）存放该数组需要多少单元？ 2）存放该数组第 4 列所有元素至少需要多少单元？ 3）数组按行存放时，元素 A[7][4]的起始地址是多少？ 4）数组按列存放时，A[4][7]的起始地址是多少？ 3. 已知一颗二叉树的先序遍历序列、中序遍历序列和后续遍历序列分别为： xBCxExGH，CxDAxGHF，xDBxxFEA，但有些字母已模糊不清了（用 x 表示），试画出这颗二叉树。 4. 当将两个长度为 n 的有序表 A=(a1,a2,…..,an)与 B=(b1,b2,….,bn)，(ai≠bj,1 ≤i, j≤n)归并为一个有序表 C=(c1,c2,…,c2n)时，所需进行的元素比较次数最少可达 n，最多可达 2n-1。 1）假设有序表 C=(2,4,5,6,7,9)，试举出两组 A 与 B 的例子，使它们在归并过程中进行的元素比较次数分别达到最少和最多； 2）写出一般情况下，使归并所需进行的元素比较次数分别达到最少和最多时，A 与 B 中的元素应满足的条件。 5. RISC 指令系统的特点是什么？ 6. 在一个分页虚存系统中，用户虚地址空间为 32 页，页长 2KB，主存物理空间为 16KB。已知某用户程序有 7 页长，虚页 0、1、2、3 已经分别被调入到主存 7、4、5、1 页中，求虚地址 (0ED7)16 和 (2ED7)16 对应的物理地址。 7. 分别说出 SRAM 和 DRAM 的工作机理，比较它们的优缺点。三、（20 分）已知一颗树采用下列结点结构用孩子兄弟法表示： FirstChild hd data hx NextSibling 其中，data 为数据域，FirstChild 为左链域，NextSibling 为右链域，hd 域用于存放该结点的后代结点数，hx 域用于存放该结点所有右边的兄弟结点数。hd 和 hx 的初值都为 0。编写算法，将每个结点的后代结点数存入 hd 域，将每个结点所有右边的兄弟结点数存入 hx 域。

四、（20 分）已知无向图 G 有 n 个顶点(用 1,2,…n 表示)，采用邻接表存储方式，试编写求图 G 的连通分量的算法。要求输出每一连通分量的顶点值。五、（15 分）一台字长 16 位的计算机，有 16 个寄存器，主存容量为 8M，具有无操作数、单操作数、双操作数三类指令，其中无操作数指令 10 个，单操作数指令 20 个，双操作数指令 8 个， 1. 操作码的位宽应是多少？ 2. RS 型双操作数间接寻址所允许的最大寻址空间是多少？ 3. 设计段寻址方式使段寻址可达整个主存空间？

分享到：

赞收藏

资料库

北京中国科学院大学2013年考研计算机原理真题.doc

相关推荐

考研

热门标签

最新资料