考研数据结构及程序设计在线题库每日一练（一十四）

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

1、设顺序队列的容量为MaxSize，其头指针为front，尾指针为rear，空队列的条件为（ ）。

A、front=rear

B、front=MaxSize

C、front+1=rear

D、rear=0

2、直接插入排序在最好情况下的时间复杂度为（ ）。

A、

B、

C、

D、

4、在一个双链表中，在ρ结点之前插入q结点的操作。

A、p->prior=q; q->next=p; p->prior->next-q; q->prior=p->prior;

B、q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;

C、q->next=p; p->next=q; q->prior->next =q; q->next=p;

D、p->prior->next=q; q->next=p; q->prior=p->prior; p->prior =q;

5、最不适合用做队列的链表（ ）。

A、只带队首指针的非循环双链表

B、只带队首指针的循环双链链表

C、只带队尾指针的循环双链表

D、只带队尾指针的循环单链表

1、试题答案：A

试题解析：

【考点】本题考查队列的判断条件。
【解析】为了方便起见，约定初始化建空队时，令front=rear=0。但是，当队空时，front=rear；当队满时，front=rear亦成立。因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：
（1）另设一个标志位以区别队列是空还是满。
（2）牺牲一个存储空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志（front指向队首元素，rear指向队尾元素的下一个元素）。即：
① 队空时：front=rear；
② 队满时：(rear+1)%maxsize=front。
综上所述，本题选A。

2、试题答案：B

试题解析：

【考点】本题考查直接插入排序在最好情况下的时间复杂度。
【解析】直接插入排序的核心思想就是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小则交换，直到全部元素都比较过。若整个待排序元素已经有序，则只需要比较n-1，且没移动元素，所以时间复杂度为O(n)。故本题选B。

4、试题答案：D

试题解析：

【考点】本题考查双链表的插入操作序列。
【解析】
在一个双链表中，在ρ结点之前插入q结点的示意图如下所示，其中① p->prior->next=q；② q->next=p；③ q->prior=p->prior；④ p->prior =q。故本题选D。

5、试题答案：A

试题解析：

【考点】本题考查链队列。
【解析】队列的特点是在队头出队元素，队尾入队元素。A选项中的只带队首指针的非循环双链表查找队尾的时间复杂度最长为O(n)，其他选项中的链表只需要O(1)的时间复杂度即可查找到队尾元素，所以只带队首指针的非循环双链表不适合做队列的链表。故本题选A。