#cspjc2022y3. 2022csp-j初赛程序阅读3

2022csp-j初赛程序阅读3

2022csp-j初赛程序阅读3

判断题 1.5 分,选择题 3 分

1.第三题

#include <iostream>

using namespace std;

int n,k;
 
int solve1()
{
	int l = 0, r = n;
	while(l <= r){
		int mid = (l + r) / 2;
		if (mid * mid <= n) l = mid + 1;  //12行 
		else r = mid - 1;
	}
	return l - 1;
}

double solve2(double x)
{
	if (x == 0) return x;
	for (int i = 0; i < k; i++)
		x = (x + n / x) / 2;
	return x;
}

int main()
{
	cin >> n >> k;
	double ans = solve2(solve1());
	cout << ans << ' ' << (ans * ans == n) << endl;
	return 0;
}

​ 假设 int 为32位有符号整数类型,输入的 n 是不超过47000的自然数、k 是不超过 int 表示范围的自然数,完成下面的判断题和单选题:

判断题

1.该算法最准确的时间复杂度分析结果为 O(log⁡n+k)。( ) {{ select(1) }}

  • √
  • ×

2.当输入为 9801 1 时,输出的第一个数为 99。( ) {{ select(2) }}

  • √
  • ×

3.对于任意输入的 n,随着所输入 k的增大,输出的第二个数会变成 1。( ) {{ select(3) }}

  • √
  • ×

4.该程序有存在缺陷。当输入的 n 过大时,第 12 行的乘法有可能溢出,因此应当将 mid 强制转换为 64 位整数再计算。( ) {{ select(4) }}

  • √
  • ×

选择题

5.当输入为 2 1 时,输出的第一个数最接近( ) {{ select(5) }}

  • 1
  • 1.414
  • 1.5
  • 2

6.当输入为 3 10 时,输出的第一个数最接近( )。 {{ select(6) }}

  • 1.7
  • 1.732
  • 1.75
  • 2

7.当输入为 256 11 时,输出的第一个数( ) {{ select(7) }}

  • 等于 16
  • 接近但小于 16
  • 接近但大于 16
  • 前三种情况都有可能