文档内容
2018 年计算机学科专业基础综合试题参考答案
一、单项选择题
BCCBBC DBACA AACDA DDDDA CBDDC ACACD ACDBB BDCD
1. 2. 3. 4. 5 6. 7. 8.
9. 10. 11. 12. n 14. 15. 16.
17. 18. 19. 20. 江 22. 23. 24.
25. 26. 27. 28. 泗 30. 31. 32.
扛
33. 34. 35. 36. 38. 39. 40.
1. 解析：
®
第一次调用：＠从 S1 中弹出 2和 3; 从 S2中弹出＋；＠执行3+2=5;@将 5 压入 S1 中，
第一次调用结束后 S1 中剩余 5,8, 5 (5 在栈顶）， S2中剩余＊，－（－在栈顶）。第二次调用： O从 S1
®
中弹出 5 和 8; 从 S2中弹出－；＠执行 8-5=3;@将 3 压入 SI 中，第二次调用结束后 S1 中剩
®
余 5, 3 (3 在栈顶）， S2中剩余＊。第三次调用：＠从 S1 中弹出 3 和 5; 从 S2中弹出＊；＠执行
5x3 = 15; @将 15 压入 S1 中，第三次调用结束后 S1 中仅剩余 15 (栈顶）， S2为空。故选B。
2. 解析：
A 的操作顺序：＠＠＠＠＠＠＠＠。 B 的操作顺序： ®CDCDCDCDCD@。 D 的操作顺序：
＠＠＠＠＠＠＠＠＠＠＠。对千 C: 首先输出 3, 说明 l 和 2 必须先依次入栈，而此后 2 肯定
比 1 先输出，因此无法得到 1,2 的输出顺序。
3. 解析：
数组N 的下标从 0 开始，第一个元素m1,1对应存入n。，矩阵 M的第一行有 12 个元素，第
二行有 11 个，第三行有 10 个，第四行有 9 个，第五行有 8 个，所以 m6,6是第 12+ 11 + 10 + 9 +
8 + 1 = 51 个元素，下标应为 50, 故选A。
4. 解析：
非叶结点的度均为 2, 且所有叶结点都位于同一层的完全二叉树就是满二叉树。对千一棵
高度为 h 的满二叉树（空树 h=O), 其最后一层全部是叶结点，数量为 2h-1; 总结点数为 2h- I。
因此当 2h-'=k时，可以得到 2h- I= 2k-l。
5. 解析：
构造一棵符合题意的哈夫曼树，如下图所示。o,
由此可知， 左子树为 右子树为1, 故答案为A。
6. 解析：
根据二叉排序树的特性：中序遍历(LNR)得到的是一个递增序列。图中二叉排序树的中
序遍历序列为Xi,X3,X 5,X 4,X 2, 可知X3<�5O&&A[i]<=n) ／／若A[i]的值介于1-n, 则标记数组B
B[A[i]一l]=l;
for (i=O"; i
