2024年北京市中小学信息学能力测评活动BCSP-X小高组真题

选择题

第 1 题单选题

计算机在工作过程中突然停电，( )中的信息不会丢失。

显存

寄存器

RAM

ROM

第 2 题单选题

中缀表达式a*(b+c)-d的后缀形式是( )。

abcd*+-

abc+*d

abc*+d

-+*abcd

第 3 题单选题

设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有( )。

a,b,c,e,d

b,c,a,e,d

a,e,c,b,d

d,c,e,b,a

第 4 题单选题

已知7个结点的⼆叉树的先根遍历是1245637(数字为结点编号),中根遍历是4265173,则该⼆叉树的后根遍历是( )。

4652731

4652137

4231547

4653172

第 5 题单选题

在C++中，若变量x为int类型且已被赋值为40,则x&(x-1)的值为()。

第 6 题单选题

有⼀个等比数列，共有奇数项，其中第⼀项和最后⼀项分别是2和118098，中间⼀项是486，请问以下那个数是可能的公比（）。

第 7 题单选题

设变量x 为float 类型且⼰赋值，则以下语句能将x中的数值四舍五入到小数点后第2位的是（）。

x = (x * 100 + 0.5) / 100.0

x = x * 100 + 0.5 / 100.0

x = (x / 100 + 0.5) * 100. 0

x = (int) (x * 100 + 0.5) / 100. 0

第 8 题单选题

十六进制下，7*7 的运算结果为（）。

第 9 题单选题

（）是⼀种选优搜索法，按选优条件向前搜索，以达到⽬标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回⼀步重新选择。

回溯法

枚举法

动态规划

贪心

第 10 题单选题

1TB代表的字节数⿏是（）。

2的10次方

2的20次方

2的30次方

2的40次方

第 11 题单选题

原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共有（）个不同的非空子串。

第 12 题单选题

1958年以前的第⼀代计算机主要⽤于科学计算、军事研究。这些计算机以（）为主要的逻辑元件。

晶体管

电子管

集成电路

⼤规模集成电路

第 13 题单选题

链表不具备的特点是（）。

可用O（1）时间随机访问任何⼀个元素。

插入、删除操作不需要移动元素。

存储单元在内存中的地址可以不连续。

无需事先估计存储空间大小。

第 14 题单选题

以下排序算法中，（）属于稳定排序算法。

堆排序

选择排序

冒泡排序

快速排序

第 15 题单选题

完全⼆叉树的顺序存储⽅案，是指将完全⼆叉树的结点从上到下、从左到右依次存放到⼀个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的⽗结点如果存在的话，应当在放在数组中的（）号位置。

2k+1

⌊k/2⌋

⌈k/2⌉

阅读程序题

第 16-22 题组合题

假设输入的所有数是不超过100的正整数, 完成下面的判断题和单选题:

第16题判断

判断題16.该程序的算法时间复杂度为0（n）。（）

正确

错误

第17题判断

若将第004⾏的代码改为“int n, a［105］，avg, ans；”（声明变量时不赋值），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（）

正确

错误

第18题判断

若将第004⾏的代码改⼒“int n, a［100］， avg = 0， ans = 0：”（更改数组a 的⼤⼩），程序仍可以被正常执⾏，且对于相同的输入数据，输出结果不变。（）

正确

错误

第19题判断

若将第011⾏的for 循环执⾏条件改为“i<=n”，程序仍可以被正常执行，且对于相同的输⼊数据，输出结果不变。（）

正确

错误

第20题判断

若将第016⾏的代码改“else｛”（去掉else 之后的条件判断），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（）

正确

错误

第21题判断

该程序的输出结果不可能为负数。（）

正确

错误

第22题单选

若输入数据第一行为“7”，第二行为“1 9 2 8 12 2 8”，则程序将输出（）。

第 23-28 题组合题

假设输入的所有数是正整数, 其中n以及数组元素h[1], h[2],…, h[n均不超过1000000, m不超过 h[1], h[2],…, h[n]之和, 完成下面的判断题和单选题:

第23题判断

若将第 011⾏的 while循环执⾏条件改为“L<=R”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。( )

正确

错误

第24题判断

若将变量m和变量 tmp 的数据类型都改为int，程序仍可以被正常执行，且对于相同的输入数据输出结果不变。( )

正确

错误

第25题判断

程序的输出结果有可能是0。( )

正确

错误

第26题单选

将第 012⾏代码改为( )，程序执行的效果不变。

int mid = (L+R) / 2;

int mid = (L+R) * 2;

int mid = L + R + 1 << 2:

int mid = L + R + 1 >> 2;

第27题单选

若输⼊数据第⼀⾏为“5 20”，第⼆⾏为“4 42 40 26 46”，则程序将输出( )。

第28题单选

若输⼊的n为 10000，程序输出结果的最大可能值是( )。

9999

10000

999999

第 29-35 题组合题

假设输入的n是不超过 5000的正整数, 数组元素a[1], a[2],…, a[nl均是不超过1的非负整数, 完成下面的判断题和单选题判断题

第29题判断

若将第 009 ⾏的 for 循环执⾏条件改为“i + k - 1<= n ”，程序仍可以被正常执行，且对于相同的输⼊数据，输出结果不变。( )

正确

错误

第30题判断

若将第 015 ⾏的代码改为“s++, res++;”(去掉 d[i]++)，程序仍可以被正常执行，且对于相同的输⼊数据，输出结果不变。( )

正确

错误

第31题判断

若将第 015 ⾏的代码改为“s++, res++;”(去掉 d[i]++)，程序仍可以被正常执行，且对于相同的输⼊数据，输出结果不变。( )

正确

错误

第32题判断

程序的输出结果有可能为0 。( )

正确

错误

第33题判断

程序的输出结果必然小于输入的 n。( ）

正确

错误

第34题单选

该程序的算法时间复杂度为()。

O（n）

O（n log n）

O（n²）

O（n² log n）

第35题单选

若输⼊数据第⼀⾏为“7”，第⼆⾏为“0 0 1 0 1 0 0”，则程序将输出()。

完善程序题

第 36-40 题组合题

给定⻓度n的整数序列a1,a2, …,an，以及q个询问。每个询问将指定两个整数l，r，请判断下标在l与r之间的序列元素包括al与ar是否互不相同。输入数据保证1≤n,q≤100000,1≤ai≤n,1≤l≤r≤n。

第36题单选

①处应填( )。

last[tmp[i]] = a[i]

last[i]= tmp[a[i]]

tmp[last[i]]= i

tmp[a[i]]=i

第37题单选

②处应填( )。

last[tmp[i]]= a[i]

last[i]= tmp[a[i]]

tmp[last[i]]=i

tmp[a[i]]=i

第38题单选

③处应填( )。

mxlast[i]= MAXN

mxlast[i]= tmp[i]

mxlast[i]=0

mxlast[i]=mxlast[ i -1 ]

第39题单选

④处应填( )。

q--

--q

!(q--)

!(--q)

第40题单选

⑤处应填() 。

mxlast[1]<= r

mxlast[r]<= 1

mxlast[1]>=r

mxlast[r]>=1

第 41-45 题组合题

给定正整数n，请编写程序计算它的全部正约数之和。输⼊数据保证 n ≤ 10000000。试⽤最优选项补全程序：

第41题单选

①处应填( )。

ans/(x-1)

ans*(x-1)

(ans-1)*(x-1)

(ans-1)/(x-1)

第42题单选

②处应填( )。

int i=1;i< MAXN; i++

inti=1;i<= MAXN; i+

int i=2;i< MAXN; i++

int i=2;i<= MAXN; i++

第43题单选

③处应填( )。

d[j]= i

d[i]=j

d[i]=i

d[j]=j

第44题单选

④处应填( )。

n -= d[n]

n-= last

n /= d[n]

n--

第45题单选

⑤处应填()

last =d[n],t=0

last =d[n]，t=1

last = d[n]，t--

last=-1，t=0

答题卡

选择题

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

阅读程序题

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

完善程序题

36 37 38 39 40 41 42 43 44 45