已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。

admin2022-06-07 38

问题已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。

选项 A、O(klog₂k)
B、O(klog₂n)
C、O(nlog₂k)
D、O(nlog₂n)

答案B

解析因组与组之间已有序，故将n／k个组分别排序即可，基于比较的排序方法每组的时间下界为n／k×O(klog₂k)，因此全部时间下界应为O(nlog₂k)。

转载请注明原文地址:https://jikaoti.com/ti/AdDjFFFM

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

计算机408

学硕统考专业

相关试题推荐

某简单分页式存储管理中，逻辑地址空间分页为每页1KB，对应相应的物理块。设主存总容量为256KB，描述主存分配情况如表1—2所列(0表示未分配，1表示已分配)。此时，操作系统创建了一个新进程，大小为2．5KB，按首先分配低址空间的策略，那么，分配
某计算机有下图所示的功能部件，其中M为主存，MDR为主存数据寄存器，MAR为主存地址寄存器，R0～R3为通用寄存器，IR为指令寄存器，PC为程序计数器(具有自动加1功能)，C、D为暂存寄存器，ALu为算术逻辑单元，移位器可左移、右移、直通传送。(1
某调制解调器同时使用幅移键控和相移键控，采用0、π／2、π和3／2π四种相位，每种相位又都有2个不同的幅值，问在波特率为1200的情况下数据速率是()。
某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E
某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0．5MB／s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请
对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是
关于DMA方式和通道方式，下列说法中错误的是()。
在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是_______。Ⅰ．LRU算法Ⅱ．FIFO算法Ⅲ．OFT算法
下列调度算法中，不可能导致饥饿现象的是_______。

随机试题

公司解散原则上都应该进行清算，但并非所有公司解散都导致公司清算。下列选项中公司解散无需进行清算的是()
哈默和钱皮在《再造公司》一书中提出“三C”的力量，他们认为其中最为重要的力量是()
阅读下面的文章，回答问题天马贾平凹四月二十一日，谭宗林从安康带来魏晋画像砖拓片数幅，和一包新茶。因茶思友，分出一半去寻马海舟。马海舟是
阴阳二纲在针灸临床的应用中，以下不正确的一项是：寒热二纲在针灸临床应用中，以下不正确的一项是：
男性，3岁，精神较差，面色萎黄，厌食，拒食，进食稍多则大便夹有残渣，容易出汗，舌苔薄白，及脉无力，此患儿的治法是
健脾丸的功用是枳实导滞丸的功用是
设立物业管理企业，必须向()进行注册登记，领取营业执照。
召开股东会会议，应当于会议召开______日以前通知全体股东；召开股东大会，应当将会议审议的事项于会议召开______日以前通知各股东。(　　)
下列关于存货决策的表述中，正确的是()。
Atienzatookashort-termjobmainlybecause______Accordingtothepassage,intheyearof2005,theUnitedStateshadworkfo

最新回复(0)

已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。

计算机408

学硕统考专业

某调制解调器同时使用幅移键控和相移键控，采用0、π／2、π和3／2π四种相位，每种相位又都有2个不同的幅值，问在波特率为1200的情况下数据速率是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E

对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是

关于DMA方式和通道方式，下列说法中错误的是()。

在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是_______。Ⅰ．LRU算法Ⅱ．FIFO算法Ⅲ．OFT算法

下列调度算法中，不可能导致饥饿现象的是_______。

公司解散原则上都应该进行清算，但并非所有公司解散都导致公司清算。下列选项中公司解散无需进行清算的是()

哈默和钱皮在《再造公司》一书中提出“三C”的力量，他们认为其中最为重要的力量是()

阅读下面的文章，回答问题天马贾平凹四月二十一日，谭宗林从安康带来魏晋画像砖拓片数幅，和一包新茶。因茶思友，分出一半去寻马海舟。马海舟是

阴阳二纲在针灸临床的应用中，以下不正确的一项是：寒热二纲在针灸临床应用中，以下不正确的一项是：

男性，3岁，精神较差，面色萎黄，厌食，拒食，进食稍多则大便夹有残渣，容易出汗，舌苔薄白，及脉无力，此患儿的治法是

健脾丸的功用是枳实导滞丸的功用是

设立物业管理企业，必须向()进行注册登记，领取营业执照。

召开股东会会议，应当于会议召开______日以前通知全体股东；召开股东大会，应当将会议审议的事项于会议召开______日以前通知各股东。( )

下列关于存货决策的表述中，正确的是()。

Atienzatookashort-termjobmainlybecause______Accordingtothepassage,intheyearof2005,theUnitedStateshadworkfo

召开股东会会议，应当于会议召开日以前通知全体股东；召开股东大会，应当将会议审议的事项于会议召开日以前通知各股东。(　　)