首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<(key2<……
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<(key2<……
admin
2013-07-12
29
问题
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
(1)关键字自小到大有序(key
1
<(key
2
<……
n);
(2)关键字自大到小逆序(key
>key
2
>……>key
n
);
(3)奇数关键字顺序有序。偶数关键字顺序有序(key
1
<key
3
……,key
2
<key
4
<……)。
(4)前半部分元素按关键字顺序有序,后半部分元素按关键字顺序逆序(key
1
<key
2
<……<key
m
,key
m+1
>key
m+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-11)*(n-m+2)/2=(n-2)(n+8)/8(假设n偶数,m=n/2)。
解析
本题主要考查直接插入法的算法思想及性能分析。
转载请注明原文地址:https://kaotiyun.com/show/mrxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
属于唐朝后期“南衙北司之争”的事件是()
在1856年用从煤焦油中提炼出来的化合物合成了染料“苯胺紫”,其色度范围超过了任何天然染料的化学家是()。
东汉时期,一再削弱地方的军权,强化中央控制下的军队,在下列中央控制的军队中,主要负责保卫京师的是()
在新民主主义革命中,进步势力和革命的主要力量是()。
试述中国共产党诞生的历史条件和意义。
评价凡尔赛—华盛顿体系。
何谓凡尔赛—华盛顿体系?如何评价?
猿人制造的工具主要是稍加敲击的石器和木棒,考古学上把使用这种工具的时代称为()。
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时,最后一个IP分片的数据长度是()。
随机试题
行政复议作为行政机关纠正错误的一种监督制度,其性质上的特点是()
我国第一部以马克思主义观点阐述教育问题的著作是【】
符合甲状腺功能亢进症代谢率增高的表现是
胎方位的指示点,正确的是
甲与乙签订了一份马的试用买卖合同,试用期间为两个月。乙牵回马后,立即与丙签订了买卖合同。双方约定,马的所有权自合同签订之日起转移给丙,但在丙10日内凑齐马款,交付乙后,才将马交付给丙。至第7日,乙因向丁借款又将该马出质于丁,且将该马交付于丁。至第8日,丙与
落球仪测试土质路基模量时,每个测点最多只能测试3次。()
依《电信条例》规定,颁发《基础电信业务经营许可证》应当按照国家有关规定采用()方式。
下列哪些属于警衔制度的内容?()
J.Martin对信息系统开发的基本出发点之一,是希望计算机化的信息系统应注意和强调【】,特别是可见效益,直接经济效益,否则难以持久。
A、9-17.B、18-26.C、27-35.D、36-45.B从选项可以初步猜测题目与数字范围有关。听完录音,可知对话的主题是一项休闲运动的调查,可进一步猜测本题与调查中的年龄组别有关。根据录音,最积极参与体育运动的是18至26岁的人。故答案是B
最新回复
(
0
)