考研数据结构在线题库每日一练（六十五）

本文提供考研数据结构在线题库每日一练，以下为具体内容

1、将森林F转换为对应的二叉树T，F中叶结点的个数等于（  ）。

A、 T中叶结点的个数

B、 T中度为1的结点个数

C、 T中左孩子指针为空的结点个数

D、 T中右孩子指针为空的结点个数

2、对一棵二叉排序树按（ ）遍历，可得到结点值从小到大的排序序列。

A、先序

B、中序

C、后序

D、层次

3、栈和队列的共同特点是（ ）。

A、只允许在端点处插入和删除元素

B、都是先进后出

C、都是先进先出

D、没有共同点

4、若无向图G有7个顶点，至少需要（ ）条边，才能保证该图一定是连通图（边可依附任两顶点，但无重复边和自环）。

A、6

B、16

C、31

D、42

5、栈和队列主要区别为（ ）。

A、逻辑结构不同

B、存储结构不同

C、包含元素不同

D、插入删除操作限定不同

1、试题答案：C

试题解析：

【考点】本题考查森林转换为二叉树的步骤。
【解析】森林转为二叉树的步骤如下：
（1）将每棵树转为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
|因此森林转换为二叉树时，森林的叶子结点没有左右子树，按照“左孩子右兄弟”的转换理论，森林的叶子结点转换二叉树后没有左孩子。但由于无法确定叶子结点是否有右兄弟结点，因此无法判断叶子结点转换为二叉树是否有右孩子。故本题选C。

2、试题答案：B

试题解析：

【考点】本题考查二叉排序树的性质。
【解析】一棵非空的二叉排序树具有以下性质：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值；
（3）它的左、右子树也分别为二叉排序树。
因此，通过对比中序遍历的算法思想，易知中序遍历二叉排序树可得到一个关键字的有序序列。故本题选B。

3、试题答案：A

试题解析：

本题考查栈和队列的共同特点。
栈的特点是“先进后出”，只能在栈顶插入和删除元素；队列的特点是“先进先出”，在队头删除元素、队尾插入元素，所以栈和队列的共同点是都只能在端点处进行元素操作。故本题选A。

4、试题答案：B

试题解析：

连通图从任一顶点出发即可以访问所有顶点。本题要求尽可能少的边保证图一定是连通图，因此7个顶点中的前6个顶点构成一个完全连通图，再增加一条边将第7个顶点连接到完全连通图即可。因此边数=6*(6-1)/2+1=16，故本题选B。

5、试题答案：D

试题解析：

A：栈和队列的逻辑结构相同，都属于线性结构。
B：栈和队列都可以顺序存储和链式存储。
C：栈和队列包含的元素可以相同，也可以不同。
D：栈和队列都属于操作受限的数据结构，其主要区别是栈的插入删除操作仅限于栈顶这一端，队列的插入删除操作限于队头和队尾这两端。
综上所述，本题选D。