一、单项选择题(共15题，每题2分，共计30分）

1. 网址 www.luogu.com.cn 当中，顶级域名是（ ）。{{ select(1) }}

• www
• com.cn
• luogu
• cn

2. 双向链表中有两个指针域 llink 和 rlink，分别指向该结点的前驱和后继。设P指向链表中的一个结点。它的左右结点均非空。现要求删除结点P，则下面语句序列中错误的是（ )。{{ select(2) }}

• P->rlink->llink = p->rlink;P->llink->rlink = p->llink; delete(p)
• P->llink->rlink =p->llink;P->rlink->llink = p->llink; delete(p)
• P->rlink-> llink =p->llink;P->rlink->llink ->rlink= p->rlink;delete(p)
• P->llink->rlink =p->rlink;P->llink->rlink->llink = p-> llink;delete(p)

3. 一个字长为8位的整数的补码是11111001，则它的原码是( )。{{ select(3) }}

• 00000111
• 01111001
• 11111001
• 10000111

4. 「流程结构」是编程中用于控制程序执行流程的一种方式．它包括顺序结构、分支结 构和循环结构．在一些诗歌作品中，也有对「流程结构」的体现．下列诗歌片段中体 现循环结构的是（ ）。{{ select(4) }}

• 只要我还能够行走，只要我还能够张望，只要我还能够呼吸，就一直走 向前方。
• 如果还能找到你，就让风儿告诉你。
• 昔闻洞庭水，今上岳阳楼。
• 啊如果我在，战斗中牺牲，啊朋友再见吧，再见吧，再见吧！如果我 在，战斗中牺牲，你一定把我来埋葬。

5. 下列IP地址中正确的是( )。{{ select(5) }}

• 202.300.12.4
• 192.168.0.3
• 100:128:35:91
• 19.256.0.1

6.已知两个二进制整数 𝑎, 𝑏： 𝑎 = $1010001010_{(2)} ; 𝑏 = 1110100110_{(2)}$ 则表达式 (a&b)^(a|b) 的值为（ ）。{{ select(6) }}

• $0011011010_{(2)}$
• $0100101100_{(2)}$
• $0011010010_{(2)}$
• $0100101000_{(2)}$

7. 后缀表达式abc+*d-中，a=1,b=2,c=3,d=4,则该后缀表达式的值为( )。{{ select(7) }}

• 3
• -1
• 5
• 1

8. 十进制小数 0.3，转写成八进制为（ ）。{{ select(8) }}

• 0.3
• 0.2314631⋯
• 0.2046204⋯
• 0.3333333⋯

9. 一个有 10 个节点的有向图，要使得每一个满足 1 ≤ 𝑖,𝑗 ≤ 10, 𝑖 ≠ 𝑗 的点对 (𝑖,𝑗) 都 存在一条从 𝑖 到达 𝑗 的路径，至少需要连（ ）条有向边。{{ select(9) }}

• 9
• 10
• 19
• 20

10. 观察下列代码

int a[] = {5, 4, 3, 2, 1};
auto p = a + 3;
auto q = &p;
(*q) ++;
auto k = *p;

其中，𝑘 的类型以及 𝑘 的值分别为（）。{{ select(10) }}

• int 类型，值为 1
• int 类型，值为 3
• int 指针类型，值为 𝑎 数组的下标为 3 的元素的地址
• int 指针类型，值为 𝑎 数组的下标为 4 的元素的地址

11. 一张大小为 6114 × 8192 的 24 位彩色图片，使用 .bmp 格式存储，占用的空间大小约为（ ）。{{ select(11) }}

• 144 MiB
• 288 MiB
• 1152 MiB
• 48 MiB

12. 有一个长为5的A序列：{3.20.4.6.1}，现通过进行交换其中相邻两个数字的操作进行排序（头尾数字算相邻），要将A序列排成从小到大的递增序列最少要进行多少次交换操作？(）{{ select(12) }}

• 5
• 6
• 7
• 2

13. 某算法计算时间表示为递推关系式：T(N)=N+T(N/2)，则该算法时间复杂度为（).{{ select(13) }}

• $O(N^2)$
• $O(NlogN)$
• $O(N)$
• $O(1)$

14. 一棵6结点二叉树的中序遍历为 DBAGECF，先序遍历为 ABDCEGF，后序遍历为（).{{ select(14) }}

• DGBEFAC
• DBEFGCA
• DBGEFCA
• ABCDEFG

15. 三名同学必须从四种不同的选修课中选一种自己想学的课程，共有（ ）种不同的选法。{{ select(15) }}

• 64
• 128
• 12
• 24

二、阅读程序（共12题，每题3分，共计36分）

1.

1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4	string s;
5	char m1,m2;
6	int i ;
7	getline(cin,s);
8	m1 = ' ';
9	m2 = ' ';
10	for(i = 0;i<s.length();i++)
11	{
12		if(s[i]>m1)
13		{
14			m2 = m1;
15			m1 = s[i];
16		}
17		else if(s[i]>m2)
18		{
19			m2 = s[i];
20		}
21	}
22	cout << int(m1)<<" "<<int(m2)<<endl;
23	return 0;
24}

字符	空格	'0'	'A'	'a'
ASCII	32	48	65	97

判断题:

16. 输入的字符串不能包含空格。() {{ select(16) }}

• 正确
• 错误

17. 若输入的字符串只包含小写字母，输出的两个值一定大于等于97。(){{ select(17) }}

• 正确
• 错误

18. 若输入的字符串只包含大小写字母，且输出的第二个值为90，则输入的字符串中有且只有一个小写字母。(){{ select(18) }}

• 正确
• 错误

19. 若输入的字符串只包含数字2，且多于两个字符，则输出的两个值都是50。(){{ select(19) }}

• 正确
• 错误

选择题:

20. 若输入的字符串为"Expo2010 Shanghai China"，则输出的结果是()。{{ select(20) }}

• 120 110
• 120 112
• 110 120
• 112 120

21. 若输入的字符串有3个字符，且都是数字，并且输出的两个值分别是51和50，则输入一共有()种不同的方案。{{ select(21) }}

• 8
• 16
• 15
• 64

2.

01	#include<bits/stdc++.h>
02	using namespace std;
03 	int n, m, result,a[101], b[101];
04	int power (int x, int y)
05	{
06		int i,ret =1;
07		for (i=1;i<=y;++i)
08			ret*=x;
09		return ret;
10	 }
11	int main()
12	{
13		int i=2;
14		cin>>n;
15		while(1 !=n)
16		{
17			if (0==n%i)
18			{
19				++m;
20				a[m]=i;
21				while (0==n%i)
22				{
23					++b[m];
24					n/=i;
25				}
26			}
27			++i;
28		}
29		result=1;
30		for(i=1;i<=m;++i)
31		{
32			result*= (a[i]-1) *power (a[i],b[i]-1);
33		}
34		cout<<result;
35	return 0;
36}

判断题和单选题

判断题

22. 不管输入什么值，程序的输出值一定比输入值大。( ) {{ select(22) }}

• 正确
• 错误

23. 若输入n是一个质数，则输出值result 也可能是一个质数。( ) {{ select(23) }}

• 正确
• 错误

24. 若输入n是一个质数，程序执行到第29行时，i的值等于刚开始输入的n。( ) {{ select(24) }}

• 正确
• 错误

25.若输入n的值等于正整数c的正整数d次方$c^d(c,d>=2)$，程序的第15行循环执行完成后，m的值为1，a[1]的值为c。( ){{ select(25) }}

• 正确
• 错误

选择题

26. 若输入n=2400，则输出 result 为( ){{ select(26) }}

• 640
• 1200
• 2400
• 960

27. 若输出 result=2400，则输入n可能为( )。{{ select(27) }}

• 3200
• 9000
• 6400
• 7200

三、完善程序（第32，33题每题4分，第28、29、30、31、34、35题每题5分，共34分）

(1) 田忌赛马，田忌每赢一次齐王的马就得200 金币，当然输了就扣 200 金币,平局则金币数 不变。 试补全程序。

01 	#include<bits/stdc++.h>
02 	using namespace std; 
03 	int main() {
04 		int n;
05		while (cin>>n&&n!=0) {
06			int tj[1001], king[1001], count =0;
07			int tj_min=0, tj_max=n-1;
08			int king_min=0, king_max=n-1;
09			for (int i=0;i<n;i++)  cin>>tj[i];
10			for (int i=0;i<n;i++)  cin>>king[i];
11			sort (tj,tj+n);
12			sort (king, king+n) ;
13			while (n--){
14				if(tj[  (1)  ]>king[  (2)  ]{
15					count++;
16					tj_max--;
17					king_max--;
18				}
19				else if (tj[  (3)  ]<king[  (4)  ]){
20					count--;
21					tj_min++;
22					king_max--;
23				}
24				else
25				{
26					if (tj[tj_min]>king[king_min]) {
27						count++;
28						(   (5)   );
29						(   (6)   );
30					}
31					else{
32						if(  (7)   )
33							count--;
34						tj_min++;
35						(   (8)   );
36					}
37				}
38			}
39			cout <<count *200 <<endl;
40		}
41		return 0;
42 	}

28. ①处和②处填( ) {{ select(28) }}

• tj_max 和 king_max
• tj_min 和king_max
• tj_min 和king_min
• tj_max 和king_ min

29. ③处和④处填( ) {{ select(29) }}

• tj_min和 king_max
• tj_min 和king_min
• tj_ max和 king_max
• tj_max 和king_min

30. ⑤处和⑥处填( ) {{ select(30) }}

• tj_min--和king_ min++
• tj_max++和king_min++
• tj_min++和king_min++
• tj_max++和king_min--

31.⑦处填( )。 {{ select(31) }}

• tj[ tj_min] <king[ king_max]
• tj[tj_min] >king[ king_ max]
• tj[ tj_ max] <king[ king_max]
• tj[ tj_min] >king[ king_ min]

32. ⑧处填( )。 {{ select(32) }}

• king_max--
• king_max++
• king_min--
• king_min++

(2) （序列问题）给定序列 an，求有多少对 (i,j) 满足 ai<aj。测试数据满足$n≤10^6，ai≤10^9$。

提示：对于任意的 ai≠ aj，可以发现 (i,j) 或 (j,i) 能对答案产生 1 的贡献，因此我们只需要用总的对数减去 ai=aj 的 (i,j) 数量，就能得到答案。

试补全程序。

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int Maxn = ①;
04 int n, a[Maxn];
05 long long s[Maxn], ans; 
06 bool check(int l, int r) { 
07     if (s[r] - s[l - 1] == ②) return true; 
08     return false; 
09 } 
10
11
12 
13 int main() { 
14     cin >> n; 
15     for (int i = 1; i <= n; i ++)  
16         cin >> a[i]; 
17      sort (a + 1, a + n + 1); 
18     for (int i = 1; i <= n; i ++)  
19         s[i] = s[i - 1] + a[i]; 
20     ans = ③; 
21     for (int i = 1; i <= n;) { 
22         int l = i, r = n, pos = n; 
23         while (④) { 
24             int mid = (l + r) >> 1; 
25             if(check(l, mid))  
26                 l = mid + 1, pos = mid; 
27             else  
28                 r = mid - 1; 
29         }  
30         ans -= ⑤;  
31         i = pos + 1; 
32     }  
33     cout << ans; 
34 }

33. ① 处应填（ ）。{{ select(33) }}

• 1e6 + 7
• 1000000
• 1e6
• 1000000000000

34. ② 处应填（ ）。{{ select(34) }}

• (r - l + 1) * a[l]
• s[r] - s[l - 1]
• 1LL * (r–l+1) * a[l]
• a[1] = 0

35. ③ 处应填（ ）。{{ select(35) }}

• n * (n + 1) / 2
• 1ll * n * (n + 1) / 2
• n * (n - 1) / 2
• 1ll * n * (n - 1) / 2

36. ④处应填（）。{{ select(36) }}

• l < r
• l <= r + 1
• l <= r
• l > r

37. ⑤处应填（）。{{ select(37) }}

• (pos -l + 1) * (pos -l) / 2
• 1ll * (pos -l + 1) * (pos -l) / 2
• (pos -i + 1) * (pos -i) / 2
• 1ll * (pos -i + 1) * (pos -i) / 2