itgle.com

试分析下面程序段的时间复杂度。 for （i=0; i＜n; i++) for （j=0; j＜m; j++) a[i][j]=0;A．O(m)B．O(n)C．O(m*n)D．O(m+n)

题目

试分析下面程序段的时间复杂度。 for （i=0; i＜n; i++) for （j=0; j＜m; j++) a[i][j]=0;

A．O(m)

B．O(n)

C．O(m*n)

D．O(m+n)

相似考题

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

2.以下程序按下面指定的数据给 x 数组的下三角置数，并按如下形式输出，请填空。43 72 6 91 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");}}

3.以下程序运行后的输出结构是。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"); }}

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)

更多“试分析下面程序段的时间复杂度。 for （i=0; i＜n; i++) for （j=0; j＜m; j++) a[i][j]=0;”相关问题

  • 第1题：

    阅读下面程序: include void main() { int i,j,row=0,column=0,m; static int a[3]

    阅读下面程序：

    include ＜iostream.h＞

    void main()

    {

    int i,j,row=0,column=0,m;

    static int a[3][3]={ 100,28,72,-30,2,-100};

    m=a[0][0];

    for (i=0;i＜3;i++)

    for (j=0;j＜3;j++)

    if (a[i][j]＜m)

    {

    m=a[i][j];

    row=i;

    column=j;

    }

    cout＜＜m＜＜","＜＜row＜＜","＜＜column＜＜endl;

    }

    该程序的功能是【 】，其执行结果为上丝【 】。


    正确答案：找到数组a中的最小元素并输出其数值及行列值 -10012
    找到数组a中的最小元素并输出其数值及行列值 -100,1,2

  • 第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．值不确定


    正确答案：C

  • 第3题：

    下面的程序段运行后,输出结果是

    int i,j,x=0;

    static int a[8][8];

    for(i=0;i<3;i++)

    for(j=0;j<3;j++)

    a[i][j]=2*i+j;

    for(i=0;i<8;i++)

    x+=a[i][j];

    printf("%d",x);

    A．9

    B．不确定值

    C．0

    D．18


    正确答案：C
    解析：本题主要考查的是用二维数组首地址和下标来引用二维数组元素的方法。通过分析可知,程序中的双重循环定义了一个如下的二维数组:
    0  1  2
    2  3  4
    4  5  6
    由于数组的下标是从0开始的,所以二维数组元素a[i][j]表示的是二维数组a的第i+1行、第j+1列对应位置的元素。

  • 第4题：

    以下程序的执行结果是______。 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

  • 第5题：

    下面这个程序段的时间复杂度是( )。 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)。

  • 第6题：

    有以下程序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。

  • 第7题：

    分析下列程序，其最终执行结果是______。 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。

  • 第8题：

    下面程序的输出结果是()。include using namespace std;void main( )int i,j,m=0,n=0;

    下面程序的输出结果是( )。 #include ＜iostream＞ using namespace std; void main( ) int i,j,m=0,n=0; for(i=0;i＜2;i++) for(j=0;j＜2;j++) if(j＞ =i) m=1;n++; cout＜＜m＜＜endl; cout＜＜n;

    A．1 1

    B．1 4

    C．1 6

    D．0 2


    正确答案：A
    解析：注意整个二重循环作用的语句为：if(j=i)m=1;，而n++语句并不为二重循环控制。其实不论循环多少次，m、n的值总为1。

  • 第9题：

    下面的程序段运行后，输出结果是 int i，j，x=0； static int a[8][8]； for(i=0；i＜3；i++) for(j＝0；j＜3；j++) a[i][j]=2*i+j； for(i=0；i＜8；i++) x+=a[i][j]； printf("%d"，x)；

    A．9

    B．不确定值

    C．0

    D．18


    正确答案：C
    解析：本题主要考查的是用二维数组首地址和下标来引用二维数组元素的方法。通过分析可知，程序中的双重循环定义了一个如下的二维数组：

    由于数组的下标是从。开始的，所以二维数组元素a[i][j]表示的是二维数组a的第i+1行、第j+1列对应位置的元素。

  • 第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<20；i++）                for（j=0；j<10；j++）               a[i]：=a[i]×j 试举例说明该程序的空间局部性和时间局部性。


    正确答案:当数组元素a[0]，a[1]，…，a[19]存放在一个页面中时，其空间局部性和时间局部性较好，也就是说，在很短时间内执行都挂行循环乘法程序，而且数组元素分布在紧邻连续的存储单元中。当数组元素存放在不同页面中时，其时间局部性虽相同，但空间局部性较差，因为处理的数组元素分布在不连续的存储单元中。

  • 第12题：

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

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

  • 第13题：

    以下程序运行后的输出结果是【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。

  • 第14题：

    下面这个程序段的时间复杂度是( )。 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)


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

  • 第15题：

    下列程序的输出结果是 #include"stdio.h" #define N 3 #define M 3 void fun(int a[M][N]) { printf("%d\n"，*(a[1]+2))；} main() { int a[M][N]； int i，j； for(i=0;i＜M；i++) for(j=0;j＜N；j++) a[i][j]=i+j-(i-j)； fun(a)；}

    A．3

    B．4

    C．5

    D．6


    正确答案：B
    解析：若有以下定义：inta[3][4]，i，j；且当0=i3，0=j4，则可以有以下几种方式来引用数组中的第i行，第j列的元素：a[i][j]，*(a[i]+j)，*(*(a+i)+j)，(*(a+i))[j]，*(&a[0][0]+4*i+j)。

  • 第16题：

    下面程序段的时间复杂度为 ( ) 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(n1)=m，内层循环的时间复杂度T(n2)=n，则此程序的时间复杂度T(n)=m*n，即为0(m*n)。

  • 第17题：

    有以下程序 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

  • 第18题：

    有以下程序

    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

  • 第19题：

    下面程序段的时间复杂度是(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)。

  • 第20题：

    下列程序的时间复杂度为( )。 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)，

  • 第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（n2）

  • 第24题：

    问答题
    考虑下面的程序： for （i=0；i<20；i++）                for（j=0；j<10；j++）               a[i]：=a[i]×j 试举例说明该程序的空间局部性和时间局部性。

    正确答案： 当数组元素a[0]，a[1]，…，a[19]存放在一个页面中时，其空间局部性和时间局部性较好，也就是说，在很短时间内执行都挂行循环乘法程序，而且数组元素分布在紧邻连续的存储单元中。当数组元素存放在不同页面中时，其时间局部性虽相同，但空间局部性较差，因为处理的数组元素分布在不连续的存储单元中。
    解析： 暂无解析

相关内容