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

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

1、下面关于B树和B+树的叙述中，不正确的结论是（ ）。

A、B树和B+树都能有效地支持顺序查找

B、B树和B+树都能有效地支持随机查找

C、B树和B+树都是平衡的多分树t

D、B树和B+树都可用于文件的索引结构

2、在下列排序方法中，（  ）方法可能出现这种情况: 在最后一趟开始之前， 所有的元素都不在其最终应在的正确位置上。

A、快速排序

B、冒泡排序

C、堆排序

D、插入排序

3、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个序列施加同样的排序操作。直到子序列为空或只剩一个元素为止。这样的排序算法是（ ）。

A、直接选择排序

B、直接插入排序

C、快速排序

D、起泡排序

4、设head(L)、tail(L)分别为取广义表表头、表尾的操作，则从广义表L=（（x，y，z），a，（u，v，w））中取出原子u的运算为（ ）。

A、head(tail(tail(head(L))))

B、tail(head(head(tail(L))))

C、head(tail(head(tail(L))))

D、head(head(tail(tail(L))))

5、若栈采用顺序存储方式存储。现两栈共享空间V[1…m]，top[i]代表第i个栈（i=1，2）栈顶，栈1的底在V[1]，栈2的底在V[m]，则栈满的条件是（ ）。

A、top[2]-top[1]=0

B、top[1]+1=top[2]

C、top[1]+top[2]=m

D、top[1]=top[2]

1、试题答案：A

试题解析：

【考点】本题考查B树和B+树的特点。
【解析】B树只能支持随机查找，而B+树是有序的树，既能支持随机查找，又能支持顺序查找，所以选项A说法错误。故本题选A。

2、试题答案：D

试题解析：

【考点】本题考查几种常见的排序算法。
【解析】
（1）快速排序：每一趟排序都可以确定枢轴元素的最终位置。
（2）冒泡排序：每一趟排序都可以确定一个最大或最小元素的最终位置。
（3）堆排序：每一趟都选取堆顶元素（最大或最小元素）加入有序序列，即可确定最大或最小元素的最终位置。
（4）插入排序：最后一趟插入的可能是最小元素，导致所有元素都不在其最终位置上。
综上所述，本题选D。

3、试题答案：C

试题解析：

【考点】本题考查快速排序的思想过程。
【解析】
（1）直接选择排序：每一趟在待排序元素中选取关键字最小的元素加入有序子序列中。
（2）直接插入排序：把n个待排序的元素看成一个有序表和一个无序表，开始时有序表只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
（3）快速排序：在待排序序列中选择一个基准值，然后将小于基准值的数字放在基准值左边，大于基准值的数字放在基准值右边，第一趟排序后基准元素将整个序列划分成两个子序列。接着继续对这两部分序列递归排序，直到子序列为空或者只剩一个元素为止。
（4）起泡排序：重复走访要排序的序列，对所有相邻记录的关键字值进行比较，如果是逆顺（a[j]>a[j+1]），则将其交换位置。排序过程中每次从后往前冒一个最小值，且每次能确定一个关键字在序列中的最终位置。
综上所述，对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个序列施加同样的排序操作。直到子序列为空或只剩一个元素为止。这样的排序算法是快速排序算法。故本题选C。

4、试题答案：D

试题解析：

【考点】本题考查广义表表头和表尾操作。
【解析】tail(L)=（a，（u，v，w））；tail(tail(L))=（（u，v，w））；head(tail(tail(L)))=（u，v，w）；head(head(tail(tail(L))))=u。故本题选D。

5、试题答案：B

试题解析：

【考点】本题考查共享栈。
【解析】在共享栈中，栈1和栈2的空间均向中间延伸，当栈1中入栈一个元素，指针top[1]向后移动一个位置后，top[1]恰好与top[2]指向同一个位置，则说明该共享栈已满，即判断栈满的条件为top[1]+1=top[2]。故本题选B。