总结

今天又双叒叕考试了

1：关于CPU下面哪些说法是正确的？（ ）。

A. CPU全称为中央控制器

B. CPU能直接运行机器语言

C. CPU最早是由Intel公司发明的

D.同样主题下，32位的CPU比16位的CPU运行速度快一倍

cpu全名中央处理器

cpu是由晶体管和电子管组成的

Intel公司发明的是微型处理器，

同样的计算器在不同的环境中的运算时间不一样

2：应用快速排序的分治思想，可以实现一个求第K大数的程序。算法的平均时间复杂度为( )。

A. $O(logn)$

B. $O(nlogn)$

C. $O(n)$

D. $O(1)$

用单臂快排，每一边只用排一遍，所以时间复杂度为$O(n)$

3：某算法计算时间表示为递推关系式：T(N)=N+2T(N/2),则该算法时间复杂度为( )。

A. O (N​^2^​)

B. O (NlogN)

C. O (N)

D. O (1)

设n=$2^k$，则n=2×k×T(1)+k×n=n×(long(n)+T(1))=$O(nlongn)$

4:假设给定有向无环图 G 中具有 n 个顶点和 m 条边，则对图 G 进行拓扑排序的时间 复杂度为（ ）。

A.O(n+m)

B.O(n*m)

C.O(nlogn)

D.O(mlogn) 拓扑排序就是每个定点和边都删除一次的过程。故时间复杂度为$O(n+m)$。

5:阅读程序

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int p[N];
int n;
int main() {
	cin >> n;
	for (int i = 2; i <= n; ++i) 
	{
		int t = i;
		for (int j=2; j*j<= i; j++) 
		{
		while (t%j==0) 
		{    
		p[j]++;    
		t /= j;
		}
	}
	if (t > 1) 
	{
		p[t]++;
	}
	}
	long long ans = 1;
	for (int i = 2; i <= n; ++i) 
	{
		ans = ans * (p[i] + 1) ;
	}
	cout << ans << endl;
return 0;
}

1、程序在求2-n中有多少个素数。()

√ ×

程序在求n的阶乘的约数个数

2、程序输入5，输出10。()

√ ×

程序累计2-5每个数的质因子

$2^3×3^1×5^1$

3、将11行的”while”改为”if”，程序运行结果不变。()

√ ×

肯定会变，每一个数又不是只有一个质因数

4、（2分）程序运行到12行是，j一定是素数。()

√ ×

j首先是t的因子。假设j不是质数，那么j一定可以分表示成a*b的情况其中a和b都不为1,且小于j，j是从小达到遍历的，那么在前面循环到j=a或者b的时候,while循环执行完后t移动就不能在被a或者b整除了，而后面又有t整除j，j=a*b,得到t整除a和b，矛盾。假设不成立。j一定是质数。

选择题

5、（4分）程序的时间复杂度为()。

A.O(n)

B.O(n​^2​)

C.O(nlogn)

D.O(sprt(n)×n)

6、（4分）输入10，运行结束时，p数组所有元素的值的和为()。

A..10

B.12

C.15

D.20

2-10被分解为$2​^1$×$3​^1$×$2​^2​$×$5​^1$​×$2^1$×$3​^1$×$7​^1$×$2​^3​$×$3​^2$×$2^1$×$5^1$ =$2​^8$×$3​^4​$×$5​^2$×$7​^1$​,即p[2]=8,p[3]=4, p[5]=2,p[7]=1，其余都为0，p数组元素之和为8+4+2+1=15.

7、输入10，运行结束时，输出为( )。

A.200

B.225

C.250

D.270

直接用上一题的方法计算

6：完善程序

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, target;
int nums[N];
int main() 
{
	scanf("%d%d", &n, &target);
	for (int i = 0; i < n; ++i) 
	{
		cin >> nums[i];
	}
	int l=0,h=n,mid=0;
	while (2) 
	{ 
			mid = (l + h) / 2;
			if (target == nums[mid]) 
			{
				printf("%d\n",  mid );
				return 0;
			}
			else if (target > nums[mid]) 
			{
				l=mid+1;
			} 
		else 
		{
			h=mid;
		}
	}
	printf("%d\n",l);
return 0;
}

1：n为元素个数，i为下标，我们从前往后一个一个插入滑动序列

2：如果队头不在窗口里则弹出队头

3：然后如果当前元素大于等于队尾元素则队尾元素出队

4：如果i>=k-1说明没有窗口了

1：首先输入数组，然后记录开始值和结束值，声明一个中间值mid

2：然后用二分答案找target

3：如果有输出下标，如果没有输入target插入的位置

①处应填 ( )

A、n

B、n - 1

C、n + 1

D、1

②处应填 ( )

A、l < h

B、l <= h

C、true

D、target != nums[mid]

③处应填 ( )

A、nums[mid]

B、mid

C、nums[l]

D、l

④处应填 ( )

A、l = mid

B、l = mid - 1

C、l = mid + 1

D、l = nums[mid]

⑤处应填 ( )

A、l

B、mid

C、r - 1

D、l + 1

(2)

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int arr[N];
int q[N];
int main() 
{
	int n,k;
	cin>>n>>k;
	int h=0,t=0;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	for(int i=0;i<n;i++)
	{
		if(i>=k&&q[h]==i-k)
		{
			h++; 
		}
		while(h<t&&arr[i]>=arr[q[t-1]])
		{
			t--;
		}
		q[t++]=i;
		if(i>=k-1)
		{
			cout<<arr[q[h]]<<' ';
		}
	}
return 0;
}

①处应填 ( )

A、i <= n

B、i < n

C、i <= k

D、i < k

②处应填 ( )

A、i >= k && q[head] == i - k

B、i > k && q[head] == i - k

C、i >= k && q[head] == arr[i-k]

D、i > k && q[head] == arr[i-k]

③处应填 ( )

A、arr[i] >= q[tail]

B、arr[i] > q[tail-1]

C、arr[i] >= arr[q[tail]]

D、arr[i] >= arr[q[tail-1]]

④处应填 ( )

A、q[tail++] = i

B、q[++tail] = i

C、q[tail++] = arr[i]

D、q[++tail] = arr[i]

⑤处应填 ( )

A、i >= k

B、i > k

C、i >= k - 1

D、i > tail