一.单项选择题

共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(nlogn)$
• $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^{k-1}$

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

• 12
• 13
• 14
• 15

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

{{ select(13) }}

• 1011.011
• 1011.010
• 1101.101
• 1101.011

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

• DGBEFAC
• ABGEFCD
• GBEACFD
• ABCDEFG

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

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

二、阅读程序

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

（1）

#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<<endl;
       return 0;
}

16. 若输入123,则输出321。（ ） {{ select(16) }}

• 正确
• 错误

17. 若输入123456789012 2 3,将输出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

（2）

#include<iostream>
using namespace std;
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\n over

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

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

（3）

#include<iostream>
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<=n;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<n;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(m*n+m*n+m+n)
• O(m*n)
• O(m*n+m*n)

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

{{ select(32) }}

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

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

33
1 2 3 4 5 6 7 8 9

则输出的结果为( )。 {{ select(33) }}

• 20
• 12
• 11
• 21

三、完善程序

单选题，除特殊说明外，每小题3分，共计30分。

（1） 将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<<t2<<t3;
           c++ ;         
       }
       return；
   }
   for( i=1;i<=n;i++){             
       if(b[i]==0){
           (      ③      )
           b[i]=1;
           (      ④      )
           (      ⑤      )
      }
   }
}
int main(  )
{     
    f(1) ;
    cout<<t1<<t2<<t3;
}

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

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

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

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

• a[c] = i;
• a[s] = i;
• a[i] = s; b[c]= i;
• b[s]=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;

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

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

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

#include<iostream>
#include<cstring>
using namespace std;
#define N 1001
int n,m,x,y;
vector<int>G;  
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<<
    for(int  i=0;i<n;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(!G.empty()) 
          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);