一、单项选择题
1.你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：
real 0m30.721s
user 0m24.579s
sys 0m6.123s
以下最接近秒表计时的时长为（ ）。
A.30s
B.24s
C.18s
D.6s
解析： real 是整个程序的运行时间
30最接近
错因：(以为是和其中一个差距最小的)
2.计算机系统用小端（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
解析：
小端存的是最后面的两位 EF
大端存的是最前面的两位 DE
EF,DE
错因：(乱选的)
3.一个深度为 5（根结点深度为 1）的完全 3 叉树，按前序遍历的顺序给结点从 1 开始编号，则第 100 号结点的父结点是第（ ）号。
A. 95
B. 96
C. 97
D. 98
解析： 画图即可
1 第1层
2 42 82 第2层
3 16 29 43 56 69 83 96 109 第3层
4 8 12 17 21 25 30 34 38 44 48 52 57 61 65 70 74 78 84 88 92 97 101 105 110 114 118 第4层
5 6 7 9 10 11 13 14 15 18 19 20 22 23 24 26 27 28 31 32 33 35 36 37 39 40 41 45 46 47 49 50 51 53 54 55 58 59 60 62 63 64 66 67 68 71 72 73 75 76 77 79 80 81 85 86 87 89 90 91 93 94 95 98 99 100 102 103 104 106 107 108 111 112 113 115 116 117 119 120 121 第5层
(不会排版,其实是用程序写的)
4.每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图，其中包含欧拉回路的不同 2 正规图的数量为（ ）。
A. n!
B. (n-1)!
C. n!/2
D. (n-1)!/2
解析:
这种图是个环 按照顺序是 n!
同一种旋转 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 n!/n=(n-1)!
再把方向去掉 1 2 3 4 1 4 3 2 (n-1)!/2
错因：(乱选的)
5.共有 8 人选修了程序设计课程，期末大作业要求由 2 人组成的团队完成。假设不区分每个团队内 2 人的角色和作用，请问共有多少种可能的组队方案。（ ）。
A. 28
B. 32
C. 56
D. 64
解析:
C28=8!/2!/6!=8*7/2=28
错因：(没除2)
6.以比较为基本运算，在 n 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算
A. n/2
B. n-1
C. n
D. n+1
解析: 无
错因：(忘记了(￣_￣|||))
二、阅读程序
(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 }
17.当输入为“abbababbbab abab”时，输出为 4。
解析: a b b a b a b
0 1 2 3 4 5 6
第一个匹配的位置是3
错因:（(╬▔皿▔)╯看成从1开始了）
18.当输入为“GoodLuckCsp2022 22”时，第 20 行的“j++”语句执行次数为 2。
解析： G o o d L u c k C s p 2 0 2 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
i=0 i+=shift[s[i+2]]
i=3 i+=shift[s[i+2]]
i=6 i+=shift[s[i+2]]
i=9 i+=shift[s[i+2]]
i=10 i+=shift[s[i+2]]
i=13
s[13+0] == t[0]? j++;
s[13+1] == t[1]? j++;
错因:(不懂shift[i+m]是什么?)
19.该算法最坏情况下的时间复杂度为（ ）。
for (i =0; i<= n - m; i += shift[s[i + m]]) 如果 m=1 且每一个shift[s[i + 1]]都是1 则循环n次
while(j < m && s[i +j] == t[j]) 易得出为m
时间复杂度
错因:(不懂shift[i+m]是什么,随便选的一个(￣_￣|) )
21.当输入为“baaabaaabaaabaaaa aaaa”，第 20 行的“j++”语句执行次数为 （ ）。
b a a a b a a a b a a a b a a a a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 i=0 i+=shift[s[i+4]]
i=5 i+=shift[s[i+4]]
s[5+0] == t[0]? j++;
s[5+1] == t[1]? j++;
s[5+2] == t[2]? j++;
s[5+3] == t[3]? no;
i=6 i+=shift[s[i+4]]
s[6+0] == t[0]? j++;
s[6+1] == t[1]? j++;
s[6+2] == t[2]? no;
i=7 i+=shift[s[i+4]]
s[7+0] == t[0]? j++;
s[7+1] == t[1]? no;
i=8 i+=shift[s[i+4]]
s[8+0] == t[0]? no;
i=13
s[13+0] == t[0]? j++;
s[13+1] == t[1]? j++;
s[13+2] == t[2]? j++;
s[13+3] == t[3]? j++;
3+2+1+4=10
错因:(不懂shift[i+m]是什么,随便选的一个(￣_￣|) )
