初赛错题集
CSP-S 2022
1.计算机系统用小端（\(Little Endian\)）和大端（\(Big Endian\)）来描述多字节数据的存储地 址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数 据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 \(C++\) 代码段表示的程序，将分别输出什么结果？（ ）
unsigned x = 0xDEADBEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);
A. \(EF、EF\)
B. \(EF、DE\)
C. \(DE、EF\)
D. \(DE、DE\)
错误答案：\(C\)，正确答案：\(B\)
tips：
从右到左依次是低位到高位
2.一个深度为 \(5\)（根结点深度为 \(1\)）的完全 \(3\) 叉树，按前序遍历的顺序给结点从 1 开始编号，则第 \(100\) 号结点的父结点是第（ ）号。
A. \(95\)
B. \(96\)
C. \(97\)
D. \(98\)
错误答案：\(D\)，正确答案：\(C\)
1 #include <iostream>
2 #include <string>
3 #include <vector>
4
5 using namespace std;
6
7 int f(const string &s, const string &t)
8 {
9 int n = s.length(), m = t.length();
10
11 vector<int> shift(128, m + 1);
12
13 int i, j;
14
15 for (j = 0; j < m; j++)
16 shift[t[j]] = m - j;
17
18 for (i =0; i<= n - m; i += shift[s[i + m]]){
19 j =0;
20 while(j < m && s[i +j] == t[j]) j++;
21 if (j == m) return i;
22 }
23
24 return -1;
25 }
26
27 int main()
28 {
29 string a ,b;
30 cin >> a >> b;
31 cout << f(a, b) << endl;
32 return 0;
33 }
3.1 该算法最坏情况下的时间复杂度为（ ）。
A. \(O(n+m)\)
B. \(O(n \log m)\)
C. \(O(m \log n)\)
D. \(O(nm)\)
错误答案：\(A\)，正确答案：\(D\)
3.2 \(f(a,b)\) 与下列（ ）语句的功能最类似。
A. \(a.find(b)\)
B. \(a.rfind(b)\)
C. \(a.substr(b)\)
D. \(a.compare(b)\)
错误答案：\(B\)，正确答案：\(A\)
tips：
\(find()\)：正向找前缀
\(rfind()\)：逆向找前缀
\(substr()\)：截取字符串
\(compare()\):比较字符串大小关系
3.3 当输入为 \(baaabaaabaaabaaaa aaaa\) ，第 \(20\) 行的 \(j++\) 语句执行次数为 （ ）。
A. 9
B. 10
C. 11
D. 12
错误答案：\(A\)，正确答案：\(B\)
1 #include <iostream>
2
3 using namespace std;
4
5 const int MAXN = 105;
6
7 int n, m, k, val[MAXN];
8 int temp[MAXN], cnt[MAXN];
9
10 void init()
11 {
12 cin >> n >> k;
13 for (int i = 0; i < n; i++) cin >> val[i];
14 int maximum = val[0];
15 for (int i = 1; i < n; i++)
16 if (val[i] > maximum) maximum = val[i];
17 m = 1;
18 while (maximum >= k) {
19 maximum /= k;
20 m++;
21 }
22 }
23
24 void solve()
25 {
26 int base = 1;
27 for (int i = 0; i < m; i++) {
28 for (int j = 0; j < k; j++) cnt[j] = 0;
29 for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
30 for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
31 for (int j = n - 1; j >= 0; j--) {
32 temp[cnt[val[j] / base % k] - 1] = val[j];
33 cnt[val[j] / base % k]--;
34 }
35 for (int j = 0; j < n; j++) val[j] = temp[j];
36 base *= k;
37 }
38 }
39
40 int main()
41 {
42 init();
43 solve();
44 for (int i = 0; i < n; i++) cout << val[i] << ;
45 cout << endl;
46 return 0;
47 }
4.1 若 \(val_i\) 的最大值为 \(100\)，\(k\) 取（ ）时算法运算次数最少。
A. 2
B. 3
C. 10
D. 不确定
错误答案：\(C\)，正确答案：\(B\)
1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 const int MAXL = 1000;
7
8 int n, k, ans[MAXL];
9
10 int main(void)
11 {
12 cin >> n >> k;
13 if (!n) cout << 0 << endl;
14 else
15 {
16 int m = 0;
17 while (n)
18 {
19 ans[m++] = (n % (-k) + k) % k;
20 n = (ans[m - 1] - n) / k;
21 }
22 for (int i = m - 1; i >= 0; i--)
23 cout << char(ans[i] >= 10 ?
24 ans[i] + 'A' - 10 :
25 ans[i] + '0');
26 cout << endl;
27 }
28 return 0;
29 }
5.1 当输入为 \(1000000 19\) 时，输出为（ ）。
A. \(BG939\)
B. \(87GIB\)
C. \(1CD428\)
D. \(7CF1B\)
错误答案：\(A\)，正确答案：\(B\)