软考初级
以下函数中渐进时间最小的是(44)。A．T1(n)=2n+nlognB．T2(n)=n+10 000lognC．T3(n)=2n+nlognD．T4(n)=n2+nlogn
题目
以下函数中渐进时间最小的是(44)。
A．T1(n)=2n+nlogn
B．T2(n)=n+10 000logn
C．T3(n)=2n+nlogn
D．T4(n)=n2+nlogn
参考答案和解析
解析：通常情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记做T(n)=O(f(n))。它表示随问题规模n的增大，算法执行的时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度。当n→∞时，常见的渐进时间复杂度大小关系如下。O(1)≤O(n)≤O(nlogn)≤O(n2)由此可知，试题中所给出的4个函数中，函数T2(n)=n+10000logn的渐进时间最小。
相似问题和答案
第1题：
（ 14 ）下面的函数定义是某函数模板能够生成的函数实例
int square(int n) {return n*n;}
double square(double n) {return n*n;}
由此可知，该函数模板的定义是 【 15 】 。
第2题：
n变量的逻辑函数其全部最小项有n个。()
第3题：
以下程序中函数 fun 的功能是：统计 person 所指结构体数组中所有性别 (sex) 为 M 的记录的个数 ， 存入变量 n 中，并做为函数值返回。请填空：
#include <stdio.h>
#define N 3
typedef struct
{ int num;char nam[10]; char sex;} SS;
int fun(SS person[])
{ int i,n=0;
for(i=0;i<N;i++)
if( 【 14 】 =='M') n++;
return n;
}
main()
{ SS W[N]={{1, "AA", 'F'},{2, "BB",'M'},{3,"CC", 'M'}}; int n;
n=fun(W); printf("n=%d\n",n);
}
第4题：
下述函数中渐进时间最小的是(137)。
A．T1(n)=nlog2n+100log2n
B．T2(n)=nlog2n+100log2n
C．T3(n)=n2-100log2n
D．T4(n)=4nlog2n-100log2n
解析：当n无限增大时，T1(n)≤T2(n)≤T3(n)T4(n)。所以T4的渐进时间最小。
第5题：
n变量的逻辑函数其全部最小项为2n个。()
第6题：
T(n)=O(f(n))中，函数O()的正确含义为
A.T(n)为f(n)的函数
B.T(n)为n的函数
C.存在足够大的正整数M，使得T(n)≤M×f(n)
D.存在足够大的正整数M，使得M×f(n)≤T(n)
第7题：
请补充main函数，该函数的功能是：把一个整数插入到一个已经按从小到大排序的数组中。插入后，数组仍然有序。
例如，在数组bb[N]={12，23，31，44，51，63，71，79，85，95}中插入93，结果为：
bb[N]{11，21，31，41，51，61，7l，79，8l，93，95}
注意：部分源程序给出如下．
请勿改动主函数main和其他函数中的任何内容，仅在 main函数的横线上填入所编写的若干表达式或语句。
试题程序：
include＜std/o. h＞
define N 10
main()
{
int i,j;
int n;
int bb IN+l] ={ t2,23, 31, 44, 51, 63, 71,
79,85,95};
clrscr ();
printf("\nInput n \n");
scanf ("%d", &n);
printf ("\nn=%d ",n);
printf("\n*** original list ***In");
for (i=0; i＜N; i++)
printf ("%4d ",bb [ii );
for (i=0; i＜N; i++)
{
if (n＜=bb [i ] )
{
for(j=N;【 】;j--)
【 】;
bb [j] =n;
【 】;
}
if (i=N)
bb[i]=n;
printf("\n***** new list ******In");
for (i=0;i＜N+l; i++)
printf ("%4d ",bb [i]);
}
j>I bb[j]=bb[j-1] break 解析：第一空：因为原数组是按从小到大排列，所以从第一个元素开始，遂一与待插入的元素进行比较，第一个大于待插入元素n的元素bb[i]的下标i即为插入位置。所以，从bb[i]到bb[N-1]都要依次向后移动一个位置，使待插入元素n存于bb[i]。
这里，for循环中j取值从N到i+1。填空i+1。为了实现从bb[i]到bb[N-1]依次向后移动一个位置，将当前元素赋给下一个元素，要注意，为了不覆盖未经处理的元素，应该从最后一个元素开始移动。第三空：将整数n插入数组后，函数功能已经实现，应使用break语句跳出for循环。
第8题：
下述函数中渐进时间最小的是______。
A．T1(n)=n+nlogn
B．T2(n)=2n+nlogn
C．T3(n)=n2-logn
D．T4(n)=n+100logn
第9题：
程序定义了N×N的二维数组，并在主函数中自动赋值。
请编写函数fun(int a[][N]，int n)，该函数的功能是使数组左下半三角元素中的值加上n。
例如：若n的值为3，a数组中的值为
a=2 5 4
1 6 9
5 3 7
则返回主程序后a数组中的值应为
5 5 4
4 9 9
8 6 10
注意：部分源程序给出如下。
请勿改动主函数main和其他函数中的任何内容，仅在函数full的花括号中填入所编写的若干语句。
试题程序：
include ＜stdio.h＞
include ＜conio.h＞
include ＜stdlib.h＞
define N 5
fun(int a[][N]，int n)
{
}
main()
{
int a[N][N]，n，i，j；
clrscr()；
printf("***** The array *****\n")；
for(i=0；i＜N；i++)
/*产生—个随机5*5矩阵*/
{
for(j=0；j＜N；j++)
{
a[i][j]=rand()%10；
printf("%4d"，a[i][j])；
}
printf("\n")；
}
do
n=rand()%10；
/*产生一个小于5的随机数n*/
while(n＞=5)；
printf("n=%4d\n"，n)；
fun(a，n)；
printf("*****THE RESULT*****\n")；
for(i=0；i＜N；i++)
{
for(j=0；j＜N；i++)
printf("%4d"，a[i][j])；
printf("\n")；
}
}
fun (int a[ ][N], int n) { int i,j; for(i=0; iN; i++) for(j=0; ji; j++) a[i][j]=a[i][j]+n /*使数组左下半三角元素中的值加上n*/ } 解析：首先从数组中找出要被加上n的那部分元素，找的过程其实就是找出将被挑出的那部分元素在原数组中的分布规律的过程。通过观察得出，要被处理的那部分元素的下标值的范围是每行中从第一个元素开始，直到列数等于该行行数时为止。找到这个规律后，依次从数组中取得合乎要求的元素，然后再加上n。
第10题：
以下函数中渐进时间最小的是(64)。
A．T1(n)=2n+nlogn
B．T2(n)=n2+logn
C．T3(n)=2n+nlogn
D．T4(n)=n+10000logn
解析：通常情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))。它表示随问题规模n的增大，算法执行的时间的增长率和f(n)的增长率相同，称为算法的渐进时间复杂度。当n→∞时，常见的渐进时间复杂度大小关系如下。
O(1)≤O(n)≤O(nlogn)≤O(n2)
由此可知，本试题选项中所给出的4个函数中，函数T4(n)=n+10000logn的渐进时间最小。