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

1. 关于 ASCII，下面哪个说法是正确的？

{{ select(1) }}

• ASCII 码就是键盘上所有键的唯一编码。
• 一个 ASCII 码使用一个字节的内存空间就能够存放。
• 最新扩展的 ASCII 编码方案包含了汉字和其他欧洲语言的编码。
• ASCII 码是英国人主持制定并推广使用的。

2. 分辨率为 $1600\times 900$、16 位色的位图，存储图像信息所需的空间为（　）。

{{ select(2) }}

• 2812.5 KB
• 4218.75 KB
• 4320 KB
• 2880 KB

3. 若某算法的计算时间表示为递推关系式：

$$T(N)=2T\left(\frac{N}{2}\right)+N\log N,\qquad T(1)=1,$$

则该算法的时间复杂度为（　）。

{{ select(3) }}

• $O(N)$
• $O(N\log N)$
• $O(N\log^2 N)$
• $O(N^2)$

4. 有向图中每个顶点的度等于该顶点的（　）。

{{ select(4) }}

• 入度
• 出度
• 入度和出度之和
• 入度和出度之差

5. 在 C++ 语言中，表达式 23|2^5 的值是（　）。

{{ select(5) }}

• 18
• 1
• 23
• 32

6. $\left(2070\right)_{16}+\left(34\right)_8$ 的结果不是（　）。

{{ select(6) }}

• $\left(8332\right)_{10}$
• $\left(208C\right)_{16}$
• $\left(100000000110\right)_2$
• $\left(20214\right)_8$

7. 已知 7 个结点的二叉树的先根遍历是 1 2 4 5 6 3 7（数字为结点的编号，以下同），后根遍历是 4 6 5 2 7 3 1，则该二叉树的不可能的中根遍历是（　）。

{{ select(7) }}

• 4 2 6 5 1 7 3
• 4 2 5 6 1 3 7
• 4 2 3 1 5 6 7
• 4 2 5 6 1 7 3

8. 一个圆上有 6 个顶点 ABCDEF，以其中三点为顶点，可以连出多少个三角形？

{{ select(8) }}

• 18
• 6
• 120
• 20

9. 从 A 点只能向上或者向右走，沿方格线到达 B 点，共有多少种走法？

{{ select(9) }}

• 7
• 35
• 15
• 20

10. 自然数中 0～9 任意选四个不同的数，组成一个四位数，共可以组成多少个这样的四位数？

{{ select(10) }}

• 5040
• 4536
• 3024
• 210

11. 一个数列，其中任意五个相邻项之和为 2010。已知第一个数是 1，第 9 个数是 9，第 17 个数是 9，第 2008 个数是 3，求第 2010 个数是多少？

{{ select(11) }}

• 1988
• 1998
• 2022
• 2032

12. 在两条直线上，分别有五个点和四个点，从中任选三个点组成三角形，有（　）种情况。

{{ select(12) }}

• 84
• 70
• 72
• 96

13. 完全二叉树共有 $2\times N-1$ 个结点，则它的叶节点数是（　）。

{{ select(13) }}

• $N-1$
• $N/2$
• $N$
• $N/2-1$

14. 在含有 $n$ 个元素的双向链表中查询是否存在关键字为 $k$ 的元素，最快情况下运行的时间复杂度是（　）。

{{ select(14) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n\log n)$

15. 有以下结构体说明和变量定义，如图所示，指针 p,q,r 分别指向一个链表中的三个续结点。

struct node {
    int data;
    struct node *next;
} *p, *q, *r;

现要将 q 和 r 所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是（　）。

{{ select(15) }}

• q->next = r->next; p->next = r; r->next = q;
• p->next = r; q->next = r->next; r->next = q;
• q->next = r->next; r->next = q; p->next = r;
• r->next = q; q->next = r->next; p->next = r;

二、阅读程序（满分 40 分，判断题 1.5 分，选择题除特殊说明外 3 分）

判断题请选择“正确”或“错误”。

阅读 1

01  #include <bits/stdc++.h>
02  long long n, m, t, a[1000005];
03  int main() {
04      scanf("%lld%lld", &n, &m);
05      while (m > 0) {
06          t++;
07          m--;
08          if (m <= 0)
09              break;
10          a[t] = a[t - 1] + 1;
11          while (m > (1 << n - a[t]) && a[t] <= n) {
12              m -= 1 << n - a[t];
13              a[t]++;
14          }
15      }
16      if (t != 1)
17          for (int i = 1; i < t; i++)
18              printf("%lld ", a[i]);
19      else
20          puts("0");
21      return 0;

原卷程序截图到第 21 行为止，未显示 main 函数最后的右花括号。

16. 第 20 行的 "0" 改成 '0'，程序运行会报错。（　）

{{ select(16) }}

• 正确
• 错误

17. 输入的 n 如果是负整数，程序运行不会报错。（　）

{{ select(17) }}

• 正确
• 错误

18. 第 10 行的功能是对 a 数组求前缀和。（　）

{{ select(18) }}

• 正确
• 错误

19. 输入的 n 最大可以到 1000000。（　）

{{ select(19) }}

• 正确
• 错误

20. 输入 4 12，输出（　）。

{{ select(20) }}

• 0
• 2 3
• 2 3 4
• 1 2 3

21. 当输入 n 为 3，m 为 1～8 之间的整数时，平均输出整数的个数（保留一位小数）是（　）。

{{ select(21) }}

• 1.0
• 1.6
• 1.8
• 2.0

阅读 2

01  #include<iostream>
02  #include<cstring>
03  using namespace std;
04  string A,B;
05  char s1[2005],s2[2005];
06  int edit[2005][2005];
07  int dfs(int i,int j){
08      if(edit[i][j]!=-1)
09          return edit[i][j];
10      if(i==0)
11          return edit[i][j]=j;
12      if(j==0)
13          return edit[i][j]=i;
14      int bonus=1;
15      if(s1[i]==s2[j])
16          bonus=0;
17      return edit[i][j]=min(min(dfs(i-1,j)+1,dfs(i,j-1)+1),dfs(i-1,j-1)+bonus);
18  }
19  int main(){
20      cin>>A>>B;
21      memset(edit,-1,sizeof(edit));
22      int len1=A.length(),len2=B.length();
23      for(int i=1;i<=len1;i++)
24          s1[i]=A[i-1];
25      for(int i=1;i<=len2;i++)
26          s2[i]=B[i-1];
27      dfs(len1,len2);
28      cout<<edit[len1][len2];
29      return 0;
30  }

输入的字符串只包含小写字母 a～z。

22. 第 8 行和第 21 行的 -1 如果改成 -2，程序运行结果可能不一样。（　）

{{ select(22) }}

• 正确
• 错误

23. $n$ 是输入的两个字符串长度的最大值，程序的时间复杂度为 $O(3^n)$。（　）

{{ select(23) }}

• 正确
• 错误

24. 输出的最小值为 -1。（　）

{{ select(24) }}

• 正确
• 错误

25. len1 和 len2 为执行完第 22 行后的值，输出的最大值为 len1+len2。（　）

{{ select(25) }}

• 正确
• 错误

26. 输入为 sfdqxbw gfdgw，输出（　）。

{{ select(26) }}

• 2
• 3
• 4
• 5

27. **（4 分）**保证输入的两个字符串长度均为 100，且只包含小写字母 a～z。第一个字符串为 "acegikmoqsuwyace...uwy...ace...moq"，第二个字符串为 "abcdefghijklmnopqrstuvwxy...abc...wxyabcd"（“...”表示省略了中间的字符），输出为（　）。

{{ select(27) }}

• 4
• 13
• 50
• 96

阅读 3

01  #include<iostream>
02  #include<cstdio>
03  #define mod 9901
04  using namespace std;
05  int a,b,sa,n[10010][2],cot=0,ans=1;
06  int q(int ml,int nl){
07      int s=1;
08      while(nl>0){
09          if(nl%2==1){
10              s=(s%mod)*(ml%mod)%mod;
11          }
12          ml=ml*ml%mod;
13          nl=nl>>1;
14      }
15      return s%mod;
16  }
17  int sum(int x,int y){
18      int k=0;
19      y=y*b;
20      if(x%mod==1){
21          k=(y+1)%mod;
22      }
23      else{
24          k=(q(x%mod,y+1)-1)%mod*q((x-1)%mod,mod-2)%mod;
25      }
26
27      return k%mod;
28  }
29  int main(){
30      scanf("%d%d",&a,&b);
31      if(a==0){
32          printf("0\n");
33          return 0;
34      }
35      for(int i=2;i*i<=a;i++){
36          if(a%i==0){
37              cot++;
38              n[cot][0]=i;
39              n[cot][1]=1;
40              a=a/i;
41              while(a%i==0){
42                  n[cot][1]++;
43                  a=a/i;
44              }
45          }
46      }
47      if(a!=1){
48          cot++;
49          n[cot][0]=a;
50          n[cot][1]=1;
51      }
52      for(int i=1;i<=cot;i++){
53          ans=ans*sum(n[i][0],n[i][1])%mod;
54      }
55      printf("%d\n",(ans%mod+mod)%mod);
56      return 0;
57  }

28. 第 35 行的 i*i 改成 i，运行结果不变。（　）

{{ select(28) }}

• 正确
• 错误

29. 第 3 行 9901 换成 1e9+7，运行结果不变。（　）

{{ select(29) }}

• 正确
• 错误

30. n[cot][0] 随着 cot 的增大而增大。（　）

{{ select(30) }}

• 正确
• 错误

31. 第 27 行删除 %mod，结果不变。（　）

{{ select(31) }}

• 正确
• 错误

32. 输入为 2 3，输出（　）。

{{ select(32) }}

• 4
• 8
• 9
• 15

33. 输出为 542，输入可能是以下哪组数据？（　）

{{ select(33) }}

• 210 5
• 210 6
• 330 5
• 330 6

34. 输入为 217823 1，输出为（　）。

{{ select(34) }}

• 1
• 2
• 9901
• 22

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

完善 1

众所周知，2 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6…。我们说 2 的正整数次幂最后一位的循环长度是 4（实际上 4 的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：

数字	循环	循环长度
2	2,4,8,6	4
3	3,9,7,1
4	4,6	2
5		1
6
7	7,9,3,1	4
8	8,4,2,6
9	9,1	2

这时问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数 $n$ 的正整数次幂来说，它的后 $k$ 位是否会发生循环？如果循环的话，循环长度是多少呢？

注意：

• 如果 $n$ 的某个正整数次幂的位数不足 $k$，那么不足的高位看做是 0。
• 如果循环长度是 $L$，那么说明对于任意的正整数 $a$，$n$ 的 $a$ 次幂和 $a+L$ 次幂的最后 $k$ 位都相同。
• $1\le n<10^{100}$，$1\le k\le100$。

输入共一行，包含 2 个整数 $n$ 和 $k$。$n$ 和 $k$ 之间用一个空格隔开，表示要求 $n$ 的正整数次幂的最后 $k$ 位的循环长度。

输出一个整数，表示循环长度。如果循环不存在，输出 -1。

试补全程序：

#include<bits/stdc++.h>
using namespace std;
int k;
struct BNR{
    int a[105];
    int len;
    BNR(){
        memset(a,0,sizeof(a));
        len=0;
    }
};
typedef BNR bign;

void cpy(①,bign y){
    x.len=y.len;
    for(int i=1;i<=x.len;i++)
        x.a[i]=y.a[i];
}

void in(①){
    char ch=getchar();x.len=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch<='9'&&ch>='0')
        x.len++,x.a[x.len]=(int)ch-'0',ch=getchar();
    for(int i=1;i<=x.len/2;i++)
        swap(x.a[i],②);
}

void out(①){
    for(int i=x.len;i>=1;i--)
        cout<<x.a[i];
    cout<<endl;
}

void AAA(①,bign y){
    for(int i=1;i<=min(y.len,k);i++)
        x.a[i]+=y.a[i];
    x.len=0;
    for(int i=1;i<=k;i++){
        if(x.a[i])x.len=max(x.len,i);
        x.a[i+1]+=x.a[i]/10,x.a[i]%=10;
    }
}

bign z;
void BBB(①,bign y){
    z.len=0;
    memset(z.a,0,sizeof(z.a));
    for(int i=1;i<=min(x.len,k);i++)
        for(int j=1;③<=k;j++)
            z.a[③] += x.a[i]*y.a[j];
    for(int i=1;i<=k;i++)
    {
        if(z.a[i])z.len=max(z.len,i);
        z.a[i+1]+=z.a[i]/10,z.a[i]%=10;
    }
    cpy(x,z);
}

int main()
{
    bign n;
    in(n);
    cin>>k;
    bign p;
    p.len=1;
    p.a[1]=④;
    bign ans,now,t,kt=n,f,mmm=n;

    cpy(ans,p);cpy(now,n);cpy(kt,n);cpy(mmm,n);
    for(int i=1;i<=k;i++){
        cpy(kt,mmm);cpy(f,ans);cpy(mmm,p);
        int flag=0;
        if(i==1)BBB(now,kt);
        for(int j=1;j<=10;j++)
        {
            BBB(mmm,kt);
            if(⑤){
                flag=1;
                break;
            }
            BBB(now,kt);
            AAA(ans,f);
        }
        if(!flag){
            cout<<"-1";return 0;
        }
    }
    out(ans);
    return 0;
}

35. ① 处应填（　）。

{{ select(35) }}

• bign x
• bign &x
• bign x[]
• bign *x

36. ② 处应填（　）。

{{ select(36) }}

• x.a[x.len-i]
• x.a[x.len/2-i]
• x.a[x.len/2-i+1]
• x.a[x.len-i+1]

37. ③ 处应填（　）。

{{ select(37) }}

• i+j-1
• i+j
• i
• z.len-i-j

38. ④ 处应填（　）。

{{ select(38) }}

• 0
• 1
• k
• -1

39. ⑤ 处应填（　）。

{{ select(39) }}

• now.a[i]!=n.a[i]
• now.a[i]!=n.a[j]
• now.a[i]==n.a[i]
• now.a[i]==n.a[j]

完善 2

二叉树是一种基本的数据结构，它要么为空，要么由根节点、左子树和右子树组成，同时左子树和右子树也分别是二叉树。

当一颗二叉树高度为 $m-1$ 时，则共有 $m$ 层。除 $m$ 层外，其他各层的结点数都达到最大，且结点节点都在第 $m$ 层时，这就是一个满二叉树。

现在，需要你用程序来绘制一棵二叉树，它由一颗满二叉树去掉若干结点而成。对于一颗满二叉树，我们需要按照以下要求绘制：

1. 结点用小写字母 o 表示。对于一个父亲结点，用 / 连接左子树，同样用 \ 连接右子树。
2. 定义 [i,j] 为位于第 $i$ 行第 $j$ 列的某个字符。若 [i,j] 为 /，那么 [i-1,j+1] 与 [i+1,j-1] 要么为 o，要么为 /。若 [i,j] 为 \，那么 [i-1,j-1] 与 [i+1,j+1] 要么为 o，要么为 \。同样，若 [i,j] 为第 1～$m$ 层的某个节点（即 o），那么 [i+1,j-1] 为 /，[i+1,j+1] 为 \。
3. 对于第 $m$ 层节点，也就是叶子结点，若两个属于同一个父亲，那么它们之间由 3 由 3 个空格隔开；若两个结点相邻但不属于同一个父亲，那么它们之间由 1 个空格隔开。第 $m$ 层左数第 1 个节点之前没有空格。

最后需要在一颗绘制好的满二叉树上删除 $n$ 个结点（包括它的左右子树，以及与父亲的连接），原有的字符用空格替换。

输入的第 1 行包含 2 个正整数 $m$ 和 $n$，为需要绘制的二叉树层数已经从 $m$ 层满二叉树中删除的结点数。接下来 $n$ 行，每行两个正整数，表示第 $i$ 层第 $j$ 个结点需要被删除。

例如，输入：

4 0

输出：

输入：

4 3
3 2
4 1
3 4

输出：

提示：关于树枝长度的规律：

层数	1	2	3	4	5
树枝长 len	1	2	5	11	23
规律		$1+(2-1)$	$(1+2)+(3-1)$	$(1+2+5)+(4-1)$	$(1+2+5+11)+(5-1)$

试补全程序：

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a;i <= b;i++)
using namespace std;

const int N = 3100;
int len[20],m,n,pos[20],h[20];
char a[N][N];

void prepare(){
    int sum = 1;
    len[1] = 1;pos[1] = 1;
    FOR(i,2,m) {
        len[i] = ①;
        sum += len[i];
        pos[i] = len[i] + 1;
    }
    h[m] = 1;
    for(int i = m-1; i ;i --)
        h[i] = h[i+1]+len[i]+1;
    memset(a,' ',sizeof(a));
}

void draw(int x,int y,int depth){
    a[x][y] = 'o';
    if(②) return;
    int lx = x+1,ly = y-1,rx = x+1,ry = y+1;
    FOR(i,1,len[depth-1]){
        a[lx][ly] = '/';
        a[rx][ry] = '\\';
        lx = lx+1,ly = ly-1,rx = rx+1,ry = ry+1;
    }
    draw(lx,ly,depth-1);
    draw(rx,ry,depth-1);
}

void destroy(int x,int y){
    a[x][y] = ' ';
    if(a[x-1][y-1] == '\\')destroy(x-1,y-1);
    ③;
    if(a[x+1][y-1] == '/' || a[x+1][y-1] == 'o')
        destroy(x+1,y-1);
    if(a[x+1][y+1] == '\\' || a[x+1][y+1] == 'o')
        destroy(x+1,y+1);
}

void print(){
    int height = h[1];
    int width = 6 * (1<<(m-1));
    FOR(i,1,height){
        FOR(j,1,width)
            printf("%c",a[i][j]);
        printf("\n");
    }
}

int main(){
    cin >> m >> n;
    prepare();
    draw(④);
    while(n--){
        int i,j;
        cin>>i>>j;
        if(i > 10) continue;
        int x = h[⑤],y;
        if(i == m){
            if(j & 1) y = pos[1] + j/2*6;
            else y = pos[1] + j/2*6 - 2;
        }
        else
            y = pos[⑤] + (j-1) * (2 * len[⑤] + 2);
        destroy(x,y);
    }
    print();
    return 0;
}

40. ① 处应填（　）。

{{ select(40) }}

• i
• len[i-1]+1
• len[i-1]+i
• sum+i-1

41. ② 处应填（　）。

{{ select(41) }}

• depth==0
• depth==1
• x==0
• x==y

42. ③ 处应填（　）。

{{ select(42) }}

• if(a[x-1][y-1] == '\\')destroy(x-1,y-1);
• if(a[x-1][y-1] == '/')destroy(x-1,y-1);
• if(a[x-1][y+1] == '/')destroy(x-1,y+1);
• if(a[x-1][y+1] == '\\')destroy(x-1,y+1);

43. ④ 处应填（　）。

{{ select(43) }}

• 1,pos[m],m
• 1,pos[m],1
• 1,pos[1],m
• 1,pos[1],1

44. ⑤ 处应填（　）。

{{ select(44) }}

• i
• m-i
• m+1-i
• m-1+i