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

一、填空题

1． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

2． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

3． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

4． 已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

5． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

6． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】O(1)；O(n)

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

二、单项选择题

7． 设有一棵3阶B 树, 如下图所示。删除关键字78得到一棵新B 树, 其最右叶结点所含的关键字是（ ）。

图 3二叉树图

A.60

B.60, 62

C.62, 65

D.65

【答案】D 。

【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于

而与该结点相邻的右兄弟(或左兄弟) 结点中的关键字数目大于

(或最大) 的关键字上移至双亲结点中, 而将双亲结点中小于(或大于) 且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下, 其最右叶结点所含的关键字是65。

, , 则需将其兄弟结点中最小

8． 用直接插入排序方法对下面4个序列进行排序(由小到大) ，元素比较次数最少的是（ ）。

A.94，32，40，90，80，46，21，69

B.32，40，21，46，69，94，90，80

C.21，32，46，40，80，69，90，94

D.90，69，80，46，21，32，94，40

【答案】C

9． 对矩阵压缩存储是为了（ ）。

A. 方便运算

B. 方便存储

C. 提高运算速度

D. 减少存储空间

【答案】D

【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。

10．—次总线事物中, 主设备只需给出一个首地址, 从设备就能从首地址开始的若干连续单元格读出或写入的个数, 这种总线事务方式称为（ ）

A. 并行传输

B. 串行传输

C. 突发

D. 同步

【答案】C

【解析】猝发数据传输方式:在一个总线周期内传输存储地址连续的多个数据字的总线传输方式

11．下列关于闪存(FlashMemory)的叙述中, 错误的是（ ）。

A. 信息可读可写, 并且读、写速度一样快

B. 存储元由MOS 管组成, 是一种半导体存储器

C. 掉电后信息不丢失, 是一种非易失性存储器

D. 采用随机访问方式, 可替代计算机外部存储器

【答案】A 。

【解析】考查闪存的特性, 闪存是EEPROM 的进一步发展, 可读可写, 用MOS 管的浮栅上有无电荷来存储信息, 它依然是ROM 的一种, 故写速度比读速度要慢不少。闪存是一种非易失性存储器, 它采用随机访问方式, 现在常见的SSD 固态硬盘就是由flash 芯片组成的, 故答案为A 。

12．下列关于UDP 协议的叙述中, 正确的是（ ）

Ⅰ提供无连接服务

Ⅱ提供复用/分用服务

Ⅲ通过差错校验, 保障可靠数据传输

A. 仅Ⅰ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅱ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

【答案】B

UDP 无连接创建, 提供多路复用服务。【解析】虽然有差错检验, 但是不能保证可靠数据传输,

所以Ⅲ错误。

13．n 个结点的线索二叉树上含有的线索数为（ ）。

A.2n

B.n ﹣1

C.n ＋1

D.n