北科大2007年《计算机组成原理及数据结构》考研真题.pdf

北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-);咨询QQ:2696670126:6-/北京科技大学2007年硕士学位研究生入学考试试题试题编号：416试题名称：计算机组成原理及数据结构（共4页）适用专业：计算机科学与技术说明：所有答案必须写在答题纸上，做在试题或草稿纸上无效第一部分计算机组成原理（共75分)、填空题（每空1分，共10分)1.冯-诺依曼体制思想的核心是采用存储程序方式，它是指2.计算机的软、硬件在功能上的等价是指3.计算机总线按其任务可分为四种，它们分别是4.机器数是指在计算机中使用的5.请写出十进制数125.125的二进制表示6.主机与外部设备间的连结模式大致可分为三类，它们是7.磁盘的存取时间可以用三个指标来描述，这三个指标分别是8.对磁盘进行格式化的目的是么9.相联存储器是种按寻址的存储器。10.DMA传送方式中的周期挪用方式是指二、问答题（每题5分，共25分）1.总线的共享和分时分别指什么？总线的数据通路是如何定义的？2.请说明双端口存储器的工作原理？3.写出Cache的Write-.Through方式的工作过程。4.请写出页式虚拟存储器的虚实地址转换的工作原理。5.在计算机的时序控制方式中可分为同步控制与异步二大类型，请问它们各有什么优缺点？三、综合题（每题10分，共40分）(注意：统考生做下列的1,2,3,4题；单考生做下列的3,4,5,6题)1.利用与非门电路，设计一个能处理三个独立中断源请求的判优电路。（要求写出具体设计说明)2.假设某机器的指令长度为16位，包括4位基本操作码字段和三个4位地址段，请设计具有15条三地址指令，14条二地址指令，31条一地址指令和16条零地址的指令格式。第1页北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-)；咨询QQ:2696670126w0:e6-35.主机与外围设备按串行方式传送时，需要对通信双方做哪些约定？如果按起始位一位，数据位7位，偶校验位一位，停止位一位，请画出十六进制数43丑的波形图。6.一个(7,4)码(CRC码7位，其中4位信息位)，求C(X)=1100的CRC码：并指出当余数为101时，是哪位出错。生成多项式G(X)=1011。第二部分数据结构（共75分)注：统考生做第一、二、三、四题；单考生做第一、二、三、五题。一。(18分)回答下列各题1.简述“层次”类型的数据结构的特点。2.设双向循环链表中结点的前驱和后继指针域分别为pre和ext,指针p为表中某一结点的地址，请写出在p结点之后插入一s绪点的C语言描述语句。3.设A345为C语言中的-个三维数组，A在存储器中的起始地址0C(A00O)=1000,每,个数组元素占4个地址单元，则L0C(A234)-?4.设度为3的树中叶结点数为n0,出度为23的结点数分别为2和3，请指出n0与n2、n3之间的关系。5.如何根据“拓扑排序”方法判断一个有向图是否存在回路？6.在构造Hash表的过程中，通常有哪几种处理“冲突”的方法？02二.(16分)算法填空用中序逸历方法”求灵划中非叶结点个数的算法如下其中为2叉制根结点的指针，Clearstack(S)Emptystack(Sush(s,p、Pop(S)分别为置栈空判栈空进栈、出栈的函数，stype为栈的类型。请填充算法中下画线的空白之处，完成其功能（请将答案写在答题纸上）。typedef struct nodeint data;struct node*Lchild,*Rchild.bnode,*blink;int Inorderc(blikblink p;int n0;stype S;)return(0);0 learstack(s)月while(p!Emptystack(S)while(Push(S,p);；p=Pop(S);if(第3页北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-);咨询QQ:2696670126No:Gib-三.(21分)一个无向图G的邻接多重表如下：0Vo032V24115com1.请画出此图的逻辑结构并等出其邻接矩阵；2.写出从项点V出发、按照“深度优先”和“广度优先”搜索方法遍历图G所得到的顶点序列：3.若边(Vo,八(V,V人WVoV2,V)、(VnV,)上的权值分别为5、2、1、4、3,6按照求最小生成树的m算法，从V,出发，画雷G的一棵最小生成树（中间过程省略画出最终的最小生成树即可。四.(20分此题统考生做)给定表(AN0,AH,A可)，其中A0)为整数。用C语言函数形式写出完成下列任务的算法：1.依次取A的(0ix建立个带头结点的单链表：2.对该链表用“插入排序”方法按升序排序。注：算法前应写出单链表结点类型的描述：完成两个任务的算法可写成一个函数，也可分别写出，算法名（或函数名）自定。五.(20分此题单考生做)设A、B分别为两个带头结点单链表的头指针，且各表中结点数据集为整数集合。用C语言函数形式写出求表A和表B的差集的算法：difference(A,B)。第4页