考研计算机学科专业基础综合

考研计算机学科专业基础综合-7-2一、单项选择题（总题数：40,分数：80.00）在OSI参考模型中，会话层使用（）层的服务来完成自己的功能。物理层数据链路层网络层传输层V在OSI参考模型中，每一层使用它下层的服务来完成自己的功能，在会话层下面是传输层，所以会话层采用传输层的服务来完成自己的功能。如果二叉树T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的（）。先序V中序后序层次序一般树中一个结点的孩子是无序的，所谓有序树是指树中任一结点的孩子是有序的。由树转换成二叉树的过程可知本题答案为A。某计算机主存容量为64KB，其中ROM区为4KB，其余为RAM区，按字节编址。现要用2KX8位的ROM芯片和4KX4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是（）。TOC\o"1-5"\h\z1、152、151、302、30V根据题意可知，该机主存由4KX8位ROM和60KX8位RAM组成；又现有ROM芯片为2KX8位，故ROM需进行字扩展，用2片2KX8位ROM串联组成4KX8位ROM；RAM芯片为4KX4位，故RAM需进行位字扩展，用2片4KX4位RAM并联构成4KX8位RAM，再用15片4KX8位RAM串联组成60KX8位RAM，即共需2X15=30片4KX4位的RAM芯片。某机字长32位，其主存储器容量为64MB，按字节编址，则该计算机的主存地址寄存器和主存数据寄存器的位数分别为（）。26，3226，8V22，32无法确定主存按字节编址，64MB=22X8位，故主存地址寄存器为26位，主存数据寄存器为8位。下列关于进程的叙述，（）是最不符合操作系统对进程的理解。进程是在多程序并行环境中的完整的程序V进程可以由程序、数据和进程控制块描述线程（THREAD）是一种特殊的进程进程是程序在一个数据集合上运行的过程，是系统进行资源管理的一个独立单位A的说法片面。浮点加减运算结果满足（）时，应作“机器零”处理。尾数为“全0”阶码上溢阶码下溢A或者CV当尾数为“全0”时，不论阶码为何值，该浮点数真值都为0，应作“机器零”处理；当阶码下溢时，说明浮点数的真值小于该机可以表示的最小值，也应作“机器零”处理，故选D。指令系统中设置多种不同的寻址方式，可以（）。缩短指令字长扩大寻址空间提高编程灵活性以上都包括V指令中设置多种寻址方式可以使程序员编程更加灵活，采用寄存器寻址等方式可以缩短指令字长，采用间址寻址等可以扩大指令寻址空间，故A、B、C选项的内容都正确，选D。下列关于并行微程序控制器的说法正确的是（）。现行微指令的执行与取下一条微指令的操作并行V现行微指令的执行与取下一条微指令的操作串行两条或更多微指令的执行在时间上并行两条或更多微指令的取微指令操作在时间上并行并行微程序控制器中，在执行现行微指令的同时，取下一条微指令，A选项的描述正确。下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。堆排序冒泡排序快速排序直接插入排序V直接插入排序在巳经排序好的序列的适当位置上插入关键字，因此可能需要移动元素。操作系统为了管理文件，设计了文件控制块（FCB）。FCB是执行系统调用（）时建立的。createopenVreadwrite文件控制块是调用OPEN时建立的。某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节PC自动加1。若某转移指令所在主存地址为2000H，相对位移量字段的内容为06H，则该转移指令成功转移以后的目标地址是（）。TOC\o"1-5"\h\z2006H2007H2008HV2009H相对寻址通过将形式地址与程序计数器PC的内容相加得到有效地址，即EA=（PC）+A；又机器字长16位，主存按字节编址，故该转移指令取出后的PC值为2000H+2=2002H；所以该转移指令成功后的目标地址为06H+2002H=2008H，选C。页面置换算法（）可能会产生Belady异常现象。先进先出算法FIFOV最近最少使用算法LRU利用referencebit的近似的LRU最优算法Optimal先进先出算法会出现Belady异常。在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点在A，并巳知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应进行（）型调整以使其平衡。TOC\o"1-5"\h\zLLLRVRLRR由题意可知，A的平衡因子为1，又由于A的左孩子的平衡因子为-1，右孩子的平衡因子为0，由此可知，A的左孩子上仅有右孩子，A的右孩子上无左右孩子，在平衡二叉树中插入一个结点后造成不平衡，说明插入结点只能插在A的左孩子的右孩子上，这种情形属于在左子树的右子树上插入结点的情形，即LR型。指出在顺序表F={2,5,7,10,14,15,18,23,35,41,52}中，用二分查找法查找12需要进行多少次比较（）。TOC\o"1-5"\h\z234V5参考二分查找法。为了在通用操作系统管理下的计算机上运行一个程序，需要经历几个步骤，但是，（）不是一定需要。向操作系统预定运行时间V将程序装入内存确定起始地址，并从这个地址开始执行指令用控制台监控程序执行过程实时系统才需要预定CPU时间。要发送的数据是1101011011，采用CRC校验，生成多项式是10011,那么最终发送的数据应该是（）。A.11010110111010B.11010110110110C.11010110111110VD.11110011011100根据给出的除数，用11010110110000除以10011,得到的冗余码为1110，添加在原来数据的最后发送出去。CPU响应中断时需要保护断点，断点指的是（）。中断服务程序的入口地址程序计数器PC的内容VCPU内各寄存器的内容指令寄存器IR的内容CPU在一条指令执行结束时响应中断，断点指的是程序计数器PC的内容，也就是现行程序下一条将要执行指令的地址。在TELNET协议中，用户发送的命令采用TCP传输到服务器，在TCP的数据包中，需要把（）符号位置移位，从而使服务器尽快响应命令。SYNURGPSHVRSTPSH位表示带有PUSH标志的数据，接收方在收到数据后应该立即请求将数据递交给应用程序，而不是将它缓存起来。现在可以使用（）来编写Web页面。HTTPHTMLVMIME：XMLHTML（超文本标记语言）是用来描述格式化文档的语言，用来编写Web页面。我们知道，有些CPU指令只能授权给操作系统内核运行，不允许普通用户程序使用，但是，以下操作中，（）可以不必具有此种特权。设置定时器初值触发trap指令V内存单元复位关闭中断允许位trap命令的一种常见用途是在脚本程序被中断时完成清理工作。在一个双链表中，删除p结点之后的一个结点的操作是（）。p-〉next=p-〉next-〉next；p->next->next->prior=p；p-〉next-〉prior=p；p->next=p->next->next；p->next=p->next->next；p->next->prior=p；Vp->next->next=p->next；p->next->prior=p；（1）p结点的后继结点指向p结点原来后继结点的后继结点，（2）更新后的p结点的后继结点的前驱结点指向P。一个以太网的帧数据长度为20字节，那么它的填充域长度是（）。0字节23字节45字节26字节V以太网要求帧的最小长度是64字节，源地址、目标地址、类型和校验及域占用了18个字节，那么一个有20字节数据的以太网帧的长度就是38字节，还需要填充26字节。两个站点之间的距离是10000km，信号在媒体上的传播速率为2X108m/s，线路的带宽是10kbps，现在发送一个3KB的数据包，那么需要（）时间使得接收方收到数据。TOC\o"1-5"\h\z0.35sV0.45s0.85s1.35s数据发送分为发送延时和传输延时。在题目中发送延时为3000/10000=0.3s。传播延时为10000/200000000=0.05s，所以总共需要0.35s来传输该数据包。一个网络的物理线路上抓到011001位串的波形如下：请问该线路采用了（）编码方式。二进制编码曼彻斯特编码V差分曼彻斯特编码归零编码曼彻斯特编码每一周期分为两个相等的间隔。二进制“1”位在发送时，在第一个间隔中为高电压，在第二个间隔中为低电压。二进制“0”正好相反。两个合作进程无法利用（）交换数据。数据库消息传递系统共享内存高级语言程序设计中的全局变量V两个进程各自拥有自己的程序段和数据段，即有各自的全局变量，所以不可能通过全局变量交换数据。26.8位二进制无符号整数可表示的数值范围是（）。0〜255V-128〜+127-127〜+1271〜2568位二进制无符号整数可表示的数值范围为0〜28-1，即0〜255。冯•诺依曼计算机的最根本特征是（）。以存储器为中心采用存储程序原理V存储器按地址访问数据以二进制编码，并采用二进制运算存储程序原理是冯•诺依曼计算机的基础，也是最根本特征。下面关于虚拟存储管理的论述中，正确的是（）。为了能让更多的进程同时运行，可以只装入10%〜30%的进程映像，即启动运行V最佳页面置换算法是实现页式虚拟存储管理的常用算法即使在多用户环境下，用户也可以运用机器指令访问任一合法的物理地址为了提高内存保护的灵活性，内存保护通常由软件完成B：最佳页面置换不是页式虚拟存储管理的常用算法，实现的代价较大；C：在多用户环境下，系统应该对用户各自的数据和指令加以保护；D：内存保护通常由硬件完成，基址寄存器和界限寄存器等。主机甲和主机乙间巳建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是（）。TOC\o"1-5"\h\z5007008001000V总共发送了1000个字节，所以主机乙发送给主机甲的确认序号应该是1000。一个文件的绝对路径名是从（）开始，逐步沿着每一级目录向下追溯，最好到指定文件的整个通路上所有子目录组成的一个有序组合。当前目录根目录V家目录（homedirectory）磁盘驱动器编号本题考查文件路径的概念。在由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为（）。TOC\o"1-5"\h\z2029V3035下列4组含C1〜C7的结点序列中，（）是下图所示的有向图的拓扑序列。A.C1，C2，C6,C7，C5，C4，C3B.C1，C2，C6,C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，Cl，C2，C6，C7V参考拓扑排序的算法。下列文件物理结构中，适合随机访问且易于文件扩展的是（）。连续结构索引结构V链式结构且磁盘块定长链式结构且磁盘块变长索引结构适合随机访问且易于文件扩展。微程序存放在CPU的哪个部件中（）。主存储器存储器控制器控制存储器V辅助存储器微程序存放在控制存储器中，选C。注意区别存控与控存的区别，控存用来存放微程序，而存控是用来管理协调CPU、DMA控制器等对主存储器访问的部件。动态ROM的刷新以（）为单位。位字节行V整个ROM动态ROM的刷新以行为单位。高度为5(除叶子层之外)的三阶B-树至少有()个结点。TOC\o"1-5"\h\z3031V3233由m阶B-树性质可知，根结点至少有两棵子树，根结点之外的所有非终端结点至少有m/2棵子树：则三阶B-树的形状至少类似于一棵满二叉树，也即高度为5的三阶B-树至少有(25-1=)31个结点。设二维数组A[6][10],每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址为()。1000VTOC\o"1-5"\h\z86011401200860+(3*10+5)*4=1000。下列排序算法中，时间复杂度不受数据初始状态影响恒为O(nlogn)的是()。堆排序V冒泡排序快速排序直接插入排序只有A和C是O(nlogn)的复杂度，但是快速排序在“最坏”的情况下蜕化为冒泡排序，其时间复杂度为O(n2)。对某一给定的程序，具有最高命中率的Cache替换算法是()。先进先出替换算法最近最少使用替换算法随机替换算法无法确定V选项中三种替换算法，平均来说LRU替换算法命中率最高，但对于某一个特定的程序，无法确定哪种替换算法命中率最高。下面关于设备属性的论述中，正确的是()。字符设备的基本特征是可寻址到字节，即能指定输入的源地址或输出的目标地址共享设备必须是可寻址和可随机访问的设备V共享设备是同一时间内允许多个进程同时访问的设备在分配共享设备和独占设备时都可能引起进程死锁可寻址是块设备的基本特征，故A不对。共享设备是指一段时间内允许多个进程同时访问的设备，在同一时间内，即对某一时刻共享设备仍然只允许一个进程访问，故C不正确。分配共享设备是不会引起进程死锁的，故D不正确。二、综合应用题(总题数：2,分数：70.00)某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和汽车类，上渡船有如下规定：同类车先到先上船，客车先于货车上船，且每上4辆客车，才允许上一辆货车，若等待客不足4辆，则以货车代替，若无货车等待允许客车都上船。写一算法模拟渡口管理。假设q数组的最大下标为10，恰好是每次渡载的最大量。假设客车的队列是q1，货车的队列是q2。算法如下：voidManager(Sqqueue*q,Squeue*q1，Squeue*q2){elemtypexintj=0，i=0；while(j<10){if(!empty(q1)&&i<4){x=q1-〉data[q1-〉front]；q1-〉front=q1-〉front+1；q-〉rear=q-〉rear+1；q-〉data[q-〉rear]=x：i++；j++；}if((i==4)&&!empty(q2)){x=q2-〉data[q2->front]；q2-〉front=q2-〉front+1；q-〉rear=q-〉rear+1；q-〉data[q-〉rear]=x：j++；i=0：}if(empty(q2)&&!empty(q1))i=0：}}某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路即可），并要求增设的道路条数为最少，要解决这个问题，问：（分数：60.00）（1）.可用什么数据结构来表示城镇和道路；（分数：4.00）用图结构表示，其中顶点表示城镇，顶点之间路径表示道路。（2）.请用伪代码描述效率最高的解法。（分数：4.00）这个应该是特殊(道路权重为1)的prim算法。采用邻接表结构，顶点结构包括：known表示时候巳经加入，dist表示到起点的道路条数，path表示相连的城镇。算法如下：voidunweight(TableT){QueueQ；Vertexv，w；Q=CreateQueue(NumVertex)；MakeEmpty(Q)；Enqueue(S，Q)；//s表示起点，可为任一城镇。While(!IsEmpty(Q)){V=Dequeue(Q)；T[V].Known=True；ForeachwadaicenttovIf(T[-w].Dist==Infinity){T[w].dist=T[v].dist+1；T[w].path=v；Enqueue(w，Q))}DisposeQueue(Q)；}dfstravrese(G，visit(intv)){booleanVisited[MAX]；initstack(S)；for(v=0；v<=G.maxvexnum；v++)Visited[v]=FLASE：for(v=0；v<=G.maxvexnum；v++)if(Visited[v]==FLASE){push(s，v)；DFS(G，；}while(!Stackempty(S)){printf("%d”，v)；}DFS(G，w){Visited[w]=TRUE：for(firstadjvex(G，w)；w〉-0；w=nextadjvex(G，w)){Visited[w]=TRUE：；}}.画出主存地址空间分配示意图；(分数：4.00)主存地址空间分配示意图如下所示。（4）.说明使用存储芯片的种类及数量;（分数：4.00）根据题目要求，使用2片2KX4位ROM位扩展构成2KX8位系统程序区；使用1片4KX8位RAM和1片8KX8位RAM构成12KX8位用户程序区。（5）.使用所给门电路画出存储芯片片选逻辑图（片选信号低电平有效）。（分数：4.00）片选逻辑图如下，片选信号CS0同时选中2片2KX4位ROM，片选信号CS〔选中1片4KX8位RAM，片选信号CS2选中1片8KX8位RAM。（6）.该流水线的加速比为多少？（分数：4.00）流水线的节拍时间应取各过程段所需时间的最大值，即100ns，该流水线的加速化为（80ns+100ns+60ns+90ns）/100ns=3.3（7）.若四个过程段的执行所需时间都为85ns，则加速比又为多少？（分数：4.00）如四个过程段所需执行时间都为85ns，则流水线的节