考研数据结构与操作系统在线题库每日一练（二十三）

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

1、在平衡二叉树中，A是最小不平衡子树，它的左孩子平衡因子为1，右孩子平衡因子为0，其中平衡因子为左子树高度-右子树高度，问需要对失衡子树做（ ）调整？

A、LR

B、RR

C、RL

D、LL

2、使用Dijkstra算法求下图从顶点3到其它各顶点的最短路径，先后求得的最短路径顶点顺序为（ ）。

A、5，1，2，6，4

B、5，2，1，6，4

C、5，4，6，2，1

D、5，3，6，1，4

3、C（n）表示二叉排序树有n个结点时可以出现的形态数量，则C（1）、C（2）、C（3）、C（4）分别为（ ）？

A、1，2，4，14

B、1，2，5，14

C、1，2，4，8

D、1，2，5，8

1、试题答案：D

试题解析：

【考点】本题考查数据结构--查找--动态查找表--平衡二叉树--平衡二叉树的应用。
【解析】下图满足题干条件，其中h代表子树的高度。由此可知是在A的左孩子的左子树中插入结点导致A这棵子树不平衡的，所以应该进行LL型调整。故本题选D。

2、试题答案：A

试题解析：

【考点】本题考查数据结构--图--最短路径--从某顶点到其余各顶点的最短路径--Dijkstra算法。
【解析】用迪杰斯特拉算法分析顶点3到各个顶点的最短路径如下所示，由此知，先后求得的最短路径顶点顺序为5，1，2，6，4。故本题选A。

3、试题答案：B

试题解析：

【考点】本题考查数据结构--查找--动态查找表--二叉排序树。
【解析】
（1）C（1）= 1毋庸置疑；
（2）C（2）固定根结点，剩下一个结点可以是左孩子，可以是右孩子，C（2）=C（1）+ C（1）=2；
（3）C（3）固定根结点，剩下两个结点可以左0右2、左1右1、左2右0组合，因此C（3）=C（0）× C（2）+ C（1）× C（1）+ C（2）× C（0）=5；
（4）C（4）固定根结点，剩下三个结点可以左0右3、左1右2、左2右1、左3右0，C（4）=C（0）× C（3）+ C（1）×C（2）+ C（2）× C（1）+ C（3）× C（0）=14。
因此，C（1）、C（2）、C（3）、C（4）分别为1，2，5，14。故本题选B。