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

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

1、下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（ ）排序。

A、冒泡排序

B、希尔排序

C、快速排序

D、堆排序

2、已知有向图G=( V，E)，如右图所示，G的可能的拓扑排序为（ ）。

A、V1，V3，V4，V6，V2，V5，V7

B、V1，V3，V5，V6，V4，V2，V7

C、V1，V3，V4，V5，V2，V6，V7

D、V1，V2，V5，V3，V4，V6，V7

3、下三角矩阵A（n×n）按行优先顺序压缩在数组Sa[(n+1)*n/2]，若非零元素aij（0≤i，j<n）存放在Sa[k]中，则i，j和k之间的关系为（ ）。

A、k=i*n+j

B、k=j*n/2+1

C、k=（i+1）*i/2+j

D、k=（j-1）*n/2+i-1

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)*e，其后缀形式为（ ）。

A、-a+b*c/d

B、-a+b*cd/e

C、abcd/+e*-

D、-+*abcde

1、试题答案：C

试题解析：

【考点】本题考查排序算法的综合比较。
【解析】分析如下：
A：若序列已有序时，选择冒泡排序进行一趟后，发现两两元素比较并未发生交换，即可确定此时序列已经有序，排序结束。
B：若序列已有序时，选择排序每一趟排序过程中都没有元素交换，直到步长为1时，整个排序过程结束。
C：在快速排序中，通过基准元素把序列分成两个部分，一般选择第一个元素为基准元素。若序列已经有序，进行第一趟排序时，第一个元素（最小元素）作为基准会将整个序列分成两部分，左部分为空，右部分为剩余元素。第一趟排序时，左部分无需排序，右部分继续进行快速排序，选取右部分第一个元素作为基准将整个序列分成两部分，左部分为空，右部分为剩余元素。这一过程中，每次分块只减少一个元素，n个元素需要进行n-1次分块才能结束整个快速排序，浪费时间耗时更长。这是快速排序最糟糕的情况，时间复杂度为O(n²)。
D：堆排序的最好、最坏、平均时间复杂度都是O(nlogn)。
综上所述，在待排序数据已有序时，花费时间反而最多的是快速排序。故本题选C。

2、试题答案：A

试题解析：

【考点】本题考查拓扑排序。
【解析】首先，选择入度为0的顶点v1加入拓扑序列，然后删除该结点以及从该结点出发的边，此时入度为0的顶点有v2、v3。若选择v3加入拓扑序列后，则删除顶点v3以及从v3出发的所有边，此时入度为0的顶点有v2、v4，第三个加入拓扑序列的顶点不可能是v5，所以B中序列不可能是拓扑序列。若将v4加入拓扑序列，此时入度为0的顶点有v2、v6，第四个加入拓扑序列的顶点不可能为v5，所以C中序列不可能是拓扑序列。若将v6加入拓扑序列，此时入度为0的顶点只有v2，将其加入拓扑序列，并删除该结点以及从该结点出发的所有边，此时入度为0的顶点只有v5。将v5加入拓扑序列，并删除该结点以及从该结点出发的所有边，此时入度为0的顶点只有v7。将v7加入拓扑序列，并删除该结点以及从该结点出发的所有边，此时图中所有结点均已纳入拓扑序列，最终得到的拓扑序列为V1，V3，V4，V6，V2，V5，V7。故本题选A。

3、试题答案：C

试题解析：

【考点】本题考查下三角矩阵的压缩存储。
【解析】因为i从0开始，所以非零元素aij是第i+1行第j+1个元素。下三角矩阵A（n×n）按行优先顺序压缩时，aij是第（1+2+…+i）+j+1=（i+1）*i/2+j+1个元素，存储在数组Sa[k]中，它所对应的数组下标为k=（i+1）*i/2+j+1-1=（i+1）*i/2+j。故本题选C。

4、试题答案：C

试题解析：

5、试题答案：C

试题解析：

【考点】本题考查中缀表达式转后缀表达式。
【解析】在后缀表达式中，首个操作数前面一定不会出现运算符，所以选项A、B、D均错误。故本题选C。