科学院大学吉林省培养单位计算机原理历年考研真题汇编

单位计算机原理历年考研真题汇编2013年中国科学院大学吉林省培养单位866计算机原理考研真题2013年招收攻读硕士学位研究生入学统一考试试题1.本试卷满分为150分，全部考试时间总计180分钟。2.所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。一、单选题(每空3分，共45分)1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除一个元素，则采用最节省运算时间的存储方式是。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表2.链表不具有的特点是。A.插入、删除操作不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性表长度成正比3.设广义表L=((a,b,c)),则L的长度和深度分别是。4.在树的双亲表示法中，对树按层次编号，用数组进行存储，则下面说法不正确的是。A.兄结点的下标值小于弟结点的下标值B.所有结点的双亲可以找到C.任意结点的孩子信息可以找到D.下标值为i和i+1结点的关系是孩子和双亲5.对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作A.求一个顶点的邻接点B.求一个顶点的度C.深度优先遍历D.广度优先遍历6.含n个关键字的二叉排序树的平均查找长度主要取决于。A.关键字的个数B.树的形态C.关键字的取值范围D.关键字的数据类型7.下列排序算法中，其时间复杂度和记录的初始排列无关的A.折半插入排序B.堆排序C.快速排序D.冒泡排序A.存取独立B.存储程序C.流水处理D.并行处理10.某浮点数x按IEEE754标准表示其16进制存储格式为(C1360000)₁6,则其十进制数值为。A.相对寻址B.寄存器间接寻址C.变址寻址D.先相对后间接寻址12.一片容量为64k×8bit的SRAM存储器芯片，地址范围从0000H。13.CPU从主存中取出一条指令的时间为m,执行这条指令的时间为n,CPU的指令周期是。A.mB.nC.mtnD.时钟周期14.CPU从主存中读取一条指令字的最短时间称为。A.取址周期B.寻址周期C.指令周期D.机器周期15.在Cache和主存构成的二级存储体系中，Cache的存取时间是10ns,主存的存取时间为100ns,如果希望平均存取时间不超过主存存取时间的15%,则Cache的命中率至少为。二、简答题(每小题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]的起始地址是多少?xBCxExGH,CxDAxGHF,xDBxxFEA,但有些字母已模糊不清了(用x表示),试画出这颗二叉树。最少可达n,最多可达2n-1。归并过程中进行的元素比较次数分别达到最少和最多2)写出一般情况下，使归并所需进行的元素比较次数分别达到最少和最5.RISC指令系统的特点是什么?6.在一个分页虚存系统中，用户虚地址空间为32页，页长2KB,主存物理空间为16KB。已知某用户程序有7页长，虚页0、1、2、3已经分别被调入到主存7、4、5、1页中，求虚地址(0ED7)₁6和(2ED7)16对应7.分别说出SRAM和DRAM的工作机理，比较它们的优缺点。三、(20分)已知一颗树采用下列结点结构用孩子兄弟法表示：hd和hx的初值都为0。编写算法，将每个结点的后代结点数存入hd域，将每个结点所有右边的兄弟结点数存入hx域。四、(20分)已知无向图G有n个顶点(用1,2,…n表示),采用邻接表存储方式，试编写求图G的连通分量的算法。要求输出每一连通分量的顶点值。五、(15分)一台字长16位的计算机，有16个寄存器，主存容量为8M,具有无操作数、单操作数、双操作数三类指令，其中无操作数指令10个，单操作数指令20个，双操作数指令8个，1.操作码的位宽应是多少?2.RS型双操作数间接寻址所允许的最大寻址空间是多少?3.设计段寻址方式使段寻址可达整个主存空间?六、(15分)用若干个8x8RAM设计一个8位字长，容量32位的RAM,说明2012年中国科学院大学吉林省培养单位866计算机原理考研真题中国科学院研究生院2012年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机原理1.本试卷满分为150分，全部考试时间总计180分钟。一、填空题(每空2分，共36分)位置固定在哪一位都可以，但是通常将数据表示成或05.规格化的浮点数是指,使用IEEE754表示0.15625时，编码为,编码为(41360000)16的浮点数其十进制数值为。6.若按层次顺序给二叉树各结点从0开始编号，则含n个结点的完全二叉7.后缀表达式32*4-563/*+的值为,表达式对应的后缀表达式为。针域，其中个指针域存放了地址，而个指针域存放的是二、判断下列说法的正误，并纠正其中错误的说法(每小题3分，共18分)4.在一个包含n个元素的线性表中查找指定元素，采用折半查找比采用顺5.线性表的逻辑顺序和物理顺序总是一致的。6.假设高度为H的二叉树上只有度为0和度为2的结点，则该二叉树结点数的最大值为2#'。三、简答题(每小题5分，共30分)1.指令和数据都存放在内存中，计算机如何区分它们是指令还是数据?2.假设由S、E、M三个域组成的一个32位二进制数所表示的非0规格化浮点数x,其真值表示为x=(-1)⁵×(1.M)×28-128,则它所表示的规格化的最大正数、最小正数、最大负数、最小负数分别是多少?1XD程序计数器，请指出下表中的(1)~(6)分别为何种寻址方式。寻址方式1X有效地址E0000114.ASCⅡ码是7位，如果设计主存单元字长为32位，指令字长为12位，是否合理?为什么?5.一个用高级语言编写的程序在计算机上运行时所消耗的时间一般取决于哪些因素?什么是算法的时间复杂度?四、(15分)某机字长16位，使用4片74181组成ALU,设最低位序号标注为第0位。根据上述信息完成下列各题：1.(5分)写出第5位的进位信息C₆的逻辑表达式；2.(5分)估算产生C₆所需的最长时间：3.(5分)估算最长求和时间。现在再用一种RAM芯片(8K×8)形成40K×16位的RAM区域，起始地1.(7分)画出地址译码方案；2.(8分)画出ROM与RAM同CPU的连接图。六、(8分)试编写算法，计算七、(16分)求证：若一棵二叉树的先序序列是u,u₂,…,u,,则其中序序列是八、(12分)设有向图G采用邻接表方式存储，试设计一个算法，采用广度优科目名称：计算机原理2007年中国科学院大学吉林省培养单位866计算机原理考研真题2007年招收攻读硕士学位研究生入学统一考试试题1.本试卷满分为150分，全部考试时间总计180分钟。2.所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。数据结构部分(共75分)一、选择题(共20分，每题2分);AA444240B:科目名称：计算机原理5、一棵满3叉树，按层次遍历的方式存储在一维数组A[1…N]中，A、2mB、m+1C、2m-1D不能唯一确定0-11-41-62-33-44-25-26二、简答题(16分)(2)(4分)如果我们使用线性探测再Hash法为1000个元素设计Hash表，Hash函数的类型(3)(4分)下图表示的是一个三阶B-树，请画出在此树中插入值47后的结果。第2页第2页共6页(4)、(4分)假设科目名称：计算机原理计算机组成原理部分(共75分)一、填空题：(共25分)(1)(4分)冯·罗依曼计算机由()、()、()和()组成。冯氏机比起之前的计算装置最大的改进是()。早期的冯氏机以(心，现在的计算机是以()为中心，这种变化的主要原因是((分)在计算机中，浮点数不能够精确表示，产生这种误差的(浮点数IEEE754的编码为((3)(7分)已知CPU第4页第4页共6页假定一个应用程序被分配给4个物理页框，页面访问序列为1817827218()、主存地址格式为()主存地址48AB9H映射到Cache的()