两个递增序列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
正确答案及解析
正确答案
解析
对于本题，求解归并比较次数最少。可分为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]。
包含此试题的试卷
你可能感兴趣的试题
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答5处
-
- A.sensor
- B.searching
- C.service
- D.source
- 查看答案
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答4处
-
- A.low-level
- B.low-cost
- C.high-cost
- D.high-performance
- 查看答案
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答3处
-
- A.19th
- B.20th
- C.21th
- D.22th
- 查看答案
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答2处
-
- A.path
- B.Internet
- C.route
- D.switch
- 查看答案
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答1处
-
- A.this
- B.thing
- C.think
- D.things
- 查看答案