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" 入栈
1 Å ¾ Š Þ / © ~ N h
f 6 Z Q $
ž u ç
2 -
" >
‰ „ 2 - >
Ú @ á $ ²
} X , ) & '
x Ÿ ) ' & À ’ & ) ' X Û ‹ s æ é ,
®
ö `
p ÷
÷
! + ( q ÷
÷ z 1 R
V Ì § « J _
a ÷
(
( ÷ _ b ÷ › 1
O r Ü @ M Ê V B 0
M 3 9
< » ñ U = P W R { 2 -
L 4 m œ Ý \ ˜ à Î I C
\ ™ S
O £ G è “ ¥ ! +
Ô ¬ S J ¯
Á v š ¿ ¼ 4 j E Ñ
L 4 k
< Ð Í U = ! + H ° Ö ¨ " w E *
³ º … B ò Ò A
# [ í Ã †
‡
" *
Æ – ˆ ¹
" *
Ç µ G # î Ë Ø 3 ó Y T
o ÷
P W 3 9 / â ´ • ?
# [ õ ë € , ! ‘ Y T
8 6 Z Q $
. 0 ] D ¡ F
— ‚
È # ï / ã Ï ¸ Ž ª t ¤ . Ù
H ƒ ^ K :
I C Ó ^ K ” n 5
: 5
. 0 ] D ¢ F
?
É · N Œ ± $
l ÷
% ÷ d
% ÷
% ÷ g
÷ ÷ ÷ ÷
8 ÷ ½
A i
c
Fp) U G Jq * ë % ï B
V Œ £ ™
^ ¸ %¯ 6 % Ñ B £ ™
_
¸ ß {° 6 %
B
T‚K v r * % Õ w± Q f
F ½ U G ^ ¿ m ² Ö { Q /
E þ ~ ¥ 8œ — ³ ^ ¿
„ ¶ ‘ 5 ‰Œ ¶W} ž › ~ i: ‰
;"2 6
ÿ / Ò Ï ¬ «
\ — ³ S IP V L ¤ h V &B(< &
– s ž Mk o > <
‰ # ^ n
h Ç - 7
˜ ‚ J = ‡ ¾‘
¼ 7 $ ® 6J
´ .T } *
š ¹n $ ¤@ 5 8 žŽ ˜ ‚ J = ˆ ¦ ª O ¾ „ ¼
¨ . = ‡
¢ 5 _ P R ú D @ y b LƒH $ ] ° 1 ª S ‹ –•§
¨ . * = ˆ
¢N _ P R D @ v b ; 8 ¦ _ P R D @ y v Ã
i c - 7
[ Z H
Y- ûª O
2012年计算机408统考真题解析.pdf
