C++ 程序分析与理解：字符串处理和时间复杂度

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；

除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

(1) 01 #include 02 #include 03 using namespace std; 04 string s, t; 05 string a, b; 06 int main(){ 07 getline(cin, s); 08 getline(cin, a); 09 getline(cin, b); 10 for(int i = 0;i < s.size();i ++){ 11 bool flag = true; 12 if(i + a.size() <= s.size()){ 13 for(int j = 0;j < a.size();j ++){ 14 char p = s[i + j], q = a[j]; 15 if('a' <= p && p <= 'z') p = p - 'a' + 'A'; 16 if('a' <= q && q <= 'z') q = q - 'a' + 'A'; 17 if(p != q) 18 flag = false; 19 } 20 } else 21 flag = false; 22 23 if(flag == true){ 24 t += b; 25 i += a.size() - 1; 26 } else 27 t += s[i]; 28 } 29 cout << t << endl; 30 return 0; 31 }

保证输入的三行字符串的长度均不超过 103，且每个字符串均由 ASCII 可视字符或 空格组成且非空。完成下面的判断题和单选题：

⚫ 判断题 16. 保持 s,b 的字母大小写不变，将 a 里的小写英文字母改写成大写、将大写英文 字母改写成小写，输出结果不变。 (√) 17. 每次调用 s.size()的复杂度是 O(1) 的，但若是把 s.size()替换成 s.length() 则调用的复杂度将会变成 O(l)，其中 l 是 s 当前的长度。这是因为 s.length() 作为 strlen() 函数的 string 版本，会每次重新计算 s 最后一个 元素的位置。 (√) 18. 当输入的字符串 s,a,b 均由小写字母 a 或 b 组成，记 s,a,b 的长度分别为 n,m,k，则程序的时间复杂度最坏为 O(nm+nk)。 (√) 19. 当输入的字符串 s,a,b 均由小写字母 a 组成，记 s,a,b 的长度分别为 n,m,k 且有 n>m>k，那么上述程序的总复杂度为 O(n)。 (×)

⚫ 单选题 20. 针对下列输入数据，程序的输出为？ 。 National Olympiad in Informatics A154 A C

A. National Olympiad in Informatics C154 B. NCtionCl OlympiCd in InformCtics C154 C. National! D. Nctioncl Olympicd in Informctics C154

21. 针对下列输入数据，程序的输出为？ 。 abaabaaabaaaabaaaaabababab aa ab

A. abABbABBbABBBbABBBBbababab B. ababbabbbabbbbabbbbbababab C. ababbababababbabababababab D. 程序陷入死循环/非正常退出，无法正常输出内容：

答案： 16. √ 17. √ 18. √ 19. × 20. A. National Olympiad in Informatics C154 21. B. ababbabbbabbbbabbbbbababab