首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl
admin
2013-09-16
50
问题
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl
key2)…>keyn)。(3)奇数关键字顺序有序,偶数关键字顺序有序(key1
keym+2>…>keyn,m为中间位置)。
选项
答案
依题意,取各种情况下的比较次数即为最少比较次数。 (1)在这种情况下,插入第i个(2≤i≤n)元素的比较次数为1,因此,总的比较次数为1+1+1+…+1=n一1。 (2)在这种情况下插入第i个(2≤i≤n)元素的比较次数为i,因此,总的比较次数为2+3+4+…+n=(n一1)(n+2)/2。 (3)在这种情况下,比较次数最少的情况是所有纪录关键字均按升序排列,这时,总的比较次数为11一1。(4)在这种情况下,后半部分元素的关键字均大于前半部分元素的关键字时需要比较次数最少,此时前半部分的比较次数m--1,
解析
转载请注明原文地址:https://kaotiyun.com/show/C0xi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第一国际成立于下面的哪个城市?()
论述新石器时代及其文化类型。
第二次世界大战的爆发是多种因素综合作用的结果,其最根本的原因是()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
洪秀全以宗教手段组织起义,主要利用的是()。
欧洲历史上第一部系统完备的法典是()。
巴黎公社采取的带有无产阶级专政性质的措施有()。①公社人员由民主选举产生②没收逃亡资本家的工厂,交给工人合作社管理③取消旧的国家机器,建立:亡人阶级自己的国家机构④工职人员年薪不得超过熟练工人的工资
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
洪武八年。朱元璋仿照元朝的办法,印造(),命令民间通行。形成了钱、钞并用的货币制度。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
随机试题
越婢加半夏汤或桑白皮汤,适用于胀哪一型涤痰汤适用于肺胀哪一型
患者,男性,40岁,主诉空腹时有上腹痛,进食后缓解2个月余。秋冬季季节性发作3年,经胃镜检查确诊为十二指肠溃疡。本病的重要致病菌是
根据某地一年级12名女大学生体重x与肺活量y数据进行相关回归分析,已算出∑()2=1.89,∑()2=1.06,则剩余标准差Sy·x等于
A.水钠潴留B.促红细胞生成素减少C.活性维生素D3,减少D.出血倾向E.含氮代谢产物潴留尿毒症患者发生贫血的主要原因是
房地产开发企业以“性价比”为导向,确定商品住房销售价格的定价方法是()。
下列各项中,属于企业流动负债的是()。
BOT项目融资的优点有()。
事业单位的其他应收款包括()。
审计防范措施可以分为三类:由______产生的防范措施;鉴证客户内部的防范措施;会计师事务所自身制度和程序中的防范措施。
请从所给的选项中,选择最适合的一个填入问号处,使之呈现一定的规律性:
最新回复
(
0
)