全国CCF提高组非专业级别软件能力认证第一轮 [2019年]

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

2. 下列属于图像文件格式的有（）

3. 二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑或运算的结果是（）。

4. 编译器的功能是（）

5. 设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（）

6. 由数字1, 1, 2, 4, 8, 8所组成的不同的4位数的个数是（）。

7. 排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

8. G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有 （）个顶点。

9. 一些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是 9,9颠倒过来看还是6,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901 。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（）

10. 一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）。

11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）。

12. 以下哪个结构可以用来存储图（）

13. 以下哪些算法不属于贪心算法？（）

14. 有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098, 中间一项是486,请问以下哪个数是可能的公比？（）

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

1.

#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;

}

判断题

选择题

2.

#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;

}

判断题

选择题

3. 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;

}

判断题

选择题

1. （匠人的自我修养）一个匠人决定要学习nn个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最 多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数n (l<=n<=10^3)n(l<=n<=10^3),以及己有经验值（<=10^7 ）。

接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（<=10^7）,以及学会第i个技术后可获得的经验值（<=10^4)。

接下来n行。第i行的第一个数mi （0<= mi< n）,表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号。
输出最多能学会的新技术个数。
下面的程序以(n^2)的时间复杂度完成这个问题，试补全程序。

#include<cstdio>

using namespace std;

const int maxn = 1001;



int n;

int cnt[maxn];

int child [maxn][maxn];

int unlock[maxn];

int threshold[maxn], bonus[maxn];

int points;

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;

}

选择题

2. (取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则，第i条规则为：如果剩余石子的个数大于等于a[i]且大于等于b[il， 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子， 而他无法按照任何规则取走石子，那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数n (1<=n<=64),以及石子个数 m (<=10^7)。

接下来n行。第i行有两个正整数a[i]和b[i]。(1<=a[i]<=10^7,1<=b[i]<=64)

如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”。

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

试补全程序。

代码说明：

~表示二进制补码运算符，它将每个二进制位的0变为1、1变为0;

而“^”表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为0,反之为1。

ull标识符表示它前面的数字是unsigned long long类型。

#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;

}

选择题