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

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

1、希尔排序的组内排序采用的是（  ）。

A、 直接插入排序

B、 折半插入排序

C、 快速排序

D、 归并排序

2、如下图1，从顶点1出发，按照广度优先规则遍历，可能得到的序列为（ ）。

A、1352467

B、142375

C、1234576

D、1354672

3、中缀表达式A*（B+C）/（D-E+F）的后缀表达式是（ ）。

A、A*B+C/D-E+F

B、AB*C+D/E-F+

C、ABC+*DE-+/

D、ABCDEF*+/-+

4、程序段for(i=n-1; i<1; i--) for(j=1; j<n; j++) if(A[j]> A[j+1]) swap(A[j]，A[j+1]);其中n为正整数，则最后一行语句执行，在最坏情况下是（ ）。

A、

B、

C、

D、

5、下列排序算法中，（ ）排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A、选择

B、冒泡

C、归并

D、堆

1、试题答案：A

试题解析：

【考点】本题考查希尔排序。
【解析】希尔排序的基本思想是现将整个待排序列分割成若干子序列，对子序列分别进行插入排序，待整个序列中的记录基本有序之后，再对整个序列进行一次插入排序。希尔排序的组内排序采用的是直接插入排序。故本题选A。

2、试题答案：C

试题解析：

【考点】本题考查图的广度优先遍历。
【解析】从1出发访问与1相邻的所有顶点，即2453（顺序可以有所不同）。因此，B和D可以排除，不满足遍历要求。A：若访问完13524，此时与顶点3和顶点5相邻的顶点均已访问完，与顶点2相邻的顶点还剩顶点7未访问，所以接下来访问顶点7，而不是顶点6。因此，A排除。C：若访问完12345，此时与顶点2相邻的顶点还剩顶点7未访问，所以接着访问顶点7。与顶点3相邻的顶点均已访问，继续看检查顶点4，与其相邻的顶点还剩顶点6未访问，所以接着访问顶点6。最终整个图按照广度优先遍历得到的序列为1234576。故本题选C。

3、试题答案：C

试题解析：

【考点】本题考查中缀表达式转后缀表达式。
【解析】
（1）首先从左至右标出中缀表达式中各个元素符号运算的先后顺序，如下所示：

（2）依次按照运算符的先后顺序将运算符移动到两个操作数的后面，即可得到中缀表达式A*（B+C）/（D-E+F）对应的后缀表达式为BC+*DE-+/。故本题选C。

4、试题答案：C

试题解析：

5、试题答案：C

试题解析：

【考点】本题考查常见排序算法的特点。
【解析】
（1）选择排序每趟排序会选择一个最大（或最小）的元素，将其放置在其最终位置上。
（2）冒泡排序的一趟过程中，相邻元素两两比较，若出现大小相反的情况则交换两个元素的位置，一趟排序后总会有一个最大（或最小）的元素冒到其最终位置。
（3）归并排序在一趟排序结束后不一定能选出一个元素放置在其最终位置上。
（4）堆排序过程中，通过建堆和调整堆可以选出一个最大（或最小）的元素，放在其最终位置上。
综上所述，本题选C。