将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较(59)次。

admin2009-02-15 49

问题将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较(59)次。

选项 A、1
B、n-1
C、→n
D、2n

答案C

解析考生首先要明白两个前提：一是要归并的两个表都是递增有序的，且长度都为n，二是题目问的是最少的关键字比较次数，即最好的情况下的比较次数。而最好的情况应该是：一个表的所有关键字都大于(或小于)另一个表的所有关键字，如：(1　2　3　4)与(5　6　7　8)。比较的时候有两个指针分别指向两个表的第一个元素，由于一个表的关键字要都大于另一个表的关键字，所以关键字小的表中的元素挨个与关键字大的表的第一个元素比较后，先被并入到新表中，这时关键字大的表的指针还是指向第一个元素没变，此时只需将关键字大的表复制到新表中即可。所以花费的比较次数就是关键字小的表长，也就是n。

转载请注明原文地址:https://kaotiyun.com/show/n1xZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较(59)次。

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

软考中级

阅读以下说明。回答回答以下问题，将解答填入答题纸对应的解答栏内。【说明】某企业在部门A和部门B分别搭建了局域网，两局域网通过两台WindowsServer2003服务器连通，如下图所示，要求采用IPSec安全机制，使得部门A的主机P

阅读以下说明，回答问题。(2010年下半年下午试题四)[说明]某企业在公司总部和分部之间采用两台WindowsServer2003服务器部署企业IPSecVPN，将总部和分部的两个子网通过Intemet互联，如图6-29所示。隧道技术

SNMPv1使用(41)进行报文认证，这个协议是不安全的。SNMPv3定义了(42)的安全模型，可以使用共享密钥进行报文认证。

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(16)，采用　CSMA/CA技术是指(17)，MAC层的分布式协调功能提供(18)，站点发出的确认帧ACK，要在(19)间隔发送。为解决隐蔽站带来的问题，802.11允许(20)。

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

I/O端口的编址方法有二种：即I/O端口单独编址方式和UO端口与存储器单元统一编址方式。在某个计算机系统中，内存与I/O是统一编址的，要靠(11)区分和访问内存单元和I/O设备。

ARPAnetisawideareanetwork(WAN)．AnetworkthatconnectedDepartmentofDefenseresearchsitesacross(1)．Createdin1969wit

暑淫证的性质特点

医疗机构的医务人员违反献血法规定，将不符合国家规定标准的血液用于患者的，可能承担以下法律责任，除了

下列不属于继发性肺结核临床病理特征的是

施工成本分析就是对成本形成过程和影响成本升降的因素进行分析，以寻求进一步降低成本的途径，进行成本分析需要的第一手资料有（）。

旅游需求的时间指向性是指旅游需求具有()。

石川馨认为，全面质量管理(TQC)在日本就是全公司范围内的质量管理，其具体内容包括()。

下列属于内部学习动机的是()。

下列选项中，体现人民警察秉公执法的有()

将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较(59)次。

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

软考中级

阅读以下说明。回答回答以下问题，将解答填入答题纸对应的解答栏内。【说明】某企业在部门A和部门B分别搭建了局域网，两局域网通过两台WindowsServer2003服务器连通，如下图所示，要求采用IPSec安全机制，使得部门A的主机P

阅读以下说明，回答问题。(2010年下半年下午试题四)[说明]某企业在公司总部和分部之间采用两台WindowsServer2003服务器部署企业IPSecVPN，将总部和分部的两个子网通过Intemet互联，如图6-29所示。隧道技术

SNMPv1使用(41)进行报文认证，这个协议是不安全的。SNMPv3定义了(42)的安全模型，可以使用共享密钥进行报文认证。

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(16)，采用 CSMA/CA技术是指(17)，MAC层的分布式协调功能提供(18)，站点发出的确认帧ACK，要在(19)间隔发送。为解决隐蔽站带来的问题，802.11允许(20)。

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

I/O端口的编址方法有二种：即I/O端口单独编址方式和UO端口与存储器单元统一编址方式。在某个计算机系统中，内存与I/O是统一编址的，要靠(11)区分和访问内存单元和I/O设备。

ARPAnetisawideareanetwork(WAN)．AnetworkthatconnectedDepartmentofDefenseresearchsitesacross(1)．Createdin1969wit

暑淫证的性质特点

医疗机构的医务人员违反献血法规定，将不符合国家规定标准的血液用于患者的，可能承担以下法律责任，除了

下列不属于继发性肺结核临床病理特征的是

施工成本分析就是对成本形成过程和影响成本升降的因素进行分析，以寻求进一步降低成本的途径，进行成本分析需要的第一手资料有（）。

旅游需求的时间指向性是指旅游需求具有()。

石川馨认为，全面质量管理(TQC)在日本就是全公司范围内的质量管理，其具体内容包括()。

下列属于内部学习动机的是()。

下列选项中，体现人民警察秉公执法的有()

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(16)，采用　CSMA/CA技术是指(17)，MAC层的分布式协调功能提供(18)，站点发出的确认帧ACK，要在(19)间隔发送。为解决隐蔽站带来的问题，802.11允许(20)。