王道计算机考研试卷2

2015年计算机专业基础综合考试最后8套模拟题·5·计算机专业基础综合考试模拟试卷（二）计算机专业基础综合考试模拟试卷（二）一、单项选择题：第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1．设n是描述问题规模的正整数，下列程序片段的时间复杂度是（）。y=0;while(n=(y+1)*(y+1))y++;A．O(log2n)B．O(n)C．O(nlog2n)D．O(n)2．循环队列用数组A[0…m-1]存放其元素值，头尾指针分别为front和rear，front指向队头元素，rear指向队尾元素的下一个元素，其移动按数组下标增大的方向进行（rear!=m-1时），则当前队列中的元素个数是（）。A．(rear-front+m)%mB．(rear-front+1)%mC．read-front-1D．read-front3．将5个字母“ooops”按此顺序进栈，则有（）种不同的出栈顺序可以仍然得到“ooops”。A．1B．3C．5D．64．设高度为100的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数最少为（）。A．100B．201C．199D．2005．由某种序列可以唯一的确定一棵二叉树，不能唯一的确定一棵二叉树是（）。A．先序序列和中序序列B．后序序列和中序序列C．中序序列和层序序列D．先序序列和层序序列6．在含有15个结点的平衡二叉树上，查找关键字为28（存在该结点）的结点，则依次比较的关键字有可能是（）。A．30,36B．38,48,28C．48,18,38,28D．60,20,50,40,38,287．对于一组权值都相等的16个字母，构造相应的哈夫曼树，这棵哈夫曼树是一棵（）。A．完全二元树B．一般二元树C．满二元树D．以上都不正确8．下列关于B-树和B+树的叙述中，不正确的是（）。A．B-树和B+树都能有效地支持顺序查找B．B-树和B+树都是平衡的多叉树C．B-树和B+树都能有效地支持随机查找D．B-树和B+树都可以用于文件索引结构9．对一组数据（25,84,21,47,15,27,68,35,20）进行排序，前三趟的排序结果如下：第一趟：20,15,21,25,47,27,68,35,84第二趟：15,20,21,25,35,27,47,68,84第三趟：15,20,21,25,27,35,47,68,84则所采用的排序方法是（）。A．选择排序B．希尔排序C．归并排序D．快速排序10．对一组数据（84,47,15,21,25）排序，数据在排序的过程中的变化如下：（1）8447152125（2）2547152184（3）2125154784（4）1521254784则所采用的排序方法是（）。A．堆排序B．冒泡排序C．快速排序D．插入排序11．下列排序方法中，时间性能与待排序记录的初始状态无关的是（）。A．插入排序和快速排序B．归并排序和快速排序C．选择排序和归并排序D．插入排序和归并排序12．对汇编语言程序员来说，以下部件中不透明的是（）。Ⅰ．指令缓冲器Ⅱ．移位器Ⅲ．通用寄存器Ⅳ．中断字寄存器Ⅴ．乘法器Ⅵ．先行进位链A．Ⅰ、Ⅱ和ⅢB．Ⅳ、Ⅴ和ⅥC．Ⅲ和ⅣD．Ⅰ、Ⅱ、Ⅴ和Ⅵ13．一个8位的二进制整数，若采用补码表示，且由3个“1”和5个“0”组成，则最小值为（）。A．-127B．-32C．-125D．-314．单精度IEEE754标准规格化的float类型所能表示的最接近0的负数是（）。A．-2−126B．-(2-2−23)2−126C．-(2-2−23)2−127D．-2−12715．下列关于DRAM和SRAM的说法中，错误的是（）。2015年计算机专业基础综合考试最后8套模拟题·6·计算机专业基础综合考试模拟试卷（二）Ⅰ．SRAM不是易失性存储器，而DRAM是易失性存储器Ⅱ．DRAM比SRAM集成度更高，因此读写速度也更快Ⅲ．主存只能由DRAM构成，而高速缓存只能由SRAM构成Ⅳ．与SRAM相比，DRAM由于需要刷新，所以功耗较高A．Ⅱ、Ⅲ和ⅣB．Ⅰ、Ⅲ和ⅣC．Ⅰ、Ⅱ和ⅢD．Ⅰ、Ⅱ、Ⅲ和Ⅳ16．某计算机的存储系统由Cache-主存系统构成，Cache的存取周期为10ns，主存的存取周期为50ns。在CPU执行一段程序时，Cache完成存取的次数为4800次，主存完成的存取次数为200次，该Cache-主存系统的效率是（）。（设Cache和主存不能同时访问）A．0.833B．0.856C．0.958D．0.86217．在运算类的零地址指令中，它的操作数来自（）。A．暂存器和总线B．寄存器C．暂存器和ALUD．栈顶和次栈顶18．在微程序控制方式中，以下说法正确的是（）。Ⅰ．采用微程序控制器的处理器称为微处理器Ⅱ．每一条机器指令由一个微程序来解释执行Ⅲ．在微指令的编码中，执行效率最低的是直接编码方式Ⅳ．水平型微指令能充分利用数据通路的并行结构A．Ⅰ和ⅡB．Ⅱ和ⅣC．Ⅰ和ⅢD．Ⅱ、Ⅲ和Ⅳ19．当微指令采用分段编码时，我们将互斥性微命令（）。A．放在同一段中B．用多级译码来区分C．放在不同段中D．任意存放20．在下列各种情况中，最应采用异步传输方式的是（）。A．I/O接口与打印机交换信息B．CPU与主存交换信息C．CPU和PCI总线交换信息D．由统一时序信号控制方式下的设备21．CPU响应中断时，保护两个关键的硬件状态是（）。A．PC和PSWB．PC和IRC．AR和IRD．AR和PSW22．1K*8位ROM芯片和1K*8位RAM芯片的引脚（含地址与数据）的总数分别是（）。A．13和18B．13和13C．18和18D．18和1323．在操作系统中，以下只能在核心态下处理执行的指令是（）。A．读时钟B．寄存器清零C．系统调用D．取数24．下列各种调度算法中，属于基于时间片的调度算法的是（）。Ⅰ．时间片轮转法Ⅱ．多级反馈队列调度算法Ⅲ．抢占式调度算法Ⅳ．FCFS（先来先服务）调度算法Ⅴ．高响应比优先调度算法A．Ⅰ和ⅡB．Ⅰ、Ⅱ和ⅣC．Ⅰ、Ⅲ和ⅣD．Ⅰ、Ⅱ和Ⅲ25．在某个十字路口，每个车道只允许一辆汽车通过，且允许直行、左拐和右拐，如图1所示。如果把各个方向的车看成进程，则需要对这些进程进行同步，那么这里临界资源个数至少应该有（）个。A．1B．2C．4D．不确定图1十字路口车道示意图26．对于两个并发进程，设互斥信号量为mutex，若mutex=0，则表示（）。A．没有进程进入临界区B．有一个进程进入临界区C．有一个进程进入临界区，另一个进程等待进入D．有一个进程在等待进入27．有两个优先级相同的并发程序P1和P2，它们的执行过程如下所示，假设，当前信号量s1=0，s2=0．当前的z=2，进程运行结束后，x、y和z的值分别是（）。进程P1进程P2……y=1;x=1y=y+2;x=x+1;z=y+1;P(s1);V(s1);x=x+y;P(s2);z=x+z;y=z+y;V(s2);…………A．5,9,9B．5,9,4C．5,12,9D．5,12,428．对外存对换区的管理应以（）为主要目标。2015年计算机专业基础综合考试最后8套模拟题·7·计算机专业基础综合考试模拟试卷（二）A．提高系统吞吐量B．提高存储空间的利用率C．降低存储费用D．提高换入、换出速度29．下列叙述中错误的是（）。Ⅰ．在请求分页存储管理中，若把页面的大小增加一倍，则缺页中断次数会减少一半Ⅱ．分页存储管理方案在逻辑上扩充了主存容量Ⅲ．在分页存储管理中，减少页面大小，可以减少内存的浪费，所以页面越小越好Ⅳ．一个虚拟存储器，其地址空间的大小等于辅存的容量加上主存的容量A．Ⅰ、Ⅲ和ⅣB．Ⅱ、Ⅲ和ⅣC．Ⅲ和ⅣD．Ⅰ、Ⅱ、Ⅲ和Ⅳ30．一个64位的计算机系统中，地址线宽为64位，实际使用的虚拟地址空间的大小是248，若采用虚拟页式存储管理，每页的大小为213，即8KB，页表表项长为8字节，采用多级页表进行管理，那么多级页表的级次最小是（）。A．3B．4C．5D．631．某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为1024B，每个盘块索引号占用4字节，请问在该文件系统中，最大的文件长度约为（）。A．16GBB．32GBC．8GBD．以上均不对32．设一个磁道访问请求序列为55,58,39,18,90,160,150,38,184，磁头的起始位置为100，若采用SSTF（最短寻道时间优先）算法，则磁头移动（）个磁道。A．55B．184C．200D．24833．在OSI参考模型中，实现系统间二进制信息块的正确传输，为上一层提供可靠、无错误的数据信息的协议层是（）。A．物理层B．数据链路层C．网络层D．传输层34．设信道带宽为4kHz，信噪比为30dB，按照香农定理，信道的最大数据速率约等于（）。A．10kb/sB．20kb/sC．30kb/sD．40kb/s35．以太网中，当数据传输率提高时，帧的发送时间就会相应的缩短，这样可能会影响到冲突的检测。为了能有效地检测冲突，可以使用的解决方案有（）。A．减少电缆介质的长度或减少最短帧长B．减少电缆介质的长度或增加最短帧长C．增加电缆介质的长度或减少最短帧长D．增加电缆介质的长度或增加最短帧长36．若子网掩码是255.255.192.0，那么下列主机必须通过路由器才能与主机129.23.144.16通信的是（）。A．129.23.191.21B．129.23.127.222C．129.23.130.33D．129.23.148.12737．在基于TCP/IP模型的分组交换网络中，每个分组都可能走不同的路径，所以在分组到达目的主机后应该重新排序；又由于不同类型的物理网络的MTU不同，所以一个分组在传输的过程中也可能需要分段，这些分段在到达目的主机后也必须重组。对于分组的排序和分段的重组，下列说法正确的是（）。A．排序和重组工作都是由网络层完成B．排序和重组工作都是由传输层完成C．排序工作由网络层完成，而重组工作由传输层完成D．排序工作由传输层完成，而重组工作由网络层完成38．ARP的作用是由IP地址求MAC地址，某节点响应其他节点的ARP请求是通过（）发送的。A．单播B．组播C．广播D．点播39．下列关于TCP协议的叙述中，错误的是（）。Ⅰ．TCP是一个点到点的通信协议Ⅱ．TCP提供了无连接的可靠数据传输Ⅲ．TCP将来自上层的字节流组织成IP数据报，然后交给IP协议Ⅳ．TCP将收到的报文段组成字节流交给上层A．Ⅰ和ⅢB．Ⅰ、Ⅱ和ⅢC．Ⅱ和ⅢD．Ⅰ、Ⅱ、III和Ⅳ40．A和B建立TCP连接，MSS为1KB。某时，慢开始门限值为2KB，A的拥塞窗口为4KB，在接下来的一个RTT内，A向B发送了4KB的数据（TCP的数据部分），并且得到了B的确认，确认报文中的窗口字段的值为2KB，那么，请问在下一个RTT中，A最多能向B发送的数据（）。A．2KBB．8KBC．5KBD．4KB二、综合应用题：第41～47题，共70分。41．（11分）如下图所示：2015年计算机专业基础综合考试最后8套模拟题·8·计算机专业基础综合考试模拟试卷（二）（1）写出该图的邻接矩阵。（2）写出全部拓扑序列。（3）以V1为源点，以V8为终点，给出所有事件（和活动）允许发生的最早时间和最晚时间，并给出关键路径。（4）求V1结点到各点的最短路径和距离。42．（13分）将一个数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个已排好序数组的一个旋转，求该旋转数组的最小元素。如，数组{3,4,5,1,2}为有序数组{1,2,3,4,5}的一个旋转数组，该数组的最小值为1。（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。43．（11分）某计算机的主存地址位数为16位，按字节编址。假定数据Cache中最多存放32个主存块，采用2-路组相联方式，块大小为16B，每块设置了1位有效位。采用一次性写回策略，为此每块设置了1位“脏”位。请问：（1）主存地址中标记（Tag）、组号（Index）和块