试题2 (15 分，每空3分)

阅读下列函数说明和C代码，将应填入(n)处的字 句写在答题纸的对应栏内。

函数说明

函数sort(int a[]),int n)的功能是对数组a中的a[0}~a[n-1]这n个元素进行排序。排序过程如下：第一趟对所有的偶数下标p,比较a[p]和a[p+1]，若a[p]>a[p+1], 则将两者交换;第二趟对所有的奇数下标q，比较a[q]和a[q+1]，若a[q]>a[q+1],则将两者交换;第三趟对偶数下标，第四趟对奇数下标，...，依次类推，直至整个数组元素有序排列为止。

函数

对包含十个元素的数组a采用上述方法排序时，元素间的比较次数最少为(4)次，最多为(5) 次。

试题2分析

本题考查的是交换排序。

根据题目中给出的排序过程可知，第-趟比较的是a[0]与a[1]、a[2]与 a[3]、a[4]与a[5]等，第二趟比较的是a[1]与a[2]、a[3]与a[4]、a[5]与a[6]等，第三趟从a[0]与a[1]开始进行比较，第四趟再从a[l]与a[2]开始，因此，内循环控制变量i的初始值随着外循环控制变量j的每一次变化而在0和1之间交替取值，因此函数中的空(1)处应填入“j%2”或其等价形式。显然,i的递增量应为2，空(2)处应填入“i+=2”或其等价形式。

排序时，只要在内循环中发生了元素的交换，则tag的值被置为0，通过外循环中的“ag++”操作又会将其变为1;若在内循环中始终没有进行过相邻元素的交换处理，则tag的值将在外循环中不断递增，因此，当tag达到一定值时排序过程即可终止。

下面，考查相邻两趟没有发生交换的排序过程。

对于偶数下标，则有a[0]≤a[1]、a[2]≤a[3]、 a[4]≤a[5]等等 。

对于奇数下标，则有a[1]≤a[2]、a[3]≤a[4]、 a[5]≤a[6]等等。

综上，则有a[0]≤a[1]≤a[2]≤a[3]≤...≤a[n-2]≤a[n-1]。因此，函数中的空(3)处应填入“tag>=3”或其等价形式。

对于10 个元素的数组a，当元素已经呈非递减排列时，先进行了a[0]与a[1]、a[2]与a[3]、a[4]与a[S]、a[6]与 a[7]、a[8]与 a[9]的比较，又进行了a[1]与a[2]、a[3]与 a[4]、a[S]与a[6]、a[7]与a[8]的比较，未发生交换，因此共进行9次元素间的比较后完成排序。相反地，当排序前元素已经呈递减排列时，要进行最多次数的比较才能完成排序，同时每次比较操作都伴随着交换处理。从题目中外循环次数为10可知，每相邻两趟内循环进行9次比较，所以总的比较次数为45。

参考答案

(1) j%2，及其等价形式

(2) i+=2， 及其等价形式

(3) tag>2， 或tag==3或tag>=3， 及其等价形式

(4) 9

(5) 45