试卷 2019年信息学奥赛CSP-S1提高组初赛真题试卷
2019年信息学奥赛CSP-S1提高组初赛真题试卷
选择题
第 1 题    单选题

若有定义:int a=7; float x=2.5, y=4.7;则表达式x+a%3*(int)(x+y)%2的值是:( ) 

A.

0.000000

B.

2.750000

C.

2.500000

D.

3.500000

第 2 题    单选题
有一个等比数列,共有奇数项,其中第一项和最后一项分别是2和118098,中间一项是486,请 问一下哪个数是可能的公比?( )
A.

5

B.

3

C.

4

D.

2

第 3 题    单选题
以下哪些算法不属于贪心算法?( )
A.

Di jkstra算法

B.

Floyd算法

C.

Prim算法

D.

Kruskal算法

第 4 题    单选题

以下哪个结构可以用来存储图( )

A.

B.

二叉树

C.

队列

D.

邻接矩阵

第 5 题    单选题

AB是两个长为n的有序数组,现在需要将AB合并成一个排好序的数组,请问任何以元素比较 作为基本运算的归并算法,在最坏情况下至少要做多少次比较?( )

A.

n2

B.

nlogn

C.

2n

D.

2n-1

第 6 题    单选题
一次期末考试,某班有15人数学得满分,有12人语文得满分,并且有4人语、数都是满分,那么这 个班至少有一门得满分的同学有多少人?( ) 
A.

23

B.

21

C.

20

D.

22

第 7 题    单选题

一些数字可以颠倒过来看,例如018颠倒过来看还是本身,6颠倒过来是99颠倒过来看还 6,其他数字颠倒过来都不构成数字。类似的,一些多位数也可以颠倒过来看,比如106颠倒过来 901。假设某个城市的车牌只有5位数字,每一位都可以取09。请问这个城市有多少个车牌倒过来恰 好还是原来的车牌,并且车牌上的5位数能被3整除?( ) 

A.

40

B.

25

C.

30

D.

20

第 8 题    单选题

G是一个非连通无向图(没有重边和自环),共有28条边,则该图至少有( )个顶点

A.

10

B.

9

C.

11

D.

8

第 9 题    单选题

排序的算法很多,若按排序的稳定性和不稳定性分类,则( )是不稳定排序。

A.

冒泡排序

B.

直接插入排序

C.

快速排序

D.

归并排序

第 10 题    单选题

由数字112488所组成的不同的4位数的个数是( )

A.

104

B.

102

C.

98

D.

100

第 11 题    单选题

设变量xfloat型且已赋值,则以下语句中能将x中的数值保留到小数点后两位,并将第三位四舍五入的是( )

A.

X=(x*100+0.5)/100.0

B.

x=(int)(x*100+0.5)/100.0

C.

x=(x/100+0.5)*100.0

D.

x=x*100+0.5/100.0

第 12 题    单选题

编译器的功能是( )

A.

将源程序重新组合

B.

将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)

C.

将低级语言翻译成高级语言

D.

将一种编程语言翻译成自然语言

第 13 题    单选题

二进制数11 1011 1001 0111  01 0110 1110 1011 进行逻辑或运算的结果是( )

A.

11 1111 1101

B.

11 1111 1111 1101

C.

0 1111 1111 1111

D.

11 1111 1111 1111

第 14 题    单选题

下列属于图像文件格式的有( )

A.

WMV 

B.

MPEG

C.

.JPEG

D.

AVI

第 15 题    单选题

有正实数构成的数字三角形排列形式如图所示。第一行的数为a2,1,a2,2,第n行的数 为an,1,an,2,...,an,n。从a1,1开始,每一行的数ai,j只有两条边可以分别通向下一行的两个 数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1,an,2,...,an,n中某个数的路径,使得 该路径上的数之和最大。令C[i][j]是从a1,1到ai,j的路径上的数的最大和,并且 C[i][0]= C[0][j]=0,则C[i][j]=( ) 

A.

mac{C[i-1][j-1],C[i-1][j]}+ ai,j

B.

C[i-1][j-1]+C[i-1][j]

C.

max{C[i-1][j-1],c[i-1][j]}+1

D.

max{C[i][j-1],C[i-1][j]}+ ai,j

阅读程序
第 16-21 题    组合题

2019年CSP-S1提高组初赛阅读程序题:

#include <cstdio>
using namespace std;
int n;
int a[100];
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d\n", ans);
    }
    return 0;
}
第16题 判断

16行输出ans时,ans的值一定大于i( )

A.
正确
B.
错误
第17题 判断

程序输出的ans小于等于n( )

A.
正确
B.
错误
第18题 判断

若将第12行的“<”改为“!=”,程序输出的结果不会改变。( )

A.
正确
B.
错误
第19题 判断

当程序执行到第16行时,若ans-i>2,则a[i+1]≦a[i]( )

A.
正确
B.
错误
第20题 单选

若输入的a数组是一个严格单调递增的数列,此程序的时间复杂度是( )

A.

 0(log n)

B.

0(n2

C.

0(nlog n)

D.

0(n)

第21题 单选

最坏情况下,此程序的时间复杂度是( )

A.

0(n2)

B.

0(log n)

C.

0(n)

D.

0(nlog n)

第 22-27 题    组合题

2019年CSP-S1提高组初赛阅读程序题:

#include <iostream>
using namespace std;
 
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];
 
int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}
第22题 判断

输入的ab值应在[0n-1]的范围内。( ) 

A.
正确
B.
错误
第23题 判断

16行改成“fa[i]=0;”, 不影响程序运行结果。( ) 

A.
正确
B.
错误
第24题 判断
若输入的a和b值均在[0, n-1]的范围内,则对于任意0≤i<n,都有0≤fa[i]<n。( )
A.
正确
B.
错误
第25题 判断
若输入的a和b值均在[0,n-1]的范围内,则对于任意≤i<n,都有≤cnt[i] ≤n。( )
A.
正确
B.
错误
第26题 单选
当n等于50时,若a、b的值都在[0,49]的范围内,且在第25行时总是不等于y,那么输出为( ) 
A.

1276

B.

1176

C.

1225

D.

1250

第27题 单选

此程序的时间复杂度是( )

A.

O(n)

B.

O(log n)

C.

O(n^2) 

D.

O(n log n)

第 28-33 题    组合题

2019年CSP-S1提高组初赛阅读程序题:t是s的子序列的意思是:从s中删去若干个字符,可以得到t;特别的,如果s=t,那么t也是s的子序列;空串是任何串的子序列。例如:"acd"是“abcde”的子序列,“acd"是“acd”的子序列,但"adc” 不是“abcde”的子序列。

s[x..y]表示s[x] ...s[y]共y-x+l个字符构成的字符串,若x>y则 s[x..y]是空串。t[x..y]同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];
 
int main() {
    cin >> s >> t;
    int slen = s.length(), tlen = t.length();
    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
    }
    for (int  i = slen - 1 , j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t [j]) --j;
        suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
    }
    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){
        while(j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

提示:
t[0..pre[i]-1]
s[0..i]的子序列; t[suf[i]+1..tlen-1]s[i..slen-1]的子序列

第28题 判断

程序输出时,suf数组满足:对任意0≤i<slensuf[i] ≤suf[i+1].( )

A.
正确
B.
错误
第29题 判断

ts的子序列时,输出一定不为0.( ) 

A.
正确
B.
错误
第30题 判断

程序运行到第23行时,“j-i-1”一定不小于0.( ) 

A.
正确
B.
错误
第31题 判断

ts的子序列时,pre数组和suf数组满足:对任意0≤i<slenpre[i]>suf[i+1].( )

A.
正确
B.
错误
第32题 单选

tlen=10,输出为0,则slen最小为( )

A.

10

B.

12

C.

0

D.

1

第33题 单选

tlen=10,输出为2,则slen最小为( )

A.

0

B.

10

C.

12

D.

1

完善程序
第 34-38 题    组合题

(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的 经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的 值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个 新技术。

输入第一行有两个数,分别为新技术个数n(1≤n≤103),以及已有经验值(≤10^7). 接下来n行。第i行的两个整数,分别表示学习第i个技术所需的最低经验值(≤10^7),以及学会第i个技 术后可获得的经验值(≤10^4)。 接下来n行。第i行的第一个数mi(0≤mi<n),表示第i个技术的相关技术数量。紧跟着m个两两不同的 数,表示第i个技术的相关技术编号,输出最多能学会的新技术个数。

下面的程序已O(n^2)的时间复杂完成这个问题,试补全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;
 
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int points;
int threshold[maxn], bonus[maxn];
 
bool find(){
    int target = -1;
    for (int i = 1; i <= n; ++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target == -1)
        return false;
    unlock[target] = -1;
    ③
    for (int i = 0; i < cnt[target]; ++i)
        ④
    return true;
}
 
int main(){
    scanf("%d%d", &n, &points);
    for (int i = 1; i <= n; ++i){
        cnt[i] = 0;
        scanf("%d%d", &threshold[i], &bonus[i]);
    }
    for (int i = 1; i <= n; ++i){
        int m;
        scanf("%d", &m);
        ⑤
        for (int j = 0; j < m; ++j){
            int fa;
            scanf("%d", &fa);
            child[fa][cnt[fa]] = i;
            ++cnt[fa];
        }
    }
    int ans = 0;
    while(find())
        ++ans;
    printf("%d\n", ans);
    return 0;
}
第34题 单选

1处应填( )

A.

unlock[i]<=0

B.

unlock[i]>=0

C.

unlock[i]==0

D.

unlock[i]==-1

第35题 单选

 ②处应填( )

A.

 threshold[i]>points

B.

threshold[i]>=points

C.

points>threshold[i]

D.

points>=threshold[i]

第36题 单选

③处应填( )

A.

target = -1

B.

- -cnt[target]

C.

bbonus[target]

D.

points += bonus[target] 

第37题 单选

④处应填( )

A.

cnt [child[target][i]] -=1

B.

cnt [child[target][i]] =0

C.

unlock[child[target][i]] -= 1

D.

unlock[child[target][i]] =0

第38题 单选

⑤处应填( )

A.

unlock[i] = cnt[i] 

B.

unlock[i] =m

C.

unlock[i] = 0

D.

unlock[i] =-1

第 39-43 题    组合题

(取石子) Alice和Bob两个人在玩取石子游戏,他们制定了n条取石子的规则,第i条规则为:如果剩 余的石子个数大于等于a[i]且大于等于b[i],那么她们可以取走b[i]个石子。他们轮流取石子。如果轮到某 个人取石子,而她们无法按照任何规则取走石子,那么他就输了,一开始石子有m个。请问先取石子的 人是否有必胜的方法? 

输入第一行有两个正整数,分别为规则个数n(1≤n≤64),以及石子个数m(≤10^7)。 接下来n行。第i行有两个正整数a[i]和b[i]。(1≤a[i]≤10^7,1b[i]≤64) 如果先取石子的人必胜,那么输出“Win”,否则输出“Loss” 

提示: 可以使用动态规划解决这个问题。由于b[i]不超过,所以可以使用位无符号整数去压缩必要的状态。 Status是胜负状态的二进制压缩,trans是状态转移的二进制压缩。

试补全程序。

代码说明:
“~”表示二进制补码运算符,它将每个二进制位的0变成1、1变为0; 而“^”表示二进制异或运算符,它将两个参与运算的数重的每个对应的二进制位一一进行比较,若两个二 进制位相同,则运算结果的对应二进制位为0,反之为1。
U11标识符表示它前面的数字是unsigned long long 类型。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

#include <cstdio>
#include<algorithm>
using namespace std;
 
const int maxn = 64;
 
int n, m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win;
 
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            if (aa[i] > a[j]){
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    status = ①;
    trans = 0;
    for(int i = 1, j = 0; i <= m; ++i){
        while (j < n && ②){
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }
    puts(win ? "Win" : "Loss");
    return 0;
}


第39题 单选
①处应填( )
A.

0

B.

~0ull

C.

~0ull^1 

D.

1

第40题 单选
②处应填( )
A.
a[j]< i
B.
a[j] ==i
C.
a[j] !=i
D.
a[j] >i
第41题 单选
③处应填( )
A.
 trans |= 1ull <<(b[j] - 1)
B.
status |=1ull << (b[j]- 1)
C.
status +=1ull << (b[j]-1)
D.
trans +=1ull<< (b[j]-1)
第42题 单选
④处应填( )
A.
~status | trans
B.
status & trans
C.
status | trans
D.
~status & trans
第43题 单选
 ⑤处应填( )
A.
trans = status | trans ^win
B.
 status = trans >> 1^win
C.
trans = status ^trans |win
D.
status =status <<1^win
答题卡
选择题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
阅读程序
完善程序
题目总数:20
总分数:100
时间:120分钟