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

admin2021-08-17 33

问题对于一个长度为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

学硕统考专业

相关试题推荐

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为
有一结点的关键字序列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行。在系统运行到某一
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如表2-4所示。该模型机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器(R-R)二地址类型，16位字长指令为寄存器-存储器(R—M)二地址变址寻址类型(-128
现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)；i=1；while(所剩边数≥顶点数){从图中删去ei；若图不再连通，则恢复ei；i++；
假定磁盘传输数据以32bit的字为单位，传输速率为1MB／s。CPU的时钟频率为50MHz。采用DMA控制进行输入输出操作，假定DMA的启动操作需要1000个时钟周期，DMA完成时处理中断需要500个时钟周期，如果平均传输的数据长度为4KB，问在磁盘工

随机试题

紫杉醇注射剂中加入表面活性剂聚氧乙烯蓖麻油是为了
水性包衣处方成分重量(％W／W)作用羟丙甲纤维素(5mPaS)7．5()聚乙二醇4000．8()色淀(按固体物计
男，46岁，因心悸、胸痛、劳力性呼吸困难数日就诊。心电图示左室肥大，Ⅱ、Ⅲ、AVF、AVL导联有病理性Q波。心导管检查示左室流出道与室腔间压差＞20mmHg，Brockenbrough现象阳性。诊断是
以下项目中不是财产清查的基本程序的是()。
某建筑物建筑面积为100m2，经过年数5年，单位建筑面积的重置价格500元／m2，该建筑物经济寿命20年，残值率为5％。除()之外建筑物折旧可以分为三大类。
某交通运输企业2017年拥有整备质量10吨的载重汽车20辆，中型商用客车10辆，整备质量8吨的挂车3辆。该企业所在地载货汽车年税额20元／吨，中型客车年税额540元／辆。该企业当年应缴纳车船税()元。
甲公司持有在境外注册的乙公司100％股权，能够对乙公司的财务和经营政策实施控制。甲公司以人民币为记账本位币，乙公司以港币为记账本位币，发生外币交易时甲公司和乙公司均采用交易日的即期汇率进行折算。(1)20×9年10月20日，甲公司以每股2美元的价格购入
从下列各项活动的内容看，属于公安机关保护公共财产和个人合法财产的有()。
某国有公司司机甲下班后将本单位的小汽车作为出租车运营，收人归自己所有。甲以这种方式共计获利1万元。甲的行为()。
Somefuturologistshaveassumedthatthevastupsurgeofwomenintheworkforcemayportendarejectionofmarriage.Manywomen,

最新回复(0)

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

计算机408

学硕统考专业

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为

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

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

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

现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)；i=1；while(所剩边数≥顶点数){从图中删去ei；若图不再连通，则恢复ei；i++；

紫杉醇注射剂中加入表面活性剂聚氧乙烯蓖麻油是为了

水性包衣处方成分重量(％W／W)作用羟丙甲纤维素(5mPaS)7．5()聚乙二醇4000．8()色淀(按固体物计

男，46岁，因心悸、胸痛、劳力性呼吸困难数日就诊。心电图示左室肥大，Ⅱ、Ⅲ、AVF、AVL导联有病理性Q波。心导管检查示左室流出道与室腔间压差＞20mmHg，Brockenbrough现象阳性。诊断是

以下项目中不是财产清查的基本程序的是()。

某建筑物建筑面积为100m2，经过年数5年，单位建筑面积的重置价格500元／m2，该建筑物经济寿命20年，残值率为5％。除()之外建筑物折旧可以分为三大类。

某交通运输企业2017年拥有整备质量10吨的载重汽车20辆，中型商用客车10辆，整备质量8吨的挂车3辆。该企业所在地载货汽车年税额20元／吨，中型客车年税额540元／辆。该企业当年应缴纳车船税()元。

从下列各项活动的内容看，属于公安机关保护公共财产和个人合法财产的有()。

某国有公司司机甲下班后将本单位的小汽车作为出租车运营，收人归自己所有。甲以这种方式共计获利1万元。甲的行为()。

Somefuturologistshaveassumedthatthevastupsurgeofwomenintheworkforcemayportendarejectionofmarriage.Manywomen,