首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。 请回答下列问题: 根据你的合并过程,描述N(N≥
设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。 请回答下列问题: 根据你的合并过程,描述N(N≥
admin
2015-12-30
30
问题
设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。
请回答下列问题:
根据你的合并过程,描述N(N≥2)个不等长升序表的合并策略,并说明理由。
选项
答案
各表的合并策略是:在对多个有序表进行两两合并时,若表长不同,则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想,依次选择最短的两个表进行合并,可以获得最坏情况下最佳的合并效率。
解析
考查二路归并和哈夫曼树以及最佳归并树。
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的Merge()函数;对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。
转载请注明原文地址:https://kaotiyun.com/show/LzRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国第一条自行设计修建的铁路是在()
下列对春秋时期各国称霸的顺序描述错误的选项是()
1951年底到1952年春,中国共产党在党政机构工作人员中开展的运动是()。
三国时期,魏、蜀、吴灭亡的先后顺序是()。
对苏联高度集中的体制的客观评价是()。①基本上适应苏联当时的生产力发展水平②这种体制有严重缺点和弊端③后来这种体制阻碍了苏联国民经济的发展④这种体制在历史上起过积极的作崩
拉美独立后,各国政治上的一种普遍现象是(),实质上它是拉美各国大地主专政的一种特殊形式。
高等院校院系调整
若某浮点机基数为4,尾数采用补码表示,则该浮点机的规格化尾数形式为()。
(将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为H(key)=(keyx3)MOD7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。请画出所构造的散列表。
随机试题
能够成为反担保的担保方式有()。
带下色白或淡黄,质粘稠,无臭气,精神疲倦,纳少便溏,舌淡,苔白腻,脉缓弱。治疗的首选方剂是:带下量多,质稀清冷,腰酸如折,小便频数,大便溏薄,舌淡,苔薄白,脉沉迟。治疗的首选方剂是:
隆鼻术成功的标准是
A、液-液萃取法B、沉淀法C、硅胶色谱法D、聚酰胺色谱法E、离子交换色谱法根据物质在两相互不相容的溶剂中的分配系数不同进行分离的方法是
费用的增加会减少企业的负债。()
下列各项,必须由特定机关实施的活动包括()。
负强化就是运用惩罚排除不良行为的过程。
在圆x2+y2-6x-8y+21=0所围区域(含边界)中,P(x,y)和Q(x,y)是使得分别取得最大值和最小值的点,线段PQ的长为()。
opinionpoll
A、 B、 C、 C
最新回复
(
0
)