当前位置：问答库＞考研试题

一、选择题

1． 归并排序中，归并的趟数是（ ）。

【答案】B

【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n

。因此每次归并元素的个数增加一倍。所以

所以归并的趟数为

2． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。

【答案】B 【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为

3． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。

A.245Mbps B.979Mbps C. D. 【答案】D

【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到

的时间用来刷新

1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：

4． 设栈S 和队列Q 的初始状态为空，元素依次通过栈S ，一个元素出栈 后即进队列Q ，若6个元素出队的序列是则栈S 的容量至少应该是（ ）。

A.6 B.4 C.3 D.2

【答案】C

5． 在虚拟存储管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（ ）。

A. 编辑

B. 编译 C. 链接 D. 装载 【答案】B

【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本，不涉及到任何与计算机运 行相关的事；编译是由编译程序将用户源代码编译成若干个目标模块，源地址编译成目标程序时，会形成逻辑地址；链接是由链接程序将编译后形成的一组目标模块，以及所需库函数链接，形成完整的装入模块；装入是由装入程序将装入模块装入内存。

6． 假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为间。若CPU

速度提高

A.55秒 B.60秒 C.65秒 D.70秒 【答案】D 。 CPU 速度提高【解析】

即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间

秒。速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。

7． 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。

A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35 C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68, 33, 34

【答案】A

【解析】各选项对应的查找过程如下图所示，从中看到选项B 、C 、D 对应的查找树都是二叉排序树，只有选项A 对应的查找树不是一棵二叉排序树，因为在以91为根的左子树中出现了比91大的结点94。

速度不变，则运行基准程序A 所耗费的时间是（ ）。

时

8． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。

A. 仅1 B. 仅2 C. 仅 1，2 D. 仅 2, 3 【答案】C

【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响

9． 计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。

A. 可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【答案】B

【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述，也就是解决问题的步骤序列。一个算法通常需要具备五大特性：有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出。

10．一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。

A.11 B.12 C.13 D.14

【答案】B

二、填空题

11．在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。

12．在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。