#4533. 1113 - 2024 BCSP-X 上半年活动基础知识测评 （⼩学⾼年级组）

1113 - 2024 BCSP-X 上半年活动基础知识测评 （⼩学⾼年级组）

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

    • A. 显存
    • B. 寄存器
    • C. RAM
    • D. ROM

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

    • A. abcd*+-
    • B. abc+*d-
    • C. abc*+d-
    • D. -+*abcd

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

    • A. a,b,c,e,d
    • B. b,c,a,e,d
    • C. a,e,c,b,d
    • D. d,c,e,b,a

  4. 已知 7 个结点的二叉树的先根遍历是 1 2 4 5 6 3 7（数字为结点编号），中根遍历是 4 2 6 5 1 7 3，则该二叉树的后根遍历是（ ）。

    • A. 4 6 5 2 7 3 1
    • B. 4 6 5 2 1 3 7
    • C. 4 2 3 1 5 4 7
    • D. 4 6 5 3 1 7 2

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

    • A. 79
    • B. 47
    • C. 32
    • D. 0

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

    • A. 2
    • B. 3
    • C. 4
    • D. 5

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

    • A. x=(x*100+0.5)/100.0;
    • B. x=x*100+0.5/100.0;
    • C. x=(x/100+0.5)*100.0;
    • D. x=(int)(x*100+0.5)/100.0;

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

    • A. 31
    • B. 3B
    • C. 41
    • D. 4B

  9. （ ）是一种选优搜索法，按选优条件向前搜索，以达到目标。

  • A. 回溯法
  • B. 枚举法
  • C. 动态规划
  • D. 贪心

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

    • A. 2 的 10 次方
    • B. 2 的 20 次方
    • C. 2 的 30 次方
    • D. 2 的 40 次方

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

    • A. 3
    • B. 12
    • C. 36
    • D. 45

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

    • A. 晶体管
    • B. 电子管
    • C. 集成电路
    • D. 大规模集成电路

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

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

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

    • A. 堆排序
    • B. 选择排序
    • C. 冒泡排序
    • D. 快速排序

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

    • A. 2k
    • B. 2k+1
    • C. ⌊k/2⌋
    • D. ⌈k/2⌉

【阅读程序第一题】

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

#include<iostream>
using namespace std;
int main(){
  int n, a[105], avg=0, ans=0; 
  cin>>n;
  for(int i=1; i<=n; i++){
    cin>>a[i]; 
    avg+=a[i];
  }
  avg/=n;
  for(int i=1; i<n; i++) 
    if(a[i]<avg){
      a[i+1]-=(avg-a[i]); 
      ans+=(avg-a[i]);
    } else if(a[i]>avg){
      a[i+1]+=(a[i]-avg); 
      ans+=(a[i]-avg);
    }
  cout<<ans<<endl;
  return 0;
}

  1. 该程序的算法时间复杂度为 O(n)。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  2. 若将第 004 行的代码改为 int n, a[105], avg, ans;（声明变量时不赋值），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  3. 若将第 004 行的代码改为 int n, a[100], avg = 0, ans= 0;（更改数组 a 的大小），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  4. 若将第 011 行的 for 循环执行条件改为 i<=n，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  5. 若将第 016 行的代码改为 else{（去掉 else 之后的条件判断），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  6. 该程序的输出结果不可能为负数。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

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

    • A. 2
    • B. 16
    • C. 21
    • D. 26

【阅读程序第二题】

假设输入的所有数是正整数，其中 n 以及数组元素 h[1]...h[n] 均不超过 1,000,000，m 不超过 h[1]...h[n] 之和。

#include<iostream>
using namespace std;
int main(){
  int n, h[1000005], L, R; 
  long long m; 
  cin>>n>>m;
  for(int i=1; i<=n; i++){
    cin>>h[i]; 
    if(h[i]>R) R=h[i];
  } 
  while(L<R){
    int mid=(L+R+1)/2; 
    long long tmp=0;
    for(int i=1; i<=n; i++) 
      if(h[i]>mid) tmp+=h[i]-mid;
    if(tmp<m) R=mid-1;
    else L=mid;
  }
  cout<<L<<endl;
  return 0;
}

  1. 若将第 11 行的 while 循环执行条件改为 L<=R，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  2. 若将变量 m 和变量 tmp 的数据类型都改为 int，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  3. 程序的输出结果有可能是 0。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

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

    • A. 35
    • B. 36
    • C. 37
    • D. 38

  5. 若输入的 n 为 10,000，程序输出结果的最大可能值是（ ）。

    • A. 9,999
    • B. 10,000
    • C. 999,999
    • D. 1,000,000

【阅读程序第三题】

假设输入的 n 是不超过 5000 的正整数，数组元素 a[1]...a[n] 均是不超过 1 的非负整数。

#include<cstdio>
#include<cstring> 
using namespace std; 
const int MAXN=5000+5; 
int n, a[MAXN], d[MAXN];
int check(int k){
  memset(d, 0, sizeof(d)); 
  int res=0;
  for(int i=1, s=0; i<=n; i++){
    s+=d[i];
    if((a[i]+s)%2==1) continue;
    if(i+k>n+1) return 1e9; 
    d[i]++, s++, res++; 
    d[i+k]--;
  }
  return res;
} 
int main(){
  scanf("%d",&n);
  for(int i=1; i<=n; i++) scanf("%d",&a[i]); 
  int ans=1e9;
  for(int k=1; k<=n; k++){
    int tmp=check(k);
    if(tmp<ans) ans=tmp;
  }
  printf("%d\n", ans); 
  return 0;
}

  1. 若将第 9 行的 for 循环执行条件改为 i+k-1<=n，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  2. 若将第 15 行的代码改为 s++, res++;（去掉 d[i]++），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  3. 若将第 15 行中的 s++ 改为 s--，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  4. 程序的输出结果有可能为 0。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

  5. 程序的输出结果必然小于输入的 n。（判断题：正确填 A，错误填 B）

    • A. 正确
    • B. 错误

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

    • A. O(n)
    • B. O(n log n)
    • C. O(n^2)
    • D. O(n^2 log n)

  7. 若输入数据第一行为 7，第二行为 0 0 1 0 1 0 0，则程序将输出（ ）。

    • A. 3
    • B. 4
    • C. 5
    • D. 6

【完善程序第一题】

给定长度 n 的整数序列 a1,a2,...,ana_1, a_2, ..., a_n，以及 q 个询问。每个询问将指定两个整数 l, r，请判断下标在 l 与 r 之间的序列元素（包括 l 与 r）是否互不相同。输入数据保证 1≤n,q≤1000001 \le n, q \le 100000, 1≤ai≤n1 \le a_i \le n, 1≤l≤r≤n1 \le l \le r \le n。

#include<iostream>
#include<algorithm> 
using namespace std; 
const int MAXN=1e5+5; 
int n, q, a[MAXN], last[MAXN], tmp[MAXN], mxlast[MAXN];
int main(){
  cin>>n>>q;
  for(int i=1; i<=n; i++){
    cin>>a[i]; 
    ___①___; 
    ___②___; 
    ___③___;
    if(last[i]>mxlast[i]) mxlast[i]=last[i];
  } 
  while(___④___){
    int l, r;
    cin>>l>>r;
    if(___⑤___) cout<<"No"<<endl; //区间内存在相同元素
    else cout<<"YES"<<endl; //互不相同 
  }
  return 0;
}

  1. ①处应填（ ）。

    • A. last[tmp[i]]=a[i]
    • B. last[i]=tmp[a[i]]
    • C. tmp[last[i]]=i
    • D. tmp[a[i]]=i

  2. ②处应填（ ）。

    • A. last[tmp[i]]=a[i]
    • B. last[i]=tmp[a[i]]
    • C. tmp[last[i]]=i
    • D. tmp[a[i]]=i

  3. ③处应填（ ）。

    • A. mxlast[i]=last[i]
    • B. mxlast[i]=max(mxlast[i-1], last[i])
    • C. mxlast[i]=max(mxlast[i], last[i])
    • D. mxlast[i]=last[i-1]

  4. ④处应填（ ）。

    • A. q--
    • B. q++
    • C. i<=q
    • D. i=l
    • B. mxlast[r]>l
    • C. last[r]>=l
    • D. last[r]>l

【完善程序第二题】

小 H 有一个长度为 n 的序列 a1,a2,...,ana_1, a_2, ..., a_n。他想要知道这个序列中有多少个不同的子序列。两个子序列不同，当且仅当它们包含的元素个数不同，或者在某个位置上的元素不同。由于答案可能很大，你只需要输出答案对 109+710^9+7 取模后的结果。 注意：空序列也算作一个子序列。

#include<iostream>
using namespace std;
const int MOD=1e9+7;
const int MAXN=1e5+5;
int n, a[MAXN], last[MAXN], dp[MAXN];
int main(){
  cin>>n;
  for(int i=1; i<=n; i++) cin>>a[i];
  dp[0]=1; // 空序列
  for(int i=1; i<=n; i++){
    dp[i]=(dp[i-1]*2)%MOD;
    if(last[a[i]]!=0){
      dp[i]=(dp[i]-___①___+MOD)%MOD;
    }
    ___②___;
  }
  cout<<___③___<<endl;
  return 0;
}

  1. ①处应填（ ）。

    • A. dp[last[a[i]]]
    • B. dp[last[a[i]]-1]
    • C. dp[i-1]
    • D. dp[last[a[i]]+1]

  2. ②处应填（ ）。

    • A. last[a[i]]=i
    • B. last[i]=a[i]
    • C. last[a[i]]=i-1
    • D. last[a[i]]=dp[i]

  3. ③处应填（ ）。

    • A. dp[n]
    • B. dp[n-1]
    • C. dp[n]+1
    • D. dp[n]-1
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  6.  粤公网安备44195502000178号
  10. 粤ICP备2026000218号
  15. Worker 0, 78ms