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

admin2009-02-15 44

问题将两个长度为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)次。

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

软考中级

阅读以下说明，回答问题。(2009年上半年，试题二)[说明]某公司总部服务器1的操作系统为WindowsServer2003，需安装虚拟专用网(VPN)服务，通过Internet与子公司实现安全通信，其网络拓扑结构和相关参数如图6-35所示。

阅读以下说明，回答问题。(2010年下半年下午试题二)[说明]在Linux操作系统中，TCP／IP网络可通过若干文本文件及命令进行配置。在Linux系统中，DNS查询文件内容如下所示，该文件的默认存储位置为(5)，当用户做DNS查询时，首选D

阅读以下说明，回答问题。(2011年上半年下午试题五)[说明]某单位网络拓扑结构示意图如图3-12所示。该网络采用RIP协议，要求在R2上使用访问控制列表禁止网络192．168．20．0／24上的主机访问网络192．168．10．0／24，在R3上使用访

Windows网络操作系统通过域模型实现网络安全管理策略。下列除(34)以外都是基于域的网络模型。在一个域模型中不允许包含(35)。

路由器命令R1(config)#iprouting的作用是(61)。

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

中国共产党的宗旨是由

便携式网络图像格式文件的扩展名是______。

在Excel中，B3：F6表示引用了__________个单元格。

根管的数目与牙根的数目之间的关系如何

根据《医疗机构管理条例》的规定，下列说法中错误的是

章先生，32岁，因车祸致脾破裂，急诊入院。病人胸闷、气促、出冷汗、脉细速，BP68／50mmHg，其体位应为

国家无偿收回划拨土地使用权的原因有()。

方先生将一笔10万元的资金投资在一个年收益率为6％的工程项目中，试估算，大约经过()年，这笔资金的本利和可以达到20万元。

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。