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

一、填空题

1． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;

2． 一个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

3． 串是一种特殊的线性表，_____；其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

4． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。

【答案】稳定

5． 空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

6． 应用prim 算法求解连通网络的最小生成树问题。

(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值

)

；2；k

(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

的值在

图的顶点数，应由用户定义

用二维数组作为邻接矩阵表示

生成树的边结点

边的起点与终点

边上的权值

最小生成树定义

从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点

初始化最小生成树

T

依次求MST 的候选边

遍历当前候选边集合

选具有最小权值的候选边

图不连通，出错处理

修改候选边集合

【答案】(1)

(2)

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于

中

是连通图

，

，v ，

直到

，开始，重复执行下述操作:在所有u 属于

加入集合

，同时将并入

的边为止。

属于E 中找一条代价最小的边

7． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】

；边稀疏

8． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4；2

9． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有

检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

10．表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。

【答案】

(表达式中的点(.)是数分隔符，如

是三个数)

二、判断题

11．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）

【答案】 ×

【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。

12．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）

【答案】√

【解析】堆排序:基本思想先将原始序列构造成一个堆(初始堆) ，使其n 个元素的最大(小) 值处于序列的第 —个位置；然后交换序列第一个元素与最后一个元素的位置。

13．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）

【答案】√

【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。

14．深度为k 的二叉树中结点总数小于等于2k ﹣l 。（ ）

【答案】 √

【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为2k ﹣l 。

15．数组是同类型值的集合。（ ）

【答案】 ×

【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。