数据结构
下面程序段的时间复杂度是（） for（i=0；i＜n；i++） for（j=0；j＜n；j++） A[i][j]=0；
题目
下面程序段的时间复杂度是（） for（i=0；i＜n；i++） for（j=0；j＜n；j++） A[i][j]=0；
相似问题和答案
第1题：
以下程序运行后的输出结构是。main(){ int i,j,a[][3]={1,2,3,4,5,6,7,8,9}; for(i=0;i<3;i++) for(j=i;j<3;j++)a[j][i]=0; for(i=0;i<3;i++) { for(j=0;j<3;j++) printf("%d ",a[i][j]); printf("\n"); }}
将a[0][0],a[1][0],a[2][0],a[1][1],a[2][1],a[2][2]赋值为0，所a[][3]={0,2,3,0,0,6,0,0,0}
第2题：
以下程序的输出结果是 ( ) main( ) { int n[3] [3]，i，j； for (i＝0；i＜3；i+ +) for(j＝0；i＜3;++) n[i][j]=i+j; for(i＝0；i＜2；i++) for(j＝0，j＜2；j++) n[i+1][j+1]+＝[i][j]； printf("%d\n"，n[1][j])； }
A．14
B．0
C．6
D．值不确定
第3题：
A、O(n)
B、O(m+n+1)
C、O(m+n)
D、O(m*n)
第4题：
下面程序段的时间复杂度为 ( ) 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)
解析：此程序的时间复杂度即为程序中循环次数的时间耗费。由程序为嵌套循环，外层循环的时间复杂度T(n1)=m，内层循环的时间复杂度T(n2)=n，则此程序的时间复杂度T(n)=m*n，即为0(m*n)。
第5题：
请补充函数fun()，该函数的功能是：按行统计N×N维矩阵元素中的最大值(均为整数)，并把这些值按从小到大的顺序保存在数组b中。矩阵的维数在主函数中输入，并赋予随机数。
注意：部分源程序给出如下。
请勿改动主函数main和其他函数中的任何内容，仅在函数fun的横线上填入所编写的若干表达式或语句。
试题程序：
include＜stdio．h＞
include＜conio．h＞
include＜stdlib．h＞
define N 20
void fun(【 】)
{
int i j；
int t；
for(i=0；i＜n；i++)
for(j=0；j＜n；j++)
if(【 】)
b[i]=a[i][j]；
for(i=0；i＜n；i++)
{
for(j=0；i＜n；j++)
if(【 】)
{
t=b[i]；
b[i]=b[j]；
b[j]=t；
}
}
}
main()
{
int a[N][N]；
int b[N]；
int n；
int i，j；
clrscr()；
printf("*****Input the dimension of array N*****\n")；
scanf("%d"，&n)；
printf("*****The array *****\n")；
for(i=0；i＜n；i++)
{
for(j=0；i＜n；j++)
{
a[i][j]=rand()%20；
while(a[i][j]==0)
a[i][j]=rand()%30；
printf("%4d"，a[i][j])；
}
printf(”\n\n”)；
}
for(i=0；i＜n；i++)
b[i]=0；
fun(a，b，n)；
printf("***** THE RESULT *****\n")；
for(i=0；i＜n；i++)
printf(“%d”，b[i])；
}
int a[][N],int b[],int n b[i]a[i][j] b[i]b[j] 解析：第一空：根据主函数main()调用函数fun()的格式，可以知道函数fun()有3个参数，第一个参数是N×N整型二维数组，第二个参数是整型—维数组，第三个参数是整型变量。第二空：数组元素b[i]保存第i行的最大值，通过循环将第i行的各元素与b[i]进行比较，如果大于b[i]，则将这个数赋给b[i].第三空：通过for循环嵌套，将数组b中的数按从小到大的顺序排列，依次将各元素与所有元素进行比较，如果有一个元素比当前元素大，就借助第三个变量交换这两个元素，最终使第一个元素保存数组中最小的数，最后一个元素保存数组中最大的数。
第6题：
以下程序运行后的输出结果是【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 解析：该题先是初始化数组n[2]中的元素全部赋值为0，然后执行两层for循环，当i=0，j=0，a[0]为1、a[1]为0，当j=1时，a[0]为1、a[1]为2；当i=1，j=0，a[0]为3、a[1]为2，当i=1，j=1时，a[0]为3、a[1]为3。
第7题：
执行下面程序段，语句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)
解析：本题考查如何衡量算法的复杂度，根据题目可以看出，两层循环每次执行的次数是不相等的，第一次循环执行了n次，第二次循环只执行了n-1次，直到最后一次循环，他执行了2次，这样就是一个等差数列的求和，可得到总的执行次数为(n-1)(n+2)/2。
第8题：
以下程序按下面指定的数据给 x 数组的下三角置数，并按如下形式输出，请填空。
4
3 7
2 6 9
1 5 8 10
#include <stdio.h>
main()
{ int x[4][4],n=0,i,j;
for(j=0;j<4;j++)
for(i=3;i>=j; 【 12 】 ) {n++;x[i][j]= 【 13 】 ; }
for(i=0;i<4;i++)
{ for(j=0;j<=i;j++) printf("%3d",x[i][j]);
printf("\n");
}
}
第9题：
以下程序的执行结果是______。 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
第10题：
下面这个程序段的时间复杂度是( )。 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)
解析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。在本例算法中，其中语句“y=y+1；”的频度是n-1，语句“x++；”的频度是(n-1)(2n+1)=2n2-n-1，则该程序段的时间复杂度是T(n)=n-1+2n2-n-1=O(n2)。