#120. YCSP 2022 一轮模拟(初赛S组)

YCSP 2022 一轮模拟(初赛S组)

一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

  1. 对一个满二叉树,mm个树叶,KK个分枝结点,nn个结点,则: {{ select(1) }}
  • n=K+m
  • K+m=2n
  • m=K-1
  • n=2K-1
  1. 先序序列和中序序列相同的二叉树为空树或( ) {{ select(2) }}
  • 任一结点均无右孩子的非空二叉树
  • 仅有两个结点的二叉树
  • 任一结点均无左孩子的非空二叉树
  • 不存在这样的二叉树
  1. 已知A=343A=343,则A123A234HA∧123∨A∧234H的结果是( ) {{ select(3) }}
  • 20H
  • 20
  • 88
  • 57H
  1. 平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成( )个不同四边形 {{ select(4) }}
  • 2250
  • 1280
  • 2400
  • 3150
  1. 当通过分治法解决输入大小为 NN 的问题时,如果在每个阶段将问题分为大小相等 N/3N/388 个子问题,并且完成其中一个步骤需要 O(N2logN)O(N^2 logN),则总时间复杂度为()。 {{ select(5) }}
  • O(N2logN)O(N^2 logN)
  • O(N2log2N)O(N^2 〖log〗^2 N)
  • O(N3logN)O(N^3 logN)
  • O(N(log8/log3))O(N^(log8/log3))
  1. 在双向循环链表中,在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;
  1. 若一棵二叉树具有nn个度为22的结点,则度为00的结点的个数是( ) {{ select(7) }}
  • 2*n
  • n-1
  • 2*(n-1)
  • 不能确定
  1. 某二叉树结点的中序序列为EDFBGAC,后序序列为EFDGBCA,则其根节点左子树中结点数目为( ) {{ select(8) }}
  • 3
  • 2
  • 4
  • 5
  1. 1010条折线能够将平面最多分割成( )块 {{ select(9) }}
  • 121
  • 191
  • 138
  • 214
  1. 下列说法不正确的是()。 {{ select(10) }}
  • GG是一个nn阶无向简单图,nn是大于等于22的奇数,则图GG与它的补图中的奇数度结点个数相等。
  • 若无向图GG中只有两个奇数度的结点,则这两个结点一定是连通的。
  • 连通图GGkk个奇数度的结点,则图GG至少要添加kk条边才能使其成为欧拉图
  • GG具有nn个结点的简单图,如果GG中每一对结点度数之和大于等于n1n-1,则在GG中存在一条汉密尔顿路
  1. 如图,一个地区分为 55 个行政区域,现给地图着色,要求相邻区域不得使用同一颜色, 现有 44 种颜色可供选择,则不同的着色方法共有()种。 {{ select(11) }}
  • 48
  • 24
  • 72
  • 96
  1. 使用线段树和ST表对区间最大值问题(RMQ)进行求解时,对于每一个查询,线段树的时间复杂度为( ),ST表的时间复杂度为( )。 {{ select(12) }}
  • O(1)O(1)O(logN)O(logN)
  • O(logN)O(logN)O(1)O(1)
  • O(logN)O(logN)O(logN)O(logN)
  • O(logN)O(logN)O(N)O(N)
  1. 一组记录的关键字为(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)
  1. 下列关于排序的算法,不正确的是()。 {{ select(14) }}
  • 不存在这样一个基于排序码比较的算法:它只通过不超过9次排序码的比较,就可以对任何6个排序码互异的数据对象实现排序。
  • 如果输入序列已经排好序,则快速排序算法仍然需移动任何数据对象才可以完成排序。
  • 希尔排序的最后一趟就是选择排序。
  • 任何基于排序码比较的算法,对n个数据对象进行排序时,最坏情况下的时间复杂度不会低于O(nlogn)O(nlogn)
  1. 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.	}  

判断题

  1. cmp函数是为了改变sort函数的排序方式
    {{ select(16) }}
  • 正确
  • 错误
  1. 将23至26行改成 cout<<s[i],对结果没有影响
    {{ select(17) }}
  • 正确
  • 错误
  1. 将20行改成 sort(s, s+n, cmp),对结果没有影响
    {{ select(18) }}
  • 正确
  • 错误
  1. 该程序的输出总长度会比输入的所有字符串长度要短
    {{ select(19) }}
  • 正确
  • 错误

选择题

  1. 如果输入为3 13 312 343,则输出为( ) {{ select(20) }}
  • 34331213
  • 343331213
  • 13312343
  • 11233334
  1. 如果输入为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.	}  

判断题

  1. 该题是为了统计整数n分成k份非空子集的方案数 {{ select(22) }}
  • 正确
  • 错误
  1. 如果将14行的i=last改成i=1,则答案会增加 {{ select(23) }}
  • 正确
  • 错误
  1. 该题可以使用动态规划的方法来做,如果使用dp[i][j]表示整数i分成j份的方案数,则状态转移方程为dp[i][j]=dp[i-1][j-1]+dp[i-j][j]+1
    {{ select(24) }}
  • 正确
  • 错误
  1. 若k=2,则输出的值为⌊(n-1)/2⌋
    {{ select(25) }}
  • 正确
  • 错误

选择题

  1. 如果输入为7 3,则结果为( ) {{ select(26) }}
  • 5
  • 7
  • 4
  • 8
  1. 如果输入为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.	}  

判断题

  1. 如果x会进入优先队列,那么4*x+5一定在之后会被弹出优先队列
    {{ select(28) }}
  • 正确
  • 错误
  1. 对于每一个输入的l,存在一个x,使得当m>x时,第39行的输出全部为9或者没有输出
    {{ select(29) }}
  • 正确
  • 错误

选择题

  1. 若在第29行输出为137915,并且m为4,则输出为( ) {{ select(30) }}
  • 11
  • 37
  • 91
  • 95
  1. 若输入为8 10,则第29行输出为( ) {{ select(31) }}
  • 137915171931
  • 13579111315
  • 1371321314357
  • 12345678
  1. 如果输入13 17,则第39行输出为( ) {{ select(32) }}
  • 99999
  • 99963
  • 11113
  • 94163
  1. 如果输入为14,则当m为( )时,第39行输出的字典序最大。 {{ select(33) }}
  • 14
  • 18
  • 20
  • 21

三、完善程序(每小题3分,共计30分)

1)

给定一棵 nn 个点的带权树,结点下标从 11 开始到 nn。寻找树中找两个结点,求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。该问题的解决步骤如下: 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.	}  
  1. ①处应填( ) {{ select(34) }}
  • 2147483647
  • 1<<31-1
  • 2147483648
  • 1<<31
  1. ②处应填( ) {{ select(35) }}
  • !x&i
  • x^i
  • x&i
  • ~(x&i)
  1. ③处应填( ) {{ select(36) }}
  • trie[rt][c]
  • trie[rt][c^1]
  • !trie[rt][c]
  • !trie[rt][c^1]
  1. ④处应填( ) {{ 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;
  1. ⑤处应填( ) {{ select(38) }}
  • 0
  • -1
  • 0x3f
  • 1

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

输入格式

第一行:nn ,保证 2n2000002≤n≤200000

接下来 nn 行:每行两个实数: xyx y ,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式

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

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.	}  
  1. ①处应填( ) {{ select(39) }}
  • -1
  • d
  • 0
  • 1
  1. ②处应填( ) {{ select(40) }}
  • -1
  • d
  • dist(left, right)
  • -1
  1. ③处应填( ) {{ select(41) }}
  • d=min(d1,d2)
  • d=d1+d2
  • d=dist(left, right)
  • d=max(d1, d2)
  1. ④处应填( ) {{ select(42) }}
  • S[mid].x - S[i].x
  • S[i].x - S[mid].x
  • fabs(S[mid].x - S[i].x)
  • dist(i, j)
  1. ⑤处应填( ) {{ 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