C＋CSP_J_试题集之2020年初赛题

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

1.在内存器中每个存储单元都被赋予一个唯一的序号，称为（ 　）。

A. 下标

B. 地址

C. 序号

D. 编号

2.编译器的主要功能是（　  ）。

A. 将源程序翻译成机器指令代码

B. 将一种高级语言翻译成另一种高级语言

C. 将源程序重新组合

D. 将低级语言翻译成高级语言

3.设x=true，y=true，z=false，以下逻辑运算表达式值为真的是（ 　）。

A.(x∧y)∧z

B.x∧(z∨y)∧z

C.(x∧y)∨(z∨x)

D.(y∨z)∧x∧z

4.现有一张分辨率为2048×1024像素的32位真彩色图像。请问要存储这张图像，需要多大的存储空间？（　 ）

A.4MB

B.8MB

C.32MB

D.16MB

5.冒泡排序算法的伪代码如下：

对n个数用以上冒泡排序算法进行排序，最少需要比较多少次？（　 ）

A. n

B.n-2

C. n2

D.n-1

冒泡排序比较次数最少的情况：原本所有数字的顺序就是对的，一趟比较结束，所以是比较 n-1 次。

6.设A是n个实数的数组，考虑下面的递归算法：

请问算法XYZ的输出是什么？（　）

A. A数组的平均值

B. A数组的最小值

C. A数组的最大值

D. A数组的中值

7.链表不具有的特点是（　 ）。

A. 插入和删除不需要移动元素

B. 可随机访问任一元素

C. 不必事先估计存储空间

D. 所需空间与线性表长度成正比

8.有10个项点的无向图至少应该有（　 ）条边才能确保是一个连通图。

A.10

B.12

C. 9

D.11

n个顶点的无向图，至少需要n-1条边，才能连通。

9.二进制数1011转换成十进制数是（ 　）。

A.10

B.13

C.11

D.12

10.五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（　）种不同排列方法。

A.24

B.36

C.72

D.48

11.下图中所使用的数据结构是（ 　）。

A.    哈希表

B. 二叉树

C. 栈

D. 队列

12.独根树的高度为1。具有61个节点的完全二叉树的高度为（　）。

A. 7

B. 5

C. 8

D. 6

13.干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。

天干=（公历年份）除以10所得余数

地支=（公历年份）除以12所得余数

例如，今年是2020年，2020除以10余数为0，查表为“庚”；2020除以12，余数为4，查表为“子”，所以今年是庚子年。

请问1949年的天干地支是（ 　）。

A. 己亥

B. 己丑

C. 己卯

D. 己酉

14.10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有（　）种不同的分配方案。

A.56

B.84

C.72

D.504

15.有五副不同颜色的手套（共10只手套，每副手套左右手各1只），一次性从中取6只手套，请问恰好能配成两副手套的不同取法有（　）种。

A.30

B.150

C.180

D.120

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

1.

·判断题

1）输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。（　）

2）若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。（　）

3）将第12行的“i

4）将第26行的“i

·单选题

5）若输出的字符串为“ABCABCABCA”，则下列说法正确的是（　）。

A. 输入的字符串中既有A又有P

B. 输入的字符串中既有S又有B

C. 输入的字符串中既有S又有P

D. 输入的字符串中既有A又有B

6）若输出的字符串为“CSPCSPCSPCSP”，则下列说法正确的是（　）。

A. 输入的字符串中既有J又有R

B. 输入的字符串中既有P又有K

C. 输入的字符串中既有J又有K

D. 输入的字符串中既有P又有R

2.

假设输入的n是不超过262的正整数，k都是不超过10000的正整数，完成下面的判断题和单选题。

·判断题

1）若k=1，则输出ans时，len=n。（　）

2）若k>1，则输出ans时，len一定小于n。（　）

3）若k>1，则输出ans时，klen一定大于n。（　）

·单选题

4）若输入的n等于1015，输入的k为1，则输出等于（　）。

A. (1030-1015)/2

B. (1030+1015)/2

C. 1

D. 1015

5）若输入的n等于205,891,132,094,649（即330），输入的k为3，则输出等于（　）。

A. (330-1)/2

B. 330

C. 330-1

D. (330+1)/2

6）若输入的n等于100,010,002,000,090，输入的k为10，则输出等于（　）。

A. 11,112,222,444,543

B. 11,122,222,444,453

C. 11,122,222,444,543

D. 11,112,222,444,543

3.

假设输入的n是不超过5的正整数，d[i][0]、d[i][1]都是不超过10000的正整数，完成下面的判断题和单选题。

·判断题

1）若输入n为0，此程序可能会死循环或发生运行错误。（　）

2）若输入n为20，接下来的输入全为0，则输出为0。（　）

3）输出的数一定不小于输入的d[i][0]和d[i][1]的任意一个。（　）

·单选题

4）若输入的n为20，接下来的输入是20个9和20个0，则输出为（　）。

A. 1917

B. 1908

C. 1881

D. 1890

5）若输入的n为30，接下来的输入是30个0和30个5，则输出为（　）。

A. 2020

B. 2030

C. 2010

D. 2000

6）（4分）若输入的n为15，接下来的输入是15到1，以及15到1，则输出为（　）。

A. 2420

B. 2220

C. 2440

D. 2240

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

1.（质因数分解）给出正整数n，请输出将n质因数分解的结果，结果从小到大输出。

例如：输入n=120，程序应该输出“2 2 2 3 5”，表示120=2×2×2×3×5。输入保证2≤n≤109。提示：先从小到大枚举变量i，然后用i不停试除n来寻找所有的质因子。

试补全程序。

1）处应填（　）。

A. n-1

B. 0

C. 1

D. 2

2）处应填（　）。

A. n/i

B. n/(i*i)

C. i*i*i

D. i*i

3）处应填（　）。

A. if(i*i

B. if(n % i==0)

C. while(i*i

D. while(n % i==0)

4）处应填（　）。

A. n>1

B. n

C. i+i

D. i

5）处应填（　）。

A. 2

B. i

C. n/i

D. n

2.（最小区间覆盖）给出n个区间，第i个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间[0,m]被所选区间的并覆盖（即每一个0≤i≤m都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数n和m（1≤n≤5000，1≤m≤109）。

接下来n行，每行两个整数ai,bi（0≤ai,bi≤m）。

提示：使用贪心法解决这个问题。先用O(n2)的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

1）处应填（　）。

A. A[j].b

B. A[j].b>A[j-1].b

C. A[j].a

D. A[j].a

2）处应填（　）。

A. A[j-1]=A[j]; A[j]=t;

B. A[j+1]=A[j]; A[j]=t;

C. A[j]=A[j-1]; A[j-1]=t;

D. A[j]=A[j+1]; A[j+1]=t;

3）处应填（　）。

A. A[i].b

B. A[i].b>A[i-1].b

C. A[i].b>A[p-1].b

D. A[i].b>A[i-1].b

4）处应填（　）。

A. q+1

B. q+1

C. q

D. q

5）处应填（　）。

A. r=max(r, A[q+1].a)

B. r=max(r, A[q].b)

C. r=max(r, A[q+1].b)

D. q++