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

admin2021-08-17 49

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

选项 A、O(n)
B、O(n²)
C、O(logD、O(nlogn)

答案D

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

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

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

计算机408

学硕统考专业

相关试题推荐

设系统缓冲区和用户工作区均果用单缓冲，从外设读人1个数据块到系统缓冲区的时间为100，从系统缓冲区读入1个数据块到用户工作区的时间为5，对用户工作区中的1个数据块进行分析的时间为90(如下图所示)。进程从外设读人并分析2个数据块的最短时间是
对给定的关键字序列110，119，007，911，114，120，122进行基数排序，则第2趟分配收集后得到的关键字序列是
假定某计算机字长16位，没有Cache，运算器一次定点加法时间等于100ns，配置的磁盘旋转速度为每分钟3000转，每个磁道上记录两个数据块，每一块有8000B，两个数据块之间间隙的越过时间为2ms，主存周期为500ns，存储器总线宽度为16位，总线带宽为
有一结点的关键字序列F={129，72，180，105，147，96，45，69}，散列函数为H(k)=kmod11，其中k为关键字，散列地址空间为0～10。要求：画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和查找不成功
下面的地址中，属于单播地址的是()。
在顺序表的动态存储定义中需要包含的数据成员是()。Ⅰ．数组指针*dataⅡ．表中元素个数nⅢ．表的大小maxSizeⅣ．数组基址base
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
输入一整数数组{5，7，6，9，11，10，8}，该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意两

随机试题

加碱化剂的目的是消除氢离子的干扰。
未经有关部门批准，医师擅自开办诊所，卫生行政部门可采取的措施不包括
A．AAI起搏器B．VVI起搏器C．VAT起搏器D．DDD起搏器E．VOO起搏器测得窦房结恢复时间为2400ms，房室结文氏点为160次／分，可选用
A．当量剂量B．有效剂量C．比释动能D．吸收剂量E．吸收剂量率当身体各部分受到不同程度照射时，对人体造成的总的随机性辐射损伤是
关于总会计师，下列说法正确的有()。
按照()，金融机构可分为金融调控机构和金融运行机构。
外国旅游者在来华途中行李确系丢失，应由()向有关航空公司索赔。
从警察起源上看，()。
下列语句中，正确的是()。
Careforchildrenandolderpeoplehasrecentlyhittheheadlines.Governmentannouncementsonfundingreformshaveputcarefir

最新回复(0)

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

计算机408

学硕统考专业

对给定的关键字序列110，119，007，911，114，120，122进行基数排序，则第2趟分配收集后得到的关键字序列是

下面的地址中，属于单播地址的是()。

在顺序表的动态存储定义中需要包含的数据成员是()。Ⅰ．数组指针*dataⅡ．表中元素个数nⅢ．表的大小maxSizeⅣ．数组基址base

假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一

加碱化剂的目的是消除氢离子的干扰。

未经有关部门批准，医师擅自开办诊所，卫生行政部门可采取的措施不包括

A．AAI起搏器B．VVI起搏器C．VAT起搏器D．DDD起搏器E．VOO起搏器测得窦房结恢复时间为2400ms，房室结文氏点为160次／分，可选用

A．当量剂量B．有效剂量C．比释动能D．吸收剂量E．吸收剂量率当身体各部分受到不同程度照射时，对人体造成的总的随机性辐射损伤是

关于总会计师，下列说法正确的有()。

按照()，金融机构可分为金融调控机构和金融运行机构。

外国旅游者在来华途中行李确系丢失，应由()向有关航空公司索赔。

从警察起源上看，()。

下列语句中，正确的是()。

Careforchildrenandolderpeoplehasrecentlyhittheheadlines.Governmentannouncementsonfundingreformshaveputcarefir