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

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

1、设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70）， 其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。

A、15，25，35，50，20，40，80，85，36，70

B、15，25，35，50，80，20，85，40，70，36

C、15，25，35，50，80，85，20，36，40，70

D、15，25，35，50，80，20，36，40，70，85

2、下列排序方法中，哪一种方法是不稳定的（ ）。

A、冒泡排序

B、希尔排序

C、归并排序

D、直接插入排序

3、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。

A、9

B、11

C、15

D、不确定

4、根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（ ）。

A、是完全二叉树

B、不是完全二叉树

C、是满二叉树

D、不是满二叉树

5、下列算法的时间复杂度是（ ）。for(i=0;i<n;i++)c[i][j]=i+j;

A、O(1)

B、O(n)

C、O(log₂n)

D、O(n²)

1、试题答案：A

试题解析：

【考点】本题考查归并排序的应用。 

【解析】题干已说明含5个长度为2的有序子表，因此对序列进行排序时需将相邻子表划分为一组，即（25，50，15，35）为一组，（80，85，20，40）为一组，（36，70）为一组，因此第二趟排序后的结果为15，25，35，50，20，40，80，85，36，70，故本题选A。

2、试题答案：B

试题解析：

【考点】本题考查排序算法的稳定性。 

【解析】排序算法的稳定性是指若排序后的序列不改变原序列中相同关键字的相对位置，则称为稳定性排序，否则为不稳定性排序。冒泡排序、归并排序、直接插入排序均为稳定性排序，而希尔排序不是稳定性排序，故本题选B。

3、试题答案：B

试题解析：

【考点】本题考查二叉树的性质。 

【解析】对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明为：因为二叉树中所有结点的度均小于或等于2，所以其结点总数为n=n0+n1+n2。二叉树中，除根结点以外，其余结点均有一个分支进入，设分支总数为B，则有n=B+1。由于这些分支是由度为1或者度为2的结点射出的，所以有B=1*n1+2*n2。带入B=n-1可得，n0+n1+n2-1=n1+2*n2，即n0=n2+1。故本题选B。

4、试题答案：A

试题解析：

【考点】本题考查二叉树的性质。

 【解析】根据二叉树的先序序列和中序序列可以唯一的确认一棵二叉树，画出这棵二叉树如下：

由上述图结构可知，该二叉树是完全二叉树，不是满二叉树，因此B和C错误。A选项是肯定结论且其表述的范围比D选项表述的范围更加精确，故本题选A。

5、试题答案：B

试题解析：

本题考查时间复杂度。
该循环语句会执行n次，所以算法的时间复杂度为O(n)。故本题选B。