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

北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(wwW.e-)；咨询QQ:2696670126恤：b-1北京科技大学2008年硕士学位研究生入学考试试题试题编号：816试题名称：计算机组成原理与数据结构（共3页)】适用专业：计算机科学与技术说明：所有答案必须写在答题纸上，做在试题或草稿纸上无效。第一部分计算机组成原理（共75分)填空题（每题2分，共20分）1典型的数字计算机硬件由五大部分组成，即控制器、输入设备和输出设备。2程序计数器PC就象一个指针，一直指示着程序的也就是指示控制流的形成。3操作系统属于系统软件，它负责和计算机系统硬软资源与运行程序。4微程序类似于软件，在逻辑功能上讲，它属于的范畴。5总线的数据通路宽度指的数据位数。6通常，一条指令能实现一次定点加减运算，所以PS值大致相当于每秒钟能完成的运算次数。7存储进位加法器的基本思想是：在同一级加法器中将进位信息暂时保留，留待再处理。8面向虚拟存储器的地址称为虚拟地址，或称逻辑地址。9在常见的指令系统中操作码格式大致有以下三种：定长操作码、操作码，。方式码。10一条指令一般应提供两方面的信息：操作码和二问答题（每题5分，共35分）1请写出动态存储器集中刷新方式和分散刷新方式的区别？2更新Cache内容的替换算法有FFO和LRU种，请写出LRU的基本思想。3温彻斯特技术最主要的特征有哪些？4主机与外部的数据通路间的信息传送控制方试分别有哪三种类型？5”列.e-请画出单存储体重叠处理方式示意图。6请写出微指令编码方式的类型7请写出向量中断的响应方式。三综合题（每题10分，h(注意：统考生做下列的3,4题；单考生做下列的1,2题)1写出下列各数的原码、反码和补码。1)-352)23641282举例说明一种键码形成的方法。3写出段式虚拟存储器的虚实地址转换过程。4根据所给模型机的数据通路图，请设计执行下列指令的指令流程图AND(R),-(Re)(R1)为目的操作数。第1页北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-);咨询QQ:26966701260:Pb-2地址总线内总线数据总线控制总线移位CPRO_ROMAR移位器1/0控制CPMAR EMARCPR1RlMBR主存M功能CPMBR控制SMBRCPR2R2IRSIRA8CPR3R3PC选择CPPC控制选择器A选择器B选择控制CPCPSWCPPSW避入不R0-R3R0-R3C DCPDDSPCPSP控制逻辑SP PCPSW MBR0%模型机数据通路框图第二部分“数据结构”75分注：统考生做第、三四题：单考生做第Q、三、五题。(18分)回答下列各题Jo心1.数据的逻辑结构在计算机存储器中的映象（或表示）通常有哪几种方法？2.一个算法一般包括哪5个特性？3.对栈和队列进行“插入”和“删除”操作分别应遵循什么原则？4.一棵h(h1)层的k(k心1)叉树最大节点数S=?5.无向图的“连通分量”和有向图的“强连通分量”分别指的是什么？6.对含有(0)个记录的文件按“直接插入排序”和“堆排序”算法#序时，其时间复杂度分别如何？二.(18分)算法填空用C语言函数形式描述的、将两个带头节点单链表合并的算法如下，其中A、B分别为待合并链表的头指针，结果链表的头指针仍由A指出（注：若两表中有数据值相同的节点，只保留其中一个）。请填充算法中下画线的空白之处，完成其功能（请将答案写在答题纸上）。typedef struct nodeint data;struct node*next;linknode,*link;void Union(link A,link B)link qp,pl,u;q=B-next;free(B);p1=A-next;while(。)p=pl;第2页北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(ww.e-)；咨询QQ:26966701260:b-3while()p=p-next;if(u=q-next;i9uelse u=q;free(u);三.（21分)设无向网G如下：24v23352v3v4v51.请写出网G的邻接矩阵、画出网G的邻接表结构：2.1写出从顶点v0出发、按照“深度优先”和“5度优先”搜索方法遍历网G所得到的顶点序列：3.从顶点v1出发，按照求最小生成树的Pm算法，画出网G的一棵最小生成树（中间过程省略，画出最终的最小生成树即可)。四.(18分此题统考生做)给定表(AO,A,Aa1),其中A(01n为整数，请用C语言函数形式写出完成下列任务的算法：1.依次取A0in-1),建立裸上叉排序树（不要求平衡）：2.按照中序遍历二叉树的递归方法，输出（或打印）该二叉排序树的中序遍历序列。注：算法前应写出二叉排序树节点类型的描述；完成两个任务的算法可分别写出，算法名（或函数名)自定。五.(18分此题单考生做)给定整数型数组（A1,A2,An),n1，请用C语言函数形式写出将此数组调整成一个小根堆的算法，算法名（或函数名）自定。注：若数组中各值满足A)A2i,A门A2i+1,=1,2,n/2时，将其视为-个小根堆。第3页