GESP-C++六级 题库
在求解最优化问题时,动态规划常常涉及到两个重要性质,即最优子结构和( )。
动态规划的性质主要包括最优子结构、无后效性和有重叠子问题
最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。这意味着问题的最优解可以通过其子问题的最优解来构建。
无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。这一性质确保了动态规划方法的有效性,因为当前阶段的选择不会影响到之前阶段的状态。
有重叠子问题:子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。这一性质是动态规划算法能够通过存储和重用子问题的解来提高效率的关键。
青蛙每次能跳1或2步,下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法,错误的是( )。
状态表示:dp[i]表示青蛙到达第i个台阶的跳法。
状态转移方程:第i个台阶由两个状态转移过来①i-2级跳两步②i-1级跳一部,因此状态转移方程为:dp[i]=dp[i-1]+dp[i-2]
目标状态:dp[n]
int jump_recur(int n)使用递归方式(斐波那契),无记忆化,因此复杂度为指数。
int jump_dp(int n)使用动规(递推)方式,复杂度O(n).
阅读以下二叉树的广度优先搜索代码:
使用以上算法,在以下这棵树搜索数值20时,可能的输出是( )。
该程序使用广搜方式,因此为二叉树层序遍历,答案选C
同上题中的二叉树,阅读以下二叉树的深度优先搜索代码:
使用以上算法,在二叉树搜索数值20时,可能的输出是( )。
该题目使用栈代替了DFS的递归形式,由输出和push的顺序,可以知道该题目为先序遍历,因此答案为A。
在上题的树中搜索数值3时,采用深度优先搜索一共比较的节点数为( )。
该二叉树中序遍历有序,同时从构造形态上,为一棵二叉排序树,但是程序并不是按照二叉排序树的规则,题目是先序遍历比较,因此比较的节点依次为:5、2、-4、3,共4次。
面向对象的编程思想主要包括以下哪些原则( )?
贪心、动态规划、回溯
并发、并行、异步
递归、循环、分治
封装、继承、多态
给定一个简单的类定义如下,( )语句在类的外部正确地创建了一个 Circle 对象并调用了 getArea 函数?
以下代码希望能在一棵二叉排序树中搜索特定的值,请在横线处填入( ),使其能正确实现相应功能。
3 位格雷编码的正确顺序是( )。
000, 001, 010, 011, 100, 101, 110, 111
000, 001, 011, 010, 110, 111, 101, 100
000, 010, 001, 011, 100, 110, 101, 111
000, 010, 110, 100, 111, 101, 011, 001
以下动态规划算法的含义与目的是( )。
阅读以下广度优先搜索的代码:
使用以上算法遍历以下这棵树,可能的输出是( )。

给定一个空栈,执行以下操作序列:
操作序列: push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()
最终栈中的元素是( )。
在求解最优化问题时,动态规划常常涉及到两个重要性质,即最优子结构和( )。
分治法
贪心策略
回溯算法
若一棵二叉树的先序遍历为:A, B, D, E, C, F、中序遍历为:D, B, E, A, F, C,它的后序遍历为( )。
以下代码使用了辗转相除法求解最大公因数,请在横线处填入( ),使其能正确实现相应功能。
下面的代码片段用于反转单链表,请进行( )修改,使其能正确实现相应功能。