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

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

• SMTP
• POP3
• MIME
• FTP

2. 二进制数11110110和00001111进行逻辑异或运算的结果是()。 {{ select(2) }}

• 11111001
• 00000110
• 11111111
• 00001001

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

• 1
• 2
• 4
• 8

4. 以下程序段执行完毕后,i和s的值分别是()。

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

{{ select(4) }}

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

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

• 5
• 2
• 3
• 4

6. 数组不具有的特点是()。 {{ select(6) }}

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

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

• O(n^2)
• O(n log2 n)
• O(n)
• O(n*sqrt(n))

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

• 16
• 14
• 20
• 10

9. 以下4个数中最大的素数是()。 {{ select(9) }}

• 91
• 89
• 119
• 93

10. 45和30的最小公倍数是()。 {{ select(10) }}

• 30
• 45
• 90
• 180

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

• 2k-1
• 2k
• 2^k - 1
• 2-1

12. 字符串"abcab"本质不同的子串个数为()。 {{ select(12) }}

• 12
• 13
• 14
• 15

13. 十进制小数11.375对应的二进制数是()。 {{ select(13) }}

• 1011.011
• 1011.01
• 1101.101
• 1101.011

14. 一棵6节点二叉树的中序遍历为ABDCECF,先序遍历为DBACECF,后序遍历为()。 {{ select(14) }}

• DGBEFAC
• ABGEFCD
• GBEACFD
• ABCDEFG

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

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

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

（一）

#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。() {{ select(16) }}

• 正确
• 错误

17. 若输入1 23456789012 23，将输出2 123456789012 123456789010。() {{ select(17) }}

• 正确
• 错误

18. 该程序中，头文件#include可以改成#include。() {{ select(18) }}

• 正确
• 错误

19. 若输入10,20,30(逗号隔开)，符合程序的输入要求。() {{ select(19) }}

• 正确
• 错误

选择题 20. 若输入10 20 30，输出()。 {{ select(20) }}

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

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

• 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，则输出结果一定不变。() {{ select(22) }}

• 正确
• 错误

23. 上述代码中，将第23行修改为break或continue这两种情况后，有相同的输入，在这两种情况下，输出结果也一定相同。() {{ select(23) }}

• 正确
• 错误

24. 上述代码中，将第23行修改为break后，有相同的输入，变量c的值和未修改前一定相同。() {{ select(24) }}

• 正确
• 错误

25. 上述代码中，将第23行修改为break后，有相同的输入，输出结果也一定相同。() {{ select(25) }}

• 正确
• 错误

选择题

26. 输入为:8 输出为( )。 {{ select(26) }}

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

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

• 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的二维数组寻找每一行上的最小值进行求和。() {{ select(28) }}

• 正确
• 错误

29. 上述代码如果删除第4行，其他地方的b数组都改成a数组，那么结果不变。() {{ select(29) }}

• 正确
• 错误

选择题 30. 若输入数据为: 4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则输出的结果为( )。 {{ select(30) }}

• 28
• 16
• 136
• 46

31. 上述代码的时间复杂度为()。 {{ select(31) }}

• O(min(m,n))
• O(2nm+m+n)
• O(nm)
• O(2nm)

32. 我们将上述算法称为( )。 {{ select(32) }}

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

33. 上述代码若删除第4行，其他地方的b数组都改成a数组，输入数据为: 3 3 1 2 3 4 5 6 7 8 9 则输出的结果为()。 {{ select(33) }}

• 20
• 12
• 11
• 21

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

（一）九宫格填数

请完善下面的程序，将1~9个数字分别填入3x3的九宫格中，第一行的三个数字组成一个三位数。要使第二行的三位数是第一行的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(34) }}

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

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

• t32==t2 && t33==t1
• t12==t2 && t23==t3
• t13==t2 && t12==t3
• t12==t2 && t13==t3

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

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

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

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

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

• 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(39) }}

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

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

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

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

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

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

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

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

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