一、单项选择题

1. $(1047)_8=$
   {{ select(1) }}

• 1
• 10
• 100
• 1000

2. 若逻辑变量 A、C为真，B、D为假，以下逻辑表达式的值为假的是
   {{ select(2) }}

• $(B\vee C\vee D)\vee D\wedge A$
• $((\neg A\wedge B)\vee C)\wedge\neg B$
• $(A\wedge B)\vee\neg(C\wedge D\vee\neg A)$
• $A\wedge(D\vee\neg C)\wedge B$

3. 小恺编写了如下函数，希望计算斐波那契数列 f(n)第 n项对 10000取余数的值：

int f(int x){
    if(x<=2)
        return 1;
    int ans = f(x-1) + f(x-2);
    ans %= 10000;
}

在运行空间限制 128MB、栈空间不超过空间限制、运行时限 1秒的情况下,在主函数中运行函数 f(12345),则最有可能首先发生什么问题?
{{ select(3) }}

• 运行时间超时
• 栈溢出
• 访问无效内存
• 返回错误的答案

4. 表达式 a+b*(c-d)/e-f的后缀表达式为
   {{ select(4) }}

• -+a/*b-c-cdef
• abcd-*e/+f-
• +ab*-cd/e-f
• f-e/d-d*b+a

5. 某个 MV是一段时长 4分整的视频文件。它每秒播放 10帧图像,每帧图像是一幅分辨率为 $2048\times 1152$ 像素(长宽比 16:9)的 32位真彩色图像，其画面没有被压缩。这个视频没有音频。这个视频文件大约需要占用多大的存储空间?
   {{ select(5) }}

• 21 GiB
• 27 GiB
• 168 GiB
• 2 GiB

6. 下图是一棵二叉树，它的后序遍历是

{{ select(6) }}

• ABDEFC
• DBEFAC
• DFEBCA
• ABCDEF

8. 五个本质不同的点在没有重边或者自环的情况下，组成不同的无向图的个数是?
   {{ select(7) }}

• 10
• 1024
• 15
• 120

9. 设元素 a,b,c,d,e,f依次入栈,则下列不合法的出栈序列为?
   {{ select(8) }}

• d,c,b,e,f,a
• f,e,d,c,b,a
• c,d,f,e,b,a
• e,d,b,a,f,c

10. 同时扔出3枚完全相同的六面骰骰子,每个骰骰子上有1到6的数字。将得到的点数排序后，有多少种不同的结果?
    {{ select(9) }}

• 208
• 56
• 216
• 120

11. 在编程时(使用任一种高级语言,不一定是C++),如果需要从磁盘文件中输入一个很大的二维数组(例如 1000*1000的 double型数组),按行读(即外层循环是关于行的)与按列读(即外层循环是关于列的)相比,在输入效率上
    {{ select(10) }}

• 没有区别
• 按行读的方式更高
• 按列读的方式更高
• 取决于数组的存储方式

12. 不考虑稳定性，下列排序方法中平均时间复杂度最大的是
    {{ select(11) }}

• 插入排序
• 希尔排序
• 归并排序
• 快速排序

13. 将数组12,23,-1,19,117,-103,79,602中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换几次
    {{ select(12) }}

• 4
• 5
• 6
• 7

14. 3名男生和3名女生围成一个圈,男生和男生不相邻,女生和女生不相邻。如果两个围成的圈经过旋转可以重合,则视为同一种方案。一共有几种方案?
    {{ select(13) }}

• 18
• 15
• 12
• 9

15. 以下关于 C++字符串的说法,错误的是
    {{ select(14) }}

• 定义 string类型的字符串时,不需要预先确定它的最大长度
• 字符数组和 string类型的字符串是可以相互转化的
• 定义字符数组 char a[100]时并从键盘读入字符串,则读入的字符串长度不能超过 99
• 定义一个字符串 string s后,获得它长度的方式就是 strlen(s)

16. 中国计算机学会成立于哪年
    {{ select(15) }}

• 1961
• 1962
• 1971
• 1972

二、阅读程序

程序1

1 #include<iostream>
2 using namespace std;
3 const int MAXN= 1000050;
4 int n, a[MAXN], a1[MAXN], b[MAXN], lim;
5 void solve1(){
6     for(int i=1; i<=n; i++ )
7         b[a[i]]++;//①
8     for(int i= 1; i<= lim; i++){
9         if(b[i])//②
10             cout<< i<<"";
11     }
12     cout<< endl;
13 }
14 void solve2(){
15     int cnt= 0, flag;
16     for(int i=1; i<=n; i++ ){
17         flag= false;
18         for(int j=1; j<=n-1; j++ ){
19             if (a[j]>a[j+1]){
20                 swap(a[j], a[j+ 1]);
21                 cnt++;
22                 flag= true;
23             }
24         }
25         //if(flag==false)
26         // break;
27     }
28     for(int i= 1; i<= n; i++)
29         cout<< a[i]<<"";
30     cout<< endl;
31 }
32 int main(){
33     cin>> n;
34     for(int i= 1; i<= n; i++){
35         cin>>a[i];
36         a1[i]=a[i];//③
37         lim=max(a[i],lim);//④
38     }
39     solve1();
40     for(int i=1; i<=n; i++ )
41         a[i]=a1[i];
42     solve2();
43     return 0;
44 }

判断题：

1. solve2函数实现了选择排序。
   {{ select(16) }}

• √
• ×

2. solve1函数的时间复杂度为 $O(n+V)$ ,其中 V指的是 $a_i$ 的最大值。
   {{ select(17) }}

• √
• ×

3. 当输入数据为: 72357146时, solve2函数中的变量 cnt最终值为 9。
   {{ select(18) }}

• √
• ×

4. 若将 solve2函数中的双斜杠全部移除,不会影响输出结果。
   {{ select(19) }}

• √
• ×

单选题：
5. 下列哪组数据,会使得 solve1函数与solve2函数的输出结果不同? (假设已经输入了 n=8)
{{ select(20) }}

• 1 10 100 1000 10000 888 8888 88888
• 6321 158987 16305684865055684715650515610
• 777 888999888777888999666
• 999993 999994 999995 999996 999997 999998 999999 1000000

6. 若要使得solve1和solve2函数的输出结果相同，则应当修改程序中的哪一处?
   {{ select(21) }}

• ①
• ②
• ③
• ④

程序2

1 #include<cstdio>
2 #include<cstring>
3 
4 const int maxn= 1003;
5 
6 int type, n, m;
7 char s[maxn], t[maxn];
8 
9 int main(){
10     scanf("%d%s%s",&type, t, s);
11     n= strlen(s); m= strlen(t);
12     if(type< 2){
13         for(int i=0; i<m;++i) s[i]=t[i];
14     } else if(type== 2){
15         strcpy(s, t);
16     } else{
17         for(int i=0; i<m ; i+=4 ){
18             unsigned int code=0, pos= i;
19             for(int j=1; pos< i+4; j*=100,++pos){
20                 if(pos== m) break;
21                 code+= t[pos]* j;
22             }
23             pos=i;
24             while(code!= 0){
25                 s[pos++]= code% 100;
26                 code/= 100;
27             }
28         }
29     }
30     for(int i=0; i<n;++i) printf("%c", s[i]);
31     printf("\n");
32 }

判断题：

1. 将程序中所有的比较运算符小于号(<)改为不等于号(!=),则程序对所有符合要求的输入的输出结果不变。
   {{ select(22) }}

• √
• ×

2. 当输入为 1 xyz abcd时,程序的输出为 xyzd。
   {{ select(23) }}

• √
• ×

3. 程序在输入为 1 xyz abcd时的输出与输入为 2 xyz abcd的输出相同。
   {{ select(24) }}

• √
• ×

4. 将程序第 25~28行的 while循环替换为 do-while循环(判断条件和循环体不变),则程序对同一合法输入的输出结果一定不变。
   {{ select(25) }}

• √
• ×

单选题：
5. (2分)若将程序第 13行改为 for(int i=0; i<strlen(t);++i) s[i]=t[i];,且已知输入的 type一定为 1的情况下,用n表示 s的长度, m表示 t的长度,则程序的时间复杂度为
{{ select(26) }}

• $\Theta(n+m)$
• $\Theta\left(n+m^2\right)$
• $\Theta\left(n^2+m\right)$
• $\Theta\left(n^2+m^2\right)$

6. 给程序分别输入选项()的两组输入数据,得到的输出不同
   {{ select(27) }}

• 1 ab abc和 3 ab abc
• 1 AB ABC和 3 AB ABC
• 1 de fgh和 3 de fgh
• 1 DE FGH和 3DE FGH

程序3

1 #include<iostream>
2 using namespace std;
3 
4 const int INF= 1000000000;
5 #define Front 0
6 #define Back 1
7 #define Left 2
8 #define Right 3
9 #define Up 4
10 #define Down 5
11 int w[6], a[1003][1003];
12 const int way1[]={Up, Right, Down, Left};
13 const int way2[]={Up, Front, Down, Back};
14 const int way3[]={Left, Front, Right, Back};
15 int get_max(int&a, int b){
16     return a= max(a, b);
17 }
18 int right_rotate(int&u){
19     for(int i=0; i<4;++i)
20         if( u== way1[i])
21             return u= way1[(i+1) % 4];
22     return u;
23 }
24 int front_rotate(int&u){
25     for(int i=0; i< 4;++ i)
26         if( u== way2[i])
27             return u= way2[(i+ 1)% 4];
28     return u;
29 }
30 const int anchorX= Up;
31 const int anchorY= Front;
32 const int anchorZ= Right;
33 int find_down(int u, int v){
34     if(u== Down|| u== Up) return anchorX^(u== Up);
35     if(v== Down|| v== Up) return anchorY^(v== Up);
36     for(int i= 0; i< 4;++ i)
37         if( u== way3[i])
38             return anchorZ ^(v== way3[(i+1)% 4]);
39     return -1;
40 }
41 int n,m, dp[1003][1003][6][6];
42 int main(){
43     cin>> n>> m;
44     for(int i=0; i<n;++ i)
45         for(int j=0; j<m ;++ j)
46             cin>> a[i][j];
47     for(int i=0; i<6;++ i)
48         cin>> w[i];
49     for(int i=0; i<n;++i)
50         for(int j= 0; j< m;++ j)
51             for(int a=0; a<6;++ a)
52                 for(int b=0; b<6;++b)
53                     dp[i][j][a][b]=-INF;
54     dp[0][0][anchorX][anchorY] = a[0][0]* w[Down];
55     for(int i=0; i<n;++i)
56         for(int j=0; j<m;++j)
57             for(int p=0; p<6;++p)
58                 for(int q=0; q<6;++q)
59                     if (dp[i][j][p][q]!=-INF){
60                         int x= dp[i][j][p][q];
61                         int u1= p, v1= q;
62                         right_rotate(u1);
63                         right_rotate(v1);
64                         get_max(dp[i][j+1][u1][v1], x+ w[find_down(u1, v1)]* a[i][j+1]);
65                         int u2= p, v2= q;
66                         front_rotate(u2);
67                         front_rotate(v2);
68                         get_max(dp[i+1][j][u2][v2], x+ w[find_down(u2, v2)]* a[i+1][j]);
69                     }
70     int ans=-INF;
71     for(int p=0; p<6;++ p)
72         for(int q=0; q<6;++ q)
73             ans= max(ans, dp[n- 1][m- 1][p][q]);
74     printf("%d\n", ans);
75     return 0;
76 }

判断题：

1. 存在一种合法的输入数据,使得运行程序时,某次 find_down函数的返回值是-1
   {{ select(28) }}

• √
• ×

2. 该程序的时间复杂度为 $\Theta\left(n^2 m^2\right)$
   {{ select(29) }}

• √
• ×

3. 对于任意 $u\in[0,6)$ ,「先执行 front_rotate(u),再执行right_rotate(u)」,与「先执行 right_rotate(u),再执行front_rotate(u)」,最终 u的值相同
   {{ select(30) }}

• √
• ×

单选题：
4. 将 anchorX、anchorY、anchorZ依次更换为()时,对于全部合法数据，与改变之前的输出结果无异
{{ select(31) }}

• Left、 Front、 Down
• Left、Up、Front
• Left、Down、Back
• Down、Right、Front

5. (2分)对于以下的输入数据,输出结果为
   输入：

5 5
2 8 15 1 10
5 19 1 9 35
6 6 2 8 2
12 16 3 8 17
12 5 3 14 13
1 1 1 1 1

{{ select(32) }}

• 95
• 97
• 94
• 103

6. (2分)对于以下的输入数据，输出结果为
   输入：

2 5
2 8 15 3 1
5 19 19 3 5

{{ select(33) }}

• 194
• 157
• 193
• 201

三、完善程序

程序1（支付问题）

1 #include<iostream>
2 
3 using namespace std;
4 
5 const int MAXN= 210;
6 const int MAXM= 5010;
7 int n,m;
8 int f[MAXM], a[MAXN];
9 
10 int main(){
11     cin>> n;
12     for(int i=1; i<=n; i++ ){
13         cin>> a[i];
14         ①;
15     }
16 
17     ②;
18     for(int i= 1; i<= n; i++)
19         for(int j= m; j>= a[i]; j--)
20             f[j] = ④;
21     int ans= 0;
22     for(int i= 1; i<= m; i++)
23         if(⑤) ans++;
24     cout<< ans;
25     return 0;
26 }

1. ①处应填
   {{ select(34) }}

• n+= a[i]
• m+=a[i]
• n=a[i]
• m=a[i]

2. ②处应填
   {{ select(35) }}

• f[0]=1
• f[1]=1
• a[0]=1
• a[1]=1

3. ③处应填
   {{ select(36) }}

• for(int j=a[i]; j<=n; j++)
• for(int j=n; j>=a[i]; j--)
• for(int j=a[i]; j<=m; j++)
• for(int j=m; j>=a[i]; j--)

4. ④处应填
   {{ select(37) }}

• f[j-1]+1
• f[j-a[i]]+1
• f[j]|| f[j-a[i]]
• f[j]&& f[j-a[i]]

5. ⑤处应填
   {{ select(38) }}

• f[i]
• f[i-1]
• f[i]== f[i+1]
• f[i]== f[i-1]

程序2（凑出17）

1 #include<cstdio>
2 
3 using namespace std;
4 
5 const int maxn= 25;
6 const int aim=17;
7 
8 int n;
9 int a[maxn];
10 bool ans;
11 
12 int getBit(const int s, int p){
13     return①;
14 }
15 
16 int main(){
17     scanf("%d",&n);
18     for(②) scanf("%d", a+ i);
19     for(int s=0, upperBound=③; s<= upperBound; ++s){
20         ④;
21         for(int j=0; j<n;++j) if(getBit(s, j)== 1){
22             sum += a[j];
23         } else{
24             ⑤;
25         }
26         if(int(sum)== aim){
27             ans= true;
28             break;
29         }
30     }
31     printf("%s\n", ans?"Yes":"No");
32 }

1. ①处应填
   {{ select(39) }}

• (s>> p)& 1
• (s<< p)& 1
• s&(1<< p)& 1
• s&(1>> p)& 1

2. ②处应填
   {{ select(40) }}

• int i=0;i<=n;++i
• int i=1; i<=n;++i
• int i=0; i< n;++i
• int i=1; i<n;++i

3. ③处应填
   {{ select(41) }}

• 1<<n
• (1<< n)|1
• (1<< n)+1
• (1<< n)-1

4. ④处应填
   {{ select(42) }}

• int sum= 0
• unsigned long long sum= 0
• unsigned short sum= 0
• unsigned int sum=0

5. ⑤处应填
   {{ select(43) }}

• sum= a[j]+ sum
• sum= a[j]- sum
• sum=-a[j]+ sum
• sum=-a[j]- sum