GESP-C++七级 题库
表达式 ‘a’ << 1 的结果为 'a ’ 。
'a’是字符常量,在C++中其ASCII码值为97。‘a’ << 1 等同于将整数97左移1位,结果为194。
选择排序一般是不稳定的。
选择排序在排序过程中,会选择最小(或最大)的元素与当前元素交换位置。这种交换可能改变相同元素的相对顺序,因此选择排序一般是不稳定的排序算法。
埃氏筛法和欧拉筛法都是使用筛法思想生成素数表的算法,欧拉筛法的时间复杂度更低。
埃氏筛法的时间复杂度是O(n log logn),欧拉筛法是O(n)。
使用 math.h 或 cmath 头文件中的正弦函数,表达式 sin(30) 的结果类型为 double 、值约为 0.5 。
sin函数输入的是弧度制的角度,角度制下的30度,转换为弧度制是π/6。
一个图,不管是否连通,都可以使用深度优先搜索算法进行遍历。
与连通性无关。对于非连通图,遍历完一个连通分量后,可以在未访问的节点中选择新的起点,继续进行DFS,直到所有节点都被访问。
某个哈希表键值 x 为整数, H(x) = x % p 是常用的哈希函数之一,要求 p 选择素数是因为这样不会产生冲突。( )
当x是p的倍数是会发送冲突。选择素数作为模数p,可以使哈希函数的值分布更均匀,减少冲突的概率,但不能完全避免冲突。
使用单链表实现队列时,链表头结点作为队首比链表头结点作为队尾更便于操作。
如果头结点作为队首,当新元素入队时,通过尾指针来实现入队操作,时间复杂度O(1);当删除元素时, 删除链表头结点,更新头指针,时间复杂度O(1)
如果头结点作为队尾,当新新元素入队时,通过头指针实现入队,时间复杂度O(1);当删除元素时,每次都需要遍历链表找到当前的队尾前一个元素(单链表),让尾指针指向这个元素,时间复杂度O(n)。
一个图中,每个结点表达一个人,连接两个结点的边表达两个结点对应的人相互认识,则这个图可以用来表达社交网络
图属于网状结构可以表示社交网络。
唯一分解定理(算术基本定理)指出,每个大于1的自然数都可以唯一地分解成若干个素数的乘积。因此,我们可以很容易的对给定的自然数 n 进行质因数分解,时间复杂度仅为O(log(n))。
对n进行质因数分解的时间复杂度为O(sqrt(n)
使用 math.h 或 cmath 头文件中的对数函数,表达式 log(128) 的结果类型为 double 、值约为 7.0 。
log默认是以e为底。
现使用有 N 个表项的哈希表,从 M 个元素中进行查找。该哈希表为解决哈希函数冲突,为每个表项处建立单链表存储冲突元素。其查找操作的最坏情况时间复杂度为O(M)。
如果M个元素全部冲突,则需要去单链表进行查询,时间复杂度为O(M).
动态规划有递推实现和递归实现,对于很多问题,通过记录子问题的解,两种实现的时间复杂度是相同的。
使用递归算法并记录子问题的解就是动态规划中的记忆化搜索,和递推算法实现动态规划的时间复杂度一致
泛洪算法的递归方法容易造成溢出,因此大的二维地图算法中,一般不用递归方法。
C++中栈空间一般比较小,递归层数过大容易造成栈溢出。