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

admin2009-02-15 37

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

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

答案C

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

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

阅读以下说明。回答以下问题，将解答填入答题纸对应的解答栏内。【说明】某公司计划部署园区网络，其建筑物分布如下图所示。根据需求分析结果，网络规划要求如下：1．网络中心机房在信息大楼。2．设计中心由于业

阅读以下说明，回答问题。【说明】某企业网络拓扑图如图1一1所示。工程师给出了该网络的需求：1．用防火墙实现内外网地址转换和访问控制策略；2．核心交换机承担数据转发，并且与汇聚层两台交换机实现OSPF功能；

IETF定义的多协议标记交换(MPLS)是一种第三层交换技术，MPLS网络由标记交换路由器和标记边缘路由器组成，负责为网络流添加/删除标记的是(29)。

在ISDN的配置中，ITU定义了R、S、T和U4个参考点，其中S参考点用于连接(25)。

以下关于分组交换技术的叙述中，说法错误的是(23)。

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

WAPuses(66)whichincludestheHandheldDeviceMarkupLanguage(HDML)developedbyPhone.com.WMLcanalsotraceitsrootstoeXte

用迭代法求解方程x5-x-1=0，下列迭代公式不可能正确的是(6)。

资本主义简单再生产实现的条件下，第一部类生产的全部产品的总价值应等于()

女，42岁。左下后牙进食嵌塞痛15天。偶有喝冷水疼痛。无自发痛。检查发现左下第一磨面深龋洞，冷测反应正常。冷刺激人洞出现一过性敏感。叩痛(一)。去净腐质后洞底无穿髓孔，该患牙应做的治疗是

患有多发性神经炎的糖尿病病人进行足部护理不当的是

期货公司申请设立分支机构，应当未因涉嫌违法违规经营正在被有权机关调查，近()内未因违法违规经营受到行政处罚或者刑事处罚。

下面符合《商业银行个人理财业务风险管理指引》规定的有()。

下列关于违反银行业监督管理有关法律规定的法律责任的说法中，正确的有()。

行政处罚包括吊销营业执照、冻结资金、拘留、没收财物。()

()对于手机相当于交流对于()