GESP-C++七级 题库
一棵完全二叉树有431个结点,则叶结点有多少个?( )
深度为8的满二叉树共有:28-1(255)个结点,深度为9的满二叉树共有:29 -1(511)个结点。一棵拥有431个结点的完全二叉树,深度为9。第9层结点数量:431-255=176(都是叶结点),第八层总结点数量:
2(8-1) =128,第8层中为叶结点的数量:128-176/2=40,所以这棵二叉树叶结点:176+40=216
下列关于树的说法,错误的是( )。
深度优先搜索是一个更广泛概念,包括三种不同的遍历方式:前序遍历、中序遍历、后序遍历,虽然中序遍 历是深度优先搜索的一种形式,所以不能说二叉树的中序遍与其深度优先搜索遍历总是相同的。
一个简单无向图有10个结点、30条边。再增加多少条边可以成为完全图。( )
n个结点的完全无向图,最多有n*(n-1)/2条边。10个结点最多:10*9/2=45条边,所以还需要15条边。
以下哪个方案可以合理解决或缓解哈希表冲突( )。
在哈希表中,冲突(也称碰撞)是指两个不同的键被映射到哈希表的同一位置。
A选项,这个方案显然不是一个好的解决策略,因为它会导致信息丢失。如果频繁发生冲突,大量新元素将被丢弃, 哈希表将失去其存储和检索数据的能力。
B选项,这个方案不可取,因为会导致旧元素被覆盖,从而丢失数据。哈希表应该能够可靠地存储和检索每个键对应 的值。
C选项,这个方案不合理,因为没有明确定义“下一个位置”是什么。在哈希表中,冲突位置之后的“下一个位置” 可能仍然是一个冲突位置,或者可能是一个已经存储了其它元素的位置。此外这种策略也没有提供一种系统化的方法 来遍历哈希表中的所有元素。
D选项,这个方案合理,描述了一种称为开放地址法(Open Addressing)的冲突解决策略。在这种方法中,当发生 冲突时,哈希表会尝试在冲突位置的后续位置找到一个空位来存储新元素。
一个迷宫,已知从起点不经过重复结点到达终点的路径有且仅有一条,则下面说法错误的是( )。
通过深搜或广搜可以找到这条路径,所以A选项和B选项正确。
C选项,根据题目条件,从起点不经过重复点到达终点的路径仅有一条,这意味着所有与起点连通的节点都在这条路 径上,因此也必然与终点连通。
D选项,尽管从起点不经过重复结点到达终点的路径有且仅有⼀条,但不在这条路径的“冗余”分支上还是可能有环的,比如下图所示的迷宫。因此不一定可以抽象为无向无环图。
下面程序的输出为( )。
log函数通常返回的是自然对数。8的自然对数约为2.07944154167,然而将log(8)的结果转换为int类型时,仅保留整数部分。
下面程序的输出为( )。
初始化第0行和第0列,从(1,1)点开始,等于上面值+左边值。
上题中程序的时间复杂度为( )。
代码的核心部分是一个双重循环,每个循环从1~n,所以时间复杂度为O(N2)
下列选项中,哪个可能是下图的广度优先遍历序列( )。

1, 3, 5, 7, 4, 2, 6, 8, 9
9, 4, 2, 1, 3, 7, 5, 6, 8
1, 3, 5, 7, 6, 8, 9, 4, 2
9, 4, 7, 2, 1, 3, 5, 6, 8
根据广度优先搜索的概念,从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正确。
图的存储和遍历算法,下面说法错误的是( )。
图的深度优先搜索和⼆叉树的先序遍历都基于深度优先的原理。