下面这个程序段的时间复杂度是( )。 for (i=1; i＜n; i++) { y=y+1; for (j=0; j＜=(2*n); j++) x++; }A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)

题目

下面这个程序段的时间复杂度是( )。 for (i=1; i＜n; i++) { y=y+1; for (j=0; j＜=(2*n); j++) x++; }

A．O(log2n)

B．O(n)

C．O(nlog2n)

D．O(n2)

相似考题

1.有以下程序main(){ int i,j,x=0;for(i=0;i<2;i++){ x++;for(j=0;j<=3;j++){ if(j ％ 2) continue;x++;}x++;}printf("x= ％ d\n",x);}程序执行后的输出结果是A)x=4B)x=8C)x=6D)x=12

2.以下程序运行后的输出结果是【13】。include<stdio．h>main(){ int n[2]，i，j；for(i=0；i<2；i++)n[i]=0；for(i=0；i<2；i++)for(j=0；j<2；j++)n[j]=n[i]+1；printf("％d＼n"，n[1])；}

3.下面这个程序段的时间复杂度是( )。 for (i=1; i＜n; i++) { y=y+3; for (j=0;j＜=(2*n);j++) x++; }A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)

4.下面程序段的时间复杂度是()。for(i=0;in;i＋＋)for(j=1;jm;j＋＋)A[i][j]=0;A、O(n)B、O(m+n+1)C、O(m+n)D、O(m*n)

参考答案和解析

正确答案：D
解析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。在本例算法中，其中语句“y=y+1;”的频度是n-1，语句“x++;”的频度是(n-1)(2n+1)=2n2-n-1。则该程序段的时间复杂度是T(n)=n-1+n2-n-1=O(n2)。

更多“下面这个程序段的时间复杂度是()。for(i=1;i<n;i＋＋){y=y＋1;for(j=0;j<=(2*n);j＋＋) x＋＋;}A.O(log2n ”相关问题

第1题：

执行下面程序段,语句3的执行次数为______。for(i=0;ii;j＋＋)state;A.n(n＋2)／2B

执行下面程序段，语句3的执行次数为______。 for(i=0;i＜n-1;i++) for(j=n;j＞i;j++) state;
A．n(n+2)/2
B．(n-1)(n+2)/2
C．n(n+1)/2
D．(n-1)(n+2)

正确答案：B
解析：本题考查如何衡量算法的复杂度，根据题目可以看出，两层循环每次执行的次数是不相等的，第一次循环执行了n次，第二次循环只执行了n-1次，直到最后一次循环，他执行了2次，这样就是一个等差数列的求和，可得到总的执行次数为(n-1)(n+2)/2。
第2题：

阅读下列函数说明和C代码，填入(n)处。
[说明]
以下C语言程序实现了生成从里到外是连续的自然数排列的回旋矩阵，矩阵形式如下：
7 6 5 16
8 1 4 15
9 2 3 14
10 11 12 13
程序的变量说明如下：
x1：矩阵上边界；
x2：矩阵下边界；
y1：矩阵左边界；
y2：矩阵右边界；
s：数组元素升降标记，s等于1为升，s等于-1为降；
a[]：存放矩阵元素的数组。
仔细阅读C语言程序源码，将(n)处的语句补充完整。(注：每处仅一个语句)
[C程序]
include＜stdio.h＞
void main ( )
{
const int N=20;
int i=0,j=0,a[N][N],n;
int m,x1,x2,y1,y2,s;
while (1)
{
Printf ("\ninput matrix row N( N＞=2): ");
scanf ("%d",&n);
printf ("\n");
if (n＞=2)
break;
}
m=n*n;
x1=0; y1=0; x2=n; y2=n;
if(n%2==0)
{j=n-1; y2=n-1; s=1;}
else
{i=n-1; y1=1; s=-1; }
while (1)
{
if (s==1)
{
for (i; i＜x2; i++) a[i][j]=m--;
i--;
j--;
(1)
for (j;j＞=y1;j--) a[i][j]=m--;
j++;
i--;
y1++;
(2)
}
else
{
for (i;i＞=x1;i--)
a[i][j]=m--;
i++;
j++;
(3)
for (j;j＜y2;j++)
(4)
(5)
i++;
(6)
S=i;
}
if (m＜1) break;
}
for (i=O;i＜n; i++)
{
for (j=O;j＜n;j++)
printf ("%6d",a[i][j]);
printf ("\n");
}
printf ("\n");
}

正确答案：(1)x2--; (2)s=-1; (3)x1++; (4)a[i][j]=m--; (5)j--; (6)y2--;
(1)x2--; (2)s=-1; (3)x1++; (4)a[i][j]=m--; (5)j--; (6)y2--; 解析：自然数排列的回旋矩阵是一个经典程序设计题目。本题中生成的是一个从里到外是连续的自然数排列的回旋矩阵。仔细阅读代码，能够发现(1)处应该为矩阵下边界递减；(2)处应该为数组元素递减状态，即为降；(3)处应该为矩阵上边界递增；(4)处应该为存放矩阵元素的数组中的数据递减；(5)处应该为数组元素的列序号递减，即j--；(6)矩阵右边界递减。
第3题：

下面程序段的时间复杂度为 ( ) for(i=0;i＜m;i++) for(j=0;j＜n;j++) A[i][j]=i*j;
A．O(m2)
B．O(n2)
C．O(m*n)
D．O(m+n)

正确答案：C
解析：此程序的时间复杂度即为程序中循环次数的时间耗费。由程序为嵌套循环，外层循环的时间复杂度T(n₁)=m，内层循环的时间复杂度T(n₂)=n，则此程序的时间复杂度T(n)=m*n，即为0(m*n)。
第4题：

有以下程序 main() { int n[3]，i，j； for(i＝0；i＜3；i++)n[i]＝0; for(i=0;i＜2,i++) for(j=0;j＜2;j++)n[j]=n[i]+1; printf("%d\n"，n[1])； } 程序运行后的输出结果是( )
A．2
B．1
C．0
D．3

正确答案：D
第5题：

有以下程序
include<stdio．h>
main( )
{int n[2l，ij；
for(i=0；i<2；i++)n[i]=0;
for(i=0；i<2；i++)
for(j=0；j<2；j++)n[j]=n[i]+1;
printf(”％d＼n”，n[1])；
}
程序运行后的输出结果是________ 。

正确答案：3
3 解析：初始化后：
N[0]=0，n[1]=0
i=0，j=0，n[0]=n[0]+1=1
j=1，n[1]=n[0]+1=1=2
i=1，j=0，n[0]=n[1]+1=3
j=1，n[1]=n[1]+1=3
第6题：

有如下程序段，设n为3的倍数。则语句③的执行频度为______。 Lnt i,j ; ① for(i=i;i＜n; i++){ ② if(3*i＜=n){ ③ for(j=3*i;j＜n;j++){
④ x++;y=3*x+2; } } }
A．n(n+1)/6
B．n(n-1)/6
C．n2/6
D．(n+1)(n-1)/6

正确答案：B
解析：取n=3，此时，语句③仅执行1次，注意，执行了一次，而不是一次也没执行。据此，只有选项B符合。
再取n=6，此时，语句③执行次数为：4+1=5，选项B正好符合。故可判断答案为B。
第7题：

有以下程序:main(){int i, j, x=0; for(i=0; i＜2; i++) { x++; for( j=0; j＜=3; j++) { if(j%2) continue; x++; } x++; } printf("x=%d\n", x);}程序执行后输出结果是( )。
A．x=4
B．x=8
C．x=6
D．x=12

正确答案：B
解析：外循环的循环变量i从0递增到1会循环2次，内循环的循环变量j从0递增到3会循环4次。但是内循环中有一条if语句，每当j%2为真，即j为奇数时会跳过下面的x++；语句，所以4次内循环只有2次执行到x++；语句，再加上外循环中包含的2条x++语句，所以每次外循环会使x自增4次，2次外循环下来x的值为8。故应该选择B。
第8题：

有以下程序： main { int i，j，x=0； for(i=0；i<2；i++) { x++； for(j=0；j<=3；j++) {if(j=0；j<=3；j++) x++； } x++； } printf("x=％d＼n"，x)； } 程序执行后的输出结果是( )。
A. x=4
B.x=8
C.x=6
D.x=12

正确答案：B
当i=0时，i<2成立，执行第一个for循环x自加为1，接着执行第二个for循环；j=0时j<=3成立，此时if不成立，执行x++后，x为2；接着j=1时，i<=3成立，继续循环，此时if成立，continue是跳出本次循环，继续下一次循环，不再执行x++了；接着j=2时，j<=3成立，此时if不成立，执行其后的语句；当j=4时，退出第二个循环，接着执行循环外部的x++，x为4；当i=1时，i<2成立，执行第一个循环，x=5，此时接着执行循环外部的语句，即第二个循环；j=0时j<3成立，此时if不成立，x++后，x为6，接着j为1时，j<=3成立，继续循环，此时if成立，不再执行x++了；接着J=2时，j<=3成立，此时if不成立，执行其后的x++，x为7；i=3时，j<=3成立，此时if成立，不再执行其后的语句了；当j=4时，退出第二个循环，执行循环外部的语句，最终x为8，故选B选项。
第9题：

下面这个程序段的时间复杂度是( )。 for (i=1； i＜n； i++) { y=y+1； for (j=0；3＜-(2*n)；j++) x++； }
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)

正确答案：D
解析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。在本例算法中，其中语句“y=y+1；”的频度是n-1，语句“x++；”的频度是(n-1)(2n+1)=2n2-n-1。则该程序段的时间复杂度是T(n)=n-1+n2-n-1=O(n2)。
第10题：

试题13
以下程序运行后的输出结果是______.
#include <stdio.h>
main()
{ int n[2], i, j;
for(i=0; i<2;i++) n[i]=0;
for(i=0; i<2; i++)
for(j=0; j<2; j++) n[j]=n[i]+1;
printf(“%d\n”, n[1]);
}

正确答案：
试题13分析
for(i=0; i<2;i++) n[i]=0;使得每个项的值赋为0。
i=0，j=0，n[0]=n[0]+1=1；i=0，j=1，n[1]=n[0]+1=2；
i=1，j=0，n[0]=n[1]+1=3；i=1，j=1，n[1]=n[1]+1=3；
试题13答案
3
第11题：

下面程序段的时间复杂度是（） for（i=0；i＜n；i++） for（j=0；j＜n；j++） A[i][j]=0；

正确答案:O（n²）
第12题：

单选题
设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for（i=1；i<=n；i++） for（j=i；j<=n；j++） x++；
A
O（1）
B
O（2n²）
C
O（n）
D
O（3n³）

正确答案： D
解析：暂无解析
第13题：

以下程序的输出结果是______。main(){ int i，j，x=0； for (i=0；i＜2；i++) { x++； for(j=0；j＜3；j++) { if(j%2) continue； x++； } x++； } printf("x=%d\n"，x)；}
A．x=4
B．x=8
C．x=6
D．x=12

正确答案：B
第14题：

以下程序的执行结果是______。 main() { int i，j，m=O，n=0； for (i=0；i＜2；i++) {for (j=0；j＜2；j++) if(j＞=i) m=1；n++； printf("%d\n"，n)； } }
A．4
B．2
C．1
D．0

正确答案：C
第15题：

下面这个程序段的时间复杂度是( )。 for (i=1； i＜n； i++) { y=y+1； for (j=0；j＜=(2*n)；j++) X++； }
A．O(log2n)
B．O(n)
C．0(nlog2n)
D．O(n2)

正确答案：D
解析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。在本例算法中，其中语句“y=y+1；”的频度是n-1，语句“x++；”的频度是(n-1)(2n+1)=2n2-n-1，则该程序段的时间复杂度是T(n)=n-1+2n2-n-1=O(n2)。
第16题：

有以下程序main(){ int n［3］，i,j; for(i=0;i<3;i++) n[i]=0; for(i=0;i<2;i++) for(j=0;j<2;j++) n[j]=n[i]+1; printf( "%d＼n",n[1]);}程序运行后的输出结果是A．2 B．1C．0 D．3

正确答案：D
初始时定义一个大小为3个一维整型数组，第一个for语句是对数组赋初值，每个值都为0。后面是一个for语句的嵌套调用，外层的循环变量i的取值为[0，2]，内层循环变量的取值范围为[0，2]。最初外层的循环变量i=0，内层的循环变量j取值从0到2，计算n[j]=n[0]+1，得到n[0]=1，n[1]=1，n[2]=1。外层for语句的循环变量为1时，内层的循环变量j取值从0到2，计算n[j]=n[1]+1，得到n[0]=2，n[1]=2，n[2]=2。外层for语句的循环变量为2时，内层的循环变量j取值从0到2，计算n[j]=n[2]+1，得到n[0]=3，n[1]=3，n[2]=3。最后的输出结果为3。
第17题：

分析下列程序，其最终执行结果是______。 main() { int n[3],i,j,k； for(i=0;i＜3;i++)n[i]=O； k=2； for(i=0;i＜k;i++) for(j=0;j＜k;j++) n[j]=n[i]-1； printf("%d\n",n[0])； }
A．-2
B．-1
C．0
D．-3

正确答案：D
解析：当i为0，内循环在j为0时，执行n[j]=n[i]-1；，即n[0]=n[0]-1， n[0]值变为-1：在j为1时，执行n[j]=n[i]-1；，即n[1]=n[0]-1，将-2赋给n[1]。当i为1时，内循环在j为0时，执行n[j]=n[i]-1；，即n[0]=n[1]-1，n[0]值变为-3；在j为1时，执行n[j]=n[i]-1；，即n[1]=n[1]-1，将-3赋给n[1]；最后n[0]和n[1]的值均为-3。
第18题：

下面程序段的时间复杂度是(9)。for(i=0，k=0；＜n；1++){ k+=A[i][j]； for(j=1；j＜m；j++) A[i][j]=1}
A．O(n)
B．O(m+n+1)
C．O(m+n)
D．O(m*n)

正确答案：D
解析：时间复杂度是解决问题的时间和问题的规模之间的关系，即解决问题所耗费的时间随问题规模增长成怎样的增长对应关系。本题中最内部的循环的执行次数为m*n，所以整段程序的复杂度为O(m*n)。
第19题：

下列程序的时间复杂度为( )。 for (i=l；i＜2n；i++) { y++； for(j=0；j＜a3n；j++) x++； }
A．0(n-1)
B．O(2n)
C．0(n2)
D．O(log2n)

正确答案：C
解析：一个算法中所有语句重复执行的次数之和构成了该算法的运算时间。题中语句y++执行了2n-1次，语句x++执行了(2n-1)(3n+1)=6n2-n-1次，则该算法的时间复杂度T(n)=6n2-n-1=O(n2)，
第20题：

下面这个程序段的时间复杂度是( )。 for {i=1； i＜n； i++) { y=y+1； for (j=0；i＜=(2*n)；i++) x++； }
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)

正确答案：D
解析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。在本题算法中，其中语句“y=y+1;”的频度是n-1，语句“x++;”的频度是(n-1)(2n+1)=2n2-n-1。则该程序段的时间复杂度是T(n)=n-1+2n2-n-1=O(n2)。
第21题：

下面的程序段的时间复杂度为【】
s=0；
for(i=0；i<n；i++)
for(j=0；j<m；j++)
s=s+a[i][i];
A．O(1)
B．O(m+n)
C．O(log2mn)
D．O(m*n)

正确答案：C
[解析]一个算法在计算机运行时所耗费的时间用时间复杂度来度量．算法的时间复杂度是算法输入规模或问题规模的函数，一般不必算出精确值，更关心的是相应的数量级．算法的时间复杂度与算法中语句的执行次数有直接关系，而语句的执行次数又取决于问题规模n的大小．实际上求解时间复杂度的方法是算出算法中执行频度最大的那条语句的频度，取其数量级放入 O( )中．
第22题：

下列程序段的时间复杂度为()。for(i=0；i＜m；i++)for(j=0；j＜t；j++)e[i][j]=0；for(i=0；i＜m；i++)for(j=0；j＜t；j++)for(k=0；k＜n；k++)c[i][j]_c[i][j]+a[i][k]×b[k][j]；

A.O(m×n×t)
B.O(m+n+t)
C.O(m×t+n)
D.O(m+n×t)

答案：A
解析：
在程序段中，有两段循环程序，第一段是一个双层嵌套循环，另一个是三层嵌套循环，所以基本操作是c[i][j]=c[i][j]+a[i][k]×b[k][j]，此基本操作共执行m×t×n次。
第23题：

填空题
下面程序段的时间复杂度是（） for（i=0；i＜n；i++） for（j=0；j＜n；j++） A[i][j]=0；

正确答案： O（n²）
解析：暂无解析

下面这个程序段的时间复杂度是( )。 for (i=1; i＜n; i++) { y=y+1; for (j=0; j＜=(2*n); j++) x++; }A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)

题目

相似考题

参考答案和解析

更多“下面这个程序段的时间复杂度是()。for(i=1;i<n;i＋＋){y=y＋1;for(j=0;j<=(2*n);j＋＋) x＋＋;}A.O(log2n ”相关问题

相关内容