#5134. YCSP 2022 一轮模拟(初赛S组)
一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)
- 对一个满二叉树,个树叶,个分枝结点,个结点,则:
- 先序序列和中序序列相同的二叉树为空树或( )
- 已知,则的结果是( )
- 平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成( )个不同四边形
- 当通过分治法解决输入大小为 的问题时,如果在每个阶段将问题分为大小相等 的 个子问题,并且完成其中一个步骤需要 ,则总时间复杂度为()。
- 在双向循环链表中,在p指针所指的结点后插入q所指向的新结点,其修改指针的操作是( )
- 若一棵二叉树具有个度为的结点,则度为的结点的个数是( )
- 某二叉树结点的中序序列为EDFBGAC,后序序列为EFDGBCA,则其根节点左子树中结点数目为( )
- 条折线能够将平面最多分割成( )块
- 下列说法不正确的是()。
- 如图,一个地区分为 个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,
现有 种颜色可供选择,则不同的着色方法共有()种。
- 使用线段树和ST表对区间最大值问题(RMQ)进行求解时,对于每一个查询,线段树的时间复杂度为( ),ST表的时间复杂度为( )。
- 一组记录的关键字为(25,50,15,35,80,85,20,40,36,70,28,90),其中含有6个长度为2的有序表,用归并排序方法对该序列进行两趟归并后的结果为( )。
- 下列关于排序的算法,不正确的是()。
- 10000以内,与10000互质的正整数有( )个
二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填 T,错误填F;除特殊说明外,判断题1.5分,选择题4分,共计40分)
1)
判断题
- cmp函数是为了改变sort函数的排序方式
- 将23至26行改成 cout<<s[i],对结果没有影响
- 将20行改成 sort(s, s+n, cmp),对结果没有影响
- 该程序的输出总长度会比输入的所有字符串长度要短
选择题
- 如果输入为3 13 312 343,则输出为( )
- 如果输入为100 1 2 3 …(递增直到100),则输出的前十位为( )
2)
判断题
- 该题是为了统计整数n分成k份非空子集的方案数
- 如果将14行的i=last改成i=1,则答案会增加
- 该题可以使用动态规划的方法来做,如果使用dp[i][j]表示整数i分成j份的方案数,则状态转移方程为dp[i][j]=dp[i-1][j-1]+dp[i-j][j]+1
- 若k=2,则输出的值为⌊(n-1)/2⌋
选择题
- 如果输入为7 3,则结果为( )
- 如果输入为12 5,则结果为( )
3)
判断题
- 如果x会进入优先队列,那么4*x+5一定在之后会被弹出优先队列
- 对于每一个输入的l,存在一个x,使得当m>x时,第39行的输出全部为9或者没有输出
选择题
- 若在第29行输出为137915,并且m为4,则输出为( )
- 若输入为8 10,则第29行输出为( )
- 如果输入13 17,则第39行输出为( )
- 如果输入为14,则当m为( )时,第39行输出的字典序最大。
三、完善程序(每小题3分,共计30分)
1)
给定一棵 个点的带权树,结点下标从 开始到 。寻找树中找两个结点,求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。该问题的解决步骤如下: 1、 建图之后dfs求出每个节点到根节点的异或值
2、 构建01Trie树
3、 贪心获得最大异或值
- ①处应填( )
- ②处应填( )
- ③处应填( )
- ④处应填( )
- ⑤处应填( )
2) 给定平面上 个点,找出其中的一对点的距离,使得在这 个点的所有点对中,该距离为所有点对中最小的。
输入格式
第一行: ,保证 。
接下来 行:每行两个实数: ,表示一个点的行坐标和列坐标,中间用一个空格隔开。
输出格式
仅一行,一个实数,表示最短距离,精确到小数点后面 位。
- ①处应填( )
- ②处应填( )
- ③处应填( )
- ④处应填( )
- ⑤处应填( )