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

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

1、已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1，2，3，4，5，则不能得到的出队序列是（ ）。

A、5，4，3，1，2

B、5，3，1，2，4

C、4，2，1，3，5

D、4，1，3，2，5

2、非空循环单链表head的尾结点p满足（ ）。

A、 p->next== null

B、 p==null

C、 p->next==head

D、 p==head

3、若在序列中采用折半查找法进行查找，用来描述该查找过程的判定树的形状与（ ）有关。

A、序列中元素的值

B、序列中元素的排序次序

C、序列中元素的类型

D、序列中元素的个数

4、要在查找表上进行分块查找，要求索引表按键值有序顺序存储，且查找的表是（ ）。

A、按键值有序的链接表

B、链接表但键值不一定有序

C、按键值有序的顺序表

D、顺序表且块内无序、块间有序

5、若数据元素序列11，12，13，8，9，10，25，5，6是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。

A、插入排序

B、起泡排序

C、二路归并排序

D、选择排序

1、试题答案：D

试题解析：

【考点】本题考查队列的基本操作
【解析】本题的队列与传统的队列不同，我们将入队列的一端称为A端，将既能入队又能出队的一端称为B端，能够从一端插入另一端出队的结构为队列，能够从一端插入一端出队的结构为栈。因此本题中的A端插入+B端出队构成一个队列；B端的插入+B端的出队构成一个栈。对上述选项分别进行模拟。A选项5、4、3、1为倒序，是栈的出栈序列，因此5、4、3、1从B端插入，2从A端插入。具体过程为：1从B插入->2从A插入->3从B插入->4从B插入->5从B插入->5从B端出队->4从B端出队->3从B端出队->1从B端出队->2从B端出队。因此A选项正确。B选项5、3为逆序，1、2、4为正序。由此可知5、3从B插入从B端出队，1、2、4从A端插入，从B端出队。具体过程为：1从A插入->2从A插入->3从B插入->4从A插入->5从B插入->5从B端出队->3从B端出队->1从B端出队->2从B端出队->4从B端出队。因此B选项正确。C选项中4、2、1逆序，从B端插入从B端出队，3、5正序，从A端插入从B端出队。。具体过程为：1从B插入->2从B插入->3从A插入->4从B插入->4从B端出队->2从B端出队->1从B端出队->3从B端出队->5从A端插入->5从B端出队。因此C选项正确。D选项中4之前1、2、3已经入队，在这种情况下3不能在A、B之间，因此D选项错误，故本题选D。

2、试题答案：C

试题解析：

本题考查非空单循环链表的指针
非空单循环链表如下,可知rear所指结点的next域指针指向头结点，故本题选C。

3、试题答案：D

试题解析：

【考点】本题考查数据结构--查找--静态查找表--折半查找--折半查找的应用。
【解析】折半查找判定树一定是一棵平衡二叉树，序列中元素的个数可以决定该判定树的高度，而序列中元素的值、排序次序和类型对判定树的形状没有影响。故本题选D。

4、试题答案：D

试题解析：

分块查找是一种性能介于顺序查找和折半查找之间的查找方法。每一块中的关键字不一定是有序的，但前一块中的最大关键字必须小于后一块中的最小关键字，即要求整个表是“分块有序”的。故本题选D。

5、试题答案：A

试题解析：

起泡排序和选择排序第二趟排序后的结果中最大或最小的两个元素以及位于对应的位置上；起泡排序第二趟排序后的结果中每四个元素是有序的；插入排序第二趟排序后的结果中前两个元素是有序的。故本题选A。