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

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

1、若某栈的输入序列为1，2，3，…，n，输出序列的第2个元素为n，则第3个输出元素为（ ）。

A、1或2

B、1或n-1

C、n-1或n-2

D、n-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、如果某应用在线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A、仅有头指针的单链表

B、仅有头指针的单循环链表

C、双链表

D、仅有尾指针的单循环链表

4、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。

A、2h-1

B、2h

C、2h+1

D、h+1

5、已知完全二叉树有10个结点，则整棵二叉树有（ ）个度为1的结点？

A、2

B、1

C、0

D、不确定

1、试题答案：C

试题解析：

栈具有“后进先出”的特性，若第二个输出序列为n，则栈的基本操作有以下两种：
① push(1) …pop(?)…push(n-1) push(n) pop(n) pop(n-1)…；
② push(1)…push(n-2) push(n-1) pop(n-1) push(n) pop(n) pop(n-2)…。
根据上述两种情况分析，可以得出第3个输出序列或者为n-1或者为n-2，故本题选C。

2、试题答案：D

试题解析：

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

3、试题答案：D

试题解析：

对于仅有头指针的单链表而言，在结尾插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于仅有头指针的单循环链表，在结尾处插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于双向链表而言，在结尾插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于仅有尾指针的单循环链表，在结尾插入元素的时间复杂度为O(1)，删除首元素的时间复杂度为O(1)。故本题选D。

4、试题答案：A

试题解析：

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

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

5、试题答案：B

试题解析：

由于树的结点数较少，可以采用画图法解决本题，画出10个结点的完全二叉树如下：

根据上图度为1的结点个数为1，故本题选B。