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

1. 在以下各项中，不是CPU的组成部分。 {{ select(1) }}

• 控制器
• 运算器
• 寄存器
• 主板

2. $(2017)_8+(1234)_{10}$ 的结果是。 {{ select(2) }}

• $(8E2)_{16}$
• $(100011100001)_2$
• $(8E0)_{16}$
• $(100011100011)_2$

3. 设 $A=B=\text{True}$，$C=D=\text{False}$，逻辑运算表达式值为假的是。 {{ select(3) }}

• $(A \land B)\lor(C \land D \lor A)$
• $\neg(((A \land B) \lor C) \land D)$
• $A \land (B \lor C \lor D) \lor D$
• $(A \land (D \lor C)) \land B$

4. 若已知一个栈的入栈序列是1,2,3,…,n，输出序列为$p_1,p_2,…,p_n$，若$p_1=n$，则$p_i$为。 {{ select(4) }}

• $i$
• $n-i$
• $n-i+1$
• 不确定

5. 设S="abbcce"，不同的非空子串个数有个。 {{ select(5) }}

• 19
• 17
• 16
• 18

6. C++中，12^5的值是。 {{ select(6) }}

• 127
• 128
• 15625
• 126

7. 算法递推$T(n)=2T(n/2)+n,\ T(1)=1$，时间复杂度为。 {{ select(7) }}

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

8. 下列有关二叉树的叙述，不正确的是。 {{ select(8) }}

• 二叉树深度为k，则最多$2^k-1$个节点$(k\ge1)$
• 二叉树第i层最多$2^{i-1}$个节点$(i\ge1)$
• 完全二叉树一定是满二叉树
• 堆是完全二叉树

9. 平均时间复杂度$O(n^2)$的排序是。 {{ select(9) }}

• 快速排序
• 插入排序
• 归并排序
• 堆排序

10. 下列图一定可黑白染色（相邻不同色）。 {{ select(10) }}

• 树
• 基环树
• 连通图
• 欧拉图

11. 下列不是操作系统的有。 {{ select(11) }}

• Linux
• Windows
• Android
• WPS

12. 下列关于算法叙述错误的是。 {{ select(12) }}

• 算法代表系统解决问题的策略机制
• 评判算法好坏只看时间复杂度
• 算法具备有穷性、可行性、输入输出
• NP完全问题暂无高效多项式算法

13. 下列叙述正确的是。 {{ select(13) }}

• 线性表是线性结构
• 栈与队列是非线性结构
• 线性链表是非线性结构
• 二叉树是线性结构

14. 链表哪种操作需要$O(n)$时间。 {{ select(14) }}

• 插入
• 定位
• 删除
• 合并

15. NOI考场可以带入的物品。 {{ select(15) }}

• 键盘
• 参考书籍
• U盘
• 铅笔

二、阅读程序（判断√/×每题1.5分，选择每题4分，共40分）

阅读程序1

#include<iostream>
using namespace std;
int n,k,ans;
int main()
{
    cin>>n>>k;
    int ans=0;
    while(n)
    {
        if(n%k>0)ans++;
        n/=k;
    }
    cout<<ans<<endl;
    return 0;
}

16. 第10行n%k>0改为n%k不影响运行结果。 {{ select(16) }}

• √
• ×

17. 输入k需要大于1。 {{ select(17) }}

• √
• ×

18. 输入n需要大于0。 {{ select(18) }}

• √
• ×

19. 算法时间复杂度$O(\log_k n)$。 {{ select(19) }}

• √
• ×

20. 输入125 5输出结果为。 {{ select(20) }}

• 1
• 2
• 3
• 4

21. n在int范围内，输出最大值为。 {{ select(21) }}

• 29
• 30
• 31
• 32

阅读程序2

#include<iostream>
using namespace std;
int equationCount(int n,int m)
{
    if(n==1||m==1)
        return 1;
    else if(n<m)
        return equationCount (n,n);
    else if(n==m)
        return 1+equationCount (n,n-1);
    else
        return equationCount (n,m-1) +equationCount (n-m,m);
}
int main()
{
    int n;
    cin>>n;
    cout<<equationCount (n,n)<<endl;
    return 0;
}

22. 输入n必须为正整数。 {{ select(22) }}

• √
• ×

23. 删除else if(n==m)分支不影响结果。 {{ select(23) }}

• √
• ×

24. equationCount(n,n)改为equationCount(n,n+1)无影响。 {{ select(24) }}

• √
• ×

25. 删除else if(n<m)分支不影响结果。 {{ select(25) }}

• √
• ×

26. 输入7输出为。 {{ select(26) }}

• 12
• 13
• 14
• 15

27. 该算法时间复杂度。 {{ select(27) }}

• $O(\log n)$
• $O(n)$
• $O(n^2)$
• 以上都不是

阅读程序3（最长上升子序列LIS）

#include<iostream>
using namespace std;
const int maxn=100000;
int a[maxn], b[maxn],n;
int Search (int num, int low, int high)
{
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(num>=b[mid]) low=mid+1;
        else high=mid-1;
    }
    return low;
}
int main()
{
    int len,pos;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    b[1]=a[1];
    len=1;
    for(int i=2;i<=n;i++)
    {
        if (a[i]>=b[len])
        {
            len++;
            b[len]=a[i];
        }
        else
        {
            pos =Search (a[i],1, len);
            b[pos]=a[i];
        }
    }
    cout<<len<<endl;
    return 0;
}

28. 输入a[i]必须在[1,n]。 {{ select(28) }}

• √
• ×

29. Search内low=mid+1改为low=mid不影响结果。 {{ select(29) }}

• √
• ×

30. a单调不降时输出为1。 {{ select(30) }}

• √
• ×

31. 数组b始终单调不降。 {{ select(31) }}

• √
• ×

32. 输入20，序列1 20 2 19 3 18 4 17 … 9 12 10 11，输出。 {{ select(32) }}

• 1
• 10
• 11
• 20

33. 算法时间复杂度。 {{ select(33) }}

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

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

完善程序1 DLX精确覆盖

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000
#define N 2005
#define M 2000005
int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&& ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m;
int h[N],s[N],q[N];
int u[M],d[M],L[M],R[M],C[M],x[M];
void del(int c)//delete ROW C
{
    ①;
    for(int i=d[c];i!=c;i=d[i])
        for(intj=R[i];j!=i;j=R[j])
        {
            u[j]=u[j],d[u[j]]=d[j],s[c[j]]--;
        }
}
void add (int c)
{
    L[R[c]]=R[L[c]]=c;
    for(int i=u[c];i!=c;i=u[i])
        for(int j=L[i];j!=i;j=L[j])
        {
            u[d[j]]=d[u[j]]=j,s[c[j]]++;
        }
}
void link(int r,int c)
{
    static int size=0;size++;
    x[size]=r;C[size]=c;
    s[c]++;
    d[size]=d[c];
    u[size]=c;u[d[size]]=size;
    d[u[size]]=size;
    if(h[r]==-1)
        h[r]=L[size]=R[size]=size;
    else
    {
        R[size]=R[h[r]];
        L[size]=h[r];
        L[R[size]]=size;
        R[L[size]]=size;
    }
}
bool dance (int k)
{
    if(R[0]==0)
    {
        printf("%d",k);
        for(int i=1;i<=k;i++)
            printf(" %d",x[q[i]]);
        puts("");
        return 1;
    }
    int mn=inf,c;
    for(int i=R[0];i;i=R[i])
        if(s[i]<mn)mn=s[i],c=i;
    ②;
    for(int i=d[c];i!=c;i=d[i])
    {
        q[k+1]=i;
        for(intj=R[i];j!=i;j=R[j])
            ③;
        if (dance (k+1)) return 1;
        for(intj=L[i];j!=i;j=L[j])
            ④;
        ⑤;
    }
    add (c);
    return 0;
}
int main()
{
    while (scanf("%d%d", &n,&m)!=EOF)
    {
        for(inti=0;i<=m;i++)
        {
            d[i]=u[i]=i;
            L[i+1]=i;R[i]=i+1;
            s[i]=0;
        }
        R[m]=0;
        int size=m;
        int x,y;
        for(inti=1;i<=n;i++)
        {
            h[i]=-1;
            x=read();
            while(x--)
            {
                y=read();
                link(i,y);
            }
        }
        if(!dance (0))puts ("NO");
    }
    return 0;
}

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

• L[L[c]]=R[c];
• L[R[c]]=L[c];
• R[L[c]]=R[c];
• R[R[c]]=L[c];

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

• del(c);
• add(c);
• del(mn);
• add(mn);

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

• add(j);
• del(j);
• add(C[j]);
• del(C[j]);

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

• add(j);
• del(j);
• add(C[j]);
• del(C[j]);

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

• add(j);
• del(j);
• add(C[j]);
• del(C[j]);

完善程序2 两次BFS求树直径

#include<iostream>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1005;
struct Node{
    int to,w,next;
}edge[maxn*2];
int head[maxn],tot;
int n;
int dis[maxn];
bool vis[maxn];
int que[maxn],first,last;
void init()
{
    memset (head, -1, sizeof (head));
    tot=0;
}
void addedge(int u,int v,int w)
{
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].next =head[u];
    head[u]=tot++;
}
int BFS(int u)
{
    first=last=0;
    memset (dis, inf,sizeof (dis));
    memset (vis,0,sizeof(vis));
    dis[u]=0; vis[u]=1;
    que[last++]=u;
    while(①)
    {
        u=que[first++];
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(②)
            {
                vis[v]=1;
                que[last++]=v;
                ③;
            }
        }
    }
    int tmp=1;
    for(int i=2;i<=n;i++)
        if(④)tmp=i;
    return tmp;
}
int main()
{
    int u,v,w,s,t;
    cin>>n; init();
    for(int i=1;i<n;i++)
    {
        cin>>u>>v>>w;
        addedge (u,v,w);
        addedge (v,u,w);
    }
    s=BFS(1);
    ⑤;
    cout<<dis[t]<<endl;
    return 0;
}

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

• first<last
• first<=last
• first<last-1
• last==n

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

• !vis[v]
• vis[v]
• vis[u]
• dis[v]

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

• dis[v]=dis[u]+1
• dis[v]=dis[u]+edge[i].w
• dis[u]=dis[v]+1
• dis[u]=dis[v]+edge[i].w

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

• dis[i]<dis[tmp]
• dis[i]<tmp
• dis[i]>dis[tmp]
• dis[i]==tmp

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

• t=BFS(s)
• t=BFS(1)
• t=BFS(t)
• s=BFS(t)