计算机专业(基础综合)模拟试卷31(题后含答案及解析)

计算机专业（基础综合）模拟试卷31(题后含答案及解析)题型有：1.单项选择题2.综合应用题单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1．一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是()。A．5，4，3，2，1B．4，5，3，2，1C．4，3，5，1，2D．1，2，3，4，5正确答案：C解析：此类问题是常见题型。解答的基本原理是：一串数据依次通过一个栈，并不能保证出栈数据的次序总是倒置，可以产生多种出栈序列。一串数据通过一个栈后的次序由每个数据之间的进栈、出栈操作序列决定，只有当所有数据“全部进栈后再全部出栈”才能使数据倒置。事实上，存在一种操作序列——“进栈、出栈、进栈、出栈……”——可以使数据通过栈后仍然保持次序不变。[解题技巧]将一组数据入栈后，判断题目备选项中的不可能的出栈顺序，上述这类题目有一个解题技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序(指的是元素的序号)的两个元素。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。3．在一棵具有n个结点的二叉树中，所有结点的空子树个数等于()。A．nB．n－1C．n＋1D．2n正确答案：C解析：在一棵具有n个结点的二叉树中，每个结点可有两棵子树，共有2n个子树。其中二叉树的总分支数等于总结点数减1，即有n－1棵不空的子树。所以在一棵具有n个结点的二叉树中，所有结点的空子树个数等于n＋1。4．在常用的描述二叉排序树的存储结构中，关键字值最大的结点是()。A．左指针一定为空B．右指针一定为空C．左右指针均为空D．左右指针均不为空正确答案：B解析：在二叉排序树的存储结构中，每个结点由三部分构成，其中左(或右)指针指向比结点的关键值小(或大)的结点。关键字值最大的结点位于二叉排序树的最右位置上，因此它的右指针一定为空。5．由权值为9、2、5、7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为()。A．23B．37C．44D．46正确答案：C解析：由权值为9、2、5、7的四个叶子构造的哈夫曼树可如下图所示。该树的带权路径长度＝9×1＋7×2＋2×3＋5×3＝44。[归纳总结]对哈夫曼树特征的总结：(1)用n个权值(对应n个叶子结点)构造哈夫曼树，共需要n－1次合并，即哈夫曼树中非叶子结点的总数为n－1，总结点个数为2n－1。(2)哈夫曼树中没有度为1的结点，因为非叶子结点都是通过两个结点合并而来。但是，没有度为1的二叉树并不一定是哈夫曼树。(3)用n个权值(对应n个叶子结点)构造的哈夫曼树，形态并不是唯一的。建立哈夫曼树的过程中有以下三种常见的错误：(1)在合并中不是选取根结点权值最小的两棵二叉树(包括已合并的和未合并的)，而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并。(2)每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树。(3)有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧合，没有规律性，而没有规律性的解法不利于用计算机进行处理。6．若一个具有n个结点、k条边的非连通无向图是一个森林(n>k)，则该森林中必有树的数目是()。A．kB．nC．n—kD．n＋k正确答案：C解析：因为一棵具有n个顶点的树有n－1条边，因此设题目中的森林有m棵树，每棵树具有顶点数为Vi(1≤i≤m)，则V1＋V2＋…Vm＝N及(V1－1)＋(V2－1)＋…(Vm－1)＝K，所以，2＝m＋k。7．采用邻接表存储的图的广度优先遍历算法类似于树的()。A．中根遍历B．先根遍历C．后根遍历D．按层次遍历正确答案：D解析：深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。广度优先搜索遍历类似于树的按层次遍历的过程。或者说，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。8．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是()。A．G中有弧B．G中有一条从Vi到Vj的路径C．G中没有弧D．G中有一条从Vi到Vj的路径正确答案：D解析：选项A、B、C都是有可能出现的，但是选项D是不可能出现的，因为若是G中有一条从Vj到Vi的路径，则在图的拓扑序列中顶点Vi应该在顶点Vi之前。9．假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要进行的探查次数是()。A．k－1B．kC．k＋1D．k(k＋1)／2正确答案：D解析：假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，探查次数最少的情况是第1个关键字通过1次比较后插入，第2个关键字通过2次比较后插入，……，第k个关键字通过k次比较后插入。总的比较次数＝1＋2＋……＋k＝k(k＋1)／2。10．下列序列中，满足堆定义的是()。A．(100，86，48，73，35，39，42，57，66，21)B．(12，70，33，65，24，56，48，92，86，33)C．(103，97，56，38，66，23，42，12，30，52，6，26)D．(5，56，20，23，40，38，29，61，36，76，28，100)正确答案：A解析：依据堆的定义，将选项中的每个数列分别看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左／右子树不空时，根结点的值小于(或大于)左／右子树根结点的值。11．对于一个长度为n的任意表进行排序，至少需要进行的比较次数是()。A．O(n)B．O(n2)C．O(log<n)D．O(nlogn)正确答案：D解析：在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少需要t次比较，则显然会有2t种情况，由于n个记录总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是有：2t≥n!，即t≥log2(n!)。因为log2(n!)≈nlog2n，所以t≥nlog2n。12．哈佛(Harvard)结构的基本特点是()。A．采用多指令流单数据流B．程序和数据在不同的存储空间C．堆栈操作D．存储器按内容选择地址正确答案：B解析：哈佛结构的指令和数据是完全分开的，存储器分为两部分，一个是程序存储器，用来存放指令，另一个是数据存储器，用来存放数据。[归纳总结]根据程序(指令序列)和数据的存放形式，存储器设计思想又可以分为冯.诺依曼结构和哈佛结构。冯.诺依曼结构的存储器设计是指令和数据是不加区别混合存储在同一个存储器中，共享数据总线；哈佛结构的存储器设计是指令和数据是完全分开的，存储器分为两部分，一个是程序存储器，用来存放指令，另一个是数据存储器，用来存放数据。在冯.诺依曼结构中不能同时取指令和取操作数，而哈佛结构允许同时获取指令字(来自程序存储器)和操作数(来自数据存储器)。13．若二进制定点小数真值是－0．1101，机器中表示为1．0010，则该数采用的编码方法是()。A．原码B．补码C．反码D．移码正确答案：C解析：真值－0．1101，对应的原码表示为1．110l，补码表示为1．0011，反码表示为1．0010。移码通常用于表示阶码，不用来表示定点小数。[归纳总结]对于负数，原码、补码和反码各有不同的表示形式。[解题技巧]由于真值是定点小数，不能用移码表示，所以可立即排除掉选项D。接下来写出真值对应的原码、补码和反码，即可得出答案。14．描述流水线CPU基本概念中，正确表述的句子是()。A．流水线CPU是以空间并行性为原理构造的处理B．流水线CPU一定是RISC机器C．流水线CPU一定是多媒体CPUD．流水线CPU是一种非常经济而实用的时间并行技术正确答案：D解析：在4个选项中唯有选项D是正确的。选项A是指超标量处理机。RIsc机器一定采用流水线技术，而流水线CPU不一定就是RIsC机器。流水线CPU也不一定是多媒体CPU。[归纳总结]超标量处理机采用的是空问并行性，流水线处理机采用的是时间并行性。15．原码乘法时，符号位单独处理，乘积的符号是()。A．两个操作数符号相“与”B．两个操作数符号相“或”C．两个操作数符号相“异或”D．两个操作数中绝对值较大数的符号正确答案：C解析：原码的符号位为“1”表示负数，为“0”表示正数。原码乘法时，符号位单独处理，乘积的符号是两个操作数符号相“异或”，同号为正，异号为负。[归纳总结]凡是原码运算，不论加减乘除，符号位都单独处理，其中乘除运算的结果符号由参加运算的两个操作数符号“异或”得到。16．页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如下图所示。假定页面的大小为8K，图中所示的十进制逻辑地址9612经过地址变换后，形成的物理地址a(十进制)是()。A．42380B．25996C．9612D．8192正确答案：B解析：由于页面大小为8K，则十进制逻辑地址9612处于第1虚页中，页内地址一1420，其对应的实页为第3页，故a＝3×8192＋1420＝25996。[归纳总结]具体的计算公式有：虚页号＝[虚地址／页面大小]页内地址＝虚地址－虚页号×页面大小主存实地址＝实页号×页面大小＋页内位移量页式虚拟存储器中的页表的每一行记录了与某个虚页对应的若干信息，包括虚页号、装入位和实页号等。页表基址寄存器和虚页号拼接成页表索引地址。根据这个索引地址可读到一个页表信息字，然后检测页表信息字中装入位的状态。若装入位为“1”，表示该页面已在主存中，将对应的实页号与虚地址中的页内地址相拼接就得到了完整的实地址；若装入位为“0”，表示该页面不在主存中，于是要启动I／O系统，把该页从辅存中调入主存后再供CPU使用。[解题技巧]首先，根据题目所给出的虚地址可以计算出虚页号和页内地址，然后根据所求出的虚页号查页表找出实页号，最后将实页号拼上页内地址得到相应的主存地址。17．在指令系统的各种寻址方式中，获取操作数最快的方式是()。A．直接寻址B．立即寻址C．寄存器寻址D．间接寻址正确答案：B解析：立即寻址是一种特殊的寻址方式，指令中在操作码字段后面的部分不是通常意义上的地址码，而是操作数本身，也就是说数据就包含在指令中，只要取出指令，也就取出了可以立即使用的操作数，不必再次访问存储器，从而提高了指令的执行速度。[归纳总结]所谓寻址，指的是寻找操作数的地址或下一条将要执行的指令地址。各种不同的寻址方式获取操作数的速度是不相同的，在这四种寻址方式中，获取操作数的速度由快至慢依次为立即寻址、寄存器寻址、直接寻址、间接寻址。18．在计算机体系结构中，cPU内部包括程序计数器PC、存储器数据寄存器MI)R、指令寄存器IR和存储器地址寄存器MAR等。若CPU要执行的指令为：MOVR0，#100(即将数值100传送到寄存器R0中)，则CPU首先要完成的操作是()。A．100→R0B．100→MDRC．PC→MARD．PC→IR正确答案：C解析：无论运行什么类型的指令，CPU首先需要取指令，取指令阶段的第一个操作就是将指令地址(程序计数器PC中的内容)送往存储器地址寄存器。[归纳总结]取指周期完成的微操作序列是公共的操作，与具体指令无关，取指公操作如下：(1)将程序计数器PC中的内容送至存储器地址寄存器MAR，记作(PC)→MAR；(2)向主存发读命令，记作Read；(3)从主存中取出的指令送到存储器数据寄存：器MDR，记作M(MAR)→MDR；(4)将MDR的内容送至指令寄存器IR中，记作(MDR)→IR；(5)将PC的内容递增，为取下一条指令做好准备，记作(PC)＋1→PC。[解题技巧]题干中虽然给出了一条具体的指令“MOVRO，#100”，实际上CPU首先要完成的操作是取指令，与具体指令是没有关系的。19．在微指令的编码方式中，若微命令数相同，下列叙述中正确的是()。I．直接控制方式与编码控制方式的微指令长度相等Ⅱ．最短编码控制和直接控制方式不影响微指令字长Ⅲ．编码控制方式的微指令比直接控制方式的微指令短Ⅳ．直接控制的微指令比字段编码的微指令长V．字段直接编码的微指令与字段间接编码的微指令长度相等Ⅵ．字段间接编码的微指令比字段直接编码的微指令长A．Ⅲ和ⅣB．I和ⅢC．Ⅱ和ⅢD．Ⅲ、Ⅳ和Ⅵ正确答案：A解析：微指令的操作控制字段可分为直接控制法、最短编码法和字段编码法，字段编码法中又可以进一步分为字段直接编码法和字段间接编码法。若微命令数相同，微指令操作控制字段的长度由短至长依次为：最短编码→字段间接编码→字段直接编码→直接控制。操作控制字段短则相应的微指令字长就短。[归纳总结]直接控制法即每个独立的二进制位代表一个微命令，该位为“1”表示这个微命令有效，为“0”则表示这个微命令无效。最短编码法将所有的微命令统一编码，每条微指令只定义一个微命令。字段编码法是前述两种编码法的一个折中的方法，将操作控制字段分为若干组，组内采用最短编码法，组与组之间采用直接控制法。在字段编码法中，操作控制字段的分组并非是任意的，必须要遵循如下的原则：(1)应把互斥性的微命令分在同一组内，兼容性的微命令分在不同组内。这样不仅有助于提高信息的利用率，缩短微指令字长，而且有助于充分利用硬件所具有的并行性，加快执行的速度。(2)应与数据通路结构相适应。(3)每个小组中包含的信息位不能太多，否则将增加译码线路的复杂性和译码时间。(4)一般每个小组还要留出一个状态，表示本组不发出任何微命令。因此当某组的长度为3位时，最多只能表示7个互斥的微命令，通常用000表示不操作。20．下列计算机总线属于串行总线的是()。A．PCIB．1394C．E1SAD．ISA正确答案：B解析：1394是高性能的串行总线。[归纳总结]IEEE一1394是由IEEE标准委员会发布的，它的最初版本传输速率为200．Mbps，高版本有望支持1600Mbps的传输速率，甚至可达到3200Mbps。IEEE一1394构建在菊花链或树状的拓扑结构上的，它支持63个节点，每个节点可以支持多达16台设备的菊花链。最新的高性能外部总线设计的趋势是使用串行结构，这样可以通过一根导线一次发送一位数据，而无须担心数据的到达时间，如1EEE一1394端口(使用高速串行技术)支持的传输速率高达400Mbps(约50MB／s)，USB2．0支持的传输速率可以为480Mbps(约60MB／s)。[解题技巧]选项A、C、D均属于并行总线。21．某数码相机内置128MB的存储空间，拍摄分辨率设定为1600×1200像素，颜色深度为24位，若不采用压缩存储技术，使用内部存储器最多可以存储的照片数是()。A．12B．25C．13D．23正确答案：D解析：颜色深度为24位(3个字节)，每张照片的存储量为1600×1200×3B≈5．5MB，128MB／5．5MB＝23．3，所以内置的存储空间最多可存储23张照片。[归纳总结]数码相机内部存储器存放照片数的多少与照片的分辨率和颜色数有关。22．中断向量表中保存的是()。A．被中断程序的返回地址B．中断服务程序入口地址C．中断优先级D．中断源编码正确答案：B解析：中断向量表是用来存放中断服务程序的人口地址的。[归纳总结]许多计算机中在主存的特定位置设置有中断向量表，在中断向量表的相关单元中存放着各级中断服务程序的入口地址。中断源给出的向量地址是中断向量表的指针，也就是中断服务程序入口地址的地址。由向量地址指向一个中断向量表，从中断向量表的相应单元中再取出中断服务程序的入口地址。23．对于设计实时操作系统，不是其设计目标的是()。A．安全可靠B．处理机效率C．及时响应输入D．快速处理请求正确答案：B解析：本题考查实时操作系统的设计目标。实时操作系统要求能对用户的请求在规定的时间内完成，同时需要保证进程运行的安全性和高可靠性。而处理机的效率不是实时操作系统设计所关心的。24．并发进程在运行时，其推进的相对速度是()。A．由进程的程序结构决定B．由进程自己的代码控制C．与进程调度策略有关D．在进程创建时确定的正确答案：C解析：在进程的一次运行过程中，其代码的执行序列是确定的，即使有循环或转移，对于进程来讲，其运行的轨迹也是确定的，所以对于这样一个确定的运行轨迹，进程自身是可以控制自身前进或停止的，例如可以休眠10秒再唤醒等，但是，当这样的进程存在于一个并发系统中时，这种确定性就被打破了。由于系统中存在有大量的可运行的进程，操作系统为了提高计算机的效率，会根据用户的需求和系统资源的数量来自动地进行调度和切换，以保证系统高效地运行。此时，进程由于被调度，打破了原来的固有执行速度，走走停停，因此，进程的相对速度就不受进程自己的控制，而是取决于进程调度的策略。不确定性也是并发系统的一个特征。25．两个旅行社甲和已为旅客到某航空公司订飞机票，形成互斥资源的是()。A．旅行社B．航空公司C．飞机票D．旅行社与航空公司正确答案：C解析：本题考查互斥资源的问题，一张飞机票不能售给不同的旅客，因此飞机票是互斥资源，其它因素只是为完成飞机票订票的中间过程，与互斥资源无关。26．在进程通信中，消息的一般形式为四个部分组成。是()。A．发送进程名、接收进程名、消息标示符、消息正文B．发送进程名、消息标示符、消息长度、消息正文C．发送进程名、接收进程名、消息长度、消息当前状态D．发送进程名、接收进程名、消息长度、消息正文正确答案：D解析：在消息传递系统中，进程间的数据交换是以消息(在计算机网络中又称为报文)为单位的。消息的一般结构形式有发送进程名、接收进程名、消息长度、消息正文。故正确答案为选项D。27．某计算机系统中内存保护采用基址、限长寄存器的疗法来实现，那么，判断是否越界的判别式是()。A．0≤被访问的逻辑地址<限长寄存器的内容B．0≤被访问的逻辑地址≤限长寄存器的内容C．0≤被访问的物理地址<限长寄存器的内容D．0≤被访问的物理地址≤限长寄存器的内容正确答案：A解析：本题考查存储保护的方法。考查基址、限长寄存器方式下是如何进行越界判断的。在基址、限长寄存器的保护方式下，系统为每个并发进程设置一个基址寄存器和一个限长寄存器，限长寄存器保存的是进程的长度，所以有关系式：逻辑地址<进程长度。在此注意，地址一般是从0开始，故需要包含。一般，对于长度为100的区域，地址为从0～99。因此选A。28．在某个计算机系统中，内存的分配采用按需调页的方式，测得当前CPU的利用率为8％，硬盘交换空间的利用率为55％，硬盘的繁忙率为97％，其它设备的利用率可以忽略不计，由此断定系统发生异常，此异常可能会是()，解决办法是()。I．Belady现象；Ⅱ．抖动；Ⅲ．死锁；Ⅳ．饥饿；V．加大交换空间容量；Ⅵ．增加内存容量；Ⅶ．增加CPU数量；Ⅷ．增加并发进程数；A．I和VB．Ⅱ和ⅥC．Ⅲ和ⅦD．Ⅳ和Ⅷ正确答案：B解析：本题考查按需调页下提高系统效率的措施。首先判断系统异常是属于什么异常，从测试数据看，CPU不忙，交换空问也不满，就是硬盘的IO非常繁忙，所以不是交换空间不够，系统也没有死锁，主要瓶颈在内外存交换上，因此可能的最大情况就是抖动，即由于内存紧缺，并发进程数多，采用按需调页而引起的频繁的换入换出作业。对于抖动问题的解决，最好的办法是增加内存，或减少并发进程数，单纯地增大交换分区的大小或增加CPU数量或提高CPU处理能力都没有解决根本问题。29．若用100个双字(字长32位)组成的位示图管理内存，假定用户归还一个块号为240的内存块时，它对应的位示图的位置是()。A．字号为6，位号为16B．字号为7，位号为16C．字号为6，位号为14D．字号为7，位号为14正确答案：B解析：位示图也称为示位图，是利用二进制的一位来表示内存或磁盘中一个存储块的使用情况。当其值为“0”时，表示对应的块空闲；为“1”时，表示已分配。反之亦然。内存或磁盘上的所有块都有一个二进制位与之对应，这样，由所有块所对应的位构成一个集合，称为位示图。计算方法：字号i＝INT(240／32)＝7字内位置j＝MOD(240／32)＝1630．通常对文件系统来说，文件名和文件属性可以找到的地方是()。A．目录B．索引C．字典D．作业控制块正确答案：A解析：在文件系统中，为每个文件建立一个目录(或称文件目录或目录项)，文件目录记录文件的名字，文件长度和文件存放的外存地址以及文件属性、文件创建时间日期等信息。文件目录在大部分文件系统中又成为文件控制块，即FCB。31．为保证文件的安全，操作系统一般采用多种方式来保护文件。为防止未经授权对文件的访问而造成的篡改或破坏，所采取的方法是()。A．访问控制列表B．转储备份C．加密数据D．口令保护正确答案：A解析：本题考查的是文件的保护。系统中的文件有些是只能由文件拥有者使用，有些是可以共享的，独享的文件需要采取保护措施，防止非法用户存取文件。保护文件的方法可以有多种，定时转储备份可以防止设备故障造成的文件损坏，口令保护和加密数据可以保护文件被非法窃取时不会泄密，而对于授权用户的使用，一般采用访问控制列表来对文件的权限进行分配，从而保证文件的安全。32．CPU输出数据的速度远远高于打印机的打印速度，为解决这一矛盾，可采用的技术是()。A．并行技术B．通道技术C．缓冲技术D．虚存技术正确答案：C解析：缓冲技术的引入主要解决cPu速度和外设速度不匹配的问题，它同时减少了通道数量上的占用，提高了CPU、IO和通道的并发性，减少了中断的次数，放宽了CPU对中断响应的时间要求，例如打印、文件访问，网络收发等场合，均要用到缓冲技术。33．在不同网络节点的对等层之间通信需要的是()。A．模块接口B．对等层协议C．电信号D．传输介质正确答案：B解析：本题考查计算机网络体系结构，注意对等层是指在计算机网络协议层次中，将数据直接传递给对方的任何两个同样的层次，因此对等层之间通信必须需要对等层之间的协议，这里选项A是相邻层之问通信所必需的，选项C和D属于物理层，答案是B。34．关于数据交换，下列叙述不正确的是()。A．线路交换面向连接B．分组交换比报文交换具有更好的网络响应速度C．报文交换无存储转发过程D．分组交换有存储转发过程正确答案：C解析：该题考查数据交换的原理，要明确报文是一份完整的信息，而分组是报文分组的简称，又叫信息包，将报文划分为若干格式化信息单位作为网络层的数据传输单元。分组交换方式：将一份完整的报文划分为若干组，每个分组独立的从源节点发送到目的节点，目的节点收到这些分组后，再组装成源报文。其特点是化整为零，即将完整的较长的报文划分为较小的分组，以分组单位传输数据。优点是减少节点缓冲区容量，并有利于差错控制。而存储转发是指每个节点均设有缓冲区，分组到达某节点后，先存储在缓冲区中，等待输出链路空闲时在转发到下一个节点。本题中面向连接的只有线路交换，存储转发只有分组和报文，由于分组交换的灵活性，使其具有更好的响应速度，因此答案是C。35．当DHCP客户计算机第一次启动或初始化1P时，广播发送给本地子网的消息是()。A．DHCPDISC()VERB．DHCPREQUESTC．DHCPOFFERD．DHCPACK正确答案：A解析：本题考查DHCP协议的工作原理，需要IP地址的主机在启动时就向DHCP服务器广播发送发现报文(DHCPDISC0VER)，这时该主机就成为DHCP客户。本地网络上所有主机都能收到此广播报文，但只有DHCP服务器才回答此广播报文。DHCP服务器先在其数据库中查找该计算机的配置信息。若找到，则返回找到的信息。若找不到，则从服务器的IP地址池(addresspool)中取一个地址分配给该计算机。DHCP服务器的回答报文叫做提供报文(DHCPOFFER)。客户计算机初始化IP的时候，首先要查找DHCP服务器，因此要发送的消息是DHCPDISCOVER，答案是A。36．网络由6个路由器互连而成，路由器之间的链路费用如下图所示，从PC机到服务器的最短路径和通路费用是()。A．1→3→6，7B．1→4→5→6，4C．1→4→3→6，6D．12→4→5→6，7正确答案：B解析：本题考查链路状态路由算法，将网络看成连通图。每条链路以其“费用”为权值。通过Dijkstra最短路径算法求出任意两个节点之间的最短距离，本题中，就是以PC机所连接的路由器1为根节点，计算到达其他网络的最短路径，也就是费用最小的路径，这样可以直接从选项中得出答案，是B。37．一个B类网络的子网掩码为255．255．252．0，则该B类网络的主机数目是()。A．2046B．1022C．510D．128正确答案：D解析：本题考查IPv4字网划分，首先明确B类网络的掩码是255．255．0．0，而192的二进制是11111100，由此可知可划分26＝64个子网，每个子网的主机数为22－2＝2，因此该B类网络的主机数目是64×2＝128，因此答案是D。38．在TCP报文段的报头中，窗口字段的作用是()。A．报头中32bit字节的数量B．说明对方端口的数量C．控制对方的发送流量D．说明网络的负荷能力正确答案：C解析：本题考查TCP报文段的作用窗口大小：用于流量控制。表示在确认了的字节之后还可以发送多少字节。窗口大小也允许为0，表示它已经收到了包括确认号减1在内的所有数据段，但接收方急需暂停接受数据。对于窗口字段，占2个字节，用来控制对方发送的数据量，并不能说明网络的负荷能力，因此答案是C。39．关于以太网交换机，下面的论述中不正确的是()。A．交换机工作在数据链路层B．交换机的每个端口形成一个冲突域C．交换机支持多端口同时收发数据D．交换机是一种多端口中继器正确答案：D解析：本题考查交换机的工作原理和特性，交换机是工作与数据链路层的网络设备，每个端口是独立的冲突域，交换机的交换结构保证了多端口同时进行数据交换，多端口的中继器可以认为是集线器，其所有端口处于同一个冲突域内，因此答案为D。40．一台主机要解析www．abc．edu．cn的IP地址，如果这台主机配置的域名服务器为202．120．66．68，因特网顶级域名服务器为11．2．8．6，而存储www．abc．edu．cn与其IP地址对应关系的域名服务器为202．113．16．10，那么这台主机解析该域名通常首先查询的服务器是()。A．202．120．66．68域名服务器B．11．2．8．6域名服务器C．202．113．16．10域名服务器D．不能确定，可从这三个域名服务器中任选一个正确答案：A解析：本题考查域名解析的过程，一个主机发出DNS查询报文时，这个查询报文首先被送往该主机的本地域名服务器。当本地域名服务器不能立即回答某个主机的查询时，该本地域名服务器就以DNS客户的身份向某一根域名服务器查询。若根域名服务器也没有该主机的信息时(但此时根域名服务器一定知道该主机的授权域名服务器的IP地址)，有两种做法：(1)递归查询：根域名服务器向该主机的授权域名服务器发送DNS查询报文，查询结果再逐级返回给原主机；(2)递归与迭代相结合的方法：根域名服务器把授权域名服务器的IP地址返回给本地域名服务器，由本地域名服务器再去查询。无论是递归方式，还是迭代方式，主机进行域名解析的第一步都是向自己的本地域名服务器发起请求，因此答案为A。综合应用题41-47小题，共70分。41．采用散列函数H(k)＝3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概率情况下查找成功的平均查找长度；(4)等概率情况下查找失败的平均查找长度。正确答案：(1)各关键字的散列函数值如下：(2)装填因子＝关键字总数／表长＝9／13≈0．7。(3)设查找成功在每个关键字上是等概率的，则查找每个关键字的概率为1／9，各关键字的探查次数分别为：所以有，ASLsucc＝(1＋1＋1＋2＋1＋2＋1＋1＋1)／9＝11／9。(4)设不成功的查找在每个地址上发生的概率相同，平均概率为1／13，对每个位置不成功查找的探查次数分别为：以散列地址在位置2的关键字为例，由于此处关键字为空，只需比较1次就可确定本次查找不成功；以散列地址在位置3的关键字为例，若该关键字不在散列表中，需要将它与从位置3开始向后直至位置5的关键字相比较，由于关键字5的关键字为空，所以不再向后比较，共比较3次，其他的类推得到。所以有，ASLunsucc＝(3＋2＋1＋3＋2＋1＋4＋3＋2＋1＋2＋1＋4)／13＝29／13。解析：用线性探测法解决冲突构造散列表，并对查找性能进行分析，具体解题步骤如上。42．假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。正确答案：voidLongpath(BiTreeb，TElemTypepath[]，intpathlen，TElemTypelongpath[]，intlongpathlen){inti；if(b＝＝NULL)(if(pathlen~longpathlen){／／若当前路径更长，将路径保存在longpath中for(i＝pathlen－1；i>＝0；i－－)longpath[i]＝path[i]；longpathlen＝pathlen；}}else{path[：pathlen]＝b－>data；／／将当前结点放入路径中pathlen＋＋；／／路径长度增lLongpath(b－>．Ichild．pat．h，pa七hlen，longpath，longpathlen)；／／递归扫描左子树Longpath(b－>rchild．pat．h，pathlen，longpath，longpathlen)；／／递归扫描右子树path]en－－；／／环境恢复}}解析：采用path数组保存扫描到当前结点的路径，pathlen保存扫描到当前结点的路径长度，longpath数组保存最长的路径，longpathlen保存最长路径长度。当b为空时，表示当前扫描的一个分支已扫描完毕，将pathlen与longpathlen进行比较，将较长路径及路径长度分别保存在longpath和longpathlen中。43．某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存储芯片都有与之相同的数据，分析故障原因。(4)如果运行时发现以0000H为起始地址的一片存储芯片不能读写，分析故障原因。(5)若发现译码器中的地址线A13与CPU断线，并搭接到低电平的故障，问后果如何?(6)如果发现只能对第l～4片RAM进行读写，试分析故障原因。正确答案：(1)选片译码逻辑如下图所示。(2)8片RAM的寻址范围分别是：0000H～1FFFH、2000H～3FFFH、4000H～5FFFH、6000H～7FFFH、8000H～9FFFH、A000H～BFFFH、C000H～DFfFH和E000H～FFFFH。(3)说明译码器有误，输出始终为低。因该输出接至第3片RAM的端，该片对应的地址范围是4000H～5FFFH，故不论往哪片RAM存放8K数据，该存储芯片始终被选中，所以都有与之相同的数据。(4)说明y0输出始终为高。因RAM的片选信号时低电平有效，故用作片选信号的存储芯片(对应0000H～1FFFH地址范围)不能读写，而其他芯片可以读写。(5)若发现A13与CPU断线，并搭接到低电平的故障，则信号均不可能输出0，故第2、4、6、8片RAM始终不被选中。(6)说明译码器的C输入端始终为低，可以检查一下A15是否搭接到低电平上。解析：(3)～(6)中出现的问题都是由于译码器连接上的问题(短路或断路)造成的，使得某些片选信号始终被选中或始终不被选中。[归纳总结]全译码法将除片内寻址外的全部高位地址线都作为地址译码器的输入，译码器的输出作为各芯片的片选信号，将它们分别接到存储芯片的片选端，以实现对存储芯片的选择。全译码法的优点是每片(或组)芯片的地址范围是唯一确定的，而且是连续的，也便于扩展，不会产生地址重叠的存储区。[解题技巧]首先确定片选电路以及各个芯片的地址分配，然后分析各种出错情况，分别找出出错的原因。44．某模型机的通路结构如下图所示，用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形式地址，分别位于指令的第2个和第3个存储字。(2)数据求反指令COM－(R0)，采用自减型寄存器间接寻址，结果送回自减后的地由E单元。正确答案：(1)MOVX(R0)，Y(R1)①PC→MAR，Read；取指令②M→MDR→IR③PC＋1→PC④PC→MAR，Read；取源操作数形式地址⑤M→MDR→C⑥PC＋1→PC⑦C＋R0→MAR，Read；形成源操作数有效地址，并取源操作数⑧M→MDR→C；源操作数暂存C中⑨PC→MAR，Read；取目的操作数形式地址⑩M→MDR→D⑩PC＋1→PC⑩D＋R1→MAR；形成目的操作数有效地址⑩C→MDR；将源操作数送存储器数据寄存器⑩MDR→M，write；将源操作数写入目的有效地址中(2)COM－(R0)①PC→MAR，Read；取指令②M→MDR→IR③PC＋l→PC④R0－1→R0，R0－1→MAR，Read；修改R0的内容(源和目的操作数地址)⑤M→MDR→D；取出源操作数⑥D→MDR；将源操作数取反⑦MDR→M，write；写入目的地址中解析：数据传送指令占3个字，第1个字是操作码和寄存器编号；第2个字是参数X，为源操作数的形式地址；第3个字是参数Y，为目的操作数的形式地址，源和目的操作数地址均采用变址寻址，指令的含义是：((R0)＋X)→(R1)＋Y。求反指令仅占1个字，自减型寄存器寻址是先修改寄存器的内容(－1)，再取数。[归纳总结](1)MOVX(R0)，Y(R1)指令执行流程中的前3步是完成取指令的操作公操作；接下来的5步是去主存中取源操作数，把取出的数放在暂存器C中；然后的4步是形成目的操作数地址；最后2步完成传送操作。(2)COM－(R0)指令执行流程中的前3步是取指令公操作；接下来的2步是去主存中取源操作数，把取出的数放在暂存器D中；然后将D的内容取反，写入目的地址中。[解题技巧]根据数据通路，写出指令执行的微操作序列。使用寄存器传送语句(如PC→MAR)，比较直观。45．某工厂有一个仓库可以存放甲、乙两种零部件，甲零件可以存放m件，乙零件可以存放n件，车间A专门生产甲零件，每次1件，每生产1件存放进仓库1件；车间B专门生产零件乙，每次1件，每生产1件存放进仓库1件。总装车间每次从仓库取出2件甲零件、l件乙零件组装成成品，车间A、B和总装车间必须互斥进入仓库。当仓库内甲、乙零件分别达到m、n件时，车间A、B分别停止生产。而仓库内任何一种零件为0时，总装车间停产。根据上述规则，请利用信号量机制，没计一个可以让车间A、B和总装车间协调运转的程序，并说明各个信号量的意义，用类c语言写出整个过程。正确答案：设信号量mutex用于车间的互斥，positionA、positionB和partA，partB为资源信号量，分别表示仓库中零件甲、乙的空位数和满位数，positionA＋partA＝m；positionB＋partB＝n；编程如下：deftypeintsemaphore；／／定义信号量semaphoremutex＝l；／／进入仓库的互斥信号量semaphorepositionA＝m，positionB＝n；／／车间A、B生产的零件甲、乙存放的位置semaphorepartA＝0，partB＝0；／／零件甲、乙的信号量voidworkshopA()／／车间A进程{while(TRUE)／／并发调度{intitem；／／仓库货架指针item＝produce(甲)；／／生产零件甲P(positionA)；／／查有无零件甲的货位P(mutex)；／／仓库可以进入吗?puton(item)；／／放置零件甲V(mutex)；／／释放仓库互斥量V(partA)；／／增加零件甲的资源信号量}／／离开}voidworkshopB()／／车间B进程{while(TRUE)／／并发调度{intitem；／／仓库货架指针item＝produce(乙)；／／生产零件乙P(positionB)；／／查有无零件乙的货位P(mutex)；／／仓库可以进入吗?puton(item)；／／放置零件乙V(mutex)；／／释放仓库互斥量V(partB)；／／增加零件乙的资源信号量)／／离开)voidassembleshop()／／总装车间进程{while(TRUE)／／并发调度{intiteml，item2；／／仓库货架指针P(partA)；／／查第一个零件甲是否有?P(partA)；／／查第二个零件甲是否有?P(partB)；／／查第一个零件乙是否有?