已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? 前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key1＜key2＜…＜keym，keym+1＞key

admin2019-08-01 84

问题已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key₁＜key₂＜…＜key_m，key_m+1＞key_m+2＞…＞key_n，m为中间位置)。

选项

答案在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的关键字较次数最少，此时前半部分的比较次数为m一1，后半部分的比较次数为(n一m一1)(n—m+2)／2，因此，总的比较次数为m一1+(n一m一1)(n一m，m+2)／2=(n-1)(n+8)／8(假设n为偶数，m=n／2)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/EtCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。

永元四年(公元92年)，汉和帝用宦官()掌握的一部分禁军，消灭了窦氏势力。郑众从此参与预政事，并受封为侯，这是宦官用权和封侯的开始。

国共十年对峙时期，中国的经济特点包括()。①帝国主义加紧了对中国的经济侵略②民族资本主义经济有了显著发展③官僚资本迅速形成④新民主主义经济有了一定的发展

西汉的主要赋税形式中，征收对象是儿童的是()。

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

若某浮点机基数为4，尾数采用补码表示，则该浮点机的规格化尾数形式为()。

设有两个子网202．118．133．0／24和202．118．130．0／24，如果进行路由汇聚，得到的网络地址是()。

肝尾叶的静脉引流入下列哪条静脉

A．突发性耳聋B．老年性耳聋C．听神经瘤D．梅尼埃病E．药物中毒性聋根据下列病历简介，最可能的诊断是患者男性，45岁，左耳聋1年逐渐加重，检查双鼓膜完整，电测听左耳神经聋，ABR示蜗后聋

母亲带1岁男孩来院体查，经检查该小儿体格发育正常。其体重可达

作为寻找腭大孔的标志的牙是

某建设项目采用以纵向工作部门指令为主的矩阵组织结构(见图1)，其优点是可以()。

应由监理工程师(建设单位项目技术负责人)组织进行验收的是()质量验收。

关于基金产品风险评价应当依据的因素，表述错误的是()。

数学老师讲课很生动，激发了小红认真学好数学的兴趣，这属于()。

娱乐：评书

某甲参加特务组织后，受敌派遣，多次在其父处窃得军事情报交给特务组织。其后，某甲又策动其父武装叛乱。某甲的行为构成()。