文档内容
2010 年计算机学科专业基础综合试题参考答案
一、单项选择题
DBDBCC DBACD AADDC DDBCB BABBA BDCDC DACAB ACBA
1. 2. 3. 4. 5. 6. 7. 8.
9. 10. 11. 12. 13. 14. 15. 16.
17. 18. 19. 20. 21. 22. 23. 24.
25. 26. 27. 28. 29. 30. 31. 32.
33. 34. 35. 36. 37. 38. 39. 40.
1. 解析：
选项 A可由 in, in, in, in, out, out, in, out, out, in, out, out得到；选项 B 可由 in, in, in, out, out,
in, out, out, in, out, in, out得到；选项 C 可由 in, in, out, in, out, out, in, in, out, in, out, out 得到；选
项D可由in, out, in, in, in, in, in, out, out, out, out, out得到，但题意要求不允许连续三次退栈操作，
故 D 不可能得到。
【另解】先进栈的元素后出栈，进栈顺序为 a,b, c, d, e, f, 故连续出栈时的序列必然是按字
母表逆序的，若出栈序列中出现了长度大千等于 3 的连续逆序子序列，则为不符合要求的出栈
序列。
2. 解析：
本题的队列实际上是一个输出受限的双端队列。 A 操作： a 左入（或右入）、 b 左入、 c 右
入、 d 右入、 e 右入。 B 操作： a 左入（或右入）、 b 左入、 c 右入、 d 左入、 e 右入。 D 操作： a
左入（或右入）、 b 左入、 c左入、 d右入、 e左入。 C操作： a左入（或右入）、 b 右入、因 d 未
出，此时只能进队， c 怎么进都不可能在b 和 a之间。
【另解】初始时队列为空，第 1 个元素 a左入（或右入），而第 2 个元素 b 无论是左入还是
右入都必与 a相邻，而选项 D 中 a与 b 不相邻，不合题意。
3. 解析：
题中所给二叉树的后序序列为 d, b, c, a。结点 d无前驱和左子树，左链域空，无右子树，
右链域指向其后继结点 b; 结点 b 无左子树，左链域指向其前驱结点 d; 结点 c 无左子树，左链
域指向其前驱结点 b, 无右子树，右链域指向其后继结点 a。故选 D。
4. 解析：
插入 48 以后，该二叉树根结点的平衡因子由-1 变为-2, 在最小不平衡子树根结点的右子
树 CR) 的左子树 (L) 中插入新结点引起的不平衡属千 RL 型平衡旋转，需要做两次旋转操作
（先右旋后左旋）。
今
24
13 90
调整后，关键字 37 所在结点的左、右子结点中保存的关键字分别是 24、 53。5. 解析：
设树中度为i Ci=O, 1,2,3,4)的结点数分别为N;, 树中结点总数为N, 则树中各结点的度
。
之和等于N-1, 即N= 1 + N 1 + 2N 2 +3 N 3 + 4N4 = Ni+N尸岛+N 3 + N4, 根据题设中的数据， 即
可得到N。=82, 即树 T的叶结点的个数是82。
6. 解析：
哈夫曼树为带权路径长度最小的二叉树， 不一定是完全二叉树。哈夫曼树中没有度为1的
结点，B正确；构造哈夫曼树时， 最先选取两个权值最小的结点作为左、右子树构造一棵新的
二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左、右子树根结点权值之和， 其权值
不小千其左、右子树根结点的权值， 在与结点P的左、右子树根结点处于同一层的结点中，若
存在权值大于结点P权值的结点Q, 则结点Q的兄弟结点中权值较小的一个应该与结点P作为
左、右子树构造新的二叉树。 综上可知，哈夫曼树中任一非叶结点的权值一定不小千下一层
任一结点的权值。
7. 解析：
要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保待连通，首
先需要G的任意6个结点构成完全连通子图GI, 需nn( -1)/2= 6x( 6-1)/2 = 15条边， 然后再添
一条边将第7个结点与Gl连接起来， 共需16条边。
8. 解析：
拓扑排序的过程如下图所示。
勹
三二
输出e 输妙， 出b
©�0---,
三 出b 输出 。 输 出c
衫
：
三出'�输出c输：
0 © ©
输出d,得到aebcd 输出d,得到abecd 输出d,得到abced
可以得到3个不同的拓扑序列， 分别为abced、abecd、aebcd。
9. 解析：
折半查找法在查找成功时进行的关键字比较次数最多为Llog 刓+1, 即判定树的高度；折半
2
查找法在查找不成功时进行的关键字比较次数最多为l1ogn」+ 1。 题中n= 16, 因此最多比较
2
L1og t6」+1=5次。 也可以画出草图求解。
2
思考：若本题题干改为求最少的比较次数呢？
10. 解析：
快递排序的递归次数与元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；
若划分后分区不平衡， 则递归次数多。但快速排序的递归次数与分区处理顺序无关， 即先处理
较长的分区或先处理较短的分区都不影响递归次数。
此外，可以形象地把快速排序的递归调用过程用一个二叉树描述，先处理较长或较短分区，可以想象为交换某一递归结点处的左右子树，这并 不会影响树中的分支数 。
11. 解析：
题中所给的三趟排序过程中，每一趟排序是从前往后依次比较，使最大值 “ 沉底 ” ，符合
冒泡排序的特点 。
看第一趟可知仅有88被移到最后。
• 如果是希尔排序，则12,88, 10应变为10,12, 88。 因此排除希尔排序。
• 如果是归并排序，则长度为2 的子序列是有序的。 因此 可排除归并排序。
• 如果是基数排序，则16,5, 10应变为10,5, 16。 因此排除基数排序。
提示：对于此 类题，先看备选项的排序算法有什么特征，再看题目中的排序过程是否符合
这一特征，从而得出答案。 一般先从选项中的简单排序方法（插入排序、起泡排序、选择排序）
开始判断，若简单排序方法不符合，再判断排序方法（希尔排序、快速排序、堆排序、归并排
序）。
12. 解析：
CPU时钟频率（主频）越高，完成指令的一个执行步骤所用的时间就越短，执行指令的速
度越快，I正确。 数据通路的功能是实现CPU内部的运算器和寄存器以及寄存器之间的数据交
换，优化数据通路结构，可以有效提高计算机系统的吞吐量，从而加快程序的执行，II正确。
计算机程序需要先转化成机器指令序列才能最终得到执行，通过对程序进行编译优化可以得到
更优的指令序列，从而使得程序的执行时间也越短，III正确。
【另解】定量分析：CPU执行时间＝（程序指令条数x每条指令时钟周期数）／时钟频率。提
高时钟频率显然可以缩短CPU执行时间；编译优化可能减少程序的指令数或优化指令结构；优
化数据通路结构可能减少时钟周期，即提高时钟频率，故选D。
13. 解析：
本题的真正意图是考查补码的表示范围，而不是补码的乘法运算。 若采用补码乘法规则计
算出4个选项，是费力不讨好的做法，而且极容易出错。
8位补码所能表示的整数范围为-128�+12兀将4个数全部转换为十进制：rl =-2,r2=-14,
r3 = -112, r4 = -8, 得r2xr3 = 1568, 远超出了表示范围，发生溢出。
【提示】解题时，尤其是对于这种看似很复杂的题，不要轻易动笔，要弄清题目考查的真
正意图，而尽可能地 “ 走捷径 ” ，以免绕进命题者设计的 “ 死胡同 ” 。
14. 解析：
题中三种数据类型的精度从低到高为int-float-double, 从低到高的转换通常可以保持其
值不变，I 和III正确，而从高到低的转换可能会有数据的舍入，从而损失精度。 对于II, 先将
float型的f转换为int型，小数点后的数位丢失，故其结果不为真。 对于IV, 初看似乎没有问
o,
题，但浮点运算d+f时需要对阶 ，对阶后f的尾数有效位被舍去而变为 故d+f仍然为d,
o,
再减去d后结果为 故IV结果不为真。
此外，根据不同类型数据混合运算的 ” 类型提升 ” 原则，在IV中，等号左端的类型为double
型，结果不为真。
15. 解析：
用2Kx4位的芯片组成一个8Kx8位存储器，共需8片2Kx4位的芯片，分为4 组，每组由
2片2Kx4位的芯片并联组成2Kx8位的芯片，各组芯片的地址分配如下：
第一组(2个芯片并联）： OOOOH�07FFH。
第二组(2个芯片并联）：0800H�OFFFH。第三组(2个芯片并 联）： 1O OOH-17FFH。
第四组(2个芯片并 联）： 1800H-IFFFH。
地址OBIFH所在的芯片属于第二组，故其所在 芯片的最小地址为0800H。
16. 解析：
RAM( 分为DRAM和SRAM)断电后会失去信息，而ROM断电后不会丢失信息，它们
都采用 随机存取方式（注意，采用随机存取方式的存储器并不一定就是随机存储器）。 Cache一
般采用高速的SRAM制成，而ROM只可读，不能用作 Cache, III错误。DRAM需要定期刷新，
而ROM不需要刷新，故IV错误。
17. 解析：
Cache中存放的是主存的一部分副本，TLB(快表）中存放的是Page(页表）的一部分副本。在
同时具有虚拟页式存储器（有TLB)和Cache的系统中，CPU发出访存命令，先查找对应的
Cache块。
1)若Cache命中，则说明所需内容在 Cache 内， 其所在页面必然已调入主存，因此Page
必然命中，但TLB不一定命中。
2)若Cache不命中，并不能说明所需 内容未调入主存，和TLB、Page命中与否没有联 系。
但若TLB命中，Page也必然命中；而当Page命中，TLB则未必命中，故D不可能发生。
主存、Cache、TLB和Page的关 系如下图所示。
芦＿尸尸三］
【提示】本题看似既涉及虚拟存储器又涉及Cache, 实际上这里并不需要考虑Cache命中与
否。 因为一旦缺页，说明信息不在主存， 那么TLB 中就一定没有该页表项，所以不存在TLB
命中、Page缺失的情况，也根本谈不上访问 Cache 是否命中。
18. 解析：
读者首先必须明白 “ 汇编语言程序员可见 ” 的含义，即汇编语言程序员通过汇编程序可以
对某个寄存器进行访问。 汇编程序员可以通过指定待执行指令的地址来设置PC的值，如转移
指令、子程序调用指令等。 而IR、MAR、MDR 是CPU的内部工作 寄存器，程序员无法直接获
取和设置它们的值，也无法直接对它们进行 其他 操作，所以对程序员不可见。
【提示】＠指令寄存器 IR中的内容总是根据PC所取出的指令代码。＠在CPU的专用 寄存
器中，只有PC和PSWR是汇编程序员可见的。
19. 解析：
采用流水线方式，相邻或相近的两条指令可能会因为存在某种关 联，后一条指令不能按照
原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：＠结构相
关，又称资源相关；＠数据相关；＠控制相关，主要由转移指令引起。
数据旁路技术，其 主要思想是不必待某条指令的执行结果送回到寄存器，再从寄存器中取
出该结果，作为下一条指令的源操作数，而是直接将执行结果送到其他指令所需要的地方，这
样可以使流水线不发生停顿。
20. 解析：
典型的总线标准有： ISA、EISA、VESA、PCI、PCI-Express、AGP、USB、RS-232C等。
A中的CRT是纯平显示器；B中的CPI 是每条指令的时钟周期数；C中的RAM 是半导体随机
存储器、MIPS是每秒执行多少百万条指令数。21. 解析：
在单级（或单重） 中断系统中， 不允许中断嵌套。中断处理过程为：＠关中断；＠保存断
点；＠识别中断源；＠保存现场；＠中断事件处理；＠恢复现场；＠开中断；＠中断返回。其
中， ＠～＠由硬件完成，＠～＠由中断服务程序完成， 故选A。
【排除法】选项B、C、D的第一个任务（保存断点或关中断）都是由中断隐指令完成的，
即由硬件直接执行， 与中断服务程序无关。
22. 解析：
刷新所需带宽＝分辨率x色深X帧频=1600x1 200x24bitx85Hz= 3916.SMbps, 显存总带宽
的50%用来刷屏， 于是需要的显存总带宽为3916.SMbps/0.5= 7833.6Mbps:=:::: 飞34Mbps。
23. 解析：
操作系统提供的接口主要有两类：命令接口和系统调用。系统调用是能完成特定功能的子
程序，当应用程序请求操作系统提供某种服务时， 便调用具有相应功能的系统调用。库函数
则是高级语言中提供的与系统调用对应的函数（也有些库函数与系统调用无关）， 目的是隐
藏访管指令的细节，使系统调用更为方便、抽象。但要注意，库函数属千用户程序而非系统
调用， 是系统调用的上层。下图是Linux中的分层关系。
24. 解析：
引起进程创建的事件有：用户登录、作业调度、提供服务、应用请求等。I. 用户登录成功
后， 系统要为此创建一个用户管理的进程， 包括用户桌面、环境等。所有的用户进程会在该进
程下创建和管理。II. 设备分配是通过在系统中设置相应的数据结构实现的， 不需要创建进程。
III. 启动程序执行是典型的引起创建进程的事件。
25. 解析：
信号量表示相关资源的当前可用数量。当信号量K>O时，表示还有K个相关资源可用，
所以该资源的可用个数是1。而当信号量K
