文档内容
2012 年计算机学科专业基础综合试题参考答案
一、单项选择题
1. B 2. A 3. A 4. B 5. C 6. C 7. C 8. A
9. D 10. A 11. D 12. D 13. B 14. D 15. D 16. A
17. C 18. C 19. C 20. D 21. D 22. B 23. C 24. B
25. B 26. A 27. D 28. A 29. B 30. C 31. A 32. B
33. B 34. C 35. A 36. B 37. C 38. A 39. D 40. D
1. 解析：
本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是n~l, 每调
用一次factO, 传入该层 facto的参数值减 l。采用递归式来表示时间复杂度有
0(1) n~1
>
T(n) ={T(n-1)+1 n 1
则 T(n)= T(n-1) + 1 = T(n-2) + 2 =…= T(l) + n-1 = O(n), 故时间复杂度为 O(n)。
2. 解析：
表达式求值是栈的典型应用。中缀表达式不仅依赖千运算符的优先级，而且要处理括号。
后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从
中缀表达式转换到后缀表达式需要用运算符进行处理，使其包含运算符优先级的信息，从而转
换为后缀表达式的形式。转换过程如下表：
运算符栈 中缀未处理部分 后缀生成部分 说明
# a+b-a*((c+d)/e-t)+g
# +b-a*((c+d)/e-f)+g a
+ b-a* ((c+d)le-f)+g a "+"入栈
+ -a*((c+d)/e-f)+g ab
a*((c+d)/e-f)+g ab+ "+"出栈，＂－”入栈
*((c+d)/e-f)+g ab+a
一＊ ((c+d)/e-f)+g ab+a "*"入栈
一＊（（ c+d)/e-f)+g ab+a 两个"("依次入栈
-•(( +d)/e-f)+g ab+ac
一＊（（＋ d)/e-f)+g ab+ac "+"入栈
一＊（（＋ )/e-f)+g ab+acd
一＊（ /e-f)+g ab+acd+ "+"和"("依次出栈
一＊（／ e-f)+g ab+acd+ "I" 入栈（续表）
运算符栈 中缀未处理部分 后缀生成部分 说明
-*(I -t)+g ab+acd+e
－＊（一 f)+g ab+acd+e/ "I"出栈，“－”入栈
-*(一 )+g ab+acd+e/f
-* +g ab+acd+e/f- "-"和"("依次出栈
+g ab+acd+e/f-* "*"出栈
＃ +g ab+acd+e/f-*- "-"出栈
＋ g ab+acd+e/f-*- "+"入栈
＃ ab+acd+e/f-*-g "+"出栈
可知， 栈中的操作符的最大个数为5。
3. 解析：
前序序列和后序序列不能唯一确定一棵二叉树， 但可以确定二叉树中结点的祖先关系： 当
两个结点的前序序列为XY与后序序列为YX时，则X为Y的祖先。考虑前序序列�'e,b, d, C、
后序序列bc, ,de, , 且，可知a为根结点，e为a的孩子结点。此外，a的孩子结点的前序序列�.b,
dc, 、 后序序列bc, ,d,�. 可知e是bed的祖先， 故根结点的孩子结点只有e。 故选A。
【排除法】显然a为根结点， 且确定e为a的孩子结点，排除D。各种遍历算法中左右子树
的遍历次序是固定的，若b也为a的孩子结点，则在前序序列和后序序列中e、b的相对次序应
是不变的， 故排除B, 同理排除C。
【特殊法】前序序列和后序序列对应着多棵不同的二叉树树形， 我们只需画出满足该条件
的任一棵二叉树即可， 任意一棵二叉树必定满足正确选项的要求。
a
(a) (b) (c) (d)
显然选A, 最终得到的二叉树满足题设中前序序列和后序序列的要求。
4. 解析：
所有非叶结点的平衡因子均为1, 即平衡二叉树满足平衡的最少结点情况， 如下图所示。
对于高度为N、左右子树的高度分别为N1- 和N2- 、所有非叶结点的平衡因子均为1的平衡二
叉树，总结点数的公式为：C
N
=C
凡I
+C'.
凡 2
+1, C1=1 , C
2
=2, C3=2+1 +1 = 4, 可推出C6=20。
勹／三三【画图法】先画出m和Tz; 然后新建一个根结点，连接T公飞构成T3; 新建一个根结点，
连接T 、飞构成T; 以此类推，直到画出T6, 可知飞的结点数为20。
3 4
c,
【排除法】对千选项A, 高度为6、 结点数为10 的树怎么也无法达到平衡。对于选项
结点较多时，考虑较极端情形，即第6层只有最左叶子的完全二叉树刚好有32个结点，虽然满
足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。同理D错误。
只可能选B。
5. 解析：
广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。
当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次 （顶点表遍历），
故时间复杂度为O(n),在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），
故时间复杂度为O(e), 算法总的时间复杂度为O(n+ e)。
6. 解析：
对角线以下元素均为零，表明只有顶点l到顶点j(i len2;lenl一一） ／／使p指向的链表与q指向的链表等长
.,g==p-
>next;
江en 江
�, 0立(q=stz;2 l <;.l en2 �P:2一一） 门使q指向的链表与p指向的链表等长
q=q->next;
while(p->next!=NULL&&p->next!=q-:->next){ II查找共同后缀起始点
p=p->next; ／／两个指针同步向后移动
.q=q一>next; p,,哭
一了夕~沪尸心“ 一鲨妇.. 、... ，于丫 沁. ， . ,3·心产心＼
立eturn·p一>p.ext; II返回共同后缀的起始点
【1)、2)的评分说明】 ＠若考生所给算法实现正确，且时间复杂度为O(m+n), 可给 12
分；若算法正确，但时间复杂度超过O(m+n), 则最高可给9分。
＠若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的 ，可 参照＠的标准给分。
© 若算法的基本设计思想描述或算法实现中部分正确， 可参照＠中各种情况的 相应给分
标准酌情给分 。
3)时间复杂度为O(lenl+len2)或O(max(lenl,len2)), 其中lenl、len2分别为两个链表 的
长度。
【3)的评分说明】 若考生所估计的时间复杂度与考生所实现的算法一致， 可给 1分。
43. 解答：
本题综合涉及多个考点：计算机的性能指标、存储器的性能指标、DMA的性能分析，DMA
方式的特点，多体交叉存储器的性能分析。
1)平均每秒CPU执行的指令数为：80M/4=20M, 故MIPS数为20;(1分）
平均每条指令访存1.5次，故平均每秒Cache缺失 的次数=20Mxl.5x(l-99%) = 300k; (1分）
当 C a c h e 缺 失 时 ， C P U 访 问 主 存 ， 主 存 与 C a c h e 之 间 以 块 为 传 送 单 位 ， 此 时 ， 主 存 带 宽 为
16Bx300k/s = 4.8MB/s。 在不考虑DMA传送的情况下，主存带宽至少达到 4.8MB/s才能满足
CPU的 访存要求。(2分）
2)题中假定在Cache缺失的情况下访问主存，平均每秒产生缺页中断300000x0.0005% = 1.5
次。因为存储器总线宽度为32位，所以每 传送32位数据， 磁盘控制器发出一次DMA请求，
故平均每秒磁盘DMA请求 的次数至少为l.5x4KB/4B= 1.5K = 1536。(2分）
3) CPU和DMA控制器同时要求使用存储器总线时，DMA请求优先级更高； (1分）
因为DMA请求得不到及时响应，10/ 传输数据可能会丢失。(1分）
4)四体交叉存储模式能提供的最大带宽为4x4B/50ns = 320MB/s。(2分）
44. 解答：
1)X 的机器码为[x]补 =11111101 1111 1111B, 即指令执行前(RI) =FDFFH, 右移l位后位
11111110 1111 1111B, 即指令执行后(Rl)= FEFFH。(2分）
2)每个时钟周期只能有一条指令进入流水线， 从第5个时钟周期开始， 每个时钟周期都
会有一条指令执行完毕， 故至少需要4+(5-1)=8个时钟周期。(2分）
3)l 3的ID段被阻塞的原因：因为l3与l 和l 都存在数据相关， 需等到l 和l 将结果写回
1 2 1 2
寄存器后，l3才能读寄存器内容，所以l3的ID段被阻塞CI分）。L的 IF段被阻塞的原因：因
为l4的 前一条指令l3在ID段被阻塞，所以L的IF段被阻塞(1分）。
注意：要求 ” 按序发射，按序完成 “ ，故2)中下一条指令的 IF必须和上一条指令的ID并
行， 以免因上一条指令发生冲突而导致下一条指令先执行完。
4)因2*x操作有左移和加法两种实现方法， 故x=x*2+a对应的指令序列为
L O A D • • . F {l, J x ]
I2 LOAD R2, .[a]
I3 SHL Rl
I4 ADD R l , R 2
II或者 Rl, Rl
IS STORE- R2, [x]
这5条指令在流水线中执行过程如下表所示。
卢
�:l'l'l'I' 时间单元
11 I 12 I 13 I 14 I 15 I 16 I 17
l3 IF IDIEXIMIWB（续表）
时间单元
I I I I 191 I I I I I I
2 I 3 I 4 5 6 7 8 JO II 12 13 14 15 16 I 17
!4 IF rn 1 Ex 1 M , WB
is IF IDIEXIMIWB
故执行x=x*2+a语句最少需要17个时钟周期。
45. 解答：
1)页框号为21。 理由： 因为起始驻留集为空， 因此0页对应的页框为空闲链表中的第三
个空闲页框 21, 其对应的页框号为21。
2)页框号为32。 理由：因 11> 10故发生第三轮扫描，页号为1的页框在第二轮已处千空
闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中， 其页 框号为32。
3)页框号为41。 理由： 因为第2页从来没有被访问过， 它不在驻留集中， 因此从 空闲页
框链表中取出链表头的页框 41, 页框号为41。
4)合适。 理 由：如果程序的时间局部性越好， 那么从空闲页框链表中重新取回的机会越
大， 该策略的优势越明显。
46. 解答：
1)文件系统中所能容纳的磁盘块总数为4TB/1KB= 232。 要完全表示所有磁盘块，索引项
中的块号最少要占32/8 = 4B。 而索引表区仅采用直接索引结构， 故512B的索引表区能容纳
512B/4B = 128个索引项。每个索引项对应一个磁盘块，所以该系统可支持的单个文件最大长度
是128x1KB = 128KB。
2)这里的考查的分配方式不同于我们所熟悉的三种经典分配方式， 但是题目中给出了详
细的解释。所求的单个文件最大长度一共包含两部分： 预分配的连续空间和直接索引区。
连续区块数 占2B, 共可以表示 2'6个磁盘块， 即226B。 直接索引区共504B/6B= 84个索引
项。所以该系统可支持的单个文件最大长度是226B+ 84KB。
为了使单个文件的长度达到最大， 应使连续区的块数字段表示的空间大小尽可能接近系统
最大容量4TB。分别设起始块号和块数分别占4B, 这样 起始块号可以寻址的范围是232个磁盘
块，共4TB, 即整个系统空间。 同样，块数字段可以表示最多232个磁盘块，共4TB。
47. 解答：
【解析】1)由题47-a 表看出，源IP地址为IP分组 头的第13-16字节。 表中 1、 3、 4号
分组的源IP地址均为192.168.0.8 Cc0a8 0008H), 所以1、 3、 4号分组是由H发送的。
题47-a 表中，1号分组封装的 TCP段的SYN=1,ACK=O, seq=846b41c5H; 2号分组封装的
TCP段的SYN=1,ACK= 1, seq= e059 9fefH , ack= 846b41c6H;3号分组封装的TCP段的ACK=1,
seq= 846b 41c6H, ack = e059 9flDH, 所以1、2、3号分组 完成了TCP连接的建立过程。
由于快速以太网数据帧有效载荷的最小长度为46字节， 表中 3、5号分组的总长度为40
(28H)字节，小 于46字节， 其余分组总长度均大 于46字节。所以3、 5号分组通过快速以太
网传输时需要填充。
2)由3号分组封装的TCP段可知，发送应用层数据初始序号为seq = 846b 41c6H, 由5
号分组封装的TCP段可知，ack为seq = 846b 41d6H, 所以S已经收到的应用层数据的字节数
