计算机专业（基础综合）模拟试卷2（共458题）

计算机专业（基础综合）模拟试卷2（共9套）（共458题）计算机专业（基础综合）模拟试卷第1套一、单选题(本题共40题，每题1.0分，共40分。)1、设n是描述问题规模的非负整数，下面程序片段的时间复杂度是()。voidfun(intn){inti，k；for(i=1；i<=n；i十十)for(j=1；j<=n；j十十){k=1：while(k<=n)k=5*k：}}A、O(n2log2n)B、O(nlog5n)C、O(n2log5n)D、O(n3)标准答案：C知识点解析：基本运算语句是k=5*k，设其执行时间为T(n)。对于j每循环一次，该语句的执行次数为m，有：5m≤n，即m≤log5n。所以：2、操作系统在运行中会采用调度策略选择新进程占用CPU完成其功能。下面的选项中，操作系统不会调度新进程的时机是()。A、当前运行进程的时间片用完B、当前运行进程出错后阻塞C、运行进程要等待某一个事件的发生D、新进程被创建进入就绪队列标准答案：D知识点解析：本题考查进程调度的时机。运行着的进程由于分配的时间到，或者运行结束，或者需要等待事件的发生(例如等待键盘响应)，或者出错，或者自我阻塞等均可以引起激活调度程序进行重新调度，选择一个新的就绪进程占有处理机运行。新的进程加入就绪队列不是引起调度的直接原因，当CPU正在处理其他进程的请求时，该进程仍然需要等待。即使在采用高优先级优先调度算法的系统中，一个最高优先级的进程进入就绪队列，仍旧需要考虑是否允许抢先，当不允许抢先时仍然需要等待。3、某二叉树的高度为50，树中只有度为O和度为2的结点，那么此二叉树中所包含的结点数最少为()。A、88B、90C、99D、100标准答案：C知识点解析：除根结点层只有1个结点外，其他各层均有两个结点，结点总数=2×(50-1)+l=99。4、MIPS(每秒百万次指令数)和MFL()PS(每秒百万次浮点运算数)是衡量CPU性能的两个指标，其中()。A、MIPS适合衡量向量处理机的性能，MFLOPS适合衡量标量处理机的性能B、MIPS适合衡量标量处理机的性能，MFLOPS适合衡量向量处理机的性能C、MIPS反映计算机系统的峰值性能，MFLOPS反映计算机系统的持续性能D、MIPS反映计算机系统的持续性能，MFLOPS反映计算机系统的峰值性能标准答案：B知识点解析：MIPS反映的是单位时间内执行定点指令的条数，MLOPS是基于所完成的浮点操作次数而不是指令数。同一个程序，不同计算机运行所需的指令数会不同，但所用到的浮点运算次数却是相同的。5、为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行()次关键字比较。A、10B、14C、20D、21标准答案：B知识点解析：首先需要知道折半查找成功的平均查找长度为log2(n+1)-1。为使查找效率最高，可对有65025个元素的有序顺序表分块，每块有=255个元素。为每一块建立一个索引项，索引表共255个索引项。若对索引表和每一块都采用折半查找，则查找效率最高，计算可得ASLIndexSeqSearch=ASLIndex+ASLBlock=log2(255+1)一1+log2(255+1)一1=14下面补充一些关于折半查找的概念。补充(1)：折半查找的时间复杂度为O(log2n)。补充(2)：折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。补充(3)：对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为h=[log2(n+1)]或者h=[log2(n+1)]+16、下列关于进程状态叙述正确的是()。Ⅰ．—次I/O操作的结束，有可能导致一个进程由就绪变为运行Ⅱ．一个运行的进程用完了分配给它的时间片后，它的状态变为阻塞Ⅲ．当系统中就绪进程队列非空时，也可能没有运行进程Ⅳ．某个进程由多个内核线程组成，其中的一个线程被调度进入运行，有的继续留在就绪队列，有的被阻塞，则此时进程的状态是运行状态A、Ⅰ、ⅡB、ⅢC、ⅣD、全错标准答案：C知识点解析：Ⅰ错误，一次I/O操作结束后，该I/O资源有可能被请求该资源的资源占有，从而使其从阻塞状态转变为就绪状态。等待I/O资源的进程状态是阻塞状态，且进程获得CPU运行是通过调度得到的，而不是获得资源，该叙述错的很明显。Ⅱ错误，运行进程用完时间片后，是由运行态变为就绪状态。Ⅲ错误，就绪进程队列非空时，处理机不应空闲，所以一定有运行进程。Ⅳ正确，在多线程操作系统中，把线程作为独立运行的基本单位，所以此时的进程已不再是一个可执行的实体。虽然如此，进程仍具有与执行相关的状态。例如，所谓进程处于“执行”状态，实际上是指该进程中的某个线程正在执行。只有当所有线程都阻塞了，该进程才会被认为是阻塞，只要有一个进程是运行态，该进程就是运行态；若没有线程运行，只要有一个线程就绪，则该进程就是就绪态。综上所述，本题选C。7、以下IP地址中，路由器不进行转发的有()。Ⅰ．10．1．32．7Ⅱ．192．168，32．2Ⅲ．172．30．1．3Ⅳ．172．35．32．244A、仅Ⅰ、Ⅱ、ⅢB、仅Ⅱ、ⅢC、仅Ⅰ、Ⅲ、ⅣD、仅Ⅳ标准答案：A知识点解析：路由器对于专用网地址（私有地址）是不进行转发的。私有地址总结如下：A类～55（记住10开头即可）B类172.16，0.0～55（这个死记）C类～55（记住192.168开头即可）8、下面关于交换机的说法中，正确的是()。A、以太网交换机可以连接运行不同网络层协议的网络B、从工作原理上讲，以太网交换机是一种多端口网桥C、集线器是一种特殊的交换机D、通过交换机连接的一组工作站形成一个冲突域标准答案：B知识点解析：本题考查交换机和集线器的区别。选项A，交换机是数据链路层设备，对于网络层来说是透明的，表述有问题。选项C，集线器是物理层设备，和交换机不在同一个层次。选项D，交换机的优势就是每个端口是一个冲突域，整个交换机是一个广播域，因此答案是B。9、一个C类地址，采用了255．255．255．240作为子网掩码，那么这个C类地址可以划分为()个子网。A、16B、32C、64D、128标准答案：A知识点解析：先将子网掩码转换成二进制得到11111111．11111111．111l1111．1111000。C类的主机号是8位的，现在用高4位来表示子网，因此可以得到16个子网。10、一个C类网络的子网掩码为255．255．252．252，则该C类网络的主机数目是()。A、2046B、1022C、510D、128标准答案：D知识点解析：本题考查IPv4子网划分，首先明确C类网络的掩码是255．255．0．255，而252的二进制是11111100，由此可知可划分26=64个子网，每个子网的主机数为22-2=2，因此该C类网络的主机数目是64×2=128，因此答案是D。11、文件系统中若文件的物理结构采用连续结构，则文件控制块FCB中有关文件的物理位置的信息包括()。Ⅰ．首块地址Ⅱ．文件长度Ⅲ．索引表地址A、只有ⅢB、Ⅰ和ⅡC、Ⅱ和ⅢD、Ⅰ和Ⅲ标准答案：C知识点解析：连续结构不需要用到索引表，那么文件控制块中也就不可能有索引表地址信息，因此排除A、C、D选项，选B。12、在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲帧时，系统正确的处理顺序为()。A、决定淘汰页→页面调出→缺页中断→页面调入B、决定淘汰页→页面调入→缺页中断→页面调出C、缺页中断→决定淘汰页→页面调出→页面调入D、缺页中断→决定淘汰页→页面调入→页面调出标准答案：C知识点解析：根据缺页中断的处理流程，产生缺页中断后，首先去内存寻找空闲物理块，若内存没有空闲物理块，则使用相应的页面置换算法决定淘汰页面，然后调出该淘汰页面；最后在调入该进程需要访问的页面，所以整个流程可以归结为：缺页中断→决定淘汰页→页面调出→页面调入。13、一个IPv6包中“通信量类”字段的值为0，表明()。A、该包优先级最低，拥塞时可以被丢弃B、该包优先级最高，拥塞时不能被丢弃C、该包中没有用户数据，只有首部D、该包不可进行路由器转发标准答案：A知识点解析：IPv6首部总结，如图4-12所示。版本(version)——4bit，它指明了协议的版本，对于IPv6，该字段总是6。通信量类(trafficclass)——8bit，这是为了区分不同的IPv6数据报的类别或优先级。已经定义了0～15共16个优先级，0的优先级最低。0～7表示允许延迟，8～15表示高优先级，需要固定速率传输。流标号(flowlabel)——20bit，“流”是互联网上从特定源点到特定终点的一系列数据报，“流”所经过的路径上的路由器都保证指明的服务质量。所有属于同一个流的数据报都具有同样的流标号。有效载荷长度(payloadlength)——16bit，它指明IPv6数据报除基本首部以外的字节数(所有扩展首部都算在有效载荷之内)，其最大值是64KB。下一个首部(nextheader)——8bit，它相当于IPv4的协议字段或可选字段。跳数限制(hoplimit)——8bit，源站在数据报发出时即设定跳数限制。路由器在转发数据报时将跳数限制字段中的值减1。当跳数限制的值为零时，就要将此数据报丢弃。源地址——128bit，数据报的发送站的IP地址。目的地址——128bit，数据报的接收站的IP地址。14、微程序存放在CPU的哪个部件中()。A、主存储器B、存储器控制器C、控制存储器D、辅助存储器标准答案：C知识点解析：微程序存放在控制存储器中，选C。注意区别存控与控存的区别，控存用来存放微程序，而存控是用来管理协调CPU、DMA控制器等对主存储器访问的部件。15、用户程序在用户态下使用陷入指令而引起的中断是()。A、故障中断B、外部中断C、不可屏蔽中断D、访管中断标准答案：D知识点解析：本题考查用户态和内核态及其转换的概念。在操作系统管理下的计算机中，为保护系统的安全，对一部分处理机的指令限定使用对象，即只有操作系统才可以执行。而当用户需要使用这些特权指令时，必须调用特定的访管指令，也称陷入指令，顾名思义由用户态陷入到内核态，从而从用户态转入内核态，继而可以执行特权指令；访管指令引起的中断称为访管中断，它是用户使用特权指令的唯一人口。16、下列所示关系中，不是信号量能实现的功能是()。A、进程同步B、进程互斥C、执行的前趋关系D、进程的并发执行标准答案：D知识点解析：本题考查信号量的功能，在多道程序技术系统中，信号量机制是一种有效的实现进程同步与互斥的工具。信号量可以实现的功能有：进程的同步与互斥，进程执行的前趋关系，进程执行的前趋关系实质上是指进程的同步关系。除此以外，只有进程的并发执行不需要信号量来控制，因此正确答案为D。17、计算机系统中，不属于DMA控制器的是()。A、命令／状态寄存器B、内存地址寄存器C、数据寄存器D、堆栈指针寄存器标准答案：D知识点解析：本题考查IO设备中DMA设备的组成。DMA设备与CPU有三类信号线：数据线、地址线和控制线。一般要DMA设备工作，必须有命令／状态寄存器，这个寄存器控制DMA的工作模式并反映给CPU它当前的状态，地址寄存器存放DMA作业时的源地址和目标地址，数据寄存器存放要DMA转移的数据，只有堆栈指针寄存器不需要在DMA控制器中存放。堆栈一般在计算机内存中开辟有统一的区域。18、假定有两个带符号整数x、y用8位补码表示，x=63，y=—31，则x—y的机器数及其相应的溢出标志OF分别是()。A、SDH．0B、SEH、0C、SDH．1D、SEH、1标准答案：B知识点解析：因为x=63，y=—31，则x—y=94，而带符号的8位整数补码所能表示的范围是—128～127，所以94在其范围之内，没有溢出，即OF标志为0，将结果转化为机器数为SEH。此种题型在2009年，2014年的统考卷当中已经出现，现在对于这种在选择题当中出现补码加减运算或者是涉及浮点数加减计算的情况，总结如下：(1)涉及浮点数计算或者是复杂的补码的计算，不要立刻去按照补码的规则和浮点数加减规则去运算，不要关注题干给你的一些无用信息（比如浮点数的各运算步骤之类的）。(2)观察题干给你的两个数，可以试着加加看，或者减减看，看结果到底为多少，然后看这个结果是否在寄存器所能表示的数（一般是补码）的范围之内。如果不能表示，那一定是溢出了，如果能表示，再把这个结果化为二进制或者十六进制。19、下列关于并行微程序控制器的说法正确的是()。A、现行微指令的执行与取下一条微指令的操作并行B、现行微指令的执行与取下一条微指令的操作串行C、两条或更多微指令的执行在时间上并行D、两条或更多微指令的取微指令操作在时间上并行标准答案：A知识点解析：并行微程序控制器中，在执行现行微指令的同时，取下一条微指令，A选项的描述正确。20、在一个采用虚拟存储管理的系统中，计算机的数据位和地址位宽均为32位，假设当前系统中存在10个进程，主存的容量是2GB，辅存的容量为500GB，在这样的系统中，所有进程虚存的总空间大小是()。A、4GBB、40GBC、2GBD、502GB标准答案：B知识点解析：本题考查虚拟存储器的最大空间的问题。虚拟存储器空间的最大值与实际存储容量没有关系，仅与其地址系统的位宽有关，32位的系统其最大虚存每个进程都是4GB。若系统中存在10个进程，则总虚拟存储空间是所有进程虚拟存储空间之和。本题中为40GB。但是若要问，虚存的实际容量是多少时，则要考虑主存和辅存的大小，若主存和辅存之和小于最大虚拟存储空间40GB，则应是主存和虚存的实际容量之和。若大于40GB，则多余的部分是没有用的(仅指虚拟存储的外存，因为硬盘的主要作用是存储文件，仅用一部分来作为虚存的外存)。21、如果I／O设备和存储设备之间的数据交换不经过CPU来完成，则这种交换方式是()。A、程序查询方式B、中断方式C、DMA方式D、外部总线方式标准答案：C知识点解析：暂无解析22、下列文件物理结构中，适合随机访问且易于文件扩展的是()。A、连续结构B、索引结构C、链式结构且磁盘块定长D、链式结构且磁盘块变长标准答案：B知识点解析：索引结构适合随机访问且易于文件扩展。23、某公司获得了一个IP地址段，在不分子网的情况下，最多可以容纳65534个主机，那么这个地址属于()。A、A类地址B、B类地址C、C类地D、D类地址标准答案：B知识点解析：B类地址的主机号的长度是16位，再去点全“0”和全“1"两个地址，还可以分配65534个主机。24、下列关于TCP和UDP的说法正确的是()。A、两者都是面向无连接的B、两者都是面向连接的C、TCP是面向连接而UDP是面向无连接的D、TCP无连接而UDP是面向连接的标准答案：C知识点解析：TCP／IP参考模型的传输层上有两个主要的协议，用户数据报协议UDP(无连接)和传输控制协议TCP(面向连接)，主要区别如下：(1)TOP是基于连接的，UDP是基于无连接，这是本质的区别，其他区别都是为之服务的。(2)对系统资源的要求：TCP较多，UDP少。(3)UDP数据包结构较简单，而TCP为了保证流量控制和拥塞控制，数据包结构较为复杂。(4)TCP采用流模式，并进行编号，但UDP采用数据报模式(5)TCP保证数据正确性，UDP可能丢包；TOP保证数据顺序，UDP不保证。本题考查TCP和UDP的传输特性，TCP可靠有连接，UDP不可靠无连接，因此答案是C。25、现在可以使用()来编写Web页面。A、HTTPB、HTMLC、MIMED、XML标准答案：B知识点解析：HTML(超文本标记语言)是用来描述格式化文档的语言，用来编写Web页面。26、下面关于图的存储结构的叙述中正确的是()。A、用邻接矩阵存储图占用空间大小只与图中顶点有关，与边数无关B、用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点无关C、用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关D、用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关标准答案：A知识点解析：暂无解析27、利用栈求表达式的值时，设立运算数栈S。假设栈S只有两个存储单元，在下列表达式中，不发生溢出的是()。A、A—B*(C—D)B、(A—B)*C—DC、(A—B*C)—DD、(A—B)*(C—D)标准答案：B知识点解析：利用栈求表达式的值时，需要设立运算符栈和运算数栈，下面仅举一例。例如，求2×(5—3)+6/2的过程如表6—2所示。从上述的计算过程中，考生可以自行对A、B、C、D选项进行练习，运算数栈S的大小分别至少为4、2、3、3，只有B选项满足条件。28、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数是()。A、5B、6C、7D、8标准答案：D知识点解析：由二叉树性质的推广，度为4的树应该有1+n2+2n3+3n4个叶结点(ni表示度为i的结点数目)，与度为1的结点的个数无关。因此，如果用n0表示叶结点的个数，则应该有n0=1+2+2×1+3×1=8。29、在读写硬盘的一个物理记录块时，不需要的参数是()。A、柱面(磁道)号B、盘片(磁头)C、簇号D、扇区号标准答案：C知识点解析：在读写硬盘的一个物理记录块时，需要的参数是磁道号、磁头号和扇区号。30、通道方式的工作过程中，下列步骤的正确顺序是()。①组织I／O操作②向CPU发出中断请求③编制通道程序④启动I／O通道A、①→②→③→④B、②→③→①→④C、④→③→②→①D、③→④→①→②标准答案：D知识点解析：考查通道的工作过程。通道的基本工作过程(以一次数据传送为例)如下：①在用户程序中使用访管指令进入操作系统管理程序，由CPIU通过管理程序组织一个通道程序，并使用I／O指令启动通道(此后CPU并行运行应用程序)。②通道处理器执行CPU为其组织的通道程序，完成指定的数据的输入／输出工作。③通道程序结束后，向CPU发出中断请求。CPU响应此中断请求后，第二次进入操作系统，调用管理程序对输入／输出中断进行处理。31、假设有一个信道的带宽是3000Hz，其信噪比为20dB，那么这个信道可以获得的理论最大传输速率是()。A、1KbpsB、32KbpsC、20KbpsD、64Kbps标准答案：C知识点解析：SNR=10log10(S／N)，题目中SNR=20dB，因此S／N=100。再使用香农定理可以得到信道的理论速率上限C=Wlog2(1+S／N)=3000×log2(1+100)≈20(Kbps)。32、假定主存按字节编址，Cache共有64行，采用4路组相联映射方式，主存块大小为32字节，所有编号都从0开始，则主存第3000号单元所在主存块对应的Cache组号是()。A、1B、5C、13D、29标准答案：C知识点解析：因为主存按字节编址，每块32B，故第3000号单元(从0开始编制)所在的块号为3000／32=93；又因为Cache采用四路组相连，一共64行(可看成64块)，一共有64／4=16组，于是按照主存块号对应Cache组号，映射后第93块在Cache中的组号为93％16=13。答案选C。33、分时系统中，为使多个用户能够同时与系统交互，最关键的问题是()。A、计算机具有足够的运行速度B、内存容量应足够大C、系统能及时地接收多个用户输入D、能在一短的时间内，使所有用户程序都能运行标准答案：D知识点解析：本题考查分时系统的特点。34、关于FTP主要应用功能的叙述正确的是()。A、FTP使用户和远程主机相连，从而对主机内的各种资源进行各种操作，如文件的读、写、执行、修改等B、FTP的功能类似于TelnetC、FTP的主要功能在于文件传输，但FTP客户端在一定的范围内也有执行修改等其他文件的功能D、FTP使用户同远程主机相连，类似于远程主机的仿真终端用户，从而应用远程主机的资源标准答案：C知识点解析：FTP(文件传输协议)，主要功能有：(1)把本地计算机上的一个或多个文件传送到远程计算机，或从远程计算机上获取一个或多个文件。(2)提供对本地计算机和远程计算机的目录操作功能。(3)客户端在一定的范围内对文件进行改名、删除、显示文件内容等。35、在微程序控制中，机器指令和微指令的关系是()。A、每一条机器指令由一条微指令解释执行B、每一条机器指令由一段微程序解释执行C、每一条微指令由一条机器指令解释执行D、每一段微程序由若干条机器指令解释执行标准答案：B知识点解析：在微程序控制中一条机器指令对应一个微程序，每一个微程序包含若干条微指令，每一条微指令对应一个或几个微操作命令。当计算机运行时，逐条执行微程序中的每一条微命令，就相应的完成了一条机器指令的全部操作。36、下而元件存取速度最快的是()。A、CacheB、寄存器C、外存D、内存标准答案：B知识点解析：速度快慢排序如下：寄存器>Cache>内存>外存。37、将N个关键字映射到一个Hash表中，用链地址法解决冲突。在这个Hash表中查找一个关键字所需的操作为()。A、Hash映射N次，链结点比较最多1次B、Hash映射1次，链结点比较最多N次C、Hash映射N／2次，链结点比较最多N／2次D、Hash映射N-1次，链结点比较最多1次标准答案：B知识点解析：查找一个关键字只需一次Hash映射就可找到关键字所在的链表，紧接着在该链表中从头到尾依次查找每个元素是否是所要查找的关键字，此时最多需N次链表结点的比较。38、在IP数据报报头中有两个有关长度的字段，一个为报头长度(IHL)字段，一个为总长度(totallength)字段，下面说法正确的是()。A、报头长度字段和总长度字段都以8比特为计数单位B、报头长度字段以8比特为计数单位，总长度字段以32比特为计数单位C、报头长度字段以32比特为计数单位，总长度字段以8比特为计数单位D、报头长度字段和总长度字段都以32比特为计数单位标准答案：C知识点解析：IHL实段以4字节为单位，totallength字段以字节为单位。39、支持多道程序的操作系统，区别于其他操作系统的主要特征为()。A、多用户、进程的独立性、进程之间的同步与通信B、进程的独立性、进程之间的同步与通信、动态存储分配C、进程的独立性、动态存储分配、虚存D、多内核结构、进程的独立性、动态存储分配标准答案：B知识点解析：A是多用户操作系统区别于其他操作系统的特点。40、三哲学家进餐问题的伪代码如下，f1，f2，f3是三根筷子，则()。A、可能死锁，p1或p2或p3都有可能饥饿B、不可能死锁．但p1或p2或p3都有可能饥饿C、不可能死锁，但只有p1或p2有可能饥饿D、不可能死锁。但只有p2或p3有可能饥饿标准答案：B知识点解析：p1、p2和p3不满足死锁的四个必要条件中的循环等待条件，故不可能发生死锁。排除A。设p3先申请到f3，若此时p2先于p1申请到f1，则此时p2好和p3任意一个申请到f2都可执行完毕，假设是p2申请到了f2执行完毕，释放f2，f1，则p3可获得f2执行完毕，倘若p2紧接着又申请到了f1，p3执行完后紧接着又申请到了f3；如此循环则p1始终没有机会获得处理机执行而发生饥饿现象。以此类推p2和p3都有可能发生饥饿现象。故选B。二、综合应用题(本题共9题，每题1.0分，共9分。)下图所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R／W信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路。另外，线上标注有小圈表示有控制信号，例中yi表示y寄存器的输入控制信号，R1o为寄存器R1的输出控制信号，未标字符的线为直通线，不受控制。41、“ADDR2，R0”指令完成(R0)+(R2)→R0的功能操作，画出其指令周期流程图，假设该指令的地址已放入PC中。并列出相应的微操作控制信号序列。标准答案：知识点解析：暂无解析42、若将“取指周期”缩短为一个CPU周期，请先画出修改数据通路，后画出指令周期流程图。标准答案：[*]知识点解析：暂无解析43、在(2)的基础上，将“执行周期”也缩短为一个CPu周期，先修改运算器数据通路，后画出指令周期流程图。此时加法指令速度比(1)提高几倍?标准答案：[*]知识点解析：暂无解析完成以下各小题。44、什么是Belady现象?为什么会产生这种现象?标准答案：如果某种换页算法，在增加页框数之后反而可能导致更多缺页，这种反常情形称为Belady现象。知识点解析：暂无解析45、页面置换算法FIFO为什么会出现Belady现象?简述理由。标准答案：FIFO换页策略将最早换人页框的页面换出，而不考虑该页面是否最近使用过，这违背了局部性原理。当页框数较大时，由于包含的页面更多，历史记录更全面，就有可能使最近频繁使用但较早进入页框的页面被换出，从而出现Belady异常。知识点解析：暂无解析46、页面置换算法LRU为什么不会出现Belady现象?简述理由。标准答案：LRU换页策略将最近最长时间未使用的页面换出，符合局部性原理。当页框数较大时，最近最长未使用的情况更全面，因此缺页数不会增加。知识点解析：暂无解析假定A和B是试图在一个以太网上发送的两个站。每个站都有一个稳定的帧的队列准备发送，A的帧编号是A1，A2和A3等，B的帧编号是B1，B2和B3等。再假定指数后退的基本单元时间是T=51．2微秒。现在A和B同时尝试发送1号帧，碰撞，并且刚好分别选择了0×T和1×T的退避时间，也就是说，A赢得了这一次竞争，发送A1，B需要等待。在这次传送结束时，B尝试再发送B1．而A则尝试发送A2。这一轮的首次尝试产生碰撞，此时，A的退避时间从0×T和1×T中选择，而B则从0×T，…，3×T中选择。47、给出A赢得第2次退避竞争的概率。标准答案：A可以选择KA=0或1；B可以选择KB=0，1，2，3。如果(KA，KB)选择(0，1)，(0，2)，(0，3)，(1，2)，(1，3)中的一个组合，那么将是A赢得这第2次竞争，其概率是5／8。知识点解析：暂无解析48、假定A已赢得了第2次退避竞争。A在成功发送A2后，接着尝试发送A3。当B再次尝试发送B1时，A和B再次碰撞。给出A赢得这第3次退避竞争的概率。标准答案：现在A是在一次成功发送之后，可以选择KA=0或1；KB是在它的第3次碰撞之后，可能的选择是0，1，2，…，7。如果KA=0，那么KB中有7种选择使得A赢；如果KA=1，那么KB中有6种选择使得A赢。所以A赢得这第3次竞争的概率是13／16。知识点解析：暂无解析49、给出A赢得所有其余后退竞争的概率的合理下限值。标准答案：A赢得第2次竞争的概率=5／8>1／2A赢得第3次竞争的概率=13／16>3／4类似地，A赢得第4次竞争的概率>7／8一般地，A赢得第i次竞争的概率>(1—1／2i一1)因此，假定A已经赢得第1至第3次竞争，那么A赢得所有其余的后退竞争的概率将不低于：(1—1／8)×(1一1／16)×(1一1／32)×(1一1／64)×…≈1—1／8—1／16—1／32—1／64一…=6／8=3／4知识点解析：暂无解析计算机专业（基础综合）模拟试卷第2套一、单选题(本题共40题，每题1.0分，共40分。)1、设有一个递归算法如下：intX(intn)；if(n＜=3)return1；elsereturnX(n一2)+X(n一4)+1；试问计算X(X(5))时需要调用()次X函数。A、2B、3C、4D、5标准答案：C知识点解析：该递归算法的定义为：即当参数值小于等于3的时候，整个流程调用X(n)一次，而当参数值大于3的时候，整个流程调用X(n)至少3次(第一次即本次调用，第二次为X(n—2)，第三次为X(n—4))。X(X(5))递归调用的执行结果如下：一个方块代表一次调用，一共调用了4次。2、设有一个10阶对称矩阵A，采用压缩存储方式，以行序为主存储，a1，1为第一个元素，其,存储地址为1，每个元素占一个地址空间，则a8,5的地址可能是()。A、13B、33C、18D、40标准答案：B知识点解析：考查特殊矩阵的存储。对称矩阵可以存储其下三角，也可以存储其上三角。数组下标从1开始，当存储下三角元素时，在a8,5的前面有7行，第1行有1个元素，第2行有2个元素，…，第7行有7个元素，这7行共有(1+7)×7／2=28个元素，在第8行中，a8,5的前面有4个元素，所以，a8,5前面有28+4=32个元素，其地址为33。当存储上三角元素时，a8,5对应于a5,8，地址为38，无此选项，故只可能选B。3、若一棵深度为6的完全二叉树的第6层有3个叶子结点，则该二叉树共有()个叶子结点。A、17B、18C、19D、20标准答案：A知识点解析：考查完全二叉树性质。完全二叉树第5层共有24=16个结点。第6层最左边有3个叶子结点，对应第5层最左边2个结点，所以第5层右边有16—2=14个叶子结点，因此共有17个叶子结点。4、在一棵非空二叉树的中序遍历序列中，根结点的右边()。A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点标准答案：A知识点解析：考查中序遍历。根据中序遍历的定义可知，在输出根结点后，才去中序递归地遍历根结点的右子树，因此根结点右边只有右子树上的所有结点。5、如右图所示为一棵平衡二叉树(字母不是关键字)，在结点D的右子树上插入结点F后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树中平衡因子的绝对值为1的分支结点数为()。A、0B、1C、2D、3标准答案：B知识点解析：考查平衡二叉树的旋转。由于在结点A的右孩子(R)的右子树(R)上插入新结点F，A的平衡因子由一1减至一2，导致以A为根的子树失去平衡，需要进行RR旋转(左单旋)。RR旋转的过程如上图所示，将A的右孩子C向左上旋转代替A成为根结点，将A结点向左下旋转成为C的左子树的根结点，而C的原来的左子树E则作为A的右子树。故，调整后的平衡二叉树中平衡因子的绝对值为1的分支结点数为1。注意：平衡旋转的操作都是在插入操作后，引起不平衡的最小不平衡子树上进行的，只要将这个最小不平衡子树调整平衡，则其上级结点也将恢复平衡。6、下列说法中，正确的是()。A、对于有n个结点的二叉树，其高度为[log2n]B、完全二叉树中，若一个结点没有左孩子，则它必是叶结点C、高度为h(h＞0)的完全二叉树对应的森林所含的树的个数一定是hD、一棵树中的叶子数一定等于其对应的二叉树的叶子数标准答案：B知识点解析：若结点数为n的二叉树是一棵单支树，其高度为n，只有完全二叉树才具有A性质。完全二叉树中最多只存在一个度为1的结点且该结点只有左孩子，若不存在左孩子，则一定也不存在右孩子，因此必是叶结点，B正确。只有满二叉树才具有C性质，如下图所示：在树转换为二叉树时，若有几个叶子结点有共同的双亲结点，则转换为二叉树后只有一个叶子(最右边的叶子)，如下图所示，D错误。7、以下关于图的叙述中，正确的是()。A、强连通有向图的任何顶点到其他所有顶点都有弧B、图与树的区别在于图的边数大于或等于顶点数C、无向图的连通分量指无向图中的极大连通子图D、假设有图G={V，{E}}，顶点集，则V’和{E’}构成G的子图标准答案：C知识点解析：考查图的基本性质。强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A错误。图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。若E’中的边对应的顶点不是V’中的元素时，则V’和{E’}无法构成图，D错误。8、如右图所示，在下面的5个序列中，符合深度优先遍历的序列有多少个()。1．aebfdc2．acfdeb3．aedfcb4．aefdbc5．aecfdbA、5B、4C、3D、2标准答案：D知识点解析：考查图的深度优先遍历。仅1和4正确。以2为例，遍历到c之后，与c邻接且未被访问的结点为空集，所以a的邻接点b或e入栈，显然2不符合这种情况。以3为例，因为遍历要按栈退回，所以是先b后c，而不是先c后b。9、一组数据(30,20,10,15,35,1,10,5)，用堆排序(小顶堆)的筛选方法建立的初始堆为()。A、1,5,15,20,35,10,30,10B、1,10,30,10,5,15,35,20C、1,5,10,15,35,30,10,20D、A、B和C均不正确标准答案：C知识点解析：考查初始堆的建立。首先对以第「n／2」个结点为根的子树(也即最后一个结点的父结点为根的子树)筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，直到筛选到根结点。从「n／2」～1依次筛选堆的过程如下图所示：10、串’acaba’的next数组值为()。A、01234B、01212C、01121D、01230标准答案：C知识点解析：考查串的next数组。(1)设next[1]=0，next[2]=1。(2)当j=3，此时k=next[j—1]=—next[2]=1，观察S[2]与S[k](S[1])是否相等，S[2]=c，S[1]=a，S[2]=S[1]，此时k=next[k]=0，所以next[j]=1。(3)当j=4，此时k=next[j—1]=next[3]=1，观察S[3]与S[k](S[1])是否相等，S[3]=a，S[1]=a，S[2]=S[1]，所以next[j]=k+1=2。(4)当j=5，此时k=next[j—1]=next[4]=2，观察S[4]与S[k](S[2])是否相等，S[4]=b，S[2]=c，S[4]!=S[2]，所以k=next[k]=1。(5)此时S[k]=S[1]=a，S[4]!=S[1]，所以k=next[k]=next[1]=0，所以next[j]=1。此时可知next数组为01121，选C。11、一组经过第一趟2．路归并排序后的记录的关键字为(25,50,15,35,80,85,20,40,36,70)，其中包含5个长度为2的有序表，用2．路归并排序方法对该序列进行第二趟归并后的结果为()。A、15,25,35,50,80,20,85,40,70,36B、15,25,35,50,20,40,80,85,36,70C、15,25,50,35,80,85,20,36,40,70D、15,25,35,50,80,20,36,40,70,85标准答案：B知识点解析：考查归并排序的执行过程。第一趟归并时，将每个关键字看成一个有序表，两两进行归并；第二趟归并时，将第一趟结果的5个长度为2的有序表归并，得到2个长度为4的有序表和1个长度为2的有序表。由于这里是采用2．路归并，而且是第二趟排序，所以每4个元素放在一起归并，可将序列划分为{25,50,15,35}，{80,85,20,40}和{36,70}，分别对它们进行排序为{15,25,35,50}，{20,40,80,85}和{36,70}。注意：区分递归和非递归的归并排序。12、已知一台时钟频率为2GHz的计算机的CPI为1．2。某程序P在该计算机上的指令条数为4×109条。若在该计算机上，程序P从开始启动到执行结束所经历的时间是4s，则运行P所用CPU时间占整个CPU时间的百分比大约是()o，A、40％B、60％C、80％D、100％标准答案：B知识点解析：本题考查根据时钟频率、指令条数和CPI来计算程序执行时间。程序的执行时间=(指令条数×CPI)／主频=1．2×4×109／2GHz=2．4s，所占百分比为(2．4／4)×100％=60％。13、在补码表示的机器中，若寄存器R中原来存的数为9EH，执行一条指令后现存的数为CFH，则表明该指令不可能是()。A、XOR异或运算指令B、IMUL有符号数乘法指令C、SAR算术右移指令D、ADD加法指令标准答案：B知识点解析：本题考查进制数的转换以及各种运算操作。将寄存器R的前、后内容转为二进制：10011110和11001111。XOR指令，和0101000l异或即可，A正确；SAR指令，算术右移一位可以得到结果，C正确；ADD指令，加上31H即可，D正确。有符号乘法指令则找不到可以相乘的整数，B错误。14、下列关于浮点数的说法中，正确的是()。Ⅰ．最简单的浮点数舍入处理方法是恒置“1”法Ⅱ．IEEE754标准的浮点数进行乘法运算的结果肯定不需要做“左规”处理Ⅲ．浮点数加减运算的步骤中，对阶的处理原则是小阶向大阶对齐Ⅳ．当补码表示的尾数的最高位与尾数的符号位(数符)相同时表示规格化Ⅴ．在浮点运算过程中如果尾数发生溢出，则应进入相应的中断处理A、Ⅱ、Ⅲ和ⅤB、Ⅱ和ⅢC、Ⅰ、Ⅱ和ⅢD、Ⅱ、Ⅲ、Ⅳ和Ⅴ标准答案：B知识点解析：本题考查浮点数的运算。最简单的舍入处理方法是直接截断，不进行任何其他处理(截断法)，Ⅰ错误。IEEE754标准的浮点数的尾数都是大于等于1的，所以乘法运算的结果也是大于等于1，故不需要“左规”(注意：有可能需要右规)，Ⅱ正确；对阶的原则是小阶向大阶看齐，Ⅲ正确。当补码表示的尾数的最高位与尾数的符号位(数符)相异时表示规格化，Ⅳ错误。浮点运算过程中，尾数出现溢出并不表示真正的溢出，只有将此数右归后，再根据阶码判断是否溢出，Ⅴ错误。注意：浮点数运算的过程分为对阶、尾数求和、规格化、舍入和溢出判断，每个过程的细节均需掌握，本题的5个选项涉及到了这5个过程。15、下列的说法中，正确的是()。Ⅰ．双端口存储器可以同时访问同一区间、同一单元Ⅱ．双端口存储器当两个端口的地址码相同时，必然会发生冲突Ⅲ．高位多体交叉存储器的设计依据了程序的局部性原理Ⅳ．高位四体交叉存储器可能在一个存储周期内连续访问四个模块A、Ⅰ和ⅢB、Ⅱ和ⅢC、Ⅰ和ⅣD、只有Ⅰ标准答案：C知识点解析：本题考查双端口存储器和交叉存储器的特点。双端口RAM的两个端口具有2组相互独立的地址线、数据线和读写控制线，因此可以同时访问同一区间、同一单元，Ⅰ正确，但是其中任一个端口都不可有写操作；当两个端口同时对相同的单元进行读操作时，则不会发生冲突，Ⅱ错误。高位多体交叉存储器由于在单个存储器中字是连续存放的，所以不能保证程序的局部性原理；而低位多体交叉存储器由于是交叉存放，所以能很好地满足程序的局部性原理，ⅡI错误。高位四体交叉存储器虽然不能满足程序的连续读取，但仍可能一次连续读出彼此地址相差一个存储体容量的4个字，只是这么读的概率较小，Ⅳ正确。注意：高位多体交叉存储器仍然是顺序存储器。16、下列说法中，错误的是()。Ⅰ．虚拟存储器技术提高了计算机的速度Ⅱ．存取时间是指连续两次读操作所需的最小时间间隔Ⅲ．Cache与主存统一编址，Cache的地址空间是主存地址空间的一部分Ⅳ．主存都是由易失性的随机读写存储器构成的A、Ⅱ和ⅢB、Ⅲ和ⅣC、Ⅰ、Ⅱ和ⅣD、Ⅰ、Ⅱ、Ⅲ和Ⅳ标准答案：D知识点解析：考查存储器的多个知识点。实际上，虚存是为了解决多道程序并行条件下的内存不足而限制了程序最多运行的道数而提出的，即为了解决内存不足，虚拟存储器进行虚实地址转换，需要多次访存(先查找页表)，增加了延迟，降低了计算机速度，是一种时间换空间的做法，Ⅰ错误。Ⅱ描述的是存取周期的概念，Ⅱ错误。Cache有自己独立的地址空间，通过不同的映射方式映射到主存的地址空间，Ⅲ错误。主存也可以由ROM组成，如可用于部分操作系统的固化固话、自举程序等，Ⅳ错误。注：虚存和Cache都是计算机存储体系中重要的部分，它们的区别和联系一定要弄清楚，虚存是为了解决内存不足提出的，即是容量问题，使用一部分的辅存来对内存进行一定的扩充，但是这样会导致整体速度的下降，是用时间换空间的做法；而Cache则是为了缓和CPU与主存的矛盾而设立的，会提高整个存储体系的速度，是一种用金钱换时间的做法。17、虚拟存储器中的页表有快表和慢表之分，下面关于页表的叙述中正确的是()。A、快表与慢表都存储在主存中，但快表比慢表容量小B、快表采用了优化的搜索算法，因此查找速度快C、快表比慢表的命中率高，因此快表可以得到更多的搜索结果D、快表采用高速存储器件组成，按照查找内容访问，因此比慢表查找速度快标准答案：D知识点解析：本题考查快表和慢表的关系。快表又称TLB，采用高速相联存储器来存储可能需要使用的页的对应表项。而慢表存储在内存中。快表采用的是相联存储器，它的速度快来源于硬件本身，而不是依赖搜索算法来查找的，慢表通常是依赖于查找算法，故A和B错误。快表与慢表的命中率没有必然联系，快表仅是慢表的一个部分拷贝，不能够得到比慢表更多的结果，因此C错误。18、在计算机体系结构中，CPU内部包括程序计数器PC、存储器数据寄存器MDR、指令寄存器IR和存储器地址寄存器MAR等。若CPU要执行的指令为：MOVR0，#100(即将数值100传送到寄存器R0中)，则CPU首先要完成的操作是()。A、100—>R0B、100—>MDRC、PC—>MARD、PC—>IR标准答案：C知识点解析：本题考查取指周期完成的操作。CPU首先需要取指令，取指令阶段的第一个操作就是将指令地址(程序计数器PC中的内容)送往存储器地址寄存器。题干中虽然给出了一条具体的指令“MOVR0，#100”，实际上CPU首先要完成的操作是取指令，与具体指令是没有关系的。注意：取指周期完成的微操作序列是公共的操作，与具体指令无关。19、下列关于微指令编码方式的说法中，错误的是()。Ⅰ．字段直接编码可以用较少的二进制信息表示较多的微操作命令信号，例如有两组互斥微命令中，微命令个数分别为8和9，则只分别需要3位和4为即可表示Ⅱ．直接编码无须进行译码，微指令的微命令字段中每一位都代表一个微命令Ⅲ．垂直型微指令以较长的微程序结构换取较短的微指令结构，因而执行效率高、灵活性强都高于水平型微指令Ⅳ．字段间接编码中，一个字段的译码输出需要依靠另外某一个字段的输入A、Ⅰ、Ⅲ和ⅣB、Ⅱ、Ⅲ和ⅣC、Ⅱ和ⅣD、Ⅰ、Ⅱ、Ⅲ和Ⅳ标准答案：A知识点解析：本题考查微指令的编码方式。编码的是对微指令的控制字段进行编码，以形成控制信号；目的是在保证速度的情况下，尽量缩短微指令字长。微命令个数为8时，需要4位，假设只用3位，将会造成每个编码都会输出一个微命令，事实上，微命令的编码需要预留一个字段表示不输出，I错误。垂直型微指令的缺点是微程序长、执行速度慢、工作效率低，Ⅲ错误。字段间接编码中的一个字段的某些微命令还需由另一个字段中的某些微命令来解释，即受到某一个字段的译码输出，Ⅳ错误。一般进行微程序控制器的设计时要注意三个原则：①微指令字长尽可能短②微程序长度尽可能短③提高微程序的执行速度20、在系统总线中，地址总线的位数与()相关。A、机器字长B、实际存储单元个数C、存储字长D、存储器地址寄存器标准答案：D知识点解析：本题考查地址总线。地址总线的位数和实际存储单元个数、机器字长还有储存字长都是无关的，如32位的地址线，可以仅仅用2GB的内存。而MAR的位数和其是相关的，一般这二者是相等的。注意：地址总线的位数和最大存储单元个数相关，也和MAR的位数相关。地址总线的宽度决定了CPU可以访存的最大物理地址空间。如32位的地址线，按字节寻址的可寻址的最大容量为232bit=4GB。关于计算机各个字长以及总线长度的关系可以总结如下：机器字长是指计算机进行一次运算所能处理的二进制数据的位数。机器字长也就是运算器进行定点数运算的字长，通常也是CPU内部数据通路的宽度，也等于CPU内通用寄存器的位数；另外，CPU的位数和操作系统的位数没有绝对的关系，但是CPU的位数一定要大于等于操作系统的位数。存储字长是指一个存储单元存储一串二进制代码(存储字)的位数。指令字长是指机器指令中二进制代码的总位数。指令字长取决于从操作码的长度、操作数地址的长度和操作数地址的个数。指令还分为变长型和定长型，对于变长型指令，不同类型指令的字长是不同的，不过通常都是存储字长的整数倍。总线(指的是非CPU内部总线)一般分为控制总线、地址总线和数据总线(当然，有些总线结构中把地址和数据总线融合再一起进行时分复用，以周期的不同来区分传送的是地址还是数据，这种做法可以有效地减少总线宽度)。控制总线的数目一般是等于CPU需要向外传递控制信号的数目，当然也可以把一些互斥的控制信号放在一根控制总线中；而地址总线的数目一般等于地址寄存器的数目，而按字节编址的系统的内存最大容量不应超过2nB(n为地址寄存器的位数)，但是它和内存容量本身并没有任何必然联系；数据总线一般等于数据寄存器的位数(数据寄存器的位数又一般等于CPU的位数)，但是也并非绝对，因为CPU可以用少于该位数的总线(比如位数的二分之一)分周期(对应的就是两个传送周期)来传送一次数据。21、关于外中断(故障除外)和DMA，下列哪个说法是正确的()。Ⅰ．DMA请求和中断请求同时发生时，响应DMA请求Ⅱ．DMA请求、非屏蔽中断、可屏蔽中断都要在当前指令结束之后才能被响应Ⅲ．非屏蔽中断请求优先级最高，可屏蔽中断请求优先级最低Ⅳ．如果不开中断，所有中断请求均不能响应Ⅴ．在DMA方式中，数据的传送完全不用CPU干预A、Ⅰ和ⅤB、Ⅰ和ⅣC、ⅠD、Ⅱ和Ⅲ标准答案：C知识点解析：本题考查外中断方式和DMA方式的区别。和中断方式相比，DMA连接的是高速设备，其优先级高于中断请求，以防止数据丢失，Ⅰ正确。DMA请求的响应时间可以发生在每个机器周期结束时，只要CPU不占用总线，而中断请求的响应时间只能发生在每条指令执行完毕，Ⅱ错误。通常情况下，DMA的优先级要高于外中断，所以DMA优先级一般要比非屏蔽中断请求要高，Ⅲ错误。如果不开中断，非屏蔽中断(以及内中断)仍可响应，Ⅳ错误。在．DMA方式的预处理和后处理中，需要CPU的干预，只是在传送的过程中不需要CPU的干预，Ⅴ错误。注意：中断方式具有对异常时间的处理能力，而DMA方式仅局限于完成传送数据块的能力。22、通道方式的工作过程中，下列步骤的正确顺序是()。①组织I／O操作②向CPU发出中断请求③编制通道程序④启动I／O通道A、①→②→③→④B、②→③→①→④C、④→③→②→①D、③→④→①→②标准答案：D知识点解析：考查通道的工作过程。通道的基本工作过程(以一次数据传送为例)如下：①在用户程序中使用访管指令进入操作系统管理程序，由CPIU通过管理程序组织一个通道程序，并使用I／O指令启动通道(此后CPU并行运行应用程序)。②通道处理器执行CPU为其组织的通道程序，完成指定的数据的输入／输出工作。③通道程序结束后，向CPU发出中断请求。CPU响应此中断请求后，第二次进入操作系统，调用管理程序对输入／输出中断进行处理。23、多用户系统有必要保证进程的独立性，保证操作系统本身的安全，但为了向用户提供更大的灵活性，应尽可能少地限制用户进程。下面列出的各操作中，()是必须加以保护的。A、从内核(kernel)模式转换到用户(user)模式B、从存放操作系统内核的空间读取数据C、从存放操作系统内核的空间读取指令D、打开定时器标准答案：D知识点解析：本题考查用户态与核心态。打开定时器属于时钟管理的内容，对时钟的操作必须加以保护，否则，一个用户进程可以在时间片还未到之前把时钟改回去，从而导致时间片永远不会用完，那么该用户进程就可以一直占用CPU，这显然不合理。从用户模式到内核模式是通过中断实现的，中断的处理过程很复杂，需要加以保护，但从内核模式到用户模式则不需要加以保护。读取操作系统内核的数据和指令是静态操作，显然无需加以保护。24、下列关于进程状态的说法中，正确的是()。Ⅰ．从运行态到阻塞态的转换是进程的“自主”行为Ⅱ．从阻塞态到就绪态的转换是由协作进程决定的Ⅲ．一次I／O操作的结束，将会导致一个进程由就绪变为运行Ⅳ．一个运行的进程用完了分配给它的时间片后，它的状态变为阻塞Ⅴ．在进程状态转换中，“就绪一阻塞"是不可能发生的A、Ⅰ、Ⅱ和ⅢB、Ⅰ、Ⅱ和ⅤC、Ⅰ、Ⅱ和ⅣD、Ⅰ、Ⅱ、Ⅲ和Ⅴ标准答案：B知识点解析：本题考查进程的状态与转换。从运行态到阻塞态的转换是由进程自身决定的，它是由于进程的时间片用完，“主动”调用程序转入就绪态。进程的阻塞和唤醒是由block和wakeup原语实现的，block原语是由被阻塞进程自我调用实现的，而wakeup原语则是由一个与被唤醒进程相合作或其他相关的进程调用实现的，故Ⅰ和Ⅱ正确。I／O操作结束不会直接导致一个进程从就绪变为运行，只是当有等待该设备的进程时，I／O操作结束时会把该进程由阻塞变为就绪，Ⅲ错误。一个进程时间片到了以后，将会从运行变为就绪状态，Ⅳ错误。只有在运行中的进程当请求某一资源或等待某一事件时，才会转入到阻塞态，因此不可能直接从就绪态转到阻塞态，Ⅴ正确。答案选B。25、设有3个作业，它们的到达时间和运行时间如下表所示，并在一台处理机上按单道方式运行。如按高响应比优先算法，则作业执行的次序和平均周转时间依次为()。A、J1,J2,J3、1．73B、J1,J3,J2、1．83C、J1,J3,J2、2．08D、J1,J2,J3、1．83标准答案：B知识点解析：本题考查高响应比优先调度和平均周转时间。高响应比优先调度算法综合考虑了进程的等待时间和执行时间，响应比=(等待时间+执行时间)／执行时间。J1第一个提交，也第一个执行，J1在10：00执行完毕，这时J2、J3都已到达。J2的响应比=(1．5+l、)／1=2．5，J3的响应比=(0．5+0．25)／’0．25=3，故第二个执行J3；第三个执行J2。平均周转时间=(J1的周转时间+J2的周转时间+J3的周转时间)／3=[2+(1．75+1)+(0．5+0．25)]／3=5．5／3=1．83。26、设有n个进程共用一个相同的程序段，假设每次最多允许m个进程(m≤n)同时进入临界区，则信号量S的初值为()。A、mB、nC、m—nD、—m标准答案：A知识点解析：本题考查互斥信号量的设置。互斥信号量的初值应为可用资源数，在本题中为可同时进入临界区的资源数。每当一个进程进入临界区，S减1，减到—(n—m)为止，此时共有｜S｜个进程在等待进入。27、利用银行家算法进行安全序列检查时，不需要的参数是()。A、系统资源总数B、满足系统安全的最少资源数C、用户最大需求数D、用户己占有的资源数标准答案：B知识点解析：本题考查银行家算法。安全性检查一般要用到进程所需的最大资源数，减去进程占用的资源数，得到进程为满足进程运行尚需要的可能最大资源数，而系统拥有的最大资源数减去已分配掉的资源数得到剩余的资源数，比较剩余的资源数是否满足进程运行尚需要的可能最大资源数就可以得到当前状态是否安全的结论。而满足系统安全的最少资源数并没有这么一个说法。28、在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1，3，2，1，1，3，5，1，3，2，1，5。当分配给该作业的物理块数分别为3和4时，则在访问过程中所发生的缺页率分别为()。A、50％、33％B、25％、100％C、25％、33％D、50％、75％标准答案：A知识点解析：本题考查页面置换的相关计算。当物理块数为3时，缺页情况如下表所示：缺页次数为6，缺页率为6／12=50％。当物理块数为4时，缺页情况如下表所示：缺页次数为4，缺页率为4／12=33％。29、如下程序在页式虚存系统中执行，程序代码位于虚空间O页，A为128"128的数组，在虚空间以行为主序存放，每页存放128个数组元素。工作集大小为2个页框(开始时程序代码已在内存，占1个页框)，用LRU算法，下面两种对A初始化的程序引起的页故障数分别为()。程序1：for(j=1；J＜=128；J++)for(i=1，i＜=128；i++)A[i][j]=0；程序2：for(i=1，i＜=128；i++)for(j=1，j＜=128；J++)A[i][j]=0；A、128*128，128B、128，12*128C、64，64*64D、64*64，64标准答案：A知识点解析：本题考查缺页中断的计算。进程的工作集是2个页框，其中一个页框始终被程序代码占用，所以可供数据使用的内存空间只有一个页框。在虚空间以行为主序存放，每页存放128个数组元素，所以每一行占～页。程序1访问数组的方式为先行后列，每一次访问都是针对不同的行，所以每一次都会产生缺页中断，一共128×128次。程序2访问数组的方式是先列后行，每次访问不同行时会产生缺页中断，一共128次。30、现代操作系统中，文件系统都有效地解决了文件重名(即允许不同用户的文件可以具有相同的文件名)问题，系统是通过()来实现这一功能的。A、重名翻译机构B、建立索引表C、树型目录结构D、建立指针标准答案：C知识点解析：本题考查文件的目录结构。树型目录结构解决了多用户之间的文件命名问题，即在不同目录下可以有相同的文件名。31、下列叙述中，错误的是()。Ⅰ．索引顺序文件也是一种特殊的顺序文件，因此通常存放在磁带上Ⅱ．索引顺序文件既能顺序访问，又能随机访问Ⅲ．存储在直接存取存储器上面的文件也能顺序访问，但一般效率较差Ⅳ．在磁带上的顺序文件中添加新记录时，必须复制整个文件A、Ⅰ和ⅣB、Ⅱ和ⅣC、Ⅰ和ⅡD、Ⅰ、Ⅱ和Ⅳ标准答案：A知识点解析：本题考查文件的物理结构。对于Ⅰ，直接存取存储器(磁盘)既不像RAM那样随机地访问任一个存储单元，也不像顺序存取存储器(如磁带)那样完全顺序存取，而是介于两者之间，存取信息时通常先寻找整个存储器的某个小区域(如磁盘上的磁道)再在小区域顺序查找。所以我认为直接存取不完全等于随机存取。索引顺序文件如果存放在磁带上，则无法实现随机访问，也就失去了索引的意义。Ⅱ显然正确。磁盘上的文件可以直接访问，也可以顺序访问，但如果顺序访问的话，就比较低效了，Ⅲ正确。对于Ⅳ，在顺序文件的最后添加新的记录时，则不必须复制整个文件。32、下列关于设备独立性的论述中，正确的是()。A、设备独立性是I／O设备具有独立执行I／O功能的一种特性B、设备独立性是指用户程序独立于具体使用的物理设备的一种特性C、设备独立性是指独立实现设备共享的一种特性D、设备独立性是指设备驱动独立于具体使用的物理设备的一种特性标准答案：B知识点解析：本题考查设备独立性的定义。设备独立性的定义就是指用户程序独立于具体物理设备的一种特性，引入设备的独立性是为了提高设备分配的灵活性和设备的利用率等。33、在OSI参考模型中，上层协议实体与下层协议实体之间的逻辑接口称为服务访问点(SAP)。在Intemet数据帧中，目的地址“0x000F781C6001”属于()的服务访问点。A、数据链路层B、网络层C、传输层D、应用层标准答案：A知识点解析：此题引用了OSI／RM中服务访问点的概念，但考查的却是TCP／IP参考模型的知识。在TCP／IP参考模型中，网络接口层的SAP是MAC地址；在网际层(也可称为网络层)使用的是IP协议，其SAP便是IP地址；而传输层使用的主要协议为TCP和UDP，TCP使用的SAP是TCP的端口号，UDP使用的SAP是UDP的端口号。在Internet数据帧中，地址“0×000F781C6001”是一个48位的地址，在TCP／IP模型中，只有网络设备(例如网卡和无线网卡)的物理地址是48位的，因此该地址属于数据链路层的服务访问点。34、一个传输数字信号的模拟信道的信号功率是0．62w，噪音功率是0．02w，频率范围是3．5～3．9MHz，该信道的最高数据传输速率是()。A、1MbpsB、2MbpsC、4MbpsD、8Mbps标准答案：B知识点解析：本题考查香农定理的应用。题干中已说明是有噪声的信道，因此应联想到香农定理，而对于无噪声的信道，则应联想到奈奎斯特定理。首先计算信噪比S／N=0．62／0．02=31；带宽W=3．9—3．5=0．4MHz，由香农定理可知最高数据传输率V=W×log2(1+S／N)=0．4×log2(1+31)=2Mbps。35、在简单停止-等待协议中，为了解决重复帧的问题，需要采用()。A、帧序号B、定时器C、ACK机制D、NAK机制标准答案：A知识点解析：本题考查简单停止．等待协议机制。在停止等待协议中，如果在规定时间内没有收到接收方的确认帧信息，发送方就会重新发送该帧，也就是发送了重复帧。为了避免因为重复帧引起不必要的错误，简单停止—等待协议采用了帧序号机制，即：在规定的时间内未接收到确认帧，即重新发送；此时接收到的帧为重复帧，而序号与前面一帧是相同的。接收端连续接收到的帧如果序号相同，则认为是重复帧；如果帧序号不同，则理解为仅仅是内容相同的不同的帧，所以A答案正确。有同学会选择C答案，实际上ACK机制是用于TCP协议中的拥塞控制机制，并不是专门为了解决重复帧问题的。36、一个2Mbps的网络，线路长度为1km,传输速度为20m／ms,分组大小为100字节，应答帧大小可以忽略。若采用“停止一等待”协议，则实际数据速率是()。A、2MbpsB、1MbpsC、8KbpsD、16Kbps标准答案：C知识点解析：本题考查“停止—等待”协议的效率分析。停止．等待协议每发送完一个分组，需要收到确认后才能发送下一个分组。发送延迟=8×100÷(2×1000000)=0．0004s，传播延迟=1000m÷20m／ms=50ms=0．05s，最小间隔=0．0004s+0．05s×2=0．1004s。故数据速率=8×100bit÷0．1004s≈8Kbps。37、R1和R2是一个自治系统中采用RIP路由协议的两个相邻路由器，R1的路由表如表l所示，当Rl收到R2发送的报文(见表2)后，R1更新的3个路由表项中距离值从上到下依次为()。A、0、4、3B、0、4、4C、0、5、3D、0、5、4标准答案：D知识点解析：对比表1和表2发现，R1到达目的网络20．0．0．0的距离为7，而表2中R2到达目的网络20．0．0．0的距离为4。由于7＞4+1，此时R1经过R2到达目的网络20．0．0．0的路由距离变短了，所以R1要根据R2提供的数据修改相应路由项的距离值为5。R1到达目的网络30．0．0．0的距离为4，而表2中R2到达目的网络30．0．0．0的距离为3。由于4=3+1，显然R1经过R2到达目的网络30．0．0．0，并不能得到更短的路由距离，所以R1无需进行更新操作，将保持该路由表项原来的参数。当R1收到R2发送的报文后，按照以下规律更新路由表信息：1)如果R1的路由表没有某项路由记录，则R1在路由表中增加该项，由于要经过R2转发，所以距离值要在R2提供的距离值基础上加1。2)如果R1的路由表中的表项路由记录比R2发送的对应项的距离值加1还要大，则R1在路由表中修改该项，距离值根据R2提供的值加1。可见，对于路由器距离值为O的直连网络，则无需进行更新操作，其路由距离保持为0。38、路由器收到一个数据包，其目的地址为195．26．17．4，该地址属于()子网。A、195．26．0．0／21B、195．26．16．0／20C、195．26．8．0／22D、195．26．20．0／22标准答案：B知识点解析：目的地址195．26．17．4转换为二进制的表达方式为：11000011．00011010．00010001．00000100。对该IP取20、21、22位的子网掩码，就可以得到该IP所对应的子网：195．26．16．0／20、195．26．16．0／21、195．26．16．0／22。从而可以得出该地址属于195．26．16．0／20的子网。39、假设在没有发生拥塞的情况下，在一条往返时间RTT为10ms的线路上采用慢开始控制策略。如果接收窗口的大小为24KB，最大报文段MSS为2KB。那么发送方能发送出一个完全窗口(也就是发送窗口达到24KB)需要的时间是()。A、30msB、60msC、50msD、40ms标准答案：D知识点解析：本题考查对TCP拥塞控制的慢开始算法的理解。按照慢开始算法，发送窗口的初始值为拥塞窗口的初始值即MSS的大小2KB，然后一次增大为4KB，8KB，16KB，然后是接收窗口的大小24KB，即达到第一个完全窗口。因此达到第一个完全窗口所需的时间为4×RTT=40ms。慢开始算法考虑了网络容量与接收端容量，要求每个发送端维护2个窗口：接收窗口和拥塞窗口，两个窗口的较小值就为发送窗口。所谓“慢开始”就是由小到大逐渐增大发送端的拥塞窗口数值。其基本原理是：在连接建立时，将拥塞窗口的大小初始化为一个MSS的大小，此后拥塞窗口每经过一个RTT，就按指数规律增长一次，直到出现报文段传输超时或达到所设定的慢开始门限值ssthresh。四种拥塞控制算法是TCP协议的核心所在，解题时或画出拥塞窗口变化曲线图，或列出拥塞窗口大小变化序列，尤其要注意在拐点处的变化情况。40、一台域名服务器希望解析域名www.google．com，如果这台主机配置的DNS地址为a，Internet的根域名服务器为b，而存储域名www．google．com与其IP地址对应关系的域名服务器为c，那么这台主机通常先查询()。A、域名服务器aB、域名服务器bC、域名服务器cD、不确定标准答案：A知识点解析：本题考查域名解析的过程。主机发出DNS查询报文时，该报文首先被送往该本地域名服务器。本地域名服务器不能立即回答该查询时，就以DNS客户的身份向某一根域名服务器查询。若根域名服务器也没有该主机的信息时(但此时其一定知道该主机的授权域名服务器的IP地址)，有两种做法：1)递归查询：根域名服务器向该主机的授权域名服务器发送DNS查询报文，查询结果再逐级返回给原主机；2)迭代查询：根域名服务器把授权域名服务器的IP地址返回给本地域名服务器，由本地域名服务器再去查询。不管采用何种查询方式，首先都要查询本地域名服务器。该主机配置的DNS地址a即为其本地域名服务器地址。二、综合应用题(本题共17题，每题1.0分，共17分。)41、对于一个堆栈、若其入栈序列为1，2,3，……，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1，2,3，……，n)／输出序列对应一种二叉树形态的方法，并以入栈序列1，2，3(即n=3)为例加以说明。标准答案：由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树。因此，若入栈序列为1,2,3，……，n相当于前序遍历序列是1,2,3，……n，出栈序列就是该前序遍历对应的二叉树的中序序列的数目，而中序遍历的过程实质就是一个结点进栈和出栈的过程。二叉树的形态确定了结点进栈和出栈的顺序，也就确定了结点的中序序列。当结点入栈序列为{1,2,3}时，出栈序列可能为：{3,2,1}，{2,3,1}，{2,1,3}，{1,3,2}，{1,2,3}，它们对应二叉树如下：【扩展】进栈出栈操作与二叉树中序遍历的关系：①一个结点进栈后有两种处理方式：要么立刻出栈(没有左孩子)：或者下一个结点进栈(有左孩子)。②一个结点出栈后也有两种处理方式：要么继续出栈(没有右孩子)；或者下一个结点进栈(有右孩子)。知识点解析：暂无解析已知一棵二叉树采用二叉链表存储，结点构造为root指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过1，例如下图所示的二叉树就是一棵平衡二叉树。要求：42、给出算法的基本设计思想。标准答案：基本的基本设计思想：设置二叉树的平衡标记balance，以标记返回二叉树bt是否为平衡二叉树，若为平衡二叉树，则返回1，否则返回0；h为二叉树bt的高度。采用前序遍历的递归算法：①若bt为空，则高度为0，balance=1。②若bt仅有根结点，则高度为1，balance=1。③否则，对bt的左、右子树执行递归运算，返回左、右子树的高度和平衡标记，bt的高度为最高子树的高度加1。若左、右子树的高度差大于1，则balance=0；若左、右子树的高度差小于1，且左、右子树都平衡时，balance=1，否则balance=0。知识点解析：暂无解析43、根据设计思想，采用C或C++语言描述算法，关键之处给出注释。标准答案：算法的实现加下：voidJudge_AVL(BjiTreebt，int&balance，int&h){intbl，br，hl，hr；／／左、右子树的平衡标记和高度if，(bt==NULL){／／空树，高度为0h=0，balance=1；}elseif(p—>ichi