早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表,最少需要进行关键字比较(24)次。A.1B.
题目
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表,最少需要进行关键字比较(24)次。
A.1
B.n-1
C.n
D.2n
参考答案
正确答案:C
解析:考生首先要明白两个前提:一是要归并的两个表都是递增有序的,且长度都为n,二是题目问的是最少的关键字比较次数,即最好的情况下的比较次数;而最好的情况应该是:一个表的所有关键字都大于(或小于)另一个表的所有关键字,如:(1234)与(5678)。比较的时候有两个指针分别指向两个表的第一个元素,由于一个表的关键字要都大于另一个表的关键字,所以关键字小的表中的元素挨个与关键字大的表的第一个元素比较后,先被并人到新表中,这时关键字大的表的指针还是指向第一个元素没变,此时只需将关键字大的表复制到新表中即可。所以花费的比较次数就是关键字小的表长,也就是n。
解析:考生首先要明白两个前提:一是要归并的两个表都是递增有序的,且长度都为n,二是题目问的是最少的关键字比较次数,即最好的情况下的比较次数;而最好的情况应该是:一个表的所有关键字都大于(或小于)另一个表的所有关键字,如:(1234)与(5678)。比较的时候有两个指针分别指向两个表的第一个元素,由于一个表的关键字要都大于另一个表的关键字,所以关键字小的表中的元素挨个与关键字大的表的第一个元素比较后,先被并人到新表中,这时关键字大的表的指针还是指向第一个元素没变,此时只需将关键字大的表复制到新表中即可。所以花费的比较次数就是关键字小的表长,也就是n。
看了将两个长度为n的递增有序表归并...的网友还看了以下:
用二次函数解该问题对某条路线的长度进行N次测量,得到N个结果x1,x2,..省略号...,xn.如 数学 2020-04-12 …
对某条路线的长度进行n次测量,得到n个结果x1,x2,x3,…,xn.如果用x作为这条路线长度的近 数学 2020-05-17 …
对某条路线的长度进行n次测量,得到n个结果x1,x2,x3,…,xn.如果用x作为这条路线长度的近 数学 2020-06-12 …
对某条公路的长度进行n次测量,得到n个结果X1,X2,X3...Xn,如果用X作为着条路线长度的近 数学 2020-07-16 …
一段长为L的通电直导线,单位长度中有n个自由电荷,自由电荷定向移动的速度是υ,在导线周围加一垂直于 物理 2020-07-18 …
对某条路线的长度进行n次测量,得到n个结果x1,x2,x3,…,xn.如果用x作为这条路线长度的近 其他 2020-07-20 …
算式的渐进复杂度的计算问题(很简单)1、fA(n)=n*log2n(以2为底的n的对数)fB(n) 数学 2020-08-01 …
Newton-Cotes公式中,为什么当n为偶数时,其代数精度为n+1,而n为奇数时,其代数精度只有 数学 2020-12-20 …
对某条路线的长度进行n次测量,得到n个结果.x1,x2.xn,如果用n做这条路线的长度的近似值,当x 其他 2020-12-27 …
小明在进行多边形内角合计算时,求得的内角和为1540度,发现多了一个内角,内角多少度?从百度上找的答 数学 2021-02-21 …