GESP-Python六级 题库
在Python 中使用列表模拟栈来非递归地实现二叉树的前序遍历,为了保证遍历顺序正确,在处理完当前结点后,应该先将该结点的左孩子压入栈中,然后再将右孩子压入栈中。()
设二叉树共有n个结点,函数 preorderTraversal 的时间复杂度为O(n),空间复杂度为O(n)。
以下代码实现了0 -1背包问题的一维动态规划解法,内层循环采用经典的逆序遍历方式。若将内层循环改为正序遍历(即for j in range(w[i], W + 1):),仍能得到正确答案。
在动态规划问题中,状态空间相同且没有重复计算的情况下,“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。
以下代码中,构造函数被调用的次数是1次。
面向对象编程中,封装是指将数据和操作数据的方法绑定在一起,并对外隐藏实现细节。
以下代码能够正确统计二叉树中叶子结点的数量。
广度优先遍历二叉树可用栈来实现。
函数调用管理可用栈来管理。
在二叉排序树(BST)中,若某结点的左子树为空,则该结点一定是整棵树中的最小值结点。
下面的函数能正确判断一棵树是不是二叉排序树(左边的数字要比当前数字小,右边的数字要比当前数字大)。
1. 检查当前节点是否为空,若为空则返回True。
2. 判断当前节点的值是否满足大于最小值且小于最大值的约束条件。
3. 递归检查左子树,更新最大值约束为当前节点的值。
4. 递归检查右子树,更新最小值约束为当前节点的值。
5. 所有递归调用均需同时满足约束条件和子树的判断结果。
格雷编码相邻两个编码之间必须有多位不同,以避免数据传输错误。
小杨在玩一个闯关游戏,从第 1 关走到第 4 关。每一关的体力消耗如下(下标表示关卡编号): cost = [0, 3, 5, 2, 4 ] ,其中 cost[i] 表示到达第 i 关需要消耗的体力, cost[0]=0 表示在开始状态,体力消耗为0。小杨每次可以从当前关卡 前进 1 步或 2 步。按照上述规则,从第 1 关到第 4 关所需消耗的最小体力为 7。
在 Python 中,类的方法默认是“虚函数”,派生类只要重写方法。如果想复用基类逻辑时,可显式调用基类对应的函数。
