2023年CSP-J初赛原创模考大赛(7月赛)
（C++语言 满分：100分 考试时间：120分钟）
单项选择题（每题只有一个正确选项，每题2分，共30分）
1. 摩尔定律（Moore‘s law)是由英特尔创始人之一戈登·摩尔(Gordon Moor)提出来的。根据摩尔定律，单块集成电路的集成度是6年前的（ ）倍。
A. 4 B. 8 C. 16 D. 32
2. 关于汇编语言，下列说法正确的是( )。
A. 是一种与软件相关的高级程序设计语言
B. 在编写复杂程序时，相对于高级语言而言代码量较大，但更易调试
C. 可以直接访问寄存器、内存单元、以及I/O端口
D. 随着高级语言的诞生，如今已完全被淘汰，不再使用
3. 如果主存容量为16MB，且按字节编址，则表示该主存地址至少需要( )位。
A. 16 B. 24 C. 26 D. 32
4. 当输入＆％￥＃＊１２３４时，以下程序结束后，x＝（ ）。
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch – '0';
ch = getchar();
}
A. 0 B. 4321 C. 1234 D. 无法确定
5. 十进制数字2020转化为二进制数字为（ ）。
A. 11111100100 B. 11110110100 C. 11111101100 D. 11110100100
6. 班级中A、B、C、D四名同学参加百米竞赛，甲、乙、丙三位同学对比赛结果进行了预测，预测结果如下：
甲：C第一，B第二
乙：C第二，D第三
丙：A第二，D第四
比赛结果发现，甲、乙、丙三位同学各预测对了一半，试问比赛结果排名是（ ）。
A. ABCD B. BCAD C. CADB D. CDAB
7. 设 a=true, b=false, c=false，以下逻辑运算表达式值为假的是（ ）。
A. (a∨c)∨b∧a B. a∧(c∨b)∧c C. (c∧b)∨a D. (a∨b)∧(a∨c)
8. 后缀表达式的1 7 3 5 + * + 9 +计算结果为( )。
A. 38 B. 66 C. 72 D. 80
9. 链表具有的特点是( )。
A. 可随机访问任一元素
B. 必须事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成反比
10. 一棵结点数为4068 的二叉树最少有( )个叶子结点；二叉树的根节点高度为 1，一棵结点数为2048的二叉树最小的高度值是( )。
A. 2020 11 B. 1 11 C. 1 12 D. 2020 12
11. 将20个相同的苹果放进3个相同的盘子，每个盘子至少放一个苹果，共有( )种方法。
A. 30 B. 33 C. 43 D. 64
12. 一棵二叉树有10个叶子节点，则总节点数不可能是( )。
A. 18 B. 31 C. 32 D. 2022
13. 5个男生，4个女生共9人站成一排，要求5个男生必须相邻。有多少种排法？
A. 4!×4! B. 5!×5! C. A_9^5×A_4^4 D. C_9^5×A_4^4
14. 一个序列的入栈顺序为abcdefg，请问下面四种出栈顺序中合法的有( )个。
1）abcdefg 2) gfedcba 3) cbdefag 4) efcdbag
A. 1 B. 2 C. 3 D. 4
15. 以下逻辑表达式的值恒为真的是( )。
A. P∨(¬P∧Q)∨(¬P∧¬Q) B. Q∨(¬P∧Q)∨(P∧¬Q)
C. P∨Q∨(P∧¬Q)∨(¬P∧Q) D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)
二、程序阅读理解题（共3大题，共计40分）
1. （13分）
输入是一个长度不超过1000的，只有大写字母构成的字符串，请完成下列的判断题和单选题：
01 #include<cstdio>
02 #include<cstring>
03 #include<iostream>
04 using namespace std;
05 char str[1005];
06 int main(){
07 scanf("%s",str);
08 int len = strlen(str);
09 int l = 0, r = len - 1, tmp;
10 while(l < r){
11 while (str[l] % 2 == 0 && l < r){
12 swap(str[l], str[r]);
13 r--;
14 }
15 l++;
16 }
17 printf("%s", str);
18 return 0;
19 }
判断题
（1）输出的字符串由大写字母组成，并且所有相邻的字符最多只有一对ASCII码的奇偶性不同。（ ）（1.5分）
（2）如果输入的字符串长度为n，那么程序的时间复杂度是O(n2)，而不是O(n)。（ ）（1.5分）
（3）将程序的第10行和第11行的while中的l < r改为l <= r，则对于相同的输入，程序输出不会发生改变。（ ）（2分）
（4）如果输入的字符串只由两种不同的字母组成，那么输出的字符串中所有相邻的字符最多只有一对字符不相同。（ ）（2分）
选择题
（5）如果输入是ABCDEF，那么程序输出。（ ）（3分）
A. AEDCFB B. AECDFB C. ACEDBF D. AFCDEB
（6）如果输入的字符串长度为n，那么程序中的swap操作最多执行（ ）次（3分）
A. ⌊n/2⌋ B. ⌊n/2⌋+1 C. n-1 D. n
2. （13.5分，判断题1.5分，选择题3分）
01 #include<bits/stdc++.h>
02 using namespace std;
03 string s;
04 void f(){
05 char c;
06 if(!(cin >> c)){
07 cout << "invalid input\n";
08 exit(0);//结束整个程序
09 }
10 if(c == '#'){
11 s += '#';
12 return;
13 }
14 f();
15 f();
16 s += c;
17 }
18 int main(){
19 f();
20 cout << s;
21 return 0;
22 }
假设输入是只包含大小写字母以及 '#' 的字符串 。请完成下列的判断题和单选题：
判断题
（1）程序的输入如果以 '#' 开头，则输出可能是invalid input。（ ）
（2）程序的输入如果不以 '#' 开头，则输出长度至少为3。（ ）
（3）若输入中的字母个数为a(a≠0)， ‘#’ 号的个数为b，输出中的字母个数为a，且输出不为invalid input，则b的最小值是a+1。（ ）
选择题
（4）若输入为 ADa##E#G##CF### 时，输出为（ ）。
A. ##A##D#aE###GCF B. ##a###GED##F#CA
C. a#DE#G##A##FC## D. invalid input
（5）若输入为 ABC####ABC#### 时，输出为( ) 。
A. AB##CA#BC B. C##B##A##CB#A#
C. ##C#B#A D. invalid input
（6）如果输入是由A、B、C、D、E各一个和6个'#'，共11个字符组成的字符串，并且A、B、C、D、E的相对顺序和字母顺序相同。则输出共有（ ）种可能。
A. 66 B. 65 C. 64 D. 63
3. （13.5分，判断题1.5分，选择题3分）
假定输入的n是不超过106的正整数，val[1...n]都是正整数, 并且总和不超过231-1。val[1...n]为升序排列。
01 include<bits/stdc++.h>
02 using namespace std;
03 int n, m, s, e, head[105], to[205], nxt[205];
04 bool v[100005];
05 vector<int> a;
06 void dfs(int u) {
07 v[u] = 1;
08 a.push_back(u);
09 if(u == e) {
10 for(int i = 0; i < a.size(); i++)
11 printf("%d", a[i]);
12 printf("\n");
13 v[u] = 0;
14 a.pop_back();
15 return;
16 }
17 for(int i = head[u]; i; i = nxt[i])
18 if(!v[to[i]]) dfs(to[i]);
19 v[u] = 0;
20 a.pop_back();
21 }
22
23 int main() {
24 scanf("%d%d", &n, &m);
25 for(int i = 1; i <= m; i++) {
26 int u, v;
27 scanf("%d%d", &u, &v);
28 to[i] = v;
29 nxt[i] = head[u];
30 head[u] = i;
31 }
32 scanf("%d%d", &s, &e);
33 dfs(s);
34 return 0;
35 }
假设输入的n代表一张图中的顶点数 (1<n≤100)，m代表边数 (0<m≤200)，u和v描述了一条从u到v的有向边，最终查询以s为起点，以e为终点的所有简单路径 (0<u,v,s,e≤n,u≠v,s≠e)，完成下面的判断题和单选题：
判断题
（1）只要输出数据不为空，则输出的每一行至少包含两个数字。（ ）
（2）如果输出数据为空，说明输入数据描述的图不满足强连通。（ ）
（3）该程序的最坏时间复杂度为O(n×m)。（ ）
选择题
（4）输入以下数据后，输出的数据为（ ）。
输入数据：
4 5
2 4
1 2
3 4
1 3
3 2
1 4
A.
1 2 4
1 3 4
1 3 2 4
B.
1 3 4
1 3 2 4
1 2 4
C.
1 2 4
1 3 2 4
1 3 4
D.
1 3 2 4
1 3 4
1 2 4
（5）当输入数据满足以下（ ）条件时，不论s和e如何改变，输出数据一定为一行。（ ）
A. m=n−1，第i条边满足u_i =i,v_i =i+1
B. m=n，第i条边的u和v满足u_i =i,v_i =i+1，其中第m条边满足u_m =n,v_m =1
C. m=n−1，第i条边满足u_i =i+1,v_i <u_i
D. m=n−1，第i条边满足v_i =i+1,u_i <v_i
（6）如果n=7，输出数据的行数最多为（ ）。
A. 5 B. 206 C. 326 D. 720
三、程序完善题（共2大题，每个选择题3分，共计30分）
1.
现有一个长度为n的数组a，我们把数组的相等性看成数组中相邻的相等数字的对数，即当1 ≤ i ≤ n−1时，ai = ai+1的数字对个数。现在对于数组a，我们可以进行以下操作：选择两个整数i和x（1 ≤ i ≤ n−1，1 ≤ x ≤ 109），可以把ai和ai+1设为x。求使得该数组的相等性小于等于1的最小操作数。
输入描述：
第一行一个整数n (2 ≤ n ≤ 2×105)，表示数组a的长度；第二行n个元素表示数组a里每个元素的值ai(1 ≤ ai ≤ 109)。
输出描述：
最小需要的操作数。
输入样例：
5
2 1 1 1 2
输出样例：
1
01 #include<bits/stdc++.h>
02 using namespace std;
03 int main() {
04 int n, temp, cnt = 0;
05 cin >> n;
06 vector<int> a;
07 while (cnt != n) {
08 cin>>temp;
09 a.push_back(temp);
10 cnt++;
11 }
12 int minv = n;
13 int maxv = -1;
14 for(int i = 0; ① ; i++) {
15 if(a[i] == a[i+1]) {
16 minv = min(minv, i);
17 ②;
18 }
19 }
21 if(③ || minv == maxv) {
22 cout << 0 << '\n';
23 } else if(④){
24 cout << 1 << '\n';
25 } else {
26 cout << (⑤) << '\n';
27 }
28 return 0;
29 }
（1）①处应填（ ）。
A. i < n B. i + 1 < n C. i + 1 <= n D. i - 1 <= n
（2）②处应填（ ）。
A. if (maxv > i) maxv = i +1; B. if (maxv > i) maxv = i;
C. if (maxv < i) maxv = i; D. if (maxv < i) maxv = i +1;
（3）③处应填（ ）。
A. maxv == -1 B. maxv == n C. maxv == 0 D. maxv = -1
（4）④处应填（ ）。
A. maxv - minv == 0 B. maxv - minv == 1
C. maxv - minv == 2 D. maxv - minv == -1
（5）⑤处应填（ ）。
A. maxv – minv B. maxv - minv + 1
C. max(maxv, minv) D. maxv - minv – 1
2. 一个数轴上，有n+1个传送点，位于: 0, a1,a2,a3,...,an的位置。如果从传送点x到传送点y，需要消耗： (x−y)2 的能量，且x、y必须都是传送点。
问：若想从数轴: 0 点到：an点，在现有n+1个传送点的前提下，若要消耗的总能量不超过m，最少需要再铺设几个传送点。（注意：传送点只能在整数点上）
输入描述：
第一行1个整数n(1≤n≤2×105)
第二行n个整数a1,a2,a3,...,an(1<a1<a2<a3<...<an≤109)
第三行1个整数m(an≤m≤1018)
输出描述：
输出一个整数，表示从0 点到an点，在现有n+1个传送点的前提下，若要消耗的总能量不超过m，最少需要再铺设传送点的个数。
输入样例：
2
1 5
7
输出样例：
2
01 #include<bits/stdc++.h>
02 using namespace std;
03 typedef long long ll;
04 const int N=2e5+5;
05 int n,a[N],c[N],d[N];
06 ll m,l,r,ans,sum,cnt;
07 //长度是n，分成k段
08 ll f(int len,int k) {
09 return lll * (k-len%k)*(len/k) * (len/k)
10 + lll * len%k*(len/k +1)*(len/k +1);
11 }
12 bool check(ll x)
13 {
14 sum=cnt=0;
15 for(int i=1;i<=n;i++)
16 {
17 ll l=2,r=d[i],ans=l;
18 while(l<=r)
19 {
20 ll mid=(l+r)>>1;
21 if(①>=x) ans=mid,l=mid+1;//填空
22 else r=mid-1;
23 }
24 cnt = ②;//填空
25 sum = ③;//填空
26 }
27 return sum<=m;
28 }
29 int main()
30 {
31 scanf("%d",&n);
32 for(int i=1;i<=n;i++)
33 {
34 scanf("%d",&a[i]);
35 d[i]=a[i]-a[i-1];
36 }
37 scanf("%lld",&m);
38 l=0,r=1e18,ans=-1;
39 while(④) //填空
40 {
41 ll mid= l + r >> 1;
42 if(check(mid)) l = mid;
43 else r = mid;
44 }
45 ans = ⑤;//填空
46 check(ans);
47 printf("%lld\n",cnt-(m-sum)/ans);
48 return 0;
49 }
（1）①处应填写（ ）。
A. f(d[i], mid-1) - f(d[i], mid) B. f(d[i], mid) - f(d[i], mid+1)
C. f(d[i], mid+1) - f(d[i], mid+2) D. f(d[i], mid)
（2）②处应填写（ ）。
A. ans B. ans - 1 C. cnt + ans D. cnt + ans - 1
（3）③处应填写（ ）。
A. f(d[i], ans) B. f(d[i], ans-1) C. sum + f(d[i], ans) D. sum + f(d[i], ans-1)
（4）④处应填写（ ）。
A. r - l >= 0 B. r - l > 0 C. r - l > 1 D. r - l > 2
（5）⑤处应填写（ ）。
A. l B. r C. l + 1 D. r + 1
答案：----->E:\csp\初赛集训模拟题试题包\23年有道小图灵\2023J组7月赛