GESP-C++八级 题库
表达式 ‘3’ & 1 的结果为 ‘1’ 。
ASCII码’3’为51,是奇数,&1操作是取51的最低位2进制。结果为1,而非字符’1’。
使用 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).
诚实国公民只说实话,说谎国公民只说谎话。你来到一处分岔口,一条通往诚实国,一条通往说谎国,但不知是哪一条通往哪里。正在为难之际,走来两位路人,他们都自称是诚实国公民,都说对方是说谎国公民。你想去说谎国,可以这样问其中一位路人:“我要去说谎国,如果我去问另一个路人,他会指向哪一条路?”。
说谎的人回答的是去诚实国的路,诚实的人回答的是去诚实国的路,故而分辨出来。
ABCDE五个小朋友,排成一队跑步,其中AB两人必须排在一起,一共有48种排法。
排列组合捆绑法。AB在一起,看成1个人,AB和BA共2中情况,所以是排队是:2*A(4,4)=48。
已知 double 类型的变量 a 和 b ,则执行语句 a = a + b; b = a - b; a = a - b; 后,变量 a 和 b 的值会互换。
a和b是double类型,加减会造成精度的损失,导致2个变量值不能互换。
一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个,再放回袋子,这样进行3次后,可能的颜色顺序有8种。
已知 int 类型的变量 a 和 b 中分别存储着一个直角三角形的两条直角边的长度,则斜边的长度可以通过表达式 sqrt(a * a + b * b) 求得。
根据勾股定理求出。
在一个包含 v 个顶点、 e 条边的带权连通简单有向图上使用Dijkstra算法求最短路径,时间复杂度为O(v2),可进一步优化至O(e+vlog(v))。
暴力枚举每个点,时间复杂度是O(v2);用优先队列每次找到距离最短的点,优先队列时间复杂度是O(logn),每个点和边都访问一次,所以时间复杂度是O(e+vlogv)。
在N个元素的二叉排序树中查找一个元素,最差情况的时间复杂度是O(logN)。
二叉排序树最坏的情况退化成1条链,时间复杂度是O(n)。
为解决哈希函数冲突,可以使用不同的哈希函数为每个表项各建立一个子哈希表,用来管理该表项的所有冲突元素。这些子哈希表一定不会发生冲突。
子哈希表仍然可能产生冲突。
要判断无向图的连通性,在深度优先搜索和广度优先搜索中选择,深度优先的平均时间复杂度更低。
都需要对每个点遍历一次,总时间复杂度不会有差距。可能在其他方面开销有区别,例如辅助空间等方面。