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

1. 表达式$a\times(b+c)-d/f$转后缀表达式的结果是。 {{ select(1) }}

• abex+df-/
• abc+xdf/
• bc+axdf/
• abc+x-df/

2. 以下字符串中，字典序最小的是。 {{ select(2) }}

• NOIP2017
• NOIPC
• NOIPC++
• NOIPP

3. 在C++中，表达式('0'^'I')*13%9+5的值是。 {{ select(3) }}

• 7
• 8
• 14
• 15

4. 在8个数中找出最小值与最大值，最坏情况下最少需要比较多少次。 {{ select(4) }}

• 9
• 10
• 12
• 13

5. 在TCP/IP协议族中，最核心的网络协议是。 {{ select(5) }}

• UDP
• HTTP
• TCP
• IP

6. 分治实现求第K大数，不考虑极端最坏，最低期望时间复杂度。 {{ select(6) }}

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

7. 主机外设缓冲池，先进先出读写，适合的数据结构。 {{ select(7) }}

• 堆栈
• 队列
• 二叉树
• 链表

8. $(1E34)_{16}-(676)_8$ 的结果是。 {{ select(8) }}

• $(1110001111110)_2$
• $(7276)_{10}$
• $(1C6C)_{16}$
• $(16166)_8$

9. 二叉树前序ABDECFCH，后EDBCFHCA，不可能的中序遍历。 {{ select(9) }}

• DEBAFCCH
• EDBAGFCH
• DBEAFCCH
• BEDAFCCH

10. 栈输入1,2,3,4,5，不可能的输出序列。 {{ select(10) }}

• 54321
• 24135
• 32541
• 13542

11. 不使用Linux内核的操作系统。 {{ select(11) }}

• Android
• CentOS
• Windows
• Ubuntu

12. 关于计算机算法说法正确的是。 {{ select(12) }}

• 可无限优化降低复杂度
• 评判标准是单台机器运行时间
• 算法至少一个输入
• NPC问题尚无多项式解法

13. 下列二叉正确描述有几个： A.n节点二叉树高度至少$\log_2 n$ B.$n_0=n_2+1$ C.深度k至多$2^k$个点 D.前序后序不可能相同 E.完全二叉树深度$\lfloor\log_2(n+1)\rfloor$ {{ select(13) }}

• 0
• 1
• 2
• 3

14. 不稳定排序算法。 {{ select(14) }}

• 直接插入排序
• 快速排序
• 冒泡排序
• 归并排序

15 手环染色，旋转翻转同算一种，$m=5,n=4$方案数。 {{ select(15) }}

• 625
• 160
• 60
• 120

二、阅读程序（判断1.5分，选择4/5分，共40分）

阅读程序1 汉诺塔计数

#include<iostream>
using namespace std;
unsigned short tot;
void Hanoi (int n, char A, char B, char C){
    ++tot;
    if(n==1){
        cout<<A<<"->"<<C<<'/';
        return;
    }
    Hanoi (n-1,A,C,B);
    cout<<A<<"->"<<C<<'/';
    Hanoi (n-1,B,A,C);
}
int main(){
    int n;
    cin>>n;
    Hanoi (n,'A','B','C');
    cout<<'\n'<<tot<<'\n';
    return 0;
}

16. 第6行++tot移到13、14行间，输出不变。 {{ select(16) }}

• √
• ×

17. 输入2，第一行输出A->B/B->C/A->C/。 {{ select(17) }}

• √
• ×

18. 输入3，第二行输出8。 {{ select(18) }}

• √
• ×

19. 程序输出最少移动步骤与总次数，规则大盘不压小盘。 {{ select(19) }}

• √
• ×

20. n=3，第一行第21个字符。 {{ select(20) }}

• A
• B
• C
• /

21. n=17，第二行输出。 {{ select(21) }}

• -1
• 131071
• 131072
• 65535

阅读程序2 螺旋矩阵填充

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
const int N=105;
int a[N][N];
int main(){
    int n,x,y,count;
    cin>>n;
    memset (a,0,sizeof (a));
    count=a[x=0][y=n-1]=1;
    while (count<n*n){
        while (x+1<n &&!a[x+1][y]) a[++x][y]=++count;
        while (y-1>=0 &&!a[x][y]) a[x][--y]=++count;
        while (x-1>=0 &&!a[x][y]) a[--x][y]=++count;
        while (y+1<n &&!a[x][y])a[x][++y]=++count;
    }
    for(x=0;x<n;x++){
        for (y=0;y<n;y++){
            cout<<setw (5)<<a[x][y];
        }
        cout<<endl;
    }
    return0;
}

22. 删除第10行memset不影响运行。 {{ select(22) }}

• √
• ×

23. while(count<nn)改为while(count<=nn)无影响。 {{ select(23) }}

• √
• ×

24. n=4时a[3][2]=15。 {{ select(24) }}

• √
• ×

25. 程序时间复杂度。 {{ select(25) }}

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

26. n=100，a[33][66]的值。 {{ select(26) }}

• 8779
• 8707
• 10957
• 8845

阅读程序3 凯撒移位+数字交换

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
string s;
int main(){
    int k;
    cin>>k>>s;
    int n=s.length();
    for(int i=0;i<n;i++){
        if (s[i]<='z'&&s[i]+k>'z')
            s[i]=(s[i]+k)-'z'+'A'-1;
        else if ('A'<=s[i] && s[i]<='z')
            s[i]+=k;
    }
    char pre;
    int st=-1;
    for(inti=0;i<n;i++){
        if(s[i]<'A'||s[i]>'z'){
            if(st==-1){
                st=i;
                pre=s[i];
            } else {
                char tmp=s[i];
                s[i]=pre;
                pre=tmp;
            }
        }
    }
    if(st!=-1)
        s[st]=pre;
    cout<<s<<endl;
    return 0;
}

27. 删除30、31行输出不变。 {{ select(27) }}

• √
• ×

28. 输入无大写字母，输出与k无关。 {{ select(28) }}

• √
• ×

29. 给定输出可唯一反推输入。 {{ select(29) }}

• √
• ×

30. k固定，不存在两组不同输入输出相同。 {{ select(30) }}

• √
• ×

31. 输入6KU96APY5，输出。 {{ select(31) }}

• QB96GWE5
• QA59GVE6
• PA59GWF6
• PB96GWE5

32. 输出ab1287F2Tguz，输入可能。 {{ select(32) }}

• 0 ab1287F2Tguz
• 3 b1287BgTuza
• 16 b12872PgDuza
• 13 b12872MgAuza

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

完善程序1 拓扑排序排课

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=105;
int a[N][N];
int in[N],s[N];
int n,m,u,v;
void Topo(){
    queue<int>q;
    int cnt=0;
    for(inti=1;i<=n;i++)
        if(①)
            q.push(i);
    while (!q.empty()){
        int cur=q.front();
        q.pop();
        s[cnt++]=②;
        for(inti=1;i<=n;i++){
            if(③){
                ④;
                if(in[i]==0)
                    q.push(i);
            }
        }
    }
}
int main(){
    memset(in,0,sizeof(in));
    memset (a,0, sizeof(a));
    cin>>n>>m;
    for(inti=0;i<m;i++){
        cin>>u>>v;
        in[v]++;
        ⑤;
    }
    Topo();
    for(inti=0;i<n;i++){
        if(i) cout<<' ';
        cout<<s[i];
    }
    cout<<endl;
    return 0;
}

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

• in[i]==0
• in[i]==1
• a[1][u]==0
• a[1][u]==1

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

• q.front()
• cur
• q.back()
• s[cur]

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

• !--in[i]
• a[u][v]==1
• a[cur][i]==1
• !in[i]

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

• in[i]++
• in[i]--
• q.pop()
• q.push(cur)

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

• in[u]++
• in[u]--
• a[u][v]=1
• a[v][u]=1

完善程序2 八皇后回溯

#include<iostream>
#include<cmath>
using namespace std;
bool Place(int k,int i,int*x){
    for(intj=0;j<k;j++)
        if((x[j]==i)||①)
            return false;
    return true;
}
void NQueens(int k,int n,int*x){
    for(inti=0;i<n;i++){
        if (Place (k,i,x)){
            ②;
            if(③){
                for (int j=0;j<n;j++) cout<<x[j]<<" ";
                cout<<endl;
            }
            else {
                ④;
            }
        }
    }
}
int main(){
    int x[8];
    for(inti=0;i<8;i++)x[i]=-1;
    ⑤;
    return 0;
}

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

• x[j]==i-1
• abs(x[j]-i)<=1
• abs(x[j]-k)==i-j
• abs(x[j]-i)==k-j

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

• x[i]=k
• x[k]=n-i
• x[k]=i
• x[i]=x[k]

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

• k>n-1
• k>=n-1
• k==n
• k>n

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

• NQueens(k, n-1, x)
• NQueens(k+1, n, x)
• NQueens(k+1, n-1, x)
• cout<<x[k]<<""

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

• NQueens(1, 8,x)
• NQueens(0, 7, x+1)
• NQueens(0, 8,x)
• NQueens(1, 8,x+1)