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

计算机专业（基础综合）模拟试卷5（共9套）（共489题）计算机专业（基础综合）模拟试卷第1套一、单选题(本题共40题，每题1.0分，共40分。)1、输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图3-1所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列()。A、2、8、1、4B、1、4、8、2C、4、2、1、8D、2、1、4、8标准答案：D知识点解析：A选项：首先，8、1、4、2都从左端入队，然后2从左端出队，8从右端出队，1从右端出队，4从左端出队，得到A的序列。B选项：首先，8和1分别从左端输入，然后1从左端出队，4再从左端入队，4再从左端出队，2从左端入对，8从右端出队，2从左端出队，得到B的序列。C选项：首先，8、1、4都从左端入队，4从左端出队，2再从左端入队，2从左端出队，1从左端出队，8从左端或者右端出队，得到C的序列。D选项：首先，8、1、4、2都从左端入队，然后2从左端出队，队列的序列变成如图3-7所示，接着如果要让1出队列，必须4或8先出队列，所以D的序列不可能实现。2、若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向()。A、各自的头结点B、各自的尾结点C、各自的第一个元素结点D、一个表的头结点，另一个表的尾结点标准答案：B知识点解析：两个循环链表头尾相接，需要改变头结点和尾结点之间的指针，而这个指针是从尾结点指向头结点的，所以只有将两个指针分别指向自己循环链表的尾结点才能完成操作。实现的代码如下：voidconnect(LNode*A，LNode*＆B)／／假设A、B为非空带头结点的循环链表的尾指针{LNode*p=A-＞next；／／保存A表的头结点A-＞neXt=B-＞next-＞next；／／B的开始结点链接到A表尾free(B-＞next)；／／释放B表的头结点B-＞next=p；／／将B表的尾结点链接到A表的头结点}3、下列说法正确的是()。Ⅰ．用链式方式存储的队列，在进行出队操作时，队头、队尾指针都必须修改Ⅱ．将递归算法转换成等价的非递归算法应使用栈Ⅲ．图的广度优先搜索使用了栈来实现A、ⅠB、Ⅰ、ⅡC、ⅡD、Ⅱ、Ⅲ标准答案：C知识点解析：Ⅰ：队列以链表方式存储时，如果队列中只有一个元素，则出队操作需要修改队头、队尾指针；反之，只需要修改队头指针，所以Ⅰ错误。Ⅱ：考查栈的基本应用，在二叉树遍历的非递归算法中可以得到认证，所以Ⅱ正确。Ⅲ：队列具有先进先出的特性，在广度优先搜索算法中，访问完每一个结点，可将其子结点全部加入队列中，这样可实现结点的按层次优先的访问，故广度优先搜索使用了队列来实现，所以Ⅲ错误。4、下列关于二叉排序树的说法正确的是()。Ⅰ．向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度Ⅱ．二叉排序树一定是平衡二叉树Ⅲ．删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树Ⅳ．平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树A、Ⅰ、Ⅱ、ⅣB、Ⅱ、Ⅲ、ⅣC、Ⅰ、ⅣD、全错标准答案：D知识点解析：Ⅰ：根据二叉排序树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以Ⅰ错误。Ⅱ：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以Ⅱ错误Ⅲ：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图3-8所示。此时删除结点3，二叉排序树变为图3-8b，再插入结点3，变为图3-8c。显然图3-8a和图3-8c不是同一个二叉排序树，所以Ⅲ错误。Ⅳ：根据平衡二叉树的概念可知，该说法是错误的，应该改为：平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉排序树(出此选项的目的是让大家深刻记住平衡二叉树默认是二叉排序树)，所以Ⅳ错误。5、对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为()。A、0．5(n+1)B、0．25(n+1)C、0．5(n-1)D、0．75n+0．25标准答案：D知识点解析：在查找成功的情况下，平均查找长度为(1+n)／2；在查找不成功时，每次都需要查找n次，即平均查找长度为n，而题目告诉我们查找成功与查找不成功各占一半，故平均查找长度为：(1+n)／2)／2+n／2=0．75n+0．25。6、一组记录的关键字为{45，78，55，37，39，83}，利用堆排序初始时的堆为()。A、78，45，55，37，39，83B、83，78，55，37，39，45C、83，78，55，45，39，37D、83，55，78，39，45，37标准答案：B知识点解析：纵观四个选项可知，显然题目要求建立一个大顶堆。按照建堆的过程，先将序列构造成一棵完全二叉树，然后由最后一个非叶子结点开始，由下至上调整使得其满足堆的性质，构建过程如图3-9所示。即堆排序初始时的堆的序列是83，78，55，37，39，45。7、设有无向图G=(V，E)和G’=(V’，E’)，如果G’是G的生成树，则下面不正确的说法是()。Ⅰ．G’为G的连通分量Ⅱ．G’是G的无环子图Ⅲ．G’为G的极小连通子图，且V’=VA、Ⅰ、ⅡB、Ⅱ、ⅢC、只有ⅢD、只有Ⅰ标准答案：D知识点解析：一个连通图的生成树是一个极小连通子图(既然是树就肯定无环)，它含有图中全部顶点，所以选项Ⅱ、Ⅲ均为生成树的特点，而选项Ⅰ为概念错误：极大连通子图称为连通分量，G’为连通图而非连通分量。8、下列说法正确的是()。Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量Ⅲ．广度优先遍历算法类似于树中的后序遍历算法A、仅Ⅰ、ⅡB、仅Ⅱ、ⅢC、仅ⅡD、仅Ⅰ、Ⅲ标准答案：A知识点解析：Ⅰ：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数)，如图3-10所示。图中各顶点分布在3个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1～3的层次顺序来遍历各个顶点，并在遍历的过程中形成了一棵树，称之为广度优先搜索生成树，树的分支总是连接不同层上的点，如图3-10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以类比为无权图(无权图可理解为各边权值为1)，因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以Ⅰ正确。Ⅱ：从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到，也就找到了该顶点所在的连通分量，因此广度优先遍历可以求出无向图的所有连通分量，所以Ⅱ正确。Ⅲ：广度优先遍历算法应该是类似于树中的层次遍历算法，所以Ⅲ错误。综上所述，Ⅰ、Ⅱ正确。9、关于Hash查找说法不正确的有()个。Ⅰ．采用链地址法解决冲突时，查找一个元素的时间是相同的Ⅱ．采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的Ⅲ．用链地址法解决冲突易引起聚集(堆积)现象Ⅳ．再散列法不易产生聚集(堆积)A、1B、2C、3D、4标准答案：B知识点解析：如果两个元素在同一链表中，查找时间肯定不相同，故Ⅰ不正确；插入规定在链首的话，插入操作不需要查找插入位置即可直接进行，因此插入任何一个元素的时间均相同，因此Ⅱ正确；所谓聚集(堆积)，即在Hash表的建立过程中，某些Hash地址是由冲突处理产生的，而不是直接由Hash函数直接产生的，这就可能造成原本Key1与Key2虽然不是同义词，但是最后却得出了相同的Hash地址，显然链地址法不会产生堆积现象，因为多个同义词只会占用表中的一个地址，因此Ⅲ不正确；再散列法即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间，因此Ⅳ正确。综上，不正确的说法有2个，选B。10、一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。A、15，25，35，50，20，40，80，85，36，70B、15，25，35，50，80，20，85，40，70，36C、15，25，50，35，80，85，20，36，40，70D、15，25，35，50，80，20，36，40，70，85标准答案：A知识点解析：根据归并算法的思想，对5个长度为2的有序表一趟归并后得到两个长度为4的有序表和一个长度为2的有序表，只有A满足。11、已知有31个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12；3段长度为20(单位均为物理块)。在最佳5-路归并方案下，则总的读／写外存的次数为()。A、400B、500C、600D、800标准答案：D知识点解析：判断是否需要补充空归并段。如何判断?设度为0的结点有n0个，度为m的结点有nm个，则对严格m叉树有n0=(m-1)nm+1，由此可以得出nm=(n0-1)／m-1。(1)如果(n0-1)mod(m-1)=0，则说明这n0个叶子结点(初始归并段)正好可以构造m叉归并树。此时，内结点有nm个。(2)如果(n0-1)mod(m-1)=u≠0，则说明这n0个叶子结点，其中有u个结点多余，不能被包含在m叉归并树内。为了构造包含所有n0个初始归并段的m叉归并树，应在原有的nm个内结点中再增加一个内结点。它在归并树中代替了一个叶子结点的位置，被代替的叶子结点加上刚才多出的u个叶子结点，再加上m-u-1个空归并段，就可以建立归并树。按照以上步骤：因为(31-1)mod(5-1)≠0，所以需要增设空归并段。需要增设5-2-1=2个空归并段。接下来就比较简单了，仿造赫夫曼树的构造方法，来构造5-路最佳归并树，如图3-11所示。从图3-11中可以算出(带有方框的结点表示原数据结点)：WPL=(2×8+3×8+5×2)×3+(5×5+12×5+20×1)×2+20×2=400则总的读／写外存的次数为：400×2=800。12、x=-0．875×21，y=0．625×22，设尾数为3位，符号位为1位，阶码为2位，阶符为1位，通过补码求出z=x-y的二进制浮点规格化的结果是()。A、1011011B、0111011C、1001011D、0110111标准答案：B知识点解析：浮点数x尾数的补码为：1．001；浮点数-y尾数的补码为1．011。因为x的阶数为1，y的阶数为2，所以要进行对阶，保留y的阶数2，把x的尾数右移一位，阶数变为2．(这里要注意，x是负数，右移的时候是补1，而不是补0)。于是，右移后的x的尾数为1．100。相加得到1．100+1．011=10．111，结果出现溢出，需要右规；将其结果右移一位，得到1．011，同时阶码加1得到11(对应真值为3)，最终得到二进制浮点规格化的结果是0111011。13、已知计算机A的时钟频率为800MHz，假定某程序在计算机A上运行时间需要12s。现在硬件设计人员想设计计算机B，希望该程序在B上的运行时间能缩短为8s，使用新技术后可使B的时钟频率大幅度提高，但在B上运行该程序所需要的时钟周期数为在A上的1．5倍。那么，机器B的时钟频率至少应为()才能达到所希望的要求。A、800MHzB、1．2GHzC、1．5GHzD、1．8GHz标准答案：D知识点解析：设计算机i的时钟频率为fi，时钟周期为Ti，时钟周期数(CPI)为Ni。TA×NA=NA／fA=12s①TB×NB=NB／fB=8s②NB=1．5NA③fA=800MHz④解得fB=1．8GHz。14、下列()是动态半导体存储器的特点。Ⅰ．在工作中存储器内容会产生变化Ⅱ．每隔一定时间，需要根据原存内容重新写入一遍Ⅲ．一次完整的刷新过程需要占用两个存储周期Ⅳ．一次完整的刷新过程只需要占用一个存储周期A、Ⅰ、ⅢB、Ⅱ、ⅢC、Ⅱ、ⅣD、只有Ⅲ标准答案：C知识点解析：动态半导体存储器是利用电容存储电荷的特性记录信息，由于电容会放电，所以必须在电荷流失前对电容充电，即刷新。方法是每隔一定时间，根据原存内容重新写入一遍，所以I错误，其他的选项请参考下面的补充知识点。15、Cache常使用的写回策略有写直达法和写回法，则下面关于写直达法和写回法说法正确的是()。Ⅰ．写回法是一个Cache数据块在任何一次写操作数时都需要写回主存Ⅱ．写直达法是一个Cache数据块仅在第一次写操作数时才需要写回主存Ⅲ．写回法的每个Cache块需要设置一位状态位A、仅Ⅰ、ⅢB、仅ⅡC、仅ⅢD、Ⅰ、Ⅱ和Ⅲ标准答案：C知识点解析：写直达法：是指每次写操作数时既写入Cache又写入主存，所以并不是仅在第一次才写回主存，所以Ⅱ错误。写回法：是写Cache时不写入主存，而当Cache数据被替换出去时才写回主存，所以会造成写回法的Cache中的数据会与主存的不一致。为了识别Cache中的数据是否与主存中的一致，Cache中的每一块要增加一个记录信息位，写Cache时设置这个位，Cache数据写回主存时清除这个位。根据这个位的值，Cache中每一块都有两个状态：清(clean)和浊(dirty)，在写Cache时状态为“浊”，在数据写回主存时状态为“清”，所以Ⅰ错误，Ⅲ正确。16、在Cache和主存构成的两级存储器中，Cache的存储时间是100ns，主存的存储时间是1000ns，如果希望有效存储时间不超过115ns，则Cache的命中率至少为()。A、90％B、98％C、95％D、99％标准答案：D知识点解析：假设Cache的命中率为x，则可以得到一个不等式：1000(1-x)+100x≤115x≥0．983所以，Cache命中率x至少为99％。17、某指令系统指令字长为8位，每一地址码长3位，采用扩展操作码技术。若指令系统具有两条二地址指令、10条零地址指令，则最多可有()条一地址指令?A、20B、14C、10D、6标准答案：B知识点解析：由于二地址指令操作码字段位数为2，最多可以有4条二地址指令，而只使用了两条，前两位剩下两条，即多余出1位留作扩展用，所以剩余空间为21+3+3=128，又因为其中包含了10条零地址指令，所以可用的空间还有118，在这个空间当中，由于一地址指令后三位为地址，故可设计出118／23，结果取整。补充：以上的方法可能理解起来可能稍微有点困难，我们还可以试着这样去做：因为二地址指令的操作码剩余1位留到一地址指令操作码来扩展，则一地址指令最多可以有21+3=16条，还剩下3位用来表示零地址指令，则最多有8条，现在题目告诉我们有10条零地址指令，这样零地址指令需要向一地址指令中去“借”两条，因此此时一地址指令最多只有14条。18、指令流通常是()。A、从主存流向控制器B、从控制器流向主存C、从控制器流向控制器D、从主存流向主存标准答案：A知识点解析：指令是存放在主存中的，在主存中取出指令后送入控制器进行分析并发出相应的各种操作序列，所以指令流是从主存流向控制器，且是单向流动；而数据流是在CPU中的运算器和主存之间流动，且是双向流动。19、为了便于实现多级中断，保存现场信息最有效的办法是采用()。A、通用寄存器B、堆栈C、存储器D、外存标准答案：B知识点解析：CPU响应中断时，需要保存当前的一些寄存器中的现场信息，以便在中断结束后进行恢复从而继续执行完毕。在多级中断时，每一层的中断都需要保护中断时的现场信息，例如一个三级中断，依次需要保护第一、第二、第三级的现场信息，当产生第三级的中断处理程序结束后，首先恢复第三级的现场进行处理，结束后返回第二级……以此类推，这样正好符合堆栈的特性，即后进入堆栈的先出来。因此，采用堆栈存储较为有效。20、为确定下一条微指令的地址，通常采用断定方式，其基本思想是()。A、用程序计数器(PC)来产生后继微指令地址B、用微程序计数器(μPC)来产生后继微指令地址C、由微指令的下地址字段直接指出后续微指令地址D、由专门的硬件电路或者外部直接向CMAR输入微指令地址标准答案：C知识点解析：A：这种方法无法用来控制微程序的执行，因为PC的最小控制单位是一条指令，或者说是一个微程序(因为一个微程序解释一条指令)，而微指令是更小的单位。B：该方法为增量计数法。C：该方法是直接由下地址字段来指出，也称为断定方式。D：此方式为硬件方式。21、下列关于程序中断方式和DMA方式的叙述中，错误的是()。Ⅰ．DMA的优先级比程序中断的优先级要高Ⅱ．程序中断方式需要保护现场，DMA方式不需要保护现场Ⅲ．程序中断方式的中断请求是为了报告CPU数据的传输结束，而DMA方式的中断请求完全是为了传送数据A、仅ⅡB、仅Ⅱ、ⅢC、仅ⅢID、仅Ⅰ、Ⅲ标准答案：C知识点解析：Ⅰ：DMA方式不需CPU干预传送操作，仅仅是开始和结尾借用CPU一点时间，其余不占用CPU任何资源，中断方式是程序切换，每次操作需要保护和恢复现场，所以DMA优先级高于中断请求，这样可以加快处理效率，故Ⅰ正确。Ⅱ：从Ⅰ的分析可知，程序中断方式需要中断现行程序，故需保护现场，以便中断执行完之后还能回到原来的点去继续没有完成的工作；DMA方式不需要中断现行程序，无须保护现场，故Ⅱ正确。Ⅲ：DMA方式中的中断请求不是为了传送信息(信息是通过主存和I／O间的直接数据通路传送的)，只是为了报告CPU一组数据传送结束，有待CPU做一些后处理工作，如测试传送过程中是否出错，决定是否继续使用DMA方式传送等。而程序中断方式的中断请求是为了传送数据，I／O和主机交换信息完全靠CPU响应中断后，转至中断服务程序完成的，故Ⅲ的说法错误。22、某计算机采用微程序控制，微指令中操作控制字段共12位，若采用直接控制，则此时一条微指令最多可同时启动()个操作。若采用字段直接编码控制，并要求一条微指令需要同时启动3个微操作，则指令中的操作控制字段应分()段，若每个字段的微指令数相同，这样的微指令格式最多可包含()个微操作指令。A、12；6；24B、12；6；18C、12；4；24D、12；4；18标准答案：B知识点解析：直接控制中每一位对应一个微操作，故能最多同时启动12个微操作；在字段直接编码控制中，每段的长度为N，则可表示的微操作的个数为2N，因为一条微指令需启动3个微操作，故至少需要两位，所以操作控制字段应分为12／2=6段；现在每个字段占2位，则最多能表示3条微指令(根据字段直接编码的要求要留出一位表示空操作)，则最多可以包含18个微操作指令。23、一台装有Linux系统的主机，只有两个账号root和guest，下面关于“Linux是一个多用户、多任务的操作系统”的理解中，正确的有()。Ⅰ．该主机允许root和guest同时登录，因为Linux系统支持多用户Ⅱ．该主机不允许root和guest同时登录，因为Linux系统最多只能有一个活跃用户Ⅲ．该主机允许多个客户端通过root账号登录，因为Linux系统支持多任务Ⅳ．该主机不允许多个客户端通过同一账号登录，因为Linux用户只能有一个活跃客户端A、Ⅰ和ⅢB、Ⅰ和ⅣC、Ⅱ和ⅢD、Ⅱ和Ⅳ标准答案：A知识点解析：这里的“账号”等价于“用户”。Ⅰ正确很容易理解，支持多用户，肯定就是支持同时登录。Ⅲ正确，多个客户端通过同一账号登录，这些个客户端其实运行的只是一个进程。Linux支持多任务的系统，所以肯定是可以的。24、下列关于进程通信的叙述正确的有()。Ⅰ．基于消息队列的通信方式中，复制发送比引用发送效率高Ⅱ．从进程通信的角度设计PCB应包含的项目，需要有消息队列指针、描述消息队列中消息个数的资源信号量、进程调度信息Ⅲ．进程可以通过共享各自的内存空间来直接共享信息Ⅳ．并发进程之间进行通信时，一定共享某些资源A、Ⅰ、ⅣB、Ⅰ、ⅢC、Ⅱ、ⅢD、Ⅳ标准答案：D知识点解析：Ⅰ错误，当发送方发送一个较小的数据包时，发送方将数据复制至消息队列，然后接收方从消息队列中拷走，这称为复制发送；如果数据包较大，发送方只是把指向数据包的指针和数据包大小发送给接收者，接收者通过指针访问数据包，这称为引用发送。显然引用发送比复制发送更复杂，但不需要复制数据，所以引用发送效率高。Ⅱ错误，进程调度信息属于进程管理的内容，并非进程通信内容，这里还缺少一个实现消息队列互斥访问的互斥信号量。Ⅲ错误，各个进程有自己的内存空间、数据栈等，所以只能使用进程间通信(InterProcessCommunications，IPC)，而不能直接共享信息。需要注意的是，这里的内存空间和进程通信中的共享的缓冲区是不一样。Ⅳ正确，并发进程之间进行通信时，必定存在资源共享问题。进程通信归结为三大类：(1)共享存储器系统，很明显共享了存储器资源。(2)消息传递系统，共享了消息文件。(3)管道通信，共享了管道文件。25、有以下的进程需要调度执行，如表3-1所示。分别采用非抢占的短进程优先调度算法和抢占的短进程优先调度算法，这5个进程的平均周转时间为()。A、8．62；6．34B、8．62；6．8C、10．62；6．34D、10．626．8标准答案：D知识点解析：非抢占式(见表3-5)：平均周转时间为(9+15．6+9+14．5+5)／5=10．62。抢占式(见表3-6)：平均周转时间为(20+5+1+6+2)／5=6．8。26、在单处理器的多进程系统中，进程什么时候占用处理器和能占用多长时间取决于()。A、进程相应的程序段长度B、进程总共需要运行时间多少C、进程自身和进程调度策略D、进程完成什么功能标准答案：C知识点解析：在进程调度时，不同调度算法有不同调度依据，一般与程序段长度、完成什么功能无关，故A、D错误。若使用与运行时间相关的调度算法(如短进程优先算法，高响应比优先调度算法等)，那么进程什么时候占用处理器与预计运行时间相关，最后能占用多长时间还是要取决于调度策略和进程自身，因此本题选C是最准确的，B选项肯定错误，因为它都没提到进程调度策略。27、利用死锁定理简化下列进程．资源图(见图3-2)，则处于死锁状态的是()。A、图3-2aB、图3-2bC、图3-2a和图3-2bD、都不处于死锁状态标准答案：B知识点解析：在图3-2a中，系统中共有R1类资源2个，R2类资源3个，在当前状态下仅有一个R2类资源空闲。进程P2占有一个R1类资源及1个R2类资源，并申请1个R2类资源；进程P1占有1个R1类资源及1个R2类资源，并申请1个R1类资源及1个R2类资源。因此，进程P2是一个既不孤立又非阻塞的进程，消去进程P2的资源请求边和资源分配边，便形成了图3-12所示情况。当进程P2释放资源后，系统中有2个R2类空闲资源，1个R1类空闲资源。因此，系统能满足进程P1的资源申请，使得进程P1成为一个既不孤立又非阻塞的进程，消去进程P1的资源请求边和资源分配边，便形成了图3-13所示情况。由死锁定理可知，图3-2a中的进程．资源图不会产生死锁。在图3-2b中，系统中共有R1类资源1个、R2类资源2个、R3类资源2个、R4类资源1个。在当前状态下仅有1个R3资源空闲。进程P1占有1个R2资源，并申请1个R1资源；进程P2占有1个R1资源及1个R3资源，并申请1个R4资源；进程P3占有1个R4资源及1个R2类资源，并申请1个R3类资源及1个R2类资源。因此，该资源分配图中没有既不孤立又不阻塞的进程结点，即系统中的3个进程均无法向前推进，由死锁定理可知，图3-2b的进程-资源图会产生死锁。28、用户在段页式存储管理方式下运行一个进程，段表寄存器和段表如图3-3所示(页面大小为1KB)。该用户在调试过程中，设计了3个地址，试图获取数据，地址如表3-2所示。这三次获取数据的操作，分别访问内存次数为()。A、3、3、3B、1、0、3C、2、1、3D、1、2、2标准答案：B知识点解析：在段页式存储系统中，为了获取一条指令或数据，必须三次访问内存，第一次访问内存中的段表，从中取得页表地址；第二次访问内存中的页表，从中取得该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问根据第二次访问所得的地址，真正取出指令或数据(但这是在访问地址正确的情况下)。为了防止越界，在段页式存储系统中，配置了一个段表寄存器，其中存放段表始址和段表长度。在进行地址变换时，首先利用段号，将它与段长进行比较。若段号超出段表长度，表示越界了。同样段表中的，页表大小这项也是为了预防地址越界的情况。一般情况下，段号页号都是从0开始编址，这点从题目所给的图中也可得知。该用户访问的3个地址中，地址一，段号检查通过，页号越界，3不在页号0～2范围内，所以只访问内存1次。地址二，段号检查未通过，8不在段号0～7范围内，越界，所以访问内存0次。地址三，段号检查通过，且页号也无越界，成功访问到数据，所以访问内存3次。29、假设系统为某进程分配了3个物理块，考虑页面走向为：7，0，1，2，0，3，0，4。试问采用CLOCK页面淘汰算法时缺页中断的次数为()。A、8B、7C、6D、5标准答案：C知识点解析：CLOCK页面淘汰算法的缺页情况(见表3-7)。30、下列关于文件控制块的错误说法的个数为()。Ⅰ．文件控制块就是文件目录项Ⅱ．文件控制块是在执行open(打开)系统调用时建立的Ⅲ．一个文件可以对应有多个文件控制块Ⅳ．文件控制块通常含有3类信息：基本信息、存取控制信息及使用信息A、1B、2C、3D、4标准答案：B知识点解析：文件控制块与文件一一对应(Ⅲ错误)，创建文件时(create)建立对应的FCB，而不是打开文件时创建的(Ⅱ错误)。人们把文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项(Ⅰ正确)。在文件控制块中，通常含有3类信息，即基本信息、存取控制信息及使用信息(Ⅳ正确)。所以Ⅰ，Ⅳ正确，Ⅱ，Ⅲ错误。错误的个数为2，所以选B。31、如果当前读写磁头正在50号柱面上执行输入输出操作，依次有4个等待者分别要访问的柱面号为37、98、124、65，当采用()调度算法时下一次读写磁头可能到达37号柱面。Ⅰ．先来先服务(FCFS)Ⅱ．最短寻道时间优先(SSTF)Ⅲ．磁头移动方向朝着小磁道方向的电梯调度(SCAN)Ⅳ．磁头移动方向朝着大磁道方向的循环扫描算法(CSCAN)A、ⅢB、Ⅰ、ⅢC、Ⅰ、Ⅱ、ⅢD、全部都是标准答案：C知识点解析：题目中暗含有时间顺序，“依次有4个等待着”，即最早来的等待着是要访问37号柱面的，所以Ⅰ正确。考虑50号两个方向最近的柱面号请求，50-37=13和65-50=15，即拥有最短寻道时间的是37号柱面，所以Ⅱ也正确。电梯调度算法，总是从磁头当前位置开始，沿磁头的移动方向(小磁道方向)去选择离当前磁头最近的那个柱面的请求，即37。循环扫描算法是电梯算法的改进版，但也是按当前移动方向(大磁道方向)去选择离当前磁头最近的那个柱面的请求，即65。不同的是为了减少延迟，规定磁头单向移动，即只能有一个移动方向。32、下列技术中属于以空间换时间的是()。Ⅰ．SPOOLing技术Ⅱ．虚拟存储技术Ⅲ．缓冲技术Ⅳ．通道技术A、Ⅰ和ⅡB、Ⅰ和ⅢC、Ⅱ和ⅢD、全部都是标准答案：B知识点解析：这类题只要记住，时间换空间就是空间变大了，空间换时间就是时间缩短了，一般就不会做错了。总结如下：时间换空间：虚拟存储技术、覆盖与交换技术等。空间换时间：SPOOLing技术、缓冲技术等。解释如下：各种虚拟存储技术都是时间换空间的技术，包括请求分页、请求分段、请求段页式，这些都是让访问时间增加了，但是扩充了主存的逻辑容量，使得大于主存容量的程序也可以得到执行。如果空间换时间，则各类的缓冲区、缓冲池都是，本来需要在速度很慢的设备上I／O的，但是自从划分了些存储区域做缓冲，那么就可以减少访问时间。SPOOLing技术需有高速大容量且可随机存取的外存支持，通过预输入及缓输出来减少CPU等待慢速设备的时间，这是典型的以空间换时间策略的实例。所以本题选B。33、下列关于TCP／IP参考模型的说法正确的是()。A、明显地区分接口和协议的概念B、网络层可以提供面向连接的服务C、不区分物理层和数据链路层D、TCP／IP参考模型共有5层标准答案：C知识点解析：TCP／IP参考模型共有四层，分别是网络接口层、网络层、传输层、应用层。其中网络接口层包含物理层和数据链路层，所以TCP／IP参考模型并不区分物理层和数据链路层。另外，在TCP／IP模型中，并没有明确区分服务、接口和协议。其他选项请参照表3-8的总结。34、某客户端采用ping命令检测网络连接故障时，发现可以ping通127．0．0．1及本机的IP地址，但无法ping通同一网段内其他正常工作的计算机的IP地址。该客户端的故障可能是()。A、TCP／IP协议不能正常工作B、本机网卡不能正常工作C、本机网络接口故障D、DNS服务器地址设置错误标准答案：D知识点解析：采用ping命令检测网络连接故障时，可以先输入ping127．0．0．1，即本地循环地址，如果发现本地址ping通，就表明本地机TCP／IP协议正常工作。如果上面的操作成功，接下来可以ping本机IP，若通，则表明网络适配器(网卡或MODEM)工作正常。最后ping同网段中某计算机的IP，如果ping不通则表明网络线路出现故障。35、在平均往返时间RTT为20ms的快速以太网上运行TCP／IP协议，假设TCP的最大窗口尺寸为64KB，此时TCP协议所能支持的最大数据传输率是()。A、3．2Mbit／sB、12．8Mbit／sC、25．6Mbit／sD、51．2Mbit／s标准答案：C知识点解析：因为TCP／IP的最大窗口尺寸／数据传输率≥往返时间RTT，即64×8×103／C≥20×10-3，所以C≤(64×8×103)／(20×10-3)=25．6Mbit／s。36、在滑动窗口机制中，已知帧的序号为3bit时，若采用后退N帧协议传送数据，则发送窗口的最大尺寸为()；若采用选择重传协议，并且发送窗口与接收窗口的尺寸相同时，发送窗口的最大尺寸为()。A、8；6B、8：4C、7；4D、7；6标准答案：C知识点解析：只有在发送窗口的大小Wt≤2m-1时(帧序号位数m)即发送窗口最大尺寸为7时，后退N帧协议才能正确运行；对于选择重传协议，若用m比特进行编号，则接收窗口的大小WR≤2m-1，即接收窗口最大尺寸为4。其理由是防止上一轮的帧号与下一轮的相同帧号同时出现而造成接收方误判。37、关于ICMP协议的说法正确的是()。Ⅰ．ICMP消息的传输是可靠的Ⅱ．ICMP被封装在IP数据报的数据部分Ⅲ．ICMP可用来进行拥塞控制A、仅ⅠB、Ⅰ和ⅡC、Ⅱ和ⅢD、Ⅰ和Ⅲ标准答案：C知识点解析：Ⅰ：由于IP层提供的是无连接不可靠的服务，所以ICMP消息的传输是不可靠的，故Ⅰ错误。Ⅱ：ICMP报文整个被作为IP分组的数据部分，所以Ⅱ正确。Ⅲ：主机在发送数据报时，经常会由于各种原因发送错误，比如路由器拥塞丢弃了或者传输过程中出现错误丢弃了，如果检测出错误的路由器或主机都能把这些错误报告通过一些控制消息告诉发送数据的主机那就好了，那么发送数据的主机就可根据ICMP报文确定发生错误的类型，并确定如何才能更好地重发失败的数据报。比如ICMP报文发过来的是改变路由，那么主机就不能继续按照这个路由线路发送了，需要用另外一条路由线路发送数据，所以Ⅲ正确。注1：ICMP报文包含的不仅是出错类型，而且还要包含出错IP数据报的数据部分的前8个字节。因为前8个字节包含了TCP和UDP报文首部巾的TCP或UDP端口号，这样源主机可更好地和用户进程(用户进程需要IP地址和端口号才能唯一确定)联系起来，因为发送数据的是某个主机中的某个进程而不足主机本身，这样才算是真正找到了发送数据源。注2：常用的ping命令使用了回送请求报文，以探测目标主机是否可达；如果在IP数据报传送过程中，发现生命周期字段为零，则路由器发出超时报文。38、经CIDR路由汇聚后的路由表如表3-3所示。如果该路由器接收到目的地址为172．16．59．37的分组，则路由器()。A、将接收到的分组直接传送给目的主机B、将接收到的分组丢弃C、将接收到的分组从SO接口转发D、将接收到的分组从S1接口转发标准答案：D知识点解析：当路由器接收到目的地址为172．16．59．37的分组，那么路由器就需要在路由表中寻找一条最佳的匹配路由，即满足最长匹配原则。由于前两个字节172．16都是一样的，所以只需比较第三个字节即可。59=(00111011)2，0=(00000000)2，56=(00111000)2，63=(00111111)2，70=(01000110)2。经比较，目的地址172．16．59．37与172．16．56．0／22的地址前缀之间有22位是匹配的，查表3-3可知，该路由器到达目的网络172．16．56．0／22的输出接口是S1。因此，该路由器将接收到的目的地址为172．16．59．37的分组从S1接口转发。39、如果主机A要向处于同一子网段的主机B(IP地址为172．16．204．89／16)发送一个分组，那么主机A使用的“这个网络上的特定主机”的地址为()。A、172．16．255．255B、172．16．204．255C、0．0．255．255D、0．0．204．89标准答案：D知识点解析：当一台主机或一台路由器向本网络的某台特定的主机发送一个分组时，它需要使用“这个网络上的特定主机”地址。该分组被限制在本网内部，由主机号对应的主机接收。例如，主机A要向处于同一子网段的主机B(IP地址为172．16．204．89／16)发送一个分组，由于172．16．204．89／16是一个B类IP地址，“／16”是子网掩码255．255．0．的简写形式，该B类IP地址的网络号为“172．16”、主机号为“204．89”，所以主机A使用的“这个网络上的特定主机”的地址为0．0．204．89。40、使用WWW浏览器浏览网页，用户可用鼠标单击某个超链接，从协议的分析角度看，此浏览器首先要进行()。A、IP地址到MAC地址的解析B、建立TCP连接C、域名到IP地址的解析D、建立会话连接，发出获取某个文件的命令标准答案：C知识点解析：如果用户直接使用域名去访问一个WWW服务器，那么首先需要完成对该域名的解析任务。只有获得服务器的IP地址后，WWW浏览器才能与WWW服务器建立连接开始后续的交互。因此，从协议执行过程来说，访问WWW服务器的第一步是域名解析。总结：客户端的WWW浏览器获得WWW服务器的主页并显示在客户端的屏幕上的过程如下(假设访问天勤论坛，域名为www．csbiji．com)：(1)WWW浏览器直接使用名称www．csbiji．com访问该WWW服务器，首先需要完成对该服务器的域名解析，并最终获得天勤论坛服务器对应的IP地址116．255．187．175。(2)WWW浏览器将通过TCP协议与服务器建立一条TCP连接。(3)当TCP连接建立之后，WWW浏览器就向WWW服务器发送要求获取其主页的HTTP请求。(4)WWW服务器在接收到浏览器的HTTP请求之后，将构建所请求的Web页面必需的各种信息，并将信息通过Internet传送给客户端的浏览器。(5)浏览器将收到的信息进行解释，然后将Web页面显示在用户的屏幕上。二、综合应用题(本题共23题，每题1.0分，共23分。)已知一个长度为12的表{Jan，Feb，Mar，Apt，May，June，July，Aug，Sep，Oct，NoV，Dec}：41、试按照表中元素的顺序依次插入一棵初始为空的二叉排序树(字符之间以字典序比较大小)，请画出最终对应的二叉排序树。标准答案：二叉排序树的构建如图6-8所示。知识点解析：暂无解析42、若对表中的元素先进行排序构成有序表(字典序)，试求在等概率情况下对此有序表进行检索时检索成功的平均检索长度。标准答案：按字典序对表中元素进行排序，得：Apr，Aug，Dec，Feb，Jan，July，June，Mar，May，Nov，Oct，Sep，其查找成功的平均查找长度为：(5+7+7+4+3+10+7+4+6+8+7+6)／12=74／12=6．2。知识点解析：暂无解析43、按表中元素的顺序构造一棵平衡二叉树，试求在等概率情况下检索成功的平均检索长度。标准答案：平衡二叉树的形状如图6-9所示。查找成功时的平均查找长度为：(6+5+7+6+4+9+7+3+6+6+5+4)／12=68／12=5．7。知识点解析：暂无解析设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。44、给出算法的基本设计思想。标准答案：基本设计思想：我们知道可以利用弗洛伊德算法(floyd)来求得图中任意两点间的最短路径长度，这里的边权是正数，如果图中所有的边权均为负数，那我们根据弗洛伊德算法求出的便是任意两点间最小的负权路径长度，此时若把所有的边权取相反数，则刚才求得的最短路径长度的相反数一定是现在的最长路径长度；根据此思想，将图G的边权改为它的相反数，得到图G’，然后用floyd算法对G’求出每对顶点间的最短路径，那么图G’中最短路径的相反数即为原图G的最长路径长度。知识点解析：暂无解析45、根据设计思想，采用C或C++语言描述算法，关键之处给出注释。标准答案：算法实现如下：intfloyd(GraphG){／／构造一个新图intdist[n][n]；／／n是已经定义的常量，代表图中顶点的个数for(inti=0；i＜G．VerticeNum()；i++){for(intj=0；j＜G．VerticeNum()；j++){dist[i][j]=-G．weight(i，j);／／初始化新图的边权}}／／弗洛伊德算法for(intk=0；k＜G．G．VerticeNum()；k++){for(inti=0；i＜G．G.VerticeNum()；i++)for(intj=0；j＜G．G．VerticeNum()；j++)if(dist[i][j]＞dist[i][k]+dist[k][j])dist[i][j]=dist[i][k]+dist[k][j]；}／／遍历新图，找出最大路径长度intmax=0；for(inti=0；i＜G．VerticeNum()，i++)for(intj=0；j＜G．VerticeNum()；j++)if(max＜-dist[i][j])max=-dist[i][j];returnmax；}知识点解析：暂无解析46、给出算法的时间复杂度。标准答案：时间复杂度分析：因为用到了floyd算法，而遍历新图用到的是两层循环(小于O(n3))，故时间复杂度为O(n3)(n代表节点的个数)。知识点解析：暂无解析设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：47、主存有多少个块?分为多少个区?标准答案：主存块大小与Cache中块大小相同，所以主存中的块个数=512KB／16B=215块，由于Cache的大小为8KB，所以主存分区个数=512KB／8KB=64个区。知识点解析：暂无解析48、该Cache可容纳多少个块?Cache字地址有多少位?块号和块内地址各多少位?标准答案：Cache中的块个数=8KB／16B=29=512块。Cache大小为8KB=213B，所以Cache地址为13位。由于块大小为16B，所以块内地址占4位，自然块号就占9位。知识点解析：暂无解析49、主存字地址有多少位?区号、区内块号和块内地址各多少位?标准答案：主存中有215个块，所以块号为15位，而块内地址占4位，所以主存地址为15+4=19位，区内块号占9位。由于主存有64个区，所以需要6位来标记区号，如图6-10所示。知识点解析：暂无解析50、主存中的第i块映像到Cache中哪一个块?标准答案：由于每个区有512块，所以主存中第j块映射到Cache中的第jmod512块中。知识点解析：暂无解析51、将主存中的第513块调入Cache，则Cache的块号为多少?它的区号为多少?标准答案：i=jmod29，j=513时，i=513mod29=1，即第1号块。其区号=[513／29]=1，即区号为1，如图6-10所示。知识点解析：暂无解析52、在上一步的基础上，假设送出的主存地址为04011H，是否命中?标准答案：主存地址为04011H=0000100000000010001B，按主存地址划分，其区号=000010B=2，而上一步从主存中读出的数据块在1号区，所以不命中。知识点解析：暂无解析下面是一段MIPS指令序列：1addSt1，$s1，$s0#R[$t1]←R[$s1]+R[Sso]2Sub$t2，Ss0，Stl#R[$t2]←R[$s0]-R[$t1]3add$t3，$t3，$s2#R[St1]←R[$t1]+R[$t2]41w$t4，100($s3)#[$t4]←M[R[$s3]+100]在“取指、译码／取数、执行、访存、写回”的五段流水线处理器中执行上述指令序列，请回答下列问题：53、以上指令序列中，哪些指令之间会发生数据相关。标准答案：因为第1条会更新第2条指令用到的寄存器的值，有可能导致第2条指令取操作数时得到的是更新前的数据，这样，第2条指令就不能正确执行，所以，第1条和第2条指令之间发生数据相关。知识点解析：暂无解析54、若不采取“转发”技术的话，怎样调整这些指令的顺序才能使其性能最好，这时还需在何处，加入几条nop指令才能保证调整后的这段指令序列的执行避免数据冒险。此时，CPI为多少?标准答案：因为第3条、第4条都没有用到第2条更新的值，且第3、4条也未使用第1条指令更新的值，故可以把顺序调整为：1addSt1，$s1，Ss0#[$t1]←R[$si]+R[$s0]2add$t3，$t3，$s2#[$t1]←R[$t1]+R[St2]31w$t4，100($s3)#R[$t4]←M[R[$s3]+100]4sub$t2，Ss0，St1#[$t2]←R[$s0]-R[$t1]此时只有第1条指令把数据写回到寄存器$t1后，第4条指令才能从$t1取到正确的值。所以第1条指令的“写回”流水段后面才应该是第4条指令的“译码／取数”流水段，为此，在第3条和第4条指令之间必须插入1条nop指令，见表6-6。采用上述方法来执行上述4条指令，则需要的时钟周期数为9，故CPI为9／4=2．5。知识点解析：暂无解析在一个分页存储管理系统中，地址空间分页(每页1K)，物理空间分块，设主存总容量是256KB，描述主存分配情况的位示图如图6-2所示(0表示未分配，1表示已分配)，此时作业调度程序选中一个长为5．2K的作业投入内存。试问：55、为该作业分配内存后(分配内存时，首先分配低地址的内存空间)，请填写该作业的页表内容。标准答案：位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，其值为“0”时，表示对应盘块空闲；为“1”时，表示已分配，地址空间分页，每页为1K，则对应盘块大小也为1K，主存总容量为256KB，则可分成256个盘块，长5．2K的作业需要占用6页空间。假设页号与物理块号都是从0开始，则根据位示图，可得到页表内容。页表内容如表6-7所示。知识点解析：暂无解析56、页式存储管理有无内存碎片存在，若有，会存在哪种内存碎片?为该作业分配内存后，会产生内存碎片吗?如果产生，大小为多少?标准答案：页式存储管理中有内存碎片的存在，会存在内部碎片，为该作业分配内存后，会产生内存碎片，因为此作业大小为5．2K，占6页，前5页满，最后一页只占了0．2K的空间，则内存碎片的大小为1K-0．2K=0．8K。知识点解析：暂无解析57、假设一个64MB内存容量的计算机，其操作系统采用页式存储管理(页面大小为4K)，内存分配采用位示图方式管理，请问位示图将占用多大的内存?标准答案：64MB内存，一页大小为4K，则共可分成64KB×1K／4K=16K个物理盘块，在位示图中每一个盘块占1位，则共占16kbit空间，因为1B=8bit，所以此位示图共占2KB空间的内存。知识点解析：暂无解析现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：58、若文件A作为共享文件，系统应采用何种目录结构?画出示意图。标准答案：系统采用二级目录结构即可满足需要，其示意图如图6-11所示。知识点解析：暂无解析59、若学生S1，S2，S3都将自己的程序名起为P，则答案(1)中的目录结构能否满足要求?标准答案：如图6-11所示的二级目录结构能够满足要求。此时用户目录中的P1、P2和P3均改为P即可，从图6-11可知，这3个P均指向各自不同的程序。知识点解析：暂无解析60、对于(2)简要说明系统是如何使每个学生获得他的程序和数据的?标准答案：在学生存取程序和数据时，文件系统会先搜索主文件目录，找到该学生的用户目录后，即可在用户目录中查找指定的文件。比如对学生S1，由路径／S1／P找到的文件就是S1的程序文件，因为它和学生S2的程序文件／S2／P不是同一个文件，所以不会引起冲突。文件／S1／A和文件／S2／A是同一个文件，因此学生S1能够取到所需要的数据。当然，文件A可由3个学生同时打开执行读操作。知识点解析：暂无解析图6-3所示为一个局域网的连接图，每个计算机的IP地址和物理地址见表6-1。61、假设该局域网采用了以太网，需要达到100Mbit／s的数据传输率，那么线路的带宽最小为多少?如果信号在网络中的传播速度是200000km／s，那么该网络的最大长度应该为多少?标准答案：由于以太网是采用曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了到达100Mbit／s的数据传送率，所以需要线路的带宽达到200Mbit／s。以太网帧的最小帧长是64B，那么发送一个最小帧需要的时间T1=64×8／(100×106)s；另外，假设网络的最大长度为L，那么信号沿网络传输的往返时延T2=2L／(200×106)s。要使得不出错，就必须满足T1≥T2，可以计算得到该网络的最大长度L=512m。知识点解析：暂无解析62、一个IP数据包的源地址和目的地址分别是192．168．48．19和192．168．48．21，为了发送该IP包，源主机应该先发送什么帧?该分组的以太网帧的源地址、目的地址各是什么?标准答案：在以太网中发送数据，首先要知道对方的以太网地址。所以主机A需要先广播一个ARP帧来获得主机C的物理地址。由于ARP要获取主机C的物理地址是采用广播的方式，所以需要使用全“1”的地址作为目的MAC地址，即FF．FF．FF．：FF．FF．FF，源地址为主机A的MAC地址，即EE．24．D3．D1．B4．A4。知识点解析：暂无解析63、假设计算机B是天勤论坛的Web服务器，计算机A分别在如下4个条件使用非持久连接模式和持久连接模式向计算机B访问天勤论坛中的一个Web页面。4个条件如下：条件一：测试的：RTT平均值为150ms，一个gif对象的平均发送时延为35ms。条件二：一个Web页面中有10个gif图片，Web页面的基本HTML文件、HTTP请求报文、TCP握手报文大小忽略不计。条件三：TCP三次握手的第三步中捎带一个HTTP请求。条件四：使用非流水线方式。试计算使用非持久连接模式和持久连接模式分别需要多少时间?标准答案：非持久连接模式：首先，因为Web页面的基本HTML文件、HTTP请求报文、TCP握手报文大小忽略不计，所以就无需计算其发送时延。TCP前两次握手消耗一个RTT=150ms，接着第三次握手的时候捎带一个HTTP请求，消耗RTT／2，传送htm1文件消耗RTT／2，所以第一次建立TCP连接并传送html文件所需的时间为150ms+150ms=300ms。而后面传送10个gif图片时，需要再建立10次TCP连接。传送1个gif图片需要的时间为(150+150+35)ms=335ms，也就是传送10个gif图片需要3350ms。可以算得总时间为300ms+3350ms=3650ms。知识点解析：暂无解析计算机专业（基础综合）模拟试卷第2套一、单选题(本题共40题，每题1.0分，共40分。)1、假设n是描述问题规模的非负整数，下面程序片段的时间复杂度为()。voidfun(intn){inti，j，k；for(i=1;i＜=n;i++)for(j=1;j＜=n;j++){k=1；while(k＜=nk=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。所以，T(n)=∑ni=1∑nj=1m=m∑ni=1∑nj=1=mn2=n2log5n=O(n2log5n)2、以下说法正确的是()。Ⅰ．带头结点的循环双链表L为空的条件是：L→prior==L&&L→next==LⅡ．线性表的插入和删除总是伴随着大量数据的移动Ⅲ．只有删除静态链表的尾结点才不需要移动元素Ⅳ．若线性表采用链式存储结构，要求内存中可用存储单元的地址必须不连续A、仅ⅠB、仅Ⅰ、ⅡC、仅Ⅱ、ⅢD、Ⅰ、Ⅱ、Ⅲ和Ⅳ标准答案：A知识点解析：Ⅰ：循环双链表为空时头结点如图1-6所示。可见当满足L→prio=L&&L→next=L时，双链表为空，并且循环双链表与循环单链表一样，没有空指针域，所以Ⅰ正确。Ⅱ：链表也是线性表，链表的插入和删除操作不需要大量的数据移动，所以Ⅱ错误。Ⅲ：静态链表尽管使用的是数组存储方式，但是数据之间是靠指针(游标)相互关联的，故不管是删除静态链表中的哪一个结点，都不需要移动元素，只需要修改指针即可，所以Ⅲ错误。Ⅳ：线性表采用链表存储，前驱和后继之间的联系需要依靠由前驱指向后继的指针，而与前驱和后继在内存中的物理位置无关，因此对于整条链表的存储，不需要划分一块连续的存储空间；但将链表中结点挨个连续存储在一片空间中也未尝不可。对于线性表的链式存储，连续或者不连续的存储空间都能满足要求，所以Ⅳ错误。3、循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear(且队尾指针rear指向队尾元素的下一个元素)，则当前队列中的元素个数是()。A、(rear-front+m)％mB、(rear-front+1)％mC、rear-front-1D、rear-front标准答案：A知识点解析：因为是循环队列，所以应该分为rear＞front和rear＜front两种情况来讨论。(1)当rear＞front时，队列中元素个数为rear-front=(rear-front+m)％m因为0＜rear-front＜m，所以rear-ront+m与m取余后结果还是rear-front。(2)当rear＜front时，队列中元素个数为m-(front-rear)=rear-front+m=(rear-front+m)％m因为0＜rear-front+m＜m，所以rear-front+m与m取余后结果还是rear-front+m。综合(1)、(2)可知，A选项正确。4、下列关于二叉树的叙述中正确的是()。Ⅰ．对于任何一棵二叉树，叶子结点数都是度为2的结点数加1Ⅱ．二叉树的左右子树不可以任意地交换Ⅲ．二叉树只适合使用链式结构存储，不可能用顺序结构存储Ⅳ．结点按层序编号的二叉树，第i个结点的左孩子(假设存在)的编号为2iA、仅Ⅰ、ⅡB、仅ⅡC、仅Ⅱ、ⅣD、仅Ⅱ、Ⅲ标准答案：B知识点解析：Ⅰ：Ⅰ的描述只有在非空二叉树的情况下才成立，所以考生在做这种概念题目的时候一定要先想到这种特殊情况，所以Ⅰ错误。Ⅱ：二叉树的左右子树是有顺序的，不能随意交换，所以Ⅱ正确。Ⅲ：一般的二叉树确实不能使用顺序结构存储，但是完全二叉树和满二叉树一般都使用顺序结构存储，所以Ⅲ错误。Ⅳ：该结论只对完全二叉树才成立，所以Ⅳ错误。综上所述，只有Ⅱ正确。5、若二叉树是由森林变换而来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点有()。A、n-1B、nC、n+1D、n+2标准答案：C知识点解析：由于森林中每一个非终端结点(根结点除外)的所有儿子在转换成二叉树之后，只有一个儿子的右孩子为空，根结点中本身有一个在转化成二叉树后右孩子为空，如图1-7所示，所以共有n+1个。6、根据使用频率为5个字符设计的赫夫曼编码不可能是()。A、000，001，010，011，1B、0000，0001，001，01，1C、000，001，01，10，11D、00，100，101，110，111标准答案：D知识点解析：赫夫曼树中只有度为0或2的结点，由D选项可以画出对应的二叉树，如图1-8所示。由赫夫曼树的性质可知，树中不应该含度为1的结点，因此D选项不可能。7、在具有n个顶点的图G中，若最小生成树不唯一，则()。Ⅰ．G的边数一定大于n-1Ⅱ．G的权值最小的边一定有多条Ⅲ．G的最小生成树代价不一定相等A、仅ⅠB、仅Ⅰ、ⅢC、仅Ⅰ、ⅡD、仅Ⅲ标准答案：A知识点解析：最小生成树边的权值之和最小，若两棵树同时为最小生成树，那么它们的边的权值之和一定相等，故Ⅲ错误；既然最小生成树不唯一，并且最小生成树的边都为n-1条，说明图G的边数一定会大于n-1，故Ⅰ正确；最小生成树不唯一，和G的权值最小的边的条数没有任何关系，故Ⅱ错误。8、图1-1中强连通分量的个数为()。A、2B、3C、4D、5标准答案：C知识点解析：在有向图G中，如果两个顶点vi、vj间有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。本题中可以看出v2、v3、v4同属于一个连通分量，另外v1、v5、v6各自属于一个强连通分量，所以共有4个强连通分量。9、在一棵二叉排序树上，查找关键字为35的结点，依次比较的关键字有可能是()。A、28，36，18，46，35B、18，36，28，46，35C、46，28，18，36，35D、46，36，18，28，35标准答案：D知识点解析：可以根据选项画出查找路线上的结点，根据二叉排序树的规定来排除不满足条件的选项。根据题目选项所得查找路线如图1-9所示。A选项中28的右子树中出现了小于它的18，不满足二叉排序树规定，排除。B选项中36的左子树中出现了大于它的46，不满足二叉排序树规定，排除。C选项中28的左子树中出现了大于它的36，不满足二叉排序树规定，排除。补充：在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度相当于折半查找的时间复杂度，即O(log2n)。平衡二叉树的查找效率最高，因为二叉树的查找效率取决于二叉树的高度，对于结点个数相同的二叉树，平衡二叉树的高度最小。10、排序趟数与序列的原始状态无关的排序方法是()。Ⅰ．直接插入排序Ⅱ．简单选择排序Ⅲ．冒泡排序Ⅳ．基数排序A、仅Ⅰ、ⅢB、仅Ⅰ、Ⅱ、ⅣC、仅Ⅰ、Ⅱ、ⅢD、仅Ⅰ、Ⅳ标准答案：B知识点解析：直接插入排序：每趟排序都是插入一个元素，所以排序趟数固定为n-1(n为元素数)。简单选择排序：每趟排序都是选出一个最小(或最大)的元素，所以排序趟数固定为n-1(n为元素数)。交换类的排序：其趟数和原始序列状态有关，所以冒泡排序与初始序列有关。基数排序：每趟排序都要进行“分配”和“收集”，排序趟数固定为d(d为组成元素的关键字位数)。综上所述，Ⅰ、Ⅱ、Ⅳ都是无关的，所以选B。11、下列关于外部排序说法正确的是()。A、内存与外设交换信息的时间只是外部排序总时间的一小部分B、外部排序就是在外存上进行排序，无需内存参与C、败者树是一棵完全二叉树D、置换-选择排序得到的初始归并段长度一定相等标准答案：C知识点解析：A：影响外部排序时间的主要因素就是内存与外设交换信息的总次数，所以A错误。B：外部排序也是在内存上进行排序，只不过需要分为多步而已，所以B错误。C：从败者树的构建方式可知，败者树是一棵完全二叉树，所以C正确。12、图1-2中计算机硬件系统基本组成部件①、②、③、④和⑤的名称分别是()。A、①控制器、②运算器、③存储器、④输入设备、⑤输出设备B、①运算器、②控制器、③存储器、④输入设备、⑤输出设备C、①运算器、②存储器、③控制器、④输入设备、⑤输出设备D、①运算器、②控制器、③存储器、④输出设备、⑤输入设备标准答案：B知识点解析：图中实线框为CPU，而CPU包含五大部件中的运算器和控制器，排除C选项。控制器为计算机提供工作统一的时钟及其发出各种控制命令来协调计算机的各部件自动地工作，所以控制器应该与其他四大部件相连，可得①为运算器，②为控制器。最后，根据数据的流向可以判断，④为输入设备，⑤为输出设备。剩下③为存储器。13、已知小写英文字母“a”的ASCII码值为61H，现字母“g”被存放在某个存储单元中，若采用偶校验(假设最高位作为校验位)，则该存储单元中存放的十六进制数是()。A、167HB、E6HC、67HD、E7H标准答案：D知识点解析：由于“a”，的ASCII码值为61H，而“g”是第7个字母，所以可以得到“g”的ASCII码值应为61H+6=67H=1100111B。现在“g”的ASCII码值中有5个“1”，按照偶校验的规则，应该在最高位上添加一个1，使得“1”的个数为偶数个，最后可得该存储单元中存放的十六进，制数为E7H(11100111)。14、页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小为4KB，地址变换过程如图1-3所示，图中逻辑地址用十进制数表示。逻辑地址经过变换后，十进制数物理地址a应为()。A、33220B、8644C、4548D、2500标准答案：A知识点解析：本题考查的是页式存储系统管理中的地址变换知识。在页式存储系统管理中，逻辑地址除以页的大小，然后向下取整为页号，取余为页内地址。本题页面的大小为4KB，逻辑地址8644除以4096，取整为2，取余为452。页号为2，查页表得物理块号为8。因此，a的有效地址为8×4096+452=33220。15、下列关于Cache和虚拟存储器的说法中，错误的有()。Ⅰ．当Cache失效(即不命中)时，处理器将会切换进程，以更新Cache中的内容Ⅱ．当虚拟存储器失效(如缺页)时，处理器将会切换进程，以更新主存中的内容Ⅲ．Cache和虚拟存储器由硬件和OS共同实现，对应用程序员均是透明的Ⅳ．虚拟存储器的容量等于主存和辅存的容量之和A、Ⅰ、ⅣB、Ⅲ、ⅣC、Ⅰ、Ⅱ、ⅢD、Ⅰ、Ⅲ、Ⅳ标准答案：D知识点解析：Cache和虚拟存储器的原理是基于程序访问的局部性原理，但它们实现的方法和作用均不相同。Cache失效与虚拟存储器失效的处理方法不同，Cache完全由硬件实现，不涉及软件端；虚拟存储器由硬件和OS共同完成，缺页时才会发出缺页中断，故Ⅰ错误，Ⅱ正确，Ⅲ错误。在虚拟存储器中，主存的内容只是辅存的一部分，Ⅳ错误。16、在计算机体系结构中，CPU内部包括程序计数器(PC)、存储器数据寄存器(MDR)、指令寄存器(IR)和存储器地址寄存器(MAR)等。若CPU要执行的指令为MOVR0，#100(即将数值100传送到寄存器R0中)，则CPU首先要完成的操作是()。A、100→ROB、100→MDRC、PC→MARD、PC→IR标准答案：C知识点解析：取指周期完成的微操作序列是公共的操作，与具体指令无关。CPU首先需要取指令，取指令阶段的第一个操作就是将指令地址(PC中的内容)送往存储器地址寄存器。题干中虽然给出了一条具体的指令“MOVR0，#100”，实际上CPU首先要完成的操作是取指令，与具体指令没有关系。17、某机器采用16位单字长指令，采用定长操作码，地址码为5位，现已定义60条二地址指令，那么单地址指令最多有()条。A、4B、32C、128D、256标准答案：A知识点解析：首先可以计算出操作码字段的长度为16-5-5=6。所以一共可以定义26=64条指令，既然二地址指令占了60条，且是定长操作码，故单地址指令最多可以有64-60=4条，所以选A。18、在一条无条件跳转指令的指令周期内，程序计数器(PC)的值被修改了()次。(注：指令均为单字长指令，且按字寻址)A、1B、2C、3D、不能确定标准答案：B知识点解析：(1)取指周期结束后，PC的值自动加1(因为指令为单字长指令，且按字寻址，故PC+1)。(2)在执行周期中，PC的值修改为要跳转到的地址。综上所述，在一条无条件跳转指令的指令周期内，程序计数器(PC)的值被修改了2次。19、当有中断源发出请求时，CPU可执行相应的中断服务程序，以下可以提出中断请求的是()。Ⅰ．外部事件Ⅱ．CacheⅢ．浮点运算下溢Ⅳ．浮点运算上溢A、仅Ⅰ、ⅢB、仅Ⅱ、Ⅲ、ⅣC、仅Ⅰ、ⅣD、仅Ⅰ、Ⅲ、Ⅳ标准答案：C知识点解析：Ⅰ：外部事件是可以提出中断请求的，如可以通过敲击键盘来中止现在正在运行的程序，这个就可以看作一个中断，所以Ⅰ可以。Ⅱ：Cache是属于存储设备，不能提出中断请求，所以Ⅱ不可以。Ⅲ、Ⅳ：浮点运算下溢，可以当作机器零处理，不需要中断来处理；而浮点运算上溢，必须中断来做相应的处理，所以Ⅲ不可以，Ⅳ可以。20、假定一个高速缓存(M1)和存储器(M2)的层次结构有以下性能。M1：16KB，存取时间为50ns；M2：1MB，存取时间为400ns。高速缓存块为8B，组大小为256个字，采用组相联映射，高速缓存命中率h=0．95时的有效存储器存取时间是()。A、50nsB、60nsC、70nsD、80ns标准答案：C知识点解析：平均存取时间是按照对不同的存储模块的存取时间进行加权平均而得，即T=T1+(1-H)T2=50+(1-95％)×400=70ns。这里H是高速缓存块的命中率。本题设置了很多干扰数据，平均存取时间与两个存储模块的存取时间以及高速缓存命中率有关，在已知命中率的情况下，对于采用什么形式的映射和存储容量来说已经不重要了；另外还有一点非常重要：对于以上公式的解读，可以这样来理解，无论怎么存取，每次肯定是要访问高速缓存块的，这是一部分，另外还有一部分(1-H)的概率要访问存储器；当然也可以分为命中时的存取时间HT1加上不命中时的存取时间(1-H)(T1+T2)。21、下面关于PCI总线的基描述中，错误的有()。Ⅰ．PCI总线是一个与处理器性能相关的高速外围总线Ⅱ．PCI总线可对传输信息进行奇偶校验Ⅲ．PCI设备一定是主设备Ⅳ．系统中允许有多条PCI总线A、仅Ⅰ、ⅡB、仅Ⅱ、ⅢC、仅Ⅲ和ⅣD、仅Ⅰ、Ⅲ标准答案：D知识点解析：PCI总线与CPU及时钟频率都无关，故I错误；PCI总线支持即插即用并且可对数据和地址进行奇偶校验，并且PCI总线采用猝发传送方式，故Ⅱ正确；主设备指获得总线控制权的设备，所以PCI设备不一定都是主设备，故Ⅲ错误；系统中肯定允许有多条PCI总线，以此来提升计算机的效率，故Ⅳ正确。22、下列说法正确的是()。A、在统一编址方式下，访问主存储器和访问I／O设备是通过不同的指令来区分的B、计算机的外围设备就是指输入和输出设备C、中断隐指令属于程序控制型指令D、在中断服务程序中，恢复现场之前需要关中断标准答案：D知识点解析：A：在统一编址方式下，访问主存储器和访问I／O设备是通过不同的地址码来区分的；在独立编址方式下，访问主存储器和访问I／O设备是通过不同的指令来区分的，所以A错误。B：除主机外的硬件装置统称为外围设备或外部设备，包括输入、输出设备和外存储器，所以B错误。C：中断隐指令并不是一条真正的指令，因此不可能把它预先编入程序中，只能在响应中断时由硬件直接控制执行，它就好像是隐藏于机器中的指令，只有在响应中断时被执行。中断隐指令不