汕头大学工学院830计算机基础综合历年考研真题0p

830计算机基础综合历年考研真题答案附后汇编2013年开始自主命题，科目改为830计算机基础综合。为帮助考生全面复习，特提供2009～2012年408计算机学科专业基础综合真题及详解。第一部分汕头大学工学院830计算机基础综合历年考研真题汇编2014年汕头大学工学院830计算机基础综合考研真题2013年汕头大学工学院830计算机基础综合考研真题第二部分全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题个选项中，只有一个选项是最符合题目要求的。1．求整数n（n≥0）阶乘的算法如下，其时间复杂度是。A．O（logn）2B．0（n）C．O（nlogn）2D．O（n2）2．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘（’和‘）’。将中缀表达式a+b-a*c+de-f）+g转换为等价的后缀表达式ab+acd+e／f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是。A．5B．7C．8D．11d，e，a，则根结点的孩子结点。A．只有eD．无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为。A．12B．20C．32D．335．对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是。A．0（n）B．0（e）C．O（n+e）D．O（n×e）6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是。D．无法确定是否存在7．有向带权图如题7图所示，若采用迪杰斯特拉（Dijkstra）算法求从源条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是()。A．d,e,fB．e，d，fC．f，d，eD．f，e，d8．下列关于最小生成树的叙述中，正确的是。最小生成树中Ⅲ.使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A．仅ⅠB．仅ⅡC．仅Ⅰ、ⅢD．仅Ⅱ、Ⅳ其最右叶结点所含的关键字是。A．60B．60，62C．62，65D．6510．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置并排序A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、Ⅳ11．对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可A．排序的总趟数B．元素的移动次数C．使用辅助空间的数量D．元素之间的比较次数12．假定基准程序A在某计算机上的运行时间为l00秒，其中90秒为CPU时间，其余为I/O时间。若CPU速度提高50I/O速度不变，则运行基准程序A所耗费的时间是。A．55秒B．60秒C．65秒D．70秒13．假定编译器规定int和short类型长度分别为32位和16位，执行下A．00007FFAHB．0000FFFAHC．FFFF7FFAHD．FFFFFFFAH14．float类型（即IEEE754单精度浮点数格式）能表示的最大正整数是()。A．2126-2103B．2127-2104C．2127-2103D．2128-210415．某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和short型长度分别为32位和16位，并且数据按边界对齐存储。某C若record变量的首地址为0xC008，则地址0xC008中内容及recordA．0x00、0xC00DB．0x00、0xCOOEC．0x11、0xC00DD．0x11、0xC00E16．下列关于闪存（FlashMemory）的叙述中，错误的是。A．信息可读可写，并且读、写速度一样快B．存储元由MOS管组成，是一种半导体存储器C．掉电后信息不丢失，是一种非易失性存储器D．采用随机访问方式，可替代计算机外部存储器大小为l个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU替A．1B．2C．3D．418．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有。C．15位D．33位19．某同步总线的时钟频率为l00MHz，宽度为32位，地址／数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方A．20nsB．40nsC．50nsD．80ns20．下列关于USB总线特性的描述中，错误的是。A．可实现外设的即插即用和热插拔B．可通过级联方式连接多台外设C．是一种通信总线，可连接不同外设D．同时可传输2位数据，数据传输率高B．仅Ⅰ、ⅢC．仅Ⅱ、Ⅲ包括。地址并送PCB．仅Ⅰ、ⅢC．仅Ⅱ、Ⅲ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，这些资源总数分别为l8、6、22。T时刻的资源分配情况如题27表所示，此时存在的0题27表资源分配情况表已分配资源已分配资源资源最大需求A．P0，P2，P4，Pl，P3B．Pl，P0，P3，P4，P2C．P2，Pl，P0，P3，P4D．P3，P4，P2，Pl，P0P0列关于此过程的叙述中，正确的是。系统调用会导致CPU从用户态切换到核心态；Ⅲ.read系统调用的参数应包含文件的名称B．仅Ⅰ、ⅢC．仅Ⅱ、ⅢP2：计算120ms，I／O40ms，计算40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是。A．240msB．260msC．340msD．360ms30．若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是。A．在进程结束时能进行处理机调度B．创建新进程后能进行处理机调度C．在进程处于临界区时不能进行处理机调度D．在系统调用完成并返回用户态时能进行处理机调度31．下列关于进程和线程的叙述中，正确的是。A．不管系统是否支持线程，进程都是资源分配的基本单位B．线程是资源分配的基本单位，进程是调度的基本单位C．系统级线程和用户级线程的切换都需要内核的支持D．同一进程中的各个线程拥有各自不同的地址空间32．下列选项中，不能改善磁盘设备I／O性能的是。A．重排I／0请求次序B．在一个磁盘上设置多个分区C．预读和滞后写D．优化文件物理块的分布A．PPPB．IPC．UDPD．TCP34．在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是()。A．机械特性B．功能特性C．过程特性D．电气特性35．以太网的MAC协议提供的是。A．无连接不可靠服务B．无连接可靠服务C．有连接不可靠服务D．有连接可靠服务36．两台主机之间的数据链路层采用后退N帧协议（GBN）传输数据，数据接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为。A．5B．4C．3D．23737．下列关于IP路由器功能的描述中，正确的是。收到的IP分组的目的IP地址，将其转发到合适的输出线路上。A．仅Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅰ、Ⅱ、Ⅳ38．ARP协议的功能是。A．根据IP地址查询MAC地址B．根据MAC地址查询IP地址C．根据域名查询IP地址D．根据IP地址查询域名39．某主机的IP地址为5，子网掩码为。若该A．B．55C．55D．5540．若用户l与用户2之间发送和接收电子邮件的过程如题40图所示，则图中①、②、③阶段分别使用的应用层协议可以是。题40图电子邮件发送接收示意图A．SMTP、SMTP、SMTPB．POP3、SMTP、POP3C．POP3、SMTP、SMTPD．SMTP、SMTP、POP34110分）设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。（1）给出完整的合并过程，并求出最坏情况下比较的总次数。（2）根据你的合并过程，描述n（n≥2）个不等长升序表的合并策略，并4213分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存题42图存储映像示意图设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为[data，next]，请设计一个时间上尽可能高效的算法，找出由strl和str2所指的两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：（1）给出算法的基本设计思想。（3）说明你所设计算法的时间复杂度。4311分）假定某计算机的CPU主频为80MHz，CPI为4，并且平均每条存储器总线宽度为32位。请回答下列问题。（1）该计算机的MIPS数是多少平均每秒Cache缺失的次数是多少在不考虑DMA传送的情况下，主存带宽至少达到多少才能满足CPU的访存要求（2）假定在Cache缺失的情况下访问主存时，存在0.0005％的缺页率，则CPU平均每秒产生多少次缺页异常若页面大小为4KB，每次缺页都需要访问磁盘，访问磁盘时DMA传送采用周期挪用方式，磁盘I／O接口的数据缓冲寄存器为32位，则磁盘I／O接口平均每秒发出的DMA请求次数至少是多少（3）CPU和DMA控制器同时要求使用存储器总线时，哪个优先级更高为什么（4）为了提高性能，主存采用4体交叉存储模式，工作时每l/4个存储周期启动一个体。若每个体的存储周期为50ns，则该主存能提供的最大带宽是多少令Cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单元地址X）表示寄存器X或存储单元X的内容。表指令系统中部分指令格式加法指令算术／逻辑左移加法指令算术／逻辑左移算术右移取数指令指令功能2*（Rd）→Rd（Rd2→Rd（mem）→RdADDRs，RdSHLRdSHRRdLOADRD，mem存数指令STORERs，mem（Rs）→mem该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行／计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB流水线采用“按序发射，按序完成”方式，没有采用转发技术题47-a表处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。（1）若int型变量x的值为-513，存放在寄存器Rl中，则执行指令“SHR（2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少（3）若高级语言程序中某赋值语句为x＝a+b，x、a和b均为int型变量，它们的存储单元地址分别表示为[x]、[a]和[b]。该语句对应的指令序列及其在34（4）若高级语言程序中某赋值语句为x＝2*x+a，x和a均为unsignedint类型变量，它们的存储单元地址分别表示为[x]、[a]，则执行这条语句至少需要多少个时钟周期要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。457分）某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程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）该策略是否适合于时间局部性好的程序说明理由。468分）某文件系统空间的最大容量为4TB（1T＝240以磁盘块为基请回答下列问题。（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节可支持的单个文件最大长度是多少字节（2）假设索引表区采用如下结构：第0～7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，则可支持的单个文件最大长度是多少字节为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。服务器S的IP地址为0。H与S使用TCP通信时，在H上捕获的其IPIP分组的前40字节内容（十六进制）019b40008006lde8coa80008d34447500bd91388846b41c5000000005db000000000400031066e833d3444750cOa8000813880bd9e0599fef846b41c66701216d037e10000019c40008006ldefcOa80008d3444750bd91388846b41c6e0599ff0501043802b320000019d400080061ddecOa80008d34447500bd91388846b4lc6e0599ff0c65500003106067ad3444750cOa8000813880bd9e0599ff0846b41d6501016d057d20000请回答下列问题。12345（1）题47-a表中的IP分组中，哪几个是由H发送的哪几个完成了TCP连接建立过程哪几个在通过快速以太网传输时进行了填充（2）根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是（3）若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所列，则该IP分组到达H时经过了多少个路由器题47-b表4006eCad1388a108e0599ff0846b41d6501016dOb7d60000总长度（16-31）总长度（16-31）标志片偏移头部校验和服务类型协议标识生存时（TTL）头部长度版本源端口（0-15）源端口（0-15）目的端口（16-31）确认号（ack）UAPRSFGKHTNN校验和紧急指针 2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解个选项中，只有一个选项是最符合题目要求的。1．求整数n（n≥0）阶乘的算法如下，其时间复杂度是。A．O（logn）2B．0（n）C．O（nlogn）2D．O（n2）【答案】B。【解析】设fact（n）的运行时间函数是T（n）。其中O（1）为乘法运算的时间。=2×O（1）+T（n-2n-1）×O（1）+T（1n×O（1）=O（n）即fact（n）的时间复杂度为O（n）。2．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘（’和‘）’。将中缀表达式a+b-a*c+de-f）+g转换为等价的后缀表达式ab+acd+e／f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是。A．5B．7C．8D．11【答案】A。【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）。表达式a+b-a*c+de-f）+g产生后缀表达式的过程如下表所列：a运算符栈内容后缀表达式++“+”进栈b+ “-”与栈顶元素“+”的优先级a-ab+a*ab+a则“*”进栈（ab+a“（”对它之前后的运算符起隔离作用（ab+aab+ac“（”对它之前后的运算符起隔离作用+-*+ab+ac“+”进栈d-*+ab+acd）ab+acd+与其配对的左括号及其前所有运算符出栈／ab+acd+eab+acd+e“-”的优先级小于栈顶元素-*（-ab+acd+e／栈f-*（-ab+acd+e／f）ab+acd+e／f-与其配对的左括号及其前所有运算符出栈+-+ab+acd+e／f-*f-*-则“*”出栈“+”与栈顶元素“-”的优先级相同，则“-”出栈，“+”进栈g+f-*-gf-*-g+全部出栈通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。d，e，a，则根结点的孩子结点。A．只有eD．无法确定【答案】A。序遍历序列为b，c，d，e，a，其中a为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e，而后序遍历的倒数第二个结点为e，说明a的孩子结点4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为。A．12B．20C．32D．33【答案】B。【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的由此可得N＝20。对应的平衡二叉树如下图所示。55．对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是。A．0（n）B．0（e）C．O（n+e）D．O（n×e）【答案】C。【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O（n2其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为0（e），其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O（n+e）。即可得出正确答案。6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是。A．存在，且唯一B．存在，且不唯一不唯一C．存在，可能不唯一D．无法确定是否存在【答案】C。【解析】图的基本应用——拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为，则存在两个拓扑序列。7．有向带权图如题7图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是()。A．d,e,f顶顶B．e，d，fC．f，d，eD．f，e，d【答案】C。【解析】本题主要考查Dijkstra算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstra算法过程中各步的状态表，故后续目标顶点依次为f,d,e。集合集合Sc5k＝1k＝2k＝3k＝4k＝5bb）点趟数8．下列关于最小生成树的叙述中，正确的是。最小生成树中Ⅲ.使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A．仅ⅠB．仅ⅡC．仅Ⅰ、ⅢD．仅Ⅱ、Ⅳ【答案】A。【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价一定是相同的，所以说法Ⅰ正确。从n个顶点的连通图中选取n-1条权值最小的边可能构成回路，所以说法Ⅱ错误。当某个顶点有权值相同的边，使用普里姆（Prim）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法Ⅲ错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡由此可得出正确答案。其最右叶结点所含的关键字是。A．55秒A．60B．60，62C．62，65D．65【答案】D。【解析】本题主要考查B树删除操作。即被删关键字所在的结点中的关键字个数等于［m/2］-1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于［m/2］-1，则需将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B树如下，其最右叶结点所含的关键字是65。10．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置并排序A．仅Ⅰ、Ⅲ、Ⅳ【答案】A。【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。11．对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可A．排序的总趟数B．元素的移动次数C．使用辅助空间的数量D．元素之间的比较次数【答案】D。【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。折半插入排序的时间复杂度仍为O（n2）,所以两者之间的不同只可能是元素之间的比较次数。12．假定基准程序A在某计算机上的运行时间为l00秒，其中90秒为CPU时间，其余为I/O时间。若CPU速度提高50I/O速度不变，则运行基准程序A所耗费的时间是。B．60秒C．65秒D．70秒【答案】D。【解析】CPU速度提高50即CPU性能提高比为l.5，改进之后的CPU运行时间＝90÷1.5＝60秒。I/O速度不变，仍维持l0秒，所以运行基准程序A所耗费的时间为70秒。13．假定编译器规定int和short类型长度分别为32位和16位，执行下A．00007FFAHB．0000FFFAHC．FFFF7FFAHD．FFFFFFFAH【答案】B。X和y均为无符号数，其中X为16位，y为32位，将16位无符号数转化成32位无符号数，前面要补零。因为X＝65530＝FFFAH，所以y=0000FFFAH。14．float类型（即IEEE754单精度浮点数格式）能表示的最大正整数是()。A．2126-2103B．2127-2104C．2127-2103D．2128-2104【答案】D。【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码×2（254-1272127×（2-2-232128-2104。15．某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规语言程序段如下：若record变量的首地址为0xC008，则地址0xC008中内容及recordA．0x00、0xC00DB．0x00、0xCOOEC．0x11、0xC00DD．0x11、0xC00E【答案】D。地址0xC008中的内容为11H。由于数据按边界对齐存储，地址0xC008～OxCOOB中存放a，地址0xC00C中存放b，地址0xC00D中空闲，地址0xC00E～0xC00F16．下列关于闪存（FlashMemory）的叙述中，错误的是。A．信息可读可写，并且读、写速度一样快B．存储元由MOS管组成，是一种半导体存储器C．掉电后信息不丢失，是一种非易失性存储器D．采用随机访问方式，可替代计算机外部存储器【答案】A。管的浮栅上有无电荷来存储信息，它依然是ROM的一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD固态硬盘就是由flash芯片组成的，故答案为A。A．1B．2C．3D．4【答案】C。主存地址为0～1、4～5、8～9可映射到第0组Cache中，主存地址为2～3的10个地址依次为0，4，8，2，0，6，8，6，4，8时，命中Cache的次数共18．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有。C．15位D．33位【答案】C。【解析】33个微命令分成5个互斥类（即5个字段根据每个类中微命令的多少可以分别确定字段的长度为3、2、4、3、3位，又因为采用直接编码19．某同步总线的时钟频率为l00MHz，宽度为32位，地址／数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方A．20nsB．40nsC．50nsD．80ns【答案】C。【解析】总线的时钟频率为l00MHz，则时钟周期为10总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5＝50ns。20．下列关于USB总线特性的描述中，错误的是。A．可实现外设的即插即用和热插拔B．可通过级联方式连接多台外设C．是一种通信总线，可连接不同外设D．同时可传输2位数据，数据传输率高【答案】D。【解析】USB总线即通用串行总线，它的特点有1）即插即用2）热插拔3）有很强的链接能力能将所有外设链接起来，且不损失带宽4）有很好的可扩展性；（5）高速传输，速度可达480Mbps。所有A，B，C都符合USB总线的特点。对于选项D,USB是串行总线，不能同时传输两位数据，所以答案为D。21．下列选项中，在I／O总线的数据线上传输的信息包括。B．仅Ⅰ、ⅢC．仅Ⅱ、Ⅲ【答案】D。【解析】在I／O总线的数据线上传输的信息包括I／O接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。22．响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还地址并送PCB．仅Ⅰ、ⅢC．仅Ⅱ、Ⅲ【答案】B。中断服务程序（形成中断服务程序入口地址并送PC）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。23．下列选项中，不可能在用户态发生的事件是。A．系统调用B．外部中断C．进程切换D．缺页【答案】C。【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为在用户态运行用户的程序，在内核运行系统的程序。所以，从选项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler，进程切换是dispather，这体现了现代操作系统策略与机制分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻），必定是在内核态（进程调度）发生的。24．中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是。A．程序计数器B．程序状态字寄存器C．通用数据寄存器D．通用地址寄存器【答案】B。【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关，而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序，并要求其去处理某一事件的一种常用手段。因此，除了要保护当前程序的地址，计数器（指针）和数据寄存器以外，还需要保存程序状态字。子程序调用是与当前进程有关，是正在运行的程序有意安排执行的，这一类调状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。A．虚拟存储只能基于连续分配技术B．虚拟存储只能基于非连续分配技术C．虚拟存储容量只受外存容量的限制D．虚拟存储容量只受内存容量的限制【答案】D。【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分存时，通过一种技术（例如缺页中断技术将所需要的页面调入内存，从而外存以及相应的软、硬件机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中的A,B,C都是错误的，所以答案是D项。26．操作系统的I／O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是。A．用户级I／O软件、设备无关软件、设备驱动程序、中断处理程序B．用户级I／O软件、设备无关软件、中断处理程序、设备驱动程序C．用户级I／O软件、设备驱动程序、设备无关软件、中断处理程序D．用户级I／O软件、中断处理程序、设备无关软件、设备驱动程序【答案】A。【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。因此，I/O软件从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。27．假设5个进程P0、Pl、P2、P3、P4共享三类资源Rl、R2、R3，这些资源总数分别为l8、6、22。T时刻的资源分配情况如题27表所示，此时存在的0一个安全序列是。题27表资源分配情况表已分配资源已分配资源资源最大需求A．P0，P2，P4，Pl，P3B．Pl，P0，P3，P4，P2C．P2，Pl，P0，P3，P4D．P3，P4，P2，Pl，P0P0【答案】D。【解析】典型的死锁避免算法、银行家算法的27题相似。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到，P3，P4，P2，Pl，P0运行已分配资源已分配资源尚需资源可用资源332323372474370R3分别变为6,3，6，而P0尚需资源2,3,7，故B方案行不通。因而最终答案28．若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是。系统调用会导致CPU从用户态切换到核心态；Ⅲ.read系统调用的参数应包含文件的名称A．仅Ⅰ、ⅡB．仅Ⅰ、ⅢC．仅Ⅱ、ⅢA【解析】对于Ⅰ,当所读文件的数据不再内存时，产生中断（缺页中断、缺段中断原进程进入睡眠等待状态（阻塞状态直到所需数据从外村调从用户态切换到核心态，从而获取操作系统提供的服务。对于Ⅲ,在操作系统中，要读一个文件首先要open系统调用将该文件打开。Open系统调用的参数需要包含文件的路径名与文件名，而read系统调用只需使用open返回的文件描述符，并不使用文件名作为参数。Read系统调用要求用户提供三个输入参数：①文件描述符；②buf缓冲区首址；③传送的字节数n。read系统调用的功能是示的缓冲区中。29．一个多道批处理系统中仅有Pl和P2两个作业，P2比Pl晚5ms到达。它们的计算和I／0操作顺序如下：P1：计算60ms，I／O80ms，计算20ms；P2：计算120ms，I／O40ms，计算40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是。A．240msB．260msC．340msD．360ms【答案】B。CPU,根据P1和P2的执行过程，作业运行的甘特图如下所示，故答案为B。30．若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是。A．在进程结束时能进行处理机调度B．创建新进程后能进行处理机调度C．在进程处于临界区时不能进行处理机调度D．在系统调用完成并返回用户态时能进行处理机调度【答案】C。【解析】对于A、B、D显然是可以进行处理机调度的，对于C，当进程处于临界区时，只要不破坏临界资源的使用规则，是不会影响处理机调度的，比如，通常访问临界资源可能是慢速的外设（如打印机），如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的。几种不进行处理机调度的情况如下：①在处理机中断的过程中；②进程在操作系统内核程序临界区中；③其他需要完全屏蔽中断的原子操作过程中。A．不管系统是否支持线程，进程都是资源分配的基本单位B．线程是资源分配的基本单位，进程是调度的基本单位C．系统级线程和用户级线程的切换都需要内核的支持D．同一进程中的各个线程拥有各自不同的地址空间【答案】A。【解析】利用排除法来确定正确答案：“线程是资源分配的基本单位，进程是调度的基本单位”这句话说反了，明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确，因为用户级线程的切换由用户编写的的地址空间”明显错误，引入线程的目的就是为了同一进程的所有线程能共享进程的地址空间，故“不管系统是否支持线程，进程都是资源分配的基本单位”32．下列选项中，不能改善磁盘设备I／O性能的是。A．重排I／0请求次序B．在一个磁盘上设置多个分区C．预读和滞后写D．优化文件物理块的分布【答案】B。【解析】磁盘I／O性能主要是指其读写速度。相对而言，磁盘的I／O性能是计算机性能提高的一个瓶颈。“重排I／O请求次序”可以优化磁臂调度的算法，减少读写时间，故正确；“预读和滞后写”是利用内存作为磁盘的缓存，使得对磁盘的访问变为对内存的访问，也可以在总体上提高其性能；“优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间，也可以提高磁盘I／OA．5性能，而磁盘分区仅在磁盘空间的组织上进行划分，对磁盘I／O性能的提升没有什么帮助，是不能改善磁盘设备I／O性能的，故答案为B。33．在TCP／IP体系结构中，直接为ICMP提供服务的协议是。A．PPPB．IPC．UDPD．TCP【答案】B。【解析】首先明确ICMP是网络层的协议，由于服务必须是下一层向上一层提供服务的，因此选项C项中的UDP和选项D项中的TCP属于传输层，在网络层上面，所以显然错误，而PPP协议是广域网数据链路层协议，直接为网络层，34．在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是()。A．机械特性B．功能特性C．过程特性D．电气特性【答案】C。【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程，也就是过程特性，答案是C。35．以太网的MAC协议提供的是。A．无连接不可靠服务B．无连接可靠服务C．有连接不可靠服务D．有连接可靠服务【答案】A。【解析】考查以太网MAC协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的36．两台主机之间的数据链路层采用后退N帧协议（GBN）传输数据，数据接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为。B．4C．3D．237【答案】B。个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节，因此首先计算出发送一帧的时间t1=128×8/16kbps＝64ms，故发送一帧到收到确认为止的总时间为;64+270*2+64=668ms，这段时间总共可以发送668/64＝10.4（帧），为了保证发送帧序号和确认帧序号在此期间不重复，因此帧序号的比特数至少为4，答案为B37．下列关于IP路由器功能的描述中，正确的是。收到的IP分组的目的IP地址，将其转发到合适的输出线路上。A．仅Ⅲ、Ⅳ【答案】C。【解析】路由器的主要功能是路由和转发，因此Ⅰ和Ⅳ是正确的，而针对Ⅱ和Ⅲ,可以从ICMP协议的差错控制出发，注意检测到拥塞时，合理丢弃IP因此答案是C。38．ARP协议的功能是。A．根据IP地址查询MAC地址B．根据MAC地址查询IP地址C．根据域名查询IP地址D．根据IP地址查询域名【答案】A。【解析】ARP协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C和D是不正确的，根据MAC地址查询IP地址是RARP协议的功能，因此进而得出正确答案是A。39．某主机的IP地址为5，子网掩码为。若该A．B．55C．55D．55【答案】D。【解析】.80.01001111.255，40．若用户l与用户2之间发送和接收电子邮件的过程如题40图所示，则图中①、②、③阶段分别使用的应用层协议可以是。题40图电子邮件发送接收示意图A．SMTP、SMTP、SMTPB．POP3、SMTP、POP3C．POP3、SMTP、SMTPD．SMTP、SMTP、POP3【答案】D。【解析】题中电子邮件的工作过程如下：①用户l调用用户代理来编辑要发送的邮件，用户代理用SMTP将邮件传送②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列③运行在发送端邮件服务器的SMTP客户进程，发现在邮件缓存中有待发送的邮件，就向运行在接收端邮件服务器也就是用户2的邮件服务器的SMTP服务④运行在接收端邮件服务器中的SMTP服务器进程收到邮件后，将邮件放人收信人的用户邮箱中，等待收信人在他方便时进行读取。收信人在打算收信时，调用用户代理，使用POP协议将自己的邮件从接收端邮件服务器的用户邮箱中取回（如果邮箱中有来信的话）。因此题中1，2，3阶段分别使用的应用层协议可以是SMTP，SMTP，POP3，因此答案是D。SMTP采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。4110分）设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。（1）给出完整的合并过程，并求出最坏情况下比较的总次数。说明理由。（1）6个表的合并顺序如下图所示。对应于合并过程的哈夫曼树根据上图中的哈夫曼树，6个序列的合并过程为：第1次合并：表A与表B合并，生成含45个元素的表AB；第3次合并：表D与表E合并，生成含ll0个元素的表DE；第4次合并：表ABC与表DE合并，生成含l95个元素的表ABCDE；第5次合并：表ABCDE与表F合并，生成含395个元素的最终表。由于合并两个长度分别为m和n的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：第1次合并：最多比较次数＝10+35-1＝44；第2次合并：最多比较次数＝45+40-l＝84；第3次合并：最多比较次数＝50+60-1＝109；第4次合并：最多比较次数＝85+110-1＝194；第5次合并：最多比较次数＝195+200-1＝394；比较的总次数最多为：44+84+109+194+394＝825。（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。解析：本题具有较强的综合性，主要考查了构造哈夫曼树的算法思想和过程、归并排序的过程等。4213分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如题42图所示。题42图存储映像示意图设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为指的两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：（1）给出算法的基本设计思想。（3）说明你所设计算法的时间复杂度。（1）算法的基本设计思想：①分别求出strl和str2所指的两个链表的长度m和n；②将两个链表以表尾对齐：令指针p、q分别指向strl和str2的头结点，若m>n，则使p指向链表中的第n+1个结点；若m<n，则使q指向链表中的第③反复将指针p和q同步向后移动，并判断它们是否指向同一结点。若p和q指向同一结点，则该点即为所求的共同后缀的起始位置。n分别为两个链表的长度。4311分）假定某计算机的CPU主频为80MHz，CPI为4，并且平均每条存储器总线宽度为32位。请回答下列问题。（1）该计算机的MIPS数是多少平均每秒Cache缺失的次数是多少在不考虑DMA传送的情况下，主存带宽至少达到多少才能满足CPU的访存要求（2）假定在Cache缺失的情况下访问主存时，存在0.0005％的缺页率，则CPU平均每秒产生多少次缺页异常若页面大小为4KB，每次缺页都需要访问磁盘，位，则磁盘I／O接口平均每秒发出的DMA请求次数至少是多少（3）CPU和DMA控制器同时要求使用存储器总线时，哪个优先级更高为什么（4）为了提高性能，主存采用4体交叉存储模式，工作时每l/4个存储周期启动一个体。若每个体的存储周期为50ns，则该主存能提供的最大带宽是多少平均每秒Cache缺失的次数为：20M×1.5×（1-99300000；此时，主存带宽为：16B×300000/s＝4．8MB/s。在不考虑DMA传输的情况下，主存带宽至少达到4．8MB/s才能满足CPU的访存要求。（2）平均每秒钟“缺页”异常次数为：300000×0.0005l.5次；因为存储器总线宽度为32位，所以，每传送32位数据，磁盘控制器发出一次DMA请求，故平均每秒磁盘DMA请求的次数至少为：1.5×4KB/4B＝1.5K=因为若DMA请求得不到及时响应，I／O传输数据可能会丢失。（4）4体交叉存储模式能提供的最大带宽为：4×4B/50ns＝320MB/s。4412分）某16位计算机中，带符号整数用补码表示，数据Cache和指存器，mem表示存储单元地址X）表示寄存器X或存储单元X的内容。表指令系统中部分指令格式名称指令的汇编格式指令功能加法指令ADDRs，Rd（Rs）+（Rd）→Rd算术／逻辑左移SHLRd2*（Rd）→Rd算术右移SHRRd（Rd2→Rd取数指令LOADRD，mem（mem）→Rd存数指令STORERs，mem（Rs）→mem/读寄存器（ID）、执行／计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。（1）若int型变量x的值为-513，存放在寄存器Rl中，则执行指令“SHR（2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少（3）若高级语言程序中某赋值语句为x＝a+b，x、a和b均为int型变量，它们的存储单元地址分别表示为[x]、[a]和[b]。该语句对应的指令序列及其在34（4）若高级语言程序中某赋值语句为x＝2*x+a，x和a均为unsignedint类型变量，它们的存储单元地址分别表示为[x]、[a]，则执行这条语句至少需要多少个时钟周期要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。（1）x的机器码为[x]补＝111111011111B,即指令执行前（R1FDFFH，右移1wei后为1111111011111111B，即指令执行后（R1FEFFH。（2）至少需要5+（4-18个时钟周期数。（4）x＝2*x+a对应的指令序列为：I3SHLRlR1//或者ADDR1，R1这5条指令在流水线中的执行过程如下图所示，执行x＝2*x+a语句最少需457分）某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程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）该策略是否适合于时间局部性好的程序说明理由。（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。（2）页框号为32。理由：因11>10故发生第三轮扫描，页号为l、3的页框32、15在第二轮已处于空闲页框链表中，此刻l页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。因此从空闲页框链表中取出链表头的页框41，页框号为41。（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。468分）某文件系统空间的最大容量为4TB（1T＝240以磁盘块为基请回答下列问题。（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节可支持的单个文件最大长度是多少字节（2）假设索引表区采用如下结构：第0～7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，则可支持的单个文件最大长度是多少字节为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。（1）文件系统存储空间共有块数242／210＝232。为表示232个块号，索引表项占32／8＝4B，512B可存放27个索引项，每个索引项对应一个磁盘块，故最大文件长度：27×210B＝217B＝128KB。/6）×210＝64MB+84KB＝65620KB。合理的起始块号和块数所占字节数分别为<4,4>（或<0，8>或<1，7>或<2，6>或<3，5>）。理由：块数占4B或以上，就可表示4TB大小的文件长度，达到文件系统的空间上限。服务器S的IP地址为0。H与S使用TCP通信时，在H上捕获的其题47-a表IPIP分组的前40字节内容（十六进制）019b40008006lde8coa80008d34447500bd91388846b41c5000000005db000000000400031066e833d3444750cOa8000813880bd9e0599fef846b41c66701216d037e10000019c40008006ldefcOa80008d3444750bd91388846b41c6e0599ff0501043802编号123b320000b320000019d400080061ddecOa80008d34447500bd91388846b4lc6e0599ff0c65500003106067ad3444750cOa8000813880bd9e0599ff0846b41d6501016d057d20000请回答下列问题。45（1）题47-a表中的IP分组中，哪几个是由H发送的哪几个完成了TCP连接建立过程哪几个在通过快速以太网传输时进行了填充（2）根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是（3）若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所列，则该IP分组到达H时经过了多少个路由器题47-b表4006eCad1388a108e0599ff0846b41d6501016dOb7d60000总长度（16-31）总长度（16-31）标志片偏移头部校验和源端口（0-15）目的端口（16-31）确认号（ack）UAPRSFGKHTNN校验和选项（长度可变）服务类型协议标识生存时（TTL）紧急指针头部长度版本填充解1）由于题47-a表中1、3、4号分组的源IP地址（第13～16字节）均为l（coa80008H），所以1、3、4号分组是由H发送的。题47-a表中1号分组封装的TCP段的FLAG为02H（即SYN＝1，ACK＝0seq＝846b41c5H，2号分组封装的TCP段的FLAG为12H（即SY＝1，ACK＝1seq＝e0599fefH，ack＝846b41c6H，3号分组封装的TCP段的FLAG为10H（即ACK＝1seq＝846b41c6H，ack＝e0599ff0H，所以1、2、3号分组完成了由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、5号分组的总长度为40（28H）字节，小于46字节，其余分组总长度均大于46字节，所以3、5号分组在通过快速以太网传输时进行了填充。层数据的字节数为846b41d6H-846b41c6H＝10H＝16B。（3）由于S发出的IP分组的标识＝6811H，所以该分组所对应的是题47-a64-49＝15。所以，可以推断该IP分组到达H时经过了l5个路由器。2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题个选项中，只有一个选项是最符合题目要求的。x＝2：while（x<n/2）x＝2×x；A．O（logn）2B．O（n）C．O（nlogn）2D．O（n）22．元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的A．3B．4C．5D．6分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是。A．0，0B．0，n-1C．n-1，0D．n-1，n-1A．257B．258C．384D．3855．若一棵二叉树的前序遍历序列和后序遍历序列分别为l，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是。A．1，2，3，4B．2，3，4，1C．3，2，4，1D．4，3，2，16．已知一棵有2011个结点的树，其叶结点个数为ll6，该树对应的二叉树中无右孩子的结点个数是。A．115B．116C．1895D．18967．对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列A．95，22，91，24，94，71B．92，20，91，34，88，35C．21，89，77，29，36，38D．12，25，71，68，33，348．下列关于图的叙述中，正确的是。Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ.若有向图中存在拓扑序列，则该图不存在回路A．仅ⅡB．仅Ⅰ、ⅡC．仅ⅢD．仅Ⅰ、Ⅲ9．为提高散列（Hash）表的查找效率，可以采用的正确措施是。Ⅲ.处理冲突（碰撞）时避免产生聚集（堆积）现象A．仅ⅠB．仅ⅡC．仅Ⅰ、ⅡD．仅Ⅱ、Ⅲ10．为实现快速排序算法，待排序序列宜采用的存储方式是。A．顺序存储B．散列存储C．链式存储D．索引存储11．已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，A．1B．2C．4D．5A．MIPSB．CPIC．IPCD．MFLOPS型变量x分配在一个32位浮点寄存器FRl中，且x＝-8.25，则FR1的内容是 ()。A．C1040000HB．C2420000HC．C1840000HD．C1C20000H14．下列各类存储器中，不采用随机存取方式的是。A．EPROMB．CDR0MC．DRAMD．SRAM15．某计算机存储器按字节编址，主存地址空间大小为64MB，现用4M×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是 ()。A．22位B．23位C．25位D．26位16．偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是。A．间接寻址B．基址寻址C．相对寻址D．变址寻址17．某机器有一个标志寄存器，其中有进位／借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的A．CF+OF＝0B．SF+ZF＝0C．CF+ZF＝0D．CF+SF＝018．下列给出的指令系统特点中，有利于实现指令流水线的是。Ⅲ.只有Load／Store指令才能对操作数进行存B．仅Ⅱ、Ⅲ19．假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是。.A．每个指令周期中CPU都至少访问内存一次B．每个指令周期一定大于或等于一个CPU时钟周期C．空操作指令的指令周期中任何寄存器的内容都不会被改变D．当前程序在每条指令执行结束时都可能被外部中断打断20．在系统总线的数据线上，不可能传输的是。A．指令B．操作数C．握手（应答）信号D．中断类型号型号21．某计算机有五级中断L～L，中断屏蔽字为MMMMM，M＝1（0≤i≤4）表示对L级中断进行屏蔽。若中断响应优先级从高到低的顺序是iL→L→L→L→L，且要求中断处理优先级从高到低的顺序为A．11110B．01101C．00011D．0101022．某计算机处理器主频为50MHz，采用定时查询方式控制设备A的I／O，查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU用于设备A的I／O的时间占整个CPU时间的百分比至少是。A．0.02%B．0.05%C．0.20%D．0.50%23．下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是()。A．先来先服务B．高响应比优先C．时间片轮转D．非抢占式短任务优先24．下列选项中，在用户态执行的是。A．命令解释程序B．缺页处理程序C．进程调度程序D．时钟中断处理程序A．进程P的代码段B．进程P中打开的文件C．进程P的全局变量D．进程P中某线程的栈指针26．用户程序发出磁盘I／O请求后，系统的正确处理流程是。A．用户程序→系统调用处理程序→中断处理程序→设备驱动程序B．用户程序→系统调用处理程序→设备驱动程序→中断处理程序C．用户程序→设备驱动程序→系统调用处理程序→中断处理程序D．用户程序→设备驱动程序→中断处理程序→系统调用处理程序27．某时刻进程的资源使用情况如下表所示进程R1R2R3可用资源R1R2R3O112O33OOA．P1，P2，P3，P4B．P1，P3，P2，P4C．P1，P4，P3，P2D．不存在28．在缺页处理过程中，操作系统执行的操作可能是。A．仅Ⅰ、ⅡB．仅ⅡC．仅Ⅲ29．当系统发生抖动（thrashing）时，可以采取的有效措施是。A．仅ⅠB．仅ⅡC．仅ⅢD．仅Ⅰ、Ⅱ30．在虚拟存储管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是。A．编辑B．编译C．链接D．装载31．某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读人缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU析完该文件的时间分别是。A．1500μs、1000μsB．1550μs、1100μsC．1550μs、1550μsD．2000μs、2000ΜsA．可能为-1或3B．只能为1C．可能为0、1或2D．可能为-1、0、1或233．TCP／IP参考模型的网络层提供的是。A．无连接不可靠的数据报服务B．无连接可靠的数据报服务C．有连接不可靠的虚电路服务D．有连接可靠的虚电路服务34．若某通信链路的数据传输速率为2400bps，采用4相位调制，则该链路A．600波特B．1200波特C．4800波特D．9600波特35．数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0H3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的A．1B．2C．3D．436．下列选项中，对正确接收到的数据帧进行确认的MAC协议是。A．CSMAB．CDMAC．CSMA／CDD．CSMA／CA37．某网络拓扑如下图所示，路由器Rl只有到达子网l/24的路由。为使R1可以将IP分组正确地路由到图中所有子网，则在R1中需要增加一条路由（目的网络，子网掩码，下一跳）是。A．，28，B．，，C．，28，D．，，192.168,1,238．在子网l/30中，能接收目的地址为l的IP分组的最大主机数是。A．0B．1C．2D．439．主机甲向主机乙发送一个（SYN一1，seq一11220）的TCP段，期望与主机乙建立TCP连接，若主机乙接受该连接请求，则主机乙向主机甲发送的ASYN＝0，ACK＝0，seq＝11221，ack＝11221）BSYN＝1，ACK＝1，seq＝11220，ack＝11220）CSYN＝1，ACK＝1，seq＝11221，ack＝11221）DSYN＝0，ACK＝0，seq＝11220，ack＝11220）40．主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3甲的确认序号是。A．300B．500C．1200D．1400418分）已知有6个顶点（顶点编号为0--5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。（1）写出图G的邻接矩阵A。（2）画出有向带权图G。（3）求图G的关键路径，并计算该关键路径的长度。4215分）一个长度为L（L≥1）的升序序列S，处在第「L／2」个位置数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S22，4，6，8，20则Sl和S2的中位数是11。现有两个等长升序序列A和B，试设计一个时间和空间两方面都尽可能高效的算法，找出两个序列A和（1）给出算法的基本设计思想。（3）说明你所设计算法的时间复杂度和空间复杂度。4311分）假定在一个8位字长的计算机中运行下列C程序段：z2、k1和k2。请回答下列问题。（提示：带符号整数用补码表示）（1）执行上述程序段后，寄存器R1、R5和R6的