当前位置:首页计算机类软件水平考试中级软件设计师->两个递增序列A和B的长度分别为m和n(m<n且m与n接近),

两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度为m+n的递增序列。当关系为(  )时,归并过程中元素的比较次数最少。

  • A.a1<a2<…<am-1<am<b1<b2<…<bn-1<bn
  • B.b1<b2<…<bn-1<bn<a1<a2<…<am-1<am
  • C.a1<b1<a2<b2<…<am-1<bm-1<am<bm<bm+1<…<bn-1<bn
  • D.b1<b2<…<bm-1<bm<a1<a2<…<am-1<am<bm+1<…<bn-1<bn
查看答案 纠错
答案: A
本题解析:

对于本题,求解归并比较次数最少。可分为3种情况:

1)A[m]数值全小于B[n],取A[1]<B[1],R[1]=A[1],接下来比较A[2]与B[1],R[2]=A[2]…直到取完A[m],A[m]<B[1],R[m]=A[m],将B序列复制到R[K],(m+1)~(m+n)的位置,完成归并排序,此时,共比较m次;

2)A[m]数值全大于B[n],取B[1]<A[1],R[1]=B[1],接下来直到取完B[n],将A[m]序列复制到(n+1)~(n+m)的位置,完成归并排序,此时,共比较n次,题干指出m<n,因此第一种情况比较次数较少;

3)A[m]数值与B[n]数值大小交叉,则归并排序过程,对于R[1]~R[k]位置上数值的确定会比较>=1次,最终复制剩余序列时,长度也会小于m(因为交叉排序,有部分序列会经过比较插入结果数列),此时复制序列所缩减的比较次数会体现在前面交叉排序的过程中,总的比较次数会较大。

因此,比较次数最少的情况是第一种A[m]数值全小于B[n]。

更新时间:2021-11-19 00:03

你可能感兴趣的试题

单选题

(  )is the process of transforming information so it is unintelligible to anyone but the intended recipient.

  • A.Encryption
  • B.Decryption
  • C.Security
  • D.Protection
查看答案
单选题

As each application module is completed,it undergoes(  )to ensure that it operates correctly and reliably.

  • A.unit testing
  • B.integration testing
  • C.system testing
  • D.acceptance testing
查看答案
单选题

(  )algorithm specifies the way to arrange data in a particular order.

  • A.Search
  • B.Random
  • C.Sorting
  • D.Merge
查看答案
单选题

After analyzing the source code,(  )generates machine instructions that will carry out the meaning of the program at a later time.

  • A.an interpreter
  • B.a linker
  • C.a compiler
  • D.a converter
查看答案
单选题

(  )can help organizations to better understand the information contained within the data and will also help identify the data that is most important to the business and future business decisions.

  • A.Data processing system
  • B.Big Data analytics
  • C.Cloud computing
  • D.Database management
查看答案
单选题

浏览器开启无痕浏览模式后,(  )依然会被保存下来。

  • A.浏览历史
  • B.搜索历史
  • C.已下载文件
  • D.临时文件
查看答案
单选题

下列协议中,不属于TCP/IP协议簇的是(  )。

  • A.CSMA/CD
  • B.IP
  • C.TCP
  • D.UDP
查看答案
单选题

下列传输介质中,带宽最宽、抗干扰能力最强的是(  )。

  • A.双绞线
  • B.红外线
  • C.同轴电缆
  • D.光纤
查看答案
单选题

数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内,确定一个点需要2个独立的参数,确定一个正方形需要(  )个独立的参数。

  • A.3
  • B.4
  • C.5
  • D.6
查看答案
单选题

某书的页码为1,2,3,...,共用数字900个(一个多位数页码包含多个数字),据此可以推断,该书最大的页码为(  )。

  • A.237
  • B.336
  • C.711
  • D.900
查看答案