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

2011年全国硕士研究生人学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题(140小题，每小题2分，共80分。下列每小题给出的四个选项中，只有一项符合题目要求）wh:il设n是描述问题规模的非负整数，下面程序片段的时间复杂度是。A. O(log2n)B. O(n)C. O(nlog2n)D. O(n2)2. 元素a, b, c, d, e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 。A. 3B. 4C. 5.D6.3. 已知循环队列存储在一维数组AOn-1中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在AO处，则初始时front和rear的值分别是 。A. 0, 0B. 0, n-1C. n-1, 0·D.n-1, n-14. 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A. 257B. 258·C. 384D. 3855. 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1,则该二叉树的中序遍历序列不会是。A. 1, 2, 3, 4B. 2, 3, 4, 1C. 3, 2, 4, 1D. 4, 3, 2, 16. 已知一棵有2011个结点的树，其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是 。A. 115·B. 116C. 1895D. 18967. 对千下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是。A. 95, 22, 91, 24, 94, 71B. 92,20,91,34,88,35C. 21. 89. 77. 29. 36. 38D. 12, 25, 71, 68, 33, 348. 下列关千图的叙述中，正确的是。I. 回路是简单路径II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III.若有向图中存在拓扑序列，则该图不存在回路A.仅IIB.仅I、IIC.仅IIID仅I、III9. 为提高散列(Hash)表的查找效率，可以采取的正确措施是。I. 增大装填（载）因子II. 设计冲突（碰撞）少的散列函数2018年计算机408统考真题 第 1 页，共 8 页III. 处理冲突（碰撞）时避免产生聚集（堆积）现象A. 仅IB. 仅IIC. 仅I、IID. 仅II、III10. 为实现快速排序算法， 待排序序列宜采用的存储方式是A. 顺序存储B. 散列存储C. 链式存储D. 索引存储11. 已知序列25, 13, 10, 12, 9 是大根堆， 在序列尾部插入新元素18, 将其再调整为大根堆，调整过程中元素之间进行的比较次数是。A. 1B. 2C. 4D. 512. 下列选项中， 描述浮点数操作速度指标的是A. MIPSB. CPIC. IPCD. MFLOPS13. float型数据通常用IEEE 754单精度浮点数格式表示。 若编译器将float型变量x分配到一个32位浮点寄存器FRI中， 且 X = -8.25, 则FRI的内容是。A. C104 OOOOHB. C242 OOOOHC. C184 OOOOHD. C1C2 OOOOH14. 下列各类存储器中， 不采用随机存取方式的是。A. EPROMB. CDROMC. DRAMD. SRAM15. 某计算机存储器按字节编址，主存地址空间大小为64MB, 现用4MBx8位的RAM芯片组成32MB的主存储器， 则存储器地址寄存器MAR的位数至少是A. 22位B. 23位C. 25位D. 26位16. 偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是。A. 间接寻址B. 基址寻址C. 相对寻址D. 变址寻址17. 某机器有一个标志寄存器， 其中有进位借位标志CF、 零标志ZF、 符号标志SF 和溢出2018年计算机408统考真题 第 2 页，共 8 页标志OF, 条件转移指令hgt (无符号.整数比较大于时转移）的转移条件是。"A. CF+ OF=lB. SF+ZF=lC. CF+ZF=lD. CF+SF=l18. 下列给出的指令系统特点中， 有利于实现指令流水线的是。I. 指令格式规整且长度一致II. 指令和数据按边界对齐存放III. 只有Load/Store指令才能对操作数进行存储访问A. 仅I、IIB. 仅II、IIIC. 仅I、IIID. I、II、III19. 假定不采用Cache和指令预取技术， 且机器处于 “ 开中断” 状态。在下列有关指令执行的叙述中，错误的是。A. 每个指令周期中CPU都至少访问内存一次B. 每个指令周期一定大于等于一个CPU时钟周期C. 空操作指令的指令周期中任何寄存器的内容都不会被改变D. 当前程序在每条指令执行结束时都可能被外部中断打断20. 在系统总线的数据线上，不可能传输的是。A. 指令B. 操作数C. 握手（应答）信号D. 中断类型号21. 某计算机有五级中断L 4-L 。， 中断屏蔽字为M 4M 3汕M 1M。, M; = 1 CO 尽4)表示对 L;级中断进行屏蔽。若中断响应优先级从高到低的顺序是L 4-L 。-L2-+L尸L 3, 则L 1 的中断处理程序中设置的中断屏蔽字是。2011年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 浓 囡函 潞颐圉囡国国回回团园A. 11110B. 01101C. 00011.D. 0101022. 某计算机处理器主频为50MHz, 采用定时查询方式控制设备A的I/0, 查询程序运行 一次所用的时钟周期数至少为500。 在设备A工作期间， 为保证数据不丢失， 每秒需对其查询至少 200次， 则CPU用于设备A的I/0的时间占整个CPU时间的百分比至少是 。A. 0.02%B. 0.05%。C. 0.20%D. 0.50%A.先来先服务B. 高响应比优先23. 下列选项中， 满足短任务优先且不会发生饥饿现象的调度算法是C. 时间片轮转D. 非抢占式短任务优先24. 下列选项中， 在用户态执行的是。A. 命令解释程序B. 缺页处理程序C. 进程 调度程序D. 时钟中断处理程序25. 在支持多线程的系统中， 进程P创建的若干线程不能共享的是。A. 进程P的代码段B. 进程P 中打开的文件c. 进程P的全局变量D. 进程P中某线程的栈指针26. 用户程序发出磁盘I/0请求后， 系统的正确处理流程是A. 用户程序一系统调用处理程序-中断处理程序一设备驱动程序B. 用户程序一系统调用处理程序一设备驱动程序-中断处理程序C. 用户程序一设备驱动程序一系统调用处理程序-中断处理程序D. 用户程序-设备驱动程序一中断处理程序一系统调用处理程序进程P1 P2 P3P4已分配资源R1R22。R3。R112。I。Il。尚需分配R2。I I23R3 12。3。IR1。可用资源R2Ra2I27. 某时刻进程的资源使用情况如下表所示。此时的安全序列是。A. P1, P2, P3, 凡B. P1, P3, P2, P4D. 不存在的28. 在缺页处理过程中， 操作系统执行的操作可能是°I. 修改页表II. 磁盘1/0III. 分配页框A. 仅I、IIB. 仅IIC. 仅IIID. I、II和III29. 当系统发生抖动(thrashing)时， 可以采取的有效措施是。I. 撤销部分进程II. 增加磁盘交换区的容量III. 提高用户进程的优先级A. 仅IB. 仅IIC. 仅IIID. 仅I、II30. 在虚拟内存管理中， 地址变换机构将逻辑地址变换为物理地址， 形成该逻辑地址的阶段是A. 编辑B. 编译C. 链接D. 装载2018年计算机408统考真题 第 3 页，共 8 页31. 某文件占1 0个磁盘块， 现要把该文件磁盘块逐个读入主存缓冲区 ，并送用户区进行分析 ，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间 为 lOOµs, 将缓冲区的数据传送到用户区的时间是SOµs, CPU对一块数据进行分析的时间 为SOµs。在单缓冲区和双缓冲区结构下， 读入并分析完该文件的时间分别是 。A. lS_ OOµs、lOOOµsB. 1550µs、llOOµsC. 1550µs、1550µsD. 2000µs、2000µs32. 有两个并发执行的进程P1和P2, 共享初值为1的变量x。P1 对x 加1, P2对x减l。加1和减l操作的指令序列分别如下所示。loadR1,. x/ /取x到寄存器Rl加1操作_II减1操作re x,中load R2, xx,inc Rl.玩oreRl/将Rl的内容存入又两个操作完成后，x的值。de··.i:. 、归， 2 s氐A. 可能为-1或3B. 只能为1C. 可能为0、 1或2D. 可能为-1、 0 、 1或233. TCP/IP参考模型的网络层提供的是。A. 无连接不可靠的数据报服务B. 无连接可靠的数据报服务C. 有连接不可靠的虚电路服务D. 有连接可靠的虚电路服务34. 若某通信链路的数据传输速率 为2400bps, 采用四相位调制，则该链路的波特率是。A. 600波特B. 1200波特C. 4800波特D. 9600波特35. 数据链路层采用选择重传协议(SR) 传输数据，发送方已发送了0-3号数据帧 ，现已收到1号帧的确认 ，而O、 2号帧依次超时， 则此时需要重传的帧数是。A.1 B. 2C. 3D. 436. 下列选项中，对正确接收到的数据帧进行确认的 MAC协议是。A. CSMAB. CDMAC. CSMA/CDD. CSMA/CA37. 某网络拓扑如下图所示，路由器Rl只有到达子网192.168.1.0/24的路由。为使Rl可以将1P分组正确地路由到 图中所有的子网， 则在 Rl中需要增加的 一条路由（目的网络，子网掩码，下一跳）是 。A. 192.168.2.0255.255.255.128192.168.1.1B. 192.168.2.0255.255.255.0192.168.1.1C. 192.168.2.0255.255.255.128192.168.1.2D. 192.168.2.0255.255.255.0192.18.l.238. 在子网192.168.4.0/30中能接收目的地址为192.168.4.3的IP分组的最大主机数是。A. 0B. 1C. 2D. 439. 主机甲向主机乙发送一个(SYN= 1, seq= 11220)的TCP段，期望与主机乙建立TCP2018年计算机408统考真题 第 4 页，共 8 页2011年全国硕士研究生入学统考试计算机科学与技术学科联考计算机学科专业基础综合试题园蓝面图匿回回囡囡园连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP段可能是。A. (SYN= 0, ACK= 0, seq= 11221, ack= 11221)B. (SYN= 1, ACK= 1, seq= 11220, ack = 11220)C. (SYN= 1, ACK= 1, seq= 11221, ack= 11221)D. (SYN= 0, ACK= 0, seq= 11220, ack= 11220)40. 主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300B、400B和500B的有效载荷， 第3个段的序号为900。 若主机乙仅正确接收到第1段和第3段，则主机乙发送给主机甲的确认序号是。2018年计算机408统考真题 第 5 页，共 8 页A. 300B. 500C. 1200二、综合应用题（第4147小题，共70分）D. 140041. (8分）已知有6个 顶点（顶点 编号为 os) 的有向带权图G, 其邻接矩阵A为上三 角矩阵，按行为主序（行优先）保存在如下的一维数组中 。1416 l=l=l=ls要求：(1)写出图G的邻接矩阵A。 (2)画出有向带权图G。(3)求图G的关键路径，并计算该关键路径的长度。42. (15分） 一个长度为 L (L?':l)的升序序列S, 处在第Lu2l个位置的数称为 S的中位数。例如，若序列Sl= (11, 13, 15, 17, 19), 则Sl的中位数是15, 两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2= (2, 4, 6,8, 20), 则 Sl和S2的中位数是11。现在有两个等长升序序列A和B, 试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：(1) 给出算法的基本设计思想 。(2) 根据设计思想，采用C、C+或Java语言描述算法， 关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。43. Cll分）假定在一个8位字长的计算机中 运 行如下 C程序段 ： unsignLJpt. x= 134.iunsigr1etiJnt. y=246;int rn=x;int n=y; unsigneti,I;t. zl=x-:-y; unsigned intz2=x+y; int·kl=rri.:n;int k2=rn+n;若 编译器编译时将8个8位寄存器RlR8分别分配给变量x、y、m、n、zl、z2、kl和k2。请回答下列问题 。（提示：带符号整数用补码表示。）(1)执行上述程序段后，寄存器Rl、R5和R6的内容分别 是什么（用十六进制表示）？ (2)执行上述程序段后，变量m和kl的值分别是多少（用十进制表示）？(3) 上述程序段涉及带符号整数加减、无符号整数加减运算，这四种运算能否利用同一个加法器辅助电路实现？简述理由。(4) 计算机内部如何判断带符号整数加I减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？虚页。号有效位I I I。I页框号0604150224367。I2BI32 . . . 44. (12分）某计算机存储器按字节编址， 虚拟（逻辑） 地址空间大小为16MB, 主存（物理）地址空间大小为1MB, 页面大小为4KB; Cache采用直接映射方式，共8行；主存与Cache之间交换的块大小为32B。 系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、 题44-b图所示，图中页框号及标记字段的内容为十六进制形式。行号有效位标记2018年计算机408统考真题 第 6 页，共 8 页234567I020。IOIDI105I064。I14DI27A . . .题44-a图 页表的部分内容请回答下列问题。题44-b图 Cache的部分内容(1) 虚拟地址共有几位， 哪儿位表示虚页号？物理地址共有几位， 哪几位表示页框号（物理页号）？(2) 使用物理地址访问Cache 时，物理地址应划分成哪儿个字段？要求说明每个字段的位数及在物理地址中的位置。(3) 虚拟地址001C60H所在的页面是否在主存中？若在主存中， 则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache命中？要求说明理由。(4) 假定为该机配置一个四路组相联的TLB共可存放8个页表项， 若其当前内容（ 十六进制）如题44-c图所示， 则此时虚拟地址024BACH所在的页面是否存在主存中？要求说明理由。I11111111l0s111I 产I:I组有效 标页框有效标页框有效 标页框有效标页框号位记号位 记号位记号位记号题44-c图 TLB的部分内容45. (8分）某银行提供1个服务窗口和10个供顾客等待的座位。 顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。 当营业员空闲时，通过叫号选取一位顾客， 并为其服务。 顾客和营业员的活动过程描述如下：cobeginprocess 顾客i从取号机获取一个号码；等待叫号；获取服务；process 营业员while (TRUE)请添加必要的信号量和P、V (或wait()、signal()操作，实现上述过程中的互斥与同步。 要求写出完整的过程，说明信号量的含义并赋初值。46. (7分）某 文件系统为一级目录结构，文件的数据 一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。 请回答如下问题。(1) 在连续、 链式、 索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。 为定位文件数据块，需要FCB中设计哪些相关描述字段？(2) 为快速找到文件，对于FCB, 是集中存储好，还是与对应的文件数据块连续 存储好？要求说明理由。47. (9分） 某主机的MAC地址为00-15-CS-Cl-SE-28 , IP地址为10.2.128.100 (私有地址）。 题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网 数据帧前80B的十六进制及ASCII码内容。MTU=l500B0000 00 21 27 21 51 ee 00 15c5 cl 5e 28 08 00 45 00.!J!Q"(.E.0010 01 ef11 3b 40 00 80 06ba 9d Oa 02 80 64 40 aa.:d.0020 62 20 04 ffOO 50 eO e200 fa 7b f9 f8 05 50 18bP. . P.0030 fa f() la c4 00 00 47 4554 20 2f72 66 63 2e 68GE T /rfc.h0040 74 6d 6c 20 48 54 54 50 2f31 2e 31 Od Oa 41 63tml HTTP /1.1.Ac题47-a图网络拓扑题47-b图以太网数据帧（前80B)请参考图中的数据 回答以下问题。(1) Web服务器的IP地址是什么？该主机的默认网关的MAC地址是什么？(2) 该主机在构造题47-b图的数据帧时，使用什么协议确定目的MAC地址？封装该协议请求报文的以太网帧的目的MAC地址是什么？(3) 假设HTTP/1.1协议以持续 的非流水线方式工作，一次请求响应时间为RTT , rfc.html页面引用了5个JPEG小图像，则从发出题47-b图中的Web请求开始到浏览器收到全部内容为止，需要多少个RTT?(4) 该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些字段？2018年计算机408统考真题 第 7 页，共 8 页6B目的 MAC 地址6B2B源 MAC 地址I类型146-1500B数据4B CRC注： 以太网数据帧结构和IP分组头结构分别如题47-c图、题47-d图所示。题47-c图 以太网帧结构上七牛寺 08162431I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I2018年计算机408统考真题 第 8 页，共 8 页版本 It言 I 服务类型标识标志I源IP地址目的IP地址总长度片偏移头部校验和题47-d图 IP分组头结构