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

一、填空题

1． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

2． 在一棵m

阶的个数是_____。

【答案】

最少

【解析】m

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

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

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

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

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

5． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构（网状结构）

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

【答案】26

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

7． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））

【答案】归并；堆

树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的

关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字

8． 表达式

【答案】

的后缀表达式是_____。

.

9．

每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。

【答案】

，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的

【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。

10．实现字符串拷贝的函数strcpy 为：

【答案】

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

【答案】

12．以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。

void leafchain（BiTree Abt）

{p={BiTree）malloc （sizeof （BiTNode ））; If （!p ）{print£（“OVERFLOW\n”; exit （1）; }

head=p; top=0; if （bt ）

{top++; stack[top]=bt; while （top ）

{t=stack[top]; top--;

if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; } else {if（ （4） ）{top++; stack[top]= （5） ; } if （ （6） ）{top++; stack[top]= （5） ; } } }

（8） ; （9） ; } } 【答案】

p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild: p->Rchild=head:head->Lchild=p

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

〔始顶点号，终顶点号，权值）

t->Lchild!=null: t->Lchild:

（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条

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

的值在〈limits •h>中

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

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

//生成树的边结点

//边的起点与终点

//边上的权值

//最小生成树定义

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

//初始化最小生成树

T

//依次求MST 的候选边

//遍历当前候选边集合

//选具有最小权值的候选边

//图不连通，出错处理

//修改候选边集合