考研数据结构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、线性表的链式存储结构与顺序（连续）存储结构相比优点是（ ）。

A、便于插入和删除

B、便于随机存取

C、所有的操作/运算的算法简单

D、便于查找

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

A、仅有头指针的单链表

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

C、双链表

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

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

试题解析：

对于A，链式存储结构插入和删除不需要移动元素，仅需要修改指针，其操作的时间复杂度为O(1)，而顺序存储结构插入和删除均需要移动元素，其操作的时间复杂度为O(n)。对于B，链式存储结构不是随机存取结构而顺序表是随机存取结构，因此B错误；对于C和D，对于已知下标的查找，链表的查找操作需要从头开始，时间复杂度为O(n)，而顺序表可以通过下标直接访问，时间复杂度为O(1)，因此C和D错误，故本题选A。

3、试题答案：D

试题解析：

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

4、试题答案：B

试题解析：

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

5、试题答案：A

试题解析：

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

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