2016考研408真题.pdf

2016年全国硕士研究生人学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1.已知表头元素为c的单链表在内存中的存储状态如下表所示。地址元素链接地址1000Ha1010H1004Hb100CH1008Hc1000H100CHdNULL1010He1004H1014H现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是A.1010H,1014H,1004HB.1010H,1004H,1014HC.1014H,1010H,1004HD.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(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包含树的个数是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。查找算法的伪代码如下所示。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.将高级语言源程序转换为机器级目标代码文件的程序是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;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为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址是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)-R5A.I1和2B.I2和I3C.I2和I4D.I3和I420.单周期处理器中所有指令的指令周期为一个时钟周期。下列关于单周期处理器的叙述中，错误的是A.可以采用单总线结构数据通路B.处理器时钟频率较低C.在指令执行过程中控制信号不变D.每条指令的CPI为121.下列关于总线设计的叙述中，错误的是A.并行总线传输比串行总线传输速度快B.采用信号线复用技术可减少信号线数量。021。C.采用突发传输方式可提高总线数据传输率D.采用分离事务通信方式可提高总线利用率22.异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或异常情况的叙述中，错误的是A.“访存时缺页”属于中断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个不同的临界资源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,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