第1題

中國的國家頂級域名是( )。

第2題

二進制數(shù) 11 1011 1001 0111 和 01 0110 1110 1011 進行邏輯與運算的結(jié)果是( )。

第3題

一個 32 位整型變量占用( )個字節(jié)。

第4題

若有如下程序段，其中 s、a、b、c 均已定義為整型變量，且 a、c 均已賦值（c > 0）

s = a;
for (b = 1; b <= c; b++) s = s - 1;

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

第5題

設(shè)有 100 個已排好序的數(shù)據(jù)元素，采用折半查找時，最大比較次數(shù)為( )。

第6題

鏈表不具有的特點是( )。

第7題

把 8 個同樣的球放在 5 個同樣的袋子里，允許有的袋子空著不放，問共有多少種不同的分法？( )

提示：如果 8 個球都放在一個袋子里，無論是哪個袋子，都只算同一種分法

第8題

一棵二叉樹如右圖所示，若采用順序存儲結(jié)構(gòu)，即用一維數(shù)組元素存儲該二叉樹中的結(jié)點（根結(jié)點的下標為 1，若某結(jié)點的下標為 i，則其左孩子位于下標 2i 處、右孩子位于下標 2i+1 處），則該數(shù)組的最大下標至少為( )。

第9題

100 以內(nèi)的最大素數(shù)是( )。

第10題

319 和 377 的最大公約數(shù)是( )。

第11題

新學(xué)期開學(xué)了，小胖想減肥，健身教練給小胖制定了兩個訓(xùn)練方案。方案一：每次連續(xù)跑 3 公里可以消耗 300 千卡（耗時半小時）；方案二：每次連續(xù)跑 5 公里可以消耗 600 千卡（耗時 1 小時）。小胖每周周一到周四能抽出半小時跑步，周五到周日能抽出一小時跑步。另外，教練建議小胖每周最多跑 21 公里，否則會損傷膝蓋，每周最多通過跑步消耗多少千卡( )。

第12題

一副紙牌除掉大小王有 52 張牌，四種花色，每種花色 13 張。假設(shè)從這 52 張牌中隨機抽取 13 張紙牌，則至少( )張牌的花色一致。

第13題

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

第14題

假設(shè)一棵二叉樹的后序遍歷序列為 DGJHEBIFCA，中序遍歷序列為 DBGEHJACIF，則其前序遍歷序列為( )。

第15題

以下哪個獎項是計算機科學(xué)領(lǐng)域的最高獎？( )

第16題

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

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

第17題

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

若將第 8 行的 i = 1 改為 i = 0，程序運行時會發(fā)生錯誤。

第18題

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

若將第 8 行的 i <= n 改為 i * i <= n，程序運行時結(jié)果不會改變。

第19題

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

若輸入的字符串全部由大寫字母組成，那么輸出的字符串就跟輸入的字符串一樣。

第20題

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

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

第21題

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

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

第22題

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

假設(shè)輸入的 n 和 m 都是正整數(shù)，x 和 y 都是在[1,n] 的范圍內(nèi)的整數(shù)。

當 m > 0時輸出的值一定小于2n。

第23題

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

假設(shè)輸入的 n 和 m 都是正整數(shù)，x 和 y 都是在 [1,n] 的范圍內(nèi)的整數(shù)。

執(zhí)行完第27 行的 ++ans 時，ans 一定是偶數(shù)。

第24題

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

假設(shè)輸入的 n 和 m 都是正整數(shù)，x 和 y 都是在 [1,n] 的范圍內(nèi)的整數(shù)。

a[i] 和 b[i] 不可能同時大于 0。

第25題

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

假設(shè)輸入的 n 和 m 都是正整數(shù)，x 和 y都是在[1,n] 的范圍內(nèi)的整數(shù)。

若程序執(zhí)行到第 13 行時，x 總是小于 y，那么第15 行不會被執(zhí)行。

第26題

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

若 m 個 x 兩兩不同，且 m 個 y 兩兩不同，則輸出的值為（ ）

第27題

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

若 m 個 x 兩兩不同，且 m 個 y 都相等，則輸出的值為（ ）

第28題

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

如果 a 數(shù)組有重復(fù)的數(shù)字，則程序運行時會發(fā)生錯誤。

第29題

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

如果 b 數(shù)組全為 0 則輸出為 0。

第30題

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

當 n=100 時，最壞情況下，與第 12 行的比較運算執(zhí)行的次數(shù)最接近的是：( )

第31題

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

當 n=100 時，最好情況下，與第 12 行的比較運算執(zhí)行的次數(shù)最接近的是：( )

第32題

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

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

第33題

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

當 n=100 時，若 b 數(shù)組滿足，對于任意0≤i<n，都有 b[i]=1，那么輸出最小為( )

第34題

（矩陣變換）有一個奇幻的矩陣，在不停的變幻，其變幻方式為：數(shù)字 0 變成矩陣 ，數(shù)字 1 變成矩陣 。最初該矩陣只有一個元素 0，變幻 n 次后，矩陣會變成什么樣？

例如，矩陣最初為：[0]；矩陣變幻一次后：；矩陣變幻 2 次后：。

輸入一行一個不超過 10 的正整數(shù) n。輸出變幻 n 次后的矩陣。

試補全程序。

提示：

<< 表示二進制左移運算符，例如 (11)₂<<2=(1100)₂。

而 ^ 表示二進制異或運算符，它將兩個運算的數(shù)中的每個對應(yīng)的二進制位一一進行比較，若兩個二進制位相同，則運算結(jié)果的對應(yīng)二進制位為 0，反之為 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;
}

① 處應(yīng)填（ ）

第35題

（矩陣變換）有一個奇幻的矩陣，在不停的變幻，其變幻方式為：數(shù)字 0 變成矩陣 ，數(shù)字 1 變成矩陣 。最初該矩陣只有一個元素 0，變幻 n 次后，矩陣會變成什么樣？

例如，矩陣最初為：[0]；矩陣變幻一次后：；矩陣變幻 2 次后：。

輸入一行一個不超過 10 的正整數(shù) n。輸出變幻 n 次后的矩陣。

試補全程序。

提示：

<< 表示二進制左移運算符，例如 (11)2<<2=(1100)2。

而 ^ 表示二進制異或運算符，它將兩個運算的數(shù)中的每個對應(yīng)的二進制位一一進行比較，若兩個二進制位相同，則運算結(jié)果的對應(yīng)二進制位為 0，反之為 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;
}

② 處應(yīng)填（ ）

第36題

（矩陣變換）有一個奇幻的矩陣，在不停的變幻，其變幻方式為：數(shù)字 0 變成矩陣 ，數(shù)字 1 變成矩陣 。最初該矩陣只有一個元素 0，變幻 n 次后，矩陣會變成什么樣？

例如，矩陣最初為：[0]；矩陣變幻一次后：；矩陣變幻 2 次后：。

輸入一行一個不超過 10 的正整數(shù) n。輸出變幻 n 次后的矩陣。

試補全程序。

提示：

<< 表示二進制左移運算符，例如 (11)2<<2=(1100)2。

而 ^ 表示二進制異或運算符，它將兩個運算的數(shù)中的每個對應(yīng)的二進制位一一進行比較，若兩個二進制位相同，則運算結(jié)果的對應(yīng)二進制位為 0，反之為 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;
}

③ 處應(yīng)填（ ）

第37題

（矩陣變換）有一個奇幻的矩陣，在不停的變幻，其變幻方式為：數(shù)字 0 變成矩陣 ，數(shù)字 1 變成矩陣 。最初該矩陣只有一個元素 0，變幻 n 次后，矩陣會變成什么樣？

例如，矩陣最初為：[0]；矩陣變幻一次后：；矩陣變幻 2 次后：。

輸入一行一個不超過 10 的正整數(shù) n。輸出變幻 n 次后的矩陣。

試補全程序。

提示：

<< 表示二進制左移運算符，例如 (11)2<<2=(1100)2。

而 ^ 表示二進制異或運算符，它將兩個運算的數(shù)中的每個對應(yīng)的二進制位一一進行比較，若兩個二進制位相同，則運算結(jié)果的對應(yīng)二進制位為 0，反之為 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;
}

④ 處應(yīng)填（ ）

第38題

（矩陣變換）有一個奇幻的矩陣，在不停的變幻，其變幻方式為：數(shù)字 0 變成矩陣 ，數(shù)字 1 變成矩陣 。最初該矩陣只有一個元素 0，變幻 n 次后，矩陣會變成什么樣？

例如，矩陣最初為：[0]；矩陣變幻一次后：；矩陣變幻 2 次后：。

輸入一行一個不超過 10 的正整數(shù) n。輸出變幻 n 次后的矩陣。

試補全程序。

提示：

<< 表示二進制左移運算符，例如 (11)2<<2=(1100)2。

而 ^ 表示二進制異或運算符，它將兩個運算的數(shù)中的每個對應(yīng)的二進制位一一進行比較，若兩個二進制位相同，則運算結(jié)果的對應(yīng)二進制位為 0，反之為 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;
}

⑤處應(yīng)填（ ）

第39題

（計數(shù)排序）計數(shù)排序是一個廣泛使用的排序方法。下面的程序使用雙關(guān)鍵字計數(shù)排序，對 n 對 10000 以內(nèi)的整數(shù)，從小到大排序。

例如有三對整數(shù)（3，4）、（2，4）、（3，3），那么排序之后應(yīng)該是（2，4）、（3，3）、（3，4）。

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

數(shù)據(jù)范圍≤n≤10⁷,1≤a[i],b[i]≤10⁴。

提示：應(yīng)先對第二關(guān)鍵字排序，再對第一關(guān)鍵字排序。數(shù)組 ord_____ 存儲第二關(guān)鍵字排序的結(jié)果，數(shù)組 res_____ 存儲雙關(guān)鍵字排序的結(jié)果。

試補全程序

#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 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 記錄初步排序結(jié)果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 記錄最終排序結(jié)果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);

    return 0;
}

① 處應(yīng)填（ ）

第40題

（計數(shù)排序）計數(shù)排序是一個廣泛使用的排序方法。下面的程序使用雙關(guān)鍵字計數(shù)排序，對 n 對 10000 以內(nèi)的整數(shù)，從小到大排序。

例如有三對整數(shù)（3，4）、（2，4）、（3，3），那么排序之后應(yīng)該是（2，4）、（3，3）、（3，4）。

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

數(shù)據(jù)范圍≤n≤107,1≤a[i],b[i]≤104。

提示：應(yīng)先對第二關(guān)鍵字排序，再對第一關(guān)鍵字排序。數(shù)組 ord_____ 存儲第二關(guān)鍵字排序的結(jié)果，數(shù)組 res_____ 存儲雙關(guān)鍵字排序的結(jié)果。

試補全程序

#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 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 記錄初步排序結(jié)果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 記錄最終排序結(jié)果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);
    return 0;
}

② 處應(yīng)填（ ）

第41題

（計數(shù)排序）計數(shù)排序是一個廣泛使用的排序方法。下面的程序使用雙關(guān)鍵字計數(shù)排序，對 n 對 10000 以內(nèi)的整數(shù)，從小到大排序。

例如有三對整數(shù)（3，4）、（2，4）、（3，3），那么排序之后應(yīng)該是（2，4）、（3，3）、（3，4）。

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

數(shù)據(jù)范圍≤n≤107,1≤a[i],b[i]≤104。

提示：應(yīng)先對第二關(guān)鍵字排序，再對第一關(guān)鍵字排序。數(shù)組 ord_____ 存儲第二關(guān)鍵字排序的結(jié)果，數(shù)組 res_____ 存儲雙關(guān)鍵字排序的結(jié)果。

試補全程序

#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 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 記錄初步排序結(jié)果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 記錄最終排序結(jié)果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);
    return 0;
}

③ 處應(yīng)填（ ）

第42題

（計數(shù)排序）計數(shù)排序是一個廣泛使用的排序方法。下面的程序使用雙關(guān)鍵字計數(shù)排序，對 n 對 10000 以內(nèi)的整數(shù)，從小到大排序。

例如有三對整數(shù)（3，4）、（2，4）、（3，3），那么排序之后應(yīng)該是（2，4）、（3，3）、（3，4）。

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

數(shù)據(jù)范圍≤n≤107,1≤a[i],b[i]≤104。

提示：應(yīng)先對第二關(guān)鍵字排序，再對第一關(guān)鍵字排序。數(shù)組 ord_____ 存儲第二關(guān)鍵字排序的結(jié)果，數(shù)組 res_____ 存儲雙關(guān)鍵字排序的結(jié)果。

試補全程序

#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 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 記錄初步排序結(jié)果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 記錄最終排序結(jié)果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);
    return 0;
}

④ 處應(yīng)填（ ）

第43題

（計數(shù)排序）計數(shù)排序是一個廣泛使用的排序方法。下面的程序使用雙關(guān)鍵字計數(shù)排序，對 n 對 10000 以內(nèi)的整數(shù)，從小到大排序。

例如有三對整數(shù)（3，4）、（2，4）、（3，3），那么排序之后應(yīng)該是（2，4）、（3，3）、（3，4）。

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

數(shù)據(jù)范圍≤n≤107,1≤a[i],b[i]≤104。

提示：應(yīng)先對第二關(guān)鍵字排序，再對第一關(guān)鍵字排序。數(shù)組 ord_____ 存儲第二關(guān)鍵字排序的結(jié)果，數(shù)組 res_____ 存儲雙關(guān)鍵字排序的結(jié)果。

試補全程序

#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 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 記錄初步排序結(jié)果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 數(shù)組統(tǒng)計數(shù)量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 記錄最終排序結(jié)果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);
    return 0;
}

⑤處應(yīng)填（ ）