考研计算机学科专业基础综合-7-1

考研计算机学科专业基础综合-7-1（总分：139.96,做题时间：90分钟）一、{{B}}单项选择题{{/B}}（总题数:40,分数:80.00）.下列说法中，正确的是。I.假设某有序表的长度为n,则可以在1〜（n+1）的位置上插入元素.在单链表中，无论是插入还是删除操作，都必须找到其前驱结点.删除双链表的中间某个结点时，只需修改两个指针域.将两个各有n和m个元素的有序表（递增）归并成一个有序表，仍保持其递增有序，则最少的比较次数是m+n-1。A.仅i、n、mB.i、n、m、ivc.仅n、md.仅i、m、v（分数：2.00）V解析：［解析］I：有序表插入的时候是不能指定位置的，因为这样可能使得插入后的表不再是有序表。正确的插入思想是：先通过元素比较找到插入的位置，再在该位置上插入，故I错误。II：从单链表插入和删除的语句描述中可以看出，无论是插入还是删除操作，都必须找到其前驱结点，故I正确。m：删除双链表中间某个结点时，需要修改前后两个结点的各一个指针域，共计两个指针域，故m正确。V：当一个较短的有序表中所有元素均小于另一个较长的有序表中所有的元素，所需比较次数最少。假如一个有序表为1、3、4,另一个有序表为5、6、7、8、12,这样只需比较3次即可，故答案应该是n和m中较小者，即min（n,m）,故V错误。2.下列关于栈的说法中，正确的是。I.若进栈顺序为a、b、c,则通过出栈操作可能得到5个a、b、c的不同排列II•链式栈的栈顶指针一定指向栈的链尾m.两个栈共享一个向量空间的好处是减少了存取时间A.仅IB.仅I、IIC.仅Id.仅n、m（分数：2.00）V解析：［解析］I：该选项旨在让考生知道一个公式。对于n个不同元素进栈，出栈序列的个数为［*］可以马上得出，当n=3时，出栈序列个数为［*］故I正确。II：链式栈一般采用单链表，栈顶指针即为链头指针。进栈和出栈均在链头进行，每次都要修改栈项指针，链空即栈空(top==NULL),故H错误。III：由于栈中数据的操作只有入栈和出栈，且时间复杂度均为0(1),因此并没有减少存取时间，故I错误。两个栈共享一个数组A［0...MaxSize-1］的空间，从而构成共享栈。数组A的两端是固定的，而栈底也是固定的，为此将下标为0的一端作为栈1的栈底，其栈顶指针为topi,将下标为MaxSize-1的一端作为栈2的栈底，其栈顶指针为top2,如图所示。［*］栈1的四要素如下：①栈空条件：top1==-1。②栈满条件：top1==top2-1。③元素x进栈:top1++；将元素x插入A［top1］处。④出栈元素：弹出A［top1］元素;top1--。栈2的四要素如下：①栈空条件：top2==MaxSize。②栈满条件：top2==top1+1。③元素x进栈：top2--；将元素x插入A［top2］处。④出栈元素：弹出A［top2］元素；top2++。注：以上都默认指针指向当前元素的下一个位置。3.若将n阶上三角矩阵A按照列优先顺序存放在一维数组B［0,1,…，{nX(n+1)/2}-1］中，第一个非零元素a(1,1)存于B［0］中，则存放到B［k］中的非零元素a(i,j)(1WiWn,1WjWn)的下标i、j与k的对应关系是。A.k=iX(i+1)/2+jB.k=iX(i-1)/2+j-1C.k=jX(j+1)/2+iD.k=jX(j-1)/2+i-1(分数：2.00)V解析：［解析］对于元素a(i,j)而言，前面有j-1歹U，第1列到第j-1列的元素个数分别为1〜j-1个，由等差数列求和公式可算得一共有j*(j-1)/2个元素，故k=jX(j-1)/2+i-1(注意B数组是从0开始存元素，因此要减去1)。4.已知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为。先序：A_CDEF_H_J中序：C_EDA_GFI后序：C__BHGJI__A.CBEDAHGFIJB.CHEDABGFIJC.CBEDAJGFIHD.CJEDAHGFIB(分数：2.00)V解析：［解析］对于一棵二叉树(包括子树)，它的遍历序列对应的结构应该是：先序遍历：|根|左子树|右子树I,中序遍历：|左子树|根|右子树1,后序遍历：|左子树|右子树|根|,由题目中给出的先序序列的第一个结点我们找到树的根A,然后在中序序列中找到A,并以A为分界将中序序列划分为|C_ED|A|_GFI_1,所以C_ED为左子树，_GFI_为右子树，再对应到后序遍历序列上，这里左子树结点的个数等于中序遍历序列中左子树结点的个数，因此C__B为左子树，HGJI_为右子树，这样把中序序列和后续序列中的左右子树一对比，则C{{U}}B{{/U}}ED为左子树，F{{U}}G{{/U}}H{{U}}I{{/U}}J为右子树。答案选A。5.设某赫夫曼树的高度为5,若已对两个字符编码为1和01,则最多还可以对个字符编码。TOC\o"1-5"\h\zA.3B.4C.5D.6（分数：2.00）V解析：［解析］首先，赫夫曼编码遵循的原则为：一个编码不能是任何其他编码的前缀。比如1和10就不行，因为1是10的前缀。既然1和01已经使用了，所以1和01开头的码字不能再使用。又由于赫夫曼树的高度为5,故赫夫曼编码的长度不能超过4,只剩下0000、0001、0010、0011等4种编码（这种编码方式可得到最多），故选B选项。6.下列说法中，正确的是。I.在含有n个顶点e条边的无向图的邻接矩阵中，零元素的个数为n2-2e.若邻接表中有奇数个边表结点，则该图一定是有向图.对于采用邻接表存储的图，其深度优先遍历算法类似于二叉树的中序遍历.使用队列实现广度优先遍历算法，则每个顶点进队列的次数可能大于1a.仅i、mb.仅n、m、ivC.仅I、II、IVD.仅I、II（分数：2.00）V解析：［解析］I：总结如下：①对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是m。②在含有n个顶点e条边的无向图的邻接矩阵中，非零元素的个数为2e。③在含有n个顶点e条边的无向图的邻接矩阵中，零元素的个数为m-2e。④在含有n个顶点e条边的有向图的邻接矩阵中，非零元素的个数为e。⑤在含有n个顶点e条边的有向图的邻接矩阵中，零元素的个数为m-e。根据⑧，故I正确。II：无向图采用邻接表表示时，每条边存储两次，所以其边表结点个数为偶数，故边表结点为奇数只能是有向图，故I正确。I：深度优先遍历算法是先访问一个顶点v,然后是离开顶点越远越优先访问，即相当于二叉树的先序遍历，故m错误。V：采用广度优先遍历算法遍历一个图时，每个顶点仅遍历一次，所以最多只能进队1次，故V错误。7.下列关于生成树的说法中，正确的是。A.最小生成树是指权值之和为最小的生成树，且唯一B.某图的广度优先生成树的高度一定大于等于深度优先生成树的高度C.Prime算法和Kruskual算法构造的最小生成树一定一样D.Prime算法适用于求边稠密的图的最小生成树(分数：2.00)V解析：［解析］A：最小生成树是指权值之和为最小的生成树，但是不唯一，故A选项错误。B：由广度优先遍历和深度优先遍历算法可知，深度优先算法构造的生成树的树高大于等于广度优先算法构造的生成树的树高，故B选项错误。C：当最小生成树不唯一时，这两种算法构造的最小生成树可能相同，也可能不同，故C选项错误。D：Prime算法的时间复杂度为O(m),适合稠密图；Kruskual算法的时间复杂度为O(eloge),适合稀疏图，2故D选项正确。8.下列关于m阶B+树的说法中，正确的是。I.具有n个关键字的结点至少含有n+l棵子树所有叶子结点包含全部关键字B+树支持随机索引B+树可用于文件的索引结构a.仅m、ivb.仅n、ivc.仅i、m、ivD.仅I、II、IV(分数：2.00)V解析：［解析］一棵m阶B+树满足下列条件：①每个分支结点至多有m棵子树。②根结点或者没有子树，或者至少有两棵子树。③除根结点外，其他每个分支结点至少有［*］棵子树。④具有n个关键字的结点含有n棵子树。⑤所有叶子结点包含全部关键字及指向相应记录的指针，而且叶子结点按关键字的大小顺序链接。⑥所有分支结点中仅包含它的各个子结点中最大关键字及指向子结点的指针。⑦B+树中，所有非终端结点可以看成是索引部分，故可用于文件的索引结构。由于B+树为链式存储结构，所以不支持随机检索。综上所述，可知n、iv正确，i、m错误，故选B选项。9.利用逐点插入建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后，要查找元素30要进行次元素间的比较。TOC\o"1-5"\h\zA.4B.5C.6D.7(分数：2.00)V

C.D.解析：［解析］由题可以建立出如图所示的一棵二叉排序树。［*］查找元素30一次经过比较的元素为50,43,20，35,30，共有5次元素间的比较，因此本题选B选项。10.用直接插入排序对下面4个序列进行递增排序，元素比较次数最少的是。A.94,32,40，90，80，46,21，69B.32，40，21，46,69，94，90，80C.21，32，46，40，80，69，90，94D.90，69，80，46，21，32，94，40A.94,32,40，90，80，46,21，69B.32，40，21，46,69，94，90，80C.21，32，46，40，80，69，90，94D.90，69，80，46，21，32，94，40（分数：2.00）V解析：［解析］对于直接插入排序，原始序列越接近有序，则比较次数越少，观察序列，C选项最接近有序。说明：本题目测即可，如果要严格来比较，则可用线性代数中求逆序数的方法，序列逆序数越小则越接近有序。对于序列中某个元素a,其逆序数为序列中a之后比a小的元素的个数，整个序列的逆序数为所有元素逆序数之和。对于A,各元素逆序数为：94:7；32:1；40:1；90:4；80:3；46:1；21:0；69:0。因此序列A的逆序数为：7+1+1+4+3+1+0+0=17。对于B,各元素逆序数为:32:1；40:1；21:0；46:0；69:0；94:2；90:1；80:0。因此序列A的逆序数为：1+l+0+0+0+2+1+0=5。对于C,各元素逆序数为：21:0；32:0；46:1；40:0；80:1；69:0；90:0；94:0。因此序列A的逆序数为：0+0+1+0+1+0+0+0=2。对于D,各元素逆序数为：90:6；69:4；80:4；46:3；21:0；32:0；94:0；40:0。因此序列A的逆序数为：6+4+4+3+0+0+0+0=17。可以看出C选项逆序数最小，即C选项最接近有序，所需比较次数最少。11.在外部排序算法中，最佳归并树主要的作用是。A.产生初始归并段B.完成归并排序C.对归并排序进行优化D.增大归并路树（分数：2.00）V解析：［解析］A：产生初始归并段的工作应该由置换-选择排序完成，故A选项错误。设输入的关键字满足匕〉人〉…〉kn,缓冲区大小为m,用置换-选择排序方法可产生困个初始归并段。B：因为最佳归并树是针对排序之后1的初始归并段操作，所以归并排序不可能由最佳归并树完成，故B选项错误。C：最佳归并树仿造赫夫曼树的构造过程，以初始归并段的长度为权值，构造具有最小带权路径长度的赫夫曼树，可以有效地减少归并过程中的读写记录数，以加快外部排序的速度，故C选项正确。D：增大归并路数应该是由败者树来完成的，故D选项错误。12.下列说法中，错误的是。I.时钟频率和CPI成反比关系II.数据字长等于MDR的位数A主机的CPU主频高于B主机的CPU主频，则前者运算能力将会高于后者A.仅I、IIb.仅n、mc.仅i、mD.i、n、m(分数：2.00)A.V解析：［解析］I：时钟频率和CPI并无关系。时钟频率的提高仅仅是将时钟周期缩短，并没有改变执行一条指令所需要的时钟周期数，故I错误。II：一般来讲，M=DR的位数和存储字长相等，而数据字长是一次存取数据的长度，可以和M=DR不相等，故I错误。I：CPU的主频是表示在CPU内数字脉冲信号震荡的次数，是衡量CPU运算速度的重要参数，但不是唯一的参数。故不能直接根据主频来比较运算能力，故m错误。13.假定采用IEEE754单精度浮点数格式表示一个数为45100000H,则该数的值是。A.(+1.125)X210B.(+1.125)X2iiC.(+0.125)X2iiD.(+O.125)X2i0(分数：2.00)V解析：［解析］45i00000H的二进制数为0i000i0i000i00000000000000000000,第i位为符号位，表示正数，随后8位i000i0i0为用移码表示的阶码，减去i27得到十进制数ii,而IEEE754中单精度数在阶码不为0时隐含i,所以尾数为(i.00i0)2=i.i25。i4.一个8位的二进制整数，若采用补码表示，且由3个“1”和5个“0”组成，则最小值为。A.-i27B.-32C.-125D.-3(分数：2.00)A.Vd.解析：［解析］8位补码最小时必为负数，所以第一位（符号位）必须为1。而负数的数值位绝对值越大，则此负数越小。又负数的补码表示的高位0相当于原码表示的1，故当剩下的2个“1”在最低位，5个“0”在数值位的最高位时此负数最小。该负数的补码为10000011，则原码为11111101，转换成十进制为-125。15.一台8位微机的地址总线为16条，其RAM存储器容量为32KB，首地址为4000H，且地址是连续的，可用的最高地址为。A.BFFFHB.CFFFHC.DFFFHD.EFFFH（分数：2.00）V解析：［解析］32KB存储空间共占用15条地址线，若32KB的存储地址起始单元为0000H，其范围应为0000〜7FFFH,但现在的首地址为4000H，即首地址后移了，因此最高地址也应该相应后移。故最高地址为4000H+7FFFH=BFFFH。32KB的存储空间是连续的，由于首地址发生变化，末地址也会跟着发生变化。16.有效容量为128KB的Cache,每块16B,8路组相联。字节地址为1234567H的单元调入该Cache,其Tag应为。A.1234HB.2468HC.048DHD.12345H（分数：2.00）V解析：［解析］因为块的大小为16B,所以块内地址字段为4位；又因为Cache容量为128KB,8路组相联，所以可以分为1024组（128KB/（8x16B）=1024）,对应的组号字段10位；剩下为标记字段。1234567H=0001001000110100010101100111,标记字段为高14位，00010010001101=048DH,故选C选项。17.在单发射、按序流动的普通流水线中，可能出现下列数据相关问题。I.写后读相关RAWII.读后写相关WARIII.写后写相关WAWA.仅IB.仅I、IIC.仅Id.仅n、m（分数：2.00）A.VB.C.D.解析：［解析］指令取操作数的动作一定在写回结果之前，故在按序流动的单发射（普通标量）普通流水线中，先进入流水线的指令的取操作数和写回结果的动作一定位于后续指令写回结果的动作之前，故不可能出现WAR和WAW。唯一可能出现的数据相关问题是后续指令在前一指令写回结果之前读相关的操作数，即RAW。18.在按字节编址的计算机中，一条指令长16位，当前分支转移指令（采用相对寻址）地址为3000，指令地址的偏移量为-5,当执行完此转移指令后，PC的值为。A.2996B.2997C.3001D.3002（分数：2.00）V解析：［解析］首先给出解答步骤，当前指令地址为3000,取完这条指令后，PC的值增加一个指令字长度，即3002,加上偏移量-5,所以执行完这条指令后，目标地址为2997,然后将这个值覆盖到PC当中。19.以下给出的事件中，无须异常处理程序进行中断处理的是。A.缺页故障B.访问Cache缺失C.地址越界D.除数为0（分数：2.00）V解析：［解析］缺页会导致缺页中断，缺页中断就是要访问的页不在主存，现行程序无法往下走，需要操作系统采用缺页处理程序将其调入主存后再进行访问；地址越界就是在采取地址访问时，由于不注意，你访问的地址超过了所允许访问的地址空间，这种操作肯定会导致结果错误，所以是非法操作，产生异常；除数为0这是不合法的，因此要终止现行程序，产生异常;而访问Cache缺失仅仅是说要访问的内容不在Cache而已，但程序至少还可以继续进行下去（比如程序可以到主存中去找需要的内容）。所以答案为B。20.假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600X1200,颜色深度为24位，帧频为85Hz,显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为。A.245Mbit/sB.979Mbit/sC.1958Mbit/sD.7834Mbit/s（分数：2.00）A.V解析：［解析］首先一帧画面的大小为1600X1200X24bit,又因为帧频为85Hz,即每秒要刷新画面85次，因此每秒需要更新的容量为46080000bitX85=3916800000bit,占显存总带宽的50%,显存的带宽至少约为3916.8Mbit/sX2=7834Mbit/so21.总线宽度只与下列选项有关。I.控制线根数II.地址线根数III.数据线根数A.仅Ib.仅n、mc.仅mD.i、n、m（分数：2.00）V解析：［解析］总线宽度又称为总线位宽，它是总线上能够同时传输的数据位数，通常是指数据总线的根数。22.在主机和外设的信息传送中，没有使用程序控制方式。A.程序查询方式B.程序中断方式C.DMA方式D.通道方式（分数：2.00）V解析：［解析］程序查询方式和程序中断方式显然是需要程序的干预，而通道方式也是要编制通道程序来控制，只有DMA方式是靠硬件电路实现的。23.下列关于操作系统结构说法中，正确的是oI.当前广泛使用的WindowsXP操作系统，采用的是分层式OS结构II.模块化的OS结构设计的基本原则是：每一层都仅使用其底层所提供的功能和服务，这样使系统的调试和验证都变得容易m.由于微内核结构能有效支持多处理机运行，故非常合适于分布式系统环境IV.采用微内核结构设计和实现操作系统具有诸多好处，如添加系统服务时，不必修改内核、使系统更高效等A.仅I、IIb.仅i、mc.仅md.仅m、iv(分数：2.00)V解析：［解析］I错误，当前比较流行的、能支持多处理机运行的OS,几乎全部都采用微内核结构，包括WindowsXPOII错误，模块化OS结构原则是：分解和模块化。II中描述的是分层式结构设计的基本原则。III正确。IV错误，微内核结构将操作系统的很多服务移动到内核以外(如文件系统)。且服务之间使用进程间通信机制进行信息交换，这种通过进程间通信机制进行信息交换影响了系统的效率，所以微内核结构设计并不会使系统更高效。由于内核的内服务变少了，且一般来说内核的服务越少肯定越稳定。24.在有一个CPU和两台外设D1和D2,且能够实现抢占式优先级调度算法的多道程序环境中，同时进入优先级由高到低的P1,P2,P3的3个作业，每个作业的处理程序和使用资源的时间如下：P1：D2(30ms),CPU(10ms),D1(30ms),CPU(10ms)P2：D1(20ms),CPU(20ms),D2(40ms)P3：CPU(30ms),D1(20ms)假设对于其他辅助操作时间忽略不计，CPU的利用率是。A.47.8%B.57.8%C.67.8%D.77.8%(分数：2.00)V解析：［解析］抢占式优先级调度算法，3个作业执行的顺序如图所示。(还可以有一种画法，即按照进程来考虑，纵坐标为P1、P2、P3。)［ A.4、8、11• B.4、6• C.6、8• D.4 A.4、8、11• B.4、6• C.6、8• D.4、8.设有如下两个优先级相同的进程P1和P2。信号量S1和S2的初值均为0,试问P1、P2并发执行结束后，z的值可能是。进程P1：V=j；z=2；V(S1)；z=y+1；P(S2)；y=z+y；进程P2：x=2；P(S1)；x=x+2；V(S2)；z=x+z；（分数：2.00）A.B.C.D.V解析：［解析］这类题目其实不难，但这种题却很容易答错，原因就是很容易漏掉某种情况。首先，将上述进程分解成以下6个程序段：PS3：y=z+y；PS1：y=3；PS2：z=y+1；PS3：y=z+y；z=2；PS4：x=2；PS5：x=x+2；PS6：z=x+z；假设没有PV操作的情况下。进程并发执行关系用前驱图表示如图1所示。加入了PV操作后用前驱图表示如图2所示。由于x的值只有PS4、PS5决定，且两者顺序关系确定，则易得x的值始终为4。又P2和P1共享的变量只有z,则PS6与PS1、PS2、PS3的关系决定了最终的y和z的值。又根据进程前驱图得，PS6在PS1之后。所以可能的情况有（PS4、PS5所处的顺序有多种情况，但都不对最后结果产生影响，为了方便，我们统一把PS4、PS5放在PS1后面执行）：PS1、PS4、PS5、PS6、PS2、PS3：PS1、PS4、PS5、PS2、PS6、PS3：PS1、PS4、PS5、PS2、PS3、PS6：这3种情况，计算过程如下表所示。困图1进程并发执行关系的前驱图

困图2加入PV操作后的前驱图{{B}}计算过程{{/B}}xyzxyzxyzPS132PS132PS132PS42PS42PS42PS54PS54PS54PS66PS24PS24PS24PS68PS37PS37PS311PS684744118478综上所述，z的值可能是4、8。.系统的资源分配图在下列情况中，无法判断是否处于死锁的情况是I.出现了环路II.没有环路.每种资源只有一个，并出现环路IV.每个进程结点至少有一条请求边A.i、n、m、ivb.仅i、mi、ivC.仅I、IVd.都能判断（分数：2.00）A.B.D.解析：［解析］首先要注意，本题的问法比较拗口，是无法判断的情况，不可理解错误。本题的难点主要在于区分资源分配图中的环路和系统状态的环路有什么关系。资源分配图中的环路通过分配资源，是可以消除的，即消边。而系统状态图中的环路其实就是死锁。两者的关系其实可以理解为资源分配图通过简化（消边）后就是系统状态图。如果资源分配图中不存在环路，则系统状态图无环路，则无死锁；故n确定不会发生死锁。反之，如果资源分配图中存在环路，经过简化（消边）后，则系统状态图中可能存在环路，也可能不存在环路。根据资源分配图算法，如果每一种资源类型只有一个实例且出现环路，那么无法简化（消边），死锁发生，故m可以确定死锁发生。剩下I和iv都不能确定，因为它们的资源分配图中虽然存在环路，但是不能确定是否可以简化成无环路的系统状态图。所以本题选c选项。27.下列存储管理方式中，会产生内部碎片的是。I.分段虚拟存储管理n.分页虚拟存储管理m.段页式分区管理iv.固定式分区管理a.仅i、n、mb.仅m、ivc.仅nd.仅n、m、iv（分数：2.00）V解析：［解析］只要是固定的分配就会产生内部碎片，其余的都会产生外部碎片。如果固定和不固定同时存在（例如段页式），物理本质还是固定的，解释如下：分段虚拟存储管理：每一段的长度都不一样（对应不固定），所以会产生外部碎片。分页虚拟存储管理：每一页的长度都一样（对应固定），所以会产生内部碎片。段页式分区管理：地址空间首先被分成若干个逻辑分段（这里的分段只是逻辑上的，而我们所说的碎片都是物理上的真实存在的，所以是否有碎片还是要看每个段的存储方式，所以页才是物理单位），每段都有自己的段号，然后再将每个段分成若干个固定的页。所以其仍然是固定分配，会产生内部碎片。固定式分区管理：很明显固定，会产生内部碎片。综上分析，本题选D选项。28.下列程序设计技术和数据结构中，适合虚拟页式存储系统的有。I.堆栈II.Hash函数索引的符号表III.顺序搜索IV.二分法查找V.纯代码W.矢量操作加.间接寻址血.矩阵操作A.i、m、v、w、加B.i、n、m、如c.n、v、w、加D.m、v、w、如（分数：2.00）V解析：［解析］虚拟分页存储系统中，页内地址是连续的，而页问地址不连续。当页面不在内存时，会引起缺页中断，相对消耗很多的时间。这类题解题思路起始都是应该从局部性出发。I适合。栈顶操作一般是在当前页中进行，此前已驻留内存。只有当栈顶跨页面时，才会引起缺页中断。II不适合。Hash函数产生的索引地址是随机的，可能会频繁缺页。III适合。搜索一般是在当前页中进行，此前已驻留内存。只有当跨页面搜索时，才会引起缺页中断。IV不适合。二分法查找是跳跃式的，可能会频繁缺页。V适合。纯代码基本上是顺序执行的。其跳转指令全是相对跳转的，范围一般在一个页面之内。只有当跨页面跳转时，才会引起缺页中断。W适合。一个矢量的各分量均顺序排列，一般在同一页面内。如不适合。存放间接地址的页面，存放直接地址的页面，以及存放内容的页面没有规律，它们可能不在同一个页面。而适合。矩阵的各元素均顺序排列，一般在同一页面内。29.下面关于文件的叙述中，错误的是。I.打开文件的主要操作是把指定文件复制到内存指定的区域II.对一个文件的访问，常由用户访问权限和用户优先级共同限制I.文件系统采用树形目录结构后，对于不同用户的文件，其文件名应该不同V.为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件A.仅Ib.仅i、mc.仅i、m、ivD.i、n、m、iv（分数：2.00）A.V解析：［解析］I错误，系统调用open把文件的信息目录放到打开文件表中。II错误，对一个文件的访问，常由用户访问权限和文件属性共同限制。m错误，文件系统采用树形目录结构后，对于不同用户的文件，其文件名可以不同，也可以相同。V错误，常采用备份的方法保护文件。而存取控制矩阵的方法是用于多用户之间的存取权限保护。30.在PC-DOS中，某磁盘文件A与B,它们所占用的磁盘空间如下所示。试问A、B文件在磁盘上各占簇。{{B}}表1FDT（文件目录表）{{加}}……A002B003……{{B}}表2FAT（文件配置表）{{/B}}簇号FAT值000FFD001FFF002004003008004009005007006FFF007FFF008006009005……TOC\o"1-5"\h\zA.3, 3B.4, 5C.5, 3D.5, 4（分数：2.00）A.VD.解析：［解析］当查找文件在磁盘上的存放地址时，首先从目录中找到文件的起始簇号，然后再到FIAT表的相应表目中找到文件存放的下一个簇号，依此类推，直至遇到值为FFF的表项为止。文件A在磁盘上占用5簇，簇号依次为002、004、009、005、007。文件B在磁盘上占用3簇，簇号依此为003、008、006。31.某磁盘盘组共有10个盘面，每个盘面上有100个磁道，每个磁道有32个扇区，假定物理块的大小为2个扇区，分配以物理块为单位。若使用位图（bitmap）管理磁盘空间，则位图需要占用的空间大小是。A.2000BB.12000BC.6000BD.16000B（分数：2.00）VC.D.解析：［解析］已知磁盘盘组共有10个盘面，每个盘面上有100个磁道，每个磁道有32个扇区，则一共有10X100X32=32000个扇区。题目又假定物理块的大小为2个扇区，分配以物理块为单位，即一共有16000个物理块。因此，位图所占的空间为16000/8B=2000B。32.关于SPOOLing技术的说法，以下正确的是。SPOOLing系统中不需要独占设备SPOOLing系统加快了作业完成的速度III.当输入设备忙时，SPOOLing系统中的用户程序暂停执行，待I/O空闲时再被唤醒执行输出操作IV.在采用SPOOLing技术的系统中，用户的打印结果首先被送到内存固定区域A.仅I、IIB.仅Ic.仅n、md.仅m、iv（分数：2.00）V解析：［解析］I错误，SPOOLing技术是将独占设备改为共享设备，所以肯定需要独占设备。II正确，SPOOLing技术通过在磁盘上开辟存储空间模拟月兑机输出，可以减少作业输出等待时间，加快作业完成的速度。III错误，引入SPOOLing技术的目的就是在输入设备忙时，进程不必等待I/O操作的完成。IV错误，在SPOOLing系统中，用户的输出数据先送入输出井，即磁盘固定区域。综上分析，本题选B选项。A.5个冲突域，1个广播域B.3个冲突域，3个广播域C.4个冲突域，2个广播域D.6个冲突域，2个广播域（分数：2.00）V解析：［解析］通常普通的集线器是一种工作在物理层，具有“共享冲突域、共享广播域”特性的网络互连设务。而将交换机和网桥称为二层设备，它是一种工作在数据链路层，具有“隔离冲突域、共享广播域”特性的网络互连设备。可见，交换机只能缩小冲突域，而不能缩小广播域。将路由器称为三层设备，它是一种工作在网络层，具有“隔离冲突域、隔离广播域”功能的网络互连设备。在Internet等主干网上，路由器的主要作用是路由选择。由以上分析可知，题图所示的拓扑结构中共有4个冲突域，2个广播域，具体如下图所示。困其中，冲突域1和冲突域2属于同一个广播域，冲突域3和冲突域4属于另外一个广播域。总结（见下表）：TOC\o"1-5"\h\z{{B}}各设备的冲突域与广播域{{/B}}设备名称隔离冲突域隔离广播域集线器 X X中继器 X X交换机 V X网桥 V X路由器 V V34.长度为1km,数据传输率为10Mbit/s以太网，电信号在网上的传播速度是200m/〃s。假设以太网数据帧的长度为256bit,其中包括64bit帧头、检验和及其他开销。数据帧发送成功后的第一个时间片保留给接收方，用于发送一个64bit的确认帧。假设网络负载非常轻（即不考虑冲突的任何情形），则该以太网的有效数据传输速率为。A.4.21Mbit/sB.11.7Mbit/sC.6.09Mbit/sD.5.19Mbit/s(分数：2.00)V解析：［解析］(1)发送256bit数据帧所用的发送时间=256bit/10Mbit/s=25.6ps；(2)数据帧在电缆线上的传播时间=1000m/(200m/ps)=5ps；(3)发送64bit的确认帧所用的发送时间=64bit/10Mbit/s=6.4ps：(4)确认帧在电缆上的传播时间=1000m/(200m/ps)=5ps； (5)为了保证冲突检测机制能够正常进行，64位确认帧要进行填充，使得其传输时延等于往返传播时延10Ps；有效数据传输率=发送的有效数据/发送有效数据所用的总时间，而有效数据=(256-64)bit=192bit,发送192bit的有效数据所占用的总时间=(25.6+5+6.4+5)ps=45.6ps；则该以太网的有效数据传输率为192bit/42ps=4.21Mbiffs。35.下面技术无法使10Mbit/s的以太网升级到100Mbit/s的是。A.帧长保持不变，网络跨距增加B.采用帧扩展技术C.传输介质使用高速光纤D.使用以太网交换机，引入全双工流量控制协议(分数：2.00)V解析：［解析］CSMA/CD协议要求每帧的发送时间不小于信号的往返时延。如果电缆线长度增加，传播时延增加，冲突检测时间增加，帧长保持不变，则发送速率应减少，A错。帧扩展技术解决了网络跨距问题，但可能影响短帧的传输性能，在千兆以太网标准中增加了帧突发技术，提高了网络带宽利用率，B对。高速光纤的使用大大提高了网络的传输速率，使10Mbit/s升级到100Mbit/s和1Gbit/s成为可能，C对。全双工的以太网交换机不执行CSMA/CD协议，每帧的发送时间不受往返时延影响，D对。36.某端口的IP地址为172.16.7.131/26,则该IP地址所在网络的广播地址是。A.172.16.7.255B.172.16.7.129C.172.16.7.191D.172.16.7.252(分数：2.00)V解析：［解析］首先要清楚广播地址就是将主机位全部置为1,/26表示前3个字节都是网络段，最后一个字节的头两位也是网络段。前3个字节忽略，只解释最后一个字节。将131以二进制表示为10000011。根据广播地址的定义，主机段全1即为广播地址，即10111111,转换为十进制为191,故广播地址为172.16.7.191。37.下列关于ARP的说法中，错误的是。ARP的请求报文是单播的ARP的响应报文是单播的III.如果局域网A的主机1想和局域网B的主机2通信，但是主机1不知道主机2的物理地址，主机1通过发送ARP报文就可以解决A.仅IB.仅Ic.仅i、md.仅n、m（分数：2.00）V解析：［解析］I：当主机A要向本局域网上的某个主机B发送IP数据报时，如果在其ARP高速缓存中查询不到主机B的物理地址，这时候ARP进程就需要在本局域网上广播发送一个ARP请求分组，所以ARP的请求报文是广播的，不是单播的，故I错误。II：接着上面的论述，此时应该是本局域网上的所有主机都可以收到此ARP的请求分组，而主机B见到ARP分组中的IP地址是自己的IP时，就向主机A发送一个ARP响应分组，所以ARP响应分组是普通的单播，故I正确。I：这个一定要注意了，很多考生都误认为是正确的。记住一句话：ARP是解决同一局域网上的主机或路由器的IP地址和硬件地址的映射问题，如果所要找的主机和源主机不在同一个局域网上，剩下的所有工作都应该由下一跳的路由器来完成，故m错误。注：ARP数据单元是被封装在以太帧中。38.一个网段的网络号为198.90.10.0/27,子网掩码固定为255.255.255.224,最多可以分成个子块，而每个子块最多具有个有效的IP地址。A.8,30B.6,30C.16,14D.32,6（分数：2.00）V解析：［解析］/27是引入无类别域间路由选择（CIDR）后子网IP地址的表示方法，对应的子网掩码表示是255.255.255.224。地址的最后1个字节中有3位属于子网号部分（物理网络号共27位），主机号只有5位。198.90.10.0是C类地址，网络号24位，最后1个字节中的子网号3位，最多可以分成8个子块，主机号部分5位共32个地址，除了全1和全0,有30个有效的IP地址。39.A和B建立TCP连接，MSS为1KB。某时，慢开始门限值为2KB,A的拥塞窗口为4KB,在接下来的一个RTT内，A向B发送了4KB的数据（TCP的数据部分），并且得到了B的确认，确认报文中的窗口字段的值为2KB,那么，请问在下一个RTT中，A最多能向B发送数据。A.2KBB.4KBC.5KBD.8KB（分数：2.00）V解析：［解析］首先，发送窗口应该在拥塞窗口和接收窗口中取最小值，所以本题关键点在于求本RTT内拥塞窗口和接收窗口的大小。在接下来的一个RTT内，A向B发送了4KB的数据，且此时拥塞窗口为4KB,按照拥塞避免算法（因为此时拥塞窗口大于慢开始门限值，所以采用拥塞避免算法），收到B的确认报文后，拥塞窗口增加到5KB。另外，B发给A的确认报文中的窗口字段的值为2KB,故此时接收窗口的大小为2KB,所以在下一个RTT中，A最多能向B发送2KB数据。40.在进行域名解析的过程中，由获取的解析结果耗时最短。A.主域名服务器B.辅域名服务器C.缓存域名服务器D.转发域名服务器（分数：2.00）V解析：［解析］缓存域名服务器是一种很特殊的DNS服务器，它本身并不管理任何区域，但是DNS客户端仍然可以向它请求查询。缓存域名服务器类似于代理服务器，它没有自己的域名数据库，而是将所有查询转发到其他DNS服务器处理。当缓存域名服务器从其他DNS服务器收到查询结果后，除了返回给客户端外，还会将结果保存在缓存中。当下一个DNS客户端再查询相同的域名数据时，就可以从高速缓存里得到结果，从而加快对DNS客户端的响应速度。二、{{B}}综合应用题{{/B}}（总题数:6,分数:60.00）已知由n-1个关键字组成的序列（K1,',•••,KJ是大顶堆，现在增加一个关键字Kn,要求将关键字序列（K/\,•••,'/Kn）,重新调整为大顶堆。请完成以下要求：（分数：12.99）.给出算法的基本设计思想。（分数：4.33）正确答案：（基本设计思想：从根结点的父母结点的标号［n/2］开始向上，对每个当前结点和左右子树进行调整。最开始的时候要判断n是左结点还是右结点，之后的情况一定是左右结点都有。每次把当前结点的标号除以2则得到当前结点的父母结点的标号。）解析：.根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。（分数：4.33）正确答案：（算法实现如下：#definen100;//宏定义n常量，由用户自定义结点个数intK［n］;//关键字序列Voidheap(){inti=n/2;〃找到最后一个结点的父母结点if(n%2==1)〃当n是右结点时{if(K[i]<K[n-1]&&K[n-1]〉K[n])swap(K[nT],K[i]);//swap()实现交换两个元素if(K[i]<K[n]图2独占查询方式下的I/O过程)解析：正确答案：（图2独占查询方式下的I/O过程)解析：正确答案：（外层磁道的长度为2nR=2X3.14X15.5cm=97.34cm每道信息量=600bit/cmX97.34cm=58404bit=7300.5B磁盘总容量=7300.5BX1320道=9636660B（非格式化容量）磁盘在使用之前要对其执行格式化操作，要首先完成划分磁道和扇区，设置文件目录区等。非格式化容量是指一个盘片上可以记录的二进制位的总数量，而格式化容量通常是指用户可用空间的二进制位的总数量，前者比后者要大，因为系统要管理磁盘会占用一定的存储空间，还要使用一个磁道用于同步，扇区之间还有间隔和一些为保存检错纠错信息的空间，磁盘上往往还会留有一些备份磁道。在谈到磁盘容量时，通常指的是格式化之后用户可用的磁盘容量。）解析：（3）.将长度超过一个磁道容量的文件记录在同一个柱面上是否合理？（分数：2.40）.说明你所设计算法的时间复杂度。(分数：4.33)正确答案：(时间复杂度分析：在循环当中，我们可以看出每次都是对结点的父母结点进行调整，因此操作次数正好是树的高度，时间复杂度为O(log2i)。)解析：假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I/O设备读取1000B的数据到主存缓冲区中，该I/O设备一旦启动即按50KB/s的数据传输率向主机传送1000B数据，每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期，则以下4种方式下，在1000B的读取过程中，CPU用在该设备的I/O操作上的时间分别为多少？占整个CPU时间的百分比分别是多少？(分数：11.00).采用定时查询方式，每次处理一个字节，一次状态查询至少需要60个时钟周期。(分数：2.20)正确答案：(定时查询方式下的I/O过程如图1所示。用户可以设置每隔20000ns查询一次，这样使得查询程序的开销达到最小，即第一次读取状态时就可能会发现就绪，然后用1000个时钟周期进行相应处理，因此，对于每个字节的传送，CPU所用时钟周期数为60+1000=1060。因此，在1000B的读取过程中，CPU用在该设备的I/O操作上的时间至少为1000X1060X1ns=1.060ms,占整个CPU时间的百分比至少为1.060/20=5.3%。[正确答案：(独占查询方式下的I/O正确答案：(独占查询方式下的I/O过程如图2所示。启动设备后，CPU就开始查询，因为333X60+20=20000,所以第一个字节传送在第334次读取状态查询时检测到就绪，随后用1000个时钟周期进行相应的处理，然后继续第二个字节的状态查询，因为40+1000+316X60=20000,所以，第二个字节的传送在第316次读取状态查询时检测到就绪，第一个和第二个字节的传送过程如图2a所示。每次检测到就绪后，就进行相应的处理，然后周而复始地进行查询，因为(20000-1000)/60=316.7,所以，第317次状态查询时发现就绪。因为1000+60X317-20000=20,所以，每3B可多60个时钟周期，正好进行一次状态查询，因此，在剩下的998B的读取过程中，前996B的传送正好用了996X20000个时钟周期，如图2b所示。最后两个字节的传送过程如图2c所示，因为2X(1000+60X317-20000)=40,此外，最后一个字节的处理还有1000个时钟周期，所以最后两个字节总的时间为2X20000+40+1000=41040个时钟周期。综上所述，CPU用在该设备的I/O操作上的总时间为1000X20000ns+1040X1ns=20.00104ms720ms,即在1000B的整个传输过程中，CPU一直为该设备服务，所用时间占整个CPU时间的100%。图1定时查询方式下的I/O过程)解析：[解析]主频为1GHz,所以时钟周期为1/1GHz=1ns。因为每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期，所以，对于像程序查询和中断等用软件实现输入/输出的方式，CPU为每个字节传送所用的时间至少为1000X1ns=1000ns=1ps。在50kB/s的数据传输率下，设备每隔1B/50kB/s=20ps=20000ns准备好一个字节，因而读取1000B的时间为1000X20ps=20ms。.采用独占查询方式，每次处理一个字节，一次状态查询至少需要60个时钟周期。(分数：2.20).采用中断I/O方式，外设每准备好一个字节发送一次中断请求。每次中断响应需要2个时钟周期，中断服务程序的执行需要1200个时钟周期。（分数：2.20）正确答案：（中断方式下的I/O过程如图3所示。中断方式下，外设每准备好一个字节请求一次中断，每次中断CPU所用时钟周期数为2+1200=1202,因此CPU用在该设备的I/O操作上的时间为1000X1202X1ns=1.202ms,占整个CPU时间的百分比至少为1.202/20=6.01%。困图3中断方式下的I/O过程）解析：.采用周期挪用DMA方式，每挪用一次主存周期处理一个字节，一次DMA传送完成1000B的传送，DMA初始化和后处理的时间为2000个时钟周期，CPU和DMA之间没有访存冲突。（分数：2.20）正确答案：（DMA方式下，由于CPU和DMA没有访存冲突，所以不需考虑由于DMA而影响到CPU执行其他程序。因此，传送1000BCPU所用的时钟周期数就是2000,在1000B的读取过程中，CPU用在该设备的I/O操作上的时间为2000X1ns=2ps,占整个CPU时间的百分比为2/（1000X20）=0.01%。）解析：.如果设备的速度提高到5MB/s,则上述4种方式中，哪些是不可行的?为什么？对于可行的方式，计算出CPU在该设备I/O操作上所用的时间占整个CPU时间的百分比。（分数：2.20）正确答案：（若设备数据传输率为5MB/s,则外设传输1000B所用时间为1000B/（5X108/s）=200ps。对于定时查询和独占查询方式，传送1000BCPU所用时间至少为1000X（60+1000）X1ns=1060ps；对于中断方式，传送1000BCPU所用时间为1000X（2+1200）X1ns=1202ps。上述3种方式下，CPU所用的时间都比设备所用时间长得多，即设备的传输比CPU的处理快得多，因而发生数据丢失。因此，这3种方式都不能用于该设备的I/O操作。对于DMA方式，传送1000BCPU所用时间为2000X1ns=2ps,占整个CPU时间的百分比为2/200=1%。这说明可以使用DMA方式，不过由于外设传输速度加快，使得CPU频繁进行DMA预处理和后处理，因而CPU的开销从0.01%上升到了1%。）解析：硬磁盘共有4个记录面，存储区域内半径为10cm,外半径为15.5cm,道密度为60道/cm,外层位密度为600bit/cm,转速为6000r/min。问：（分数：12.00）.硬磁盘的磁道总数是多少？（分数：2.40）正确答案：（有效存储区域=15.5cm-10cm=5.5cm,道密度=60道/cm,因此每个面60道/cmX5.5cm=330道，即有330个柱面，磁道总数=4X330道=1320道。）解析：.硬磁盘的容量是多少?磁盘的非格式化容量和格式化容量是一个什么概念，两者之间有什么关系？（分数：2.40）正确答案：（如果长度超过一个磁道容量的文件，将它记录在同一个柱面上比较合理，因为不需要重新寻找磁道，这样数据读/写速度快。）解析：.采用定长数据块记录格式，直接寻址的最小单位是什么？寻址命令中磁盘地址如何表示？（分数：2.40）正确答案：（采用定长数据块格式，直接寻址的最小单位是一个扇区，每个扇区记录固定字节数目的信息，在定长记录的数据块中，活动头磁盘组的编址方式可用如下格式：［*］此地址格式表示最多可以接4台硬盘，每台最多有8个记录面，每面最多可有128个磁道，每道最多可有16个扇区。）解析：.假定每个扇区的容量512B，每个磁道有12个扇区，寻道的平均等待时间为10.5ms，试计算读出磁盘一个扇区中数据的平均时间。（分数：2.40）正确答案：（读一个扇区中数据所用的时间为找磁道的时间+找扇区的时间+磁头扫过一个扇区的时间找磁道时间是指磁头从当前所处磁道运动到目标磁道的时间，一般选用磁头在磁盘径向方向上移动1/2个半径长度所用时间为平均值来估算，题中给的是10.5ms。找扇区的时间是指磁头从当前所处扇区运动到目标扇区的时间，一般选用磁盘旋转半周的所用时间作为平均值来估算，题中给出的磁盘转速为6000r/min，即100r/s，即磁盘转一周用时为10ms，转半周的时间是5ms。题中给出每个磁道有12个扇区，磁头扫过一个扇区用时为10/12ms=0.83ms，计算结果应该为10.5ms+5ms+0.83ms=16.33ms。为了减少寻找磁道和等待扇区所占时间的比例，磁盘通常应该以多个扇区为单位进行读写，一旦开始具体的读写操作，就对多个连续的扇区进行顺序读写，读写的数据首先保存到系统设置的一个缓存区中，CPU通常要经过操作系统实现与这个缓冲区交换数据，而不是直接与磁盘设备本身交换数据。）解析：在一个段式存储管理系统中，逻辑地址为32位，其中高16位为段号，低16位为段内偏移，以下是段表（其中的数据均为十六进制，见下表）。{{B}}段表{{/B}}段基地址长度保护01000018C0只读1119003FF只读211D001FF读-写300禁止访问411F001000读-写500禁止访问600禁止访问713000FFF读-写以下是代码段的内容:mainsin240pushX[10108]360mov4+(sp),r2244callsin364pushr2248…366…488ret试问：（分数:7.98）（1）.x的逻辑地址为10108,它的物理地址是多少？（分数：1.33）正确答案：（高16位为段号，低16位为段内偏移，则1为段号（对应基址11900）,0108为段内偏移，则逻辑地址11A08对应的物理地址为基址加段内偏移，即11900+0108=11A08。）解析：.栈指针的当前地址是70FF0，它的物理地址是多少？（分数：1.33）正确答案：（7为段号，0FF0为段内偏移，13000+0FF0=13FF0。）解析：.第一条指令的逻辑地址和物理地址各为多少？（分数：1.33）正确答案：（逻辑地址240，物理地址为基址加段内偏移，即10000+240=10240。）解析：.pushx指令的执行过程：将sP（堆栈寄存器）减4,然后存储x的值。试问x被存储在什么地方（物理地址）？（分数：1.33）正确答案：（知道SP对应物理地址为13FF0，减4之后为13FEC，即x存储地址为13FEC。）解析：.callsin指令的执行过程：先将当前PC值入栈，然后在PC内装入目标PC值。试问哪个值被压入栈了?新的栈指针的值是多少?新的Pc值是多少？（分数：1.33）正确答案：（PC在调用callsin命令之后，自增为248,所以逻辑