一、单项选择题（共15题，每题2分，共计30分）

1. 以下属于系统软件的是:()。 {{ select(1) }}

• C++编译器
• 腾讯QQ
• CAD
• 游戏软件

2. 哪年哪月哪日在国际电信标准组织3GPP RAN第78次全体会议上，5G NR首发版本正式发布，这是全球第一个可商用部署的5G标准。() {{ select(2) }}

• 2017年8月18日
• 2018年1月1日
• 2017年12月25日
• 2017年12月21日

3. 如果用一个字节来表示整数，最高位用作符号位，其他位表示数值。例如：00000001表示+1，10000001表示-1，试问这样表示法的整数A的范围应该是( )。 {{ select(3) }}

• -127<=A<=127
• -128<=A<=128
• -128<=A<128
• -127<=A<=128

4. 下列属于网络模型的名称是()。 {{ select(4) }}

• LAN
• TCP/IP
• FTP
• SMTP

5. 在C++中，(-7)%(-5)等于()。 {{ select(5) }}

• 2
• -2
• 3
• -3

6. 学号为1到30的小朋友顺时针排成一圈，从1号小朋友开始顺时针报数，从数字1开始数下去，1,2,3,…,28,29,30,31,32,…，一圈又一圈，问当数到数字n，所在的小朋友的学号为多少?()。 {{ select(6) }}

• (n-1)%30
• 1+(n-1)%30
• (n+1)%30-1
• (n+1)%30

7. 一棵完全二叉树的结点总数为41，其叶结点数为( )。 {{ select(7) }}

• 18个
• 19个
• 20个
• 21个

8. 给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是( )。 {{ select(8) }}

• O(n)、O(n²)、O(log₂n)
• O(log₂n)、O(n)、O(n²)
• O(n²)、O(n)、O(n)
• O(n²)、O(n²)、O(n²)

9. 请给以下四个事件发生的时间排序( )。
10. 举办第一次NOIP
11. 举办第一次NOI网络同步赛
12. NOIP提高组由四题改为三题
13. 举办第一次APIO {{ select(9) }}

• 1234
• 1243
• 2134
• 2143

10. 以下在OSI模型中属于TCP/IP模型中的应用层的是()。 {{ select(10) }}

• 应用层
• 网络层
• 数据链路层
• 表示层

11. 以下关于图的不正确说法是()。 {{ select(11) }}

• 所有顶点的度数之和等于边数的2倍
• 所有顶点的度数之和不一定等于边数的2倍
• 任意一个图一定有偶数个奇点
• 在有向图中顶点的入度之和等于出度之和

12. 6个人分乘两辆不同的汽车，每辆车最多坐4人，则不同的乘车方法数为( )。 {{ select(12) }}

• 40
• 50
• 60
• 70

13. 为了实现两数交换，代码如下：

void swapAB(int &a, int &b)
{
    ______
    b = a - b;
    a = a - b;
}

则空格内要填入的语句是( )。 {{ select(13) }}

• a = a + b;
• a = a * b;
• a = a - b;
• a = a & b;

14. 某数列有1000个各不相同的数，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检索()个数据。 {{ select(14) }}

• 1000
• 10
• 100
• 500

15. 以下简称和全称不对应的是()。 {{ select(15) }}

• NAT(Network Address Translation)
• TCP(Transmission Control Protocol)
• ARP(Adobe Resolution Protocol)
• ICMP(Internet Control Message Protocol)

二、阅读程序（共计40分；判断题每题1.5分，选择题每题4分）

（一）字符串相同字符计数

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1, s2;
    cin >> s1; cin >> s2;
    int cnt = 0;
    for(int i = 0; i < s1.size(); i++)
    {
        for(int j = 0; j < s2.size(); j++)
            if(s1[i] == s2[j]) cnt++;
    }
    cout << cnt;
    return 0;
}

判断题 16. 输入必须全要是字母，否则无法被识别。() {{ select(16) }}

• 正确
• 错误

17. 将第10行的j全部换成i是有问题的。() {{ select(17) }}

• 正确
• 错误

18. 本程序的功能是统计两个字符串的最长公共子序列长度。() {{ select(18) }}

• 正确
• 错误

19. 本程序的时间复杂度为O(n²)。() {{ select(19) }}

• 正确
• 错误

选择题 20. 若输入的两个字符串长度均为12，那么输出最大为()。 {{ select(20) }}

• 0
• 144
• 12
• 24

21. 若s1长度为4，输出为6，则s2的长度至少为()。 {{ select(21) }}

• 1
• 2
• 3
• 4

（二）差分数组求和

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
int a[MAXN], b[MAXN];
int main(){
    int n, m, x, y;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> x >> y;
        a[x]++;
        a[y + 1]--;
    }
    int cnt = 0, ans = 0;
    for(int i = 0; i <= m; i++)
    {
        cnt += a[i];
        ans += cnt;
    }
    cout << ans;
    return 0;
}

注：输入流中 1<=x<=y<=m

判断题 22. 输入的x和y可以是全体整数。() {{ select(22) }}

• 正确
• 错误

23. 将第14行的变量清零过程除去没有问题。() {{ select(23) }}

• 正确
• 错误

24. 将第17行与第18行交换位置不会影响最终结果。() {{ select(24) }}

• 正确
• 错误

25. 将第11行的x改成x-1并把第12行的y+1改成y不会影响最终结果。() {{ select(25) }}

• 正确
• 错误

选择题 26. 现在已知输入的n与m，则答案的极差为()。 {{ select(26) }}

• n-m
• 2n-m
• nm-n
• n²-2m

27. 除去"注"中的条件，则答案的极差为()。 {{ select(27) }}

• 2n+2nm
• n+m
• 2n+2m
• mn+m

（三）指针与传值/传引用

#include<bits/stdc++.h>
using namespace std;
int a[6];
int change(int a){ a++; }
int change1(int &a){ a++; }
int main(){
    int c = 1;
    for(int i = 1; i <= 5; i++) a[i] = i * 3;
    int *b = &a[1];
    change(*b);
    cout << *b << endl;
    cout << a[1] << endl;
    (*b)++;
    cout << *b << endl;
    cout << a[1] << endl;
    change1(*b);
    cout << *b << endl;
    cout << a[1] << endl;
    *b = c;
    change(c);
    cout << *b << endl;
    cout << c << endl;
    change1(c);
    cout << *b << endl;
    cout << c << endl;
    return 0;
}

判断题 28. 将第7行中int换为long long后程序依然能通过编译。() {{ select(28) }}

• 正确
• 错误

29. change与change1两个函数等价。() {{ select(29) }}

• 正确
• 错误

30. 将第12行换为b = &c;输出值不变。() {{ select(30) }}

• 正确
• 错误

31. 将第8行换为int *b = a + 1;输出值不变。() {{ select(31) }}

• 正确
• 错误

选择题 32. 所有输出结果中的最大值是()。 {{ select(32) }}

• 6
• 4
• 7
• 5

33. 所有输出结果的乘积是()。 {{ select(33) }}

• 6804
• 5760
• 11520
• 13608

三、完善程序（单选题，每小题3分，共计30分）

（一）统计前面比当前大的数

给出N个整数，要统计每个数前面有多少比它大的数字。比如有5个数的数列：2 5 1 3 4，则第1个数2之前有0个数比它大；第2个数5之前有0个数比它大；第3个数1之前有2个数比它大；第4个数3之前有1个数比它大；第5个数4之前有1个数比它大。 数据范围：每个数范围是[0...200]，N<=10⁵

#include<iostream>
using namespace std;
int d[100002];
int c[1300];
int main(){
    int n, ans, x;
    cin >> n;
    for(int i = 0; i < n; i++)
        ① ;
    for(int i = 0; i < n; i++){
        ② ;
        for(int j = ③ ; j <= 200; j++)
            ④ ;
        cout << ans << " ";
        ⑤ ;
    }
    cout << endl;
    return 0;
}

34. ①处应该填( )。 {{ select(34) }}

• cin>>c[i]
• cin>>d[i]
• read(c[i])
• read(d[i])

35. ②处应该填( )。 {{ select(35) }}

• ans++
• c[i] = d[i]
• ans = 0
• c[i]++

36. ③处应该填()。 {{ select(36) }}

• d[i]
• c[i]+1
• d[i]+1
• c[i]

37. ④处应该填()。 {{ select(37) }}

• c[j] += d[i]
• ans += (c[j]==1)
• ans++
• ans += c[j]

38. ⑤处应该填()。 {{ select(38) }}

• c[d[i]]++
• c[i]++
• ans = c[i]
• d[c[i]]++

（二）二分求区间中位数

给定n个数a₁,⋯,aₙ。求第l到第r个数当中的中位数，我们可以用二分的经典思想来解决此问题。所谓中位数就是n个数中从小到大排序第⌊n/2⌋+1个数。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
int n, m, a[MAXN], maxn;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i], maxn = max(maxn, a[i]);
    while(m--){
        int lft, rgt; cin >> lft >> rgt;
        int l = 1, r = ① ;
        while( ② ){
            int mid = ③ , s1 = 0, s2 = 0;
            for(int i = lft; i <= rgt; i++){
                if(a[i] > mid) s1++;
                if(a[i] < mid) s2++;
            }
            if(s1 <= s2) ④ = mid;
            else ⑤ = mid;
        }
        cout << l;
    }
    return 0;
}

39. ①处应填()。 {{ select(39) }}

• maxn
• maxn+1
• maxn-1
• n*2

40. ②处应填()。 {{ select(40) }}

• l+r < n
• l <= r
• l < r
• l+1 < r

41. ③处应填()。 {{ select(41) }}

• l+r
• (l+r)>>1
• r-l+1
• r-1

42. ④处应填( )。 {{ select(42) }}

• l
• r
• lft
• rgt

43. ⑤处应填( )。 {{ select(43) }}

• l
• r
• lft
• rgt