江苏网站建设机构,计算机编程网课,c asp做网站,app网站开发哪家专业一、选择题 01.一个算法应该是( B ). A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和C 02#xff0e;某算法的时间复杂度为O(n)#xff0c;则表示该…一、选择题 01.一个算法应该是( B ). A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和C 02某算法的时间复杂度为O(n²)则表示该算法的( C )。 A,问题规模是n² (默认都是n) B.执行时间等于n² k*n² C.执行时间与n²成正比 D.问题规模与n²成正比解析:算法时间复杂度O(F(n))意味着算法在任何情况下规模为n时所花费的时间k*F(n) 03若某算法的空间复杂度为O(1)则表示该算法 B )。 A,不需要任何辅助空间 B.所需辅助空间大小与问题规模n无关 C.不需要任何空间 D.所需空间大小与问题规模n无关 04下列关于时间复杂度的函数中时间复杂度最小的是 D ). 05以下算法的时间复杂度为 D ). void fun(int n){ //n作为参数 int i1; while(in) ii*2; //核心运算 } 解析核心操作是ii*2判断运算次数 即1*2*2*2乘多少次是n (2的几次方是n)
06.有以下算法其时间复杂度为 C ). void fun (int n){ int i0; while(i*i*in) i; //i通过操作往后推进是核心操作 } 解析核心运算是i,i*i*i仅用于逻辑判断并没有“推进i” 当i*i*in时则停止增加 即i n开三次方
07程序段如下: for(in-1;i1;i--) for(j1;ji;j) if(A[j]A[j1]) //满足条件执行if A[j]与A[j1]对换; 其中n为正整数则最后一行语句的频度在最坏情况下是( D )。解析冒泡排序的算法代码所有相邻元素都为逆序时最后一行的语句每次都会执行 08.下列程序段的时间复杂度为 A )。 if(n0){ for (int i0;in;i) for(int j0;jn;j) printf(输入数据大于或等于零\n) } else{ for(int j0;jn;j) printf(输入数据小于零\n) 09以下算法中加下画线的语句的执行次数为 A )。 m的执行次数 int m0,i,j; for(i1;in;i) for(j1;j2*i;j) m; A. n(n1) B.n C. n1 D. n² 10.下列函数代码的时间复杂度是( C )。 int Func(int n){ if(n1) return 1; else return 2* Func(n/2)n; 11.【2011统考真题】设n是描述问题规模的非负整数下列程序段的时间复杂度是( A ) x2; //初值 while(xn/2) //结束条件 x2*x; //执行操作 解析x2*2*2*....乘多少次2达到n 12.【2012统考真题】求整数n(n≥0)的阶乘的算法如下其时间复杂度是( B )。 int fact(int n){ if(n1) return 1; return n*fact (n-1); //递归程序 “解析程序就是一个递归整个程序的基础操作只有递归处有乘法一次递归是一次乘法运算值为n的情况下递归嵌套n次
13.【2014统考真题】下列程序段的时间复杂度是( C )。 count0; for(k1;kn;k*2) for(j1;jn;j) count; 解析第一层:k的取值分别是1248...一直到nlog2n次循环 第二层:无论k的取值是多少第二层都是自加n次 14.【2017统考真题】下列函数的时间复杂度是 B ). int func (int n){ int i0,sum0; while(sumn) sum i; return i; ) 解析核心操作sumi; sum的变化过程0123....i ,当sumn时跳出循环判断i加了几次求和公式为sumi*(i-1)/2n,根据数量级可以把左边看成i²即i²n 所以in的二分之一次方 15.【2019统考真题】设n是描述问题规模的非负整数下列程序段的时间复杂度是( B )。 x0; while (n(x1)*(x1)) xx1; 解析(x1)²n 根据同阶数量级可以看成x²n 即x趋向于根号n
16.【2022统考真题】下列程序段的时间复杂度是( B )。 int sum0; for(int il;in;i*2) for(int j0;ji;j) sum; 解析:求出sum的执行次数 第一层i1,2,4,8...2的k次方 第二层ji,所以j有0~i-1个 123....2的k次方 2的k1次方-12n
二、综合应用题
01分析以下各程序段求出算法的时间复杂度。 ① i1;k0; while(in-1){ kk10*i; i; ② y0; while((y1)*(y1)n) yy1; ③ for(i0;in;i) for(j0;jm;j) a[i][j]0; ①基本语句kk10*i共执行了n-2次所以T(n) O(n)。 ②设循环体共执行t次,每循环一次,循环变量y加1,最终ty。故t²≤n,得T(n)O(n1/2)。 ③内循环执行m次,外循环执行n次,根据乘法原理,共执行了mxn次,故T(m, n)O(mxn)。
