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

一、填空题

1． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

3． 栈是_____的线性表，其运算遵循_____的原则。

；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）

4． 设二维数组A 的行和列的下标范围分别为

【答案】

当其值为

和

每个元素占2个单元，按行优先顺处的元素为_____。

序存储，第一个元素的存储起始位置为b ，则存储位置为

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是

时，则i=2，j=3。

5． 在一棵m 阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。

【答案】

最少

【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是

6． 阅读下列程序说明和裎序，填充程序中的_____。

本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：

（1）把根结点放入堆栈。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）

存放还没有转换过的结点，它的栈顶指针为

。

（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。

（1）

{（2）

If （ （3） ）

} }}

【答案】

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。

7． 求最短路径的Dijkstra 算法的时间复杂度为_____。

【答案】

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

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

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

【答案】稳定

10．

设单链表的结点结构为

为指针域，已知指针px 指向单链表中data 为x 的结

_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：

_____;

【答案】

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

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

12．n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注：（1）图的顶点号从0开始计；

（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；

（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。

）

.

【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

；

（“图有回路”）

二、选择题

13．已知有向图G=（V ，E ），其中

G 的拓扑序列是

（ ）。

【答案】A

【解析】设G=（V ，E ）是一个具有n 个顶点的有向图，V 中顶点序列

能被称

，则在序列中顶点Vi 为拓扑序列的条件：若是图中的边（即从顶点V i 到V j 有一条路径）

必须排在顶点Vj 之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列

是

14．假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。

A.146k