1、2013年全国硕士研究生人学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是A.O(n)B.O(mXn)C.O(min(m,n)D.O(max(m,n)2.一个栈的入栈序列为1,2,3，n,其出栈序列是p1,p2,P3,Pa。若p23,则p3可能取值的个数是A.n-3B.n-2C.n-1D,无法确定3.若将关键字1,2,3,4,5,6,7依次插入到初始为空的平衡二叉树T中，
2、则T中平衡因子为0的分支结点的个数是。A.0B.1C.2D.34.已知三叉树T中6个叶结点的权分别是2,3,4,5,6,7，T的带权（外部）路径长度最小是A.27B.46C.54D.565.若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y。则X的右线索指向的是A.X的父结点B.以Y为根的子树的最左下结点C.X的左兄弟结点YD.以Y为根的子树的最右下结点6.在任意一棵非空二叉排序树T,中，删除某结点V之后形成二叉排序树T2,再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是一。I若v是T的叶结点，则T与T3不同，若v是T1的叶结点，则T与T3相同.若v不是T1的叶结点，则
3、T与T3不同V.若v不是T1的叶结点，则T,与T3相同A.仅I、B.仅I、VC.仅、D.仅、V7.设图的邻接矩阵A如下所示。各顶点的度依次是010110011A01001000A.1,2,1,2B.2,2,1,1C.3,4,2,3D.4,4,2,2备驱动程序中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是A.用户程序B.系统调用处理程序C.设备驱动程序D.中断处理程序26.若某文件系统索引结点(inode)中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是A.索引结点的总数B.间接地址索引的级数C.地址项的个数D.文件块大小27.设系统缓冲区和用户工作区均
4、采用单缓冲，从外设读入1个数据块到系统缓冲区的时间为100，从系统缓冲区读入1个数据块到用户工作区的时间为5，对用户工作区中的1个数据块进行分析的时间为90（如下图所示）。进程从外设读入并分析2个数据块的最短时间是90用户工作区5系统缓冲区100外设A.200B.295C.300D.39028.下列选项中，会导致用户进程从用户态切换到内核态的操作是I.整数除以零.sinO函数调用l.read系统调用A.仅I、B.仅I、C.仅、D.I、和29.计算机开机后，操作系统最终被加载到A.BIOSB.ROMC.EPROMD.RAM30.若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是
5、I.处理越界错.置换页.分配内存A.仅I、B.仅、C.仅I、D.I、和31.某系统正在执行三个进程P1、P2和P3,各进程的计算(CPU)时间和I/O时间比例如下表所示。进程计算时间/O时间PI90%10%P250%50%P315%85%为提高系统资源利用率，合理的进程优先级设置应为A.P1P2P3B.P3P2P1C.P2P1=P3D.P1P2=P332.下列关于银行家算法的叙述中，正确的是A.银行家算法可以预防死锁B.当系统处于安全状态时，系统中一定无死锁进程C.当系统处于不安全状态时，系统中一定会出现死锁进程D.银行家算法破坏了死锁必要条件中的“请求和保持”条件33.在OSI参考模型中，下
6、列功能需由应用层的相邻层实现的是081素；否则输出-1。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C、C+或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。42.(10分)设包含4个数据元素的集合S=“do”,“for”,“repeat”,“while”,各元素的查找概率依次为：pl=0.35,p2-0.15,p3-0.15,p4-0.35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。请回答：(1)若采用顺序存储结构保存S,且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的
7、平均查找长度是多少？(2)若采用链式存储结构保存S,且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？43.(9分)某32位计算机，CPU主频为800MHz,Cache命中时的CPI为4，Cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40s:存储器总线宽度为32位，总线时钟频率为200MHz,支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备数据、传送数据。每次突发传送32字节，传送地址或32位数据均需要一个总线时钟周期。请回答下列问题，要求给出理由或计算过程。(1)CPU和
8、总线的时钟周期各为多少？总线的带宽（即最大数据传输率）为多少？(2)Cache缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？(3)存储器总线完成一次读突发传送总线事务所需的时间是多少？(4)若程序BP执行过程中，共执行了100条指令，平均每条指令需进行1.2次访存，Cache缺失率为5%，不考虑替换等开销，则BP的CPU执行时间是多少？44.(14分)某计算机采用16位定长指令字格式，其CPU中有一个标志寄存器，其中包含进位/借位标志C、零标志ZF和符号标志NP。假定为该机设计了条件转移指令，其格式如下：151110987.000000 C Z N OFFSET其中，00000为
9、操作码OP;C、Z和N分别为CF、ZF和NF的对应检测位，某检测位为1时表示需检测对应标志位，需检测的标志位中只要有一个为1就转移，否则不转移，例如，若C=1,Z-O,N=1,则需检测CF和NP的值，当CF=1或NF=1时发生转移；OFFSET是相对偏移量，用补码表示。转移执行时，转移目标地址为PC)+2+2OFFSET;顺序执行时，下条指令地址为(PC+2。请回答下列问题。(1)该计算机存储器按字节编址还是按字编址？该条件转移指令向后（反向）最多可跳转多少条指令？(2)某条件转移指令的地址为200CH,指令内容如下图所示，若该指令执行时CF=0,ZF-0,NF=1,则该指令执行后PC的值是多少？若该指令执行时CP=1,ZFO,NF-O,则该指令执行后PC的值又是多少？请给出计算过程。15711109800000001111100011(3)实现“无符号数比较小于等于时转移”功能的指令中，C、Z和N应各是什么？(4)以下是该指令对应的数据通路示意图，要求给出图中部件的名称或功能说明。083