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

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

1、设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中至少有（ ）个结点。

A、2h

B、2h-1

C、2h+1

D、h+1

2、设循环队列中数组的下标范围是0到n-1，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（ ）。

A、rear-front

B、rear-front+1

C、（rear-front+1）%（n-1）

D、（rear-front+n+1）%n

3、有n个球队参加的某联赛按单循环方式进行比赛，那么共需要进行（ ）场比赛。

A、n(n-1)/2

B、n

C、n(n-1)

D、n+1

4、下述编码中哪一个不是前缀码（ ）。

A、（00，01，10，11）

B、（0，1，00，11）

C、（0，10，110，111）

D、（1，01，000，001）

5、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数为（ ）。

A、n

B、2n-1

C、2n

D、n-1

1、试题答案：B

试题解析：

根据题干描述，画出符合要求的二叉树如下所示：

根据上图可知二叉树至少有2*（h-1）+1=2h-1，故本题选B。

2、试题答案：D

试题解析：

在本题中，front指向队首元素，rear指向队尾元素，因此元素个数应当为rear-front+1，因此A错误。再加n是为了保证当rear<front时，计算出的结果是非负数，因此B错误。数组的最大容量为n，因此C错误，故本题选D。

3、试题答案：A

试题解析：

n个球队需要和除自身以外的其余队比赛，因此n*(n-1)，而A同B比赛与B同A比赛是一样的，将重复计算的部分去掉n*(n-1)/2。这种计算思路与求有n个顶点的完全无向图的边数的思路是一样的。故本题选A。

4、试题答案：B

试题解析：

在哈夫曼编码每个编码都不会其他编码的前缀，在B选项中0是00的前缀，1是11的前缀，因此B不是前缀码，其余选项均为前缀编码，故本题选B。

5、试题答案：A

试题解析：

当将两个有序表合并为一个有序表时，具体来说，从两个有序表中各取一个元素比较大小，较小的元素放入新表中，同时将该元素所在的表的指针向后移动一位，重复此过程直到某一个表遍历完毕。最后，将未遍历完毕的表中的元素直接复制到新表中。当其中一个有序表的最大元素小于另一个有序表的最小元素时，此时比较次数最少，为n。故本题选A。