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

1. 对一个满二叉树，$m$个树叶，$K$个分枝结点，$n$个结点，则： {{ select(1) }}

• n=K+m
• K+m=2n
• m=K-1
• n=2K-1

2. 先序序列和中序序列相同的二叉树为空树或( ) {{ select(2) }}

• 任一结点均无右孩子的非空二叉树
• 仅有两个结点的二叉树
• 任一结点均无左孩子的非空二叉树
• 不存在这样的二叉树

3. 已知$A=343$,则$A∧123∨A∧234H$的结果是( ) {{ select(3) }}

• 20H
• 20
• 88
• 57H

4. 平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成（ ）个不同四边形 {{ select(4) }}

• 2250
• 1280
• 2400
• 3150

5. 当通过分治法解决输入大小为 $N$ 的问题时，如果在每个阶段将问题分为大小相等 $N/3$ 的 $8$ 个子问题，并且完成其中一个步骤需要 $O(N^2 logN)$，则总时间复杂度为（）。 {{ select(5) }}

• $O(N^2 logN)$
• $O(N^2 〖log〗^2 N)$
• $O(N^3 logN)$
• $O(N^(log8/log3))$

6. 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ） {{ select(6) }}

• p->next=q; q->prior=p; p->next->prior=q; q->next=q;
• p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
• q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
• q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

7. 若一棵二叉树具有$n$个度为$2$的结点，则度为$0$的结点的个数是( ) {{ select(7) }}

• 2*n
• n-1
• 2*(n-1)
• 不能确定

8. 某二叉树结点的中序序列为EDFBGAC，后序序列为EFDGBCA，则其根节点左子树中结点数目为( ) {{ select(8) }}

• 3
• 2
• 4
• 5

9. $10$条折线能够将平面最多分割成（ ）块 {{ select(9) }}

• 121
• 191
• 138
• 214

10. 下列说法不正确的是（）。 {{ select(10) }}

• 设$G$是一个$n$阶无向简单图，$n$是大于等于$2$的奇数，则图$G$与它的补图中的奇数度结点个数相等。
• 若无向图$G$中只有两个奇数度的结点，则这两个结点一定是连通的。
• 连通图$G$有$k$个奇数度的结点，则图$G$至少要添加$k$条边才能使其成为欧拉图
• 设$G$具有$n$个结点的简单图，如果$G$中每一对结点度数之和大于等于$n-1$，则在$G$中存在一条汉密尔顿路

11. 如图，一个地区分为 $5$ 个行政区域，现给地图着色，要求相邻区域不得使用同一颜色， 现有 $4$ 种颜色可供选择，则不同的着色方法共有（）种。 {{ select(11) }}

• 48
• 24
• 72
• 96

12. 使用线段树和ST表对区间最大值问题（RMQ）进行求解时，对于每一个查询，线段树的时间复杂度为（ ），ST表的时间复杂度为（ ）。 {{ select(12) }}

• $O(1)$，$O(logN)$
• $O(logN)$，$O(1)$
• $O(logN)$，$O(logN)$
• $O(logN)$，$O(N)$

13. 一组记录的关键字为（25，50，15，35，80，85，20，40，36，70，28，90），其中含有6个长度为2的有序表，用归并排序方法对该序列进行两趟归并后的结果为（　 ）。 {{ select(13) }}

• （15，25，35，50，20，40，80，85，28，36，70，90）
• （15，25，35，50，80，20，85，40，70，36，28，90）
• （15，25，35，50，80，85，20，28，36，40，70，90）
• （15，20，25，35，40，50，80，85，28，36，70，90）

14. 下列关于排序的算法，不正确的是（）。 {{ select(14) }}

• 不存在这样一个基于排序码比较的算法：它只通过不超过9次排序码的比较，就可以对任何6个排序码互异的数据对象实现排序。
• 如果输入序列已经排好序，则快速排序算法仍然需移动任何数据对象才可以完成排序。
• 希尔排序的最后一趟就是选择排序。
• 任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度不会低于$O(nlogn)$。

15. 10000以内，与10000互质的正整数有（ ）个 {{ select(15) }}

• 1000
• 2000
• 3000
• 4000

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 T，错误填F；除特殊说明外，判断题1.5分，选择题4分，共计40分）

1）

1.	#include<bits/stdc++.h>  
2.	using namespace std;  
3.	  
4.	bool cmp(string a,string b)  
5.	{  
6.	    string ab,ba;  
7.	    ab=a+b;  
8.	    ba=b+a;  
9.	    return ab>ba;  
10.	}  
11.	int main()  
12.	{  
13.	    string s[105];  
14.	    int n;  
15.	    cin>>n;  
16.	    for(int i=1;i<=n;i++)  
17.	    {  
18.	        cin>>s[i];  
19.	    }  
20.	    sort(s+1,s+1+n,cmp);  
21.	    for(int i=1;i<=n;i++)  
22.	    {  
23.	        for(int j=0;j<s[i].length();j++)  
24.	        {  
25.	            cout<<s[i][j];  
26.	        }  
27.	    }  
28.	}  

判断题

16. cmp函数是为了改变sort函数的排序方式
    {{ select(16) }}

• 正确
• 错误

17. 将23至26行改成 cout<<s[i]，对结果没有影响
    {{ select(17) }}

• 正确
• 错误

18. 将20行改成 sort(s, s+n, cmp)，对结果没有影响
    {{ select(18) }}

• 正确
• 错误

19. 该程序的输出总长度会比输入的所有字符串长度要短
    {{ select(19) }}

• 正确
• 错误

选择题

20. 如果输入为3 13 312 343，则输出为（ ） {{ select(20) }}

• 34331213
• 343331213
• 13312343
• 11233334

21. 如果输入为100 1 2 3 …(递增直到100)，则输出的前十位为（ ） {{ select(21) }}

• 9999999999
• 0000000000
• 9998979695
• 9999897969

2）

1.	#include <bits/stdc++.h>  
2.	using namespace std;  
3.	  
4.	int tot=0;  
5.	int n,k;  
6.	void dfs(int last,int cnt,int ans)  
7.	{  
8.	    if(cnt==1)  
9.	    {  
10.	        tot++;  
11.	    }  
12.	    else   
13.	    {  
14.	        for(int i=last;i<=ans/cnt;i++)  
15.	        {  
16.	            dfs(i,cnt-1,ans-i);  
17.	        }  
18.	    }  
19.	}  
20.	  
21.	int main()  
22.	{  
23.	    scanf("%d%d",&n,&k);  
24.	    dfs(1,k,n);  
25.	    printf("%d\n",tot);  
26.	}  

判断题

22. 该题是为了统计整数n分成k份非空子集的方案数 {{ select(22) }}

• 正确
• 错误

23. 如果将14行的i=last改成i=1，则答案会增加 {{ select(23) }}

• 正确
• 错误

24. 该题可以使用动态规划的方法来做，如果使用dp[i][j]表示整数i分成j份的方案数，则状态转移方程为dp[i][j]=dp[i-1][j-1]+dp[i-j][j]+1
    {{ select(24) }}

• 正确
• 错误

25. 若k=2，则输出的值为⌊(n-1)/2⌋
    {{ select(25) }}

• 正确
• 错误

选择题

26. 如果输入为7 3，则结果为（ ） {{ select(26) }}

• 5
• 7
• 4
• 8

27. 如果输入为12 5，则结果为（ ） {{ select(27) }}

• 12
• 15
• 13
• 16

3）

1.	#include<iostream>  
2.	#include<cstdio>  
3.	#include<cstring>  
4.	#include<queue>  
5.	using namespace std;  
6.	priority_queue<int,vector<int>,greater<int> > q;  
7.	int a[30005],ans[5000010],topa,topans,next[5000010];  
8.	int main() {  
9.	    int l,m;  
10.	    cin>>l>>m;  
11.	    memset(ans,0x3f,sizeof(ans));  
12.	    q.push(1);  
13.	    while(1) {  
14.	        int x=q.top(),d=0;  
15.	        q.pop();  
16.	        q.push(2*x+1);  
17.	        q.push(4*x+5);  
18.	        a[++topa]=x;  
19.	        while(x) {  
20.	            d=d*10+x%10;  
21.	            x/=10;  
22.	        }  
23.	        while(d) {  
24.	            ans[++topans]=d%10;  
25.	            d/=10;  
26.	        }  
27.	        if(topa>=l) break;  
28.	    }  
29.	    for(int i=1; i<=topa; i++) cout<<a[i];  
30.	    cout<<endl;  
31.	    for(int i=0; i<topans; i++) next[i]=i+1;  
32.	    while(m) {  
33.	        int l=0;  
34.	        while(ans[next[l]]>=ans[next[next[l]]])  
35.	            l=next[l];  
36.	        next[l]=next[next[l]];  
37.	        m--;  
38.	    }  
39.	    for(int i=0; next[i]; i=next[i]) cout<<ans[next[i]];  
40.	    return 0;  
41.	}  

判断题

28. 如果x会进入优先队列，那么4*x+5一定在之后会被弹出优先队列
    {{ select(28) }}

• 正确
• 错误

29. 对于每一个输入的l，存在一个x，使得当m>x时，第39行的输出全部为9或者没有输出
    {{ select(29) }}

• 正确
• 错误

选择题

30. 若在第29行输出为137915，并且m为4，则输出为（ ） {{ select(30) }}

• 11
• 37
• 91
• 95

31. 若输入为8 10，则第29行输出为（ ） {{ select(31) }}

• 137915171931
• 13579111315
• 1371321314357
• 12345678

32. 如果输入13 17，则第39行输出为（ ） {{ select(32) }}

• 99999
• 99963
• 11113
• 94163

33. 如果输入为14，则当m为（ ）时，第39行输出的字典序最大。 {{ select(33) }}

• 14
• 18
• 20
• 21

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

1）

给定一棵 $n$ 个点的带权树，结点下标从 $1$ 开始到 $n$。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。该问题的解决步骤如下： 1、 建图之后dfs求出每个节点到根节点的异或值

2、 构建01Trie树

3、 贪心获得最大异或值

1.	#include<bits/stdc++.h>  
2.	using namespace std;  
3.	  
4.	#define maxn 100005  
5.	int trie[maxn*31][2],xo[maxn],ans,rt;  
6.	int val[maxn],n,head[maxn],tot;  
7.	  
8.	struct Edge {  
9.	    int u,v,w;  
10.	} edge[maxn<<1];  
11.	void add(int x,int y,int z) {  
12.	    edge[++tot].u=head[x];  
13.	    edge[tot].v=y;  
14.	    edge[tot].w=z;  
15.	    head[x]=tot;  
16.	    edge[++tot].u=head[y];  
17.	    edge[tot].v=x;  
18.	    edge[tot].w=z;  
19.	    head[y]=tot;  
20.	}  
21.	void build_trie(int x,int rt) {  
22.	    for(int i=①; i; i>>=1) {  
23.	        bool c=②;  
24.	        if(!trie[rt][c])trie[rt][c]=++tot;  
25.	        rt=trie[rt][c];  
26.	    }  
27.	}  
28.	int query(int x,int rt) {  
29.	    int ans=0;  
30.	    for(int i=1<<30; i; i>>=1) {  
31.	        bool c=x&i;  
32.	        if(③)ans+=i,rt=trie[rt][c^1];  
33.	        else rt=trie[rt][c];  
34.	    }  
35.	    return ans;  
36.	}  
37.	void dfs(int u,int fa) {  
38.	    for(int i=head[u]; ~i; i=edge[i].u) {  
39.	        if(edge[i].v!=fa) {  
40.	            ④  
41.	            dfs(edge[i].v,u);  
42.	        }  
43.	    }  
44.	}  
45.	int main() {  
46.	  memset(head, ⑤, sizeof(head));
47.	    scanf("%d", &n);  
48.	    for(int i=1,u,v,w; i<n; i++) {  
49.	        scanf("%d%d%d", &u, &v, &w);  
50.	        add(u, v, w);  
51.	    }  
52.	    dfs(1,0);  
53.	    for(int i=1; i<=n; i++)build_trie(xo[i],rt);  
54.	    for(int i=1; i<=n; i++)ans=max(ans,query(xo[i],rt));  
55.	    printf("%d",ans);  
56.	}  

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

• 2147483647
• 1<<31-1
• 2147483648
• 1<<31

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

• !x&i
• x^i
• x&i
• ~(x&i)

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

• trie[rt][c]
• trie[rt][c^1]
• !trie[rt][c]
• !trie[rt][c^1]

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

• xo[edge[i].v]=xo[u]^edge[i].w;
• xo[u]=xo[edge[i].v]^edge[i].w;
• xo[edge[i].w]=xo[u]^edge[i].v;
• xo[u]=xo[edge[i].w]^edge[i].v;

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

• 0
• -1
• 0x3f
• 1

2） 给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的。

输入格式

第一行：$n$ ，保证 $2≤n≤200000$ 。

接下来 $n$ 行：每行两个实数： $x y$ ，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式

仅一行，一个实数，表示最短距离，精确到小数点后面 $4$ 位。

1.	#include <cstdio>  
2.	#include <algorithm>  
3.	#include <cmath>  
4.	using namespace std;  
5.	const int maxn = 1000001;  
6.	const int INF = 2 << 20;  
7.	int n, temp[maxn];  
8.	struct Point   
9.	{  
10.	    double x, y;  
11.	} S[maxn];  
12.	bool cmp(const Point &a, const Point &b)   
13.	{  
14.	    if(a.x == b.x) return a.y < b.y;  
15.	    else return a.x < b.x;  
16.	}  
17.	bool cmps(const int &a, const int &b) { return S[a].y < S[b].y; }  
18.	double min(double a, double b) { return a < b ? a : b; }  
19.	double dist(int i, int j)   
20.	{  
21.	    double x = (S[i].x - S[j].x) * (S[i].x - S[j].x);  
22.	    double y = (S[i].y - S[j].y) * (S[i].y - S[j].y);  
23.	    return sqrt(x + y);  
24.	}  
25.	double merge(int left, int right)   
26.	{  
27.	    double d = INF;  
28.	    if(left == right) return ①;  
29.	    if(left + 1 == right) return ②;  
30.	    int mid = left + right >> 1;  
31.	    double d1 = merge(left, mid);  
32.	    double d2 = merge(mid + 1, right);  
33.	    ③  
34.	    int i, j, k = 0;  
35.	    for(i = left; i <= right; i++)  
36.	        if(④ < d)   
37.	            temp[k++] = i;  
38.	    sort(temp, temp + k, cmps);  
39.	    for(i = 0; i < k; i++)  
40.	        for(j = i + 1; j < k && ⑤ < d; j++)   
41.	        {  
42.	            double d3 = dist(temp[i], temp[j]);  
43.	            if(d > d3) d = d3;  
44.	        }  
45.	    return d;  
46.	}  
47.	int main()   
48.	{  
49.	    scanf("%d", &n);  
50.	    for(int i = 0; i < n; i++) scanf("%lf%lf", &S[i].x, &S[i].y);  
51.	    sort(S, S + n, cmp);  
52.	    printf("%.4lf\n", merge(0, n - 1));  
53.	  return 0;
54.	}  

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

• -1
• d
• 0
• 1

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

• -1
• d
• dist(left, right)
• -1

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

• d=min(d1,d2)
• d=d1+d2
• d=dist(left, right)
• d=max(d1, d2)

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

• S[mid].x - S[i].x
• S[i].x - S[mid].x
• fabs(S[mid].x - S[i].x)
• dist(i, j)

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

• S[temp[j]].y - S[temp[i]].y
• S[j].y - S[i].y
• S[temp[i]].y - S[temp[j]].y
• S[i].y - S[j].y