2024北京市中小学信息学能力测评活动第一轮基础知识测评(小学高年级组)

一、单项选择题(共15题，每题2分，共计30分)

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

{{ select(1-1) }}

• 显存
• 寄存器
• RAM
• ROM

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

{{ select(1-2) }}

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

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

{{ select(1-3) }}

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

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

{{ select(1-4) }}

• 4652731
• 4652137
• 4231547
• 4653172

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

{{ select(1-5) }}

• 79
• 47
• 32
• 0

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

{{ select(1-6) }}

• 2
• 3
• 4
• 5

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

{{ select(1-7) }}

• 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 的运算结果为（）。

{{ select(1-8) }}

• 31
• 38
• 41
• 48

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

{{ select(1-9) }}

• 回溯法
• 枚举法
• 动态规划
• 贪心

10.1TB代表的字节数鼠是（）。

{{ select(1-10) }}

• 2的10次方
• 2的20次方
• 2的30次方
• 2的40 次方

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

{{ select(1-11) }}

• 3
• 12
• 36
• 45

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

{{ select(1-12) }}

• 晶体管
• 电子管
• 集成电路
• 大规模集成电路

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

{{ select(1-13) }}

• 可用0（1）时间随机访问任何一个元素。
• 插入、删除操作不需要移动元素。
• 存储单元在内存中的地址可以不连续。
• 无需事先估计存储空间大小。

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

{{ select(1-14) }}

• 堆排序
• 选择排序
• 冒泡排序
• 快速排序

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

{{ select(1-15) }}

• 2k
• 2k + 1
• [k /2]
• [k / 2]

二、阅读程序（判断题正确填A，错误填B，选择题每题有且仅有一个正确选项；除特说明外，判断題1.5分，选择題3分，共计40分）

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

判断題

1. 该程序的算法时间复杂度为0（n）。（ ）

{{ select(2-11) }}

• 对
• 错

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

{{ select(2-12) }}

• 对
• 错

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

{{ select(2-13) }}

• 对
• 错

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

{{ select(2-14) }}

• 对
• 错

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

{{ select(2-15) }}

• 对
• 错

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

{{ select(2-16) }}

• 对
• 错

单选題

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

{{ select(2-17) }}

• 2
• 16
• 21
• 26

假设输入的所有数是正整数，其中n以及数组元素h[1]，h[2]，…，h[n]均不超过1000000，m

不超过 h[1]，h[2]，…，h[n]之和，完成下面的判断题和单选题:

判断题

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

{{ select(2-21) }}

• 对
• 错

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

{{ select(2-22) }}

• 对
• 错

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

{{ select(2-23) }}

• 对
• 错

单选題

4.(本题4分)将第 012行代码改为( 此题错误 )，程序执行的效果不变。

{{ select(2-24) }}

• int mid = (L+R) / 2;
• int mid = (L+R) * 2;
• int mid = L + R + 1 << 2:
• int mid = L + R + 1 >> 1;

5.若输入数据第一行为“5 20”，第二行为“4 42 40 26 46”，则程序将输出( )。

{{ select(2-25) }}

• 35
• 36
• 37
• 38

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

{{ select(2-26) }}

• 9999
• 10000
• 999999
• 1000000

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

●判断题

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

{{ select(2-31) }}

• 对
• 错

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

{{ select(2-32) }}

• 对
• 错

3.若将第 015 行中的“s++”改为“s--”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。( )

{{ select(2-33) }}

• 对
• 错

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

{{ select(2-34) }}

• 对
• 错

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

{{ select(2-35) }}

• 对
• 错

●单选题

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

{{ select(2-36) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• $O(n^2\log n)$

7.若输入数据第一行为“7”，第二行为“0 0 1 0 1 0 0”，则程序将输出()。

{{ select(2-37) }}

• 3
• 4
• 5
• 6

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

(1)给定长度n的整数序列$a_1,a_2,…，a_n$，以及$q$个询问。每个询问将指定两个整$l，r$，请判断下标在$l$与$r$之间的序列元素(包括$a_l$与$a_r$)是否互不相同。输入数据保证$1 ≤ n, q ≤ 100000，1≤a_i≤n,1≤l≤r≤n.$

1.①处应填( )。

{{ select(3-11) }}

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

2.②处应填( )。

{{ select(3-12) }}

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

3.③处应填( )。

{{ select(3-13) }}

• mxlast[i]= MAXN
• mxlast[i]= tmp[i]
• mxlast[i]=0
• mxlast[i]=mxlast[ i -1 ]

4.④处应填( )。

{{ select(3-14) }} }}

• q--
• --q
• !(q--)
• !(--q)

5.⑤处应填()。

{{ select(3-15) }}

• mxlast[1]<= r
• mxlast[r]<= 1
• mxlast[1]>=r
• mxlast[r]>=1

（2）给定正整数n，请编写程序计算它的全部正约数之和。输入数据保证 n≤ 10000000。

试用最优选项补全程序：

1.①处应填( )。

{{ select(3-21) }}

• ans/(x-1)
• ans*(x-1)
• (ans-1)*(x-1)
• (ans-1)/(x-1)

2.②处应填( )。

{{ select(3-22) }}

• int i=1;i< MAXN; i++
• inti=1;i<= MAXN; i+
• int i=2;i< MAXN; i++
• int i=2;i<= MAXN; i++

3.③处应填( )。

{{ select(3-23) }}

• d[j]= i
• d[i]=j
• d[i]=i
• d[j]=j

44.④处应填( )。

{{ select(3-24) }}

• n -= d[n]
• n-= last
• n /= d[n]
• n--

45.⑤处应填()

{{ select(3-25) }}

• last =d[n],t=0
• last =d[n]，t=1
• last = d[n]，t--
• last=-1，t=0