2014年全国硕士研究生考试计算机学科专业基础试题（含解析）.pdf

2014年全国硕士研究生人学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题（第140小题，每小题2分，共80分下列每题给出的四个选项中，只有一个选项最符合试题要求）1. 下列程序段的时间复杂度是count=O; for (k=l; ki=n;.k*=2) for (j=l; j=n; j+) count+; A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 2. 假设栈初始为空，将中缀表达式alb+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是A. + (* -B. + (-* C. I+ (* - * D. I+ - * 3. 循环队列放在一维数组AOM-1中，endl指向队头元素，end2指向队尾元素的后一个位置假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素初始时为空下列判断队空和队满的条件中，平确的是A. 队空：end 1 = end2; 队满：endl = (end2 + 1) mod M B. 队空：endl = end2; 队满：end2 = (endl + 1) mod (M-1) C. 队空：erid2 = (endl + 1) mod M; 队满：endl = (end2 + 1) mod M D. 队空：endl = (end2 + 1) mod M; 队满：end2 = (endl + 1) mod (M-1) 4. 若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是。

A. e、cB. e、aC. d、cD. b、a5. 将森林F转换为对应的二叉树T,F中叶结点的个数等千A. T中叶结点的个数B. T中度为l的结点个数C. T中左孩子指针为空的结点个数D. T中右孩子指针为空的结点个数6. 5个字符有如下4种编码方案，不是前缀编码的是A. 01 0000 0001 001 1 B. 011, 000, 001, 010, 1 C. 000, 001, 010, 011, 100 D. 0, 100, 110, 1110, 1100 7. 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是2014年全国硕士研究生考试计算机学科专业基础试题第 1 页，共 21 页A. 3, 1, 2, 4, 5, 6B. 3,1,2,4,6,5C. 3,1,4,2,5,6D. 3,1,4,2,6,58. 用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象 下 列选项中，会受堆积现象直接影响的是A. 存储效率B. 散列函数c.装填（装载）因子D. 平均查找长度9. 在一棵具有15个关键字的4阶B树中， 含关键字的结点个数最多是A. 5B. 6 C. 10 D. 1510. 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1, 4, 13, 7, 8, 20,23, 15, 则该趟排序采用的增量（间隔）可能是。

A. 2B. 3C. 4D. 511. 下列选项中，不可能是快速排序第2趟排序结果的是A. 2, 3, 5, 4, 6, 7, 9B. 2, 7, 5, 6, 4, 3, 9 C. 3, 2, 5, 4, 7, 6, 9 D. 4, 2, 3, 5, 7, 6, 912.程序P在机器M上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的70%, 而CPI 增加到原来的1.2倍，则P在M上的执行时间是A. 8.4秒B. 11.7秒C. 14秒D. 16.8秒13. 若X= 103, y = -25, 则下列表达式采用8位定点补码运算实现时，会发生溢出的是A. x+yB.-x+yC. x- yD.-x-y14. float型数据常用IEEE754单精度浮点格式表示 假设两个float型变量x和y分别存放在32位寄存器f, 和f2中，若(f1)=CC90 OOOOH, (f2)= BOCO OOOOH, 则x和y之间的关系为一A. xy且符号相同. B. xy且符号相同D. xy且符号不同15. 某容量为256MB 的存储器由若干4Mx8位的DRAM芯片构成，该 DRAM芯片的地址引脚和数据引脚总数是。

A. 19B. 22C. 30D. 3616. 采用指令Cache与数据Cache分离的主要目的是A.降低Cache的缺失损失B. 提高Cache的命中率c.降低CPU平均访存时间D.减少指令流水线资源冲突17. 某计算机有16个通用寄存器，采用32位定长指令字， 操作码字段（含寻址方式位）为8位，Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式若基址寄存器可使用任一通用寄存器，且偏移量用补码表示， 则Store 指令中偏移量的取值范围定A.-32768-+32767B. -32767-+32768C.-65536-+65535D.-65535-+6553618. 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微指令，各指令对应的微程序平均由4条微指令组成，采用断定法（下地址字段法）确定下条微指令地2014年全国硕士研究生考试计算机学科专业基础试题第 2 页，共 21 页址， 则微指令中下地址字段的位数至少是A.5B.6C.8D.919. 某同步总线采用数据线和地址线复用方式， 其中地址数据线有32根， 总线时钟频率为 66MHz, 每个时钟周期传送两次数据（上升沿和下降沿各传送一次数据），该总线的最大数据传输率（总线带宽） 是。

A.132MB/s B. 264MB/s C. 528MB/s D. 1056MB/s20.一次总线事务中， 主设备只需给出一个首地址， 从设备 就能从首地址开始的若干连续单元读出或写入多个数据 这种总线事务方式称为A. 并行传输B.串行传输C. 突发传输D.同步传输21. 下列有关l/0接口的叙述中， 错误的是A. 状态端口和控制端口可以合用同一个寄存器B. VO接口中CPU可访问的寄存器称为1/ 0端口C. 采用独立编址方式时， 1/ 0端口地址和主存地址可能相同D. 采用统一编址方式时，CPU不能用访存指令访问VO端口22. 若某设备中断请求的响应和处理时间为lOOns, 每400ns发出一次中断请求， 中断响应所允许的最长延迟时间为50ns, 则在该设备持续工作过程中，CPU用于该设备的 1/ 0时间占整个CPU时间的百分比至少是A.12.5%B.25%C.37.5%D.50%23. 下列调度算法中， 不可能导致饥饿现象的是A. 时间片轮转B. 静态优先数调度C. 非抢占式短作业优先D. 抢占式短作业优先24. 某系统有n台互斥使用的同类设备， 三个并发进程分别需要3、4、5台设备， 可确保系统不发生死锁的设备数n最小为。

A.9B.10C.11D.1225. 下列指令中， 不能在用户态执行的是A.trap指令B. 跳转指令c.压栈指令D.关中断指令26. 一个进程的读磁盘操作完成后， 操作系统针对该进程必做的是A. 修改进程状态为就绪态B. 降低进程优先级C. 给进程分配用户内存空间D. 增加进程时间片大小27. 现有一个容量为10GB的磁盘分区， 磁盘空间以簇(Cluster)为单位进行分配， 簇的大小为4KB, 若采用位图法管理该分区的空闲空间， 即用一位(bit)标识一个簇是否被分配，则存放该位图所需簇的个数为A.80B.320C.80KD.320K28. 下列措施中， 能加快虚实地址转换的是I. 增大块表(TLB)容量II. 让页表常驻内存III. 增大交换区(swap)A. 仅IB. 仅IIC. 仅I、IID. 仅II、III29. 在一个文件被用户进程首次打开的过程中， 操作系统需要做的是A. 将文件内容读到内存中B. 将文件控制块读到内存中C. 修改文件控制块中的读写权限D. 将文件的数据缓冲区首指针返回给用户进程30. 在页式虚拟存储管理系统中， 采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。

下列算法中，可能出现Belady异2014年全国硕士研究生考试计算机学科专业基础试题第 3 页，共 21 页常现象的是I. LRU算法II. FIFO算法III. OPT算法A. 仅IIB. 仅I、IIC. 仅I、IIID. 仅II、III31. 下列关于管道(Pipe)通信的叙述中，正确的是A. 一个管道可实现双向数据传输B. 管道的容量仅受磁盘容量大小限制C. 进程对管道进行读操作和写操作都可能被阻塞D. 一个管道只能有一个读进程或一个写进程对其操作32. 下列选项中，属于多级页表优点的是A. 加快地址变换速度B. 减少缺页中断次数C. 减少页表项所占字节数D. 减少页表所占的连续内存空间33. 在OSI参考模型中，直接为会话层提供服务的是A. 应用层B. 表示层C. 传输层D. 网络层34. 某以太网拓扑及交换机当前转发表如下图所示，主机 OO-el-dS-00-23-al向主机00-e l -dS-00-23-c 1发送 l个数据帧，主机OO-el-d5-00-23-cl收到该帧后，向 主机00-e1-dS-00-23-a 1发送 1个确认帧，交换机对这两个帧的转发端口分别是交换机目的地址端口00-e l-d5-00-23-b I 2 00-e 1-dS-00-23-alOO-el-dS-00-23-bl 00-e l-dS-00-23-c 1 A. 3禾廿1B. 2, 3禾日1C. 2,3禾D1, 2D. 1, 2, 3禾Dl35. 下列因素中，不会影响信道数据传输速率的是。

A.信噪比B. 频率宽带C. 调制速率D.信号传播速度36. 主机甲与主机乙之间使用后退N帧协议CGBN)传输数据，甲的发送窗口尺寸为1000,数据帧长为1000字节，信道带宽为lOOMbps, 乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲 、乙之间的单向传播延迟是50ms, 则甲可以达到的最大平均数据传输速率约为A. lOMbpsB. 20MbpsC. 80MbpsD. lOOMbps37. 站点 A、B、C通过CDMA共享链路，A、B、C的码片序列(chipping sequence) 分别是(1,1, I, 1)、(1,-I, I, -1)和(1,I, -1, -1)若C从链路上收到的序列是(2,0, 2, 0, 0, -2, 0, -2, 0, 2, 0, 2), 则C收到 A发送的数据是A. 000B. 101C. 110D. 11138. 主机甲和主机乙已建立了TCP连接，甲始终以MSS = 1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认段 若甲在t时刻发生超时时拥塞窗口为8KB, 则从t时刻起，不再发生超时的情况下，经过10个RTT后，甲的发送窗口是A. 10KBB.12KBC.14KB39. 下列关千UDP协议的叙述中，正确的是。

I. 提供无连接服务D.15KB2014年全国硕士研究生考试计算机学科专业基础试题第 4 页，共 21 页II. 提供复用I分用服务III. 通过差错校验，保障可靠数据传输A. 仅IB. 仅I、IIC. 仅II、IIID. I、II、III40.使用浏览器访问某大学Web网站主页时， 不可能使用到的协议是A. PPPB. ARPC. UDPD. SMTP二、综合应用题（第4147小题， 共70分）41. (13分）二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和给定一棵二叉树T , 采用二叉链表存储， 结点结构如下：Ileft Iweight Iright 其中叶结点的weight域保存该结点的非负权值 设root为指向T的根结点的指针， 请设计求T的WPL的算法， 要求：1)给出算法的基本设计思想2)使用C或C+语。