考研计算机学科专业基础综合

考研计算机学科专业基础综合-33（总分80,考试时间90分钟）一、单项选择题在每小题给出的四个选项中，请选出一项最符合题目要求的。1.若已知一个栈的入栈序列是1，2，3....n,其输出序列为pl,p2,p3,...pn，若p1=n,则pi是（）。A.iB.n—i C.n—i+1 D.不确定2,将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1.,298]中，A中元素A66,65（即该元素下标i=66,j=65），在B数组中的位置k为（）。A.198B.195C.197D.196查找效率最高的二叉排序树是（）。所有结点的左子树都为空的二叉排序树B•所有结点的右子树都为空的二叉排序树平衡二叉树没有左子树的二叉排序树一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0,则该树的结点数是（）。A.2k-1-1B.2k-1C.2k-1+1 D.2k-1判断以下叙述的正确性I对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图II连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点III图的深度优先搜索中一般要采用栈来暂存访问过的顶点a.i、iB.n、mC.i、mD.i、ii、m一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中零元素的个数是

()。A.eB.2eC.n2-eD.n2-2e从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是（）。二叉排序树B.大顶堆C.小顶堆D.平衡二叉树顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为（）。A.21B.23C.41D.62在下列存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系的是（）。树形存储结构B.链式存储结构C.索引存储结构D.散列存储结构若对27个元素只进行三趟多路归并排序，则选取的归并路数是（）。A.2B.3C.4D.5下列序列中，执行第一趟快速排序的结果是（）。A.[da,ax,eb,de,bb]ff[ha,gc] B.[cd,eb,ax,da]ff[ha,gc,bb]C.[gc,ax,eb,cd,bb]ff[da,ha] D.[ax,bb,cd,da]ff[eb,gc,ha]若一台计算机的机器字长为4字节，则表明该机器（）。能处理的数值最大为4位十进制数能处理的数值最多为4位二进制数组成在CPU中能够作为一个整体处理的32位的二进制代码在CPU中运算的结果最大为2325位二进制定点小数，用补码表示时，最小负数是（）。A.0.1111B.1.0001 C.1.1111D.1.0000下列说法中正确的是（）。采用变形补码进行加减法运算可以避免溢出只有定点数运算才可能溢出，浮点数运算不会发生溢出定点数和浮点数运算都有可能产生溢出

两个正数相加时一定产生溢出15.如果一个高速缓冲存储系统中，主存的容量为12MB,Cache的容量为400KB，则该存储系统的总容量为（）。A.12MB+400KBB.12MBC.400KBD.12MB-400KB16.某计算机的存储系统由Cache一主存系统构成，Cache的存取周期为10ns，主存的存取周期为50ns。在CPU执行一段程序时，Cache完成存取的次数为4800次，主存完成的存取次数为200次，该Cache一主存系统的效率是（）。A.0.856B.0.862 C.0.958 D.0.96017,对于RISC机和CISC机，以下说法错误的是（）。RISC机的指令条数比CISC机少RISC机指令的平均字长比CISC机指令的平均字长短对大多数计算任务来说，RISC机程序所用的指令条数比CISC机少RISC机和CISC机都在发展微程序在计算机中存放的位置是（）。主存储器 B.控制存储器C.通用寄存器 D.指令寄存器下列各叙述中正确的命题是（）。I在取指周期中也可能从内存取到操作数IICPU的访存时间是由存储器的容量决定的，存储容量越大，访存时间就越长III在主存与Cache之间的直接映射方式下，不采用替换策略也可以实现正确的块替换W动态存储器的读操作也具有刷新的功能A.i、n、mb.i、ii、wC.n、m、wD.i、m、w在菊花链方式中，靠近控制器的设备与远处设备的（）。优先级高B.优先级相等C.优先级低 D.不一定21.RAID利用冗余技术实现高可靠性，其中RAID1的磁盘利用率是（）。A.25%B.50% C.75%D.100%22.设存储器容量为32字，字长64位，模块数m=4，存储周期T=200ns，数据总线宽度为64位，总线传送周期T=50ns用交叉方式进行组织，交叉存储器的带宽是（）。A.32x107位/秒B.8x107位/秒 C.73x107位/秒D.18x107位/秒

操作系统为用户提供了多种接口，它们是（）。I计算机高级指令II终端命令III图标菜单W汇编语言VC语言W系统调用a.i、ii、vB.n、m、wc.m、w、vd.ii、w、w在交互式操作系统中，当选择调度算法时，不作为主要调度准则考虑的是（）。尽量提高处理机的利用率尽可能高地提高系统的吞吐量尽可能地降低用户响应时间尽量公平地对待每一个进程在解除死锁的方法中，代价最大的是（）。A.终止一个死锁进程 B.终止所有的死锁进程C.重启系统D.剥夺一个死锁进程的资源若有一进程拥有100个线程，这些线程都属于内核级线程，则在系统调度执行时间上占用的时间片是（）。A.1B.100C.1/100D.027.某计算机采用页式存储管理，内存中现有1000个页表项，CPU的cache中可以存放N个页表项，该系统中，CPU内存访问的时间为100ns，对cache访问的时间是5ns，如果希望页表映射的平均时间降到20ns以下，那么cache中的N必须高于（）。A.850B.858C.923 D.842在分页系统中，程序员编制的程序，其地址空间是连续的，分页过程的完成是（）。A.由程序员进行分页 B.由操作系统自动分页C.由用户进行分页 D.由编程工具进行分页某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接索引项，假定物理块的大小是1K，每个索引项占用4个字节，则该文件系统中最大的文件可以达到（）。A.65793KB.32768KC.65536KD.34000K30,设磁盘的IO请求队列中所要访问的磁道号为：96，184，25，120，12，126，73，75,当前磁头在96,前一次在90。当采用最短寻道时间优先算法（SSTF）和电梯算法所要移动的距离是（）。

A.618,418 B.306,260C.306,418D.618,260文件系统中若文件的物理结构为单一索引结构，则在文件控制块中有关文件的信息中，不会有的是（）。A.文件大小 B.文件首块地址C.索引表地址D.文件创建时间在设备管理中，用来实现设备分配的四个数据结构中，每个设备一张，描述设备的特性和状态，反映设备的特性、设备和控制器的连接情况的数据结构是（）。A.设备控制表（DCT）B.系统设备表（SDT）C.控制器控制表（COCT）D.通道控制表（CHCT）33.在OSI参考模型中，第N层和其上的第N+1层的关系是（）。第N层为第N+1层提供服务第N+1层将从第N层接收的信息增加了一个头第N层利用第N+1层提供的服务第N层对N+1层没有任何作用34.电路交换的优点是（）。I传输时延小II分组按序到达m无需建立连接w线路利用率高a.i和II b.i和m c.i和m d.i和w若数据链路的发送窗口尺寸WT=4，在发送3号帧、并接到2号帧的确认帧后，发送方还可连续发送的帧数是（）。A.2帧B.3帧C.4帧D.1帧下列对于IP分组的分片和重组的描述正确的是（）。IP分组可以被源主机分片，并在中间路由器进行重组IP分组可以被路径中的路由器分片，并在目的主机进行重组IP分组可以被路径中的路由器分片，并在中间路由器上进行重组IP分组可以被路径中的路由器分片，并在最后一跳的路由器上进行重组为了限制路由信息传播的范围，OSPF协议把网络划分成4种区域（Area），其中连接各个区域的传输网络是（）。A.不完全存根区域 B.标准区域C.主干区域D.存根区域

38.一台主机的IP地址为00,子网掩码为。现在用户需要配置该主机的默认路由。经过观察发现，与该主机直接相连的路由器具有如下4个IP地址和子网掩码：IIP地址:,子网掩码:IIIP地址:,子网掩码:miP地址:,子网掩码:WIP地址:,子网掩码:请问IP地址和子网掩码可能是该主机的默认路由的是（）。a.i和Ib.i和m c.i、m和w D.m和w39.以太网交换机中的端口/MAC地址映射表是（）。是由交换机的生产厂商建立的是交换机在数据转发过程中通过学习动态建立的是由网络管理员建立的是由网络用户利用特殊的命令建立的FTP客户端登陆到FTP服务器，并下载了一个文件，请问这个过程中需要建立TCP连接和断开TCP连接的次数分别是（）。A.2, 1 B. 1, 1 C. 1,2 D. 2, 2、综合应用题任意给定1,2,...,n指定为一棵树的先根遍历序列；同时任意给定这n个数值（1,2,...,n）的一个排列p1,p2,...pn为这棵树的后根遍历序列。（1） 根据这样的先根遍历序列和后根遍历序列，是否都可以得到一棵树？如果能够，请简述理由（不要求形式化证明）。如果不能，请给出一个简单反例。（2） 如果能得到树，所得到的树是否唯一?如果能够，请简述理由（不要求形式化证明）。如果不能，请给出一个简单反例。42.设有一个双向链表h,每个结点中除有prior、data和next共3个域外，还有一个访问频度域freq,在链表被起用之前，每个结点中的freq域的值均被初始化为零。每当进行LocateNode（h,x）运算时，令元素值为x的结点中freq域的值加1,并调整表中结点的次序，使其按访问频度的递减序列排序，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。43.已知两个实数x=-68,y=-8.25,它们在C语言中定义为float型变量，分别存放在寄存器A和B中。另外，还有两个寄存器C和D。A、B、C、D都是32位的寄存器。

请回答下列问题(要求刚十六进制表示二进制序列)：寄存器A和B的内容分别是什么？x和y相加后的结果存放在c寄存器中，寄存器C中的内容是什么？x和y相减后的结果存放在D寄存器中，寄存器D中的内容是什么?44,一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10四、30卜、30卜、50四和75gs向通道发出一次数据传送的服务请求，请回答下列问题：计算这个字节多路通道的实际流量和工作周期。如果设计字节多路通道的最大流量正好等于通道实际流量，并假设对数据传输率高的设备，通道响应它的数据传送请求的优先级也高。5台设备在0时刻同时向通道发出第一次传送数据的请求.并在以后的时间里按照各自的数据传输率连续工作。画出通道分时为每台设备服务的时间关系图，并计算这个字节多路通道处理完各台设备的第一次数据传送请求的时刻。从时间关系图上可以发现什么问题?如何解决这个问题？设某多道程序系统中有用户使用的内存1000M，打印机1台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计，采用最短剩余时间优先的进程调度算法，进程最短剩余时间相同时采用先来先服务的算法，进程调度时机选择在进程执行结束或新进程创建时，现有进程如下：进程创建时间要求执行时间要求内存申请打印机008150M1144300M12101600M031120200M141614100M0假设系统优先分配内存低地址区域，且不允许移动，那么，求:给出进程调度算法选中进程的次序，并说明理由。全部进程执行结束所用的时间是多少？假定某采用页式虚拟存储管理的计算机系统中，主存储器容量为1GB，被分为262144块物理块，物理块号为0,1，2,......，262143。某进程的地址空间占4页，逻辑页号为0,1，2，3，被分配到主存储器的第20,45，101，58号物理块中。回答：内存物理地址至少应该用多少位字长来表示？进程每一页的长度为多少字节?逻辑地址中的页内地址应占用多少位字长？把进程中每一页在分到的主存物理块中的起始地址和结束地址填入下表： 逻辑页号物理起始地址 物理结