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

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

1、在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。 下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是（  ）。I. 简单选择排序II. 希尔排序III. 快速排序IV. 堆排序V. 二路归并排序

A、 仅I、III、IV

B、 仅I、III、V

C、 仅II、III、IV

D、 仅III、IV、V

2、设一个栈的输入序列为a、b、c、d，则借助该栈所得到的输出序列不可能是（ ）。

A、a、b、c、d

B、d、a、b、c

C、a、c、d、b

D、d、c、b、a

3、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ ）。

A、2，4，3，1，5，6

B、3，2，4，1，6，5

C、4，3，2，1，5，6

D、2，3，5，1，6，4

4、假设n为2的乘幂，并且n大于2，下列算法的时间复杂度是（ ）。int time(int n){ count =0; x = 2; while (x<n/2) { x*=2;count++; } Return (count);}

A、O(1)

B、O(log2n)

C、O(n)

D、

5、设a=6，b=4，c=2，d=3，e=2，则后缀表达式abc-/de*+的值为（ ）。

A、12

B、5.5

C、9

D、10

1、试题答案：A

试题解析：

【考点】本题考查排序算法的应用。
【解析】简单选择排序每一趟将最无序数组中的最小元素放入正确位置，因此I正确。希尔排序是划分子序列的排序，每趟排序得到局部有序序列，只有最后一趟排序故才能确定所有元素的位置，因此II错误。快速排序每一趟排序将比基准值小的放在其左边，比基准值大的放在其右边，因此每一趟排序后基准值的位置可以确定，III正确。堆排序每次构建大（小）根堆其堆顶元素为最大（小）值，每一趟堆排序都可以确认一个最大（小）值的位置，因此IV正确。二路归并排序对子表排序，得到局部有序序列，最后一趟排序才能确定元素的值，因此V错误。综上，只有I、III、IV正确，本题选A。

2、试题答案：B

试题解析：

栈是限定仅在表尾进行插入或删除操作的线性表。选项A中栈的操作过程是：a入栈、a出栈、b入栈、b出栈、c入栈、c出栈、d入栈、d出栈；选项C中栈的操作过程是：a入栈、a出栈、b入栈、c入栈、c出栈、d入栈、d出栈、b出栈；选项D中栈的操作过程是：a入栈、b入栈、c入栈、d入栈、d出栈、c出栈、b出栈、a出栈；选项B中栈在d出栈后，栈顶的元素是c，此时a需要c、b出栈之后再出栈。故本题选B。

3、试题答案：D

试题解析：

对于A，经过这样的操作可以得到该出栈序列：push(1)、push(2)、pop(2)、push(3)、push(4)、pop(4)、pop(3)、pop(1)、push(5)、pop(5)、push(6)、pop(6)；对于B，经过这样的操作可以得到该出栈序列：push(1)、push(2)、push(3)、pop(3)、pop(2)、push(4)、pop(4)、pop(1)、push(5)、push(6)、pop(6)、pop(5)；对于C，经过这样的操作可以得到该出栈序列：push(1)、push(2)、push(3)、push(4)、pop(4)、pop(3)、pop(2)、pop(1)、push(5)、pop(5)、push(6)、pop(6)；对于D，4在1之后入栈，因此4应当在1之前出栈，D序列不符合栈“后进先出”的特性，故本题选D。

4、试题答案：B

试题解析：

5、试题答案：C

试题解析：

先计算后缀表达式的值：
（1）a=6，将6入栈；
（2）b=4，将4入栈；
（3）c=2，将2入栈；
（4）-，弹出栈顶的2和4，计算4-2=2，将2入栈；
（5）/，弹出栈顶的2和6，计算6/2=3，将3入栈；
（6）d=3，将3入栈；
（7）e=2，将2入栈；
（8）*，弹出栈顶的2和3，计算3*2=6，将6入栈；
（9）+，弹出栈顶的6和3，计算3+6=8，得出最终结果9。
故本题选C。