首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn)。 (2)关键字自大到小逆序(key1>key2
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn)。 (2)关键字自大到小逆序(key1>key2
admin
2014-12-08
30
问题
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?
(1)关键字自小到大有序(key1<key2<…<keyn)。
(2)关键字自大到小逆序(key1>key2>…>keyn)。
(3)奇数关键字顺序有序,偶数关键字顺序有序(key1<key3…,key2<key4<…)。
(4)前半部分元素按关键字顺序有序,后半部分元素按关键字顺序逆序(key1<key2<…<keym,keym+1>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)在这种情况下,比较次数最少的情况是所有纪录关键字均按升序排列,这时,总的比较次数为n-1。 (4)在这种情况下,后半部分元素的关键字均大于前半部分元素的关键字时需要比较次数最少,此时前半部分的比较次数=m-1,后半部分的比较次数=(n-m-1)*(n-m+2)/2,因此,总的比较次数为m-1+(n-m-1)×(n-m+2)/2=(n-2)(n+8)/8(假设n偶数,m=n/2)。
解析
转载请注明原文地址:https://jikaoti.com/ti/psajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
宗法制是西周又一项重要的政治制度,与分封制密切相关,宗法制的核心内容是()
确定毛泽东思想为党的指导思想的大会是()。
第三次科技革命初期,苏联领先于美国的新兴科学技术成就是()。
1945年8月,毛泽东指出“抗日战争的阶段过去了,新的情况和任务是国内斗争”。此斗争主要集中在()。
在1900年巴黎代表大会上,第二国际围绕米勒兰入阁事件展开激烈争论,并通过“橡皮决议案”暂时防止了国际的分裂。这个“决议案”的起草人是()。
建国初期的土地改革与解放战争时期的土改最主要的区别是()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
随机试题
治疗糖尿病酮症酸中毒时
真性动脉瘤与假性动脉瘤的区别是
放射工作人员在特殊情况下。有效剂量在一生中不得超过
A.二巯基丙醇B.解磷定C.亚甲蓝D.亚硝酸钠E.乙酰胺可用于解救氟乙酰胺中毒的药物是
施工总承包单位与建设单位于2008年2月20日签订了某二十层综合办公楼工程施工合同。合同中约定:①人工费综合单价为45元/工日;②一周内非承包方原因停水、停电造成的停工累计达8小时可顺延工期一天;③施工总承包单位须配有应急备用电源。工程于3月15日开工,施
一般认为,态度与品德形成过程的阶段依次为依从、认同、_________。
光彩夺目的金刚石的化学成分与下列哪个一样()。
某公司发出通知,要求下属的连锁便利店增加同类但不同品牌的商品。公司管理层认为,这样做能让任何消费者进来买某类商品时,总能挑到他想买的,从而使公司获得更多的利润。以下哪个选项如果为真,则最能削弱该公司的推论?()
DNS服务器的默认端口号是()端口。
TheMysteryoftheMayasTheruinsofonce-beautifulcitiesintheforestsofCentralAmericatellscientistsmuchaboutthe
最新回复
(
0
)