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

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

admin2021-01-13  42
问题 递增序列A(a1，a2，…，abn)和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给出的结果可知，aiii+1，在排序的过程中，将a1与b1进行比较，a1小，然后将a2与b1进行比较，a2大，则已排好的部分为a1b1，共比较了2次；然后将a2与b2进行比较，a2小，再将a3与b2进行比较，a3大，则已排好的部分为a1b1a2b2，共比较了4次；以此类推，完全排好时共比较了2(n一1)+1=2n一1次。由选项A给出的结果可知，递增序列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…，an分别与bi/2+1进行比较，共比较了n一i／2—2次，完全排好时共比较了i+1+n—i／2—2=n+j／2—1次。
转载请注明原文地址:https://kaotiyun.com/show/fCCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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