对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

admin2019-07-18 56

问题对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

选项 A、O(n)
B、O(n²)
C、O(log n)
D、O(nlog n)

答案D

解析在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少需要t次比较，则显然会有2’种情况，由于n个记录总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是有：2^t≥n!，即t≥log₂(n!)。因为log₂(n!)≈nlog₂n，所以t≥nlog₂n。

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

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

计算机408

学硕统考专业

相关试题推荐

在巴黎和会上，列强讨论的中心问题是（）。
全国高校院系调整的时间是()。
20世纪的两次世界大战给人类造成巨大灾难，使这两次世界性大战得以发生的因素是()①少数大国争夺世界霸权②以欧洲为中心的国家格局开始发生变化③军国主义政策的推行④英法等大国在战前对法西斯的侵略采取了纵容姑息政策
某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和汽车类，上渡船有如下规定：同类车先到先上船，客车先于货车上船，且每上4辆客车，才允许上一辆货车，若等待客不足4辆，则以货车代替，若无货车等待允许客车都上船。写一算法模拟渡口管理。
通常通信信道的带宽越大，在数据传输中失真将会()。
在机器数中，正数的符号位用“1”表示的是()。
以下说法中错误的是()。
已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。
假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。
某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是____。

随机试题

下列散文中属于历史笔记的是()。
引起等渗性缺水的原因有()
下列行为中，既缴纳增值税又缴纳消费税的有()。
甲公司为境内上市公司。2017年，甲公司发生的有关交易或事项如下：(1)甲公司生产并销售环保设备。该设备的生产成本为每台300万元(未发生减值)，正常市场销售价格为每台500万元。甲公司按照国家确定的价格以每台400万元对外销售；同时，按照国家有关政策；
下列属于社区工作方法在贫困救助中的关注点的是(　　)。
()是运用教学设计的基本原理，遵循中学语文教学的一般规律，依据教学对象的特点和教师自己的教学观念、经验、风格，分析教学中的问题和需要，确定教学目标，建立解决问题的步骤，合理组织各种教学要素，为优化教学效果而制订实施方案的系统的计划过程。
2018年二季度，J省各项社会服务事业总费用累计支出933638.1万元，同比增长12.71%；一季度累计支出409206.2万元，同比增长5.87%。下列四类社会服务事业中，2018年二季度支出小于一季度的是：
天池经历了漫长的无名时期，后来伴随着天池传说的兴起，天池也开始________。谈到天池传说，还有一个缘由：人们面对神奇的山水之境时，总爱把神灵的光环罩在山水的头上，使山水之景与神灵之气________，即所谓山不在高，有仙则名。填入画横线部分最恰当的一项
依次填入下列各句横线处的词语，最恰当的一组是(　　)。①在欧元区十二国中，作为龙头老大的德国经济持续低迷的话，很可能______其他国家。②新任市长每天都接到大量的群众来信，即便工作再忙，他也要______作出答复。
某会计网校的刘老师正在准备有关《小企业会计准则》的培训课件，她的助手已搜集并整理了一份该准则的相关资料存放在Word文档“《小企业会计准则》培训素材．docx”中。按下列要求帮助刘老师完成PPT课件的整合制作。将第15张幻灯片自“(二)定性标准”开始拆

最新回复(0)

对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

计算机408

学硕统考专业

在巴黎和会上，列强讨论的中心问题是（）。

全国高校院系调整的时间是()。

通常通信信道的带宽越大，在数据传输中失真将会()。

在机器数中，正数的符号位用“1”表示的是()。

以下说法中错误的是()。

已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是____。

下列散文中属于历史笔记的是()。

引起等渗性缺水的原因有()

下列行为中，既缴纳增值税又缴纳消费税的有()。

下列属于社区工作方法在贫困救助中的关注点的是( )。

2018年二季度，J省各项社会服务事业总费用累计支出933638.1万元，同比增长12.71%；一季度累计支出409206.2万元，同比增长5.87%。下列四类社会服务事业中，2018年二季度支出小于一季度的是：

依次填入下列各句横线处的词语，最恰当的一组是( )。①在欧元区十二国中，作为龙头老大的德国经济持续低迷的话，很可能______其他国家。②新任市长每天都接到大量的群众来信，即便工作再忙，他也要______作出答复。

下列属于社区工作方法在贫困救助中的关注点的是(　　)。

依次填入下列各句横线处的词语，最恰当的一组是(　　)。①在欧元区十二国中，作为龙头老大的德国经济持续低迷的话，很可能其他国家。②新任市长每天都接到大量的群众来信，即便工作再忙，他也要作出答复。