一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 16 进制下的 A.2，相当于 8 进制下的（ ） {{ select(1) }}

• 10.9
• 11.2
• 12.1
• 13.4

2. 已知字符’B’的 ASCII 码为十进制下的 66，十进制减法表达式：’A’-80，其结果在内存中的 8 位补码形式为（ ） {{ select(2) }}

• 11110001
• 11100001
• 11001101
• 11110011

3. 假设当前网速为 80000bit/秒，要下载一个 50KB 的文件大概需要多久（ ）？{{ select(3) }}

• 5 分钟
• 1 秒
• 5 秒
• 50 秒

4. 若逻辑变量 A、C 为真，B、D 为假，以下逻辑运算表达式为真的有（ ）。{{ select(4) }}

• (A ∧ B) ∨ (C ∧ D ∨ ¬A)
• (B ∨ C ∨D) ∨D ∧ A
• A ∧ (D ∨ ¬C) ∧ B
• (D ∨ ¬C) ∧¬B∧¬C

5. 表达式 a*(b+c)-d 的后缀表达形式为（ ）。{{ select(5) }}

• abcd*+-
• abc+*d-
• abc*+d-
• -+*abcd

6. 栈的插入和删除操作在（ ）。{{ select(6) }}

• 栈底
• 栈顶
• 任意位置
• 指定位置

7. 若对 n 个元素进行直接插入排序，在进行任意一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（ ）{{ select(7) }}

• O(1)
• O(n)
• O($n^2$)
• O(logn)

8. 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，12 个顶点的二分图至多有（ ）条边。{{ select(8) }}

• 18
• 24
• 36
• 66

9. 线性表的顺序存储结构是一种（ ）的存储结构。{{ select(9) }}

• 随机存取
• 顺序存取
• 索引存取
• 散列存取

10. 用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。{{ select(10) }}

• 栈
• 队列
• 树
• 图

11. 非空二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定满足( )。{{ select(11) }}

• 所有结点均无左孩子
• 所有的结点均无右孩子
• 只有一个叶子结点
• 是任意一棵二叉树

12. 一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人( ) {{ select(12) }}

• 3
• 13
• 33
• 23

13. 将 3 个不同的小球放入 4 个盒子中，则不同放法种数有（ ）{{ select(13) }}

• 81
• 64
• 12
• 14

14. 下列选项中，不是下图深度优先搜索序列的是( ) {{ select(14) }}

• V1, V5, V4, V3, V2

• V1, V3, V2, V5, V4

• V1, V2, V5, V4, V3

• V1, V2, V3, V4, V5

  

15. 以下程序段实现了找第二小元素的算法。输入是 n 个不等的数构成的数组 S，输出S 中 第二小的数 SecondMin。在最坏情况下，该算法需要做（ ）次比较 {{ select(15) }}

    1   if (S[1] < S[2]) {
    2       FirstMin = S[1];
    3       SecondMin = S[2];
    4   } else {
    5       FirstMin = S[2];
    6       SecondMin = S[1];
    7   }
    8   for (i = 3; i <= n; i++)
    9       if (S[i] < SecondMin)
    10   if (S[i] < FirstMin) {
    11      SecondMin = FirstMin;
    12      FirstMin = S[i];
    13   } else {
    14      SecondMin = S[i];
    15   }
    

• 2n
• n-1
• 2n-3
• 2

二、阅读程序（程序输入不超过数组或字符串定义的范围；无特殊说明判断题 2 分，除31题外选择题 3 分，31题4分，共计 40 分） 1.

1 #include <iostream>
2 #include <string>
3 using namespace std;
4 int main(){
5 string map = "22233344455566677778889999";
6 string tel;
7 int i;
8 cin>>tel;
9 for (i = 0; i < tel.length(); i++)
10      if ((tel[i] >= '0') && (tel[i] <= '9'))
11          cout<<tel[i];
12      else if ((tel[i] >= 'A') && (tel[i] <= 'Z'))
13          cout<<map[tel[i] - 'A'];
14 cout<<endl;
15 return 0;
16 }

判断题

16. 若输入字符串 I have a dream 该程序能正常运行( ) {{ select(16) }}

• 正确
• 错误

17. 如果输入字符串内包含数字字符，则该程序不能正常运行( ) {{ select(17) }}

• 正确
• 错误

选择题

18. 输入 AABCCD 输出为（ ） {{ select(18) }}

• 222233
• 222223
• 223333
• 233333

19. 输入 ABBCCCDDF 输出为（ ） {{ select(19) }}

• 222223333
• 222222333
• 222333333
• 223333333

20. 若将代码 if((tel[i] >= '0') && (tel[i] <= '9'))改为 {{ select(20) }} if((tel[i] >= 'a') && (tel[i] <= 'z'))之后，输入 ABCDDFFFabcd， 输出为（ ）

• abcd
• ABCDDFFF2223
• 222333332223
• 22233333abcd

01 #include<iostream>
02 #include<cstring>
03 using namespace std;
04 char s[10000];
05 int cnt[26];
06 int main(){
07 cin >> s;
08 for(int i = 0 ; i <strlen(s) ;++i){
09      if(cnt[s[i] - 'a'] <= 50)
10          s[strlen(s)] = s[i];
11      ++cnt[s[i]-'a'];
12 }
   cout<<s;
13 return 0;
14 }

假设设初始时输入的字符串长度不超过 500，且不是空串。

判断题

21. 将第 8 行改为“for(int i=0,len=s.size();i < len;++i)” ，程序的运行结果不会改变，同时程序的运行效率将得到提升（ ） {{ select(21) }}

• 正确
• 错误

22. 对于任意一个出现了 a 到 z 中所有的字符、且各字符出现的次数不小于 50 的字符串 b，总存在一个字符串 a，使得将 a 输入程序后的运行结果为字符串 b。（ ） {{ select(22) }}

• 正确
• 错误

23. 程序的输出字符串长度一定不小于 1300。 {{ select(23) }}

• 正确
• 错误

选择题

24. （5 分）设输入字符串长度为 x（1≤x≤500），输出字符串长度为 y，则关于 x 和 y 的大小关系正确的是（ ）。 {{ select(24) }}

• 对于全部的输入字符串，都有 x=y。
• 对于全部的输入字符串，都有 x < y。
• 存在一部分输入字符串，使得 x=y；也存在一部分输入字符串，使得 x < y；但是不存在 x>y 的情况。
• 存在一部分输入字符串，使得 x=y；也存在一部分输入字符串，使得 x>y；还存在一部分输入字符串，使得 x < y。

25. （3.5 分）设字符串 w 为 ab...z，即从 a 到 z 在 w 中依次出现一次，共 26个字符。若输入为 w 重复出现两次的结果（abcdefg...zabcdefg...z，则输出结果为（ ）。 {{ select(25) }}

• w 重复出现 50 次的结果。
• w 重复出现 51 次的结果。
• w 重复出现 52 次的结果。
• w 重复出现 53 次的结果。

1	#include<bits/stdc++.h>
2	using namespace std;
3	int a[100009],b[100009];
4	int main(){
5		long long n;
6		cin>>n;
7		for(int i=1;i<=n;i++){
8			cin>>a[i];
9		}
10		for(int i=1;i<=n;i++){
11			b[i]=a[i]-a[i-1];
12		}
13		long long sum1=0,sum2=0;
14		for(int i=2;i<=n;i++){
15			if(b[i]<0) sum1=sum1-b[i];
16			else sum2=sum2+b[i];
17		}
18		if(sum1>sum2)cout<<sum1;
19		else cout<<sum2;
20		cout<<"\n";
21		cout<<abs(sum2-sum1)+1; 
22		return 0;
23	}

假设输入的数据约定为:$n≤100000,0≤a_i≤2e9$，试完成下面的判断题和选择题。
判断题

26. 若只将第$10$行中的for(int i=1;i<=n;i++)修改为for(int i=2;i<=n;i++)，输入数据相同的情况下，输出结果不会发生改变。( ) {{ select(26) }}

• 对
• 错

27. 若只将第$14$行中的for(int i=2;i<=n;i++)修改为for(int i=1;i<=n;i++)，输入数据相同的情况下，输出结果不会发生改变。( ) {{ select(27) }}

• 对
• 错

28. 当输入的数据$a_i\le 2e9$时，只将程序中第$13$行sum1、sum2的数据类型修改为int，输入数据相同的情况下，输出结果不会发生改变。( ) {{ select(28) }}

• 对
• 错

29. 若所有$a_i$的值都是大于$0$的，则$b$数组中的最小值不可能为负数。( ) {{ select(29) }}

• 对
• 错

选择题

30. 若只将第$15$行中的 if(b[i]<0) sum1=sum1-b[i]; 替换为( )，可以在输入数据相同时，保证输出结果不变。 {{ select(30) }}

• if(b[i]>=0) sum1=sum1+b[i];
• if(b[i]<0) sum1=sum1+abs(b[i]);
• if(b[i]>=0) sum1=sum1+abs(b[i]);
• if(b[i]<0) sum1=sum1-abs(b[i]);

31. 若输入数据 5 1 2 5 4 3 ，则程序的输出结果是( )。 {{ select(31) }}

• 1
  2
  

• 3
  2
  

• 3
  4
  

• 4
  3
  

三、完善程序（单选题，每小题 3 分，共计 30 分）

1. (翻硬币)：小 X 看到大叔在翻转硬币，每次会将区间$[x, y]$内的硬币翻面。初始时硬币都是反面朝上，经过 $m$次操作后，小 X 想知道有多少枚硬币正面朝上。下面的程序用于统计经过$m$次区间翻转操作后，最终有多少个硬币正面朝上。请根据程序的逻辑，选择合适的选项填写在相应的空格处。$(0<n<=1e6),(0<x,y<n)$,$(m<1e6)$

1	#include <bits/stdc++.h>
2	using namespace std;
3	typedef long long ll;
4	const int N = 1e6+5;
5	int a[N], b[N];
6	int main()
7	{
8	    int n, m;
9	    cin >> n >> m; 
10	    int l, r;
11	    for(int i = 1; i <= m; i++) {
12	        cin >> l >> r;
13	        ____①____
14	        ____②____
15	    }
16	    int res = 0;
17	    for(int i = 1; i <= n; i++) {
18	        ____③____
19	        if(____④____)
20	            ____⑤____
21	    }
22	    cout << res << endl;
23	    return 0;
24	}

32.①处应该填入 ( ) {{ select(32) }}

• b[l+1]++;
• B.b[l]++;
• C.b[l-1]++;
• D.b[l]--;

33.②处应该填入 ( ) {{ select(33) }}

• b[r+1]--;
• b[r]--;
• b[r-1]++;
• b[r]++;

34.③处应该填入 ( ) {{ select(34) }}

• a[i] = a[i+1]+a[i]
• b[i] = b[i+1]+b[i];
• b[i] = b[i - 1] + b[i];
• a[i] = a[i]+b[i];

35.④处应该填入 ( ) {{ select(35) }}

• b[i]%2==0
• b[i]>0
• b[i]%2 !=0
• b[i]>1

36.⑤处应该填入 ( ) {{ select(36) }}

• res--;
• res+=2;
• res-=2;
• res++;

2.(送礼物）:有$n$个朋友互送礼物，每个人送出的钱会平均分给收到礼物的人。我们需要计算每个人送出的钱和收到的钱的差额。每个朋友都有一些钱准备送礼，这些钱将被平均分给他选择的朋友。如果一个人有 $x$ 元钱，并决定送给 $y$ 个朋友，那么每个朋友将得到 $\lfloor x/y \rfloor$ 元，剩余的钱返还给送礼者。我们需要根据每个人送出和收到的钱数，计算他们的净收入。

1	#include<iostream>
2	#include<cstring>
3	using namespace std;
4	struct person{
5	    string name;
6	    int money;
7	}a[12]; 
8	string name_out, name_in;
9	int n, mout, num, sum;
10	int main(){
11	    cin >> n;
12	    for(int i = 1; i <= n; i++) cin >> a[i].name;  
13	    for(int i = 1; i <= n; i++){
14	        cin >> name_out >> ___①____ >> num;  
15	        if(___②____) continue; 
16
17			int flag = 1;
18  		for(int j = 1; j <= num; j++){
19            	cin >> name_in; 
20            	for(int k = 1; k <= n; k++){
21                	if(flag && ___③___) flag--, a[k].money -= mout / num * num; 
22	
23	                if(___④___) a[k].money += ___⑤____; 
24	            }
25	        }
26	    }
27	    for(int i = 1; i <= n; i++) cout << a[i].name << " " << a[i].money << endl; 
28	}

37. ①处应该填入 ( ) {{ select(37) }}

• mout
• sum
• num
• n

38. ②处应该填入 ( ) {{ select(38) }}

• !num || !mout
• num == 0 && mout == 0
• sum == 0 || mout == 0
• !num && !mout

39. ③处应该填入 ( ) {{ select(39) }}

• a[k].name == name_in
• a[k].name == name_out
• flag
• a[k].money > 0

40. ④处应该填入 ( ) {{ select(40) }}

• a[k].name == name_out
• a[k].name == name_in
• flag
• name_out != name_in

41. ⑤处应该填入 ( ) {{ select(41) }}

• mout / num
• num / mout
• mout * num
• num - mout