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

admin2021-08-17 55

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

学硕统考专业

相关试题推荐

若某文件系统索引结点(inode)中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是
用海明码对长度为8位的数据进行检／纠错时，若能纠正一位错，则校验位数至少为
对给定的关键字序列110，119，007，911，114，120，122进行基数排序，则第2趟分配收集后得到的关键字序列是
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是
下面的地址中，属于单播地址的是()。
在顺序表的动态存储定义中需要包含的数据成员是()。Ⅰ．数组指针*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行。在系统运行到某一
输入一整数数组{5，7，6，9，11，10，8}，该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意两
设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：在(5)的基础上，假设送出的主存地址为04011H，是否命中?

随机试题

布雷顿森林体制采取黄金一美元本位制，实行“双挂钩”制度，即________、_______。
哪一种不是可摘局部义齿固位力的组成
凡是(　　)的单位，均可称为监理单位。
混凝土小型空心砌块砌体灰缝砂浆饱满度，下列描述正确的是()。
某事业单位与期货公司签订期货经纪合同，委托期货公司进行期货交易。关于该事业单位期货交易的说法，正确的是()。
行长不得担任贷审会的成员，但可指定()副行长担任贷审会主任委员，但该主任委员不得同时分管前台业务部门。
个人外汇储蓄账户资金境内划转办理的规定不包括()。
我国经济体制改革的目标是建立()。
()对于导游相当于()对于教师
Nooneworddemonstratedtheshiftincorporations’attentioninthemid-1990sfromprocessestopeoplemorevividlythanthesi

最新回复(0)

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

计算机408

学硕统考专业

若某文件系统索引结点(inode)中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是

用海明码对长度为8位的数据进行检／纠错时，若能纠正一位错，则校验位数至少为

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

若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是

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

在顺序表的动态存储定义中需要包含的数据成员是()。Ⅰ．数组指针*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行。在系统运行到某一

设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：在(5)的基础上，假设送出的主存地址为04011H，是否命中?

布雷顿森林体制采取黄金一美元本位制，实行“双挂钩”制度，即________、_______。

哪一种不是可摘局部义齿固位力的组成

凡是( )的单位，均可称为监理单位。

混凝土小型空心砌块砌体灰缝砂浆饱满度，下列描述正确的是()。

某事业单位与期货公司签订期货经纪合同，委托期货公司进行期货交易。关于该事业单位期货交易的说法，正确的是()。

行长不得担任贷审会的成员，但可指定()副行长担任贷审会主任委员，但该主任委员不得同时分管前台业务部门。

个人外汇储蓄账户资金境内划转办理的规定不包括()。

我国经济体制改革的目标是建立()。

()对于导游相当于()对于教师

Nooneworddemonstratedtheshiftincorporations’attentioninthemid-1990sfromprocessestopeoplemorevividlythanthesi

布雷顿森林体制采取黄金一美元本位制，实行“双挂钩”制度，即__、_。

凡是(　　)的单位，均可称为监理单位。