农村信用社
下面的程序段的时间复杂度为【】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)
题目
下面的程序段的时间复杂度为【】
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)
相似问题和答案
第1题：
下面程序的运行结果是( )。 #include＜stdio.h＞ void del(char*s) { int i,j; char *a; a=s; for(i=0,j=0;a[i]!='\0';i++) { if(a[i]＞='0'&&a[i]＜='9') { s[j]=a[i]; j++; } s[j]='\0'; }} main() {char s[]="aa89gggh"; del(s); printf("\n%s",s); }
A．aa
B．89
C．gggh
D．aa89gggh
解析：本题中del(char*s)函数实现的功能是：逐个读入s数组中的字符，如果遇到数字，则将其重新存在s中，遇到非数字字符则跳过。所以最后输出的应该是字符串s中的所有数字。
第2题：
现在有如下程序
#include "stdio.h"
main（）
{char s［80］;
int i,j;
gets（s）;
for（i=j=0;s［i］!=′＼0′;i++）
if（s［i］!=′H′______）
s［j］=′＼0′;
puts（s）;}
这个程序段的功能是删除输入的字符串中字符′H′，则空线上应当添入的是
A．s［j++］=s［i］;j++;
B．s［j］=s［i++］;j++;
C．s［j++］=s［i］;
D．s［j］=s［i］;
第3题：
（ 14 ）以下程序用以删除字符串所有的空格，请填空。
#include <stdio.h>
main （）
{ char s[100]={ " Our teacher teach C language! " };int i,j;
for （ i=j=0;s[i]!= ’ \0 ’ ;i++ ）
if （ s[i]!= ‘ ’ ） {s[j]=s[i];j++;}
s[j]= 【 14 】
printf （ " %s\n " ,s ） ;
}
第4题：
阅读下列函数说明和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)处应该为矩阵下边界递减；(2)处应该为数组元素递减状态，即为降；(3)处应该为矩阵上边界递增；(4)处应该为存放矩阵元素的数组中的数据递减；(5)处应该为数组元素的列序号递减，即j--；(6)矩阵右边界递减。
第5题：
A、O(m2)
B、O(n2)
C、O(m*n)
D、O(m+n)
第6题：
下面这个程序段的时间复杂度是( )。 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)
解析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。在本例算法中，语句①的频度是n-1，语句②的频度是(n-1)(2n+1)-2n2-n-1。则该程序段的时间复杂度是T(n)=n-1+2n2-n-1=O(n2)。
第7题：
下列程序段的时间复杂度为()。i=0，s=0;while(sn){s=s+i;i++;}
A、O(n1/2)
B、O(n1/3)
C、O(n)
D、O(n2)
第8题：
A、O(n)
B、O(m+n+1)
C、O(m+n)
D、O(m*n)
第9题：
A.6385
B.69825
C.63825
D.693825
第10题：
以下程序的执行结果是______。 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