2023年研究生类研究生入学考试专业课计算机学科专业综合基础历年真题荟萃带答案难题附详解荟萃

2023年研究生类研究生入学考试专业课计算机学科专业综合基础历年真题荟萃带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共60题)1.在以下的文件物理存储组织形式中，______常用于存放大型的系统文件。A.连续文件B.串联文件C.索引文件D.多重索引文件2.证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。3.试分析，在第一级磁盘容错技术和第二级磁盘容错技术中，各采取了哪些容错措施?什么是写后读校验?4.死锁预防是保证系统不进入死锁状态的静态策略，其解决办法是破坏产生死锁的4个必要条件之一。下列方法中破坏了“循环等待”条件的是______。A.银行家算法B.一次性分配策略C.剥夺资源法D.资源有序分配策略5.某公司网络的地址是/17，下列选项中，______一定属于这个网络。A./17B./20C./16D./206.设有整数0～n-1存放在整型数组A[0，…，n-1]中，请设计一个时间复杂度为O(n)，且只用常量空间复杂度O(1)的算法来实现对A的排序(要求按从小到大排序)。7.下图是一个简化的CPU与主存连接结构示意图(图中省略了所有多路选择器)。其中有一个累加寄存器AC、一个状态寄存器和其他四个寄存器(主存地址寄存器MAR、主存数据寄存器MDR、程序计数器PC和指令寄存器IR)，各部件及其之间的连线表示数据通路，箭头表示信息传送方向。

要求：

(1)写出图中a、b、c、d四个寄存器的名称。

(2)简述图中指令从主存取到控制器的过程。

(3)说明数据从主存取出、运算、写回主存所经过的数据通路(假定数据地址已在MAR中)。8.如果到达的分组的片偏移值为100，分组首部中的首部长度字段值为5，总长度字段值为100。请问：数据部分第一个字节的编号是多少?能够确定数据部分最后一个字节的编号吗?9.CPU响应中断的时间是

。A.中断源提出请求B.取指周期结束C.执行周期结束D.间址周期结束10.下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是______

Ⅰ．插入排序

Ⅱ．选择排序

Ⅲ．起泡排序

Ⅳ．希尔排序

Ⅴ．堆排序A.仅Ⅰ、ⅡB.仅Ⅱ、ⅢC.仅Ⅲ、ⅣD.仅Ⅳ、Ⅴ11.在微程序控制器设计中，假设微命令采用最短编码法，需产生N种微操作。则微命令控制字段要设置的位数是______。

12.证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。13.对给定关键字的序号j(0≤j＜n)，要求在无序记录A[0，…，n-1]中找按关键字从小到大排在第i位上的记录，利用快速排序的划分思想设计上述算法。14.下列功能中，属于表示层提供的功能是______。A.拥塞控制B.透明传输C.死锁处理D.文本压缩15.对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是

A.该树一定是一棵完全二叉树B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一任一结点的权值16.通常为用户提供4种使用接口，它们是终端命令、图标菜单、系统调用和______。A.计算机高级指令B.宏命令C.类似DOS的批命令文件或UNIX的shell文件D.汇编语言17.执行一次磁盘输入输出操作所花费的时间包括______。A.寻道时间、延迟时间、传送时间和等待时间B.寻道时间、等待时间、传送时间C.等待时间、寻道时间、延迟时间、读写时间D.寻道时间、延迟时间、传送时间18.设磁盘的I/O请求队列中的柱面号为19、376、205、134、18、56、193、396、29、3、19、40，磁头的起始位置为100，若采用SCAN(电梯调度)算法(磁头的当前是往柱面号小的方向移动)，则磁头移动共需移动的磁道数为______(该调度算法的磁头移动到最内/外磁道后，就改变方向)。A.205B.480C.490D.51219.由于进程具有异步性，这就可能使进程按下述两种顺序向前推进：______和______。20.若系统中有五个并发进程涉及某个相同的变量A，则变量A的相关临界区是由

临界区构成。A.2个B.3个C.4个D.5个21.为进程分配连续内存的是______。A.分页存储管理B.分段存储管理C.可变分区管理D.段页式存储管理22.单级中断系统中，中断服务程序内的执行顺序是______。

Ⅰ．保护现场

Ⅱ．开中断

Ⅲ．关中断

Ⅳ．保存断点

Ⅴ．中断事件处理

Ⅵ．恢复现场

Ⅶ．中断返回A.Ⅰ→Ⅴ→Ⅵ→Ⅱ→ⅦB.Ⅲ→Ⅰ→Ⅴ→ⅦC.Ⅲ→Ⅳ→Ⅴ→Ⅵ→ⅦD.ⅣⅠ→Ⅴ→Ⅵ→Ⅶ23.若循环队列以数组Q[0..m-1]作为其存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MODm进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是______。A.rear-lengthB.(rear-length+m)MODmC.(1+rear+m-length)MODmD.m-length24.下列死锁的论述中，正确的论述是

。A.由于产生死锁的基本原因是系统资源不足，因而预防死锁最常用方法，是根据系统规模，配置足够的系统资源B.由于产生死锁的另一个基本原因是进程推进顺序不当，因而预防死锁的常用方法，是使进程的推进顺序合法C.因为只要系统不进入不安全状态，便不会产生死锁，故预防死锁的常用方法，是防止系统进入不安全状态D.可以通过破坏产生死锁的四个必要条件之一或其中几个方法，来预防发生死锁25.一组N个站点共享一个56kb/s的纯ALOHA信道，每个站点平均每100s输出一个1000bit的帧，即使前一个帧没有发送完也依旧进行。问N可取的最大值是多少?26.随着3D游戏软件的大量出现，许多机器的显卡中配置了具有3D功能的GPU，下列有关这类显卡的显示存储器的叙述中，错误的是______。A.显存大多数由DRAM芯片组成B.CPU和GPU都可以访问显存C.显存和主存之间可采用DMA方式传送数据D.显存容量大致等于最高分辨率与像素深度的乘积27.对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为______。A.3B.4C.5D.628.下列有关曼彻斯特编码的叙述正确的是______。A.每个信号起始边界作为时钟信号有利于同步B.将时钟与数据取值都包含在信号中C.这种模拟信号的编码机制特别适合于传输声音D.每位的中间不跳变表示信号的取值为029.进程状态由就绪状态转化到运行状态是由

引起的。A.中断事件B.进程状态转换C.进程调度D.程序被创建为进程30.通道管理没有涉及的数据结构有______。

Ⅰ．设备控制表

Ⅱ．控制器控制表

Ⅲ．通道控制表

Ⅳ．系统设备表

Ⅴ．内存分配表A.仅ⅤB.Ⅳ和ⅤC.Ⅰ和ⅡD.Ⅰ、Ⅱ和Ⅲ31.设有n个进程共用一个相同的程序段，假设每次最多允许m个进程(m≤n)同时进入临界区，则信号量S的初值为______。A.mB.nC.m-nD.-m32.采用顺序结构存储串，编写一个实现串通配符匹配的函数pattern_index()，其中的通配符只有'?'，它可以和任一字符匹配成功，例如，pattern_index("?re"，"thereare")返回的结果是3。33.为了加快文件目录的查找，许多操作系统为用户强加了两个文件操作系统调用：OPEN系统调用和CLOSE系统调用。但是在某些操作系统中，不需要打开和关闭文件操作用户也可以进行文件读/写。请问在两类系统中，读和写文件的系统调用分别应该包含哪些参数?34.下列关于PROM与掩模ROM的说法中，错误的是______。A.掩模ROM制成后不可改写B.PROM制成后可编写一次，编程之后不可再改写C.PROM制成后可多次改写D.以上说法都不对35.14.IEEE802.3MAC帧的最小帧长是

。A.64ByteB.128ByteC.512ByteD.1024Byte36.下列关于磁盘的说法中，错误的是______。A.本质上，U盘(闪存)是一种只读存储器B.RAID技术可以提高磁盘的磁记录密度和磁盘利用率C.未格式化的硬盘容量要大于格式化后的实际容量D.计算磁盘的存取时间时，“寻道时间”和“旋转等待时间”常取其平均值37.802.3标准定义的以太网中，实现“给帧加序号”功能的层次是______。A.物理层B.介质访问控制子层(MAC)C.逻辑链路控制子层(LLC)D.网络层38.计算机系统的层次结构，下列五个级别机器由下到上的顺序是______。

Ⅰ．机器语言机器

Ⅱ．汇编语言机器

Ⅲ．高级语言机器

Ⅳ．微程序控制机器

Ⅴ．操作系统机器A.Ⅰ→Ⅱ→Ⅲ→Ⅳ→ⅤB.Ⅳ→Ⅰ→Ⅴ→Ⅱ→ⅢC.Ⅲ→Ⅱ→Ⅴ→Ⅰ→ⅣD.Ⅴ→Ⅳ→Ⅲ→Ⅱ→Ⅰ39.有一矩阵varA:array[1..100，1..100]ofinteger以行为先进行存储。有一个虚存系统，物理内存共有三页，其中一页用来存放程序，其余两页用于存放数据。假设程序已在内存中占一页，其余两页空闲。

程序A：

fori:=1to100do

forj:=1to100do

A[i,j]:=0;

程序B：

forj:=1to100do

fori:=1to100do

A[i,j]:=0;

若每页可存放200个整数，程序A和程序B的执行过程各会发生多少次缺页?若每页只能存放100个整数呢?以上说明了什么问题?40.设排序二叉树中结点的结构由三个域构成：数据域data，指向左儿子结点的指针域left，指向右儿子结点的指针域right。

设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除。41.下列四个序列中，______是堆。A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15．25，20，10D.75，45，65，10，25，30，20，1542.如果一个用户需要实现漫游，那么它需要完成______工作。

Ⅰ．创建一个本地代理

Ⅱ．创建一个外部代理

Ⅲ．外部代理与该用户本地代理进行联系A.全部B.Ⅰ、ⅡC.Ⅰ、ⅢD.Ⅱ、Ⅲ43.试计算一个包括5段链路的传输连接的单程端到端时延。5段链路中有2段是卫星链路，每条卫星链路又由上行链路和下行链路两部分组成，可以取这两部分的传播时延之和为250ms。每一个广域网的范围为1500km，其传播时延可按150000km/s来计算。各数据链路速率为48kb/s，帧长为960b。44.下图是一个3阶B树。分别画出在插入65、15、40、30后B树的变化。

45.数据总线的宽度由总线的______来定义。A.物理特性B.功能特性C.电气特性D.时间特性46.二维数组Amn按行序为主序存放在内存，每个数组元素占1个存储单元，则元素aij的地址计算公式是(

)。A.loc(aij)-loc(all)+[(i-1)*m+(j-1)]B.loc(aij)-loc(all)+[(j-1)*m+(i-1)]C.loc(aij)-loc(all)+[(i-1)*n+(j-1)]D.loc(aij)-loc(all)+[(j-1)*n+(i-1)]47.在可变式分区分配方案中，将空白区在空白区表中按地址递增次序排列的是(

)。A.最佳适应算法B.最差适应算法C.最先适应算法D.最迟适应算法48.采用SPOOLing技术后，使得系统资源利用率

。A.提高了B.降低了C.有时提高有时降低D.出错的机会增加了49.

不是常用三级时序系统中的一级。A.指令周期B.工作周期C.时钟周期D.定时脉冲50.计算机系统中，创建的进程数量受到制约的主要因素是

。A.内存大小B.终端数目C.打开文件数D.处理机数量51.下列说法中正确的是______。A.如果有向图的邻接矩阵是对称矩阵，则该有向图一定是有向完全图B.如果某个图的邻接矩阵不是对称矩阵，则该图一定是有向图C.如果某个图的邻接矩阵是对称矩阵，则该图一定是无向图D.邻接矩阵表示法只存储了边的信息，没有存储顶点的信息52.用户要求计算机系统所做的工作的集合称为______。53.端口(port)和套接字(socket)的区别是什么?54.存SPOOLing技术中，用户进程实际分配到的是______。A.用户所需的外设B.一块内存区，即虚拟设备C.共享设备的一部分存储区D.虚拟设备的一部分空间55.TCP采用滑动窗口协议解决了______。A.端到端的流量控制B.整个网络的拥塞控制C.端到端的流量控制和网络的拥塞控制D.整个网络的差错控制56.下列______是动态半导体存储器的特点。

Ⅰ．在工作中存储器内容会产生变化

Ⅱ．每隔一定时间，需要根据原存内容重新写入一遍

Ⅲ．一次完整的刷新过程需要占用两个存储周期

Ⅳ．一次完整的刷新过程只需要占用一个存储周期A.Ⅰ、ⅢB.Ⅱ、ⅢC.Ⅱ、ⅣD.只有Ⅲ57.下列关于栈和队列说法中，正确的是

。A.消除递归不一定需要使用栈B.对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同C.通常使用队列来处理函数或过程调用D.队列和栈是运算受限的线性表，只允许在表的两端进行运算58.现在有三个同时到达的作业J1、J2和J3，它们的执行时间分别是T1、T2、T3，且T1＜T2＜T3。系统按单道方式运行且采用短作业优先调度算法，则平均周转时间是

。A.T1+T2+T3B.(3×T1+2×T2+T3)/3C.(T1+T2+T3)/3D.(T1+2×T2+3×T3)/359.以下关于网络操作系统的功能的叙述不正确的是

。A.网络通信的任务是在源主机和目标主机之间，实现无差错的数据传输B.在局域网中典型的共享资源有硬盘、打印机、文件和数据C.网络操作系统最基本的功能是网络管理D.网络管理最基本的任务是安全管理60.已知小写英文字母“a”的ASCII码值为61H，现字母“g”被存放在某个存储单元中，若采用偶校验(假设最高位作为校验位)，则该存储单元中存放的十六进制数是______。A.66HB.E6HC.67HD.E7H第1卷参考答案一.历年考点试题黑钻版1.参考答案：A[解析]连续文件常用于存放大型的系统文件。2.参考答案：此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(A[i][j]=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)3.参考答案：在第一级磁盘容错技术中，包括以下容错措施：

(1)双份目录和双份文件分配表。在磁盘上存放的文件目录和文件分配表FAT均为文件管理所用的重要数据结构，所以为之建立备份。

(2)在系统每次加电启动时都要对两份目录和两份FAT进行检查，以验证它们的一致性。

在第二级磁盘容错技术中，包括以下容错措施：

(1)磁盘镜像。在同一磁盘控制器下增设一个完全相同的磁盘驱动器，在每次向文件服务器的主磁盘写入数据后，都要采用写后读校验方式将数据再同样地写到备份磁盘上，使两者具有完全相同的位像图。

(2)磁盘双工。将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘机镜像成对，从而在磁盘控制器发生故障时起到数据保护的作用。在磁盘双工时，由于每一个磁盘都有自己的独立通道，故可以同时(并行)地将数据写入磁盘。在读入数据时，可采用分离搜索技术，从响应快的通道上取得数据，因而加快了对数据的读取速度。

(3)热修复重定向和写后读校验。两者均用于防止将数据写入有缺陷的盘块中。就热修复重定向而言，系统将一定的磁盘容量作为热修复重定向区，用于存放当发现盘块有缺陷时的待写数据，并对写入该区的所有数据进行登记，方便将来对数据进行访问。而写后读校验则是为了保证所有写入磁盘的数据都能写入到完好的盘块中，故在每次从内存缓冲区向磁盘中写入一个数据块后，应立即从磁盘上读出该数据块并送至另一缓冲区中，再将该缓冲区中内容与原内存缓)中区中在写后仍保留的数据进行比较。若两者一致，便认为此次写入成功，可继续写入下一个盘块；否则，则重写。若重写后两者仍不一致，则认为该盘块有缺陷，此时便将应写入该盘块的数据写入热修复重定向区中，并将该损坏盘块的地址记录在坏盘块表中。4.参考答案：D资源有序分配策略将资源编号并有序分配，如果前置资源没有得到，则不能申请后续资源，因此系统中不会出现得到后续资源而请求前置资源的情况，破坏了循环等待条件，因此答案选择D选项。

一次性分配策略破坏了请求与保持条件，有资源就全部分配，没有就一点也不分配；剥夺资源法破坏了不剥夺条件；银行家算法是对情况进行预测，如果存在安全序列则分配，如果不存在则拒绝分配，因此银行家算法并没有破坏4个必要条件之一，不属于死锁预防。5.参考答案：B[解析]/17转换为二进制是11001010.01101110.1XXXXXXX.XXXXXXXX。

A：/17转换为二进制是11001010.01101110.0XXXXXXX.XXXXXXXX，第17位和/17的第17位不同，所以A不属于这个网络。

B：/20转换为二进制是11001010.01101110.1010XXXX.XXXXXXXX，前17位和/17的前17位完全相同，所以B属于此网络。

C：/16这个是具有欺骗性的表达方法，实际上这个网络是/16，网络号为16位的网络不可能属于一个网络号为17位的网络。

D：/20转换为二进制是11001010.01101110.0001XXXX.XXXXXXXX。第17位和/17的第17位不同，所以D不属于这个网络。6.参考答案：本题关键字本身即指示了其在序列中的位置，由此可以写出如下代码：

voidorder(intA[],intn)

{

inti;

for(i=0;i＜n;++1)

A(A[i]]=A[i];

}[说明]本题用直接给A[]从i=0到n-1进行赋值的做法是不对的，虽然结果一样。因为实际应用中，关键字一般都与数据域相关，有可能需要将相关数据放在正确位置上，而不仅仅是将关键字放在正确位置上。7.参考答案：(1)b单向连接微控制器，由微控制器的作用不难得知b是指令寄存器(IR)；a和c直接连接主存，只可能是MDR和MAR，c到主存是单向连接，a和主存双向连接，根据指令执行的特点，MAR只单向给主存传送地址，而MDR既存放从主存中取出的数据又要存放将要写入主存的数据，因此c为主存地址寄存器(MAR)，a为主存数据寄存器(MDR)。d具有自动加1的功能，且单向连接MAR，不难得出为程序计数器(PC)。

因此，a为MDR，b为IR，c为MAR，d为PC。

(2)先从程序计数器(PC)中取出指令地址，将指令地址送入主存地址寄存器(MAR)，在相关的控制下从主存中取出指令送至主存数据寄存器(MDR)，然后将MDR中的指令送至指令寄存器(IR)，最后流向微控制器，供微控制器分析并执行指令。

因此，取指令的数据通路为：PC→MAR，M(MAR)→MDR→IR→控制器

(3)与(2)的分析类似，根据MAR中的地址去主存取数据，将取出的数据送至主存数据寄存器(MDR)，然后将MDR中的数据送至ALU进行运算，运算的结果送至累加器(AC)，运算结束后将AC中的结果送至MDR，最后将MDR中的数据写入主存。

因此，从主存取出、运算和写回主存所经过的数据通路为：MAR→M，M(MAR)→MDR→ALU，ALU→AC，AC→MDR→M(MAR)。8.参考答案：分片的片偏移值表示其数据部分首字节在原始分组的数据部分中的相对位置，单位为8字节。首部长度字段以4字节为单位，总长度字段以字节为单位。题目中，分组的片偏移值为100，那么其数据部分第一个字节的编号是800。因为分组的总长度100B，首部长度为4×5=20B，所以数据部分长度为80B。那么该分组的数据部分的最后一个字节的编号是879。9.参考答案：C因为CPU是在指令周期的最后一个机器周期——执行周期的结束时刻统一向所有中断源发出中断查询信号，所以答案为C。10.参考答案：D11.参考答案：C[解析]由于微命令控制字段必须是一个整数，所以在最短编码法中为位。

最短编码法将所有的微命令统一编码，每条微指令只定义一个微命令。若微命令的总数为N，操作控制字段的长度为L，则最短编码法应满足下列关系式：

L≥log2N12.参考答案：此题考查的知识点是图的定义。具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树(在图论中树定义为无回路的连通图)。13.参考答案：本算法不需要将整个记录排序，只进行查找第j个记录(从小到大排序)。

程序代码如下：

voidsplit(intA[],intlow,inthigh,int&i)

{

intj;

elemtypex;

i=low;j=high;x=A[i];

//初始化

while(i＜j)

{

while(A[j]＞=x&&i＜j)

//从右向左遍历

--j;

if(i＜j)

{

A[i]=A[j];++i;

//相当于交换A[i]与A[j]

}

while(A[i]＜=x&&i＜j)

//从左向右遍历

++i;

if(i＜j)

{

A[j]=A[i];--j;

//相当于交换A[i]与A[j]

}

}

A[i]=x;

//x定位在位置i处

}

sort(intA[],intj,intn)

{

ints=0,t=n-1,k;

split(A,s,t,k);

while(k!=j)

if(k＜j)

split(A,k+1,t,k);

//元素在右边，对右边进行划分

else

split(A,s,k-1,k);

//元素在左边，对左边进行划分

returnA[j];

}14.参考答案：D[解析]表示层涉及在应用层进程之间传送的数据表示，这可以包括加密、正文压缩或者两个端点系统，使用的语法或数据格式之间的转换(例如EBCDIC和ASCII码之间的转换)，也可以包括为了建立适当的语法与远方对等表示层进行的协商过程。15.参考答案：A[解析]考查哈弗曼树的特性。

哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。

哈夫曼树中没有度为1的结点，B正确；

构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；

哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点．P权值的结点Q，那么结点Q的兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树。

综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。16.参考答案：C操作系统作为用户与计算机硬件系统之间的接口，用户可通过3种方式使用计算机：①命令方式；②系统调用方式；③图形、窗口方式。题于中所说的终端命令属于①，图标菜单属于③，系统调用属于②。而C选项中的批处理命令就是把一批终端命令放在一个文本里，然后批量执行。UNIX的shell文件也是类似的，因此C选项属于命令方式。因此本题选C。

宏命令一般是指用户与应用程序之间的接口。17.参考答案：B[解析]本题考查磁盘操作时间的概念。18.参考答案：C本题其实是有争议的。问题其实就是SCAN算法和LOOK算法的区别。SCAN算法是要扫到头的，而LOOK算法是移动到最内/外磁道后，就改变方向。但很多时候教材只提到SCAN算法，而算法描述其实是LOOK算法。考生如果遇到这样的问题，建议这样处理：如果没有给出最内、最外磁道号，题目就默认是考查LOOK算法；给出最内、最外磁道号的，而又无特殊说明的，就默认考查SCAN算法。2012年的大纲解析中，对SCAN算法的解释是要扫到底才改变方向。解答如下：

寻道顺序为100、56、40、29、19、18、3、134、193、205、376、396，移动磁道数分别为44、16、11、10、1、15、131、59、12、171、20，总数为490。

注意：

1)对于SCAN算法，磁臂从磁盘的一端向另一端移动，同时当磁头移过每个柱面时，处理位于该柱面上的服务请求。当到达另一端时，磁头改变移动方向，处理继续。

2)C-SCAN调度是SCAN调度的变种，主要提供一个更为均匀的等待时间。与SCAN一样，C-SCAN将磁头从磁盘一端移到磁盘的另一端，随着移动不断地处理请求。不过，当磁头移到另一端时，它会马上返回到磁盘开始处，返回时并不处理请求。C-SCAN调度算法基本上将柱面当做一个环链，以将最后柱面和第一柱面相连。

3)LOOK调度，正如上所述，SCAN和C-SCAN位磁头在整个磁盘宽度内进行移动。事实上，这两个算法都不是这样实现的。通常，磁头只移动到一个方向上最远的请求为止，接着马上回头，而不是继续到磁盘的尽头。这种形式的SCAN和C-SCAN称为LOOK调度和C-LOOK调度，这是因为它们在朝一个方向移动时会看是否有请求。19.参考答案：进程推进顺序合法；进程推进顺序非法20.参考答案：D临界资源是诸进程之间应采取互斥方式访问的，也就是一次只允许一个进程访问的资源，可以为硬件，软件，变量，数据，表格，队列等，并不单指硬件资源。临界区就是每个进程中访问临界资源的那段代码。五个并发进程都涉及了变量A，每一个进程中都有访问变量A的代码，所以每个进程中都有相关临界区，因此是五个临界区构成。21.参考答案：C22.参考答案：A[解析]在单级(或单重)中断系统中，不允许中断嵌套。中断处理过程为：①关中断；②保存断点；③识别中断源；④保存现场；⑤中断事件处理；⑥恢复现场；⑦开中断；⑧中断返回。其中，①～③由硬件完成，④～⑧由中断服务程序完成，故选A。23.参考答案：C[解析]按照循环队列的定义，因为元素移动按照rear=(rear+1)MODm进行，则当数组Q[m-1]存放了元素之后，下一个入队的元素将存放到Q[0]中，因此队列的首元素的实际位置是(rear-length+1+m)MODm。24.参考答案：DA：不可能根据系统的规模，配置足够的系统资源，因为系统的资源是有限的。B：这种方法不能保证死锁不发生，而且进程推进过程很复杂，实现合理的顺序不太可能。C：系统进入不安全状态不一定会产生死锁，防止系统进入不安全状态不太可能，故不是常用的方法。25.参考答案：对于纯ALOHA协议，其信道利用率为0.184，故可用带宽是0.184*56kb/s。每个站需要的带宽是1000/100=10b/s。因此，N可取的最大值是10304/10≈1030。26.参考答案：D[解析]从早期的EDORAM、MDRAM、SDRAM、SGRAM、VRAM、WRAM等到今天广泛采用的DDRSDRAM，显存经历了很多代的进步。目前市场中所采用的显存类型主要有SDRAM，DDRSDRAM和DDRSGRAM三种，故A选项正确。

GPU是显示卡的“心脏”，也就相当于CPU在计算机中的作用，CPU和GPU都可以访问显存，故B选项正确。

DMA方式高效的I/O控制方式，当然可以应用于显存和主存之间的数据传输，故C选项正确。

D选项错误比较明显，举例如下：显示分辨率基本都是1024×768，颜色位数为32bit，那么需要的显存容量=1024×768×32bit/8bit=3145728B，可是这针对是2D显卡(普通平面)，如果是3D加速卡，那么需要的显存容量为1024×768×32bit×3/8bit=9437184B=9.216MB，这是最低需求，而且还必须增加一定的容量作为纹理显示内存，否则当显示资源被完全占用时，计算机只有占用主内存作为纹理内存，这样的二次调用会导致显示性能下降，因此作为真正的3D加速卡显存容量一定大于9.216MB。27.参考答案：B折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序(升序或降序)排列，也就是说折半查找只适用于对有序顺序表进行查找。有序顺序表也称为有序表。

折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功；否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。28.参考答案：B[解析]曼彻斯特编码将每一个码元分成两个相等的间隔。前面一个间隔为高电平而后一个间隔为低电平表示码元1，码元0正好相反；也可以采用相反的规定，因此D错。位中间的跳变作为时钟信号，每个码元的电平作为数据信号，因此B正确。曼彻斯特编码是将时钟和数据包含在数据流中，在传输代码信息的同时，也将时钟同步信号一起传输到对方，因此A错。声音是模拟数据，而曼彻斯特编码最适合传输二进制数字信号，因此C错。29.参考答案：C[解析]本题目考查进程的基本状态转换。处于就绪态的进程经过进程调度则会获得CPU执行，从而转化为执行态。因此应该选C。30.参考答案：A[解析]本题考查通道管理。为了实现对I/O设备的管理和控制、需要对每台设备、通道及控制器的情况进行登记。设备分配依据的主要数据结构有，系统设备表：记录系统中全部设备的情况。设备控制表：系统为每个设备配置一张设备控制表，用户记录本设备的情况。控制器控制表：系统为每个控制器设置一张用于记录本控制器情况的控制器控制表，它反映控制器的使用状态及于通道的链接情况等。通道控制表：用来记录通道的特性、状态、及其他的管理信息。31.参考答案：A[解析]本题考查互斥信号量的设置。互斥信号量的初值应为可用资源数，在本题中为可同时进入临界区的资源数。每当一个进程进入临界区，S减1，减到-(n-m)为止，此时共有|S|个进程在等待进入。32.参考答案：本题增加了'?'的处理功能。实现代码如下：

intpattern_index(Str*subs,Str*s)

{

inti,j,k;

for(i=0;s-＞ch[i];++i)

for(j=i,k=0;(s-＞ch[j]==subs-＞ch[k])||(subs-＞ch[k]=='?');++j,++k)

if(subs-＞ch[k+1]=='\0')

returni+1;

return-1;

}33.参考答案：支持文件打开和关闭的文件系统参照《计算机考研考点精讲及复习指导》一书的对应章节的“考点精讲”。

在不支持文件打开和关闭的文件系统中，读/写文件的系统调用参数包括：①文件名；②文件读/写缓冲地址；③文件读/写长度；④文件读/写指针位置。[解析]在文件系统实现上存在许多选择，OPEN和CLOSE并不是唯一的实现选择。OPEN和CLOSE存在的唯一理由是整数比较的开销小于字串匹配，但是有许多没有实现OPEN/CLOSE接口的操作系统，其性能并没有显著的下降(这个性能问题可以进一步讨论，读者可以继续考虑这样的实现方法)。

是否支持OPEN/CLOSE接口的问题本质上是有状态和无状态服务器问题。支持OPEN/CLOSE接口的操作系统实现了一个有状态的服务器——文件系统，文件系统维持文件的操作状态，因此调用者无需提供状态参数。而不支持OPEN/CLOSE接口的操作系统则实现了一个无状态服务器，因此需调用者自行维护文件状态，在调用时必须提供类似于“读/写指针位置”的状态信息。34.参考答案：C[解析]PROM(ProgrammableRead-OnlyMemory)——可编程只读存储器，也叫One-TimeProgrammable(OTP)ROM(一次可编程只读存储器)，是一种可以用程序操作的只读内存。其最主要特征是只允许数据写入一次，如果数据烧入错误只能报废。

注：可擦除的ROM的名字中都带E，如EPROM、EEPROM等，还有一个是FlashMemory。35.参考答案：A36.参考答案：B[解析]闪存是在E2PROM的基础上发展起来的，本质上是只读存储器。RAID将多个物理盘组成像单个逻辑盘，不会影响磁记录密度，也不可能提高磁盘利用率。37.参考答案：C[解析]以太网没有网络层。物理层的主要功能是：信号的编码和译码、比特的接收和传输；MAC子层的主要功能是：组帧和拆帧、比特差错检测、寻址、竞争处理；LLC子层的主要功能是：建立和释放数据链路层的逻辑连接、提供与高层的接口、差错控制、给帧加序号。38.参考答案：B[解析]现代计算机系统是一个硬件与软件组成的综合体，可以把它看成按功能划分的多级层次结构。计算机系统的多层次结构，如下图所示。层次结构由高到低的次序分别是：应用语言机器级、高级语言机器级、汇编语言机器级、操作系统机器级、传统机器级、微程序机器级。对每一个机器级的用户来说，都可以将此机器看成是一台独立的使用自己特有的“机器语言”的机器。

39.参考答案：有两个内存块可以用来存放数组信息，每个主存块可存放200个数组元素，数组中的元素按行编址。对于程序A来说，其访问顺序也是按行进行，由于每行有100个元素，每访问两行遇到一次缺页中断。如果采用FIFO或LRU页面调度算法，一共产生50次缺页中断。

对于程序B来说，其访问顺序按列进行，与数组的按行存储顺序不一致，每访问两个数组元素将发生一次缺页中断。如果采FIFO或LRU页面调度算法，一共产生5000次缺页中断。

若每页只能存放100个整数，对于程序A，数组的存储顺序与访问顺序一致，每访问一行数组遇到一次缺页中断。如果采用FIFO或LRU页面调度算法，会产生100次缺页中断。对于程序B，数组的存储顺序与访问顺序不一致，每访问一个数组元素遇到一次缺页中断。如果采用FIFO或LRU页面调度算法，一共产生10000次缺页中断。

以上结果说明：页面越大，缺页中断次数越少；页面越小，缺页中断次数越多。40.参考答案：利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。

typedefstructnode{

intdata;

structnode*left,*right;

}BiTNode,*BSTree;

voidDelTree(BSTreer){

//非递归删除以r为根的二叉排序树

BSTreeS[];

//栈，容量足够大，栈中元素是二叉排序树结点的指针

BSTreep;

inttop=0;

while(r!=null||top＞0){

while(r!=null){S[++top]=r;r=r-＞left;}

//沿左分支向下

if(top＞0)

//退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间

{p=S[top--];r=p-＞fight;free(p);}

}

}//DelTree

voidDeleteAllx(BSTreeT,intx){

//在二叉排序树T中，删除所有小于等于x的结点

BSTreep=T,q;

while(T&&T-＞data＜=x){

//根结点的值小于等于x

p=T;T=T-＞fight;p-＞fight=null;

DelTree(p);}

//删除二叉树P，删除持续到“根”结点值大于x或T为空树为止

if(T){

q=T;p=T-＞left;

while(p&&p-＞data＞x){

//沿根结点左分支向下，查小于等于x的结点

while(p&&p-＞data＞x){q=p;p=p-＞left;}

//q记p的双亲

if(p)

//p结点的值小于等于x

{q-＞left=p-＞fight;p-＞fight=null;DelTree(p);}

p=q-＞left;

//再查原p的右子树中小于等于x的结点

}

}41.参考答案：C堆排序是另一种基于选择的排序方法。n个元素的序列{k1，k2，k3，．．．kn}，当且仅当满足以下关系时，称之为堆：

或者：

其中i=1，2，…，n/2。

若将同以上序列对应的一维数组看成是一棵完全二叉树，则堆的含义表明：该完全二叉树的所有非终端结点均不大于(或不小于)其左、右孩子结点的值。由此，若{k1，k2，．．．kn)是堆，则堆顶元素(或完全二叉树的根结点)必定是该序列n个元素中的最小值(或者最大值)。

若将堆看成是一棵以k1为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这n个结点中的最小者(或最大者)。下面图给出的两个堆的示例。

从堆的定义可以看出，若将堆用一棵完全二叉树表示，则根结点是当前堆中所有结点的最小者(或最大者)。堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小(或次大)的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。42.参考答案：A[解析]如果一个站点的用户希望实现漫游，那么它必先创建一个本地代理，如果一个站点允许其他的访问者进到它的网络中，那么它必须创建一个外部代理。当移动主机在一个外地站点中启动时，它与当地的外部代理联系，并且进行注册。然后，外部代理与该用户的本地代理进行联系，并且交给它一个移交地址。43.参考答案：5段链路的传播时延=250×2+(1500/150000)×3×1000=530ms。

5段链路的发送时延=960/(48×1000)×5×1000=100ms。

所以5段链路单程端到端时延=530+100=630ms。44.参考答案：插入过程：

插入65后，如下图所示：

插入65后的3阶B树

插入15后，如下图所示：

插入15后的3阶B树

插入40后，如下图所示：

插入40后的3阶B树

插入30后，如下图所示：

插入30后的3阶B树45.参考答案：B总线的物理特性描述了总线的根数、插头、形状及引脚排列等物理连接方式。功能特性描述总线的每一根线的功能，如数据总线的宽度指明了访问一次存储器或外设时能够交换数据的位数。电气特性定义每根线上信号的传递方向及有效电平范围。时间特性定义了每根线在什么时间有效。46.参考答案：A二维数组就是平常所说的矩阵，也可以看成是数据元素是一维数组的一位数组。由于计算机内部存储器的地址是一维线性排列的，故在存储数据时，必须将二维数组转换为计算机的内部存储形式才可以。一般有两种存储方式：以行为主的存储方式(row—major)和以列为主的存储方式(column—major)。

设二维数组A[1:U1，1:U2]，该数组有(U1-1)+1=U1行，有(U1-1)+1=U1列。设每个元素占d个空间，数组的起始地址为L1。

①以行为主(row—major)：也称行优先存储。其特点为：以每一行为单位，一行一行地放入内存，如C语言、PASCAL语言等都是如此处理二维数组的。

②以列为主(column—major)：也称列优先存储。其特点为：以每一列为单位，一列一列地放入内存，如Fortran语言就是如此处理二维数组的。二维数组A可以看成由U2个一维数组组成，每个一维数组有U1个元素。同1)类似，有：

*第j列数据元素的起始地址为：(j-1)×U1×d+L1

*数组元素A[i，j]的地址为：Loc(A[i，j])=L1+(j-1)×U1×d-6(i-1)×d

重要说明：二维数组Am*n的含义是：该数组有m行(0～m-1第一维)，有n列(0～n-1，第二维)，占用m*n个存储空间。假设每个数据元素占用L个存储单元(可理解为字节)，则二维数组A中任意一个元素aij的存储位置为：

行优先：LOC(