# 2014年全国硕士研究生入学统一考试 # 计算机科学与技术学科联考计算机学科专业基础综合试题 # 一、单项选择题：第 $1\sim 40$ 小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。 1. 下列程序段的时间复杂度是 ```javascript count=0; for $(k = 1;k < = n;k^{*} = 2)$ for $(j = 1;j < = n;j + + )$ count++; ``` A. $\mathrm{O}\left( {{\log }_{2}\mathrm{n}}\right)$ B. O(n) C. $\mathrm{O}(\mathrm{nlog}_{2}\mathrm{n})$ D. $O\left(n^{2}\right)$ 2. 假设栈初始为空，将中缀表达式 $a / b + (c^* d - e^* f) / g$ 转换为等价的后缀表达式的过程中，当扫描到 $f$ 时，栈中的元素依次是 A. $+ (* -$ B. $+(-^{*})$ C. $1 + \left( \begin{array}{l} * \\ - * \end{array} \right)$ D. /+-* 3. 循环队列放在一维数组 A[0...M-1]中，end1 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素。初始时为空。下列判断队空和队满的条件中，正确的是________。 A. 队空: end1 == end2; 队满： $\mathrm{end1} == (\mathrm{end2} + 1) \bmod \mathbf{M}$ B. 队空: end1 == end2; 队满： $\mathrm{end2} == (\mathrm{end1} + 1) \bmod (\mathrm{M - 1})$ C. 队空: end2 == (end1 + 1) mod M; 队满： $\mathrm{end1} == (\mathrm{end2} + 1) \bmod \mathbf{M}$ D. 队空: end1 == (end2 + 1) mod M; 队满： $\mathrm{end2} == (\mathrm{end1} + 1) \bmod (\mathrm{M - 1})$ 4. 若对如下的二叉树进行中序线索化, 则结点 $\mathrm{x}$ 的左、右线索指向的结点分别是 ![](https://408.foreverlink.love/images/52bea3a840225deb0ca67f018664f9e6.jpg) A.e、c B. e、a C. d、c D. b、a 5. 将森林 F 转换为对应的二叉树 T, F 中叶结点的个数等于____。 A. T中叶结点的个数 B. T 中度为 1 的结点个数 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. 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是 A. 3,1,2,4,5,6 B. 3,1,2,4,6,5 C. $3,1,4,2,5,6$ D. 3,1,4,2,6,5 ![](https://408.foreverlink.love/images/bcff4fa9172671327cc5a95294a3c445.jpg) 8. 用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是________。 A. 存储效率 B. 散列函数 C. 装填(装载)因子 D. 平均查找长度 9. 在一棵具有 15 个关键字的 4 阶 B 树中, 含关键字的结点个数最多是_____。 A. 5 B. 6 C. 10 D. 15 10. 用希尔排序方法对一个数据序列进行排序时，若第 1 趟排序结果为 9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是 ______。 A. 2 B. 3 C. 4 D. 5 11. 下列选项中，不可能是快速排序第2趟排序结果的是 A. 2,3,5,4,6,7,9 B. 2,7,5,6,4,3,9 C. $3,2,5,4,7,6,9$ D. 4,2,3,5,7,6,9 12. 程序 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 + y$ B. $-x + y$ C. x-y D. -x-y 14. float 型数据据常用 IEEE754 单精度浮点格式表示。假设两个 float 型变量 x 和 y 分别存放在 32 位寄存器 $\mathrm{f}_1$ 和 $\mathrm{f}_2$ 中，若 $(\mathrm{f}_1) = \mathrm{CC90000H}$ ， $(\mathrm{f}_2) = \mathrm{B0C0000H}$ ，则 x 和 y 之间的关系为 ________。 A. $x < y$ 且符号相同 B. $x < y$ 且符号不同 C. $x > y$ 且符号相同 D. $x > y$ 且符号不同 15. 某容量为 256MB 的存储器由若干 $4\mathrm{M} \times 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\sim +32767$ B. $-32767\sim +32768$ C. $-65536\sim +65535$ D. $-65535 \sim +65536$ 18. 某计算机采用微程序控制器，共有 32 条指令，公共的取指令微程序包含 2 条微指令，各指令对应的微程序平均由 4 条微指令组成，采用断定法（下地址字段法）确定下条微 指令地址，则微指令中下址字段的位数至少是____。 A. 5 B. 6 C. 8 D. 9 19. 某同步总线采用数据线和地址线复用方式，其中地址/数据线有 32 根，总线时钟频率为 $66 \mathrm{MHz}$ ，每个时钟周期传送两次数据(上升沿和下降沿各传送一次数据)，该总线的最大数据传输率(总线带宽)是 ______。 A. $132\mathrm{MB / s}$ B. $264 \mathrm{MB} / \mathrm{s}$ C. $528 \mathrm{MB} / \mathrm{s}$ D. $1056 \mathrm{MB} / \mathrm{s}$ 20. 一次总线事务中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元读出或写入多个数据。这种总线事务方式称为________。 A. 并行传输 B. 串行传输 C. 突发传输 D. 同步传输 21. 下列有关 I/O 接口的叙述中, 错误的是____。 A. 状态端口和控制端口可以合用同一个寄存器 B. I/O 接口中 CPU 可访问的寄存器称为 I/O 端口 C. 采用独立编址方式时, I/O 端口地址和主存地址可能相同 D. 采用统一编址方式时, CPU 不能用访存指令访问 I/O 端口 22. 若某设备中断请求的响应和处理时间为 $100 \mathrm{~ns}$ , 每 $400 \mathrm{~ns}$ 发出一次中断请求, 中断响应所允许的最长延迟时间为 $50 \mathrm{~ns}$ , 则在该设备持续工作过程中, CPU 用于该设备的 I/O 时间占整个 CPU 时间的百分比至少是 A. $12.5\%$ B. $25\%$ C. $37.5\%$ D. $50\%$ 23. 下列调度算法中，不可能导致饥饿现象的是________。 A. 时间片轮转 B. 静态优先数调度 C. 非抢占式短作业优先 D. 抢占式短作业优先 24. 某系统有 n 台互斥使用的同类设备, 三个并发进程分别需要 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)为单位进行分配, 簇的大小为 $4 \mathrm{KB}$ , 若采用位图法管理该分区的空闲空间, 即用一位(bit)标识一个簇是否被分配, 则存放该位图所需簇的个数为_____。 A. 80 B. 320 C. $80 \mathrm{~K}$ D. 320K 28. 下列措施中，能加快虚实地址转换的是________。 I. 增大快表(TLB)容量 II. 让页表常驻内存 III. 增大交换区(swap) A. 仅 I B. 仅 II C. 仅 I、II D. 仅 II、III 29. 在一个文件被用户进程首次打开的过程中，操作系统需做的是 A. 将文件内容读到内存中 B. 将文件控制块读到内存中 C. 修改文件控制块中的读写权限 D. 将文件的数据缓冲区首指针返回给用户进程 30. 在页式虚拟存储管理系统中，采用某些页面置换算法，会出现 Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现 Belady 异常现象的是________。 I. LRU算法 II. FIFO算法 III. OPT算法 A. 仅 II B. 仅 I、II C. 仅 I、III D. 仅 II、III 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 发送 1 个确认帧，交换机对这两个帧的转发端口分别是（）。 ![](https://408.foreverlink.love/images/6853c60f252479c9ba62d65c2e7e1698.jpg) ![](https://408.foreverlink.love/images/94dd944f5df8d303dd33af470b74a963.jpg) 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. 10Mbps B. 20Mbps C. 80Mbps D. 100Mbps 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 连接，甲始终以 $\mathrm{MSS} = 1\mathrm{KB}$ 大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为 $10\mathrm{KB}$ 的确认段。若甲在 t 时刻发生超时时拥塞窗口为 $8\mathrm{KB}$ ，则从 t 时刻起，不再发生超时的情况下，经过 10 个 RTT 后，甲的发送窗口是 ________。 A. 10KB B. 12KB C. $14 \mathrm{KB}$ D. 15KB 39. 下列关于 UDP 协议的叙述中，正确的是____。 I. 提供无连接服务 II. 提供复用/分用服务 III. 通过差错校验，保障可靠数据传输 A. 仅 I B. 仅 I、II C. 仅 II、III D. I、II、III 40. 使用浏览器访问某大学 Web 网站主页时，不可能使用到的协议是____。 A. PPP B. ARP C. UDP D. SMTP # 二、综合应用题：41—47小题，共70分。 41.(13分)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：
leftweightright
其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法，要求： 1）给出算法的基本设计思想； 2）使用C或 $\mathbf{C} + +$ 语言，给出二叉树结点的数据类型定义； 3）根据设计思想，采用C或 $\mathbf{C} + +$ 语言描述算法，关键之处给出注释。 42. (10分)某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息(LSI)，题42图是根据题42表及R1的接口名构造出来的网络拓扑。 题42表 R1所维护的LSI
R1的LSIR2的LSIR3的LSIR4的LSI备注
Router ID10.1.1.110.1.1.210.1.1.510.1.1.6标识路由器的IP地址
Link1ID10.1.1.210.1.1.110.1.1.610.1.1.5所连路由器的Router ID
IP10.1.1.110.1.1.210.1.1.510.1.1.6Link1的本地IP地址
Metric3366Link1的费用
Link2ID10.1.1.510.1.1.610.1.1.110.1.1.2所连路由器的Router ID
IP10.1.1.910.1.1.1310.1.1.1010.1.1.14Link2的本地IP地址
Metric2424Link2的费用
Net1Prefix192.1.1.0/24192.1.6.0/24192.1.5.0/24192.1.7.0/24直连网络Net1的网络前缀
Metric1111到达直连网络Net1的费用
![](https://408.foreverlink.love/images/c48b662d85d5c7219deb414f152a3f4c.jpg) 题42图R1构造的网络拓扑 请回答下列问题。 1）本题中的网络可抽象为数据结构中的哪种逻辑结构？ 2）针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应题42表的链式存储结构示意图(示意图中可仅以ID标识结点)。 3）按照迪杰斯特拉(Dijikstra)算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。 43.（9分）请根据题42描述的网络，继续回答下列问题。 1）假设路由表结构如下表所示，请给出题 42 图中 R1 的路由表，要求包括到达题 42 图中子网192.1.x.x的路由，且路由表中的路由项尽可能少。
目的网络下一条接口
2）当主机192.1.1.130向主机192.1.7.211发送一个 $\mathrm{TL} = 64$ 的IP分组时，R1通过哪个接口转发该IP分组？主机192.1.7.211收到的IP分组TTL是多少？ 3）若R1增加一条Metric为10的链路连接Internet，则题42表中R1的LSI需要增加哪些信息？ 44.（12分）某程序中有如下循环代码段p：”for(int i = 0; i < N; i++) sum += A[i]；”。假设编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中，数组A的首地址在寄存器R3中。程序段P起始地址为08048100H，对应的汇编代码和机器代码如下表所示。
编号地址机器代码汇编代码注释
108048100H00022080Hloop: sll R4,R2,2(R2) \(<<2 \rightarrow\) R4
208048104H00083020Hadd R4,R4,R3(R4)+(R3) → R4
308048108H8C850000Hload R5,0(R4)((R4)+0) → R5
40804810CH00250820Hadd R1,R1,R5(R1)+(R5) → R1
508048110H20420001Hadd R2,R2,1(R2)+1 → R2
608048114H1446FFFFAHbne R2,R6,loopif(R2)!=(R6) goto loop
执行上述代码的计算机M采用32位定长指令字，其中分支指令bne采用如下格式：
312625212016150
OPRsRdOFFSET
OP 为操作码;;Rs 和 Rd 为寄存器编号；OFFSET 为偏移量，用补码表示。请回答下列问题，并说明理由。 1）M的存储器编址单位是什么？ 2）已知sll指令实现左移功能，数组A中每个元素占多少位？ 3）题44表中bne指令的OFFSET字段的值是多少？已知bne指令采用相对寻址方式，当前PC内容为bne指令地址，通过分析题44表中指令地址和bne指令内容，推断出bne指令的转移目标地址计算公式。 4）若 M 采用如下“按序发射、按序完成”的 5 级指令流水线：IF（取值）、ID（译码及取数）、EXE（执行）、MEM（访存）、WB（写回寄存器），且硬件不采取任何转发措施，分支指令的执行均引起 3 个时钟周期的阻塞，则 P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令 1 的执行不会因为与指令 5 的数据相关而发生阻塞？ 45. 假设对于 44 题中的计算机 M 和程序 P 的机器代码，M 采用页式虚拟存储管理；P 开始执行时， $(R1)=(R2)=0$ ， $(R6)=1000$ ，其机器代码已调入主存但不在 Cache 中；数组 A 未调入主存，且所有数组元素在同一页，并存储在磁盘同一个扇区。请回答下列问题并说明理由。 (1) P 执行结束时, R2 的内容是多少? 2）M的指令Cache和数据Cache分离。若指令Cache共有16行，Cache和主存交换的块大小为32字节，则其数据区的容量是多少？若仅考虑程序段P的执行，则指令Cache的命中率为多少？ 3）P 在执行过程中，哪条指令的执行可能发生溢出异常？哪条指令的执行可能产生缺页异常？对于数组 A 的访问，需要读磁盘和 TLB 至少各多少次？ 46. 文件 F 由 200 条记录组成，记录从 1 开始编号。用户打开文件后，欲将内存中的一条记录插入到文件 F 中，作为其第 30 条记录。请回答下列问题，并说明理由。 1）若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块？F的文件控制块内容会发生哪些改变？ 2）若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块？若每个存储块大小为1KB，其中4个字节存放链接指针，则该文件系统支持的文件最大长度是多少？ 47. 系统中有多个生产者进程和多个消费者进程，共享一个能存放 1000 件产品的环形缓冲区（初始为空）。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出 10 件产品后，其他消费者进程才可以取产品。请使用信号量 P，V.wait()，signal() 操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。 # 2014年计算机学科专业基础综合试题参考答案 # 一、单项选择题 # （一）单选题答案
1.C2.B3.A4.D5.C6.D7.D8.D
9.D10.B11.C12.D13.C14.A15.A16.D
17.A18.C19.C20.C21.D22.B23.A24.B
25.D26.A27.A28.C29.B30.A31.C32.D
33.C34.B35.D36.C37.B38.A39.B40.D
# （二）单选题答案解析 1. 内层循环条件 $j <= n$ 与外层循环的变量无关，每次循环 $j$ 自增 1，每次内层循环都执行 $n$ 次。外层循环条件为 $k <= n$ ，增量定义为 $k^* = 2$ ，可知循环次数为 $2^k <= n$ ，即 $k <= \log_2 n$ 。所以内层循环的时间复杂度是 $O(n)$ ，外层循环的时间复杂度是 $O(\log_2 n)$ 。对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度 $T(n) = T_1(n)^* T_2(n) = O(n)^* O(\log_2 n) = O(n \log_2 n)$ 。 2. 将中缀表达式转换为后缀表达式的算法思想如下： 从左向右开始扫描中缀表达式； 遇到数字时，加入后缀表达式； 遇到运算符时： a. 若为 '('，入栈； b. 若为 ' )', 则依次把栈中的的运算符加入后缀表达式中, 直到出现(', 从栈中删除('; c. 若为除括号外的其他运算符，当其优先级高于除'('以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。 当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
待处理序列栈后缀表达式当前扫描元素动作
a/b+(c*d-e*f)/gaa加入后缀表达式
/b+(c*d-e*f)/ga//入栈
b+(c*d-e*f)/g/abb加入后缀表达式
+(c*d-e*f)/g/ab++优先级低于栈顶的/,弹出/
+(c*d-e*f)/gab/++入栈
(c*d-e*f)/g+ab/((入栈
c*d-e*f)/g+(ab/cc加入后缀表达式
*d-e*f)/g+(ab/c*栈顶为(, *入栈
d-e*f)/g+(*ab/cdd加入后缀表达式
-e*f)/g+(*ab/cd--优先级低于栈顶的*,弹出*
-e*f)/g+(ab/cd*-栈顶为(，-入栈
e*f)/g+(-ab/cd*ee加入后缀表达式
*f)/g+(-ab/cd*e**优先级高于栈顶的-, *入栈
f)/g+(-*ab/cd*eff加入后缀表达式
)/g+(-*ab/cd*ef)把栈中(之前的符号加入表达式
/g+ab/cd*ef*-//优先级高于栈顶的+, /入栈
g+/ab/cd*ef*-gg加入后缀表达式
+/ab/cd*ef*-g扫描完毕, 运算符依次退栈加入表达式
ab/cd*ef*-g/+完成
由此可知，当扫描到f的时候，栈中的元素依次是 $+(-\ast$ ，选B。 在此，再给出中缀表达式转换为前缀或后缀表达式的一种手工做法，以上面给出的中缀表达式为例： 第一步：按照运算符的优先级对所有的运算单位加括号。 式子变成了： $((\mathrm{a / b}) + (((\mathrm{c^*d}) - (\mathrm{e^*f})) / \mathrm{g}))$ 第二步：转换为前缀或后缀表达式。 前缀：把运算符号移动到对应的括号前面，则变成了：+((ab)/(-(\*(cd)\*(ef))g)) 把括号去掉：+/ab/-*cd*efg前缀式子出现。 后缀：把运算符号移动到对应的括号后面，则变成了：((ab)/(((cd)*ef*)-g))+ 把括号去掉：ab/cd*ef*-g/+后缀式子出现。 当题目要求直接求前缀或后缀表达式时，这种方法会比上一种快捷得多。 3. end1 指向队头元素，那么可知出队的操作是先从 A[end1]读数，然后 end1 再加 1。end2 指向队尾元素的后一个位置，那么可知入队操作是先存数到 A[end2]，然后 end2 再加 1。若把 A[0]储存第一个元素，当队列初始时，入队操作是先把数据放到 A[0]，然后 end2 自增，即可知 end2 初值为 0；而 end1 指向的是队头元素，队头元素的在数组 A 中的下标为 0，所以得知 end1 初值也为 0，可知队空条件为 end1==end2；然后考虑队列满时，因为队列最多能容纳 M-1 个元素，假设队列存储在下标为 0 到下标为 M-2 的 M-1 个区域，队头为 A[0]，队尾为 A[M-2]，此时队列满，考虑在这种情况下 end1 和 end2 的状态，end1 指向队头元素，可知 end1=0，end2 指向队尾元素的后一个位置，可知 end2=M-2+1=M-1，所以可知队满的条件为 end1=((end2+1)mod M，选 A。 注意：考虑这类具体问题时，用一些特殊情况判断往往比直接思考问题能更快的得到答案，并可以画出简单的草图以方便解题。 4. 线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点,所以先写出二叉树的中序遍历序列: edbxac, 中序遍历中在 x 左边和右边的字符, 就是它在中序线索化的左、右线索, 即 b、a, 选 D。 5. 将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那么转化为二叉树时，该结点就没有左结点，所以 F 中叶结点的个数 就等于 $\mathrm{T}$ 中左孩子指针为空的结点个数，选C。 此题还可以通过一些特例来排除A、B、D选项。 6. 前缀编码的定义是在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。D 中编码 110 是编码 1100 的前缀，违反了前缀编码的规则，所以 D 不是前缀编码。 7. 按照拓扑排序的算法，每次都选择入度为 0 的结点从图中删去，此图中一开始只有结点 3 的入度为 0；删掉 3 结点后，只有结点 1 的入度为 0；删掉结点 1 后，只有结点 4 的入度为 0；删掉 4 结点后，结点 2 和结点 6 的入度都为 0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为 314265 和 314625，选 D。 8. 产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选 D。 9. 关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含 $\lceil 4 / 2\rceil -1 = 1$ 个关键字，所以每个结点中，关键字数量最少都为1个，即每个结点都有2个分支，类似与排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得叶子结点全在第四层，符合B树定义，因此选D。 10. 首先，第二个元素为 1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为 2，第 $1 + 2$ 个元素 4 明显比第 1 个元素 9 要大，A 排除；若增量为 3，第 i、i+3、i+6 个元素都为有序序列 $(\mathrm{i} = 1,2,3)$ ，符合希尔排序的定义；若增量为 4，第 1 个元素 9 比第 $1 + 4$ 个元素 7 要大，C 排除；若增量为 5，第 1 个元素 9 比第 $1 + 5$ 个元素 8 要大，D 排除，选 B。 11. 快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在2个这样的数的选项。A选项中2、3、6、7、9均符合，所以A排除；B选项中，2、9均符合，所以B排除；D选项中5、9均符合，所以D选项排除；最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。 12. 不妨设原来指令条数为 $x$ , 那么原 CPI 就为 $20 / x$ , 经过编译优化后, 指令条数减少到原来的 $70 \%$ , 即指令条数为 $0.7 x$ , 而 CPI 增加到原来的 1.2 倍, 即 $24 / x$ , 那么现在 P 在 M 上的执行时间就为指令条数 $\mathrm{CPI} = 0.7 x * 24 / x = 24 * 0.7 = 16.8$ 秒, 选 D。 13. 8 位定点补码表示的数据范围为-128~127，若运算结果超出这个范围则会溢出，A选项 $x + y = 103 - 25 = 78$ ，符合范围，A排除；B选项 $x + y = -103 - 25 = -128$ ，符合范围，B排除；D选项 $x - y = -103 + 25 = -78$ ，符合范围，D排除；C选项 $x - y = 103 + 25 = 128$ ，超过了127，选C。 该题也可按照二进制写出两个数进行运算观察运算的进位信息得到结果，不过这种方法更为麻烦和耗时，在实际考试中并不推荐。 14. (f1)和(f2)对应的二进制分别是(110011001001……)₂ 和(101100001100……)₂，根据IEEE754浮点数标准，可知(f1)的数符为1，阶码为10011001，尾数为1.001，而(f2)的数符为1，阶码为01100001，尾数为1.1，则可知两数均为负数，符号相同，B、D排除，(f1)的绝对值为 $1.001 \times 2^{26}$ ，(f2)的绝对值为 $1.1 \times 2^{-30}$ ，则(f1)的绝对值比(f2)的绝对值大，而符号为负，真值大小相反，即(f1)的真值比(f2)的真值小，即 $x < y$ ，选A。 此题还有更为简便的算法，(f1)与(f2)的前4位为1100与1011,可以看出两数均为负数，而阶码用移码表示，两数的阶码头三位分别为100和011，可知(f1)的阶码大于(f2)的阶码，又因为是IEEE754规格化的数，尾数部分均为1.xxx，则阶码大的数，真值的绝对值必然大，可知(f1)真值的绝对值大于(f2)真值的绝对值，因为都为负数，则 $(\mathrm{f}1)<(\mathrm{f}2)$ ，即 $xlchild == NULL && root->lchild == NULL) //若为叶子结点，累积wpl wpl += deep*root->weight; if(root->lchild != NULL) //若左子树不空，对左子树递归遍历 wpl_PreOrder(root->lchild, deep+1); if(root->rchild != NULL) //若右子树不空，对右子树递归遍历 wpl_PreOrder(root->rchild, deep+1); return wpl; ``` ②基于层次遍历的算法： ```txt define MaxSize 100 //设置队列的最大容量 int wpl_LevelOrder(BiTree root){ BiTree q[MaxSize]; //声明队列，end1为头指针，end2为尾指针 int end1, end2; //队列最多容纳MaxSize-1个元素 end1 = end2 = 0; //头指针指向队头元素，尾指针指向队尾的后一个元素 int wpl = 0, deep = 0; //初始化wpl和深度 BiTree lastNode; //lastNode用来记录当前层的最后一个结点 BiTree newlastNode; //newlastNode用来记录下一层的最后一个结点 lastNode = root; //lastNode初始化为根节点 newlastNode = NULL; //newlastNode初始化为空 q[end2++] = root; //根节点入队 while(end1 != end2){ //层次遍历，若队列不空则循环 BiTree t = q[end1++]; //拿出队列中的头一个元素 if(t->lchild == NULL & t->lchild == NULL) { wpl += deep*t->weight; } //若为叶子结点，统计wpl if(t->lchild != NULL) { //若非叶子结点把左结点入队 q[end2++] = t->lchild; newlastNode = t->lchild; } //并设下一层的最后一个结点为该结点的左结点 if(t->rchild != NULL) { //处理叶节点 q[end2++] = t->rchild; newlastNode = t->rchild; } if(t == lastNode) { //若该结点为本层最后一个结点，更新lastNode lastNode = lastNode; deep += 1; //层数加1 } } return wpl; //返回wpl ``` # 【评分说明】 ①若考生给出能够满足题目要求的其他算法，且正确，可同样给分。 (2)考生答案无论使用 C 或者 C++ 语言, 只要正确同样给分。 ③若对算法的基本设计思想和主要数据结构描述不十分准确，但在算法实现中能够清晰反映出算法思想且正确，参照①的标准给分。 ④若考生给出的二叉树结点的数据类型定义和算法实现中，使用的是除整型之外的其他数值，可视同使用整型类型。 ⑤若考生给出的答案中算法主要设计思想或算法中部分正确，可酌情给分。 注意：上述两个算法一个为递归的先序遍历，一个为非递归的层次遍历，读者应当选取自己最擅长的书写方式。直观看去，先序遍历代码行数少，不用运用其他工具，书写也更容易，希望读者能掌握。 在先序遍历的算法中，static 是一个静态变量，只在首次调用函数时声明 wpl 并赋值为 0，以后的递归调用并不会使得 wpl 为 0，具体用法请参考相关资料中的 static 关键字说明，也可以在函数之外预先设置一个全局变量，并初始化。不过考虑到历年真题算法答案通常都 直接仅仅由一个函数构成，所以参考答案使用static。若对static不熟悉的同学可以使用以下形式的递归： ```c int wpl_PreOrder(BiTree root, int deep){ //用于存储左子树和右子树的产生的wpl int lwpl, rwpl; lwpl = rwpl = 0; if(root->lchild == NULL && root->lchild == NULL) //若为叶子结点，计算当前叶子结点的wpl return deep*root->weight; if(root->lchild != NULL) //若左子树不空，对左子树递归遍历 lwpl = wpl_PreOrder(root->lchild, deep+1); if(root->rchild != NULL) //若右子树不空，对右子树递归遍历 rwpl = wpl_PreOrder(root->rchild, deep+1); return lwpl + rwpl; ``` C/C++语言基础好的同学可以使用更简便的以下形式： ```c int wpl_PreOrder(BiTree root, int deep){ if(root->lchild == NULL && root->lchild == NULL) //若为叶子结点，累积wpl return deep * root->weight; return (root->lchild != NULL ? wpl_PreOrder(root->lchild, deep + 1) : 0) + (root->rchild != NULL ? wpl_PreOrder(root->rchild, deep + 1) : 0); } ``` 这个形式只是上面方法的简化而已，本质是一样的，而这个形式代码更短，在时间有限的情况下更具优势，能比写层次遍历的考生节约很多时间，所以读者应当在保证代码正确的情况下，尽量写一些较短的算法，为其他题目赢得更多的时间。但是，对于基础不扎实的考生，还是建议使用写对把握更大的方法，否则可能会得不偿失。例如在上面的代码中，考生容易忘记三元式(x?y:z)两端的括号，若不加括号，则答案就会是错误的。 在层次遍历的算法中，读者要理解lastNode和newlastNode的区别，lastNode指的是当前遍历层的最后一个结点，而newlastNode指的是下一层的最后一个结点，是动态变化的，直到遍历到本层的最后一个结点，才能确认下层真正的最后一个结点是哪个结点，而函数中入队操作并没有判断队满，若考试时用到，读者最好加上队满条件，这里队列的队满条件为 $\mathrm{end1} == (\mathrm{end2} + 1)\% \mathrm{M}$ ，采用的是2014年真题选择题中第三题的队列形式。同时，考生也可以尝试使用记录每层的第一个结点来进行层次遍历的算法，这里不再给出代码，请考生自行练习。 # 42. 解答： 考察在给出具体模型时，数据结构的应用。该题很多考生乍看之下以为是网络的题目，其实题本身并没有涉及太多的网络知识点，只是应用了网络的模型，实际上考察的还是数据结构的内容。 # (1)图(1分) 题中给出的是一个简单的网络拓扑图，可以抽象为无向图。 # 【评分说明】 只要考生的答案中给出与图含义相似的描述，例如“网状结构”、“非线性结构”等，同样给分。 # (2)链式存储结构的如下图所示 弧结点的两种基本形态
Flag=1Next
ID
IP
Metric
Flag=2Next
Prefix
Mask
Metric
表头结点结构示意
RouterID
LN_link
Next
其数据类型定义如下：(3分) ```txt typedef struct{ ``` ```c unsigned int ID, IP; }LinkNode; //Link的结构 typedef struct{ unsigned int Prefix, Mask; }NetNode; //Net的结构 typedef struct Node{ int Flag; //Flag=1为Link; Flag=2为Net union{ LinkNode Lnode; NetNode Nnode }LinkORNet; unsigned int Metric; struct Node *next; }ArcNode; //弧结点 typedef struct HNode{ unsigned int RouterID; ArcNode *LN_link; Struct HNode *next; }HNODE; //表头结点 ``` 对应题 42 表的链式存储结构示意图如下。(2 分) ![](https://408.foreverlink.love/images/7f8a2636efcbd163c83a93a4854ef3c2.jpg) # 【评分说明】 ① 若考生给出的答案是将链表中的表头结点保存在一个一维数组中(即采用邻接表形式)，同样给分。 ②若考生给出的答案中，弧结点没有使用union定义，而是采用两种不同的结构分别表示Link和Net，同时在表头结点中定义了两个指针，分别指向由这两种类型的结点构成的两个链表，同样给分。 ③考生所给答案的弧结点中，可以在单独定义的域中保存各直连网络 IP 地址的前缀长度，也可以与网络地址保存在同一个域中。 (4) 数据类型定义中, 只要采用了可行的链式存储结构, 并保存了题目中所给的 LSI 信息,例如将网络抽象为一类结点, 写出含 8 个表头结点的链式存储结构, 均可参照①~③的标准给分。 (5)若考生给出的答案中, 图示部分应与其数据类型定义部分一致, 图示只要能够体现链 式存储结构及题42图中的网络连接关系（可以不给出结点内细节信息），即可给分。 ⑥若解答不完全正确，酌情给分。 (3)计算结果如下表所示。(4分)
目的网络路径代价（费用）
步骤1192.1.1.0/24直接到达1
步骤2192.1.5.0/24R1→R3→192.1.5.0/243
步骤3192.1.6.0/24R1→R2→192.1.6.0/244
步骤4192.1.7.0/24R1→R2→R4→192.1.7.0/248
# 【评分说明】 (1)若考生给出的各条最短路径的结果部分正确, 可酌情给分。 (2)若考生给出的从 R1 到达子网 192.1.x.x 的最短路径及代价正确, 但不完全符合代价不减的次序, 可酌情给分。 # 43. 解答： (1)因为题目要求路由表中的的路由项尽可能少，所以这里可以把子网 192.1.6.0/24 和 192.1.7.0/24 聚合为子网 192.1.6.0/23。其他网络照常，可得到路由表如下：(6 分)
目的网络下一条接口
192.1.1.0/24-E0
192.1.6.0/2310.1.1.2L0
192.1.5.0/2410.1.1.10L1
# 【评分说明】 ①每正确解答一个路由项，给2分，共6分。 (2)路由项解答不完全正确, 或路由项多于 3 条, 可酌情给分。 (2) 通过查路由表可知: R1 通过 L0 接口转发该 IP 分组。(1 分)因为该分组要经过 3 个路由器(R1、R2、R4), 所以主机 192.1.7.211 收到的 IP 分组的 TTL 是 $64 - 3 = 61$ 。(1 分) (3)R1 的 LSI 需要增加一条特殊的直连网络，网络前缀 Prefix 为“0.0.0.0/0”，Metric 为 10。(1 分) # 【评分说明】 考生只要回答：增加前缀 Prefix 为“0.0.0.0/0”，Metric 为 10，同样给分。 # 44. 解答： 该题为计算机组成原理科目的综合题型，涉及到指令系统、存储管理以及CPU三个部分内容，考生因注意各章节内容之间的联系，才能更好的把握当前考试的趋势。 (1)已知计算机 M 采用 32 位定长指令字, 即一条指令占 4B, 观察表中各指令的地址可知,每条指令的地址差为 4 个地址单位, 即 4 个地址单位代表 4B, 一个地址单位就代表了 1B,所以该计算机是按字节编址的。(2 分) (2)在二进制中某数左移二位相当于以乘四，由该条件可知，数组间的数据间隔为4个地址单位，而计算机按字节编址，所以数组A中每个元素占4B。(2分) (3)由表可知，bne指令的机器代码为1446FFFAH，根据题目给出的指令格式，后2B的内容为OFFSET字段，所以该指令的OFFSET字段为FFFAH，用补码表示，值为-6。(1分)当系统执行到bne指令时，PC自动加4，PC的内容就为08048118H，而跳转的目标是 08048100H，两者相差了 $18 \mathrm{H}$ ，即 24 个单位的地址间隔，所以偏移址的一位即是真实跳转地址的 -24/-6=4 位。(1 分)可知 bne 指令的转移目标地址计算公式为 $(\mathrm{PC}) + 4 + \mathrm{OFFSET} * 4$ 。(1 分) (4)由于数据相关而发生阻塞的指令为第2、3、4、6条，因为第2、3、4、6条指令都与各自前一条指令发生数据相关。(3分) 第6条指令会发生控制冒险。(1分) 当前循环的第五条指令与下次循环的第一条指令虽然有数据相关，但由于第6条指令后有3个时钟周期的阻塞，因而消除了该数据相关。(1分) # 【评分说明】 对于第1问，若考生回答：因为指令1和2、2和3、3和4、5和6发生数据相关，因而发生阻塞的指令为第2、3、4、6条，同样给3分。答对3个以上给3分，部分正确酌情给分。 # 45. 解答： 该题继承了上题中的相关信息，统考中首次引入此种设置，具体考察到程序的运行结果、Cache的大小和命中率的计算以及磁盘和TLB的相关计算，是一题比较综合的题型。 (1)R2里装的是i的值，循环条件是 $\mathrm{i} < \mathrm{N}(1000)$ ，即当i自增到不满足这个条件时跳出循环，程序结束，所以此时i的值为1000。(1分) (2) Cache 共有 16 行, 每块 32 字节, 所以 Cache 数据区的容量为 $16 * 32 \mathrm{~B} = 512 \mathrm{~B}$ 。 (1 分) P共有6条指令，占24字节，小于主存块大小(32B)，其起始地址为0804 8100H，对应一块的开始位置，由此可知所有指令都在一个主存块内。读取第一条指令时会发生Cache缺失，故将P所在的主存块调入Cache某一行，以后每次读取指令时，都能在指令Cache中命中。因此在1000次循环中，只会发生1次指令访问缺失，所以指令Cache的命中率为： $(1000\times 6 - 1) / (1000\times 6) = 99.98\%$ 。(2分) 【评分说明】若考生给出正确的命中率，而未说明原因和过程，给1分。若命中率计算错误，但解题思路正确，可酌情给分。 (3)指令 4 为加法指令，即对应 $\mathrm{sum} += \mathrm{A}[i]$ ，当数组 A 中元素的值过大时，则会导致这条加法指令发生溢出异常；而指令 2、5 虽然都是加法指令，但他们分别为数组地址的计算指令和存储变量 i 的寄存器进行自增的指令，而 i 最大到达 1000，所以他们都不会产生溢出异常。(2 分) 只有访存指令可能产生缺页异常，即指令3可能产生缺页异常。(1分) 因为数组A在磁盘的一页上，而一开始数组并不在主存中，第一次访问数组时会导致访盘，把A调入内存，而以后数组A的元素都在内存中，则不会导致访盘，所以该程序一共访盘一次。(2分) 每访问一次内存数据就会查TLB一次，共访问数组1000次，所以此时又访问TLB1000次，还要考虑到第一次访问数组A，即访问A[0]时，会多访问一次TLB（第一次访问A[0]会先查一次TLB，然后产生缺页，处理完缺页中断后，会重新访问A[0]，此时又查TLB)，所以访问TLB的次数一共是1001次。(2分) # 【评分说明】 ①对于第1问，若答案中除指令4外还包含其他运算类指令(即指令1、2、5)，则给1分，其他情况，则给0分。 ②对于第2问，只要回答“load指令”，即可得分。 ③对于第3问，若答案中给出的读TLB的次数为1002，同样给分。若直接给出正确的TLB及磁盘的访问次数，而未说明原因，给3分。若给出的TLB及磁盘访问次数不正确，但解题思路正确，可酌情给分。 # 46. 解答： 考察文件系统中，记录的插入问题。题目本身比较简单，考生需要区分顺序分配方式和连接分配方式的区别。 (1)系统采用顺序分配方式时，插入记录需要移动其他的记录块，整个文件共有200条记录，要插入新记录作为第30条，而存储区前后均有足够的磁盘空间，且要求最少的访问存储块数，则要把文件前29条记录前移，若算访盘次数移动一条记录读出和存回磁盘各是一次访盘，29条记录共访盘58次，存回第30条记录访盘1次，共访盘59次。(1分) F 的文件控制区的起始块号和文件长度的内容会因此改变。(1 分) (2)文件系统采用链接分配方式时，插入记录并不用移动其他记录，只需找到相应的记录，修改指针即可。插入的记录为其第30条记录，那么需要找到文件系统的第29块，一共需要访盘29次，然后把第29块的下块地址部分赋给新块，把新块存回内存会访盘1次，然后修改内存中第29块的下块地址字段，再存回磁盘(1分)，一共访盘31次。(1分) 4 个字节共 32 位，可以寻址 $2^{32} = 4 \mathrm{~G}$ 块存储块，每块的大小为 1KB，即 1024B，其中下块地址部分占 4B，数据部分占 1020B，那么该系统的文件最大长度是 $4 \mathrm{~G} \times 1020 \mathrm{~B} = 4080 \mathrm{GB}$ 。(2 分) # 【评分说明】 (1)第(1)小题的第2问，若答案中不包含文件的起始地址和文件大小，则不给分。 (2)若按 $1024 \times 2^{32} \mathrm{~B} = 4096 \mathrm{~GB}$ 计算最大长度, 给 1 分。 # 47. 解答： 这是典型的生产者和消费者问题，只对典型问题加了一个条件，只需在标准模型上新加一个信号量，即可完成指定要求。 设置四个变量 mutex1、mutex2、empty 和 full，mutex1，用于一个控制一个消费者进程一个周期(10次)内对于缓冲区的控制，初值为1，mutex2用于进程单次互斥的访问缓冲区，初值为1，empty代表缓冲区的空位数，初值为0，full代表缓冲区的产品数，初值为1000，具体进程的描述如下： ```c semaphore mutex1=1; semaphore mutex2=1; semaphore empty=n; semaphore full $= 0$ producer(){ while(1){ 生产一个产品; P(empty); //判断缓冲区是否有空位 P(mutex2); //互斥访问缓冲区 把产品放入缓冲区； V(mutex2); //互斥访问缓冲区 V(full); //产品的数量加1 } } consumer(){ while(1){ P(mutex1) //连续取10次 for(int $\mathrm{i} = 0$ ;i<=10;++i){ P(full); //判断缓冲区是否有产品 P(mutex2); //互斥访问缓冲区 从缓冲区取出一件产品; V(mutex2); //互斥访问缓冲区 V(empty); //腾出一个空位 消费这件产品; } ``` ```txt V(mutex1) } 1 ``` # 【评分说明】 ①信号量的初值和含义都正确给2分。 ②生产者之间的互斥操作正确给1分；生产者与消费者之间的同步操作正确给2分；消费者之间互斥操作正确给1分。 ③控制消费者连续取产品数量正确给2分。 (4)仅给出经典生产者-消费者问题的信号量定义和伪代码描述最多给3分。 (5)若考生将题意理解成缓冲区至少有 10 件产品, 消费者才能开始取, 其他均正确, 得 6 分。 (6)部分完全正确, 酌情给分。