CSP初赛模拟题

进群领取CSP知识点手册。

9月13日，上海交大教练直播课，13:00-15:00，C++信奥零基础新班开课。

完善程序（一）

（字符串替换）给定一个字符串 （ 仅包含大小写字母），下面的程序将  中的每个字母用规定的字母替换，并输出  经过替换后的结果。

程序的输入是两个字符串，第一个字符串是给定的字符串 ，第二个字符串  由 26 个字母组成，它是  的任一排列，大小写不定， 规定了每个字母对应的替换字母： 中的第一个字母是字母  和  的替换字母，即  中的  用该字母的大写替换， 中的  用该字母的小写替换； 中的第二个字母是字母  和  的替换字母，即  中的  用该字母的大写替换， 中的  用该字母的小写替换；……以此类推。

#include<iostream>#include<cstring>usingnamespacestd;char change[26], str[5000];voidCheckChangeRule(){int i;for (i = 0; i < [ ① ]; i++) {if ( [ ② ] )            change[i] -= 'A' - 'a';    }}voidChangeString(){int i;for (i = 0; i < strlen(str); i++) {if ( [ ③ ] )            str[i] = change[str[i] - 'A'] - 'a' + 'A';else            [ ④ ]     }}int main() {int i;cin >> str;cin >> change;    CheckChangeRule();       [ ⑤ ]cout << str << endl;return0;}

1. ① 处应填（ ）。

A. strlen(change)

B. strlen(str)

C. 25

D. 27

【解析】change 字符串长度为 26，也可以使用 strlen(change) 计算得到。

【答案】A

1. ② 处应填（ ）。

A. change[i] >= 'a' || change[i] <= 'z'

B. change[i] >= 'a' && change[i] <= 'z'

C. change[i] >= 'A' && change[i] <= 'Z'

D. change[i] >= 'A' || change[i] <= 'Z'

【解析】将 change 中大写字母都变成小写。

【答案】C

1. ③ 处应填（ ）。

A. str[i] >= 'a' || str[i] <= 'z'

B. str[i] >= 'A' && str[i] <= 'Z'

C. str[i] >= 'a' && str[i] <= 'z'

D. str[i] >= 'a' || str[i] <= 'z'

【解析】change 中都是小写字母，如果 str[i] 是大写，找到 change 中对应的小写，并转回大写。

【答案】B

1. ④ 处应填（ ）。

A. str[i] = change[str[i] - 'a'];

B. str[i] = change[str[i] - 'A'];

C. str[i] = change[str[i] - 'a']-'a'+'A';

D. str[i] = change[str[i] - 'a']+'a'-'A';

【解析】如果 str[i] 是大写，找到 change 中对应的小写。

【答案】A

1. ⑤ 处应填（ ）。

A. ChangeString(CheckChangeRule());

B. ChangeString(str);

C. ChangeString(change);

D. ChangeString();

【解析】调用 ChangeString() 进行字符串变换。

【答案】D

完善程序（二）

（找第 k 大的数） 给定一个长度为  的无序正整数序列, 以及另一个数 ，然后以类似快速排序的方法找到序列中第 n 大的数（关于第 n 大的数：例如序列 {1,2,3,4,5,6} 中第 3 大的数是 4）。

#include<iostream>usingnamespacestd;int a[1000001], n, ans = -1;voidswap(int &a, int &b){int c;    c = a;    a = b;    b = c;}intFindKth(int left, int right, int n){int tmp, value, i, j;if (left == right)return left;    tmp = rand() % (right - left) + left;    swap(a[tmp], a[left]);    value = [ ① ];    i = left;    j = right;while (i < j) {while (i < j && [ ② ]) j--;if (i < j) {            a[i] = a[j];            i++;        } elsebreak;while (i < j && [ ③ ]) i++;if (i < j) {            a[j] = a[i];            j - -;        } elsebreak;    }    [ ④ ] if (i < n) return FindKth([ ⑤ ]);if (i > n)return [ ⑥ ] return i;}intmain(){int i;int m = 1000000;for (i = 1; i <= m; i++)cin >> a[i];cin >> n;    ans = FindKth(1, m, n);cout << a[ans];return0;}

1. ① 处应填（ ）。

A. a[left]

B. a[left+1]

C. a[right]

D. a[right-1]

【解析】tmp 选取随机轴点，然后和 left 指向元素交换，value 最终取值为 a[left]。

【答案】A

1. ② 处应填（ ）。

A. a[i]<value

B. a[j]=value

C. a[j]<value

D. a[i]=value

【解析】找到右侧第一个不合法的值。

【答案】C

1. ③ 处应填（ ）。

A. a[i]>value

B. a[i]=value

C. a[j]>value

D. a[j]=value

【解析】找到左侧第一个不合法的值。

【答案】A

1. ④ 处应填（ ）。

A. a[i]>value;

B. a[i]=value;

C. a[j]>value;

D. a[j]<value;

【解析】i 位置放轴点元素 value。

【答案】B

1. ⑤ 处应填（ ）。

A. left,i,n

B. i,right,n

C. i+1,right,n

D. left,i-1,n

【解析】i<n，找右侧。

【答案】C

1. ⑥ 处应填（ ）。

A. FindKth(i+1,right,n);

B. FindKth(i,right,n);

C. FindKth(left,i-1,n);

D. FindKth(left,i,n);

【解析】i>n，找左侧。

【答案】C