首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl
admin
2013-09-16
45
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
东汉时期,一再削弱地方的军权,强化中央控制下的军队,在下列中央控制的军队中,主要负责保卫京师的是()
以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍
李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。
二里头文化以及相关考古遗址的发现和研究,是近年来史学界关注的一个热点。二里头文化的年代断限是()。
我国第一部系统的史学理论著作是()。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
1951年底到1952年春,中国共产党在党政机构工作人员中开展运动的内容是()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
随机试题
下列选项中,不属于中央军事委员会的职能部门的是()。
简述公共政策变动的原因。
调节氧化磷酸化作用的激素是
下列关于我国公民政治权利与自由的说法,正确的是:()
在相同的荷载作用下,相同厚度的单面排水土层渗透固结速度最慢的是:
工程项目施工进度控制总目标应进行分解,可按( )分解为交工分目标。
在我国婚姻成立的形式要件是( )。
十一届三中全会以来,我国实施的一系列改革措施,取得了举世瞩目的巨大成就,但也出现了某些负面效应。请用辩证唯物主义的矛盾学说,阐述你对这个问题的认识。
根据《行政处罚法》的规定,下列关于行政拘留的说法正确的是?
HistoryofPublicTransportationIn1915,theMorrellvillelinewasextendedintoOakhurstandanunderpasswasbuiltonFai
最新回复
(
0
)