2020年计算机408统考真题.docx

《2020年计算机408统考真题.docx》由会员分享，可在线阅读，更多相关《2020年计算机408统考真题.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020全国硕士研究生招生考试计算机学科专业基础试题一、单项选择题第0140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。01. 将一个IOxlO对称矩阵M的上三角部分的元素mt,l (li冬i:s;10)按列优先存入C语言的一维数组N中，元素m7,2在N中的下标是()。A. 15B. 16C. 22D. 2302. 对空栈S进行Push和Pop操作，入栈序列为a, b, c,d,e,经过Push, Push, Pop, Push, Pop, Push, Push, Pop操作后得到的出栈序列是()。A. b,a,cB. b,a,eC. b,c,aD. b,

2、c, e03. 对千任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数晕至少是()。A. 31B. 16C. 15D. 1004. 已知森林F及与之对应的二叉树T,若F的先根遍历序列是a, b, c, d, e,f,中根遍历序列是b, a, d,f, e, c,则T的后根遍历序列是（ ）。A. b, a, d,f, e, cB. b, d,f, e, c, aC. b,f, e, d, c, aD. f, e, d, c, b, a05. 下列给定的关键字输入序列中，不能生成如下二叉排序树的是（ ）。A

3、. 4, 5, 2, 1, 3C. 4, 2, 5, 3, 1B. 4,5,1,2,3D. 4, 2, 1, 3, 506. 修改递归方式实现的图的深度优先搜索(DFS)算法，将输出（访问）顶点信息的语句移到退出递归前（即执行输出语旬后立刻退出递归）。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点，则输出的顶点序列是G的（ ）。A. 拓扑有序序列B.逆拓扑有序序列C.广度优先搜索序列D.深度优先搜索序列07. 已知无向图G如下所示，使用克鲁斯卡尔(Kruskal)算法I a求图G的最小生成树，加到最小生成树中的边依次是( )。A. (b,f), (b, d), (a, e),

4、 (c, e), (b, e)B. (b,f), (b, d), (b, e), (a, e), (c, e)C. (a, e), (b, e), (c, e), (b, d), (b,f)D. (a, e), (c, e), (b, e), (b,f), (b, d)08. 若使用AOE网估算工程进度，则下列叙述中正确的是( )。A.关键路径是从原点到汇点边数最多的一条路径 B.关键路径是从原点到汇点路径长度最长的路径 C.增加任一关键活动的时间不会延长工程的工期 D.缩短任一关键活动的时间将会缩短工程的工期09. 下列关千大根堆（至少含2个元素）的叙述中，正确的是（ ）。I.可以将堆视为一

5、棵完全二叉树 II.可以采用顺序存储方式保存堆 III.可以将堆视为一棵二叉排序树 IV.堆中的次大值一定在根的下一层 A.仅I、IIB.仅II、IIIC.仅1、11和IV D. I、III和IV10. 依次将关键字5, 6, 9, 13, 8, 2, 12, 15插入初始为空的4阶B树后，根结点中包含的关键字定曰 （）。A. 8B. 6,9C. 8, 13D. 9, 1211. 对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是()。I.直接插入排序过程中元素之间的比较次数更少 II.直接插入排序过程中所需要的辅助空间更少 III.直接插入排序过程中元素的移动次

6、数更少A.仅IB.仅IIIC.仅I、IID. I、II和III12. 下列给出的部件中，其位数（宽度）一定与机器字长相同的是（ ）。I.ALUII.指令寄存器III.通用寄存器IV.浮点寄存器A.仅I、IIB.仅I、IIIC.仅II、IIID.仅II、III、IV13. 已知带符号整数用补码表示，float型数据用IEEE 754标准表示，假定变量x的类型只可能是int或float，当x的机器数为C800 OOOOH时，x的值可能是()。A. -7x227B. -216c. 217D. 25x22714. 在按字节编址，采用小端方式的32位计算机中，按边界对齐方式为以下C语言结构型变量a分配存

7、储空间：Struct recordshor七xl;intx2;) a;若a的首地址为2020 FEOOH, a的成员变量x2的机器数为1234 OOOOH,则其中34H所在存储单元的地址是()。 022 A. 2020 FE03HB. 2020 FE04HC. 2020 FE05HD. 2020 FE06H15. 下列关千TLB和Cache的叙述中，错误的是（ ）。A. 命中率都与程序局部性有关B.缺失后都需要去访问主存C.缺失处理都可以由硬件实现D.都由DRAM存储器组成16. 某计算机采用16位定长指令字格式，操作码位数和寻址方式位数固定，指令系统有48条指令，支持直接、间接、立即、相对4

8、种寻址方式。单地址指令中，直接寻址方式的可寻址范围是( )。A. 0255B. 01023C. -128127D. -51251117. 下列给出的处理器类型中，理想情况下，CPI为l的是（ ）。I.单周期CPUII.多周期CPUIII.基本流水线CPUIV.超标量流水线CPUA.仅I、IIB.仅I、IIIC.仅II、IVD.仅III、IV18. 下列关于“自陷(Trap,也称陷阱）的叙述中，错误的是()。A.自陷是通过陷阱指令预先设定的一类外部中断事件 B.自陷可用千实现程序调试时的断点设置和单步跟踪 C.自陷发生后CPU将转去执行操作系统内核相应程序 D.自陷处理完成后返回到陷阱指令的下一

9、条指令执行19. QPI总线是一种点对点全工同步串行总线，总线上的设备可同时接收和发送信息，每个方向可同时传输20位信息(16位数据4位校验位），每个QPI数据包有80位信息，分2个时钟周期传送，每个时钟周期传递2次。因此，QPI总线带宽为：每秒传送次数x2Bx2。若QPI时钟频率为2.4GHz,则总线带宽为( )。A. 4.8GBpsB. 9.6GBpsC. 19.2GBpsD. 38.4GBps20. 下列事件中，属千外部中断事件的是（I.访存时缺页II.定时器到时)。III.网络数据包到达A.仅I、IIB.仅I、IIIC.仅II、IIID. I、II和III21. 外部中断包括不可屏蔽中

10、断(NMI)和可屏蔽中断，下列关于外部中断的叙述中，错误的是()。A.CPU处于关中断状态时，也能响应NMI请求 B.一旦可屏蔽中断请求信号有效，CPU将立即响应 C.不可屏蔽中断的优先级比可屏蔽中断的优先级高 D.可通过中断屏蔽字改变可屏蔽中断的处理优先级22. 若设备采用周期挪用DMA方式进行输入和输出，每次DMA传送的数据块大小为512字节，相应的1/0接口中有一个32位数数据缓冲寄存器。对千数据输入过程，下列叙述中，错误的是( )。 023 A.每准备好32位数据，DMA控制器就发出一次总线请求 B.相对千CPU, DMA控制器的总线使用权的优先级更高 C.在整个数据块的传送过程中，C

11、PU不可以访问主存储器 D.数据块传送结束时，会产生“DMA传送结束中断请求23. 若多个进程共享同一个文件F,则下列叙述中，正确的是()。A. 各进程只能用“读”方式打开文件FB. 在系统打开文件表中仅有一个表项包含F的属性 C.各进程的用户打开文件表中关于F的表项内容相同D.进程关闭F时，系统删除F在系统打开文件表中的表项24. 下列选项中，支持文件长度可变、随机访问的磁盘存储空间分配方式是()。A.索引分配B.链接分配C.连续分配D.动态分区分配25. 下列与中断相关的操作中，由操作系统完成的是()。I.保存被中断程序的中断点II.提供中断服务 III.初始化中断向量表IV.保存中断屏蔽

12、字A.仅1、IIB.仅I、II、IVC.仅III、IVD.仅II、III、IV26. 下列与进程调度有关的因素中，在设计多级反馈队列调度算法时需要考虑的是（ ）。I.就绪队列的数量II.就绪队列的优先级III.各就绪队列的调度算法IV.进程在就绪队列间的迁移条件A.仅I、IIB.仅III、IVC.仅II、III、IVD. I、II、III和IV27. 某系统中有A、B两类资源各6个，t时刻资源分配及需求情况如下表所示。A已分配数扯B已分配数量A需求总量IB需求总量234|442I3l|I23进程 Pl P2 P3t时刻安全性检测结果是（ )。A. 存在安全序列Pl、P2、P3 C.存在安全序列

13、P2、P3、PlB. 存在安全序列P2、Pl、P3D.不存在安全序列28. 下列因素中，影响请求分页系统有效（平均）访存时间的是（ ）。I.缺页率II.磁盘读写时间III.内存访问时间 IV.执行缺页处理程序的CPU时间A.仅II、IIIB.仅I、IVC.仅I、III、IVD. I、II、III和IV29. 下列关千父进程与子进程的叙述中，错误的是()。 024 A. 父进程与子进程可以并发执行B. 父进程与子进程共享虚拟地址空间C. 父进程与子进程有不同的进程控制块D. 父进程与子进程不能同时使用同一临界资源30. 对千具备设备独立性的系统，下列叙述中，错误的是（ ）。A. 可以使用文件名访

14、问物理设备B. 用户程序使用逻辑设备名访问物理设备C. 需要建立逻辑设备与物理设备之间的映射关系 D.更换物理设备后必须修改访问该设备的应用程序31. 某文件系统的目录项由文件名和索引结点号构成。若每个目录项长度为64字节，其中4字节存放索引结点号，60字节存放文件名。文件名由小写英文字母构成，则该文件系统能创建的文件数量的上限为( )。A. 226B. 232C. 260D. 26432. 下列准则中，实现临界区互斥机制必须遵循的是（ ）。I.两个进程不能同时进入临界区II.允许进程访问空闲的临界资源 III.进程等待进入临界区的时间是有限的IV.不能进入临界区的执行态进程立即放弃CPUA.

15、仅I、IVB.仅II、IIIC.仅I、II、IIID.仅I、III、IV33. 下图描述的协议要素是（ ）。发送方接收方I.语法A.仅III.语义B.仅II时间III.时序C.仅IIID. I、II和III34. 下列关千虚电路网络的叙述中，错误的是()。A. 可以确保数据分组传输顺序B. 需要为每条虚电路预分配带宽c.建立虚电路时需要进行路由选择D.依据虚电路号(VCID)进行数据分组转发35. 在下图所示的网络中，冲突域和广播域的个数分别是（ ）。 025 IOOBaseT集线器以太网交换机路由器A. 2,2B. 2,4C. 4,2D. 4,436. 假设主机甲采用停等协议向主机乙发送数据

16、帧，数据帧长与确认帧长均为1000B,数据传输速率是10kbps,单项传播延时是200ms。则甲的最大信道利用率为（ ）。A. 80%B. 66.7%C. 44.4%D. 40%37. 某IEEE 802.11无线局域网中，主机H与AP之间发送或接收CSMA/CA帧的过程如下图所示。在H或AP发送帧前所等待的帧间间隔时间(IFS)中，最长的是（ ）。 - C_TSDATAIFS2-ACKIFS4A. IFSl时间B. IFS2C. IFS3D. IFS438. 若主机甲与主机乙已建立一条TCP连接，最大段长(MSS)为1KB,往返时间(RTT)为2ms,则在不出现拥塞的前提下，拥塞窗口从8KB

17、增长到32KB所需的最长时间是()。A. 4msB. 8msC. 24msD. 48ms39. 若主机甲与主机乙建立TCP连接时，发送的SYN段中的序号为1000,在断开连接时，甲发送给乙的FIN段中的序号为5001,则在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为( )。 026 A. 4002B. 4001C. 4000D. 399940. 假设下图所示网络中的本地域名服务器只提供递归查询服务，其他域名服务器均只提供迭代查询服务；局域网内主机访间Internet上各服务器的往返时间(RTT)均为lOms,忽略其他各种时延。若主机H通过超链接 ）。本地域名服务器、服务器com顶级

18、域名服务器A. 1Oms, 40msB. !Oms, 50msC. 20ms, 40msD. 20ms, 50ms二、综合应用题第4147小题，共70分。41. (13分）定义三元组(a, b, c)（其中a, b, c均为正数）的距离D = la - bl + lb - cl + le - a|。给定3个非空整数集合S!、和S3,按升序分别存储在3个数组中。设计一个尽可能高效的算法，计算并输出所有可能的三元组(a, b, c) (aES1, bES2, cES3)中的最小距离。例如S1=-1,0,9, S2= -25,-10, 10, 11, S3=2,9, 17,30,41，则最小距离为2

19、,相应的三元组为(9, 10, 9)。要求：l)给出算法的基本设计思想。2) 根据设计思想，采用C或C+语言描述算法，关键之处给出注释。3) 说明你所设计算法的时间复杂度和空间复杂度。42. C 10分）若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数?2)的不等长编码，每个字符的编码均为二进制的0、1序列，砐长为L位，且具有前缀特性。谓回答下列问题：l)哪种数据结构适宜保存上述具有前缀特性的不等长编码？2) 基于你所设计的数据结构，简述从0/1串到字符串的译码过程。3) 简述判定某字符集的不等长编码是否具有前缀特性的过程。43. (13分）有实现x

20、xy的两个C语言函数如下：unsigned umul (unsigned x, unsigned y) return x*y; intimul (int x, int y)return x * y; 假定某计算机M中ALU只能进行加减运算和逻辑运算。请回答下列问题。 027 l)若M的指令系统中没有乘法指令，但有加法、减法和位移等指令，则在M上也能实现上述两个函数中的乘法运算，为什么？2) 若M的指令系统中有乘法指令，则基千ALU、位移器、寄存器以及相应控制逻辑实现乘法指令时，控制逻辑的作用是什么？3) 针对以下三种情况：没有乘法指令；有使用ALU和位移器实现的乘法指令；有使用阵列乘法器实现的

21、乘法指令，函数umul(）在哪种情况下执行时间最长？哪种情况下执行的时间最短？说明理由4) n位整数乘法指令可保存2n位乘积，当仅取低n位作为乘积时，其结果可能会发生溢出。当n=32,x=231- 1,y=2时，带符号整数乘法指令和无符号整数乘法指令得到的欢y的2n位乘积分别是什么（用十六进制表示）？此时函数umul(）和imul(）的返回结果是否溢出？对千无符号整数乘法运算，当仅取乘积的低n位作为乘法结果时，如何用2n位乘积进行溢出判断？44. (10分）假定主存地址为32位，按字节编址，指令Cache和数据Cache与主存之间均采用8路组相联映射方式，直写(Write Through)写策

22、略和LRU替换算法，主存块大小为64B,数据区容量各为32KB。开始时Cache均为空。请回答下列问题。1) Cache每一行中标记(Tag)、LRU位各占几位？是否有修改位？2) 有如下C语言程序段：for(k = 0; k 1024 ; k+) sk)=2*sk);若数组s及其变量k均为int型，int型数据占4B,变量K分配在寄存器中，数组s在主存中的起始地址为0080 OOCOH,则该程序段执行过程中，访问数组s的数据Cache缺失次数为多少？3) 若CPU最先开始的访问操作是读取主存单元0001 0003H中的指令，简要说明从Cache中访问该指令的过程，包括Cache缺失处理过程。

23、45. C7分）现有5个操作A、B、C、D和E,操作C必须在A和B完成后执行，操作E必须在C和D完成后执行，请使用信号量的wait(）、signal(）操作(P、V操作）描述上述操作之间的同步关系，并说明所用信号量及其初值。46. (8分）某32位系统采用基千二级页表的请求分页存储管理方式，按字节编址，页目录项和页表项长度均为4字节，虚拟地址结构如下所示。页目录号(10位）页号(10位）页内偏移量(12位）某C程序中数组a10241024的起始虚拟地址为1080 OOOOH,数组元素占4字节，该程序运行时，其进程的页目录起始物理地址为0020 1000H,请回答下列问题。l)数组元素al 2的

24、虚拟地址是什么？对应的页目录号和页号分别是什么？对应的页目录项的物理地址是什么？若该目录项中存放的页框号为00301H,则a12所在页对应的页表项的物理地址是什么？2) 数组a在虚拟地址空间中所占的区域是否必须连续？在物理地址空间中所占区域是否必须连续？ 028 3) 已知数组a按行优先方式存放，若对数组a分别按行遍历和按列遍历，则哪种遍历方式的局部性更好？47. (9分）某校园网有两个局域网，通过路由器Rl、R2和R3互联后接入Internet, Sl和S2为以太网交换机。局域网采用静态IP地址配置，路由器部分接口以及各主机的IP地址如下图所示。203.10.2.5/30S2192.168.1.1Web服务器I 92. I 68.1.2假设NAT转换表结构为HJ192.I 68.1.3H3I92.168.1.3网内IP地址夕卜网端口号IP地址端口号请回答下列问题：1) 为使H2和H3能够访问Web服务器（使用默认端口号），需要进行什么配置？2) 若H2主动访问Web服务器时，将HTTP请求报文封装到1P数据报P中发送，则H2发送P的源IP地址和目的IP地址分别是什么？经过R3转发后，P的源IP地址和目的 IP地址分别是什么？经过R2转发后，P的源IP地址和目的IP地址分别是什么？ 029