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

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

1、下面程序段的时间复杂度是（ ）。for(i=0;i<m;i++) A[i]=0;for(i=0;i<m;i++) for(j=1;j<n;j++) A[i]+=5;

A、O(m+n)

B、O(m+n+1)

C、O(n)

D、O(m*n)

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

A、1或2

B、1或n-1

C、n-1或n-2

D、n-1

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

A、rear-front

B、rear-front+1

C、(rear-front+1)%(n+1)

D、(rear-front+n+1)%n

4、在长度为n顺序实现的线性表的第i（1≤i≤n）个位置之前插入一个元素，需要后移（ ）个元素。

A、i

B、n-i+1

C、n

D、1

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

A、2h-1

B、2h

C、2h+1

D、h+1

1、试题答案：D

试题解析：

第一个for循环内的语句执行m次，时间复杂度是O(m)，双层for循环内的语句执行m*n次，时间复杂度为O(m*n)，故本题选D。

2、试题答案：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。

3、试题答案：D

试题解析：

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

4、试题答案：B

试题解析：

对于顺序表的插入操作，若要在第i个位置之前插入一个元素，则需要将第i个位置到第n个位置的元素向后移动1个元素，需要后移的元素个数为n-i+1，故本题选B。

5、试题答案：A

试题解析：

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

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