GESP-Python六级 题库
如果根结点的深度记为 1,则一棵恰有 2011 个叶结点的二叉树的深度最少是( )。
如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为 a,b,c,另有元素 d 已经出栈,则可能的入栈顺序是( )。
d,a,b,c
在程序运行过程中,如果递归调用的层数过多,会因为( )引发错误。
今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈,进栈,出栈,进栈, 进栈,出栈的操作,则此操作完成后,栈S的栈顶元素为:
面向对象程序设计将对象作为程序的基本单元,将数据和程序封装在对象中,以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中,不正确的是( )。
前序遍历序列与中序遍历序列相同的二叉树为( )。
以下( )没有涉及Python语言的面向对象特性支持。
调用 printf 函数并没有涉及到类或者对象的概念,因此不属于面向对象特性的一部分。
关于Python中面向对象的类的继承,下面说法错误的是( )
A选项描述不正确,子类可以通过继承访问到父类的公有属性,但不能访问到私有属性。
B和D选项描述正确。
C选项描述正确,子类对象可以通过句点方式访问父类的公有属性。
有6个元素,按照 6,5,4,3,2,1 的顺序进入栈S,下列( )的出栈序列是不能出现的( )。
栈的操作是先进后出(FILO),出栈序列需要满足这个规则。
选项A、B和D都可以实现。
选项C无法实现,因为3出栈后不可能有4和6出栈。
采用如下代码实现检查输入的字符串括号是否匹配,横线上应填入的代码为( )。
当遇到开括号时,应该将开括号压入栈中,以便后续匹配闭括号。
正确的代码是 s.push(symbol)。
下面代码判断队列的第一个元素是否等于 a,并删除该元素,横向上应填写( )。
判断队列的第一个元素是否等于 a,并删除该元素,应填写 not q.empty() and q.queue[0] == a。
假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%,15%,30%,16%,29%。若使用哈夫曼编码方式对字母进行二进制编码,则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为( )。
求哈夫曼编码需要先构建哈夫曼树,构建方法:① 从频率表中取出最小的两个元素,构建出新元素,② 将新元加入到频率表中,所以很明显abcdef分别对应的一组哈夫曼编码长度为3 3 2 2 2
以下Python代码实现 n 位的格雷码,则横线上应填写( )。
题目要求实现一个函数generate_gray_code(n),该函数生成n位的格雷码。格雷码的特点是相邻两个数之间只有一个位不同。解析过程
1.基础情况
n <= 0:如果 n 小于等于0,返回空列表。
n == 1:如果 n 等于1,返回 [0, 1],这是1位格雷码。
2.递归调用
生成 n-1 位的格雷码:gray_code = generate_gray_code(n - 1)。
3.构造 n 位格雷码
我们需要构造n位的格雷码,方法是:
生成 n-1 位格雷码的前缀为 0 的部分。
生成 n-1 位格雷码的前缀为 1 的部分。
具体做法是:
对于 n-1 位格雷码的每个元素 x,构造前缀为 1 的 n 位格雷码。
横线处的代码
我们需要构造前缀为1的n位格雷码。对于n-1位格雷码的每个元素x,构造前缀为1的n位格雷码:
inverted_gray_code = [int((‘1’ * n + bin(x)[2:])[-n:], 2) for x in gray_code]
选项分析
inverted_gray_code = [int((‘0’ * n + bin(x)[2:])[-n:], 2) for x in gray_code]:
错误,前缀应该是 1,而不是 0。
inverted_gray_code = [int((‘1’ * n + bin(x)[2:])[-n:], 2) for x in gray_code]:
正确,构造前缀为 1 的 n 位格雷码。
inverted_gray_code = [int((‘1’ * n + bin(x)[1:])[-n:], 2) for x in gray_code]:
错误,bin(x)[1:] 应该是 bin(x)[2:]。
inverted_gray_code = [int((‘1’ * n + bin(x)[2:])[n:], 2) for x in gray_code]:
错误,切片 [n:] 导致截取错误的位置。
因此正确的答案是B
给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG,则这棵树的正确后序遍历结果是( )。
在前序遍历中找根,在中序遍历中找根的左右子树,建好树后进行后序遍历。
结果为EDBGFCA
一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。
完全二叉树兄弟结点一般是左偶右奇,9号结点的兄弟结点只能是8号,而右子结点即9*2+1 = 19,选C
二叉树的深度定义为从根结点到叶结点的最长路径上的结点数,则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写( )。
代码的思路是计算出当前根结点左子树的深度,右子树的深度,那么以根结点为子树的深度即max(左子树,右子树)+1,+1即将根结点的深度也计算在内,所以选C。