选择题

1. （2分）中国的国家顶级域名是：{{ select(1) }}

• .cn
• .ch
• .chn
• .china

2. （2分）下列不属于面向对象程序设计语言的是：{{ select(2) }}

• C
• C++
• Java
• C#

3. （2分）以比较作为基本运算，在N个数中找出最大数，最坏情况下所需要的最少的比较次数为：{{ select(3) }}

• N²
• N
• N-1
• N+1

4. （2分）表达式a*(b+c)*d的后缀表达式为：{{ select(4) }}

• **a+bcd
• abc+*d*
• abc+d**
• *a*+bcd

5. （2分）在8位二进制补码中，10101011表示的数是十进制下的：{{ select(5) }}

• 43
• -85
• -43
• -84

6. （2分）FTP可以用于：{{ select(6) }}

• 远程传输文件
• 发送电子邮件
• 浏览网页
• 网上聊天

7. （2分）319和377的最大公约数是：{{ select(7) }}

• 27
• 33
• 29
• 31

8. （2分）对于有n个顶点、m条边的无向联通图（m>n），需要删掉多少条边才能使其成为一棵树：{{ select(8) }}

• n-1
• m-n
• m-n-1
• m-n+1

9. （2分）如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是：{{ select(9) }}

• ABC
• CBA
• ACB
• BAC

10. （2分）以a为起点，对右边的无向图进行深度优先遍历，则b,c,d,e四个点中有可能作为最后一个遍历到的点个数为：

{{ select(10) }}

• 1
• 2
• 3
• 4

11. （2分）以A0作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是：

{{ select(11) }}

• A0,A1,A2,A3
• A0,A1,A3,A2
• A0,A2,A1,A3
• A0,A3,A1,A2

12. （2分）6个人，两个人组一队，总共组成三只不区分队伍的编号，不同的组队情况有多少种：{{ select(12) }}

• 10
• 15
• 30
• 20

13. （2分）如果根的高度为1,具有61个结点的完全二叉树的高度为：{{ select(13) }}

• 5
• 6
• 7
• 8

14. （2分）设x=true,y=true,z=false以下逻辑运算表达式值为真的是：{{ select(14) }}

• (y∨z)∧x∧z
• x∧(z∨y)∧z
• (x∧y)∧z
• (x∧y)∨(z∨x)

15. （2分）有五副不同颜色的手套（共10只手套，每副手套左右手各1只），一次性从中取6只手套，请问恰好能配成两副手套的不同取法有多少种：{{ select(15) }}

• 120
• 180
• 150
• 30

阅读理解1（12分）

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

第16题（1.5分）

输入的字符串只能由小写字母或大写字母组成。（ ）{{ select(16) }}

• 正确
• 错误

第17题（1.5分）

若将第8行的"i=1"改为"i=0",程序运行时会发生错误。（ ）{{ select(17) }}

• 正确
• 错误

第18题（1.5分）

若将第8行的"i <=n"改为"i*i<=n",程序运行结果不会改变。（ ）{{ select(18) }}

• 正确
• 错误

第19题（1.5分）

若输入的字符串全部由大写字母组成,那么输出的字符串就跟输入的字符串一样。（ ）{{ select(19) }}

• 正确
• 错误

第20题（3分）

若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比,至多有多少个字符不同：{{ select(20) }}

• 3
• 6
• 9
• 12

第21题（3分）

若输入的字符串长度为多少时,那么输入的字符串跟输出的字符串相比,至多有36个不同字符：{{ select(21) }}

• 36
• 100000
• 72
• 18

阅读理解2（14分）

#include <iostream>
using namespace std;
long long n, ans;
int k, len;
long long d[1000000];
int main(){
    cin >> n >>k;
    d[0]=0;
    len=1;
    ans=0;
    for (long long i=0; i <n; ++i){
        ++d[0];
        for (int j=0;j+ 1<len; ++j) {
            if (d[j]== k) {
                d[j]=0;
                d[j +1]+=1;
                ++ans;
            }
        }
        if (d[len -1] ==k) {
            d[len -1]=0;
            d[len]=1;
            ++len;
            ++ans;
        }
    }
    cout << ans <<endl;
    return 0;
}

第22题（2分）

该程序的功能是模拟k进制数的加法运算。（ ）{{ select(22) }}

• 正确
• 错误

第23题（2分）

变量ans记录的是k进制加法过程中的进位次数。（ ）{{ select(23) }}

• 正确
• 错误

第24题（2分）

当n=3, k=2时,程序输出结果为2。（ ）{{ select(24) }}

• 正确
• 错误

第25题（2分）

当k=10, len=3时,d数组最多可表示的数是999。（ ）{{ select(25) }}

• 正确
• 错误

第26题（3分）

若输入n=5, k=2,程序的输出结果是：{{ select(26) }}

• 3
• 4
• 5
• 6

第27题（3分）

该程序的时间复杂度是：{{ select(27) }}

• O(n)
• O(n log n)
• O(nk)
• O(n²)

阅读理解3（14分）

#include <stdio.h>
int n;
int a[1000];
int f(int x)
{
    int ret=0;
    for (; x; x &=x-1) ret++;
    return ret;
}
int g(int x)
{
    return x & -x;
}
int main()
{
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    for (int i=0;i<n; i++)
    printf("%d ", f(a[i]) +g(a[i]));
    printf("\n");
    return 0;
}

第28题（1.5分）

输入的n等于1001时,程序不会发生下标越界。（ ）{{ select(28) }}

• 正确
• 错误

第29题（1.5分）

输入的a[i]必须全为正整数,否则程序将陷入死循环。（ ）{{ select(29) }}

• 正确
• 错误

第30题（1.5分）

函数f(x)的功能是计算x的二进制表示中1的个数。（ ）{{ select(30) }}

• 正确
• 错误

第31题（1.5分）

当输入为"1 511998"时,输出为"18"。（ ）{{ select(31) }}

• 正确
• 错误

第32题（3分）

当输入为"5 2 11 9 16 10"时,输出为（ ）{{ select(32) }}

• 3 4 3 17 5
• 3 4 3 17 4
• 3 5 3 17 5
• 3 5 4 17 5

第33题（4分）

当输入为"2 -65536 2147483647"时,输出为：{{ select(33) }}

• 65552 32
• 17 32
• 16 31
• 17 31

编程填空1（15分）

题目描述

给定 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i, b_i]$ 。需要从这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并集覆盖（即每一个 $0 \leq i \leq m$ 都在某个所选的区间中 ），且保证答案存在，要求找出所选区间个数的最小值。

输入格式

• 第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 5000, 1 \leq m \leq 10^{9}$ ）。
• 接下来 $n$ 行，每行两个整数 $a_i, b_i$（$0 \leq a_i \leq b_i \leq m$ ）。

#include <bits/stdc++.h>
using namespace std;
int n, m;

struct segment { int a, b; } A[MAXN];
void sort()//排序
{
    for (int i=0; i<n; i++)
        for (int j=1; j<n; j++)
            if (①)
            {
                segment t = A[j];
                ②;
            }
}
int main()
{
    cin >>n>>m;
    for (int i=0;i<n; i++)
        cin >> A[i].a >> A[i].b;
    sort();
    int p=1;
    for (int i=1;i<n; i++)
        if (③)
            A[p++]=A[i];
    n =p;
    int ans =0, r=0;
    int q=0;
    while (r<m)
    {
        while (④)
            q++;
        ⑤;
        ans++;
    }
    cout << ans <<endl;
    return 0;
}

第34题（3分）①处应填（ ）{{ select(34) }}

• A[j].a < A[j-1].a
• A[j].a > A[j-1].a
• A[j].b < A[j-1].b
• A[j].b > A[j-1].b

第35题（3分）②处应填（ ）{{ select(35) }}

• A[j] = A[j-1]; A[j-1] = t
• A[j-1] = A[j]; A[j] = t
• swap(A[j], A[j-1])
• t = A[j]; A[j] = A[j-1]

第36题（3分）③处应填（ ）{{ select(36) }}

• A[i].b > A[p-1].b
• A[i].a > A[p-1].b
• A[i].a > A[p-1].a
• A[i].b > A[p-1].a

第37题（3分）④处应填（ ）{{ select(37) }}

• q+1<n&&A[q+1].a<=r
• q+1<n&&A[q+1].b<=r
• q+1<n&&A[q+1].a>r
• q+1<n&&A[q+1].b>r

第38题（3分）⑤处应填（ ）{{ select(38) }}

• r = max(r, A[q].b)
• r = A[q].b
• r = max(r, A[q].a)
• r += A[q].b

编程填空2（15分）

题目描述

使用计数排序对 n 对整数 进行双关键字排序：

• 排序规则：先按 第二关键字 b[i] 升序 排序；若 b[i] 相同，则按 第一关键字 a[i] 升序 排序。
• 输入：
  • 第一行：整数 n（$1 < n < 10^7$）；
  • 接下来 n 行：每行两个整数 a[i] 和 b[i]（1 < a[i], b[i] < 10⁴）。
• 输出：按排序规则输出所有数对。

测试用例验证

输入（修正后合理样例）：

3  
3 4  
2 4  
3 3  

输出：

3 3  
2 4  
3 4  

#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<n; ++i)
        ①;//利用cnt数组统计数量
    for (int i=0; i< maxs; ++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;
}

第39题（3分）①处应填（ ）{{ select(39) }}

• ++cnt[a[i]]
• ++cnt[b[i]]
• cnt[++a[i]]
• cnt[++b[i]]

第40题（3分）②处应填（ ）{{ select(40) }}

• ord[cnt[b[i]]--] = i
• ord[--cnt[b[i]]] = i
• ord[cnt[a[i]]--] = i
• ord[--cnt[a[i]]] = i

第41题（3分）③处应填（ ）{{ select(41) }}

• ++cnt[a[ord[i]]]
• ++cnt[b[ord[i]]]
• ++cnt[a[i]]
• ++cnt[b[i]]

第42题（3分）④处应填（ ）{{ select(42) }}

• res[--cnt[a[ord[i]]]] = ord[i]
• res[cnt[a[ord[i]]]--] = ord[i]
• res[--cnt[b[ord[i]]]] = ord[i]
• res[cnt[b[ord[i]]]--] = ord[i]

第43题（3分）⑤处应填（ ）{{ select(43) }}

• a[i], b[i]
• a[res[i]], b[res[i]]
• ord[i], res[i]
• a[ord[i]], b[ord[i]]