该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分） (1)

01	#include<iostream>
02	#include<cstdio>
03	using namespace std;
04	const int N = 100010;
05	int n,a[N],x,y;
06	void work(int i,int j,int &x,int &y)
07	{
08		if (j - i == 0)
09		{
10			x = y = a[i];
11			return;	
12		}
13		else
14		{
15			int t = i + (j - i) / 2;
16			int x1,y1,x2,y2;
17			work(i,t,x1,y1);
18			work(t + 1,j,x2,y2);
19			if (x1 > x2)	x = x1;
20			else	x = x2;
21			if (y1 < y2)	y = y1;
22			else	y = y2;	
23		}
24	}
25	int main()
26	{
27		cin >> n;
28		for (int i = 1;i <= n;i++)
29		{
30			cin >> a[i];
31		}
32		x = y = 0;
33		work(1,n,x,y);
34		cout << x << " " << y << endl; 
35		return 0;
36	}

程序输入n 为[1,100000]范围内的正整数，a[i]为[-100000,100000]范围内的整数。

判断题

1). 将第15行改为int t = (l + r) / 2，程序行为不变。 {{ select(1) }}

• √
• ×

2). 第16行的数据没有给初始值，会影响后续的比较。（ ） {{ select(2) }}

• √
• ×

3). 输出的x和y始终为0。（ ） {{ select(3) }}

• √
• ×

4).即使输入有负数，输出的x和y也都是大于等于0的数。（ ） {{ select(4) }}

• √
• ×

单选题 5). 该程序的采用了下列哪种算法思想（ ）。 {{ select(5) }}

• 贪心算法
• 分治算法
• 宽度优先搜索
• 冒泡排序算法

6). 当输入为5 8 -5 3 4 0，输出为（ ）。 {{ select(6) }}

• 8 -5
• 8 0
• -5 8
• 0 8

(2)

01	#include<iostream>
02	#include<cstdio>
03	using namespace std;
04	int work(int x,int y)
05	{
06		int i,j;
07		for (i = 0;0 == (x & 1);++i)	x >>= 1;
08		for (j = 0;0 == (y & 1);++j)	y >>= 1;
09		if (j < i) i = j;
10		while (1)
11		{
12			if (x < y)	x ^= y,y ^= x,x ^= y;
13			if (0 == (x -= y))	return y << i;
14			while (0 == (x & 1))	x >>= 1;
15		}
16	}
17	int main()
18	{
19		int a = 0,b = 0;
20		cin >> a >> b;
21		cout << work(a,b); 
22		return 0;
23	}

输入的a 和 b 为[1,100000]范围内的正整数。 判断题 1). 0 == (x & 1)是在判断x的二进制表示中最后一位是不是0。 {{ select(7) }}

• √
• ×

2). work函数有可能出现死循环。（ ）

{{ select(8) }}

• √
• ×

3). 执行完第8行语句后，x和y都会变成奇数。（ ）

{{ select(9) }}

• √
• ×

4). 若输入6 9 输出为 3。（ ）

{{ select(10) }}

• √
• ×

单选题

5). 第12行的“x ^= y,y ^= x,x ^= y;”可以用下列哪个语句替换（ ）。 {{ select(11) }}

• swap(x,y);
• x = pow(x,y);
• y = pow(y,x);
• x = swap(x,y);

6). (4分)若输入42568 31926，输出为（ ）。 {{ select(12) }}

• 1
• 4
• 5321
• 313

(3)

01	#include <iostream>
02	using namespace std;
03	typedef long long LL;
04	bool is_prime(int n)
05	{
06	    if (n == 1) return false;
07	    for (int i = 2; i * i <= n; i ++ )
08	        if (n % i == 0)
09	            return false;
10	    return true;
11	}
12	bool check(int n, int d)
13	{
14	    if (!is_prime(n)) return false;
15	    LL r = 0;
16	    while (n)
17	    {
18	        r = r * d + n % d;
19	        n /= d;
20	    }
21	    return is_prime(r);
22	}
23	int main()
24	{
25	    int n = 0, d = 0;
26		cin >> n >> d; 
27	    if (check(n, d)) puts("Yes");
28	    else puts("No");
29	    return 0;
30	}

输入的 1 ≤ n ≤ 100000，2 ≤ d ≤ 10。

判断题

1). 当输入的n是2时，d输入2~10任意一个数，程序输出都是Yes。（ ） {{ select(13) }}

• √
• ×

2). 当输入的n是6时，d输入2~10任意一个数，程序输出都是No。（ ） {{ select(14) }}

• √
• ×

3). (2分)第18行语句是使用秦九韶算法，将n转为d进制。（ ） {{ select(15) }}

• √
• ×

单选题

4). 当n为157时，d输入下列哪个值，输出为Yes（ ）。

{{ select(16) }}

• 2
• 3
• 4
• 5

5). 函数is_prime()的时间复杂度为（ ）。

{{ select(17) }}

• O($sqrt {2}$)
• O(log(n))
• O(n)
• O(n²)

6). (4分) 当n为101时，d输入下列哪个值，21行中传入的参数r最小。（ ）

{{ select(18) }}

• 6
• 8
• 5
• 3