2025csp-j 完善程序

（单选题，每小题 3 分，共计 30 分）

完善程序(一)

1. (字符串解码) “行程长度编码 ” (Run-Length Encoding)是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。

2.压缩规则 如下：i)如果原始字符串中一个字符连续出现N次(N>=2)，在压缩字符串中它被表示为”字符＋数字N"。

例如，编码 "A12"代表12个连续的字符A。ii)如果原始字符串中一个字符只出现1次，在压缩字符串中它就表示为该字符本身。

例如，编码 "B"代表1个字符B。 以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

1  #include <cctype> 
2  #include <iostream> 
3  #include <string> 
4  using namespace std; 
5
6  int main() { 
7      string z; 
8      cin >> z; 
9      string  s = "";
10
11     for (int i = 0; i < z.length(); ) {
12         char ch = z[i];
13
14         if ( ____(1)____ && isdigit(z[i + 1])) {
15             i++; 
16             int count = 0; 
17             while (i < z.length() && isdigit(z[i])) {
18                 count = ____(2)____; 
19                 i++;
20             } 
21             for (int j = 0; j <＿＿＿(3)＿＿; ++j) {
22                s+=ch;
23            }
24        } else {
25                   s+=____(4)____; 
26                   ____(5)____;
27        }
28    }
29
30    cout << s << endl; 
31    return 0; 
32 }

34. ①处应填（ ） {{ select(34) }}

• i < z.length()
• i - 1 >= 0
• i + 1 < z.length()
• isdigit(z[i])

35. ②处应填（ ） {{ select(35) }}

• count + (z[i] - '0')
• count * 10 + (z[i] - '0')
• z[i] - '0'
• count + 1

36. ③处应填（ ） {{ select(36) }}

• count - 1
• count
• 10
• z[i] - '0'

37. ④处应填（ ） {{ select(37) }}

• z[i+1]
• ch
• z.back()
• (char)z[i] + 1

38. ⑤处应填（ ） {{ select(38) }}

• i--
• i = i + 2
• i++
• //不执行任何操作

完善程序(二)

2.（精明与糊涂）有N个人，分为两类：

i)精明人：永远能正确判断其他人是精明还是糊涂；

ii)糊涂人：判断不可靠，会给出随机的判断。已知精明人严格占据多数，即如果精明入有k个，则满足k > N/2。

你只能通过函数query(i,j)让第i个人判断第j个人：返回true表示判断结果为 “精 明人” ；返回false表示判断结果为 ＂糊涂人＂ 。

你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心query(i,j)的内部实现。

以下程序利用 “精明人占多数” 的优势。设想一个 “消除＂的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。

例如，假设有三个人0、1、2。如果0说1 是糊涂人，而1也说0是糊涂人，则0和1至少有一个是糊涂人。程序将同时淘汰0和1。

由于三人里至少有两个精明人，我们确定2是精明人。 试补全程序。

01 #include <iostream> 
02 #include <vector> 
03 using namespace std; 
04 
05 int N; 
06 bool query(int i, int j); 
07 
08 int main() { 
09     cin >> N; 
10
11     int candidate = 0; 
12     int count =____(1)____;
13
14     for (int i = 1; i < N; ++i) { 
15         if (____(2)____) {
16             candidate = i;
17             count = 1; 
18         } else { 
19             if (____(3)____) {
20                 ____(4)____;
21             } else { 
22                    count++; 
23             }
24        }
25    }
26    cout << ____(5)____ << endl;
27    return 0;
28 }

39. ①处应填（ ） {{ select(39) }}

• 0
• 1
• N
• -1

40. ②处应填（ ） {{ select(40) }}

• count < 0
• count == 1
• count == 0
• query(candidate, i) == false

41. ③处应填（ ） {{ select(41) }}

• query(candidate, i) == false
• query(i, candidate) == true
• query(candidate, i) == false && query(i, candidate) == false
• query(candidate, i) == false || query(i, candidate) == false

42. ④处应填（ ） {{ select(42) }}

• count--
• break
• count++
• candidate = i

43. ⑤处应填（ ） {{ select(43) }}

• N - 1
• count
• candidate
• 0