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

一、填空题

1． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

2． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

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

阶个关键码。

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

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

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

5． 以下是用类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;

树每个结点至多有_____个儿子，除

根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____

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: t->Lchild!=null: t->Lchild: p->Rchild=head:head->Lchild=p

6． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

【答案】（1）链表未到尾就一直进行

（2） 7．

【答案】5

8． 顺序栈用

【答案】

存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

将当前结点作为头结点后的第一元素结点插入

=_____

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。 9． 设有一个10阶对称矩阵A 采用压缩存储方式，（以行为主序存储：）则

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若则

则

的地址为

的地址为_____。

若

的地址为将代入得33。

10．遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

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

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

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

12．当两个栈共享一存储区时，栈利用一维数组当栈1空时

，

【答案】

为_____，栈2空时

，

表示，两栈顶指针为则

为_____，栈满时为_____。

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

二、判断题

13．如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）

【答案】×

【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。

14．在初始数据表已经有序时，快速排序算法的时间复杂度为

【答案】×

【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为〇（n2）。

15．m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）

【答案】√

【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。

16．若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）

【答案】×

【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。

（ ）