下列C++代码的输出结果是( )。
查看答案与解析
计算机中的三角函数使用的是弧度,3.1415926可以看作Π,也就是求sin(Π/2)=1.
下列C++代码的输出结果是( )。
计算机中的三角函数使用的是弧度,3.1415926可以看作Π,也就是求sin(Π/2)=1.
对于如下图的二叉树,说法正确的是( )。

先序遍历为123,中序遍历为132,后序遍历为321,答案选D
已知两个序列s1= {1,3,4,5,6,7,7,8,1} 、s2= {3,5,7,4,8,2,9,5,1} ,则它们的最长公共子序列是()。
最长公共子序列指最长的序列满足即是s1的子序列又是s2的子序列,选项A满足要求且是最长的
关于序列 {2,7,1,5,6,4,3,8,9} ,以下说法错误的是( )。
{2,5,6,8,9}也是它的最长上升子序列,并不唯一
关于图的深度优先搜索和广度优先搜索,下列说法错误的是( )。
广度优先搜索往往使用队列按照节点的深度有序的方式依次遍历,很容易发现,后序遍历中节点的深度并不有序。
对于如下二叉树,下面访问顺序说法错误的是( )。

后序遍历可以记作左右根,上图的后序遍历为HDEBFIGCA,选项A错误
以下哪个方案不能合理解决或缓解哈希表冲突( )。
不能丢弃发生冲突的新元素
在C++中,关于运算符&,下面说法正确的是( )。
运算符&是按位与,结果类型为整类型,A错误。,数字3的二进制为11,6的二进制为110,所以3&6=。注意B和D选项中,011为八进制的9,而111、110、101则均为十进制。
下面关于图的说法正确的是( )。
每条有向边都会贡献一个入度和一个出度,所以所有顶点的⼊度和出度的总和就是图的边数的两倍,选项D正确。
图的存储和遍历算法,下面说法错误的是( )。
图的深度优先搜索和⼆叉树的先序遍历都基于深度优先的原理。
如下图所示的邻接表结构,表示的是下列哪个选项中的图?

注意到存边方式是邻接表,0号点(V1)连向的是3号点(V4)和1号点(V2),1号点连向的是4,2,0号点,2号点连向的是4,3,1号点,依次类推,可以选出正确选项C。
如下图所示的邻接矩阵(inf表示无穷大),表示的是下列哪个选项中的图?

注意到存边方式是邻接矩阵,0连向2,3,距离分别是12和30,1不连向任何人,2连向4,距离是32,依次类推,可以选出正确答案A。
下面程序的输出为( )。
容易发现这是斐波那契数列,可以使用递推的方式,算出斐波那契数列的前6项分别是1,1,2,3,5,8,答案为B。
下面 count_triple 函数的时间复杂度为( )。
两层for循环,每层for循环的上界均为n,总时间复杂度为%O(n^2)%
下列选项中,哪个可能是下图的深度优先遍历序列( )。

深度优先遍历需要按照能走就走的原则进行遍历,A选项5后面应该是6,B选项3后面应该是7,D选项8后面应该是5
C++语言中,表达式 6 & 5 的结果类型为 int 、值为 1 。
6的二进制位110,5二进制为101,6&5=4
冒泡排序是稳定的排序算法。
稳定的排序算法指值相同的元素在排序前后的相对顺序不变,冒泡排序是稳定的排序算法
唯一分解定理(算术基本定理)指出,每个大于1的自然数都可以唯一地分解成若干个素数的乘积。因此,我们可以很容易的对给定的自然数 n 进行质因数分解,时间复杂度仅为O(log(n))。
对n进行质因数分解的时间复杂度为O(sqrt(n)
C++语言中,可以为同一个类定义多个构造函数。
C++会根据参数的不同选择正确的构造函数。
使用 math.h 或 cmath 头文件中的对数函数,表达式 log(128) 的结果类型为 double 、值约为 7.0 。
log默认是以e为底。
一颗 N 层的二叉树,至少有2N−1个节点。
N层的二叉树,最少的节点数量为N。
非连通图不能使用广度优先搜索算法进行遍历。
非连通图需要进行多次广度优先搜索算法。
现使用有 N 个表项的哈希表,从 M 个元素中进行查找。该哈希表为解决哈希函数冲突,为每个表项处建立单链表存储冲突元素。其查找操作的最坏情况时间复杂度为O(M)。
如果M个元素全部冲突,则需要去单链表进行查询,时间复杂度为O(M).
动态规划有递推实现和递归实现,对于很多问题,通过记录子问题的解,两种实现的时间复杂度是相同的。
使用递归算法并记录子问题的解就是动态规划中的记忆化搜索,和递推算法实现动态规划的时间复杂度一致
泛洪算法的递归方法容易造成溢出,因此大的二维地图算法中,一般不用递归方法。
C++中栈空间一般比较小,递归层数过大容易造成栈溢出。
黑白翻转
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含 n 个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。小杨认为一棵树是美丽树当且仅当在删除所有白色节点之后,剩余节点仍然组成一棵树。
小杨每次操作可以选择一个白色节点将它的颜色变为黑色,他想知道自己最少要执行多少次操作可以使得这棵树变为美丽树。
输入格式
第一行包含一个正整数n,代表树的节点数。
第二行包含 n 个非负整数a1,a2,...,an,其中如果 ai=0,则节点 i的颜色为白色,否则为黑色。
之后 n−1 行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。
输出格式
输出一个整数,代表最少执行的操作次数。
输入样例
输出样例
样例解释
将节点 1 和 3 变为黑色即可使这棵树变为美丽树,此时删除白色节点 5,剩余黑色节点仍然组成一棵树。
数据范围

对于全部数据,保证有1≤n≤105,0≤ai≤1。
我们考虑一个树的哪些节点删除后,依然为一棵树。显然是所有叶子节点。在把所有叶子节点删去后,新的树的叶子节点依然可以继续删除。以此类推。也就是说,对于一个白点u,如果以u为根的子树中不存在黑点的话,那么这个白点就可以被删除,否则该白点需要被染为黑点,只需要一遍深度优先搜索,最终答案为n-黑色节点数量-以u为根的子树中不存在黑点的节点数量。还有一个特殊情况,即根节点也可能可以删除,解决方法是钦定一个黑色节点为根。
区间乘积
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个包含 n 个正整数的序列A=[a1,a2,...,an]。
小杨想知道有多少对<l,r>(1≤l≤r≤n) 满足al×al+1×...×ar为完全平方数。
一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得x=y×y。
输入格式
第一行包含一个正整数n,代表正整数个数。
第二行包含 n 个正整数a1,a2,...,an,代表序列A。
输出格式
输出一个整数,代表满足要求的 <l,r>数量。
输入样例
输出样例
样例解释
满足条件的 <l,r> 有<3,3> 和<1,5>。
数据范围

对于全部数据,保证有1≤n≤105,1≤ai≤30。
一段区间积的真实值很显然我们无法求出来,那么就要通过完全平方数的性质进行转化。我们有结论:一个数是完全平方数,当且仅当这个数质因数分解后,所有质因子的指数都为偶数。那么,判定一个数是否为完全平方数,可以等价于判定它的所有素因子的指数是否为偶数。注意到a[i]<=30,那么a[i]中质因子的个数只有2,3,5,7,11,13,17,19,23,29共10个,可以用十位的二进制数进行表示,若a[i]中含有奇数个第x个质因子,则让二进制表示的第x位为1,否则为0。设这个十位二进制数为b[i],则问题转变为找到[l,r]满足b[l]b[l+1]b[l+2]…b[r]=0,区间的xor和是满足做差的性质的,进一步转化为sum[r]^sum[l-1]=0(sum数组为b数组的xor前缀和),也就是找l和r,满足sum[r]=sum[l-1],这一步可以先统计出sumi等于某一定值k的数量cnt,根据乘法原理,最终答案为cnt*(cnt-1)/2,而k的取值范围为[0~],可以使用类似桶排的方式统计。