一、单项选择题（共15题，每题2分，共计30分；每题仅有一个正确选项）

1. 以下属于系统软件的是 {{ select(1) }}

• c++编译器
• 腾讯QQ
• CAD
• 游戏软件

2. 一字节，最高位符号位，00000001=+1，10000001=-1，该表示法整数范围 {{ select(2) }}

• $-127 \leq A \leq 127$
• $-128 \leq A \leq 128$
• $-128 \leq A<128$
• $-128<A<128$

3. 200中文、50英文、20半角空格，仅文字存储字节数 {{ select(3) }}

• 270字节
• 320字节
• 470字节
• 400字节

4. 属于网络分层模型名称的是 {{ select(4) }}

• LAN
• TCP/IP
• FTP
• SMTP

5. DFS不递归时常用数据结构 {{ select(5) }}

• 链表
• 队列
• 栈
• 散列表

6. 1~30顺时针一圈报数，数n对应学号 {{ select(6) }}

• $(n-1)\%30$
• $1+(n-1)\%30$
• $(n+1)\%30-1$
• $(n+1)\%30$

7. 完全二叉树共41个节点，叶子数量 {{ select(7) }}

• 18个
• 19个
• 20个
• 21个

8. 插入、冒泡、选择排序平均复杂度 {{ select(8) }}

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

9. 快速排序最慢初始序列 {{ select(9) }}

• 19,23,3,15,7,21,8
• 23,21,28,15,19,3,7
• 19,7,15,28,23,21,3
• 3,7,15,19,21,23,28

10. 算法定义 {{ select(10) }}

• 解决问题的计算机程序
• 解决问题的方法步骤
• 解决问题的编程语言
• 计算方法

11. 图的说法错误的是 {{ select(11) }}

• 所有顶点度数和=边数×2
• 所有顶点度数和不一定等于边数×2
• 任意图奇点数量为偶数
• 有向图入度总和=出度总和

12. 打印缓冲区先进先出，对应结构 {{ select(12) }}

• 堆栈
• 数组
• 队列
• 链表

13. 6人分两车，每车最多4人，分配方案数 {{ select(13) }}

• 40
• 50
• 60
• 70

14. 不用临时变量交换a,b，空缺代码

void swapAB (int &a, int &b)
{
    ;
    b=a-b;
    a=a-b;
}

{{ select(14) }}

• $a=a+b$
• $a=a*b$
• $a=a-b$
• $a=a \& b$

15. 1000个有序不同数字二分查找最坏比较次数 {{ select(15) }}

• 1000
• 10
• 100
• 500

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

阅读程序1 LIS朴素DP

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005],f[1005];
int main(){
    int i,j;
    cin>>n;int ans=0;
    for (i=0;i<n;i++) cin>>a[i];
    for(i=0;i<n;++i){
        f[i]=1;
        for(j=i-1;j>=0;--j)
            if (a[i]>a[j])f[i]=max(f[i],f[j]+1);
        ans =max (ans,f[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

16. int i,j;改为int i;编译报错 {{ select(16) }}

• √
• ×

17. a[i]>a[j]改成a[i]<a[j]输出不变 {{ select(17) }}

• √
• ×

18. f[i]代表以i结尾最长上升子序列长度 {{ select(18) }}

• √
• ×

19. i=0改为i=1运行结果不变 {{ select(19) }}

• √
• ×

20. n=100，ans最大值 {{ select(20) }}

• 90
• 50
• 99
• 100

21. n=15，序列5,7,6,8,1,3,5,4,2,9,14,11,12,8,7，ans为 {{ select(21) }}

• 3
• 7
• 6
• 5

阅读程序2 归并排序+加权和

#include<iostream>
using namespace std;
const int maxn=100005;
int n;
int a[maxn];
int b[maxn];
void solve(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)/2;
    solve (l,mid) ;solve (mid+1,r);
    int i=1,j=mid+1,k=1;
    while (i<=mid &&j<=r)
    {
        if (a[i]<=a[j])b[k++]=a[i++];
        else b[k++]=a[j++];
    }
    while (i<=mid) b[k++]=a[i++];
    while(j<=r)b[k++]=a[j++];
    for(int i=1;i<=r;i++)a[i]=b[i];
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    solve (1,n);
    int ans=0;
    for (int i=1;i<=n;i++) ans=ans+a[i]*i;
    cout<<ans<<endl;
    return 0;
}

22. a含重复数字程序可正常运行 {{ select(22) }}

• √
• ×

23. 排序后a单调不增 {{ select(23) }}

• √
• ×

24. 输入1 2 3 … n，输出 {{ select(24) }}

• $n \times n$
• $n(n+1)/2$
• $n(n+1)(n+2)/6$
• $n(n+1)(2n+1)/6$

25. 输入5 50 60 30 40 50输出 {{ select(25) }}

• 660
• 760
• 770
• 720

26. 四组输入答案最大的是 {{ select(26) }}

• 5 30 50 60 70 70
• 5 20 30 50 50 80
• 5 10 10 70 70 50
• 5 60 70 70 55

阅读程序3 统计连续0段长度

#include<stdio.h>
char c[200][200];
int s[200],m,n;
void numara()
{
    int i,j,cod,nr;
    for(j=0;j<n;j++){
        nr=0;cod=1;
        for(i=0;i<m;i++){
            if(c[i]=='1'){
                if (!cod){cod=1;s[nr]++;nr=0;}
            }
            else{
                if(cod){nr=1;cod=0;}
                else nr++;
            }
        }
        if (!cod) s[nr]++;
    }
}
int main(){
    int i,j;
    scanf("%d%d\n",&m, &n);
    for(i=0;i<m;i++) gets(c[i]);
    numara();
    for(i=1;i<=m;i++)
        if (s[i]!=0)printf("%d %d",i,s[i]);
    return 0;
}

27. int i,j;改为int i;编译报错 {{ select(27) }}

• √
• ×

28. 程序最少输出0个数字，最多输出2*m个 {{ select(28) }}

• √
• ×

29. s[i]代表有i个0的列数量 {{ select(29) }}

• √
• ×

30. cod=1两处全部替换，运行结果不变 {{ select(30) }}

• √
• ×

31. m=100,n=100，s[1]最大值 {{ select(31) }}

• 100
• 500
• 1000
• 5000

32. m=95,n=95，s[5]最大值 {{ select(32) }}

• 760
• 950
• 1520
• 1900

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

完善程序1 二叉树变换判定

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m,tot;
int lc[N],rc[N];
vector<int>t;
inline bool isleaf(int u){
    ①;
}
inline bool solve (vector<int>t){
    if (t.empty()) return false;
    for (auto o:t)
        if(isleaf (o))return true;
    vector<int>t1,t2,t3,t4;
    for (auto o:t){
        if (!lc[o]) t2.push_back (rc[o]);
        if (!rc[o]) t1.push_back (lc[o]);
        if(②){
            if (isleaf (lc[o])) t3.push_back (rc[o]);
            if (isleaf (rc[o])) t4.push_back (lc[o]);
        }
    }
    ③;
}
int main(){
    scanf ("%d", &m);
    for(inti=1;i<=m;++i){
        int n;
        ④;
        for(intj=1;j<=n;++j){
            scanf("%d",&lc[tot+j]);
            if (lc[tot+j]) lc[tot+j]+=tot;
            scanf("%d",&rc[tot+j]);
            if (rc[tot+j]) rc[tot+j]+=tot;
        }
        ⑤;
        if (solve(t))printf("Almost Complete\n");
        else printf("No\n");
    }
    return0;
}

33. ①处 {{ select(33) }}

• lc[u]&&rc[u]
• !lc[u]&&!rc[u]
• lc[u]||rc[u]
• !lc[u]||!rc[u]

34. ②处 {{ select(34) }}

• lc[o]&&rc[o]
• !lc[o]&&!rc[o]
• lc[o]||rc[o]
• !lc[o]||!rc[o]

35. ③处 {{ select(35) }}

• return solve(t1)&&solve(t2)&&solve(t3)&&solve(t4)
• return solve(t1)||solve(t2)||solve(t3)||solve(t4)
• return (solve(t1)&&solve(t2))||(solve(t3)&&solve(t4))
• return (solve(t1)||solve(t2))&&(solve(t3)||solve(t4))

36. ④处 {{ select(36) }}

• tot++
• tot =0
• t.push_back(1+tot)
• t.push_back(1)

37. ⑤处 {{ select(37) }}

• tot +=n
• tot++
• tot =0
• t.clear()

完善程序2 一笔画判定

#include<stdio.h>
#include<math.h>
int orig,n,ns,bun;
int a[102][102];
int d[]={1,0,-1,0,0,1};
void plimba (int x,int y){
    int i,xx,yy;
    a[x][y]=-a[x][y];
    if (abs(a[x-1][y])!=orig && ①!=a[x-1][y]
        || abs(a[x-1][y])!=orig) ns++;
    if (abs(a[x+1][y])!=orig && (a[x+1][y-1]!=a[x+1][y]
        || abs(a[x][y-1])!=orig)) ns++;
    if (abs(a[x][y-1])!=orig && (②|| abs(a[x][y-1])!=orig)) ns++;
    if (abs(a[x][y+1]) !=orig && (a[x-1][y+1]!=a[x][y+1]
        || abs(a[x-1][y])!=orig)) ns++;
    for(i=0;i<4;i++){
        xx=x+d[2*i];yy=y+③;
        if xx>=1 &&xx<=n &&yy>=1 && ④)
            plimba (xx,yy);
    }
}
int main(){
    int i,j;
    bun=1;
    scanf ("%d",&n);
    for(i=0;i<=n+1;i++) for (j=0;j<=n+1;j++) a[i][j]=0;
    a[0][0]=-1;a[n+1][0]=-1;
    a[0][n+1]=-1;a[n+1][n+1]=-1;
    for(i=1;i<=n;i++)
        for (j=1;j<=n;j++) scanf("%d",&a[i][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            if(a[i][j]>-1){
                ⑥;
                plimba(i,j);
                if(ns%2==1)bun=0;
            }
        }
    if (bun) printf("YES\n");else printf("NO\n");
    return 0;
}

38. ①处 {{ select(38) }}

• a[x][y-1]
• a[x-1][y+1]
• a[x-1][y-1]
• a[x+1][y+1]

39. ②处 {{ select(39) }}

• a[x][y-1]
• a[x-1][y+1]
• a[x-1][y-1]
• a[x+1][y+1]

40. ③处 {{ select(40) }}

• d[2*i-1]
• d[i]
• d[i-1]
• d[2*i+1]

41. ④处 {{ select(41) }}

• abs(a[xx][yy]))!=orig
• abs(a[xx][yy])==orig
• a[xx][yy]!=orig
• a[xx][yy]==orig

42. ⑤处 {{ select(42) }}

• orig=a[i][j]
• orig=-a[i][j]+bun
• orig=bun
• orig =abs(a[i][j]) +bun