2. 计算机
  3. 阅读下列函数说明和C代码，将应填入(n)处的字句写在的对应栏内。 请根据算法的C代码，分析此算法效率。

阅读下列函数说明和C代码，将应填入(n)处的字句写在的对应栏内。 请根据算法的C代码，分析此算法效率。

admin2009-02-15  60
问题 阅读下列函数说明和C代码，将应填入(n)处的字句写在的对应栏内。
请根据算法的C代码，分析此算法效率。
选项
答案此局部冒泡排序算法至少需进行1趟扫描，至多需进行n-1趟扫描(其中只有一趟扫描是全局的，其余趟扫描都是局部扫描，扫描范围相对小得多。即在待排序数据初始有序(正序)情况下，关键字的比较次数为n-1，数据的移动次数为0；在待排序数据初始逆序的情况，关键字的比较次数为n(n—1)/2，最坏情况下，每一次比较均会发生数据的交换，即移动次数为3n(n-1)/2。显然局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。
解析 本题所涉及的算法是对冒泡排序算法的改进，即局部冒泡排序算法。题目说明中对这种局部冒泡排序算法的思想进行了详细的介绍，一定要仔细阅读。做题时，如考生对冒泡排序比较熟练，对于局部冒泡排序算法只要理解了其“只对待排序列作局部的冒泡处理”这一本质，回答问题1只需根据局部冒泡排序算法思想和程序代码进行对照阅读。问题2见答案分析。
转载请注明原文地址:https://www.kaotiyun.com/show/qwDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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