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

admin2021-08-17 51

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

学硕统考专业

相关试题推荐

用户程序发出磁盘I／O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
有一结点的关键字序列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
输入一整数数组{5，7，6，9，11，10，8}，该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意两
假设系统为某进程分配了3个物理块，考虑页面走向为：7，0，1，2，0，3，0，4。试问采用CLOCK页面淘汰算法时缺页中断的次数为()。
现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：若文件A作为共享文件，系统应采用何种目录结构?画出示意图。

随机试题

CT扫描发现左心后区类圆形“肿块”影，内含少量气体，与横膈关系密切。下述疾病中可能性最大的是
A．酸败B．破裂C．分层D．转相E．絮凝乳滴聚集成团但保持乳滴的完整分散体而不呈现合并现象
某投保人缴净保费P=1800元，附加费比例k=10%，则该投保人缴纳的营业保费为(　　)元。
某企业取得3年期银行存款1000万元，年利率8％，半年付息一次，到期一次还本，筹资费用率为l％，企业所得税率为25％。该企业的银行借款资本成本为()。
德国古典哲学是马克思主义哲学的直接理论来源。()
阅读《一个小官吏之死》这篇小说的片断，完成下列题。一个极好的傍晚，一个同样极好的名叫伊万.德米特里奇.切尔维亚科夫的庶务官坐在剧院大厅第二排的围椅上，架上望远镜观看《哥纳维勒的钟》。他凝神注目，飘然欲仙。突然……在小说里经常遇到“突然”这两个字。
王珏、柳枚、江倩三人分别是三个孩子的母亲，她们带着自己的孩子一同去郊游。王珏对自己的孩子说：“真有趣，你们这三个孩子，也是一个姓王，一个姓柳，一个姓江，但是你们都不和自己的母亲同姓。”另一个姓江的孩子说：“一点都没错。”根据上述条件，请判断以下哪项为真?
在美化演示文稿版面时，下列叙述不正确的是______。
在窗体上画一个名称为Command1的命令按钮和一个名称为Text1的文本框，并编写如下事件过程：PrivateSubCommand1_Click()DimiAsInteger,aAsInteger,jAsInteger
Forthispart,youareallowed30minutestowriteashortessayonthetopicBroadenOurKnowledge.Youshouldwriteatleast1

最新回复(0)

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

计算机408

学硕统考专业

用户程序发出磁盘I／O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是

有一结点的关键字序列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行。在系统运行到某一

假设系统为某进程分配了3个物理块，考虑页面走向为：7，0，1，2，0，3，0，4。试问采用CLOCK页面淘汰算法时缺页中断的次数为()。

CT扫描发现左心后区类圆形“肿块”影，内含少量气体，与横膈关系密切。下述疾病中可能性最大的是

A．酸败B．破裂C．分层D．转相E．絮凝乳滴聚集成团但保持乳滴的完整分散体而不呈现合并现象

某投保人缴净保费P=1800元，附加费比例k=10%，则该投保人缴纳的营业保费为( )元。

某企业取得3年期银行存款1000万元，年利率8％，半年付息一次，到期一次还本，筹资费用率为l％，企业所得税率为25％。该企业的银行借款资本成本为()。

德国古典哲学是马克思主义哲学的直接理论来源。()

在美化演示文稿版面时，下列叙述不正确的是______。

在窗体上画一个名称为Command1的命令按钮和一个名称为Text1的文本框，并编写如下事件过程：PrivateSubCommand1_Click()DimiAsInteger,aAsInteger,jAsInteger

Forthispart,youareallowed30minutestowriteashortessayonthetopicBroadenOurKnowledge.Youshouldwriteatleast1

某投保人缴净保费P=1800元，附加费比例k=10%，则该投保人缴纳的营业保费为(　　)元。