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

1. 以下不是属于国家顶级域名的是( )。 {{ select(1) }}

• .au
• .cn
• .com
• .jp

2. 2个10进制数1111和1010的异或运算结果的10进制表示是()。 {{ select(2) }}

• 101
• 3
• 1957
• 5

3. 8位二进制数中去掉符号位,最大能表示多少字符()。 {{ select(3) }}

• 127
• 128
• 255
• 256

4. 在写递归函数时,哪些定义一般不写在递归函数中?()。 {{ select(4) }}

• int
• float
• double
• 数组

5. 一棵完全二叉树,共有1234个节点,其叶子结点的个数为( )。 {{ select(5) }}

• 615
• 616
• 617
• 210

6. 某公司派赵钱孙李周五人出国学习,选派条件是: a.若赵去,钱也去; b.李、周两人必有一人去; c.若周去,则赵、钱也同去; d.孙、李二人同去或同不去; 如何选他们出国?( )。 {{ select(6) }}

• 孙赵周去
• 赵钱周去
• 李周孙去
• 钱孙去

7. 已知一棵二叉树前序遍历为ABCDEFCI,后序遍历为CEDBICFA,则其中序遍历可能为 ()。 {{ select(7) }}

• ABCDEFGI
• CBEDAFIG
• CBDEAGFI
• CBEDAIFC

8. 8颗子弹,编号为1,2,3,4,5,6,7,8,从编号1开始按序嵌入弹夹,以下不是正常的打出子弹的次序的是()。 {{ select(8) }}

• 12345678
• 87654321
• 32154876
• 32164587

9. 已知循环队列空间为30,队头位置编号为12,队尾元素下一个空位置编号为5,则队伍中元素个数为( )。 {{ select(9) }}

• 22
• 23
• 7
• 8

10. 甲箱中有200个螺杆,其中有160个A型螺杆;乙箱中有240个螺母,其中有180个A型的。现从甲乙两箱中各任取一个,则能配成A型螺栓的概率为多少?()。 {{ select(10) }}

• 1/20
• 19/20
• 3/5
• 15/16

11. 今年信息学进复赛的同学有6人,老师将他们排成一圈分发奖品,一共有()种排法。 {{ select(11) }}

• 60
• 120
• 180
• 240

12. 设二维数组A的行下标为0至5,列下标为1至5,每个数据元素均占2个字节。在按行存贮的情况下,已知数据元素A[3][3]的第一个字节是2019,则A[4][4]的第一个字节的地址为( )。 {{ select(12) }}

• 2029
• 2025
• 2027
• 2031

13. 在下图中,有( )个顶点出发存在一条路径可以遍历图中的每条边,而且仅遍历一次。 {{ select(13) }}

• 6
• 2
• 3
• 4

14. 有A,B,C,D,E,F六个绝顶聪明又势均力敌的盗墓贼,他们都排着队,每个人都想独吞财宝。最前面的A如果拿了财宝,体力下降,则后面的B会杀掉A拿财宝；B拿了财宝体力下降,也会被C杀掉；如果B不拿财宝,则C无法杀B。若每个人杀人必拿财宝,且优先保命,请问A、C、E的最终想法是()。 {{ select(14) }}

• A不拿C不拿E拿
• A拿C拿E不拿
• A不拿C不拿E不拿
• A不拿C拿E拿

15. 以下不属于应用层的是( )。 {{ select(15) }}

• HTTP
• FTP
• TELNET
• UDP

二、阅读程序（共计40分；判断题每题1.5分，选择题每题3分，特殊标注除外）

（一）

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    char s1[100];
    int len,j=0;
    cin>>s;
    len=s.size();
    memset(s1,0, sizeof(s1));
    for(int i=0;i<len;i++){
        if(i%2==0)
            if ((s[i]>='A'&&s[i]<'z')||(s[i]>='a'&& s[i]<'z'))
            {
                s1[j]=s[i]+1;
                ++j;
            }
    }
    cout<<s1<<endl;
    return 0;
}

判断题 16. 输出的字符串只能是字母组成。() {{ select(16) }}

• 正确
• 错误

17. 若将第12行的"<"改为"<=",则输出结果有可能包含数字。() {{ select(17) }}

• 正确
• 错误

18. 将第9行删除,程序运行结果不会改变。() {{ select(18) }}

• 正确
• 错误

19. 若将第11行删除,则输出字符的长度和输入字符的长度一致。() {{ select(19) }}

• 正确
• 错误

选择题 20. 若输入的字符串长度为10,则输出的字符串长度最长可能为()。 {{ select(20) }}

• 4
• 5
• 6
• 10

21. 若输入的字符串都是字母,则输出中可能出现()。 {{ select(21) }}

• A
• Z
• a
• 以上都不对

（二）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[1001],i,j,t,n;
    for(i=0;i<=1000;i++)
        a[i]=0;
    scanf("%d", &n);
    for(i=1;i<=n;i++){
        scanf("%d",&t);
        a[t]++;
    }
    for(i=1000;i>=0;i--)
        for(j=1;j<=a[i];j++)
            printf("%d",i);
    return 0;
}

判断题 22. 输入10个数字,输出结果是从小到大。() {{ select(22) }}

• 正确
• 错误

23. 若输入的数字中有两个1,则输出时出来第一个1是第一个输入的。() {{ select(23) }}

• 正确
• 错误

24. 若将第13行的"<="改为"<",且输入数据为1 0 2 1 2 3 3 3 4 1 2 8 7 2 2 9 0,则输出2。() {{ select(24) }}

• 正确
• 错误

25. 若将第12行改为for(i=0;i<=1000;i++),则程序运行结果不变。() {{ select(25) }}

• 正确
• 错误

选择题 26. 若将第12行改为for(i=1000;i>1;i--);第13行为for(j=a[i];j>1;j--),输入数据为5 2 1 2 3 3 3 4 4 4,则运行结果( )。 {{ select(26) }}

• 不变
• 输出2 1 2 3 3 3 4 4 4
• 无输出
• 输出44 34 33 12 2

27. 若将第10行改为++a[t]或a[t++],则输入5 1 2 3 4 5,输出结果为()。 {{ select(27) }}

• 12345或54321
• 12345或无输出
• 54321或54321
• 54321或无输出

（三）

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000, INF=0x3f3f3f3f;
int L[maxn/2+2], R[maxn/2+2];
void unknown (int a[],int n,int left, int mid, int right)
{
    int n1=mid-left,n2=right-mid;
    for(int i=0;i<n1;i++) L[i]=a[left+i];
    for(int i=0;i<n2;i++) R[i]=a[mid+i];
    L[n1]=R[n2]=INF;
    int i=0,j=0;
    for(int k=left;k<right;k++){
        if(L[i]<=R[j]) a[k]=L[i++];
        else a[k]=R[j++];
    }
}
void unknownsort(int a[],int n,int left,int right){
    if(left+1<right){
        int mid=(left+right)/2;
        unknownsort (a,n,left,mid);
        unknownsort (a,n,mid, right);
        unknown (a,n,left,mid,right);
    }
}
int main(){
    int a[maxn],n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    unknownsort (a,n,0,n);
    for(int i=0;i<n;i++){
        cout<<a[i];
        if(i)cout<<" ";
    }
    cout<<endl;
    return 0;
}

判断题 28. 将第13行的"<"改为"<="不会改变运行结果。() {{ select(28) }}

• 正确
• 错误

29. 将第21行的"<"改为"<="不会改变运行结果。() {{ select(29) }}

• 正确
• 错误

30. 此类排序方法是高效的,但是不稳定。() {{ select(30) }}

• 正确
• 错误

31. 将第4行的2个"+2"都去掉不会改变运行结果。() {{ select(31) }}

• 正确
• 错误

选择题 32. 此题是哪种排序?()。 {{ select(32) }}

• 选择排序
• 桶排序
• 归并排序
• 堆排序

33. 此题用到了()思想。 {{ select(33) }}

• 动态规划
• 分治
• 冒泡
• 贪心

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

（一）田忌赛马

田忌每赢一次齐王的马就得200金币,输了就扣200金币,平局则金币数不变。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin!=0){
        int tj[1001],king[1001],count=0;
        int tj_min=0,tj_max=n-1;
        int king_min=0,king_max=n-1;
        for(int i=0;i<n;i++) cin>>tj[i];
        for(int i=0;i<n;i++) cin>>king[i];
        sort(tj,tj+n);
        sort(king,king+n);
        while (n--){
            if(tj[ ① ]>king[ ② ])
            {
                count++;
                tj_max--;
                king_max--;
            }
            else if(tj[ ③ ]<king[ ④ ])
            {
                count--;
                tj_min++;
                king_max--;
            }
            else
            {
                if(tj[tj_min]>king[king_min])
                {
                    count++;
                    ⑤
                    ⑥
                }
                else{
                    if( ⑦ )
                    count--;
                    tj_min++;
                    ⑧
                }
            }
        }
        cout<<count*200<<endl;
    }
    return 0;
}

34. ①处和②处填()。 {{ select(34) }}

• tj_max 和 king_max
• tj_min和king_max
• tj_min和king_max
• tj_max和king_min

35. ③处和④处填()。 {{ select(35) }}

• tj_min和king_max
• tj_min和king_min
• tj_max和king_max
• tj_max和king_min

36. ⑤处和⑥处填()。 {{ select(36) }}

• tj_min--和king_min++
• tj_max++和king_min++
• tj_min++和king_min++
• tj_max++和king_min--

37. ⑦处填()。 {{ select(37) }}

• tj[tj_min]<king[king_max]
• tj[tj_min]>king[king_max]
• tj[tj_max]<king[king_max]
• tj[tj_min]>king[king_min]

38. ⑧处填()。 {{ select(38) }}

• king_max--
• king_max++
• king_min--
• king_min++

（二）寻路问题

N*N矩阵,其中0表示可以走,1表示无法走,左上角是入口,右下角是出口,只能横着走和竖着走,要求找出最短路径。

#include<bits/stdc++.h>
using namespace std;
int mymax=10000;
int f[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int a[20][20],v[20][20],v1[20][20];
int l=1;
int n;
bool check(int x1,int y1){
    if(x1<0||x1>=n)return false;
    if(a[x1][y1]==1|| ① )return false;
    return true;
}
void dfs (int x,int y){
    if(x==n-1&&y==n-1){
        if(l<mymax){
            mymax=l;
            memcpy (v1,v,sizeof(v1));
        }
        return;
    }
    for(int k=0;k<4;k++){
        int x1,y1;
        x1=x+ ②
        y1=y+ ③ ;
        if(check(x1,y1)){
            ④
            ⑤
            dfs(x1,y1);
            ⑥
            ⑦
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    dfs (0,0);
    int d=v1[n-1][n-1];
    int x=n-1,y=n-1;
    int k;
    int qn[400][2];
    qn[0][0]=n-1; qn[0][1]=n-1;
    for(k=1;;k++){
        x=x-f[d][0];
        y=y-f[d][1];
        qn[k][0]=x; qn[k][1]=y;
        d=v1[x][y];
        if(x==0&&y==0)break;
    }
    for(int i=k;i>=0;i--)
        cout<< ⑧ <<","<< ⑨ <<endl;
    return 0;
}

39. ①处和②处填()。 {{ select(39) }}

• y1<=0||y1>n和v[x1][y1]>0
• y1<0||y1>=n和v[x1][y1]>0
• y1>0&&y1<=n和v[x1][y1]>0
• y1>0&&y1<n和v[x1][y1]>0

40. ③和④处填()。 {{ select(40) }}

• f[k][0]和f[k][1]
• f[k][1]和f[k][0]
• f[0][k]和f[1][k]
• f[1][k]和f[0][k]

41. ⑤处填()。 {{ select(41) }}

• v[x1][y1]=k+1;
• v[x1][y1]=k;
• v[x][y]=k;
• v[x][y]=k+1;

42. ⑥处和⑦处填()。 {{ select(42) }}

• l++和l--
• k++和k--
• x1++和x1--
• y1++和y1--

43. ⑧处和⑨处填( )。 {{ select(43) }}

• qn[i][1]和qn[i][2]
• qn[i][0]和qn[i][1]
• qn[1][i]和qn[2][i]
• qn[0][i]和qn[1][i]