一、选择题

1． 对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是( )。

A. 每次分区后，先处理较短的部分

B. 每次分区后，先处理较长的部分

C. 与算法每次分区后的处理顺序无关

D. 以上三者都不对

【答案】A

【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为整个f 的最大深度为递归深度。

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

A.11

B.12

C.13

D.14

【答案】B

3． 在系统总线的数据线上，不可能传输的是( )。

A. 指令

B. 操作数

C. 握手(应答)信号

D. 中断类型号型号

【答案】C

【解析】握手(应答)信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。

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

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。

5． 动态存储管理系统中，通常可有( )种不同的分配策略。

【答案】C

【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。

6． 某网络的IP 地址空间为采用定长子网划分，子网掩码为则该网络的最大子网个数、每个子网内的最大可分配地址个数分别是( )。

A.32, 8

B.32, 6

C.8, 32

D.8, 30

【答案】B

【解析】子网号为5位，在CIDR 中可以表示个子网，主机号为3位，除去全0和全1的情况可以表示6个主机地址，答案为B 。

7． 在参考摸型中，下列功能需由应用层的相邻层实现的是( )

A. 对话管理

B. 数据格式转换

C. 路由选择

D. 可靠数据传输

【答案】B

【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换

等，故答案为B 。

8． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。

A. 分块

B. 顺序

C. 折半

D. 哈希

【答案】A

【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。

9． 若一个栈以向量

存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是( )。

【答案】C

【解析】题中初始栈顶指针top 为n+1, 而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。

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

A.245Mbps

B.979Mbps

C.

D.

【答案】D

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

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

11．现有容量为10GB 的磁盘分区，磁盘空间以簇(cluster )为单位进行分配，簇的大小为4KB , 若采用位图法管理该分区的空闲空间，即用一位(bit )标识一个簇是否被分配，则存放该位图所需簇的个数为( )

A.80

B.320

C.80K

D.320K

【答案】A

【解析】磁盘的簇的个数为：

而一个簇的位示图能管理的簇的个数为：

个