2. 计算机
  3. 在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列{Q，H，C，Y，P，A，M，S，R，D，F，　X}中的关键码按字母的升序重新排列，则(24)是冒泡排序一趟扫描的结果，(25)是初始步长为4

在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列{Q，H，C，Y，P，A，M，S，R，D，F，　X}中的关键码按字母的升序重新排列，则(24)是冒泡排序一趟扫描的结果，(25)是初始步长为4

admin2019-03-04  70
问题 在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列{Q，H，C，Y，P，A，M，S，R，D，F，　X}中的关键码按字母的升序重新排列，则(24)是冒泡排序一趟扫描的结果，(25)是初始步长为4的希尔排序一趟扫描的结果，(26)是两路归并(合并)排序一趟扫描的结果，(27)是以第一个元素为分界元素的快速排序一趟扫描的结果，(28)是堆排序初始建堆的结果。
选项 A、F，H，C，D，P，A，M，Q，R，S，Y，X
B、P，A，C，S，Q，D，F，X，R，H，M，Y
C、A，D，C，R，F，Q，M，S，Y，P，H，X
D、H，C，P，A，M，S，R，D，F，X，Y
E、H，Q，C，Y，A，P，M，S，D，R，F，X
答案C
解析 本题比较容易，直接考查各种排序的方法，但从历年试题看来，再考的概率是比较高的。
   1．冒泡排序
   冒泡排序将被排序的记录数组R[1．．n]垂直排列，每个记录R看做是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
   冒泡排序的具体过程如下。
   第一步，先比较k1和k2，若k1＞k2，则交换k1和k2所在的记录，否则不交换。继续对k2和k3重复上述过程，直到处理完kn-1，和kn。这时最大的排序码记录转到了最后位置，称第1次起泡，共执行n-1次比较。
   与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行n-2次比较，称第2次起泡。
   依次类推，共做n-1次起泡，完成整个排序过程。
   在本题中，待排序的序列为{Q，H，C，Y，P，A，M，S，R，D，F，X}，按照上述规则，第一趟冒泡结果为{H，C，Q，P，A，M，S，R，D，F，X，Y}。
   2．希尔排序
   希尔(Shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2＜d1重复上述的分组和排序，直至所取的增量dt＝1(dt＜dt-1＜…＜d2＜d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
   一般取d1＝n/2，di+1＝di/2。如果结果为偶数，则加1，保证di为奇数。
   在本题中，待排序的序列为{Q，H，C，Y，P，A，M，S，R，D，F，X}，规定初始步长d1=4，则(Q，P，R)排在一组。这需要对Q，P，R进行排序，排序得：P，Q， R，所以P应是序列的首字母。在4个选项中，只有B满足要求。
   3．归并排序
   归并排序是将m(m＞1)个有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看做由n个长度都为1的有序子表所组成，将它们依次m归并得到长度为2的若干有序子表，再对它们m合并。直到得到长度为n的有序表，排序结束。
   在本题中，待排序的序列为{Q，H，C，Y，P，A，M，S，R，D，F，X}，规定m=2 (两路归并)。把题目中的数据进行分组有：[Q，H]，[C，Y]，[P，A]，[M，S]，[R，D]， [F，X]，调整后得：[H，Q]，[C，Y]，[A，P]，[M，S]，[D，R]，[F，X]。所以正确答案为E。
   4．快速排序
   快速排序采用了一种分治的策略，通常称其为分治法。其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
   快速排序的具体过程如下。
   第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。
   第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。
   从上面的介绍中我们知道，对一个序列进行快速排序后有一个非常明显的特征，即“关键字前面的所有元素小于关键字，关键字后面的所有元素大于关键字”。我们往往能以此规则来快速又准确地得到正确答案。在此题中，以序列首字母Q为关键字，我们先看A，此选项满足上述特征。
   请读者想想：分析到此处，我们能否断定A是正确答案呢?不能。我们只能说找到不合规则的选项将其排除，最终得到正确答案。一个序列满足上述条件不一定就是快速排序的结果。所以我们继续看B和C在这两个选项中，H比Q小，但在Q后面，不正确。D和E两个选项中A在Q的后面，显然不正确，所以答案应选A。
   5．堆排序
   有关堆的定义和性质，请读者参考第2题的分析。
   堆排序的关键步骤有两个：一是如何建立初始堆：二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新成为堆。
   在本题中，只要求建立初始堆，我们可以按照4.1.2节的方法，判断给定的5个选项中，哪个选项满足堆的定义就可以了，在此不再重复。
转载请注明原文地址:https://www.kaotiyun.com/show/i3TZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

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