首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl
admin
2013-09-16
41
问题
已知下列各种初始状态(长度为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://jikaoti.com/ti/GoajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
玄奘、义净西游和鉴真东渡,体现出唐文化的什么特征?()
独立战争前,北美殖民地的类型主要包括()。①王室殖民地②业主殖民地③自治殖民地④“居留地"
简要分析在蒸汽时代资本主义的决定性的胜利。
()巩固了王权,正式确定了世袭制度,开始了我国历史上的“家天下”局面。
我国第一部系统的史学理论著作是()。
系统阐明社会主义初级阶段理论是在()。
清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏
下列历史事件发生的先后顺序是()①“铁幕”演说②马歇尔计划③北大西洋公约
材料一:1913年,印度在政府注册的工厂有2744家,1922年时増加到4744家,民族资本获得了丰厚的利润,一战时期因而被印度企业家们称为创业的“黄金时代”。在两次世界大战期间,印度的制糖业和水泥业得到较快的发展,水泥和糖不再依靠进口。第二次世界大战时
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
随机试题
假定某系统有A,B,C三类资源可供五个进程P1,P2,P3,P4,P5共享。系统对这三类资源的拥有量为:A类7个,B类2个,C类6个。进程对资源的需求和已占用情况如下表所示。回答下列问题:如果现在进程P2提出需要资源A类2个,B类1个,C类2个,系
血小板释放的物质不包括
连续12小时测胎动数,提示为慢性胎儿窘迫的是( )。
信用证支付方式应由开证行承担独立付款责任,其付款义务不同于汇票付款人的义务。如果信用证规定使用汇票,依UCP600的规定,有关该汇票的下述说法中正确的是哪些?()
期货公司首席风险官向公司住所地中国证监会派出机构提交上一年度全面工作报告,其内容包括( )。
()是债券产品的主要供给方。
下列收入中,不属于民间非营利组织收入的是()。
如果旅游团在一地缩短行程超过多长时间,应及时将变更情况通知组团社和下一站接待社,并办理好提前退费、退车、退餐等工作事宜()
PuertoRicanCuisine(菜肴)PuertoRico,aCaribbean(加勒比海区)islandrichinhistoryandremarkablenaturalbeauty,hasacuisine
TheOzoneLayer,foundinthestratospherebetween10kmand【M10】kmabovetheground,protectsearthfromtheharmfuleffectsof
最新回复
(
0
)