真題解析Ⅰ | CCF CSP-J 2019 入門級 C++語言真題及答案(附信奧真題庫)

2019CCF非專業級別軟體能力認證第一輪

（CSP-J）入門級C++語言試題A卷

（B卷與A卷僅順序不同）

認證時間：2019年10月19日

考生注意事項：

1、試題紙共有9頁，答題紙共有1頁，滿分100分。請在答題紙上作答，寫在試題紙上的一律無效

2、不得使用任何電子設備（如計算器、手機、電子詞典等）或查閱任何書籍資料。

一、單項選擇題（共15題，每題2分，共計30分；每題有且僅有一個正確選項）

1.中國的國家頂級域名是()

A.  .cn        B.   .ch         C.  .chn         D.   .China

答案：A

試題分析：常識，詳情見普及組課程105課時。

2.二進位數11 1011 1001 0111和01 0110 1110 1011進行邏輯與運算的結果

是()

A.01 0010 1000 1011      B.01 0010 1001 0011

C.0l 0010 1000 0001      D.01 0010 1000 0011

答案：D

試題分析：邏輯與，若且唯若2個數對應位都為1的，答案才為1，詳情見普及組課程63課時。

3.一個32位整型變量佔用()個字節。

A. 32        B.128         C. 4         D.8

答案：C

試題分析：1Byte(字節) = 8 bit(位)  32/8=4 詳情見普及組課程103課時。

4.若有如下程序段,其中s、a、b、c均已定義為整型變量,且a、c均已賦值(c

大於0)

s=a

for(b= 1: b< c: b++)s=s-1

則與上述程序段功能等價的賦值語句是()

A.s=a-c;          B.s=a-b;      C.s=s-c;          D.s=b-c;

答案：A

試題分析：s初始化為a; for循環執行c次，每次s減1，共減c，所以s=a-c

考察for循環的應用，詳情見普及組課程16課時。

5.設有100個已排好序的數據元素,採用折半查找時,最大比較次數為()

A.7        B.10       C.6        D.8

答案：A

試題分析：折半查找，首先將待查記錄所在範圍縮小一半，然後再縮小一半，即對100個元素進行折半查找，第一次比較範圍縮小到50，第二次縮小到25，第三次縮小到17，第四次縮小到7，第五次縮小到4，第六次縮小到2，最多七次就可以查找到所要元素。詳情見普及組課程第106課時。

6.鍊表不具有的特點是()

A.插入刪除不需要移動元素        B.不必事先估計存儲空間

C.所需空間與線性表長度成正比    D.可隨機訪問任一元素

答案：D

試題分析：鍊表沒有下標，不可隨機訪問詳情見普及組第108課時。

7.把8個同樣的球放在5個同樣的袋子裡,允許有的袋子空著不放,問共有多少種不同的分法?()提示:如果8個球都放在一個袋子裡,無論是哪個袋子,都只算同一種分法。

A.22   B.24   C.18   D.20

答案：C

試題分析：把整數8拆分成5個數字之和，允許有0，我們可以按照非零數字個數進行枚舉，1個：1種，2個：4種，3個：5種，4個：5種，5個：3種，累加起來一共18種。詳情見普及組課 程109課時。

8.一棵二叉樹如右圖所示,若採用順序存儲結構,即用一維數組元素存儲該二叉樹中的結點(根結點的下標為1,若某結點的下標為i,則其左孩子位於下標2i處、右孩子位於下標2i+1處),則該數組的最大下標至少為()

A.6    B.10   C.15   D.12

答案：C

試題分析：根據題目描述直接計算就可以了，（（1*2+1）*2+1）*2+1=15

詳情見普及 組課程99課時。

9.100以內最大的素數是()。

A.89   B.97   C.91   D.93

答案：B

試題分析：97最大且為素數，詳情見普及組課程123課時。

10.319和377的最大公約數是()。

A.27   B.33   C.29   D.31

答案：C

試題分析：使用輾轉相除法計算(319,377)=(319,58)=(58,29) = 29

詳 情見普及組課程第121課時。

11.新學期開學了,小胖想減肥,健身教練給小胖制定了兩個訓練方案。方案一：

每次連續跑3公裡可以消耗300千卡(耗時半小時):方案二:每次連續跑5公裡可以消耗600千卡(耗時1小時)。小胖每周周一到周四能抽出半小時跑步,周五到周日能抽出一小時跑步。另外,教練建議小胖每周最多跑21公裡,否則會損傷膝蓋。請問如果小胖想嚴格執行教練的訓練方案,並且不想損傷膝蓋,每周最多通過跑步消耗多少千卡?()

A.3000     B.2500     C.2400     D.2520

答案：C

試題分析：設方案1,2各i,j天，由題意，3*i+5*j<=21,i+j<=7,i<=3.求300*i+600*j的最大值。枚舉所有情況當i=2,j=3時，最大值2400。

12.一副紙牌除掉大小王有52張牌,四種花色,每種花色13張。假設從這52張

牌中隨機抽取13張紙牌,則至少()張牌的花色一致

A.4    B.2    C.3    D.5

答案：A

試題分析：抽屜原理，13張牌最壞情況就是4種花色分別為3,3,3,4張，也就是至少4張一樣花色。

13.一些數字可以顛倒過來看,例如0、1、8顛倒過來還是本身,6顛倒過來是9,9顛倒過來看還是6,其他數字顛倒過來都不構成數字。類似的,一些多位數也可以顛倒過來看,比如106顛倒過來是901。假設某個城市的車牌只由5位數字組成,每一位都可以取0到9。請問這個城市最多有多少個車牌倒過來恰好還是原來的車牌?()

A.60       B.125      C.75       D.100

答案：C

試題分析：考察乘法原理，第1，2位有5種選法（0，1，6，8，9），第三位有三種0，1，8，第4，5位由前兩位決定，所以答案位5*5*3=75。

14.假設一棵二叉樹的後序遍歷序列為 DGJHEBIFCA，中序遍歷序列為 DBGEHJACIF，則其前序遍歷序列為( )。

A. ABCDEFGHIJ       B. ABDEGHJCFI 

C. ABDEGJHCFI      D. ABDEGHJFIC

答案：B

試題分析：考察二叉樹的遍歷，後序遍歷決定根是A，中序遍歷中看A的左邊DBGEH是左子樹，右邊CIF是右子樹，依次類推可畫出完整的樹，再求先序遍歷，詳情見普及組課程100課時。

15.以下哪個獎項是計算機科學領域的最高獎?()

A.圖靈獎   B.魯班獎   C.諾貝爾獎D.普立茲獎

答案：A

試題分析：考察常識問題，並且是一道原題。詳情見普及組課程102課時。

二、閱讀程序(程序輸入不超過數組或字符串定義的範圍:判斷題正確填√,錯誤填×:除特殊說明外,判斷題1.5分,選擇題3分,共計40分)

1.

#include <cstdio>

#include <cstring>

using namespace std;

char st[100];

int main() {

    scanf("%s", st);

    int n = strlen(st);

    for (int i = 1; i <= n; ++i) {

        if (n % i == 0) {

            char c = st[i - 1];

            if (c >= 'a')

                st[i - 1] = c - 'a' + 'A';

        }

    }

    printf("%s", st);

    return 0;

}

判斷題

1)輸入的字符串只能由小寫字母或大寫字母組成。()

答案：×

試題分析：題目沒說，可以輸入包含其他字符的字符串。

2)若將第8行的「i=1」改為「i=0」,程序運行時會發生錯誤()

答案：√

試題分析：不能對0取餘操作，錯誤。

3)若將第8行的「i<=n」改為「i*i<=n」,程序運行結果不會改變()

答案：×

試題分析：求約數不是判斷質數，i*i<=n只能取到n的前半部分約數。

4)若輸入的字符串全部由大寫字母組成,那麼輸出的字符串就跟輸入的字符串一樣。()

答案：√

試題分析：按題意說明即可判斷。

選擇題

5)若輸入的字符串長度為18,那麼輸入的字符串跟輸出的字符串相比至多有()個字符不同。

A.18       B.6        C.10       D.1

答案：B

試題分析：約數個數定理求約數個數。18的約數是：1，2，3，6，9，18。所以最多判定6次。

6)若輸入的字符串長度為(),那麼輸入的字符串跟輸出的字符申相比,至多有36個字符不同。

A.36       B.100000      C.1    D.128

答案：B

試題分析：和上題同理。枚舉4個選項。36有9個約數，1有1個約數，128有8個約數。選B。100000有36個約數。

2.

#include<cstdio>

using namespace std;

int n, m;

int a[100], b[100];

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i)

        a[i] = b[i] = 0;

    for (int i = 1; i <= m; ++i) {

        int x, y;

        scanf("%d%d", &x, &y);

        if (a[x] < y && b[y] < x) {

            if (a[x] > 0)

                b[a[x]] = 0;

            if (b[y] > 0)

                a[b[y]] = 0;

            a[x] = y;

            b[y] = x;

        }

    }

    int ans = 0;

    for (int i = 1; i <= n; ++i) {

        if (a[i] == 0)

            ++ans;

        if (b[i] == 0)

            ++ans;

    }

    printf("%d", ans);

    return 0;

}

假設輸入的n和m都是正整數,x和y都是在[1,n]的範圍內的整數,完成下面的判斷題和單選題

判斷題

1)當m>0時,輸出的值一定小於2n。()

答案：√

試題分析：按照題意，a數組和b數組賦值為0，a[x] < y && b[y] < x成立，累計計算求和，最終結果肯定小於2n。

2)執行完第27行的「++ans」時,ans一定是偶數。()

答案：×

試題分析：不一定，可以舉例求出ans不是偶數的情況。

3) a[i]和b[i]不可能同時大於0。()

答案：×

試題分析：舉例即可找到反例。

4)若程序執行到第13行時,x總是小於y,那麼第15行不會被執行。()

答案：×

試題分析：同樣舉例可以實現。

選擇題

5)若m個x兩兩不同,且m個y兩兩不同,則輸出的值為()

A. 2n-2m      B.2n+2     C.2n-2     D.2n

答案：A

試題分析：根據題意，m次循環中會有2m個位置的值會變化，ans=2n-2m。

6)若m個x兩兩不同,且m個y都相等,則輸出的值為()

A.2n-2        B.2n       C.2m       D.2n-2m

答案：A

試題分析：如果m個x各不相同，循環裡面的if都不會執行。對數組a，b賦值，只修改了2個位置。也可舉例

3 3

3 3

2 3

1 3

答案是4。

3.

#include <iostream>

using namespace std;

const int maxn = 10000;

int n;

int a[maxn];

int b[maxn];

int f(int l, int r, int depth) {

    if (l > r)

        return 0;

    int min = maxn, mink;

    for (int i = l; i <= r; ++i) {

        if (min > a[i]) {

            min = a[i];

            mink = i;

        }

    }

    int lres = f(l, mink - 1, depth + 1);

    int rres = f(mink + 1, r, depth + 1);

    return lres + rres + depth * b[mink];

}

int main() {

    cin >> n;

    for (int i = 0; i < n; ++i)

        cin >> a[i];

    for (int i = 0; i < n; ++i)

        cin >> b[i];

    cout << f(0, n - 1, 1) << endl;

    return 0;

}

分析：分治算法。左右兩邊找答案，然後求運算。

判斷題

1)如果a數組有重複的數字,則程序運行時會發生錯誤。()

答案：×

試題分析：分析代碼，有重複的數字不會導致程序運行出錯。

2)如果b數組全為0,則輸出為0.()

答案：√

試題分析：如果b數組是0，遞歸推出條件l>r返回0，根據return lres + rres + depth * b[mink];返回結果總是0。

選擇題

3)當n=100時,最壞情況下,與第12行的比較運算執行的次數最接近的是（）

A.5000     B.6000     C.6    D.100

答案：A

試題分析：最壞情況下a有序，總是求mink和min最小值，需要判斷100+99+98+...+2+1 =5050，選A。

4)當n=100時,最好情況下,與第12行的比較運算執行的次數最接近的是（）

A.100      B.6        C.5000     D.600

答案：D

試題分析：最好情況每次都二分，總次數為100，層數為 6<log2100<7，總次數約為[6*100,7*100]，選D。

5)當n=10時,若b數組滿足,對任意0≤i<n,都有b[i]=i+1,那麼輸出最大為()

A.386      B.383      C.384      D.385

答案：D

試題分析：n=10，深度最大是10，根據代碼：1*b[0]+2*b[1]+...+10*b[9]=1*1+2*2+3*3+...+10*10=385。

6)(4分)當n=100時,若b數組滿足,對任意0≤i<n,都有b[i]=1, 那麼輸出最小為()

A.582      B.580      C.579      D.581

答案：B

試題分析：b[i]=1,即求一個100節點的完全二叉樹，節點深度之和最小為多少。畫圖後，計算為

1*1+2*2+4*3+8*4+16*5+32*6+37*7=580

三、完善程序(單選題,每小題3分,共計30分)

1.

#include <cstdio>

using namespace std;

int n;

const int max_size = 1 << 10;

int res[max_size][max_size];

void recursive(int x, int y, int n, int t) {

    if (n == 0) {

        res[x][y] = ①;

        return;

    }

    int step = 1 << (n - 1);

    recursive(②, n - 1, t);

    recursive(x, y + step, n - 1, t);

    recursive(x + step, y, n - 1, t);

    recursive(③, n - 1, !t);

}

int main() {

    scanf("%d", &n);

    recursive(0, 0, ④);

    int size = ⑤;

    for (int i = 0; i < size; i++) {

        for (int j = 0; j < size; j++)

            printf("%d", res[i][j]);

        puts("");

    }

    return 0;

}

① 處應填（ ）

A.n%2          B.0        C.t        D.1

答案：C

試題分析：（猜的話，變量t沒有用過。）遞歸退出判斷，參數t的賦值能發現是經常做取反操作。賦值和n沒有必然聯繫，錯誤。選C。

② 處應填（ ）

A.x-step,y-step          B.x,y-step

C.x-step,y               D.x,y

答案：D

試題分析：四個方向，x，y是當前坐標。根據下面參數，參數分別是x,y;x,y+step;x+step,y;x+step,y+step。

③ 處應填（ ）

A. x-step,y-step         B. x+step,y+step         

C. x-step,y                 D. x,y-step

答案：B

④ 處應填（ ）

A.n-1,n%2         B.n,0          C.n,n%2           D.n-1,0

答案：B

試題分析：第一次調用recursive函數，n是矩陣規模，初始為n，t是取反次數，所以t初始為0或者1。

1)⑤ 處應填（ ）

A.i<<(n+1)        B.1<<n         C.n+1          D.1<<(n-1)

答案：B

試題分析：size是輸出矩陣的邊長，2^n,位運算是1<<n。

2. (計數排序）計數排序是一個廣泛使用的排序方法。下面的程序使用雙關鍵字計數排序，對 n 對 10000 以內的整數，從小達到排序。

例如有三對整數（3，4）、（2，4）、（3，3），那麼排序之後應該是（2，4）、（3，3）、（3，4）。

輸入第一行為 n，接下來 n 行，第 i 行有兩個數 a[i] 和 b[i]，分別表示第 i 對整數的第一關鍵字和第二關關鍵字。

從小到大排序後輸出。

提示：應先對第二關鍵字排序，再對第一關鍵字排序。數組 ord[]存儲第二關鍵字排序的結果，數組 res[]存儲雙關鍵字排序的結果。

試補全程序

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 10000000;

const int maxs = 10000;

int n;

unsigned a[maxn], b[maxn],res[maxn], ord[maxn];

unsigned cnt[maxs + 1];

int main() {

    scanf("%d", &n);

    for (int i = 0; i < n; ++i)

        scanf("%d%d", &a[i], &b[i]);

    memset(cnt, 0, sizeof(cnt));

    for (int i = 0; i < maxs; ++i)

        ①; // 利用 cnt 數組統計數量

    for (int i = 0; i < n; ++i)

        cnt[i + 1] += cnt[i];

    for (int i = 0; i < n; ++i)

        ②; // 記錄初步排序結果

    memset(cnt, 0, sizeof(cnt));

    for (int i = 0; i < n; ++i)

        ③; // 利用 cnt 數組統計數量

    for (int i = 0; i < maxs; ++i)

        cnt[i + 1] += cnt[i];

    for (int i = n - 1; i >= 0; --i)

        ④ // 記錄最終排序結果

    for (int i = 0; i < n; i++)

        printf("%d %d", ⑤);

    return 0;

}

1)①處應填()

A.  ++cnt[1]

B. ++cnt[b[1]]

C, ++cnt[a[i]*maxs+b[i]]

D, ++cnt[a[i]]

答案：B

試題分析：提示：應先對第二關鍵字排序，再對第一關鍵字排序。排序的題做了很多，認真讀題，不是特別難的事。先對第二關鍵字進行排序，選B。

2)②處應填()

A. ord[--cnt[a[i]]]=i

B, ord[--cnt[b[i]]]=a[i]

C. ord[--cnt[a[i]]]=b[i]

D. ord[--cnt[b[i]]]=i

答案：D

試題分析：cnt[b[i]]表示第i個數按第二關鍵字排的位。ord[i]表示第i個數在原位置。

3)③處應填()

A. ++cnt[b[i]]

B. ++cnt[a[i]*maxs+ b[i]]

C, ++cnt[a[il]

D. ++cnt[i]

答案：C

試題分析：對第一關鍵字進行計數。

4)④處應填()

A. res[--cnt[a[ord[i]]]]=ord[i]

B. res[--cnt[b[ord[i]]]]=ord[i]

C. res[--cnt[b[i]]]=ord[i]

D. res[--cnt[a[i]]]=ord[i]

答案：A

試題分析：對應填空②，此處res[i]記錄第一關鍵字第i的數的原位置。

5) ⑤處應填()

A. a[i],b[i]

B. a[res[i]], b[res[i]]

C. a[ord[res[i]]], b[ord[res[i]]]

D. a[res[ord[i]]], b[res[ord[i]]]

答案：B

試題分析：res[i]記錄第i個數的原位置。

以上是2019CSP-J（入門級）C++語言試題的解題分析，參加此次考試的學員們，你們都答對了嗎？另，在後臺回復【真題】即可免費領取「信息學奧賽歷年真題資料包」哦~

CSP-J/S是CCF創辦的CSP（軟體能力認證）中面向非專業級的軟體能力認證，也就是我們熟知的信息學奧賽，不僅含金量高，而且對孩子升學有很大的幫助。

童程童美信息學奧賽課程是由專業教研團隊與北京知名學府聯合研發，課程內容循序漸進，指導學員圍繞每個考試階段的重點知識進行學習；教研團隊強大專業，授課老師經驗充足，確保準確把握競賽方向和特點，保證學員學習進度和質量，助力學員在考試中取得優異成績！

點擊【閱讀原文】

了解更多關於信息學奧賽詳情

還可免費領取

價值388元的編程體驗課

給孩子一個免費學習的機會

讓孩子離名校更進一步！