下面关于C++类和对象的说法,错误的是( )。
查看答案与解析
在C++中,struct默认的访问权限是public,而class的默认访问权限是private。如果你想改变这一默认行为,可以在struct中显式地声明成员为private。
下面关于C++类和对象的说法,错误的是( )。
在C++中,struct默认的访问权限是public,而class的默认访问权限是private。如果你想改变这一默认行为,可以在struct中显式地声明成员为private。
在一个单位圆上,随机分布 n 个点,求这 n 个点能被一个单位半圆周全部覆盖的概率( )。
对于一个具有 n 个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为( )。
n个顶点对的无向图,需要n行n列的矩阵(对称),可以用数组下标0~n-1对应,选B。
设有编号为A、B、C、D、E的5个球和编号为A、B、C、D、E的5个盒子。现将这5个球投入5个盒子,要求每个盒子放一个球,并且恰好有两个球的编号与盒子编号相同,问有多少种不同的方法?( )。
先从5个球中选择2个球放到对应的盒子中,有种,剩余的3个球不能和盒子编号相同,因此第3个球有2种盒子可以选择,第4个球和第5个球只有1种选择。
共10*2=20种,选C。
从甲地到乙地,可以乘高铁,也可以乘汽车,还可以乘轮船。一天中,高铁有10班,汽车有5班,轮船有2班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法?( )。
由加法原理,ans=10+5+2=17种。
n个结点的二叉树,执行释放全部结点操作的时间复杂度是( )。
对二叉树执行DFS,在回溯阶段依次释放每个节点,复杂度O(n)。
下面 pailie 函数是一个实现排列的程序,横线处可以填入的是( )。
函数作用:在0n-1的区间,对A[0n-1]的元素进行全排列。
全排列可以这么理解,每个元素都有尝试在开头的机会,之后其他的元素在这个前提之下,继续在该元素后方继续尝试。当然在尝试完成后,还需要将排列还原,方便后续尝试,符合该要求的只有C选项。
上一题中,如果主函数为如下的程序,则最后的排列数是多少个?( )。
5的全排列5!=120。
下列程序实现了输出杨辉三角形,代码中横线部分应该填入的是( )。
下面最小生成树的Kruskal算法程序中,横线处应该填入的是( )。
Kruskal基于避圈法和贪心思想,先按照边权升序,依次考虑每条边(x,y,z),如果x和y已经处于同一个生成树中,则过滤掉当前的边,否则将x和y的生成树通过z边连接,同时用并查集维护x和y(联接x和y的集合),组成更大的生成树。
横线处为判断x和y是否处于同一个集合,不是则链接,并更新最小生成树的边权和。答案选C。
下面Prim算法程序中,横线处应该填入的是( )。
最小生成树的Prim算法思想:选择圈内的一个点x(一开始随便选一个点作为x),遍历x的所有出边y,从中选取一个边权z最小的y,该(x,y,z)一定是最小生成树的生成边(因为最小生成树的点之间相互连通),程序中key数组就是用来记录过程中每个节点距离圈的距离的最小值,parent数组是记录节点和边权依次加入圈的具体路径(最终形成一棵生成树),横线处是比较圈外距离u最小的边权v,因此答案选D。
下列Dijkstra算法中,横线处应该填入的是( )。
朴素dijkstra算法,在非负权图中,用cheak[]标记已经求得最短路的点(因为已经求得,所以后续不会再更新),每次选择距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx,由非负权图的原因,该节点minxj将加入已经求得最短路的点的集合,同时用minx尝试是否能更新S到其他待球节点的最短路。横线处就是求解距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx的,因此选B。
下面Floyd算法中,横线处应该填入的是( )。
Floyd算法本质是个DP,或者可以理解为松弛操作:
i和j的最短路如果可以通过中间节点k做更新:
则需要map[i][j]>map[i][k]+map[k][j];选B。
下面程序的 Merge_Sort 函数时间复杂度为( )。
归并排序基于分治
时间复杂度为O(nlogn)。空间复杂度O(n);
下面 fibonacci 函数的时间复杂度为( )。
表达式 ‘3’ & 1 的结果为 ‘1’ 。
ASCII码’3’为51,是奇数,&1操作是取51的最低位2进制。结果为1,而非字符’1’。
在C++语言中,变量定义必须在某一个函数定义之内。
变量可以为全局变量。
冒泡排序一般是不稳定的。
基于比较的排序中不稳定的有四个:希尔,选择,快速,堆,其余都稳定。
二叉排序树的查找操作的平均时间复杂度,正比于树的高度。
二叉排序树查找的时间复杂度为树的高度。
使用 math.h 或 cmath 头文件中的余弦函数,表达式 cos(60) 的结果类型为 double 、值约为 0.5 。
cos函数接受的角度参数是以弧度为单位的。因此,如果要用角度(如60度)作为参数,需要先将其转换为弧度。在C或C++中,可以使用M_PI(在math.h或cmath中定义)来表示π,从而将60度转换为弧度,即60 * M_PI / 180。
你有三种硬币,分别面值2元、5元和7元,每种硬币都有足够多。买一本书需要27元,则最少可以用5个硬币组合起来正好付清,且不需要对方找钱。
7+5+5+5+5=27共5枚,且没有更优方案。
现有 n 个完全相同的元素,要将其分为 k 组,允许每组可以有 0 个元素,则一共有C(n−1,k−1) 种分组方案。
插板法:首先,我们有n个球排成一列,然后在这n个球之间以及两端共n+1个空位中选择k-1个位置插入隔板。这样,隔板将球分成了k组,每组中的球数即为该组的元素数(包括0个)。
组合计算:从n+1个空位中选择k-1个位置插入隔板,即组合数C(n+1, k-1)。但注意到,由于我们实际上是在n个球和k-1个板之间做选择,且板的数量是固定的k-1,所以更准确的组合应该是从n+k-1个“位置”(n个球和k-1个“潜在隔板位置”的总和)中选择k个“实体”(k-1个实际隔板和1个“虚拟”的起始或结束位置,用于确定组的边界),即C(n+k-1, k)。
已知 int 类型的变量 a 和 b 中分别存储着一个直角三角形的两条直角边的长度,则该三角形的面积可以通过表达式 a / 2.0 * b 求得。
a/2.0会自动隐式转换为double,从而保证结果的正确性。
已知等差数列的通项公式an=a1+(n−1)⋅d,则前 n nn 项和的求和公式为Sn=n⋅(a1+an)/2。使用这一公式计算Sn的时间复杂度是O(1)。
公式计算一步到位,和规模无关,复杂度O(1).
诚实国公民只说实话,说谎国公民只说谎话。你来到一处分岔口,一条通往诚实国,一条通往说谎国,但不知是哪一条通往哪里。正在为难之际,走来两位路人,他们都自称是诚实国公民,都说对方是说谎国公民。你想去说谎国,可以这样问其中一位路人:“我要去说谎国,如果我去问另一个路人,他会指向哪一条路?”。
说谎的人回答的是去诚实国的路,诚实的人回答的是去诚实国的路,故而分辨出来。
手套配对
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 对不同的手套,每对手套由左右各一只组成。
小杨想知道从中取出 m 只手套,m 只手套恰好包含 k 对手套的情况有多少种。
小杨认为两种取出的情况不同,当且仅当两种情况取出的手套中存在不同的手套(同一对手套的左右手也视为不同的手套)。
输入格式
第一行包含一个正整数 t ,代表测试用例组数。
接下来是 t 组测试用例。对于每组测试用例,一共一行。
第一行包含三个正整数n,m,k,代表手套数量,取出的手套数和目标对数。
输出格式
对于每组测试数据,输出一个整数,代表可能的情况数量对109+7 取模的结果。
输入样例
输出样例

对于全部数据,保证有1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。
试题名称:美丽路径
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含 n 个节点的树,节点从 1 到 n 编号,并且每个节点要么是白色,要么是黑色。
对于树上的一条简单路径(不经过重复节点的路径),小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图,其中节点 1 和节点 4 是黑色,其余节点是白色,路径2−1−3−4 是美丽路径,而 路径2−1−3−5 不是美丽路径(相邻节点 3 和 5 颜色相同)。

对于树上的一条简单路径,小杨认为它的长度是路径包含节点的数量。小杨想知道最长的美丽路径的长度是多少。
输入格式
第一行包含一个正整数 n ,代表节点数量。
第二行包含 n 个整数c1,c2,...,cn,代表每个节点的颜色,如果 ci=0,代表节点 i 为白色,如果ci=1,代表节点 i 为黑色。
之后 n−1 行,每行包含两个正整数ui,vi,代表存在一条连接节点ui和节点vi的边。
输出格式
输出一个整数,代表最长美丽路径的长度。
输入样例1
输出样例1
输入样例2
输出样例

对于全部数据,保证有1≤n≤105,0≤ci≤1,同时保证给出的数据构成一棵树。
1.定义DP[x][0/1]:x以x为根的,x颜色为(0白1黑)的最长链路节点数量
初始化:DP[x][A[x]]=1 ,DP[x][1-A[x]]=0;
2.定义Fx:穿过x的满足题目要求的最长节点数量,则Fx由以x为端点的最长链和次长链组成。
状态转移方程:
对(父亲x->孩子y A[x]为x的节点颜色)
①若A[x]=0:DP[x][0]=max(DP[x][0],DP[y][1]+1);
②若A[x]=1:DP[x][1]=max(DP[x][1],DP[y][0]+1);
在此基础上,Fx因为由最长和次长组成,因此需要在DP[x]更新前完成更新,因此:
①若A[x]=0
Fx=max(Fx,DP[x][0]+DP[y][1]);
DP[x][0]=max(DP[x][0],DP[y][1]+1);
②若A[x]=1;
Fx=max(Fx,DP[x][1]+DP[y][0]);
DP[x][1]=max(DP[x][1],DP[y][0]+1);
目标状态:Fx