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

一、填空题

1． 建立索引文件的目的是_____。

【答案】提高查找速度

2． 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

3． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

4． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】

在B 5． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素

中的存储位置k=_____。（注：矩阵元素下标从1开始）

【答案】93

【解析】对于上三角矩阵

，将代入得93。

6． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法

，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）

中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ）

{ if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/

{ （2） ;

if （node->rflag）（3）;

else {do t=*x；;

while （*x==node ）;

*x=t;

}

}

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

7． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

8． 以下是用类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:

p->Rchild=head:head->Lchild=p

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

9． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m

阶

个关键码。

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

10．设有个结点的完全二叉树顺序存放在向量

【答案】 树每个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____中，其下标值最大的分支结点为_____。 【解析】最大的分支结点是最后一个叶子结点的父结点。

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

【答案】记录；数据项

12．N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。

【答案】2（N-1）

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。

二、判断题

13．二叉树中除叶结点外，任一结点点的值大于等于该结点

【答案】×

【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点；其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。

14．二元查找树的任何结点的左右子树都是二元查找树。（ ）

【答案】√

【解析】二元查找树也称作二元排序树。二元查找树的性质：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树所有结点的值均大于它的根结点的值；③左右子树也分别为二元查找树。

15．AOE 网一定是有向无环图。（ ）

【答案】×

其左子树根结点的值小于该结点的值；其右子树根结的值，则此二叉树一定是二叉排序树。（ ）