设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 order (int j，int m) } int i，ternp； if(j＜m) { if(a[i]＜a[j]) { temp=a [i]； a [j]=temp； } j

admin2019-12-10 61

问题设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。
order (int j，int m)
  }
int i，ternp；
if(j＜m)
{
if(a＜a[j])
{
temp=a ；
a [j]=temp；
  }
j++；
order(j，m)； //递归调用
  }
}

选项 A、O(n)
B、O(nlog₂n)
C、O(n²)
D、O(n³)

答案C

解析 order()函数是一个递归排序过程，设T(n)是排序n个元素所需要的时间。在排序n个元素时，算法的计算时间主要花费在递归调用order()上。第一次调用时，处理的元素序列个数为n—1，也就是对余下的n—1个元素进行排序，所需要的计算时间应为T(n—1)。又因为在其中的循环中，需要n—1次比较，所以排序n个元素所需要的时间为
T(n)=T(n—1)+n—1， n＞1
这样得到如下方程：
T(1)=0
T(n)=T(n—1)+n一1 n＞1
求解过程为：
T(n)=[T（n一2）+（n一2）]+（n一1）
=[T（n一3）+（n一3）]+（n一2）+（n一1）
.
.
.
=[T(1)+1]+2+…+n—1
=0+1+2+…+n—1
=n(n—1)/2
=O(n²)

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 order (int j，int m) } int i，ternp； if(j＜m) { if(a[i]＜a[j]) { temp=a [i]； a [j]=temp； } j

计算机408

学硕统考专业

执行一次磁盘输入输出操作所花费的时间包括()。

在一个单处理器系统中，存在3个进程，最多有几个进程处于就绪队列()。

某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存

42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，

进程从运行状态转换为就绪状态的可能原因是()。

一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。

在单处理机的多进程系统中，进程什么时候占用处理机以及决定占用时间的长短是()。

已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多的是____。

在补码表示的机器中，若寄存器A中原存的数为9EH，现存的数为CFH，则表明执行的一条指令是()。

E-mail中的存取协议IMAP与POP3协议的差别包括()。

导致甲状腺肿大最常见的原因是()。

下列关于战术资产配置与战略资产配置说法错误的是()。

有明确的目的、不需要意志努力的注意是()

郑兵的孩子即将上高中，郑兵发现，在当地中学，学生与老师的比例低的学校，学生的高考成绩普遍都比较好，郑兵因此决定，让他的孩子选择学生总人数最少的学校就读。以下哪项最为恰当指出了郑兵上述决定的漏洞?

查询每门课程的最高分，要求得到的信息包括课程名称和分数。正确的命令是(　　)。向学生表插入一条记录的正确命令是(　　)。

Thegovernmentaldepartmentsconcernedareawarethattherearedownfalls______morecarsontheroads.

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 order (int j，int m) } int i，ternp； if(j＜m) { if(a[i]＜a[j]) { temp=a [i]； a [j]=temp； } j

计算机408

学硕统考专业

执行一次磁盘输入输出操作所花费的时间包括()。

在一个单处理器系统中，存在3个进程，最多有几个进程处于就绪队列()。

某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存

42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，

进程从运行状态转换为就绪状态的可能原因是()。

一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。

在单处理机的多进程系统中，进程什么时候占用处理机以及决定占用时间的长短是()。

已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多的是____。

在补码表示的机器中，若寄存器A中原存的数为9EH，现存的数为CFH，则表明执行的一条指令是()。

E-mail中的存取协议IMAP与POP3协议的差别包括()。

导致甲状腺肿大最常见的原因是()。

下列关于战术资产配置与战略资产配置说法错误的是()。

有明确的目的、不需要意志努力的注意是()

郑兵的孩子即将上高中，郑兵发现，在当地中学，学生与老师的比例低的学校，学生的高考成绩普遍都比较好，郑兵因此决定，让他的孩子选择学生总人数最少的学校就读。以下哪项最为恰当指出了郑兵上述决定的漏洞?

查询每门课程的最高分，要求得到的信息包括课程名称和分数。正确的命令是( )。向学生表插入一条记录的正确命令是( )。

Thegovernmentaldepartmentsconcernedareawarethattherearedownfalls______morecarsontheroads.

查询每门课程的最高分，要求得到的信息包括课程名称和分数。正确的命令是(　　)。向学生表插入一条记录的正确命令是(　　)。