一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 以下与电子邮件无关的网络协议是（ ）{{ select(1-1) }}

• SMTP
• POP3
• MIME
• FTP

2. 二进制数 1111 0110 和 0000 1111 进行逻辑异或运算的结果是（ ）{{ select(1-2) }}

• 1111 1001
• 0000 0110
• 1111 1111
• 0000 1001

3. 布尔型变量占用（ ）个比特位。（ ）{{ select(1-3) }}

• 1
• 2
• 4
• 8

4. 以下程序段：

int i,s=0;
for(i=1;i<=5;i=i+2)
    s=s+i;

执行完毕后，i 和 s 的值分别是（ ）{{ select(1-4) }}

• 5 和 9
• 7 和 9
• 5 和 7
• 9 和 7

5. 已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为 90 的元素时，查找成功的比较次数为（ ）{{ select(1-5) }}

• 5
• 2
• 3
• 4

6. 数组不具有的特点是（ ）{{ select(1-6) }}

• 插入、删除不需要移动元素
• 可随机访问任一元素
• 是一块连续的内存空间
• 所需空间与线性长度成正比

7. 用冒泡排序的方法对一个长度为 n 的数据进行排序，平均时间复杂度为（ ）{{ select(1-7) }}

• O(n*n)
• O(nlogn)
• O(n)
• O(nsqrtn)

8. 由 4 个节点构成的形态不同的二叉树有（ ）种。（ ）{{ select(1-8) }}

• 16
• 14
• 20
• 10

9. 以下 4 个数中最大的素数是（ ）{{ select(1-9) }}

• 91
• 89
• 119
• 93

10. 45 和 30 的最小公倍数是（ ）{{ select(1-10) }}

• 30
• 45
• 90
• 180

11. 深度为 k 的二叉树上，最多含有（ ）个节点。（ ）{{ select(1-11) }}

• 2k−1
• 2k
• 2^k−1
• 2^k−1

12. 字符串“abcab”本质不同的子串个数为（ ）{{ select(1-12) }}

• 12
• 13
• 14
• 15

13. 十进制小数 11.375 对应的二进制数是（ ）{{ select(1-13) }}

• 1011.011
• 1011.01
• 1101.101
• 1101.011

14. 一棵 6 节点二叉树的中序遍历为 ABDGECF，先序遍历为 DBACEGF，后序遍历为（ ）{{ select(1-14) }}

• DGBEFAC
• ABGEFCD
• GBEACFD
• ABCDEFG

15. 当价格不变时，集成电路上可容纳的元器件的数目，约每隔 18～24 个月就会增加一倍，性能也将提升一倍。提出该规律的是（ ）{{ select(1-15) }}

• 图灵
• 诺贝尔
• 摩尔
• 冯·诺依曼

二、阅读程序（程序输入不超过数组或字符串定义的范围；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）

（一）

#include<iostream>
using namespace std;
int a,b,c;
int main( )
{
    cin>>a>>b>>c;
    a=b-a;
    b=b-a;
    a=b+a;
    c=b-a;
    cout<<a<<" "<<b<<" "<<c;
    return 0;
}

判断题

16. 若输入 1 2 3，则输出 3 2 1。（ ）{{ dropdown(2-1)[√, ×] }}

17. 若输入 123456789012 2 3，将输出 2 123456789012 123456789010。（ ）{{ dropdown(2-2)[√, ×] }}

18. 该程序中，头文件 #include<iostream> 可以改成 #include<cstdio>。（ ）{{ dropdown(2-3)[√, ×] }}

19. 若输入 10,20,30（逗号隔开），符合程序的输入要求。（ ）{{ dropdown(2-4)[√, ×] }}

选择题

20. 若输入 10 20 30，输出（ ）{{ select(2-5) }}

• 20 10 20
• 20 10 10
• 20 10 30
• 20 10 -10

21. 若将第 10 行的 c=b-a 改成 c=b，则输入 3 6 9，输出（ ）{{ select(2-6) }}

• 6 3 6
• 6 3 9
• 6 3 3
• 3 6 3

（二）

#include<cstdio>
bool pd(long long n)
{
    if(n==1)
        return false;
    for(long long i=2;i<n;i++)
        if(n%i==0)return false;
    return true;
}
int main( )
{
    long long n,i,c=0;
    int INF=1<<30;
    scanf("%d",&n);
    for(i=2;i<=INF;i++)
    {
        if(pd(i))
        {
            c++;
            if(c==n)
            {
                printf("%d",i);
                return 0;
            }
        }
    }
    printf("\nover");
    return 0;
}

判断题

22. 上述代码中，若将第 13 行修改为 INF=1<<40，则输出结果一定不变。（ ）{{ dropdown(2-7)[√, ×] }}

23. 上述代码中，将第 23 行修改为 break 或 continue 这两种情况后，有相同的输入，在这两种情况下，输出结果也一定相同。（ ）{{ dropdown(2-8)[√, ×] }}

24. 上述代码中，将第 23 行修改为 break 后，有相同的输入，变量 c 的值和未修改前一定相同。（ ）{{ dropdown(2-9)[√, ×] }}

25. 上述代码中，将第 23 行修改为 break 后，有相同的输入，输出结果也一定相同。（ ）{{ dropdown(2-10)[√, ×] }}

选择题

26. 若输入为 8，输出为（ ）{{ select(2-11) }}

• 17
• 19 回车 over
• 19
• 23\nover

27. 上述代码中，将第 6 行的 i<n 修改为（ ）后功能不变，效率更高。（ ）{{ select(2-12) }}

• i*i<=n
• i<n/2
• i<n/3
• i<n/4

（三）

#include<bits/stdc++.h>
using namespace std;
int a[100][100];
int b[100][100];
int f(int m,int n){
    if (m <= 0 || n <= 0)
        return 0;
    a[0][0] = b[0][0];
    for(int i=1;i<n;i++)a[0][i]=a[0][i-1]+b[0][i];
    for(int i=1;i<m;i++)a[i][0]=a[i-1][0]+b[i][0];
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            a[i][j]=min(a[i-1][j],a[i][j-1])+b[i][j];
        }
    }
    return a[m-1][n-1];
}
int main(){
int m,n;
cin>>m>>n;
for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
        cin>>b[i][j];
    }
}
cout<<f(m,n);
return 0;
}

判断题

28. 上述代码实现了对一个长度为 m * n 的二维数组寻找每一行上的最小值进行求和。（ ）{{ dropdown(2-13)[√, ×] }}

29. 上述代码如果删除第 4 行，其他地方的 b 数组都改成 a 数组，那么结果不变。（ ）{{ dropdown(2-14)[√, ×] }}

选择题

30. 若输入数据为：

4 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

则输出的结果为（ ）{{ select(2-15) }}

• 28
• 16
• 136
• 46

31. 上述代码的时间复杂度为（ ）{{ select(2-16) }}

• O(min(m,n))
• O(m*n+m*n+m+n)
• O(m*n)
• O(m*n+m*n)

32. 我们将上述算法称为（ ）{{ select(2-17) }}

• 深度搜索
• 广度搜索
• 动态规划
• 贪心

33. 上述代码若删除第 4 行，其他地方的 b 数组都改成 a 数组，输入数据为：

3 3
1 2 3 4 5 6 7 8 9

则输出的结果为（ ）{{ select(2-18) }}（4 分）

• 20
• 12
• 11
• 21

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

（一）

请完善下面的程序，将 1～9 个数字分别填入 3×3 的九宫格中，第一行的三个数字组成一个三位数。要使第二行的三位数是第一行的 2 倍，第三行的三位数是第一行的 3 倍，且每个格子里的数字都不能重复，现在要求输出所有的填充方案，以每种方案中的第一行组成的三位数升序输出。

输出格式：每一种方案输出共三行，每行中每两个数没有空格，每种方案输出后要输出一个空行。最后一行一个数字，表示方案的总数。

#include<bits/stdc++.h>
using namespace std;
#define n 9
int a[10],b[10],t1,t2,t3,c;
void f(int s){
    int i;
    if( ① ){
        t1=a[1]*100+a[2]*10+a[3];
        t2=a[4]*100+a[5]*10+a[6];
        t3=a[7]*100+a[8]*10+a[9];
        if( ② ){
            cout<<t1<<endl<<t2<<endl<<t3<<endl<<endl;
            c++;
        }
        return;
    }
    for(i=1;i<=n;i++){
        if(b[i]==0){
            ③
            b[i]=1;
            ④
            ⑤
        }
    }
}
int main( )
{
    f(1);
    cout<<c<<endl;
}

34. ① 处应填（ ）{{ select(3-1) }}

• s==n+1
• s==n
• s<n
• s>=n

35. ② 处应填（ ）{{ select(3-2) }}

• t3*2==t2&&t3*3==t1
• t1*2==t2&&t2*3==t3
• t1*3==t2&&t1*2==t3
• t1*2==t2&&t1*3==t3

36. ③ 处应填（ ）{{ select(3-3) }}

• a[c]=i;
• a[s]=i;
• a[i]=s;b[c]=i;
• b[s]=i;

37. ④ 处应填（ ）{{ select(3-4) }}

• f(i+1);
• f(s+1);
• f(c+1);
• f(c+i+1);

38. ⑤ 处应填（ ）{{ select(3-5) }}

• a[s]=0;
• f(s-1);
• a[s]=i;
• b[i]=0;

（二）（拓扑排序）

输入一张 n 节点 m 条边的有向图，用求该图的一个拓扑排序的方式判断该图是否存在有向环，若有拓扑排序输出拓扑排序，并输出“不存在有向环”，否则直接输出“存在有向环”。

输入：第一行两个正整数 n，m 表示节点数和边数。接下来 m 行，每行 2 个正整数 x，y 表示节点 x→y 之间有一条边。

输出：一个拓扑序：按拓扑序输出点的编号。若拓扑序不唯一，输出任意一个均可，并输出“不存在有向环”。若无拓扑序，直接输出“存在有向环”。

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#define N 1001
using namespace std;
int n,m,x,y;
vector<int>G[N];
stack<int>q;
int cnt[N],tpc;
bool pd()
{
    for(int i=1;i<=n;i++)
        if( ① )q.push(i);
    while(! q.empty())
    {
        int u=q.top();
        q.pop();
        tpc++;
        cout<<u<<" ";
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            ②
            if(! cnt[v]) ③
        }
    }
    if( ④ )return 1;
    else return 0;
}

int main()
{
    cin>>n>>m;
    while(m--)
    {
        cin>>x>>y;
        G[x].push_back(y);
        ⑤
    }
    if(pd( ))cout<<"存在有向环";
    else cout<<"不存在有向环";
}

39. ① 处应填（ ）{{ select(3-6) }}

• ! cnt[i]
• cnt[i]
• cnt[i]=0
• cnt[i]==1

40. ② 处应填（ ）{{ select(3-7) }}

• q.push(v);
• q.pop();
• cnt[u]--;
• cnt[v]--;

41. ③ 处应填（ ）{{ select(3-8) }}

• q.pop( );
• q.push(v);
• tpc--;
• tpc++;

42. ④ 处应填（ ）{{ select(3-9) }}

• tpc! =n
• tpc==n
• tpc==0
• tpc! =0

43. ⑤ 处应填（ ）{{ select(3-10) }}

• cnt[x]++;
• G[y].push(x)
• cnt[y]++;
• G[y].push_back(x)