一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

1. 在计算机的内存储器中,每个存储单元都被赋予一个唯一的序号,称为()。

{{ select(1) }}

• 下标
• 地址
• 指针
• 索引

2. 以下关于算法的描述中正确的是()。

{{ select(2) }}

• 算法一定要用某种计算机语言写成程序才有价值
• 要想实现算法,必须先画流程图
• 算法只需要用到数学的计算方法
• 算法是为解决问题而采取的方法与步骤

3. 一张分辨率为800×600的BMP图片,若每个像素用24位表示,那么这张图片所占用的存储空间是()。

{{ select(3) }}

• 1400KB
• 750KB
• 600KB
• 1000KB

4. 若某算法的计算时间表示为递推关系式: $T(N)=2T(N/2)+2N$，$T(1)=1$，则其时间复杂度为()。

{{ select(4) }}

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

5. 下列哪个特性不是数组和链表都可以实现的?()

{{ select(5) }}

• 数据元素之间的次序关系
• 数据元素的动态添加和删除
• 通过索引直接访问任意位置的数据元素
• 数据可以为任意类型

6. 如果$a=2$，那么经过运算$a=~-a+2$，最后a的值为()。

{{ select(6) }}

• 3
• 1
• 0
• 4

7. 用一个大小为7的数组来实现循环队列,且tail和head的值分别为1和4。当从队列中删除2个元素,再加入3个元素后,tail和head的值分别为()和()。

{{ select(7) }}

• 6 3
• 2 0
• 3 6
• 0 2

8. 关于二分算法,下列说法中错误的是()。

{{ select(8) }}

• 二分算法可以用于二分查找、二分答案等不同应用
• n个数的随机序列先排序再进行二分查找,总时间复杂度是$O(\log n)$
• 二分算法的左右区间可以左闭右闭,也可以左闭右开
• 二分算法是典型的使用分治思想的算法

9. 如下代码主要表示什么数据结构?()

typedef int LTDataType;
typedef struct ListNode {
    LTDataType data;
    struct ListNode* next;
} LTNode;

{{ select(9) }}

• 单向链表
• 双向链表
• 循环链表
• 优先队列

10. 关于字符串和字符串函数,以下说法中错误的是()。

{{ select(10) }}

• s="ccfgesp"占用8字节内存空间
• 在字典序下,字符串s1="123"比字符串s2="99"要小
• s.substr(2,4)表示截取字符串s[2]~s[4]这一段的字符
• cstring标准库包含了strcpy、strlen等函数

11. 在计算机历史上,科学家冯·诺依曼的主要贡献是()。

{{ select(11) }}

• 发明了第一台计算机ENIAC
• 破解了德军的ENIGMA密码
• 发明了二进制并应用到电子计算机中
• 提出存储程序的思想

12. 如下代码对树的操作是()。

void order(tree bt) {
    if(bt) {
        cout<<bt->value;
        order(bt->lchild);
        order(bt->rchild);
    }
}

{{ select(12) }}

• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

13. 给一排10个同样的玩偶的头发分别染红色和绿色,要求任意两个绿色头发的玩偶不能相邻,不同的染色方案共有()种。

{{ select(13) }}

• 136
• 140
• 144
• 150

14. 一棵完全二叉树共有2026个结点,则该树中共有()个叶子结点。

{{ select(14) }}

• 1014
• 1013
• 1012
• 1011

15. 无向图G中有2025个度为1的结点,2个度为2的结点,3个度为3的结点,4个度为4的结点,则无向图G有()条边。

{{ select(15) }}

• 1025
• 1026
• 1027
• 1028

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特殊说明外,判断题每题1.5分,选择题每题3分,共计40分)

(1)

01#include<bits/stdc++.h>
02using namespace std;
03const int N = 1e5+5;
04int n,T,x,y,sum[N],is_prime[N];
05int main(){
06    memset(is_prime,true,sizeof(is_prime));
07    for(int i=2;i<N;++i){
08        if(is_prime[i]){
09            for(int j=i+i;j<N;j+=i)
10                is_prime[j]=false;
11        }
12    }
13    for(int i=1;i<N;++i){
14        sum[i]=sum[i-1];
15        if(is_prime[i]) sum[i]+=1;
16    }
17    scanf("%d%d",&x,&y);
18    if(x>y) swap(x,y);
19    printf("%d\n",sum[y]-sum[x-1]);
20    return 0;
21}

判断题

16. 当输入为1 5时,输出为10。

{{ select(16) }}

• 正确
• 错误

17. 若去除第2行,程序仍能正常运行。

{{ select(17) }}

• 正确
• 错误

18. (2分)在运行第15行时,可能溢出int上界。

{{ select(18) }}

• 正确
• 错误

选择题

19. 若输入91 95,则输出为()。

{{ select(19) }}

• 0
• 184
• 91
• 188

20. (4分)该程序的时间复杂度为()。

{{ select(20) }}

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

(2)

01#include <bits/stdc++.h>
02using namespace std;
03int l,r,X;
04int restrict(int ql,int qr){
05    return max(0,qr-max(l,ql)+1);
06}
07int calc(int l,int r){
08    if(l>r)
09        return 0;
10    X=l;
11    while(X<=r)
12        X*=2;
13    X/=2;
14    return restrict(X,r)+calc(l,2*X-r-1);
15}
16int main(){
17    scanf("%d%d",&l,&r);
18    printf("%d\n",calc(l,r));
19    return 0;
20}

已知$1 ≤l ≤r ≤10^9$，回答以下问题。

判断题

21. 第14行中的$2*x-r-1$一定比l小。

{{ select(21) }}

• 正确
• 错误

22. 在运行第12行时,x可能会溢出int的上界。

{{ select(22) }}

• 正确
• 错误

23. $l=1$，$r=29$、$l=1$，$r=30$、$l=1$，$r=31$这三种情况的输出均一样。

{{ select(23) }}

• 正确
• 错误

24. 若输入为10 20,则输出为7。

{{ select(24) }}

• 正确
• 错误

选择题

25. 该程序的时间复杂度为()。

{{ select(25) }}

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

26. 若输入为1 2007,则输出为()。

{{ select(26) }}

• 1003
• 1004
• 1006
• 1007

(3)

01#include <bits/stdc++.h>
02using namespace std;
03const int N=5e3+5,mo=998244353;
04int n,j,ans1,ans2,mi,mj;
05int c[N][N],a[N],pre[N],suf[N];
06signed main(){
07    scanf("%d",&n);
08    c[0][0]=1;
09    for(int i=1;i<=n;++i)
10        for(int j=0;j<=i;++j)
11            c[i][j]=(c[i-1][j]+(j?c[i-1][j-1]:0))%mo;
12    for(int i=1;i<=n;++i){
13        scanf("%d",&a[i]);
14        if(a[i]==(n+1)/2) j=i;
15        else a[i]=(a[i]>(n+1)/2)?1:-1;
16    }
17    for(int i=1;i<=j-1;++i)
18        pre[i]=pre[i-1]+a[i];
19    for(int i=n;i>=j+1;--i)
20        suf[i]=suf[i+1]+a[i];
21    mi=0;
22    for(int i=1;i<=j-1;++i)
23        if(!pre[i])
24            ++ans1,mi=i+1;
25    mj=n;
26    for(int i=n;i>=j+1;--i)
27        if(!suf[i])
28            ++ans2,mj=i-1;
29    printf("%d %d\n",ans1+ans2+!(mi==mj),c[ans1+ans2][ans1]);
30    return 0;
31}

已知$n ≤5000$，n为奇数，a是长度为n的排列。完成下列各题。

判断题

27. 若pre数组的最大值为$\frac{n-1}{2}$，则输出为1 1。

{{ select(27) }}

• 正确
• 错误

28. 第29行中的c[ans1+ans2][ans1]可以改成c[ans1+ans2][ans2]。()

{{ select(28) }}

• 正确
• 错误

选择题

29. 若$n=9$，则输出的第一个数的最大值为()。

{{ select(29) }}

• 3
• 4
• 5
• 6

30. 若输入为7 1 6 2 4 5 7 3，则输出为()。

{{ select(30) }}

• 3 2
• 2 3
• 3 3
• 2 2

31. 若输入为7 3 5 4 1 7 2 6，则输出为()。

{{ select(31) }}

• 3 2
• 2 3
• 3 3
• 2 2

32. (4分)若$n=13$，则输出的第二个数的最大值为()。

{{ select(32) }}

• 6
• 10
• 20
• 36

三、完善程序(单选题,每小题3分,共计30分)

(1)题目描述: 给定一个长度不超过$10^4$的化学式,计算其分子质量。(分子质量即一个化学式中原子质量之和。) 化学式可能有如下两种构成。

• 若原子只出现了一次,则直接用大写字母表示,如H代表氢元素,原子质量为1。若化学式为两个字母,则首字母大写,第二个字母小写,如Mg代表镁元素,原子质量为24。
• 若原子出现了多次,则用元素_{数量}代表有几个这种元素的原子,如C_{2}代表有两个碳原子;H_{2}ClO_{4}则表示H元素出现了2次,Cl元素出现了1次,O元素出现了4次。相对分子质量为$1×2 + 35.5+16×4=101.5$。

编号	1	2	3	4	5	6	7	8	9	10	11	12
元素	H	C	N	O	F	P	S	Na	Mg	Al	Si	Cl
原子质量	1	12	14	16	19	31	32	23	24	27	28	35.5

01#include <bits/stdc++.h>
02using namespace std;
03const int N =5e5+5;
04const double val[N] = {0,1,12,14,16,19,31,32,23,24,27,28,35.5};
05int n,to[N];
06char s[N];
07double ans;
08int Hash(int x){
09    if(to[s[x+1]]>=8){
10        if(s[x+1]=='i')
11            return ①;
12        return to[s[x+1]];
13    }
14    return to[s[x]];
15}
16int read(int x){
17    int ans=0;
18    for(int i=x;i<=n;i++){
19        if(s[i]=='}') break;
20        ans=②;
21    }
22    return ans;
23}
24int main(){
25    to['H']=1,to['C']=2,to['N']=3,to['O']=4;
26    to['F']=5,to['P']=6,to['S']=7;
27    to['a']=8,to['g']=9,to['l']=10,to['i']=11;
28    scanf("%s",s+1);
29    n=strlen(s+1);
30    for(int i=1;i<=n;++i){
31        int x=Hash(i);
32        int j=i+1+(x>=8);
33        if(s[j]=='{'){
34            int k=③;
35            ans+=val[x]*k;
36            while(④) ++i;
37            continue;
38        }
39        ans+=val[x];
40        i+=(x>=8);
41        continue;
42    }
43    if(⑤) printf("%.0lf",ans);
44    else printf("%.1lf",ans);
45    return 0;
46}

33. ①处应填()。

{{ select(33) }}

• (s[x] =='C')?10:12
• (s[x]=='A')?12:10
• 10+2*(s[x]=='C')
• 10+2*(s[x]=='A')

34. ②处应填()。

{{ select(34) }}

• ans+(int)(s[i])
• ans*10+(int)(s[i])
• ans+s[i]-'0'
• ans*10+s[i]-'0'

35. ③处应填()。

{{ select(35) }}

• read(i+3)
• read(j+1)
• read(j+2)
• read(i+2)

36. ④处应填()。

{{ select(36) }}

• s[i]!='}'
• !(s[i]>='A'&&s[i]<='Z')
• !(s[i]>='0'&&s[i]<='9')
• i<=j

37. ⑤处应填()。

{{ select(37) }}

• ceil(ans+0.5) ==ans
• ceil(ans)==ans
• (int(ans))/2 ==ans/2
• int(ans+0.5)!=ans

(2)题目描述: 给定整数m,定义一个数列的权值为这个数列所有乘积大于或等于m的子序列(可以不连续)的和。例如数列[1,2,3],当$m=4$时,子序列[2,3]和[1,2,3]满足条件,这时此数列的权值为11。 现在给定整数n,m以及一个长度为n的数列A,请求出A的所有前缀数列A的权值。由于答案很大,输出对$10^9+7$取模。

01#include <bits/stdc++.h>
02using namespace std;
03const int N=1e5+5;
04const int mod=1e9+7;
05int n,m,sum,K,tot,f[2][1000],g[2][1000];
06int a[N],r[N],to[N],pw[N]={1};
07int main(){
08    scanf("%d%d",&n,&m);--m;
09    for(int i=1;i<=n;++i)pw[i]=pw[i-1]*2%mod;
10    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
11    for(int i=1;i<=m;++i){
12        if(①)++tot;
13        r[tot]=i;to[i]=tot;
14    }
15    for(int x=1;x<=n;++x){
16        int i=x%2,k=i^1;
17        for(int j=1;j<=tot;++j)
18            f[k][j]=g[k][j]=0;
19        if(a[x]<=m){
20            f[i][to[a[x]]]+=1;
21            g[i][to[a[x]]]+=②;
22        }
23        for(int j=1;j<=tot;++j){
24            f[k][j]+=f[i][j];
25            g[k][j]+=g[i][j];
26            if(a[x+1]*r[j]<=m){
27                int mj=③;
28                f[k][mj]+=f[i][j];
29                g[k][mj]+=④;
30            }
31        }
32        sum=⑤;
33        int rs=0;
34        for(int j=1;j<=tot;++j)
35            rs+=g[i][j];
36        printf("%d\n",(sum-rs+mod)%mod);
37    }
38    return 0;
39}

38. ①处应填()。

{{ select(38) }}

• i==1||m/i!=m/(i-1)
• i==1||m/i!=m/(i+1)
• m/i==m%(i-1)
• m/i!=m/(i+1)

39. ②处应填()。

{{ select(39) }}

• 1
• a[x]
• sum
• a[x]*pw[x-1]

40. ③处应填()。

{{ select(40) }}

• to[a[x+1]*r[j]-1]
• to[a[x]*r[j]]
• to[a[x+1]*r[j]]
• to[a[x+1]*r[j]+1]

41. ④处应填()。

{{ select(41) }}

• g[i][j]+f[i][j]*a[x+1]
• g[i][j]+f[i][j]*a[x+1]*pw[x-1]
• f[i][j]*a[x+1]
• f[i][j]*a[x+1]*pw[x-1]

42. ⑤处应填()。

{{ select(42) }}

• sum*2+pw[x]*a[x]
• sum+a[x]
• sum*2+pw[x-1]*a[x]
• (sum+a[x])*pw[x]