2. 计算机
  3. (2012年上半年上午试题61)递增序列A(a1，a2，…，an)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为________时，归并过程中元素的比较次数最多。

(2012年上半年上午试题61)递增序列A(a1，a2，…，an)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为________时，归并过程中元素的比较次数最多。

admin2019-07-12  31
问题 (2012年上半年上午试题61)递增序列A(a1，a2，…，an)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为________时，归并过程中元素的比较次数最多。
选项 A、a1，a2，…，an，b1，b2，…，bn
B、b1，b2，…，bn，a1，a2，…，an
C、a1，b1，a2，b2，…，ai，bi，…，an，bn
D、a1，a2，…，ai／2，b1，b2，…，bi／2，ai／2+1，ai／2+2，…an，bi／2+1，bi／2+2，…，bn
答案C
解析 归并排序是将两个排好序的序列合并成一个有序的序列。由选项A给出的结果可知，递增序列B的每一个元素都比A中的元素要大，也就是说ai(1≤i≤n)比b1小，在排序的过程中，只需要将ai与b1进行比较，共比较了n次。由选项B给出的结果可知，递增序列B的每一个元素都比A中的元素要小，在排序的过程中，只需要将bi(1≤i≤n)与a1进行比较，共比较了n次。由选项C给出的结果可知，ai＜bi＜ai+1，在排序的过程中，将a1与b1进行比较，a1小，然后将a2与b1进行比较，a2大，则已排好的部分为a1b1，共比较了2次；然后将a2与b2进行比较，a2小，再将a3与b2进行比较，a3大，则已排好的部分为a1b1a2b2，共比较了4次；以此类推，完全排好时共比较了2(n-1)+1=2n-1次。由选项D给出的结果可知，递增序列B的前i／2个元素都比A中的前i／2个元素要大，但比A中的后i／2个元素要小，B的后i／2个元素都比A中的后i／2个元素要大，因此在排序的时候，A中的前i／2个元素只需与b1进行比较，当比较到ai／2+1时，ai／2+1比b1大，则已排好的部分为a1，a2，…，ai／2，共比较了i／2+1次；然后将b2，b3，…，bi／2与ai／2+1进行比较，都比ai／2+1小，当比较到bi／2+1时，bi／2+1比ai／2+1大，则已排好的部分为a1，a2，…，ai／2，b1，b2，…，bi／2，共比较了i+1次；然后将ai／2+2，ai／2+3，…，an分别与bi／2+1进行比较，共比较了n-i／2-2次，完全排好时共比较了i+1+n-i／2-2=n+i／2-1次。
转载请注明原文地址:https://kaotiyun.com/show/VmCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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