对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

admin2019-08-01 38

问题对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

选项

答案将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较……比较中的小者放前半部，大者放后半部，用了n／2次比较。再在前后两部分中分别简单选择最小和最大元素，各用(n／2)一1次比较。总共用了(3n／2)一2次比较。显然，当n≥3时，(2n一3)>(3n／2)一2。用分治法求解再给出另一参考答案。对于两个数x和y，经一次比较可得到最大值和最小值；对于三个数x，y，z，最多经3次比较可得最大值和最小值；对于凡个数(n>3)，将分成长为n一2和2的前后两部分A和B，分别找出最大者和最小者：Max A，Min A，Max B，Min B，最后Max={Max A，Max B}和Min={Min A，MinB}。对A使用同样的方法求出最大值和最小值，直到元素个数不超过3。设C(n)是所需的最多比较次数，根据上述原则，当n>3时有如下关系式： [*] 通过逐步递推，可以得到：C(n)=(3n／2)一2。显然，当n>3时，2n一3>(3n／2)一2。事实上(3n／2)一2是解决这一问题的比较次数的下限。

解析

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

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

计算机408

学硕统考专业

魏晋南北朝时期，社会经济特点与前一历史阶段的明显不同之处是()。

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

世界天文史上最早实地测量子午线的记录是由谁进行的?()

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。

设有两个子网202．118．133．0／24和202．118．130．0／24，如果进行路由汇聚，得到的网络地址是()。

某计算机存储器按字节编址，主存地址空间大小为64MB，现用4MBx8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是____。

尽职调查的原则有

利用服务场所进行宣传属于服务营销中的以下哪种策略?

肺心病呼吸衰竭患者行气管切开辅助呼吸后，检查PaO210kPa；血pH7.42；PaCO23.74kPaBE-5.2mmol/L；HCO3-18.3mmo/L，你考虑是

A、中枢抑制作用B、止咳平喘作用C、扩张血管，促进发汗D、肾上腺皮质激素样作用E、收敛作用甘草具有

知母皂苷及皂苷元的生物活性有

在双代号网络计划中，关键线路上的工作必然是(　　)。

财政部制定的《会计核算软件基本功能规范》是对会计软件的()要求。

统计的认识过程一般经历统计设计阶段对调查对象的初步认识；统计调查和整理阶段的资料搜集与再加工；统计分析阶段的对事物本质和规律性认识，并对发展趋势进行预测。这一过程可概括为()。

在我国旅游业的初创阶段，旅游业的发展面临着不少制约因素，最突出的是国内铁路运输，它成为旅游业发展的“瓶颈”。()

北京龙脉温泉度假村、九华山庄，都位于昌平区小汤山镇。()

对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

计算机408

学硕统考专业

魏晋南北朝时期，社会经济特点与前一历史阶段的明显不同之处是()。

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

世界天文史上最早实地测量子午线的记录是由谁进行的?()

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。

设有两个子网202．118．133．0／24和202．118．130．0／24，如果进行路由汇聚，得到的网络地址是()。

某计算机存储器按字节编址，主存地址空间大小为64MB，现用4MBx8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是____。

尽职调查的原则有

利用服务场所进行宣传属于服务营销中的以下哪种策略?

肺心病呼吸衰竭患者行气管切开辅助呼吸后，检查PaO210kPa；血pH7.42；PaCO23.74kPaBE-5.2mmol/L；HCO3-18.3mmo/L，你考虑是

A、中枢抑制作用B、止咳平喘作用C、扩张血管，促进发汗D、肾上腺皮质激素样作用E、收敛作用甘草具有

知母皂苷及皂苷元的生物活性有

在双代号网络计划中，关键线路上的工作必然是( )。

财政部制定的《会计核算软件基本功能规范》是对会计软件的()要求。

统计的认识过程一般经历统计设计阶段对调查对象的初步认识；统计调查和整理阶段的资料搜集与再加工；统计分析阶段的对事物本质和规律性认识，并对发展趋势进行预测。这一过程可概括为()。

在我国旅游业的初创阶段，旅游业的发展面临着不少制约因素，最突出的是国内铁路运输，它成为旅游业发展的“瓶颈”。()

北京龙脉温泉度假村、九华山庄，都位于昌平区小汤山镇。()

在双代号网络计划中，关键线路上的工作必然是(　　)。