2014年全国硕士研究生入学统一考试计算机专业基础综合真题.pdf

2014 年全国硕士研究生入学统一考试 计算机学科专业基础综合试题 一、单项选择题： 1~40 小题，每小题 2 分，共 80 分下列每题给出的四个选项中，只有一个选项是符合题目要求的 1. 下列程常段的时间复杂度是 count=0; for(k=1;ky且符号相同 D x>y且符号不同 15. 某容量为 256M 的存储器，由若干 4M*8 位的 DRAM 芯片构成，该 DRAM 芯片的地址引脚和数据引脚总数是： A 19 B 22 C 30 D 36 16. 采用指令 Cache 与数据 Cache 分离的主要目的是 A 减低 Cache 的缺失损失 B 提高 Cache 的命中率 C 减低 CPU 平均访问时间 D 减少指令流水线资源冲突 17. 某计算机有 16 个通用寄存器，采用 32 位定长指令字操作码字段（含寻址方式位）为 8 位， Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则 Store 指令中偏移量的取值范围是 A -32768~+32768 B -32767~+32768 C -65536~+65535 D -65535~+65536 18. 某计算机采用微程序控制器，共有 32 条指令 ，公共的取指令微程序包含 2 条微程序，各指令对应的微程序平均由 4 条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是： A 5 B 6 C 8 D 9 19. 某同步总线采用数据线和地址伐复用方式。

其中之地数据伐有红根，总伐时钟频率 为 66MHZ，每个时钟同期传送两次数据上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）：（） A. 132MB/S B. 264 C.528 D. 1056 20.一次 总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总伐事务方式称为（） A. 并行传输 B.串行传输 C.突发 D.同步 21.下列有关 I/O 借口的叙述中错误的是： A.状态端口和控制端口可以合用同一寄存器 B. I/O 接口中 CPU 可访问寄存器，称为 I/O 端口 C.采用独立编址方式时， I/O 端口地址和主存地址可能相同 D.采用统一编址方式时， CPU 不能用访存指令访问 I/O 端口 22. 某设备中 断请求的相应和处理时间为 100ns，每 400ns 发出一次中断请求，中断相应所容许的最长延迟时间为 50ns，则在该设备持续工作过程中 CPU 用于该设备的 I/O 时间占整个 CPU 时间百分比至少是 A.12.5% B.25% C.37.5% D.50% 23. 下列调整中，不可能导致饥饿现象的是 A.时间片 转移 B.静态优先及调度 C.非抢占式作业优先 D.抢占式短作业优先 24. 某系统有 n 台互斥使 用的同类设备， 3 个并发进程需要 3,4,5 台设备，可确保系统发生 死锁的设备数 n 最小为 A.9 B.10 C.11 D.12 25. 下列指令中，不能在用户 态 执行的是 A.trap 指令 B.跳转指令 C.后栈指令 D.关 断指令 26. 一个进程的读磁区操作完成后，操作系统针对该进程必做的是 A.修改进程状态为就绪态 B.降低进程优先级 C.进程分配用户内存空间 D.增加进程的 时间 片 大小 27. 现有容量为 10GB 的磁盘分区，磁盘空间以簇（ cluster）为单位进行分配，簇的大小为 4KB，若采用位图法管理该分区的空闲空间，即用一位（ bit）标识一个簇是否被分配，则存放该位图所需簇的个数为 A.80 B.320 C.80K D.320K 28. 下列措施中，能加快虚实地址转换的是 1 增大快表（ TLB） 2 让页表常驻内存 3 增大交换区 A.仅 1 B.仅 2 C.仅 1,2 D.仅 2,3 29.在一个文件被用户进程首次打开的过程中，操作系统需做的是 A.将文件内容读到内存中 B.将文件控制块读到内存中 C.修改文件控制块中的读写权限 D.将文件的数据缓冲区首指针返回给用户进程 30．在页式存储管理系统中，采用某些页面置换算法，会出现 Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。

下列算法中，可能出现 Belady异常现象的是 Ⅰ .LRU 算法 Ⅱ .FIFO 算法 Ⅲ .OPT 算法 A．仅 Ⅱ B．仅 ⅠⅡ C．仅 ⅠⅢ D．仅 Ⅱ Ⅲ 31.下列关于管道（ Pipe）通信的叙述中，正确的是 A．一个管道可实现双向数据传输 B．管道的容量仅受磁盘容量大小限制 C．进程对管道进行读操作和写操作都可以被阻塞 D．一个管道只能有一个读写进程或一个写进程对其操作 32. 下列选项中，属于多级页表优点的是 A.加快地址变换速度 B.减少缺页中断次数 C.减少页表项所占字节数 D.减少页表所占的连续内存空间 33. 在 OSI 参考模型中，直接为会话层提供服务的是 A.应用层 B.表示层 C.传输层 D.网络层 34.某以太网拓扑及交换机当前转发表如下图所示，主机 00-e1-d5-00-23-a1 向主机00-e1-d5-00-23-c1 发送 1 个数据帧，主机 00-e1-d5-00-23-c1 收到该帧后，向主机00-e1-d5-00-23-a1 发送一个确认帧，交换机对这两个帧的转发端口分别是 A. 3 和 1 B.  2,3 和 1 C.  2,3 和  1,2 D.  1,2,3 和 1 35.下列因素中，不会影响信道数据传输速率的是 A．信噪比 B.频率宽带 C.调制速率 D.信号传播速度 36.主机甲与主机乙之间使用后退 N帧协议（ GBN）传输数据，甲的发送窗口尺寸为 1000，数据帧长为 1000 字节，信道宽带为 100Mbps，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间的单向传播延迟是 50ms，则甲可以达到的最大平均数据传输速率约为 A． 10 Mbps B.20 Mbps C.80 Mbps D.100 Mbps 37.站点 A、 B、 C 通过 CDMA 共享链路， A、 B、 C 的码片序列（ chipping sequence）分别是（ 1,1,1,1）、（ 1， -1,1， -1）和（ 1， 1,-1， -1），若 C 从链路上收到的序列是（ 2,0,2,0,0，-2,0， -2,0,2,0,2），则 C 收到 A 发送的数据是 A． 000 B.101 C.110 D.111 38.主机甲和乙已建立了 TCP 连接，甲始终以 MSS=1KB 大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一 个接收窗口为 10KB 的确认段。

若甲在 t 时刻发生超时时拥塞窗口为 8KB，则从 t 时刻起，不再发生超时的情况下，经过 10 个 RTT 后，甲的发送窗口是 A． 10KB B. 12KB C. 14KB D. 15KB 39.下列关于 UDP 协议的叙述中，正确的是 Ⅰ 提供无连接服务 Ⅱ 提供复用 /分用服务 Ⅲ 通过差错校验，保障可靠数据传输 目的地址 端口 00-e1-d5-00-23-b1 2 00-a1-d5-00-23-a1 00-e1-d5-00-23-b1 00-e1-d5-00-23-c1 交换机 1 2 3 A．仅Ⅰ B. 仅Ⅰ、Ⅱ C. 仅Ⅱ、Ⅲ D. Ⅰ、Ⅱ、Ⅲ 40、使用浏览器访问某大学 Web 网站主页时，不可能使用的协议是 A． PPP B. ARP C. UDP D. SMTP 二、综合应用题： 41~47 小题，共 70 分 41.（ 13 分）二叉树的带权路径长度（ WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树 T，采用二叉链表存储，节点结构为： 其中叶节点的 weight 域保存该结点的非负权值。

设 root 为指向 T 的根节点的指针，设计求 T 的 WPL 的算法要求： （ 1）给出算法的基本设计思想； （ 2）使用 C 或 C++语言，给出二叉树结点的数据类型定义； （ 3）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释 42. （ 10 分）某网络中的路由器运行 OSPF 路由协议，题 42 表是路由器 R1 维护的主要链路状态信息（ LSI），题 42 图是根据题 42 表及 R1 的接口名构造出来的网络拓扑 题 42 表 R1 所维护的 LSI R1 的 LSI R2 的 LSI R3 的 LSI R4 的 LSI 备注 Router ID 10.1.1.1 10.1.1.2 10.1.1.5 10.1.1.6 标识路由器的IP 地址 Link1 ID 10.1.1.2 10.1.1.1 10.1.1.6 10.1.1.5 所连路由 器的RounterID IP 10.1.1.1 10.1.1.2 10.1.1.5 10.1.1.6 Link1 的基本 IP地址 Metric 3 3 6 6 Link1 的费用 Link2 ID 10.1.1.5 10.1.1.6 10.1.1.1 10.1.1.12 所连路由器的RounterID IP 10.1.1.9 10.1.1.13 10.1.1.10 10.1.1.14 Link2 基本 IP 地址 left weight right Metic 2 4 2 4 Link2 费用 Net1 Prefix 192.1.1.0/24 192.1.6.0/24 192.1.7.0/24 192.1.7.0/24 直接网络 Net1的网络前缀 Metric 1 1 1 1 到达直连网络Net1 的费用 题 42 图 R1 构造的网络拓扑 请回答下列问题。

（ 1） 本题中的网络可抽象为数据结构中的哪种逻辑结构？ （ 2） 针对题 42 表中的内容，设计合理的链式存储结构，以保存题 42 表中的链路状态信息（ LSI）要求给出链式存储结构的数据类型定义，并画出对应题 42 表的链式存储结构示意图（示意图中可仅以 ID 标识节点） （ 3） 按照迪杰斯特拉（ Dijikstra）算法的策略，依次给出 R1 到达题 42 图中子网192.1.x.x 的最短路径及费用 43. （ 9 分）请根据题 42 描述。