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

admin2009-02-15 47

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

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

软考中级

阅读以下说明，回答以下问题，将解答填入答题纸对应的解答栏内。【说明】某公司搭建了一个小型局域网，网络中配置一台Linux服务器作为公司内部文件服务器和Internet接入服务器，该网络结构如下图所示。vsftpd程序主配置

阅读以下说明，回答问题。(2010年下半年下午试题二)[说明]在Linux操作系统中，TCP／IP网络可通过若干文本文件及命令进行配置。在Linux操作系统中，可通过命令(1)获得如图5-6所示的网络配置参数。(1)备选答案：A

阅读以下说明，回答问题。(2011年下半年下午试题二)[说明]如图5—3所示，某公司办公网络划分为研发部和销售部两个子网，利用一台双网卡Linux服务器作为网关，同时在该Linux服务器上配置Apache提供Web服务。图5—4是Linux

阅读以下说明，回答问题。[说明]某小区采用HFC接入Intemet的解决方案进行网络设计，网络结构如图3-19所示。有线电视HFC网络的上、下行信道是非对称的，容易产生噪声、影响传输质量的是上行信道还是下行信道?

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

SNMPv1是一个不安全的协议，管理站(Manager)与代理(Agent)之间通过(55)进行身份认证，由于认证信息没有加密，因此是不安全的。1998年公布的SNMPv3定义了基于用户的安全模型USM，其中的认证模型块结合(56)算法形成认证协议，产生了

容量为64块的Cache采用组相联方式映像，字块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应为(7)位，主存区号应为(8)位。

下列关于PGP(PrettyGoodPrivacy)的说法，错误的是(37)。

Routingprotocolsusedifferenttechniquesforassigning(1)toindividualnetwork．Further，eachroutingprotocolformsametricag

由哪些国际检索单位作出国际检索报告的PCT国际申请，在进入中国国家阶段并提出实质审查请求时，只需要缴纳80％的实质审查费?

下列关于收养关系解除的说法中，正确的是

患者男，50岁，发现口内有白色斑块半年，粗糙感，吸烟史十年，临床检查：右颊黏膜有白色斑块样改变，大小约1．0cm×1．5cm，稍高出黏膜表面，触之柔软。该患者诊断首先考虑

关于刑讯逼供罪的认定，下列哪些选项是错误的?()(2012年卷二第60题)

项目建设投产运营阶段回顾与评价内容有()。

钢筋施工包括()等内容。

JIT理论中的关键要素包括()。

调制解调器具有信号的调制与解调功能，其中调制的作用是把数字信号转换成一—。

Thefactthattheworld’scitiesaregettingmoreandmorecrowdedisawell-documenteddemographicfact.CitiessuchasTokyo

WillAIRobotsTurnHumansintoPets?A)InaroomattheUnitedNationsoverlookingNewYork’sEastRiver,atatableaslon