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

admin2019-08-01 52

问题已知下列各种初始状态(长度为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://kaotiyun.com/show/EtCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下列历史事件发生的先后顺序是()。①“铁幕”演说②马歇尔计划③北大西洋公约

试述明代一条鞭法的主要内容和历史意义。

第二次世界大战后，资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

基督教产生的时间是()。

“一战”期间，中国民族资本主义迅速发展的重要作用是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

文件系统的主要目的是()。

下列的网络协议中，()的运输层协议是使用TCP的。

对大脑半球一侧优势现象正确的叙述有()

构成心左缘的是【】

中毒性痢疾多见于

β值为零的证券的均衡收益率是()。

当建设工程竣工验收时，对隐蔽工程进行必要的开挖和修复等费用计入()中。

卢梭的自然教育理论及其影响。

某关系数据库系统中，设有“选修操作系统”的学生关系A，“选修电子商务”的学生关系B，那么，求“选修操作系统”而没有“选修电子商务”的学生，则需要对这两个关系进行______运算。