​（​普及组​ C++ 语言​两小时完成）

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

1、 以下设备断电之后仍能保存数据的是（） {{ select(1) }}

• 硬盘
• 寄存器
• 显存
• 内存

2、 下列哪个不是CPU（中央处理单元）（） {{ select(2) }}

• Intel Itanium
• AMD Opteron
• DDR SDRAM
• IBM Power 5

3、在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。 {{ select(3) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

4、十进制小数125.125对应的8进制数是（） {{ select(4) }}

• 100.1
• 175.175
• 175.1
• 100.175

5、已知大写字母A的ASCII编码为65，则大写字母J的10进制ASCII编码为（）

{{ select(5) }}

• 71
• 72
• 73
• 都不是

6、在一个无向图中,如果任意两点之间都存在路径相连,则称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图,至少要删去其中的()条边

{{ select(6) }}

• 1
• 2
• 3
• 4

7、设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（ ）个顶点。

{{ select(7) }}

• 10
• 12
• 8
• 16

8、元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是（ ）。

{{ select(8) }}

• R1
• R2
• R4
• R5

9、以下关于字符串的判定语句中正确的是（ ）。 {{ select(9) }}

• 字符串是一种特殊的线性表
• 串的长度必须大于0
• 字符串不可以用数组来表示
• 空格字符组成的就是空串

10、散列表的地址区间为 0-10,散列函数为 H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将关键字序列 26，25，72，38，8，18，59 存储到散列表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素 59 存放在散列表中的可能地址是（） {{ select(10) }}

• 5
• 7
• 9
• 10

11、将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。 {{ select(11) }}

• 4
• 5
• 6
• 7

12、二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查找树的（ ）是一个有序序列。 {{ select(12) }}

• 先序遍历
• 中序遍历
• 后序遍历
• 宽度优先遍历

13、已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ） {{ select(13) }}

• 3 2 1 4 6 5
• 3 2 1 5 4 6
• 2 3 1 5 4 6
• 2 3 1 4 6 5

14、表达式17^3&6计算结果() {{ select(14) }}

• 2
• 19
• 17
• 9

15、 表达式a*(b+c)-d的后缀表达式是（） {{ select(15) }}

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

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

1、

1 #include <iostream>

2 #include <string>

3 using namespace std;

4 int main(){

5 int len, maxlen;

6 string s, ss;

7 maxlen = 0;

8 do{

9   cin >> ss;

10   len = ss.length();

11   if (ss[0] == '#')

12     break;

13  if (len > maxlen){

14       s = ss;

15       maxlen = len;

16     }

17 } while (true);

18 cout << s << endl;

19 return 0;

}

判断题

1、do…while可以换成while(true)，效果相同（）

{{ select(16) }}

• √
• ×

2、 第10行的ss.length()可以换成strlen(ss)（）

{{ select(17) }}

• √
• ×

3、 若将第13行len>maxlen换成len>=maxlen效果相同（）

{{ select(18) }}

• √
• ×

4、 若程序不输入#,程序将不会结束（）

{{ select(19) }}

• √
• ×

选择题

5、 若输入数据

I
am
a
citizen
of
China
#

那么输出的结果为（）

{{ select(20) }}

• China
• citizen
• I
• I am a citizen of China

6、基于第5题的输入，若将18行改为输出 maxlen，那么输出结果为（）

{{ select(21) }}

• 5
• 7
• 2
• 12

2、

1 #include <iostream>

2 using namespace std;

3 int main(){

4 string s;

5 cin >> s;

6 for(int i = 0; i < s.length(); i++){

7  if (isdigit(s[i])) continue;

8  else

9   if( i&1) s[i] |= 32;

10 }

11 cout << s << endl;

12 return 0;

}

判断题

1、 s.length()放在循环里比放外面更慢（）

{{ select(22) }}

• √
• ×

2、 如果是数字字符将不会被处理（）

{{ select(23) }}

• √
• ×

3、 大写字母将会变成小写字母（）

{{ select(24) }}

• √
• ×

4、 第9行i&1可以替换成i%2 （）

{{ select(25) }}

• √
• ×

选择题

5、若输入数据2020CSP Will Coming，那么输出的结果为（） {{ select(26) }}

• 2020
• 2020CsP
• 2020CsP Will coming
• 2020CsP will Coming

6、若输入数据 I am 18，那么输出结果为（）

{{ select(27) }}

• I
• i
• I am 18
• i am 18

3、

1 #include <iostream>

2 using namespace std;

3 int ans = 0;

4 int func(int m,int n, int q){

5 if( q == m%n || n == 1)

6  return 1;

7 for(int i = 1;i <= m/n;i++)

8  ans += func(m-i,n-i,q);

9 return ans;

10 }

11 int main(){

12  int a,b,c;

13 cin >> a >> b >> c;

14 cout << func(a,b,c) << endl;

15 return 0;

}

判断题

1、程序不会出现参数n等于0的情况（） {{ select(28) }}

• √
• ×

2、若将第5行 m%n==q的结束条件去除,递归次数可能会增加很多（）

{{ select(29) }}

• √
• ×

3、若m是n的倍数，程序递归次数会比非倍数关系少（）

{{ select(30) }}

• √
• ×

4、func(a,b,c)的参数顺序调整会影响递归次数（）

{{ select(31) }}

• √
• ×

选择题

5、若输入11 5 1，那么结果为（）。

{{ select(32) }}

• 11
• 5
• 1
• 17

6、若输入11 5 0，那么结果为（）。

{{ select(33) }}

• 5
• 11
• 16
• 1

四、完善程序

1、木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定了的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是 cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

输入:第一行是两个正整数 N 和 K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N 是原木的数目，K 是需要得到的小段的数目。 接下来的 N 行，每行有一个 1 到 10000 之间的正整数，表示一根原木的长度。

输出:输出能够切割得到的小段的最大长度。如果连 1cm 长的小段都切不出来，输出”0”。

输入样例:

3 7
232
124
456

输出样例:

114

程序

1）①处应填（）

{{ select(34) }}

• len[i]
• num + len[i]
• num+len[i]/t
• len[i]/t

2. ②处应填（）

{{ select(35) }}

• num
• num>=k
• num < k
• num <= t

3. ③处应填（）

{{ select(36) }}

• left--
• left = 0
• left = 1
• left++

4. ④处应填（）

{{ select(37) }}

• left
• mid
• left+1
• left++

5. ⑤处应填（）

{{ select(38) }}

• isok(left)
• !isok(mid)
• isok(mid)
• !isok(left)

2、（最短路径问题）无向连通图 G 有 n 个结点，依次编号为 0,1,2,...,(n-1)。用邻接矩阵的形式给出每条边的边长，要求输出以结点 0 为起点出发，到各结点的最短路径长度。 使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值；不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）

1）①处应填（）

{{ select(39) }}

• v = 0
• v = -1
• dist[0]=0
• used[0] = 1

2. ②处应填（）

{{ select(40) }}

• dist[v]> dist[i]
• dist[v]>=dist[i]
• dist[v]< dist[i]
• dist[v]<= dist[i]

3. ③处应填（）

{{ select(41) }}

• i = v
• v = 0
• v = i
• v++

4. ④处应填（）

{{ select(42) }}

• used[v]=1
• used[v]=0
• dist[v] = 0
• dist[v]=1

5. ⑤处应填（）

{{ select(43) }}

• dist[v]+w[v][i] < dist[i]
• dist[v]+w[v][i] > dist[i]
• dist[v] < dist[i]+w[v][i]
• dist[v] > dist[i]+w[v][i]