2. 计算机
  3. 下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。 A：待排序数组 p,r：数组元素下标，从p到r q：划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于i的元素

下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。 A：待排序数组 p,r：数组元素下标，从p到r q：划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于i的元素

admin2010-01-15  47
问题 下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。
   A：待排序数组
   p,r：数组元素下标，从p到r
   q：划分的位置
   x：枢轴元素
   i：整型变量，用于描述数组下标。下标小于或等于i的元素的值，小于或等于枢轴元素的值
   j：循环控制变量，表示数组元素下标
   
(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素。下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i,j)表示随机取i到j之间的一个数，包括i和j。
   
   (2)随机化快速排序是否能够消除最坏情况的发生? (10)。(是或否)
选项
答案由于随机化的快速排序的划分调用了传统的快速排序算法的PARTITION操作，而传统的划分每次以数组的最后一个元素作为枢轴元素，因此随机化的划分操作中每次先随机获得一个元素，将其与最后一个元素交换。随机化的快速排序消除了输入数据的不同排列对算法性能的影响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。
解析
转载请注明原文地址:https://kaotiyun.com/show/i0DZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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