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

1. 在内存储器中每个存储单元都被赋予一个唯一的序号，称为（） {{ select(1) }}

• 地址
• 序号
• 下标
• 编号

2. 编译器的主要功能是（） {{ select(2) }}

• 将源程序翻译成机器指令代码
• 将源程序重新组合
• 将低级语言翻译成高级语言
• 将一种高级语言翻译成另一种高级语言

3. 设 x=true，y=true，z=false，以下逻辑运算表达式值为真的是（） {{ select(3) }}

• (y∨z)∧x∧z
• x∧(z∨y)∧z
• (x∧y)∧z
• (x∧y)∨(z∨x)

4. 现有一张分辨率为 2048×1024 像素的 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（） {{ select(4) }}

• 16MB
• 4MB
• 8MB
• 32MB

5. 冒泡排序算法在最好情况下的比较次数为（） {{ select(5) }}

• n²
• n-2
• n-1
• n

6. 设 A 是 n 个实数的数组，递归算法 XYZ 的输出是（） {{ select(6) }}

• A 数组的平均
• A 数组的最小值
• A 数组的中值
• A 数组的最大值

7. 链表不具备的特点是（） {{ select(7) }}

• 可随机访问任意元素
• 不必事先估计存储空间
• 插入删除不需要移动元素
• 所需空间与线性表长度成正比

8. 有 10 个顶点的无向图至少应该有（）条边才能确保是一个连通图。 {{ select(8) }}

• 9
• 10
• 11
• 12

9. 二进制数 1011 转换成十进制数是（） {{ select(9) }}

• 11
• 10
• 13
• 12

10. 五个小朋友并排站成一列，其中有两个双胞胎必须相邻，则有（）种不同排列方法？ {{ select(10) }}

• 48
• 36
• 24
• 72

11. 下图中所使用的数据结构是（） {{ select(11) }}

• 栈
• 队列
• 二叉树
• 哈希表

12. 独根树高度为 1。具有 61 个结点的完全二叉树的高度为（） {{ select(12) }}

• 7
• 8
• 5
• 6

13. 1949 年的天干地支是（） {{ select(13) }}

• 己酉
• 己亥
• 己丑
• 己卯

14. 10 个三好学生名额分配到 7 个班级，每班至少一个，共有（）种不同方案 {{ select(14) }}

• 84
• 72
• 56
• 504

15. 五副不同颜色手套取 6 只，恰好配成两副的取法有（）种 {{ select(15) }}

• 120
• 180
• 150
• 30

---

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

（1）字符串置换

#include <iostream>
#include <cstdlib>
using namespace std;
char encoder[26]={'C','S','P'};
char decoder[26];
string st;
int main(){
    int k=3;
    for(int i=3;i<26;++i){
        char x='A'+i;
        bool flag=true;
        for(int j=0;j<k;++j)
            if(encoder[j]==x){flag=false;break;}
        if(flag)encoder[k++]=x;
    }
    for(int i=0;i<26;++i)
        decoder[encoder[i]-'A']='A'+i;
    cin>>st;
    for(int i=0;i<st.length();++i)
        st[i]=decoder[st[i]-'A'];
    cout<<st;
    return 0;
}

16. 输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。（） {{ select(16) }}

• 对
• 错

17. 若输入字符串非空，则输入与输出一定不同。（） {{ select(17) }}

• 对
• 错

18. 将第 12 行 i<26 改为 i<16，结果不变。（） {{ select(18) }}

• 对
• 错

19. 将第 26 行 i<26 改为 i<16，结果不变。（） {{ select(19) }}

• 对
• 错

20. 输出为 ABCABCABCA，则输入（） {{ select(20) }}

• 既有 S 又有 P
• 既有 S 又有 B
• 既有 A 又有 P
• 既有 A 又有 B

21. 输出为 CSPCSPCSPCSP，则输入（） {{ select(21) }}

• 既有 P 又有 K
• 既有 J 又有 R
• 既有 J 又有 K
• 既有 P 又有 R

---

（2）k 进制进位统计

#include <iostream>
using namespace std;
long long n,ans;
int k,len;
long long d[1000000];
int main(){
    cin>>n>>k;
    d[0]=0; len=1; ans=0;
    for(long long i=0;i<n;++i){
        ++d[0];
        for(int j=0;j+1<len;++j){
            if(d[j]==k){
                d[j]=0; d[j+1]+=1; ++ans;
            }
        }
        if(d[len-1]==k){
            d[len-1]=0; d[len]=1;
            ++len; ++ans;
        }
    }
    cout<<ans<<endl;
    return 0;
}

22. 若 k=1，则输出 ans 时 len=n。（） {{ select(22) }}

• 对
• 错

23. 若 k>1，则输出 ans 时 len 一定小于 n。（） {{ select(23) }}

• 对
• 错

24. 若 k>1，则 k^len >n 一定成立。（） {{ select(24) }}

• 对
• 错

25. 若 n=10^15，k=1，则输出为（） {{ select(25) }}

• 1
• (10^30-10^15)/2
• (10^30+10^15)/2
• 10^15

26. 若 n=3^30，k=3，则输出为（） {{ select(26) }}

• 3^30
• (3^30-1)/2
• 3^30-1
• (3^30+1)/2

27. 若 n=100010002000090，k=10，则输出为（） {{ select(27) }}

• 11112222444543
• 11122222444453
• 11122222444543
• 11112222444453

---

（3）两行合并最大值

#include <algorithm>
#include <iostream>
using namespace std;
int n;
int d[50][2];
int ans;
void dfs(int n,int sum){
    if(n==1){
        ans=max(sum,ans);
        return;
    }
    for(int i=1;i<n;++i){
        int a=d[i-1][0],b=d[i-1][1];
        int x=d[i][0],y=d[i][1];
        d[i-1][0]=a+x; d[i-1][1]=b+y;
        int s=a+x+abs(b-y);
        for(int j=i;j<n-1;++j)
            d[j][0]=d[j+1][0],d[j][1]=d[j+1][1];
        dfs(n-1,sum+s);
        for(int j=n-1;j>i;--j)
            d[j][0]=d[j-1][0],d[j][1]=d[j-1][1];
        d[i-1][0]=a; d[i-1][1]=b;
        d[i][0]=x; d[i][1]=y;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i)cin>>d[i][0];
    for(int i=0;i<n;++i)cin>>d[i][1];
    ans=0;
    dfs(n,0);
    cout<<ans<<endl;
    return 0;
}

28. 若输入 n=0，程序会死循环或运行错误。（） {{ select(28) }}

• 对
• 错

29. 若输入 n=20，全为 0，则输出为 0。（） {{ select(29) }}

• 对
• 错

30. 输出一定不小于输入 d[i][0]、d[i][1] 任意一个。（） {{ select(30) }}

• 对
• 错

31. n=20，输入 20 个 9、20 个 0，输出为（） {{ select(31) }}

• 1890
• 1881
• 1908
• 1917

32. n=30，输入 30 个 0、30 个 5，输出为（） {{ select(32) }}

• 2000
• 2010
• 2030
• 2020

33. n=15，输入 15~1、15~1，输出为（） {{ select(33) }}

• 2440
• 2220
• 2240
• 2420

---

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

（1）质因数分解

#include <cstdio>

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

• 1
• n-1
• 2
• 0

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

• n/i
• n/(i*i)
• i*i
• iii

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

• if(n%i==0)
• if(i*i<=n)
• while(n%i==0)
• while(i*i<=n)

37. ④ 处填（） {{ select(37) }}

• n>1
• n<=1
• i<n/i
• i+i<=n

38. ⑤ 处填（） {{ select(38) }}

• 2
• n/i
• n
• i

---

（2）区间覆盖

#include <iostream>
using namespace std;
const int MAXN=5000;
int n,m;
struct segment{int a,b;}A[MAXN];
void sort(){
    for(int i=0;i<n;i++)
        for(int j=1;j<n;j++)
            if( ① ){
                segment t=A[j];
                ② ;
            }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>A[i].a>>A[i].b;
    sort();
    int p=1;
    for(int i=1;i<n;i++)
        if( ③ )
            A[p++]=A[i];
    n=p;
    int ans=0,r=0,q=0;
    while(r<m){
        while( ④ )q++;
        ⑤ ;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

39. ① 处填（） {{ select(39) }}

• A[j].b>A[j-1].b
• A[j].a<A[j-1].a
• A[j].a>A[j-1].a
• A[j].b<A[j-1].b

40. ② 处填（） {{ select(40) }}

• A[j+1]=A[j];A[j]=t;
• A[j-1]=A[j];A[j]=t;
• A[j]=A[j+1];A[j+1]=t;
• A[j]=A[j-1];A[j-1]=t;

41. ③ 处填（） {{ select(41) }}

• A[i].b>A[p-1].b
• A[i].b<A[i-1].b
• A[i].b>A[i-1].b
• A[i].b<A[p-1].b

42. ④ 处填（） {{ select(42) }}

• q+1<n&&A[q+1].a<=r
• q+1<n&&A[q+1].b<=r
• q<n&&A[q].a<=r
• q<n&&A[q].b<=r

43. ⑤ 处填（） {{ select(43) }}

• r=max(r,A[q+1].b)
• r=max(r,A[q].b)
• r=max(r,A[q+1].a)
• r=max(r,A[q].a)