2. 计算机
  3. 阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。 函数说明 函数sort(iraa[]，int n)的功能是对数组a中的a[0]～a[n-1]这n个元素进行排序。排序过程如下：第一趟对所有的偶数下标p，比较a[p]和a[p+1]

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。 函数说明 函数sort(iraa[]，int n)的功能是对数组a中的a[0]～a[n-1]这n个元素进行排序。排序过程如下：第一趟对所有的偶数下标p，比较a[p]和a[p+1]

admin2007-03-15  110
问题 阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
函数说明
   函数sort(iraa[]，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)，则将两者交换；第三趟对偶数下标，第四趟对奇数下标，……，依次类推，直至整个数组元素有序排列为止。
函数
   void sort(iht a[],iht n)
   {
        int i，j，t，tag=1；
       for(j=0；j＜n；j++){
             for(i=(1)；i＜n-1； (2) ){
                   if (a＞a[i+1]){t=a[1]；a=a[i+1)；a[i+1]=t；tag=0；}
             }
             tag++；
             if((3)) break；
       }
   }
   对包含十个元素的数组a采用上述方法排序时，元素间的比较次数最少为  (4)  次，最多为  (5)  次。
选项
答案(1)j%2，及其等价形式． (2)i+=2，及其等价形式 (3)tag＞2，或tag==3或tag＞=3，及其等价形式 (4) 9 (5) 45
解析 本题考查的是交换排序。
   根据题目中给出的排序过程可知，第一趟比较的是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[1]与a[2]开始，因此，内循环控制变量i的初始值随着外循环控制变量，i的每一次变化而在0和1之间交替取值，因此函数中的空(1)处应填入“j% 2”或其等价形式。显然，i的递增量应为2，空(2)处应填入“i+=2”或其等价形式。
   排序时，只要在内循环中发生了元素的交换，则tag的值被置为0，通过外循环中的“tag++”操作又会将其变为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[O]与a[1]、a[2]与a[3]、a[4]与a[5]、a[6]与a[7]、a[8]与a[9]的比较，又进行了a[1]与a[2]、a[3]与a[4]、 a[5]与a[6]、a[7]与a[8]的比较，未发生交换，因此共进行9次元素间的比较后完成排序。相反地，当排序前元素已经呈递减排列时，要进行最多次数的比较才能完成排序，同时每次比较操作都伴随着交换处理。从题目中外循环次数为10可知，每相邻两趟内循环进行9次比较，所以总的比较次数为45。
转载请注明原文地址:https://kaotiyun.com/show/YzjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)