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

1. 大多数计算机病毒主要造成计算机( )的损坏。 {{ select(1) }}

• 软件和数据
• 硬件和数据
• 硬件、软件和数据
• 硬件和软件

2. 假设今年中秋有253个月饼，把它们装到15个盒子里面，那么数量最多的一盒至少装几个月饼( )。 {{ select(2) }}

• 16
• 23
• 15
• 17

3. ASCII编码是由美国国家标准委员会指定的一种包括数字、字母、通用字符和控制符号在内的字符编码集，它是一种( )位二进制编码。 {{ select(3) }}

• 8
• 7
• 4
• 32

4. 计算机的硬件主要包括控制器、( )、存储器、输入设备、输出设备。 {{ select(4) }}

• 运算器
• 操作系统
• 计算机语言
• 磁盘

5. 字符"a"的ASCII码是97，写出下面程序的输出结果：char c='a'+4;cout<<c<<","<< (int) c+3<<endl;( )。 {{ select(5) }}

• e,h
• 101,104
• e,104
• 101,h

6. 操作系统是对( )进行管理的软件。 {{ select(6) }}

• 计算机资源
• 软件
• 硬件
• 应用程序

7. 以下选项中( )不是一个操作系统环境。 {{ select(7) }}

• Linux
• Windows CE
• Solaris
• Celeron

8. 以下关于C++语言注释的说法正确的是( )。 {{ select(8) }}

• 写C++语言程序时必须书写注释，否则会对程序的功能造成影响
• C++语言的注释将参与编译器编译，并形成指令
• 可以采用/...../的形式书写多行注释，其中的注释内容可以是任何字符
• //注释表示从//开始直到本行末尾的所有字符均是注释内容

9. 要使用putchar函数实现向显示器输出字符"A"，则可以使用( )。 {{ select(9) }}

• putchar(65)
• putchar(A)
• putchar('\65')
• putchar("A")

10. 两个指针( )。 {{ select(10) }}

• 可在一定条件下相加
• 如果同时指向一个变量，则此后就不能再指向其他变量了
• 任何时候都不能相减
• 可在一定条件下进行相等或不等的比较运算

11. 下列属于B类IP地址的是()。 {{ select(11) }}

• 27.33.119.2
• 134.300.12.4
• 133.201.189.32
• 192.97.32.121

12. 现有变量a,b,c,d，取值范围均为[0,15]，假设每个值出现的概率相同，则表达式a^b^c^d的值能被3整除的概率( )。 {{ select(12) }}

• $\frac{3}{8}$
• $\frac{1}{2}$
• $\frac{1}{4}$
• $\frac{1}{8}$

13. 假设以S和X分别表示进和出栈操作，则对输入序列a,b,c,d,e进行一系列栈操作 SSXSXSSXXX之后，得到的输出序列为( )。 {{ select(13) }}

• baced
• bceda
• cbaed
• edcba

14. 某递归算法的执行时间的递推关系如下： 当 $n=1$ 时, $T(n)=1$； 当$n>1$时, $T(n)=2 ×T(n / 2)+1$。 则该算法的时间复杂度为()。 {{ select(14) }}

• $O(1)$
• $O\left(log _{2} n\right)$
• $O(n)$
• $O(n \log_2 n)$

15. 一棵完全二叉树中有501个叶子节点，则至少有( )个节点。 {{ select(15) }}

• 501
• 502
• 1001
• 1002

二、阅读程序（判断题正确打√，错误打×；判断每题1.5分，选择每题4分，共40分）

阅读程序1

#include<iostream>
using namespace std;
const int maxn=100001;
int N,M,K;
int x[maxn],y[maxn],d[maxn];
int c[maxn];
int*a[maxn];

int main(){
    cin>>N>>M>>K;
    for(int i=0;i<K;++i){
        cin>>x[i]>>y[i]>>d[i];
        c[y[i]]++;
    }
    for(int i=1;i<=M;++i)
        a[i]=new int[c[i]];
    for(int i=0;i<K;++i){
        *a[y[i]]=d[i];
        a[y[i]]++;
    }
    for(int i=1;i<=M;++i){
        a[i]=a[i]-c[i];
        for (int j=0;j<c[i];++j,++a[i])
            cout<<*a[i]<<' ';
    }
    return 0;
}

16. 程序第09行定义了一个指针数组,a[i]表示第i列的指针。 {{ select(16) }}

• √
• ×

17. 第20行代码改成 a[y[i]][0]=d[i] 不影响运算结果。 {{ select(17) }}

• √
• ×

18. 第15行中，数组c用来统计每行中的数据个数。 {{ select(18) }}

• √
• ×

19. 在本程序中，采用动态数组以优化空间的利用，每一列数组长度可能不同。 {{ select(19) }}

• √
• ×

20. 该程序的时间复杂度为()。 {{ select(20) }}

• $O(M \times N \times K)$
• $O(M+K)$
• $O(M+N)$
• $O(K)$

21. 该程序的空间复杂度为( )。 {{ select(21) }}

• $O(M+K)$
• $O(N \times K)$
• $O(M+N)$
• $O(M \times N)$

阅读程序2

#include<iostream>
#include<iomanip>
using namespace std;
int m[101][101];

int main(){
    int a;
    cin>>a;
    int c=a*a,i=1,k=(a+1)/2;
    for(int j=1;j<=c;j++){
        m[i][k]=j;
        if(j%a==0){
            if(i==a)
                i=1;
            else
                i++;
        } else {
            if(i==1)
                i=a;
            else
                i--;
            if(k==a)
                k=1;
            else
                k++;
        }
    }
    for(int i=1;i<=a;i++){
        for(int j=1;j<=a;j++)
            cout<<setw (5)<<m[i][j];
        cout<<endl;
    }
    return 0;
}

22. 从程序可以看出,i为被填数位置行，j为填入数字，k为填数列位置。 {{ select(22) }}

• √
• ×

23. 填数结束后，数组m中的元素互不相同。 {{ select(23) }}

• √
• ×

24. 当$j\%a==0$ 且 $i !=a$ 时，下一步填入的是()。 {{ select(24) }}

• $m[1][k]$
• $m[i+1][k]$
• $m[k+1][i]$
• $m[k+1][i+1]$

25. 当$j\%a!=0$, $i !=1$ 且 $k==a$ 时，下一步填入的是()。 {{ select(25) }}

• $m[a][1]$
• $m[i-1][1]$
• $m[a][k+1]$
• $m[i-1][k+1]$

26. 填数后，每行每列及对角线的和均为( )。 {{ select(26) }}

• $\frac{\left(a^{2}+1\right) × a}{2}$
• $\frac{\left(a^{2}+1\right)}{2}$
• $\left(a^{2}+1\right) × a$
• $a^{2}+1$

阅读程序3

#include<iostream>
using namespace std;
int a[101],d[101];

int main(){
    int n=5;
    a[1]=d[1]=1;
    for(int i=1;i<=n;++i){
        int s=i+1,x=0;
        for (int j=1;j<=n+1-i;++j){
            int k=s+x;
            x++;
            a[j+1]=a[j]+k;
            cout<<a[j]<<" ";
        }
        cout<<"..."<<endl;
        a[1]=d[i+1]=d[i]+i;
    }
    return 0;
}

27. 该程序有两重循环构成，外循环i控制列的变化，内循环j是控制行的变化。 {{ select(27) }}

• √
• ×

28. 程序运行输出样例：

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

{{ select(28) }}

• √
• ×

29. 本题在输出时，每行为( )个a[j]数组的值。 {{ select(29) }}

• $n+1-i$
• $n+1$
• $n+1+i$
• $n$

30. 本题代码的运算结果是输出()行。 {{ select(30) }}

• 4
• 5
• 6
• 7

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

完善程序1 麦森数高精度计算

#include<cstdio>
#include<cstring>
#include<cmath>
#define LEN 125

void Multiply(int*a, int*b) {
    int i,j;
    int nCarry;
    int nTmp;
    int c[LEN];
    memset (c,0,sizeof (int)*LEN);
    for(i=0;i<LEN;i++){
        nCarry=0;
        for(j=0;①;j++){
            nTmp=c[i+j]+a[j]*b[i]+nCarry;
            c[i+j]=nTmp%10000;
            nCarry=nTmp/10000;
        }
    }
    memcpy (a, c, LEN*sizeof (int));
}

int main(){
    int i;
    int p;
    int anPow[LEN];
    int aResult[LEN];
    scanf("%d",&p);
    printf("%d\n", (int) (p*log10(2))+1);
    anPow[0]=2;
    aResult[0]=1;
    for(i=1;i<LEN;i++){
        anPow[i]=0;
        aResult[i]=0;
    }
    while(②){
        if(③)
            Multiply (aResult, anPow);
        p>>=1;
        Multiply (anPow,anPow);
    }
    aResult[0]--;
    for(i=LEN-1;i>=0;i--){
        if(④)
            printf("%02d%02d", aResult[i]/100, aResult[i]%100);
        else {
            printf("%04d", aResult[i]);
            if(i%25==0)
                printf("\n");
        }
    }
    return 0;
}

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

• j<LEN
• j<LEN-i-1
• j<LEN-i
• j<1

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

• p>0
• p==0
• p<0
• p>=0

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

• p&1
• p
• p||1
• p==0

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

• i !=0
• i>0
• i%10==0
• i%25==12

完善程序2 陪审团DP

#include<cstdio>
#include<cstring>
#include<algorithm>
int f[30][1000];
int Path[30][1000];
int P[300];
int D[300];
int Answer[30];

int main(){
    int i,j,k;
    int t1,t2;
    int n,m;
    int nMinP_D;
    int nCaseNo;
    nCaseNo=0;
    scanf("%d%d",&n, &m);
    while (n+m){
        nCaseNo++;
        for(i=1;i<=n;i++)
            scanf("%d%d",&P[i],&D[i]);
        memset (f, -1,sizeof(f));
        memset (Path,0,sizeof (Path));
        nMinP_D=①;
        f[0][nMinP_D]=0;
        for(j=0;j<m;j++){
            for(k=0;②;k++)
                if(③){
                    for(i=1;i<=n;i++)
                        if(④){
                            t1=j;
                            t2=k;
                            while (t1>0 && Path[t1][t2]!=i) {
                                t2-=P[Path[t1][t2]]-D[Path[t1][t2]];
                                t1--;
                            }
                            if(t1==0){
                                f[j+1][k+P[i]-D[i]]=f[j][k]+P[i]+D[i];
                                Path[j+1][k+P[i]-D[i]]=i;
                            }
                        }
                }
        }
        i=nMinP_D;
        j=0;
        while (f[m][i+j]<0 && f[m][i-j]<0)j++;
        if(f[m][i+j]>f[m][i-j])
            k=i+j;
        else
            k=i-j;
        printf("Jury #%d\n",nCaseNo);
        printf ("Best jury has value %d for prosecution and value %d for defence:\n",(k-nMinP_D+f[m][k])/2, (f[m][k]-k+nMinP_D)/2);
        for(i=1;i<=m;i++){
            ⑤;
            k-=P[Answer[i]]-D[Answer[i]];
        }
        std::sort (Answer+1,Answer+m+1);
        for(i=1;i<=m;i++) printf("%d ",Answer[i]);
        printf("\n\n");
        scanf ("%d%d", &n, &m);
    }
    return 0;
}

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

• nMinP_D=m*20
• nMinP_D=m
• nMinP_D=m*200
• nMinP_D=m*n

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

• k<nMinP_D*2
• k<nMinP_D
• k<=nMinP_D*2
• k<=nMinP_D

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

• f[j][k]>1
• f[j][k]>=1
• f[j][k]>=0
• f[j][k]>0

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

• f[j][k]+P[i]+D[i]>f[j+1][k+P[i]-D[i]]
• f[j][k]+P[i]+D[i]>f[j+1][k+P[i]]
• f[j][k]+P[i]>f[j+1][k+P[i]]
• f[j][k]+P[i]+D[i]>f[j][k+P[i]-D[i]]

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

• Answer[i]=Path[m-i][k]
• Answer[i]=Path[m-i][k+1]
• Answer[i]=Path[m-i+1][k+1]
• Answer[i] =Path[m-i+1][k]