CSP-J2019NOIP普及组初赛真题（选择题部分）

时间：10⽉的第2/3个星期六下午14:30~16:30

分数及形式：满分100分，形式为笔试(今年可能上机)

1.单项选择题，共15题，每题2分，共30分

2.阅读程序题，共3题，前两题12分，第三题16分，共40分（考试形式为选择判断形式，其中判断题1.5分，选择题3分）

3.完善程序，共2题，每题15分，共30分（选择题形式，每空3分）

1.中国的国家顶级域名是（）

A. .cn

B. .ch

C. .chn

D. .china

正确答案： A

解析：.cn是中国国家顶级域名；.ch是瑞⼠国家顶级域名；.chn是中国拥有⾃主产权的⽹络域名，⾮国家顶级域名；暂⽆.china域名

2.⼆进制数11 1011 1001 0111和01 0110 1110 1011进⾏逻辑与运算的结果是（）。

A. 01 0010 1000 1011

B. 01 0010 1001 0011

C. 01 0010 1000 0001

D. 01 0010 1000 0011

正确答案： D

解析：逻辑运算是按位进⾏的，位与位之间不像加减运算那样有进位或借位的联系。逻辑与（即逻辑乘法）有以下规则00=0,01=1,1*1=1；所以选D

3.⼀个32位整型变量占⽤（）个字节。

A. 32

B. 128

C. 4

D. 8

正确答案： C

解析：1字节(byte)等于8位(bit)，32位及32/8=4字节，所以选C

4.若有如下程序段，其中s、a、b、c均已定义为整型变量,且a、c均已赋值（c⼤于0）

s = a;

for （b = 1; b <= c; b++） s = s - 1;

则与上述程序段功能等价的赋值语句是（）

A. s = a - c;

B. s = a - b;

C. s = s - c;

D. s = b - c;

正确答案： A

解析：循环执⾏c次，每次s-1，s⼀共减去了c个1，即s=a-c

5.设有100个已排好序的数据元素，采⽤折半查找时，最⼤⽐较次数为（）

A. 7

B. 10

C. 6

D. 8

正确答案： A

解析：对折半查找，⾸先将待查记录所在范围缩⼩⼀半，然后逐步缩⼩，对100个元素的顺序表，第⼀次⽐较范围缩⼩到50，第⼆次缩⼩到25，第三次缩⼩到13，第四次缩⼩到7，第五次缩⼩到4，第六次缩⼩到2，第七次就可以找到查找的元素。

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

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

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

C. 所需空间与线性表长度成正⽐

D. 可随机访问任⼀元素

正确答案： D

解析：链表采⽤的是链式存储结构，它克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指⽰，不需要移动数据元素。但是链式存储结构也有不⾜之处：①每个结点中的指针域需额外占⽤存储空间；②链式存储结构是⼀种⾮随机存储结构。

7.把8个同样的球放在5个同样的袋⼦⾥，允许有的袋⼦空着不放，问共有多少种不同的分法？（）

提⽰：如果8个球都放在⼀个袋⼦⾥，⽆论是哪个袋⼦，都只算同⼀种分法。

A. 22

B. 24

C. 18

D. 20

正确答案： C

解析：运⽤5个袋⼦装8个球有3种：1+1+1+1+4 = 8,1+1+1+2+3 = 8,1+1+2+2+2 = 8;运⽤4个袋⼦分8个球有5种：1+1+1+5=8,1+1+2+4=8,1+1+3+3=8,1+2+2+3=8,2+2+2+2=8;运⽤3个袋⼦分8个球有5种：1+1+6=8,1+2+5=8,1+3+4=8,2+2+4=8,2+3+3=8;运⽤2个袋⼦分8个球则有4种：1+7=8,2+6=8,3+5=8,4+4=8;运⽤1个袋⼦装8个球则有1种：8=8。所以⼀共有3+5+5+4+1 = 18种。

8.⼀棵⼆叉树如右图所⽰，若采⽤顺序存储结构，即⽤⼀维数组元素存储该⼆叉树中的结点（根结点的下标为1,若某结点的下标为i ,则其左孩⼦位于下标2i处、右孩⼦位于下标2i+l处），则该数组的最⼤下标⾄少为（）。

A. 6

B. 10

C. 15

D. 12

正确答案： C

解析：根据题⽬给定的规则可知，下标最⼤的结点为树中深度最⼤且最靠右的结点，其下标为（（12+1）2+1）*2+1=159.100以内最⼤的素数是（）。

A.

B. 97

C. 91

D. 93

正确答案： B

解析：98~100均为合数，97为素数

10.319和377的最⼤公约数是（）。

A. 27

B. 33

C. 29

D. 31

正确答案：C

解析：使⽤辗转相除法可得GCD(319,377)=GCD(319,58)=GCD(58,29)=29。或者将两数分解质因数后，提取公共部分亦可求解

11.新学期开学了，⼩胖想减肥，健⾝教练给⼩胖制定了两个训练⽅案。

⽅案⼀：每次连续跑3公⾥可以消耗300千卡（耗时半⼩时）；

⽅案⼆：每次连续跑5公⾥可以消耗600千卡（耗时1⼩时）。

⼩胖每周周⼀到周四能抽出半⼩时跑步，周五到周⽇能抽出⼀⼩时跑步。

另外，教练建议⼩胖每周最多跑21公⾥，否则会损伤膝盖。

请问如果⼩胖想严格执⾏教练的训练⽅案，并且不想损伤膝盖，每周最多通过跑步消耗多少千卡？（）

A. 3000

B. 2500

C. 2400

D. 2520

正确答案： C

解析：设⽅案1执⾏x天，⽅案2执⾏y天，则有3x+5y<=21、x+y<=7、y<=3。要求300x+600y的最⼤值，枚举可得最优⽅案为x=2、y=3,此时300x+600y为2400。

12.—副纸牌除掉⼤⼩王有52张牌，四种花⾊，每种花⾊13张。

假设从这52张牌中随机抽取13张纸牌，则⾄少（）张牌的花⾊⼀致。

A. 4

B. 2

C. 3

D. 5

正确答案： A

解析：抽屉原理，最坏情况，13张牌对应四种花⾊的牌数为3、3、3、4

13.—些数字可以颠倒过来看，例如0、1、8颠倒过来还是本⾝，6颠倒过来是9, 9颠倒过来看还是6,其他数字颠倒过来都不构成数字。

类似的，⼀些多位数也可以颠倒过来看，⽐如106颠倒过来是901。假设某个城市的车牌只由5位数字组成，每⼀位都可以取0到9。

请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？（）

A. 60

B. 125

C. 75

D. 100

正确答案： C

解析：乘法原理，前2位有0,1,8,6,9共5种选择，第3位只能放0,1,8、后2位由前2位决定，因此总⽅案数为55311=75。

14.假设⼀棵⼆叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为（）。

A. ABCDEFGHIJ

B. ABDEGHJCFI

C. ABDEGJHCFI

D. ABDEGHJFIC

正确答案： B

解析：后序遍历的规则是“左右根”、中序遍历的规则是“左根右”，因此可知，A是树根、DBGEHJ是A左⼦树的中序遍历（对应后序遍历DGJHEB）、CIF是A右⼦数的中序遍历（对应后序遍历IFC），递归画出对应的⼆叉树，再根据前序遍历规则“根左右”即可求出答案

15.以下哪个奖项是计算机科学领域的最⾼奖？（）

A. 图灵奖

B. 鲁班奖

C. 诺贝尔奖

D. 普利策奖

正确答案： A

解析：图灵奖由美国计算机协会于1966年设⽴，其名称取⾃计算机科学之⽗图灵，专门奖励对计算机事业作出重要贡献的个⼈，被誉为“计算机界的诺贝尔奖”。