GESP-C++七级 题库
下面程序的运行结果为( )。
给定一个无向图,图的节点编号从 0 到 n - 1,图的边以邻接表的形式给出。
下面的程序使用深度优先搜索(DFS)遍历该图,并输出遍历的节点顺序。横线处应该填入的是?( )
标记 neighbor 已经入栈并且将 neighbor 入栈,选择 D。(图结构、深度优先搜索)
给定一个整数数组 nums,找到其中最长的严格上升子序列的长度。
子序列是指从原数组中删除一些元素(或不删除)后,剩余元素保持原有顺序的序列。
下面的程序横线处应该填入的是?( )
考察 DP 解决最长上升子序列问题,如果 nums[i] > nums[j] ,则以 i 结尾的最长上升子序列可以从以 j 结尾 的最长上升子序列转移而来,所以选择 D 项。(动态规划)
给定一个整数数组 nums,找到其中最长的严格上升子序列的长度。
子序列是指从原数组中删除一些元素(或不删除)后,剩余元素保持原有顺序的序列。
该程序的时间复杂度为?( )
11, 12 两行执行了 O(n2) 次循环,所以复杂度为 O(n2)。(动态规划)
给定两个无向图 G1和 G2 ,判断它们是否同构。图的同构是指两个图的节点可以通过某种重新编号的方式完全匹配,且边的连接关系一致。
为了简化问题,假设图的节点编号从 0 到 n-1,并且图的边以邻接表的形式给出。下面程序中横线处应该给出的是?( )
应该将所有 neighbor ⽤ , 隔起来,因此选择 C。(图结构)
给定一个 m×n的二维网格 grid,每个格子中有一个非负整数。
请找出一条从左上角 (0, 0) 到右下角 (m-1, n-1) 的路径,使得路径上的数字总和最小。每次只能向右或向下移动。
横线处应该填入的是?( )
B。(i, j) 可以从 (i 1 , j) 或者 (i, j 1) 走过来,因此 grid[i][j],选择 B。(动态规划)
给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
下面横线处应该填入的是?( )
dp[i] 表示以 i 结尾的最大子段和。如果 i-1 也在最大子段和中,对应 dp[i-1] + nums[i] ,否则只有 i 在最 大子段和,对应 nums[i] ,所以选择 B。(动态规划)
已知小写字母 b 的ASCII码为98,下列C++代码的输出结果是( )。
在C++中,字符在计算机中是整数存储,小写字母b的ASCII码为98,对a进行自增操作时,其ASCII码增加到99,程序输出的是ASCII码值为99的字符,即小写字母c
下面程序的输出为( )。
log函数通常返回的是自然对数。8的自然对数约为2.07944154167,然而将log(8)的结果转换为int类型时,仅保留整数部分。
下面程序的输出为( )。
初始化第0行和第0列,从(1,1)点开始,等于上面值+左边值。
下列C++代码的输出结果是( )。
计算机中的三角函数使用的是弧度,3.1415926可以看作Π,也就是求sin(Π/2)=1.
下面程序的输出为( )。
容易发现这是斐波那契数列,可以使用递推的方式,算出斐波那契数列的前6项分别是1,1,2,3,5,8,答案为B。