对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【】。

admin2010-05-13 60

问题对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【】。

选项

答案O(n)

解析初始状态没有部分排序的文件中若有n个记录，可以把它看作n个子文件，每个子文件中只包含一个记录，因而是部分排序的。通常先将两个子文件归并，得到n/2个部分排序的较大的于文件，每个子文件中只包含2个记录。再将这些子文件归并，如此反复，直到归并到一个文件中，排序完成。上述每步归并都是将两个子文件全成一个文件，这种做法叫“二路归并排序”。二路归并排序时，需利用一个同待排序数组一样大小的辅助数组，所以其空间复杂度为O(n)。

转载请注明原文地址:https://kaotiyun.com/show/VySZ777K

本试题收录于：三级数据库技术题库NCRE全国计算机三级分类

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【】。

三级数据库技术

NCRE全国计算机三级

下面关于三星公司基于ARM9内核的S3C2410嵌入式微处理器芯片的叙述中，错误的是()。

在μC／OS—II操作系统下，处于运行态的任务因更高优先级的任务就绪而被剥夺CPU使用权后将转入()。

在μC／OS—II操作系统中，某任务正在等待键盘输入消息，该任务应处于【67】态。若键盘中断服务程序向该任务发送了消息，则该任务转变为【68】态。

存储器容量单位有字节(B)、千字节(KB)、兆字节(MB)、吉字节_【55】和太字节_【56】等。

μC／OS—II系统内核提供的基本功能有：【69】、任务间通信与同步、任务调度、时间管理和【70】等。

计算机局域网传输数据时，必须把数据组织成规定格式的“帧”，每一数据帧由下图所示的5个部分组成，其中①、②、③分别是()。

下面对ADS1．2集成开发环境进行描述的语句中，正确的是()。

GNU开发工具套件中的C语言编译器，其英文简称是【79】。它所能编译的目标机处理器包括X86、ARM、PowerPC等体系结构的处理器。针对于ARM体系结构的目标机而言，该C语言编译器的命令书写格式中，其带前缀的命令是【80】。

逆变电路的SPWM控制方式可分为单极性控制方式和______控制方式。

下列病因的胸腔积液是渗出液的是

轮椅的基本结构包括

A、分子内氢键B、N为酰胺型C、氮原子杂化方式不同D、诱导效应E、空间效应麻黄碱碱性小于伪麻黄碱是由于

执业药师注册有效期麻醉药品处方备查年限

[2005年]设二维随机变量(X，Y)的概率分布为若随机事件{X=0}与{X+Y=1}相互独立，则()．

Please______fromsmokinguntiltheairplaneisairborne.[1997]

Jointhe"SleepChallenge"[A]Didyougetenoughsleeplastnight?Probablynot."Weareanationofsleep-deprivedwomen,"says

按期权所赋予的权利的不同可将期权分为()。

A、Hisanotherarticleisbetter.B、Onlypartofhisarticlewaspublished.C、Hisarticlewaspublishedtoolate.D、Hewouldrath

对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【 】。

三级数据库技术

NCRE全国计算机三级

下面关于三星公司基于ARM9内核的S3C2410嵌入式微处理器芯片的叙述中，错误的是()。

在μC／OS—II操作系统下，处于运行态的任务因更高优先级的任务就绪而被剥夺CPU使用权后将转入()。

在μC／OS—II操作系统中，某任务正在等待键盘输入消息，该任务应处于__________【67】态。若键盘中断服务程序向该任务发送了消息，则该任务转变为__________【68】态。

存储器容量单位有字节(B)、千字节(KB)、兆字节(MB)、吉字节_________【55】和太字节_________【56】等。

μC／OS—II系统内核提供的基本功能有：【69】、任务间通信与同步、任务调度、时间管理和【70】等。

计算机局域网传输数据时，必须把数据组织成规定格式的“帧”，每一数据帧由下图所示的5个部分组成，其中①、②、③分别是()。

下面对ADS1．2集成开发环境进行描述的语句中，正确的是()。

GNU开发工具套件中的C语言编译器，其英文简称是【79】。它所能编译的目标机处理器包括X86、ARM、PowerPC等体系结构的处理器。针对于ARM体系结构的目标机而言，该C语言编译器的命令书写格式中，其带前缀的命令是【80】。

逆变电路的SPWM控制方式可分为单极性控制方式和______控制方式。

下列病因的胸腔积液是渗出液的是

轮椅的基本结构包括

A、分子内氢键B、N为酰胺型C、氮原子杂化方式不同D、诱导效应E、空间效应麻黄碱碱性小于伪麻黄碱是由于

执业药师注册有效期麻醉药品处方备查年限

[2005年]设二维随机变量(X，Y)的概率分布为若随机事件{X=0}与{X+Y=1}相互独立，则()．

Please______fromsmokinguntiltheairplaneisairborne.[1997]

Jointhe"SleepChallenge"[A]Didyougetenoughsleeplastnight?Probablynot."Weareanationofsleep-deprivedwomen,"says

按期权所赋予的权利的不同可将期权分为()。

A、Hisanotherarticleisbetter.B、Onlypartofhisarticlewaspublished.C、Hisarticlewaspublishedtoolate.D、Hewouldrath

对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【】。

在μC／OS—II操作系统中，某任务正在等待键盘输入消息，该任务应处于【67】态。若键盘中断服务程序向该任务发送了消息，则该任务转变为【68】态。

存储器容量单位有字节(B)、千字节(KB)、兆字节(MB)、吉字节_【55】和太字节_【56】等。