沈阳农业大学信息与电气工程学院805计算机专业基础历年考研真题汇编附答案

沈阳师范大学教育技术学院862计算机学科专业基

础综合（数据结构、操作系统）历年考研真题汇编附答案最新资料，WORD式，可编辑修改!目录说明：沈阳师范大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为867计算机学科专业基础综合（数据结构、操作系统），2015年科目代码改为862o为帮助考生全面复习，特提供2009〜2012年408计算机学科专业基础综合真题及详解。第一部分 沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编2014年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题科目代码：867科目名称：计算机学科专业基础综合（数据结构、操作系统）适用专业名称：计算机应用技术考生注意：请将答案写在答题纸上，写在本题签及草纸上无效。考试后本题签同答题纸一并交回。一、单项选择题（共10题，每题2分，合计20分）1．某算法的时间复杂度为 O（n2），表明该算法（）。A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比2设线性表有 n个元素，以下操作中，（）在顺序表上实现比在链表上实现效率更高。A.输出第i（1<i<n）个元素B.交换第1个元素与第2个元素的值C.顺序举^出这n个元素的值D.输出与给定值x相等的元素在线性表中的序号3．给定一个空栈，若 10、20、23、13依次进栈，然后有两个数出栈，又有3个数进栈，第一次进栈的23现在在（）。A.已出栈B.从栈底算起第3个C.栈顶D.从栈底算起第4个4.循环队列qu（其队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置，队列中的单元个数为 MaxSize）的队满足条件是（）。A．（+1）%MaxSize==+1）%MaxSize+1）%MaxSize==+1C．+1）%MaxSize==D．==5.一棵二叉树的中序序列为 ABDCEF,G后序序列为BDCAFGE则其左子树中的节点个数为（）。A．32C．4D．56．根据使用频率为 5个字符设计的哈夫曼编码不可能是（）。A．111,110,10,01,00B．000,001,010,011,1C．100,11,10,1,0D．001,000,01,11,107．对所示的无向图，从顶点1开始进行深度优先遍历，可得到的顶点访问序列为（）。A．1243576B．1243567C．1245637D．12345768．对于下图，以下（）是其拓扑序列。A．1,3,4,6,2,5,7B．1,3,2,6,4,5,7C．1,3,4,5,2,6,7D．1,2,5,3,4,6,79．对数据序列{15,9,7,8,20,-1,4}进行排序,一趟排序后的结果为{9,15,7,8,20,-1,4},采用的是（）。A.简单选择排序B.起泡排序C.直接插入排序D.堆排序10．对一组数据 （2,12,16,88,5,10）进行排序,若前三趟的结果如下 :第一趟： 2,12,16,5,10,88第二趟： 2,12,5,10,16,88第三趟： 2,5,10,12,16,88则采用的排序方法可能是 （）。A.起泡排序B.希尔排序C.归并排序D.基数排序二、应用题（共4题，每题10分，合计40分）11.使用普里姆算法构造如图所示的图G中从顶点1开始的一棵最小生成树。12．设有一组关键字 {19,1,23,14,55,20,84,27,68,11,10,77}，其哈希函数如下：H（key）=key%13采用开放地址法的线性探测法解决冲突，试在 0~18的哈希表中对该关键字序列构造哈希表。13.已知有6个顶点（顶点编号为0-5）的有向带权图G,其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。46OOOOOO5OOOOOO43OOOO33要求：（1）写出图G的邻接矩阵A。（2）画出有向带权图Go（3）求图G的关键路径，并计算该关键路径的长度。.将整数序列{4,5,7,2,1,3,6} 中的数依次插入到一棵空的平衡二叉树中，构造相应的平衡二叉树。三、算法设计题（共3题，每题10分，合计30分）.设0=包1白1,a2,b2,…,an,bn}为一线性表，采用带头节点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表（它们都用单链表存放），使A={a1,,a2,…，an},B={b1，b2,…,bn}.假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有分支节点个数。.设计一个算法，判断一个数据序列是否构成一个小根堆。四、简答题（共6题，每题5分，合计30分）.什么是操作系统的基本功能？.描述系统调用的含义。.说明什么是进程间的直接制约与间接制约。.说明什么是虚拟存储器。.请说明分区存储管理方式的主要优缺点。.说明什么是中断。五、综合题（共2题，每题15分，合计30分）.若有以下四个作业以1、2、3、4的顺序，在0时刻几乎同时到达系统并立即进入调度：作业名 所需CPUH间作业19小时作业22小时作业310小时作业45小时假设系统中没有其他作业，试给出对它们实施FCFSM度算法的计算结果,并计算其平均周转时间和平均带权周转时间。.几个并行进程共享一个数据集（如文件或表格）时，有些进程可能只是要求读这数据集的内容，而另一些进程则可能要求修改这数据集的内容。这种情况在操作系统中是很普遍的。通常我们称读数据的进程为读者，而把要求修改数据的进程称为写者。用P、V操作来描述读者一写者问题。2013年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题代码：868科目名称：计算机学科专业基础综合适用专业名称：计算机应用技术考生注意：请将答案写在答题纸上，写在本题签及草纸上无效。考试后本题签同答题纸一并交回。一、单项选择题（共30题，每题2分，合计60分）某算法的时间复杂度为 O（n2），表明该算法的（ ）。A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比2．设线性表中有 2n个元素，以下操作中，（）在单链表上实现要比在顺序表上实现效率更高。A.删除指定的元素B.在最后一个元素的后面插入一个新元素C.顺序举^出前k个元素D.交换第i个元素和第2n-i-1个元素的值（i=0,1…,n-1）3．在一个单链表 L中，指针p指向L的某个结点，在 p之前插入一个指针s所指结点时的操作为（）。A．s->next=p->next；p->next=s；t=p->data；p->data=s->data；s->data=t；B．p->next=s；s->next=p->next；t=p->data；p->data=s->data；s->data=t；C．s->next=p->next；p->next=s；p->data=s->data；t=p->data；s->data=t；D．p->next=s；s->next=p->next；t=s->data；s->datap->data；p->data=t；4.已知一个栈的进栈序列是 1,2,3,……，n,其输出序列是pi,p2,…，pn,若p产n,则pi的值（）。A．iB．n-iC．n-i+1D.不确定5．对稀疏矩阵进行压缩存储，常用的两种方法是（）。A.二元组和散列表B.三元组和十字链表C.三角矩阵和对角矩阵D.对角矩阵和十字链表.广义表（（a）,a）的表头和表尾分别是（ ）。（a）和（a）a和（a）（a）和a（（a））和（a）.已知二叉树的先序序列为ABDEGCF中序序列为DBGEACF则后序序列为（）。GEDBFCADGEBFCADGEBAFCEBFDGCA.一棵完全二叉树上有1000个结点，其中叶子结点的个数是（ ）。250500505501.线索二叉树是一种（ ）结构。A.逻辑逻辑和存储C.物理D.线性.以数据集｛2,5,7,9,13｝为权值构造一棵哈夫曼树，则其带权路径长为（）。78808179.一个有向图的邻接表存储如图 1所示，现按深度优先搜索遍历，从顶点V1出发，所得到的顶点序列是（ ）。D.可能不存在13.若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（）。A.是个有根有向图B.是个强连通图C.含有多个入度为0的顶点D.含有顶点数目大于1的强连通分量14．顺序查找法适合于存储结构为（）的线性表。A.哈希存储B.索引存储C.压缩存储D.顺序存储或链式存储15．在含有27个结点的二叉树排序树上，查找关键字为35的结点，则依次比较的关键字有可能是（）。TOC\o"1-5"\h\zA． 28， 36， 18， 46， 35B． 18， 36， 28， 46， 35C． 46， 28， 18， 36， 35D． 46， 36， 18， 28， 3516．在有序表 a[1..20]中，采用二分查找算法查找元素值等于a[12]的元素，所比较过元素的次数为（）。A．4B．5C．3D．617.数据序列｛8,9,10,4,5,6,20,1,2｝只能是下列排序算法中的（）的两趟排序后的结果。A.选择排序B.冒泡排序C.插入排序D.堆排序18．就平均性能而言，目前最好的内部排序方法是（）排序法。A.冒泡排序B.希尔排序C.插入排序D.快速排序19.有一组数据｛ 15, 9, 7,8,20,-1,7,4｝,用堆排序的筛选方法建立的初始堆为（）。TOC\o"1-5"\h\zA． -1 ， 4， 5，9， 20， 7， 15， 7B． -1 ， 7， 15，7，4， 8， 20， 9C． -1 ， 4， 7，8， 20， 15，7， 9D.A,B,C都不对．下面说法不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，将使整个工程提前完成C.所有关键活动都提前完成，则整个工程提前完成D.某些关键活动若提前完成，将使整个工程提前完成．下列选项中，（）不是操作系统关心的主要问题。A.管理计算机裸机B.设计、提供用户程序与计算机硬件系统的界面C.管理计算机系统资源D.高级程序设计语言的编译器．系统功能调用是（）。A.用户编写的一个子程序B.高级语言中的库程序C.操作系统中的一条命令D.操作系统向用户程序提供的接口．在处理机管理中，当（）时，进程从阻塞状态变为就绪状态。A.进程被调度程序选中B.等待某一事件发生C.等待的事件发生D.时间片用完．高级调度是（）。A.进程调度B.作业调度C.程序调度D.设备调度．临界区是（）。一个缓冲区一段共享数据区一段程序一个互斥资源．产生死锁的根本原因是（）。A.资源共享B.并发执行的进程太多C.进程推进顺序非法D.以上3个因素全是．在下述存储管理方案中，（）管理方式要求作业占用连续的存储空间。A.分区B.分页C.分段D.段页式．操作系统中对数据进行管理的部分叫做（）。A.数据库系统B.文件系统

C.检索系统D.数据存储系统.下列文件中属于逻辑结构的文件是（ ）。A.连续文件B.系统文件C.散列文件D.流式文件.在磁盘文件系统中，对于下列文件物理结构，（ ）不具有直接读写文件任意一个记录的能力。A.顺序结构B.链接结构C.索引结构D.散列结构二、算法设计题（共2题，每题10分，合计20分）.设C={a1,b1,a2,b2,…,an,bn}为一线性表，采用带头结点的 hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得：A={a1,a2,…，an},B={b1,b2, …，bn}.冒泡排序的算法是把大的元素向上移动（气泡的上升）也可以把最小的元素向下移动（气泡的下沉）。请给出上浮和下沉过程交替的冒泡排序算法。三、综合应用题（共6题，合计70分）.写出用Prim算法构造图2最小生成树的过程。（10分）图2无向网.关键字序列A=（36,27,68,33,97,40,81,24,23,90,32,14） 共12个数据，哈希表长为13,采用的哈希函数为：h（key尸key%13。如果采用开放定址的线性探测再散列方法解决冲突，请构造哈希表并求其查找成功时的平均查找长度。（10分）.在如图3所示的AOEW,求：（10分）（1）完成此工程最少需要的多少天（设边上权值为天数）。（2）是否存在某项活动，当其提高速度后能使整个工程缩短工期。a3=36.若有以下四个作业同2怜作业名作业

作业

作业

作业12347ck=a8=150AOEa3=36.若有以下四个作业同2怜作业名作业

作业

作业

作业12347ck=a8=150AOE典并遇=4入调8SJEa13=29CPUH间（分钟）a6=38a2=6假设系统中没有其他作业,3..现新3注球94给出作业调度顺序并求出平均作业周转时间 T,平均带权作业周转时间W（15分）.在一个请求式页式管理系统中，某程序在内存中分配三个页面，初始为空.页面走向为：4,3,2,1,4,3,5,4,3,2,1,5。用学过的页面值换算法FIFO算出缺页次数。给出执行过程中内存页面的变化情况。（ 15分）.在4*100m接力赛中，4个运动员之间存在如下关系图4,运动员1跑到终点把接力棒交给运动员2,……，运动员4接到棒后跑完全程。试用信号量机制进行描述。试写出这四个并发进程能正确执行的程序。（ 10分）第二部分 全国硕士研究生入学统一考试 408计算机学科专业基础综合历年真题及详解2012年全国硕士研究生入学统一考试 408计算机学科专业基础综合真题一、单项选择题：l〜40小题。每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。.求整数n（n>0）阶乘的算法如下，其时间复杂度是（ ）。A．O（log2n）0（n）C．O（nlog2n）D．O（n2）2．已知操作符包括‘ +’、‘ -’、‘ *’、‘／’、‘（’和‘）’。将中缀表达式a+b-a*（（c+d）/e-f）+g转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。A．57C．8D．113.若一棵二叉树的前序遍历序列为 a,e,b,d,c,后序遍历序列为b,c,d,e,a,则根结点的孩子结点（ ）。A.只有eB.有e、bC.有e、cD.无法确定4．若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（）。A．12B．20C．32D．335．对有 2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。A．0（n）B．0（e）C．O（n+e）D.O（nxe）6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。A.存在，且唯一B.存在，且不唯一不唯一C.存在，可能不唯一D.无法确定是否存在7．有向带权图如题 7图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是（ ）。题7图有向带权图A．d,e,fB．e，d，fC．f，d，eD．f，e，d8．下列关于最小生成树的叙述中，正确的是（）。I.最小生成树的代价唯一 n.所有权值最小的边一定会出现在所有的最小生成树中 田.使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A.仅IB.仅nC.仅I、mD.仅n、iv9.设有一棵3阶B树，如题9图所示。删除关键字 78得到一棵新B树，其最右叶结点所含的关键字是（）。题9图3二叉树图A．60B．60，62C．62，65D．6510．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。I.简单选择排序 n.希尔排序 田.快速排序 iv.堆排 V.二路归并排序A.仅I、m、IVB.仅I、n、mC.仅n、m、ivD.仅田、IV、V11．对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。A.排序的总趟数B.元素的移动次数C.使用辅助空间的数量D.元素之间的比较次数

12．假定基准程序 A在某计算机上的运行时间为 l00秒，其中90秒为CPU时间，其余为I/O时间。若CPU1度提高50%,I/O速度不变，则运行基准程序A所耗费的时间是（）。A．55秒B．60秒C．65秒D．70秒13．假定编译器规定int和short类型长度分别为32位和16位，执行下列C语言语句：unsignedshortX=65530;unsignedinty =X：得至Uy的机器数为（）。A．00007FFAHB．0000FFFAHC．FFFF7FFAHD．FFFFFFFAH.float类型（即IEEE754单精度浮点数格式）能表示的最大正整数是）。A．B．C）。A．B．C．D．02126-22127-22127-22128-2103104103104．某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和short型长度分别为32位和16位，并且数据按边界对齐存储。某 C语言程序段如下：若record变量的首地址为0xC008,则地址0xC008中内容及的地址分别为（ ）。A．0x00、0xC00D0x00、0xCOOEC．0x11、0xC00DD．0x11、0xC00E.下列关于闪存（FlashMemory）的叙述中，错误的是（ ）。A.信息可读可写，并且读、写速度一样快B.存储元由MOST组成，是一种半导体存储器C.掉电后信息不丢失，是一种非易失性存储器D.采用随机访问方式，可替代计算机外部存储器.假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为l个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU瞽换算法，当访问的主存地址依次为0，4，8，2，0，6，8，6，4，8时，命中Cache的次数是（）。A．1B．2C．3D．4．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33个微命令，构成5个互斥类，分别包含 7、3、12、5和6个微命令，则操作控制字段至少有（）。A．5位B．6位C．15位D．33位.某同步总线的时钟频率为100MHz,宽度为32位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输 128位数据所需要的时间至少是 （ ）。）A．20nsB．40nsC．50nsD．80ns.下列关于USB总线特性的描述中，错误的是（ ）。A.可实现外设的即插即用和热插拔B.可通过级联方式连接多台外设C.是一种通信总线，可连接不同外设D.同时可传输2位数据，数据传输率高.下列选项中，在I/O总线的数据线上传输的信息包括（ ）。I.I/O接口中的命令字 n.I/O接口中的状态字 m.中断类型号A.仅I、nB.仅I、mC.仅n、田d.I、n、田22．响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（）。I.开关中断 n.保存通用寄存器的内容 田.形成中断服务程序入口地址并送 PCA.仅I、nB.仅I、mC.仅n、田d.I、n、田23．下列选项中，不可能在用户态发生的事件是（）。A.系统调用B.外部中断C.进程切换D.缺页24．中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（A.程序计数器B.程序状态字寄存器C.通用数据寄存器D.通用地址寄存器25.下列关于虚拟存储的叙述中，正确的是（ ）。A.虚拟存储只能基于连续分配技术B.虚拟存储只能基于非连续分配技术C.虚拟存储容量只受外存容量的限制D.虚拟存储容量只受内存容量的限制26.操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。A.用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序B.用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序C.用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序D.用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序27.假设5个进程P0、Pl、P2、P3、P4共享三类资源Rl、R2、R3,这些资源总数分别为18、6、22oTo时刻的资源分配情况如题27表所示，此时存在的一个安全序列是（ ）。题27表资源分配情况表已分配资源资源最大需求进程R1R2R3R1R2R3PO3235510P14O3536P24O54O11P32O4425P4314424P0,P2,P4,Pl,P3Pl,P0,P3,P4,P2P2,Pl,P0,P3,P4P3,P4,P2,Pl,P0P028.若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。I.若该文件的数据不在内存， 则该进程进入睡眠等待状态； n.请求read系统调用会导致CPU从用户态切换到核心态；m.read系统调用的参数应包含文件的名称A.仅I、nB.仅I、mC.仅n、田d.I、n和田29.一个多道批处理系统中仅有 Pl和P2两个作业，P2比Pl晚5ms到达它们的计算和I/0操作顺序如下：P1:计算60msI/O80ms,计算20msP2:计算120ms,I/O40ms,计算40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。A．240msB．260msC．340msD．360ms30．若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（）。A.在进程结束时能进行处理机调度B.创建新进程后能进行处理机调度C.在进程处于临界区时不能进行处理机调度D.在系统调用完成并返回用户态时能进行处理机调度．下列关于进程和线程的叙述中，正确的是（）。A.不管系统是否支持线程，进程都是资源分配的基本单位B.线程是资源分配的基本单位，进程是调度的基本单位C.系统级线程和用户级线程的切换都需要内核的支持D.同一进程中的各个线程拥有各自不同的地址空间.下列选项中，不能改善磁盘设备 I/O性能的是（ ）。A.重排I/0请求次序B.在一个磁盘上设置多个分区C.预读和滞后写D.优化文件物理块的分布33.在TCP/IP体系结构中，直接为ICMP提供服务的协议是（ ）。A．PPPB．IPC．UDPD．TCP34．在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。A.机械特性B.功能特性C.过程特性D.电气特性35.以太网的MAO议提供的是（ ）。A.无连接不可靠服务B.无连接可靠服务C.有连接不可靠服务D.有连接可靠服务36.两台主机之间的数据链路层采用后退 N帧协议（GBN传输数据，数据传输速率为16kbps,单向传播时延为270ms数据帧长度范围是128〜512字节,接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（）。A．5B．4C．3D．23737．下列关于 IP路由器功能的描述中，正确的是（）。I.运行路由协议，设置路由表；n.监测到拥塞时，合理丢弃 ip分组；出.对收到的ip分组头进行差错校验，确保传输的IP分组不丢失；IV.根据收到的Ip分组的目的Ip地址，将其转发到合适的输出线路上。A.仅田、IVB.仅I、n、mC.仅i、n、ivd.i、n、m、iv.ARPB议的功能是（ ）。A.根据IP地址查询MACft址B.根据MACM址查询IP地址C.根据域名查询IP地址D.根据IP地址查询域名．某主机的 IP地址为，子网掩码为。若该主机向其所在子网发送广播分组，则目的地址可以是（）。A.若用户l与用户2之间发送和接收电子邮件的过程如题 40图所示，则图中①、②、③阶段分别使用的应用层协议可以是（ ）。题40图电子邮件发送接收示意图A．SMTP、SMTP、SMTPPOP3、SMTP、POP3C．POP3、SMTP、SMTPD．SMTP、SMTP、POP3二、综合应用题： 41"--47小题。共70分。41.（10分）设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过 5次两两合并，将6个表最终合并成 1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。（1）给出完整的合并过程，并求出最坏情况下比较的总次数。（2）根据你的合并过程，描述n（n>2）个不等长升序表的合并策略，并说明理由。42．（13分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如题42图所示。题42图存储映像示意图设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为[data,next],请设计一个时间上尽可能高效的算法，找出由strl和str2所指的两个链表共同后缀的起始位置（如图中字符 i所在结点的位置p）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C+域JAVA语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度。43.（11分）假定某计算机的CPU主频为80MHzCPI为4,并且平均每条指令访存次，主存与Cache之间交换的块大小为168,Cache的命中率为99%,存储器总线宽度为32位。请回答下列问题。（1）该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA专送的情况下，主存带宽至少达到多少才能满足 CPU的访存要求？（2）假定在Cache缺失的情况下访问主存时，存在％的缺页率，则 CPU¥均每秒产生多少次缺页异常？若页面大小为4KB,每次缺页都需要访问磁盘，访问磁盘时DMA专送采用周期挪用方式，磁盘 I/O接口的数据缓冲寄存器为32位，则磁盘I/O接口平均每秒发出的DMA青求次数至少是多少？CPUffiDMA空制器同时要求使用存储器总线时， 哪个优先级更高？为什么？（4）为了提高性能，主存采用4体交叉存储模式，工作时每l/4个存储周期启动一个体。若每个体的存储周期为 50ns,则该主存能提供的最大带宽是多少？（12分）某16位计算机中，带符号整数用补码表示，数据Cache和指令Cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，me谯示存储单元地址，（X）表示寄存器X或存储单元X的内容。表指令系统中部分指令格式名称指令的汇编格式指令功能加法指令ADDRsRd(Rs)+(Rd)fRd算术/逻辑左移SHLRd2*(Rd)fRd算术右移SHRRd(Rd)/2fRd取数指令LOADRDmem(mermfRd存数指令STORERsmem(Rs)—mem该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB,流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。（1）若int型变量x的值为-513,存放在寄存器Rl中，则执行指令“SHRRl”后，Rl的内容是多少？（用十六进制表示）(2)若某个时间段中，有连续的 4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少 ？(3)若高级语言程序中某赋值语句为 x=a+b,x、a和b均为int型变量,它们的存储单元地址分别表示为［x］、［司和［b］。该语句对应的指令序列及其在指令流水线中的执行过程如题 44图所示。则这4条指令执行过程中，I3的ID段和14的IF段被阻塞的原因各是什么？(4)若高级语言程序中某赋值语句为 x=2*x+a,x和a均为unsignedint类型变量，它们的存储单元地址分别表示为 ［x］、回，则执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。(7分)某请求分页系统的局部页面置换策略如下：系统从 0时刻开始扫描，每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计)，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41o进程P依次访问的＜虚拟页号，访问时刻＞是：＜1,1＞、＜3,2＞、＜0,4＞、＜0,6＞、＜1,11＞、＜0,13＞、＜2,14＞。请回答下列问题。(1)访问＜0,4＞时，对应的页框号是什么？(2)访问＜1,11＞时，对应的页框号是什么？说明理由。(3)访问＜2,14＞时，对应的页框号是什么？说明理由。(4)该策略是否适合于时间局部性好的程序 ？说明理由。(8分)某文件系统空间的最大容量为 4TB(1T=24°),以磁盘块为基本分配单位，磁盘块大小为IKB。文件控制块(FCB包含一个512B的索引表区。请回答下列问题。(1)假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节 ？(2)假设索引表区采用如下结构：第0〜7字节采用＜起始块号，块数＞格式表示文件创建时预分配的连续存储空间，其中起始块号占 6B,块数占2B;剩余504字节采用直接索引结构，一个索引项占 6B,则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。(9分)主机H通过快速以太网连接Internet,IP地址为，服务器S的IP地址为。H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所不。题47-a表IP分组的前40字节内容(十六进制)019b40008006lde8coa80008d34447500bd91388846b41c500000000 5db00000

20000400031066e833d3444750cOa8000813880bd9e0599fef846b41c66701216d037e100003019c40008006ldefcOa80008d3444750bd91388846b41c6e0599ff0501043802b3200004019d400080061ddecOa80008d34447500bd91388846b4lc6e0599ff0 c655000053106067ad3444750cOa8000813880bd9e0599ff0846b41d6501016d057d20000请回答下列问题。(1)题47-a表中的IP分组中，哪几个是由H发送的？哪几个完成了TCP连接建立过程？哪几个在通过快速以太网传输时进行了填充 ？(2)根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是多少？(3)若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所列，则该IP分组到达H时经过了多少个路由器？题47-b表注:4006eCadd3444750ca7601061388a108e0599ff0846b41d6501016dOb7d60000版本注:4006eCadd3444750ca7601061388a108e0599ff0846b41d6501016dOb7d60000版本头部长度服务类型(8-15)总长度(16-31)标识标志片偏移生存时(TTL)协议头部校验和源IP地址目的IP地址来自S发出的3组IP分组头和TCP段头结构分别如题47-a图、题47-b图所示:题47-a图IP分组头结构源端口(0-15)目的端口(16-31)序号(seq)确认号(ack)数据偏移保留URGACKPSHRSTSYNFIN窗口校验和紧急®#选项(长度可艾) 填充题47-b图TCP段头结构2012年全国硕士研究生入学统一考试 408计算机学科专业基础综合真题及详解一、单项选择题：l〜40小题。每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。.求整数n(n>0)阶乘的算法如下，其时间复杂度是( )。O(log2n)0(n)O(nlog2n)O(n2)【答案】Bo【解析】设fact(n)的运行时间函数是T(n)。该函数中语句①的运行时间是0(1),语句②的运行时间是T(n-1)+O(1),其中O(1)为乘法运算的时间。因此，当n&l时，T(n)-0(1);当n>1时，T(n)=T(n-1)+O(1)。则，T(n)=O(1)+T(n-1)=2XO(1)+T(n-2)=(n-1)xO(1)+T(1)=nxO(1)=0(n)即fact(n)的时间复杂度为O(n)。.已知操作符包括‘+‘、'-'、'*'、'/'、'('和。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是( )。57811【答案】Ao【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符(先出栈的运算符先计算，同优先级的运算符在栈中的先计算)。表达式a+b-a*((c+d)/e-f)+g产生后缀表达式的过程如下表所列：当前字符运算符栈内容后缀表达式说明a++“+”进栈b+ab--ab+“-”与栈顶兀素“+”的优先级相同，则“+”出栈，“-”进栈a-ab+a*-*ab+a"”的优先级大于栈顶兀素“-”，

则“*”进栈(-*(ab+a“(”对它之前后的运算符起隔离作用(-*((ab+a“(”对它之前后的运算符起隔离作用-*((ab+ac+-*((+]ab+ac“+”进栈d-*((+1ab+acd)-*(ab+acd+与其配对的左括号及其前所有运算符出栈/-*(/ab+acd+进栈e-*(/ab+acd+e--*(-ab+acd+e/“-”的优先级小于栈顶兀素“/：则出栈，“-”进栈f-*(-ab+acd+e/f)-*ab+acd+e/f-与其配对的左括号及其前所有运算符出栈+-ab+acd+e/f-*“+”的优先级小于栈顶兀素“*”，则“*”出栈+ab+acd+e/f-*-“+”与栈顶兀素“-”的优先级相同，则“-”出栈，“+”进栈g+ab+acd+e/f-*-gab+acd+e/f-*-g+全部出栈通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。.若一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,则根结点的孩子结点( )。A.只有e.有e、bC.有e、cD.无法确定【答案】Ao【解析】由题目可知，若一棵二叉树的前序遍历序列为 a,e,b,d,c,后序遍历序列为b,c,d,e,a,其中a为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e,而后序遍历的倒数第二个结点为e,说明a的孩子结点只有e。.若平衡二叉树的高度为6,且所有非叶结点的平衡因子均为1,则该平衡二叉树的结点总数为( )。12203233【答案】Bo【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。Nh表示深度为h的平衡二叉树中含有的最少结点数，有 NL=0,N=1,Nb=2Nn=N-i+N-2+1由此可得20。对应的平衡二叉树如下图所示。.对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是( )。0(n)0(e)O(n+e)O(nxe)【答案】Co【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为 O(n2),其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为0(e),其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。即可得出正确答案。.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是( )。A.存在，且唯一.存在，且不唯一不唯一C.存在，可能不唯一D.无法确定是否存在【答案】Co【解析】图的基本应用一一拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但r«\I]不一定唯一，如图的邻接矩阵为 ，则存在两个拓扑序列。0I)停7.有向带权图如题7图所示，若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是()。题7图有向带权图d,e,fe,d,ff,d,ef,e,d【答案】Co【解析】本题主要考查Dijkstra算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为 f,d,e\顶点\^刖数、bcdef集合Sk=12(a,b)5(a,c)(a,b)k=2(a,b,c)(a,b,d){a,b,c}k=3(a,b,d)4(a,b,c,f)(a,b,c,e){a,b,c,f)k=4(a,b,d)(a,b,c,e){a,b,c,f,d)k=5(a,b,d,e){a,b,c,f,d,e)8.下列关于最小生成树的叙述中，正确的是（ ）I.最小生成树的代价唯一 n.所有权值最小的边一定会出现在所有的最小生成树中 田.使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A.仅IB.仅nC.仅I、mD.仅n、iv【答案】Ao【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价一定是相同的，所以说法I正确。从 n个顶点的连通图中选取n-1条权值最小的边可能构成回路，所以说法n错误。当某个顶点有权值相同的边，使用普里姆（Prim）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法出错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树可能相同， 也可能不同，所以说法IV错误。由此可得出正确答案。.设有一棵3阶B树，如题9图所示。删除关键字78得到一棵新B树，其最右叶结点所含的关键字是（ ）。题9图3二叉树图A．60B．60，62C．62，65D．65【答案】 D。【解析】 本题主要考查 B树删除操作。即被删关键字所在的结点中的关键字个数等于[ m/2]-1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于[ m/2] -1，则需将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字 78得到一棵新 B树如下，其最右叶结点所含的关键字是 65。．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。i.简单选择排序 n.希尔排序田.快速排序 iv.堆排V.二路归并排序A.仅I、m、IVB.仅I、n、mC.仅n、m、ivD.仅田、IV、v【答案】 A。【解析】 其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。11．对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。A.排序的总趟数B.元素的移动次数C.使用辅助空间的数量D.元素之间的比较次数【答案】 D。【解析】 折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。折半插入排序的时间复杂度仍为O（n2）,所以两者之间的不同只可能是元素之间的比较次数。12．假定基准程序 A在某计算机上的运行时间为l00秒，其中90秒为CPU时间，其余为I/O时间。若CPU1度提高50%,I/O速度不变，则运行基准程序A所耗费的时间是（）。A．55秒

B．60秒C．65秒D．70秒【答案】D。【解析】CPU1度提高50%,即CPU生能提高比为，改进之后的CPUS行时间=90+=60秒。I/O速度不变，仍维持10秒，所以运行基准程序A所耗费的时间为70秒。13．假定编译器规定 int和short类型长度分别为32位和16位，执行下列C语言语句：unsignedshortX=65530;unsignedinty =X：得至Uy的机器数为（）。A．00007FFAH0000FFFAHC．FFFF7FFAHD．FFFFFFFAH【答案】B。【解析】X和y均为无符号数，其中X为16位，y为32位，将16位无符号数转化成32位无符号数，前面要补零。因为 X=65530=FFFAh|所以y=0000FFFAH。.float类型（即IEEE754单精度浮点数格式）能表示的最大正整数是A．021262103B．A．021262103B．2127-2104C．D．2127-21032128-2104【答案】 D。【解析】 IEEE754单精度浮点数尾数采用隐藏位策略的原码表示， 且阶码用移码表示的浮点数。规格化的短浮点数的真值为：（ -1）SxX2（E-127）,S为符号位，E的取值为1〜254,f为23位；故float类型能表示的最大整数是7X2（254-127）=2127X（2-2-23）=2128-2104。．某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和short型长度分别为32位和16位，并且数据按边界对齐存储。某 C语言程序段如下：若record变量的首地址为0xC008,则地址0xC008中内容及的地址分别为（ ）。A．0x00、0xC00D0x00、0xCOOEC．0x11、0xC00DD．0x11、0xC00E【答案】 D。【解析】32位整数a需要占4个字节，l6位整数c需要占2个字节，而字符数据b占一个字节。a=273，转换成十六进制是111H,采用小端方式存放数据，地址0xC008中的内容为11H。由于数据按边界^^齐存储，地址0xC008〜OxCOOB中存放a,地址0xC00C中存放b,地址0xC00D中空闲，地址0xC00&0xC00F中存放 c。.下列关于闪存（FlashMemory）的叙述中，错误的是（ ）。A.信息可读可写，并且读、写速度一样快B.存储元由MOST组成，是一种半导体存储器C.掉电后信息不丢失，是一种非易失性存储器D.采用随机访问方式，可替代计算机外部存储器【答案】 A。【解析】考查闪存的特性，闪存是EEPROMJ进一步发展，可读可写，用MOS管的浮栅上有无电荷来存储信息，它依然是 ROM勺一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD固态硬盘就是由flash芯片组成的，故答案为 A。.假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为l个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU瞽换算法，当访问的主存地址依次为0，4，8，2，0，6，8，6，4，8时，命中Cache的次数是（）。A．1B．2C．3D．4【答案】 C。【解析】Cache有4个行，2路组相联，即Cache被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9可映射到第0组Cache中，主存地址为2〜3、6〜7可映射到第1组Cache中。Cache初始为空，采用LRU替换算法，当访问主存的10个地址依次为0,4,8,2,0,6,8,6,4,8时，命中Cache的次数共有3次，分别发生在第 7、8和10步时。．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33个微命令，构成5个互斥类，分别包含 7、3、12、5和6个微命令，则操作控制字段至少有（）。A．5位B．6位C．15位D．33位【答案】 C。【解析】 33个微命令分成 5个互斥类（即5个字段），根据每个类中微命令的多少可以分别确定字段的长度为 3、2、4、3、3位，又因为采用直接编码方式，所以它们之和3+2+4+3+3=15也就是操作控制字段的位数。.某同步总线的时钟频率为l00MHz,宽度为32位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输 l28位数据所需要的时间至少是 （ ）。）。A．20nsB．40nsC．50nsD．80ns【答案】 C。【解析】总线的时钟频率为100MHz,则时钟周期为10ns。数据是128位，总线宽度是 32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5=50ns。.下列关于USB总线特性的描述中，错误的是（ ）。A.可实现外设的即插即用和热插拔B.可通过级联方式连接多台外设C.是一种通信总线，可连接不同外设D.同时可传输2位数据，数据传输率高TOC\o"1-5"\h\z【答案】 D。【解析】USB总线即通用串行总线，它的特点有：（1）即插即用；（2）热插拔；（ 3）有很强的链接能力能将所有外设链接起来，且不损失带宽；（ 4）有很好的可扩展性；（5）高速传输，速度可达480Mbp4所有A,B,C都符合USB总线的特点。对于选项D,USB是串行总线，不能同时传输两位数据，所以答案为D。.下列选项中，在I/O总线的数据线上传输的信息包括（ ）。I.I/O接口中的命令字 n.I/0接口中的状态字 m.中断类型号A.仅I、nB.仅I、mC.仅n、田d.I、n、田TOC\o"1-5"\h\z【答案】 D。【解析】在I/O总线的数据线上传输的信息包括 I/O接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。22．响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。.开关中断 n.保存通用寄存器的内容 田.形成中断服务程序入口地址并送 PCA.仅I、nB.仅I、mC.仅n、田d.I、n、田【答案】 B。【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送 PQo而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。23．下列选项中，不可能在用户态发生的事件是（A.系统调用B.外部中断C.进程切换D.缺页【答案】 C。【解析】 我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设定了用户态和内核态（可以通过设置软、硬件标志位来实现），在用户态运行用户的程序，在内核运行系统的程序。所以，从选项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是 scheduler，进程切换是dispather，这体现了现代操作系统策略与机制分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻），必定是在内核态（进程调度）发生的。24．中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）。A.程序计数器B.程序状态字寄存器C.通用数据寄存器D.通用地址寄存器【答案】 B。【解析】 中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关，而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序，并要求其去处理某一事件的一种常用手段。因此，除了要保护当前程序的地址，计数器（指针）和数据寄存器以外，还需要保存程序状态字。子程序调用是与当前进程有关，是正在运行的程序有意安排执行的，这一类调用发生的时间以及位置具有确定性，处于同一个进程内，因此不需要保存程序状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。25．下列关于虚拟存储的叙述中，正确的是（）。A.虚拟存储只能基于连续分配技术B.虚拟存储只能基于非连续分配技术C.虚拟存储容量只受外存容量的限制D.虚拟存储容量只受内存容量的限制【答案】 D。【解析】 所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断技术），将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中的 A,B,C都是错误的，所以答案是D项。26.操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。A.用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序B.用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序C.用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序D.用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序【答案】Ao【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。因此，I/O软件从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。27.假设5个进程P0、Pl、P2、P3、P4共享三类资源Rl、R2R3,这些资源总数分别为18、6、22oTo时刻的资源分配情况如题27表所示，此时存在的一个安全序列是（ ）。题27表资源分配情况表已分配资源资源最大需求进程R1R2R3R1R2R3PO3235510P14O3536P24O54O11P32O4425P4314424P0,P2,P4,Pl,P3Pl,P0,P3,P4,P2P2,Pl,P0,P3,P4P3,P4,P2,Pl,P0P0【答案】Do【解析】典型的死锁避免算法、银行家算法的应用。本题的题型与 2011年的27题相似。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到， P3,P4,P2,Pl,P0运行是可以的。已分配资源尚需资源可用资源进程R1R2R3R1R2R3R1R2R3P32O4221233P4314llO437P24O5O067411P1403113311416PO32323715419本题也可以排除法，To时刻可用资源是R1,R2,R3分另U为2,3,3,此时刻，P0需要R1,R2,R3分另U为2,3,7,故排除A,P1需要R1,R2,R3分另U为1,3,3,P2还需要资源R1,R2,R3分别为0,0,6,故C排除，P3需要R1,R2,R3分别为2,2,1。所以正确答案在B,D之间。看B选项，P1之后的可用资源R1,R2,R3分别变为6,3,6,而P0尚需资源2,3,7,故B方案行不通。因而最终答案只有D项。28.若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。I.若该文件的数据不在内存，则该进程进入睡眠等待状态； n.请求read系统调用会导致CPU从用户态切换到核心态；m.read系统调用的参数应包含文件的名称A.仅I、nB.仅I、mC.仅n、田d.I、n和田【答案】A【解析】对于I,当所读文件的数据不再内存时，产生中断（缺页中断、缺段中断），原进程进入睡眠等待状态（阻塞状态），直到所需数据从外村调入内存后，将该进程唤醒，使其变为就绪状态。对于n,read系统调用CPUW从用户态切换到核心态，从而获取操作系统提供的服务。对于田，在操作系统中，要读一个文件首先要open系统调用将该文件打开。Open系统调用的参数需要包含文件的路径名与文件名，而 read系统调用只需使用open返回的文件描述符，并不使用文件名作为参数。 Read系统调用要求用户提供三个输入参数：①文件描述符；②buf缓冲区首址；③传送的字节数noread系统调用的功能是试图从fd所指示的文件中读入n个字节的数据，并将它们送至由指针 buf所指示的缓冲区中。一个多道批处理系统中仅有Pl和P2两个作业，P2比Pl晚5ms到达。它们的计算和I/0操作顺序如下：P1:计算60msI/O80ms,计算20msP2:计算120ms,I/O 40ms,计算40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。240ms260ms340ms360ms【答案】B。【解析】考查处理系统的性能计算，由于P2比P1晚5ms到达，P1先占用CPU根据P1和P2的执行过程，作业运行的甘特图如下所示，故答案为 Bo30．若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（）。A.在进程结束时能进行处理机调度B.创建新进程后能进行处理机调度C.在进程处于临界区时不能进行处理机调度D.在系统调用完成并返回用户态时能进行处理机调度【答案】 C。【解析】对于A、B、D显然是可以进行处理机调度的，对于C,当进程处于临界区时，只要不破坏临界资源的使用规则，是不会影响处理机调度的，比如，通常访问临界资源可能是慢速的外设（如打印机），如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的。几种不进行处理机调度的情况如下：①在处理机中断的过程中；②进程在操作系统内核程序临界区中；③其他需要完全屏蔽中断的原子操作过程中。．下列关于进程和线程的叙述中，正确的是（）。A.不管系统是否支持线程，进程都是资源分配的基本单位B.线程是资源分配的基本单位，进程是调度的基本单位C.系统级线程和用户级线程的切换都需要内核的支持D.同一进程中的各个线程拥有各自不同的地址空间【答案】 A。【解析】 利用排除法来确定正确答案：“线程是资源分配的基本单位，进程是调度的基本单位”这句话说反了，明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确，因为用户级线程的切换由用户编写的RuntimeSystem执行的，内核并不感知。“同一进程中的各个线程拥有各自不同的地址空间”明显错误，引入线程的目的就是为了同一进程的所有线程能共享进程的地址空间，故“不管系统是否支持线程，进程都是资源分配的基本单位”是正确的。.下列选项中，不能改善磁盘设备 I/O性能的是（ ）。A.重排I/0请求次序B.在一个磁盘上设置多个分区C.预读和滞后写D.优化文件物理块的分布【答案】B。【解析】磁盘I/O性能主要是指其读写速度。相对而言，磁盘的I/O性能是计算机性能提高的一个瓶颈。“重排 I/O请求次序”可以优化磁臂调度的算法，减少读写时间，故正确；“预读和滞后写”是利用内存作为磁盘的缓存，使得对磁盘的访问变为对内存的访问，也可以在总体上提高其性能；“优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间，也可以提高磁盘 I／O性能，而磁盘分区仅在磁盘空间的组织上进行划分，对磁盘I/O性能的提升没有什么帮助，是不能改善磁盘设备 I/O性能的，故答案为Bo33.在TCP/IP体系结构中，直接为ICMP提供服务的协议是（ ）。A．PPPB．IPC．UDPD．TCP【答案】B。【解析】首先明确ICMP是网络层的协议，由于服务必须是下一层向上一层提供服务的，因此选项C项中的UD济口选项D项中的TCP属于传输层，在网络层上面，所以显然错误，而PPPW议是广域网数据链路层协议，直接为网络层，也就是IP层提供服务，ICMP协议是封装在网络层，因此PPP不能直接为ICMP提供服务，ICMP报文直接封装在IP分组中，故答案是Bo34．在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。A.机械特性B.功能特性C.过程特性D.电气特性【答案】 C。【解析】 物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程，也就是过程特性，答案是 C。35.以太网的MAO议提供的是（ ）。A.无连接不可靠服务B.无连接可靠服务C.有连接不可靠服务D.有连接可靠服务【答案】A。【解析】考查以太网MA的议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。36.两台主机之间的数据链路层采用后退N帧协议（GBN传输数据，数据传输速率为16kbps,单向传播时延为270ms数据帧长度范围是128〜512字节,接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（）。A．5B．4C．3D．237TOC\o"1-5"\h\z【答案】 B。【解析】GBN勺工作原理如下图所示，本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节，因此首先计算出发送一帧的时间 t1=128X8/16kbps=64ms,故发送一帧到收到确认为止的总时间为 ；64+270*2+64=668ms.这段时间总共可以发送668/64=（帧），为了保证发送帧序号和确认帧序号在此期间不重复，因此帧序号的比特数至少为 4，答案为 B37．下列关于 IP路由器功能的描述中，正确的是（）。I.运行路由协议，设置路由表；n.监测到拥塞时，合理丢弃 ip分组；出.对收到的ip分组头进行差错校验，确保传输的 IP分组不丢失；IV.根据收到的Ip分组的目的Ip地址，将其转发到合适的输出线路上。A.仅田、IVB.仅I、n、mC.仅i、n、ivd.i、n、m、ivTOC\o"1-5"\h\z【答案】 C。【解析】路由器的主要功能是路由和转发，因此I和IV是正确的，而针对

n和田，可以从icmp协议的差错控制出发，注意检测到拥塞时，合理丢弃 ip分组，并回传ICMP源抑制报文，n是正确的，而田对收到的IP分组头进行差错校验，确保传输的ip分组不丢失，差错校验是正确的，但网络层不保证 ip分组不丢失，也就是不可靠的，因此田的说法错误，正确的说法仅I、n、iv,因此答案是 C。.ARPB议的功能是（ ）。A.根据IP地址查询MACM址B.根据MACM址查询IP地址C.根据域名查询IP地址D.根据IP地址查询域名TOC\o"1-5"\h\z【答案】 A。【解析】ARPW议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项 C和D是不正确的，根据MAO址查询IP地址是RAR的议的功能，因此进而得出正确答案是 Ao．某主机的 IP地址为，子网掩码为。若该主机向其所在子网发送广播分组，则目的地址可以是（）。A．【答案】D。【解析】.，也就是，因此答案是 D。40．若用户 l与用户2之间发送和接收电子邮件的过程如题40图所示，则图中①、②、③阶段分别使用的应用层协议可以是（ ）。题40图电子邮件发送接收示意图A．SMTP、SMTP、SMTPPOP3、SMTP、POP3C．POP3、SMTP、SMTPD．SMTP、SMTP、POP3【答案】 D。【解析】 题中电子邮件的工作过程如下：①用户l调用用户代理来编辑要发送的邮件，用户代理用 SMTP等邮件传送给用户1的发送端邮件服务器。②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列中，等待发送。③运行在发送端邮件服务器的SMT喀户进程，发现在邮件缓存中有待发送的邮件，就向运行在接收端邮件