CSP-S2022初赛

一、单项选择题

假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排 序算法结束后，可能出现的最坏情况是（）。

A.移除受影响的数据后，最终序列是有序序列

B.移除受影响的数据后，最终序列是前后两个有序的子序列

C.移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列

D.移除受影响的数据后，最终序列基本无序

解析：

基数排序是按桶排序的思想，某一个值的改变，不会造成其他数字排序失败。排除这个数字，其他数字仍是有序序列。所以选A。

错误解析：

没有学过基数排序，导致对基数排序不太熟悉。

---

每个顶点度数均为$2$的无向图称为“$2$正规图”。由编号为从$1$到n的顶点构成的所有$2$正规图，其中包含欧拉回路的不同$2$正规图的数量为（）。

A.n!

B.(n-$1$)!

C.n!/$2$

D.(n-$1$)!/$2$

解析：

一个图是欧拉图（包含欧拉回路）的条件是充分必要条件是每个顶点的度都是偶数度。

因此根据题目的定义，$2$正规图每个顶点度数都为$2$，那么该图一定是欧拉图，其中包含欧拉回路。每个顶点度都为$2$，设共有n个顶点，总度数为$2$，每条边提供$2$个度，因此有n条边。也就是n个顶点n条边连成一个环。顶点$1$连出的一条边连到的顶点有n-$1$种选择。

假设连到顶点$2$，第$2$步顶点$2$连到的顶点除了顶点$1$，有n-$2$种选择；

假设连到顶点$3$，第$3$步顶点$3$连到的顶点除了顶点$1$，$2$，有n-$3$种选择；

第n-$1$步，顶点n-$1$只能连到顶点n，有$1$种选择。

顶点n再连接到顶点$1$，形成环。共有：

$(n-1)!(n-1)(n-2)...1=(n-1)!(n-1)(n-2)...1=(n−1)!$种情况

而这样的环也可以是从顶点$1$连到顶点n，顶点n连到顶点n-$1$，顶点n-$1$连到顶点n-$2$，……，连到顶点$2$，顶点$2$连到顶点$1$得到。因此相同的环是算了两遍的，因此应该再除以$2$。所以选D。

错误解析：

不知道欧拉回路是什么意思，没有学过。

---

小明希望选到形如“省A·LLDDD”的车牌号。车牌号在“·”之前的内容固定的$5$位号码中，前$2$位必须是大写英文字母，后$3$位必须是阿拉伯数字（L代表A至Z，D表示$0$至$9$，两个L和三个D之间可能相同也可能不同）。请问总共有（）个可供选择的车牌号？

A.$20280$

B.$52000$

C.$676000$

D.$1757600$

解析：

• 确定第$1$个“L"位置的字母，有$26$种情况

• 确定第$2$个“L"位置的字母，有$26$种情况

• 确定第$1$个“D"位置的数字，有$10$种情况

• 确定第$2$个“D"位置的数字，有$10$种情况

• 确定第$3$个“D"位置的数字，有$10$种情况

根据乘法原理，总情况数为$26*26*10*10*10=676000$种情况。所以选C。

错误解析：

计算出了问题，以后认真计算。

二、阅读程序

(1)

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 }

当输入为“baaabaaabaaabaaaa aaaa”，第$20$行的“j++”语句执行次数为 （）。

A.$9$

B.$10$

C.$11$

D.$12$

解析：

手动运行，在纸上执行程序。 shift['a']为1。 i为$0$，baaa中的第一个b与aaaa中的第$1$个a不同，直接跳过。此时s[i+m]是b，shift['b']为m+$1$，i直接增加m+$1$，也就是$5$。 i为$5$，指向第$2$组baaa中的第$1$个a。匹配$3$个a，j++执行$3$次，遇到b与a不相等。此时s[i+m]是a，shift['a']为$1$，i增加$1$。 i为$6$，指向第$2$组baaa中的第$2$个a。匹配$2$个a，j++执行$2$次，遇到b与a不相等。此时s[i+m]是a，shift['a']为$1$，i增加$1$。 i为7，指向第$2$组baaa中的第$3$个a。匹配$1$个a，j++执行$1$次，遇到b与a不相等。此时s[i+m]是a，shift['a']为$1$，i增加$1$。 i为$8$，指向第$3$组baaa中的第$14$个b。此时s[i+m]是b，shift['b']为m+$1$，i直接增加m+$1$，变为$13$。

i为$13$，执行字符串最后aaaa中的第$1$个a，与模式串aaaa匹配4个a，j++执行$4$次。

j++总计执行$10$次。所以选B。

错误解析：

没有认真去模拟过程，导致计算出错。

谢谢