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

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

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

A、rear-front

B、rear-front+1

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

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

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

A、仅有头指针的单链表

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

C、双链表

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

3、在长度为n且带头结点的链式存储实现的线性表的第i（0≤i≤n）个位置插入一个元素，需要查找运算（ ）次。

A、1

B、n-i

C、i

D、n-2

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

A、2h-1

B、2h

C、2h+1

D、h+1

5、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。

A、直接插入排序

B、希尔（ShelI）排序

C、简单选择排序

D、冒泡排序

1、试题答案：D

试题解析：

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

2、试题答案：D

试题解析：

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

3、试题答案：C

试题解析：

链式存储结构不是随机存取结构，因此在本题中查找第i个位置的元素需要从链表的头开始遍历查找链表，查找到第i个链表需要查找运算i次，故本题选C。

4、试题答案：A

试题解析：

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

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

5、试题答案：C

试题解析：

对于A，若初始序列完全有序，则关键字的比较次数为n-1，若无序，则比较次数>n-1，因此A错误；
对于B，希尔排序的关键字比较次数也会受到初始排列次数的影响，因此B错误；
对于C，简单选择排序通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换，选择排序的比较次数为 n*(n-1)/2，关键字的比较次数与关键字的初始状态无关，因此C正确。
对于D，冒泡排序若初始序列有序则仅需要进行一趟冒泡排序，比较次数为n-1，若初始序列无序，则比较次数>n-1，因此D错误。故本题选C。