首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
admin
2021-08-17
51
问题
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
选项
A、O(n)
B、O(n
2
)
C、O(log
D、O(nlogn)
答案
D
解析
在排序过程中,每次比较会有两种情况出现,若整个排序过程中至少需要t次比较,则显然会有2
t
种情况,由于n个记录总共有n!种不同的排列,因而必须有n!种不同的比较路径,于是有:2
t
≥n!,即t≥log
2
(n!)。因为log
2
(n!)≈nlog
2
n,所以t≥nlog2n。
转载请注明原文地址:https://kaotiyun.com/show/HD3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机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
)