1、2016年全国硕士研究生人学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1.已知表头元素为c的单链表在内存中的存储状态如下表所示。地址元素链接地址1000Ha1010H1004Hb100CH1008Hc1000H100CHdNULL1010He1004H1014H现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是A.1010H,1014H,1004HB.1010H,1004H,1014HC.1014H,1010H,1004H
2、D.1014H,1004H,1010H2.已知一个带有表头结点的双向循环链表L,结点结构为prevdata next,其中，prev和ext分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是A.p-next-prev=p-prev;p-prev-next=p-prev;free(p);B.p-next-prev=p-next;p-prev-next=p-next;free(p);C.p-next-prev=p-next;p-prev-next=p-prev;free(p);D.p-next-prev=p-prev;p-prev-next=p-next;free
3、(p);3.设有下图所示的火车车轨，入口到出口之间有条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为19的9列列车，驶入的次序依次是8,4,2,5,3,9,1,6,7。若期望驶出的次序依次为19，则n至少是761935248.交过t拉本p时冬987654321nii atduuh4ii中mmit中入口交女ti9出口轨道A.2B.3C.4D.54.有一个100阶的三对角矩阵M,其元素m,(1i100,1j100)按行优先依次压缩存入下标从0开始的一维数组N中。元素m30,30在N中的下标是A.86B.87C.881D.895.若森林F有15条边、25个结点，则F包含树的个数
4、是A.8B.9C.10D.116.下列选项中，不是下图深度优先搜索序列的是A.V1,V5,V4 V3,V2B.V1,V3,V2,V5,V4C.VI,V2,V5,V4 V3D.V1,V2,V3,V4,Vs7.若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是A.O(n)B.O(n+e)C.0n3)D.O(n*e)8.使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是A.5,2,3,4,6B.5,2,3,6,4C.5,2,43,6D.5,2,6,3,49.在有n(n1000)个元素的升序数组A中查找关键字x。查找算法的
5、伪代码如下所示。k=0:while(kn Akx)k=k+3;iE(kn且Ak=)查找成功：e1se1f(k-1n且Ak-1=x)查找成功：e1se1f(k-2n且Ak-2=x)查找成功；else查找失败：本算法与折半查找算法相比，有可能具有更少比较次数的情形是A.当x不在数组中B.当x接近数组开头处C.当x接近数组结尾处D.当x位于数组中间位置10.B+树不同于B树的特点之一是A.能支持顺序查找B.结点中含有关键字C.根结点至少有两个分支D.所有叶结点都在同一层上11.对10TB的数据文件进行排序，应使用的方法是A.希尔排序B.堆排序C.快速排序D.归并排序12.将高级语言源程序转换为机器级
6、目标代码文件的程序是020A.汇编程序B.链接程序C.编译程序D.解释程序13.有如下C语言程序段short si=-32767;unsigned short usi si;执行上述两条语句后，usi的值为A.-32767B.32767C.32768D.3276914.某计算机字长为32位，按字节编址，采用小端（Little Endian)方式存放数据。假定有一个double型变量，其机器数表示为1122334455667788H,存放在00008040H开始的连续存储单元中，则存储单元00008046H中存放的是A.22HB.33HC.77HD.66H15.有如下C语言程序段：for(k=0
7、;k1000;k+)ak=ak+32;若数组a及变量k均为int型，int型数据占4B,数据Cache采用直接映射方式，数据区大小为1KB、块大小为l6B,该程序段执行前Cache为空，则该程序段执行过程中访问数组a的Cache缺失率约为A.1.25%B.2.5%C.12.5%D.25%16.某存储器容量为64KB,按字节编址，地址4000H5FFFH位ROM区，其余为RAM区。若采用8K4位的SRAM芯片进行设计，则需要该芯片的数量是A.7B.8C.14D.1617.某指令格式如下所示。OPM其中M为寻址方式，I为变址寄存器编号，D为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址
8、是A.I+DB.(+DC.(+D)D.()+D18.某计算机主存空间为4GB,字长为32位，按字节编址，采用32位字长指令字格式。若指令按字边界对齐存放，则程序计数器(PC)和指令寄存器(R)的位数至少分别是A.30、30B.30、32C.32、30D.32、3219.在无转发机制的五段基本流水线（取指、译码/读寄存器、运算、访写回寄存器）中，下列指令序列存在数据冒险的指令对是I1:add R1,R2,R3;(R2)+(R3)-R1I2:add R5,R2,R4;(R2)+(R4)-R5I3:add R4,R5,R3;(R5)+(R3)-R4I4:add R5,R2,R6;(R2)+(R6)-
9、R5A.I1和2B.I2和I3C.I2和I4D.I3和I420.单周期处理器中所有指令的指令周期为一个时钟周期。下列关于单周期处理器的叙述中，错误的是A.可以采用单总线结构数据通路B.处理器时钟频率较低C.在指令执行过程中控制信号不变D.每条指令的CPI为121.下列关于总线设计的叙述中，错误的是A.并行总线传输比串行总线传输速度快B.采用信号线复用技术可减少信号线数量。021。C.采用突发传输方式可提高总线数据传输率D.采用分离事务通信方式可提高总线利用率22.异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或异常情况的叙述中，错误的是A.“访存时
10、缺页”属于中断B.“整数除以0”属于异常C.“DMA传送结束”属于中断D.“存储保护错”属于异常23.下列关于批处理系统的叙述中，正确的是I.批处理系统允许多个用户与计算机直接交互，批处理系统分为单道批处理系统和多道批处理系统I.中断技术使得多道批处理系统和I/O设备可与CPU并行工作A.仅、IB.仅C.仅I、D.仅I、I24.某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms,且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是。A.15msB.17msC.22msD.27ms25.系统中有3个不同的临界
11、资源R1、R2和R3,被4个进程p1、p2、p3及p4共享。各进程对资源的需求为：p1申请R1和R2,p2申请R2和R3,p3申请R1和R3,p4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是-9A.1B.2C.3D.426.某系统采用改进型CLOCK置换算法，页表项中字段A为访问位，M为修改位。A0表示页最近没有被访问，A=1表示页最近被访问过。M=0表示页没有被修改过，M=1表示页被修改过。按(A,M)所有可能的取值，将页分为四类：(0,0)、(1,0)、(0,1)和(1,1)，则该算法淘汰页的次序为A.(0,0),(0,1),(1,0),(1,1)B.(0,0),(1,0),(0
12、,1),(1,1)C.(0,0),(0,1),(1,1),(1,0)D.(0,0),(1,1),(0,1),(1,0)27,使用TSL(Test and Set Lock)指令实现进程互斥的伪代码如下所示。dof0while(TSL(&lock);critical section;lock=FALSE;while(TRUE);下列与该实现机制相关的叙述中，正确的是A,退出临界区的进程负责唤醒阻塞态进程B.等待进入临界区的进程不会主动放弃CPUC.上述伪代码满足“让权等待”的同步准则D.while(TSL(&lock)语句应在关中断状态下执行28.某进程的段表内容如下所示。022段号段长内存起始
13、地址权限状态01006000只读在内存200一读写不在内存23004000读写在内存当访问段号为2、段内地址为400的逻辑地址时，进行地址转换的结果是A.段缺失异常B.得到内存地址4400C.越权异常D.越界异常29.某进程访问页面的序列如下所示。1,3,4,5,6,0,3,2,3,240,4,0,3,2,9,2,1时间若工作集的窗口大小为6，则在t时刻的工作集为A.6,0,3,2B.2,3,0,4C.0,4,3,2,9D.4,5,6,0,3,230.进程P1和P2均包含并发执行的线程，部分伪代码描述如下所示。/进程P1/进程P2int x=0;int x=0;Thread1()Thread3
14、()int a;int a;a=1;x+=1;a=x;X+=3;Thread2()Thread4()int a;int b;a=2;x+=2;b=x;x+=4;下列选项中，需要互斥执行的操作是A.a=1与a=2B.a=x与b=xC.x+=1与x+=2D.X+=1与x+=331.下列关于SPOOLing技术的叙述中，错误的是A.需要外存的支持B.需要多道程序设计技术的支持C.可以让多个作业共享一台独占设备D.由用户作业控制设备与输入/输出井之间的数据传送32.下列关于管程的叙述中，错误的是A.管程只能用于实现进程的互斥B.管程是由编程语言支持的进程同步机制C.任何时候只能有一个进程在管程中执行D
15、.管程中定义的变量只能被管程内的过程访问题3341均依据题3341图回答。023图中：R1R3为路由器；-130.18.10.1Switch为100 Base-T?交换机；Web服务器S201.1.3.9Hub为100Base-T集线器：主机H1H4的默认域名服务NAT LO器均配置为201.1.1：1。201.11.024E0装L1201.1.3.1201.12.025R2R3E1192.168.3.254SwitchHub4192.168.3.252DNS服务器201.1.1.1白HIH3192.168.3.251192.168.3.2192.168.3.3题3341图33.在OSI参考模
16、型中，R1、Switch、Hub实现的最高功能层分别是A.2、2、1B.2、2、2C.3、2、1D.3、2、234.若连接R2和R3链路的频率带宽为8kHz,信噪比为30dB,该链路实际数据传输速率约为理论最大数据传输速率的50%，则该链路的实际数据传输速率约是A.8kbpsB.20kbpsC.40kbpsD.80kbps35.若主机H2向主机H4发送1个数据帧，主机H4向主机H2立即发送一个确认帧，则除H4外，从物理层上能够收到该确认帧的主机还有A.仅H2B.仅H3C.仅H1、H2D.仅H2、H336.若Hub再生比特流过程中，会产生1.535us延时，信号传播速度为200mus,不考虑以太
17、网帧的前导码，则H3与H4之间理论上可以相距的最远距离是。A.200mB.205mC.359mD.512m37.假设R1、R2、R3采用RIP协议交换路由信息，且均已收敛。若R3检测到网络201.1.2.0/25不可达，并向2通告一次新的距离向量，则R2更新后，其到达该网络的距离是。A.2B.3C.16D.1738.假设连接R1、R2和R3之间的点对点链路使用201.1.3.x/30地址，当H3访问Wb服务器S时，R2转发出去的封装HTTP请求报文的P分组的源P地址和目的P地址分别是A.192.168.3.251,130.18.10.1B.192.168.3.251,201.1.3.9C.201.1.3.8,130.18.10.1D.201.1.3.10,130.18.10.139.假设H1与H2的默认网关和子网掩码均分别配置为192.168.3.1和255.255.255.128，H3和H4的默认网关和子网掩码均分别配置为192.168.3.254和255.255.255.128，则下列现象中可能发生的是A.H1不能与H2进行正常IP通信B.H2与H4均不能访问InternetC.H1不能与H3进行正常P通信D.H3不能与H4进行正常P通信024
