GESP-Python六级 题库

共 132 道题 ,第 1 / 7 页 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

在二叉搜索树(BST)中,若中序遍历的序列为{1, 2, 3, 4, 5},且先序遍历的第一个序列元素为3,则下列说法正确的是()。

A
该树一定是一棵完全二叉树。
B
元素4和5不可能是兄弟节点。
C
元素1所在节点的深度可能大于3(根节点深度为1)。
D
元素2一定是元素1的父节点。
答案与解析
正确答案:B
中序遍历序列{1, 2, 3, 4, 5}表明二叉搜索树的节点按升序排列,根节点为3时,左子树包含{1, 2},右子树包含{4, 5}。先序遍历首元素为3,确认根节点是3。左子树中,2可为1的父节点或1为2的左子节点;右子树中,4与5可构成不同父子关系。完全二叉树要求除最后一层外满填充,但当前结构无法确定层级填充情况。节点深度由路径长度决定,1的深度取决于其在左子树中的位置。兄弟关系取决于共同父节点,4和5可能同属一个父节点也可能不是。各节点具体位置存在多种合法构造方式,需依据BST性质和遍历顺序推导可能结构。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

某二叉树共有10个结点,记为A~J,已知它的先序遍历序列为:<strong>AB D H I E C F J G</strong>,中序遍历序列为:<strong>H DI B E A FJ C G</strong>,则该二叉树的后序遍历序列是()。

A
H I D E B J F G C A
B
H I D B E J F G C A
C
I H D E B J F G C A
D
H I D E B F J G C A
答案与解析
正确答案:A
根据先序遍历序列确定根节点,结合中序遍历序列划分左右子树。先序序列首元素为当前子树根节点,在中序序列中找到该根节点位置,其左侧为左子树结点,右侧为右子树结点。递归应用此过程,重建各子树结构。每层递归均按先序定位根、中序分左右的方式推进,直至所有结点位置确定。后序遍历顺序为左子树、右子树、根节点,依据重建的树结构进行访问即可得到后序序列。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

下列关于树的遍历的说法中,正确的一项是()。

A
对任意一棵树进行深度优先遍历,所得序列一定唯一。
B
已知一棵二叉树的先序遍历和后序遍历序列,可以唯一确定这棵二叉树。
C
若一棵二叉树的先序遍历序列与中序遍历序列相同,则该二叉树一定为只有右子树的链式结构。
D
已知一棵二叉树的先序遍历序列,即可唯一地确定该二叉树的结构。
答案与解析
正确答案:C
深度优先遍历的序列唯一性取决于访问子节点的顺序是否固定,若无明确次序则结果不唯一。仅凭先序和后序遍历无法唯一确定二叉树结构,因缺乏中序提供的根节点分割信息。先序与中序序列相同时,表明每个节点均无左子树,遍历过程中始终优先访问右子树。仅知先序遍历时,无法区分各节点在树中的具体位置,缺失分支结构信息,不能重建唯一二叉树。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.2 哈夫曼树

有6 个字符,它们出现的次数分别为:{2 , 3 , 3 , 4 , 6 , 8 },现在用哈夫曼编码为这些字符编码,最小加权路径长度WPL(每个字符的出现次数X它的编码长度,再把每个字符结果加起来)的值为()。

A
58
B
60
C
62
D
64
答案与解析
正确答案:D
将给定的6个字符出现次数作为叶节点权重,构建哈夫曼树。每次选择当前权值最小的两个节点合并为新节点,新节点的权值为两者之和,重复此过程直至只剩一个根节点。每个字符的编码长度等于其在哈夫曼树中的路径长度(从根到该叶节点的边数)。计算每个字符的权值与其路径长度的乘积,再求所有字符的乘积之和,即得最小加权路径长度WPL。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

对n个不同符号的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点,则n的值是()。

A
60
B
58
C
57
D
56
答案与解析
正确答案:B
哈夫曼树由n个叶子结点构成,每个非叶子结点由两个子结点合并生成。设非叶子结点数为k,则树中总共有n + k个结点。每次合并减少一个符号,从n个符号合并到1个根结点需进行n - 1次合并,故非叶子结点数为n - 1。因此,总结点数为n + (n - 1) = 2n - 1。给定总结点数为115,代入公式得2n - 1 = 115,解此方程可求n的值。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

给定一棵二叉树,采用广度优先搜索(BFS) 算法,返回右视图所有节点的值。其中右视图定义为:二叉树的右视图是从树的右侧看过去时可见的节点集合,即右视图中的每个节点都是某一层中最右侧的节点。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def rightSideView(root):
    rightmost_value_at_depth = {}
    max_depth = -1

    node_queue = []
    depth_queue = []
    node_queue.append(root)
    depth_queue.append(0)

    while node_queue:
        node = node_queue.pop(0)
        depth = depth_queue.pop(0)

        if node is not None:
            max_depth = max(max_depth, depth)
            rightmost_value_at_depth[depth] = node.val

            node_queue.append(node.left)
            node_queue.append(node.right)

            # (1) 填空处
            depth_queue.append(depth + 1)
            depth_queue.append(depth + 1)

    right_view = []
    # (2) 填空处
    for depth in range(max_depth + 1):
        right_view.append(rightmost_value_at_depth[depth])

    return right_view

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(4)

    print(rightSideView(root))


A
(1)depth , depth ;(2)0 , max_depth
B
(1)depth + 1 , depth + 1 ;(2)0 , max_depth + 1
C
(1)depth + 1 , depth + 1 ;(2)1 , max_depth + 1
D
(1)depth , depth ;(2)1 , max_depth
答案与解析
正确答案:B
使用BFS遍历二叉树,按层处理节点。每层维护一个映射记录该层最后访问的节点值,因队列中同一层节点按从左到右入队,同层后续节点会覆盖前序节点值,最终保留最右侧节点。节点入队时将其左右子节点依次加入队列,对应深度加1。初始化根节点深度为0,故遍历所有层需从0开始到max_depth(含)。遍历完成后,按深度从小到大收集每层最右节点值形成右视图结果序列。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

下列关于树的深度优先搜索(DFS)的说法中,正确的是()。

A
对树进行DFS 时,一定是按层从上到下依次访问结点
B
对任意一棵树进行DFS,得到的遍历序列唯一
C
对一棵树进行DFS 时,常借助递归或栈实现
D
DFS 只能用于二叉树,不能用于普通树
答案与解析
正确答案:C
深度优先搜索通过访问起始节点后递归探索每个子树,直到无法深入为止。该过程可利用函数调用栈通过递归实现,也可显式使用栈结构模拟访问顺序。遍历过程中访问节点的次序取决于访问子节点的顺序,不同顺序会导致不同的遍历路径。树的结构不限于二叉树,DFS适用于任何树形结构。层序访问是广度优先搜索的特征,而非深度优先搜索。遍历序列是否唯一由树的结构和子节点访问顺序共同决定。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

以下函数check()用于判断一棵二叉树是否为( )。

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def check(root):
    if not root:
        return True
    q = deque()
    q.append(root)
    has_null = False
    while q:
        cur = q.popleft()
        if not cur:
            has_null = True
        else:
            if has_null:
                return False
            q.append(cur.left)
            q.append(cur.right)
    return True
A

满二叉树

B

完全二叉树

C

二叉搜索树

D

平衡二叉树

答案与解析
正确答案:B
函数通过层序遍历处理二叉树节点。初始化队列并将根节点入队。遍历过程中,从队列取出节点,若当前节点为空,设置标志表示已遇到空节点。若当前节点非空且空节点标志已设置,则后续逻辑基于节点存在性与队列操作继续推进。将当前节点的左右子节点依次加入队列,无论其是否为空。遍历持续直至队列为空。整个过程依据节点出队顺序、空节点出现时机及子节点入队规则进行。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

以下代码实现了二叉树的( )。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def traverse(root):
    if not root:
        return
    traverse(root.left)
    traverse(root.right)
    print(root.val, end=" ")


if __name__ == "__main__":
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    print("后序遍历结果:", end="")
    traverse(root)
A

前序遍历

B

中序遍历

C

后序遍历

D

层序遍历

答案与解析
正确答案:C
分析函数traverse的执行顺序:首先判断根节点是否存在,若不存在则直接返回;接着递归调用左子树,然后递归调用右子树,最后打印当前节点的值。该过程遵循先处理左子树、再处理右子树、最后访问根节点的顺序。观察函数中对左右子树的调用位置与根节点值输出的时间关系,可推断其遍历次序的特点。结合二叉树遍历定义,此种调用结构对应特定的遍历方式。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

下面代码实现了哈夫曼编码,则横线处应填写的代码是( )。

class Symbol:
    def __init__(self, ch='', freq=0, code=''):
        self.ch = ch
        self.freq = freq
        self.code = code


class Node:
    def __init__(self, w=0, l=-1, r=-1, sym=-1):
        self.w = w
        self.l = l
        self.r = r
        self.sym = sym


def pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB):
    if pA[0] < n and (pB[0] >= len(internal_idx) or nodes[leaf_idx[pA[0]]].w <= nodes[internal_idx[pB[0]]].w):
        res = leaf_idx[pA[0]]
        pA[0] += 1
        return res
    else:
        res = internal_idx[pB[0]]
        pB[0] += 1
        return res


def dfs_build_codes(u, nodes, sym_list, path):
    if u == -1:
        return
    if nodes[u].sym != -1:
        sym_list[nodes[u].sym].code = ''.join(path)
        return
    path.append('0')
    dfs_build_codes(nodes[u].l, nodes, sym_list, path)
    path.pop()
    path.append('1')
    dfs_build_codes(nodes[u].r, nodes, sym_list, path)
    path.pop()


def build_huffman_codes(sym_list):
    n = len(sym_list)
    for sym in sym_list:
        sym.code = ''
    if n <= 0:
        return -1
    if n == 1:
        sym_list[0].code = '0'
        return 0

    nodes = []
    leaf_idx = []
    for i in range(n):
        leaf_idx.append(len(nodes))
        nodes.append(Node(sym_list[i].freq, -1, -1, i))
    leaf_idx.sort(key=lambda x: (nodes[x].w, nodes[x].sym))

    internal_idx = []
    pA = [0]
    pB = [0]
    for k in range(1, n):
        x = pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB)
        y = pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB)
        z = len(nodes)
        # 补全缺失的构建内部节点代码(原代码空白处)
        nodes.append(Node(w=nodes[x].w + nodes[y].w, l=x, r=y, sym=-1))
        internal_idx.append(z)

    root = internal_idx[-1] if internal_idx else -1
    path = []
    dfs_build_codes(root, nodes, sym_list, path)
    return root


if __name__ == "__main__":
    syms = [
        Symbol('A', 5),
        Symbol('B', 9),
        Symbol('C', 12),
        Symbol('D', 13),
        Symbol('E', 16),
        Symbol('F', 45)
    ]
    root = build_huffman_codes(syms)
    print(f"哈夫曼树根节点下标:{root}")
    for sym in syms:
        print(f"字符 '{sym.ch}' (频率 {sym.freq}):编码 {sym.code}")
A
nodes.append(Node(nodes[x].w + nodes[y].w, x, y, -1)) 
internal_idx.append(z)
B
nodes.append(Node(nodes[x].w + nodes[y].w, x, y, 1)) 
internal_idx.append(z)
C
nodes.append(Node(nodes[x-1].w + nodes[y].w, x, y, 1)) 
internal_idx.append(z)
D
nodes.append(Node(nodes[x+1].w + nodes[y].w, x, y, 1)) 
internal_idx.append(z)
答案与解析
正确答案:A
分析符号频率并构建叶子节点,将所有叶子节点按权重加入待处理队列。每次从队列中选取权重最小的两个节点合并为新内部节点,新节点权重为其子节点权重之和,左右子节点分别指向被合并的两个节点,且该内部节点不关联具体字符。将新生成的内部节点加入节点集合,并记录其索引。重复此过程直至队列中仅剩一个节点,即哈夫曼树的根节点。在合并过程中需维护叶节点和内部节点的索引列表,确保每次取最小权重节点时能正确访问对应节点。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.2 哈夫曼树

以下关于哈夫曼编码的说法,正确的是( )。

A

哈夫曼编码是定长编码

B

哈夫曼编码中,没有任何一个字符的编码是另一个字符编码的前缀

C

哈夫曼编码一定唯一

D

哈夫曼编码不能用于数据压缩

答案与解析
正确答案:B
哈夫曼编码基于字符出现频率构建二叉树,频率越低的字符位于更深的叶节点。编码通过从根到叶路径生成,左分支标记0,右分支标记1,或反之。每个字符对应唯一路径,路径序列即为其编码。由于编码由叶节点决定,任意编码均无法通过另一条完整路径延伸得到,故一个字符的编码不会是另一个字符编码的前缀。构建过程中,不同合并顺序可能产生不同结构的二叉树,导致编码方案不唯一。编码长度随字符频率动态变化,非固定长度。该机制将高频字符映射为短码,低频字符映射为长码,整体编码长度趋于最小化。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念
以下函数实现了二叉排序树(BST)的( )操作。
class TreeNode: 
    def __init__(self, val=0, left=None, right=None): 
        self.val = val 
        self.left = left 
        self.right = right 
def op(root, x): 
    if not root: 
        return TreeNode(x) 
    if x &lt; root.val: 
        root.left = op(root.left, x) 
    else: 
        root.right = op(root.right, x) 
    return root
A

查找

B

插入

C

删除

D

遍历

答案与解析
正确答案:B
分析函数参数,识别递归结构与节点创建行为。观察函数在空节点时返回新节点,表明涉及结构修改。比较输入值与根节点值决定递归方向,左子树处理较小值,右子树处理较大值,符合二叉排序树的组织规则。递归调用嵌入赋值语句,更新左或右子树引用,体现自底向上传播的结构调整过程。无中序前驱或后继节点查找逻辑,未处理双子树非空的复杂情况,排除删除操作的可能性。函数未返回布尔类型或节点值,排除纯查找行为。遍历操作通常不改变树结构且会访问所有节点,与此函数仅沿单一路径深入的行为不符。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

下列代码实现了树的深度优先遍历,则横线处应填入( )。

class TreeNode: 
    def __init__(self, x): 
        self.val = x 
        self.left = None 
        self.right = None 
def dfs1(root): 
    if not root: 
        return 
    temp = [] 
    temp.append(root) 
    while temp: 
        node = temp[-1] 
        temp.pop() 
        print(node.val, end=" ") 
        if node.right: 
            temp.append(node.right) 
        if node.left: 
            temp.append(node.left) 
def dfs2(root): 
    if not root: 
        return 
    st = [] 
    st.append(root) 
    while st: 
        node = st[-1] 
        st.pop() 
        print(node.val, end=" ") 
        if node.right: 
            st.append(node.right) 
        ——————————————————


A
if node.left: 
    st.append(node.left)
B
if node.right: 
    st.append(node.left)
C
if node.left: 
    st.append(node.right)
D
if node.right: 
    st.append(node.right)
答案与解析
正确答案:A
分析代码逻辑,观察遍历过程中栈的使用方式。dfs1函数中先将右子节点压栈,再将左子节点压栈,导致左子节点先被弹出处理,实现的是根-左-右的访问顺序。dfs2函数结构与dfs1一致,已存在对右子节点的判断和压栈操作。为保持相同的遍历顺序,需在右子节点之后处理左子节点。栈为后进先出结构,因此后续入栈的左子节点将在下一轮循环中优先被访问。需补全对左子节点的条件判断及入栈操作,以维持与dfs1一致的处理流程。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

给定一棵普通二叉树(节点值没有大小规律),下面代码判断是否存在值为 x 的结点,则横线处应填入( )。

class TreeNode: 
    def __init__(self, x): 
        self.val = x 
        self.left = None 
        self.right = None 
from collections import deque 
def bfs_find(root, x): 
    if not root: 
        return None 
    q = deque() 
    q.append(root) 
    while q: 
        cur = q.popleft() 
        if cur.val == x: 
            return cur 
        ______________________ 
    return None
A
q.append(cur.left)
B
q.append(cur.right)
C
if cur.left: 
    q.append(cur.left) 
if cur.right: 
    q.append(cur.right)
D
if cur.right: 
    q.append(cur.left) 
if cur.left: 
    q.append(cur.right)
答案与解析
正确答案:C
使用队列实现广度优先搜索,从根节点开始逐层遍历。每次从队列头部取出一个节点,检查其值是否为目标值。若匹配,则返回该节点。否则,将其存在的左子节点和右子节点依次加入队列尾部,确保后续节点能按层次顺序被访问。遍历持续到队列为空,期间未找到目标值则最终返回None。需保证每个节点的左右子树在存在前提下被加入队列,以避免空引用错误并维持遍历完整性。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

在二叉排序树(Binary Search Tree, BST)中,假设节点值互不相同。给定如下搜索函数,以下说法 一定正确的是( )。

class Node: 
    def __init__(self, val=0, left=None, right=None): 
        self.val = val 
        self.left = left 
        self.right = right 
def find(root, x): 
    while root: 
        if root.val == x: 
            return True 
        if x &lt; root.val: 
            root = root.left 
        else: 
            root = root.right 
    return False
A

最坏情况下,访问结点数是 O(log n)

B

最坏情况下 ,访问结点数是O(n)

C

无论如何 ,访问结点数都不超过树高的一半

D

一定比在普通二叉树中搜索快

答案与解析
正确答案:B
分析二叉排序树的结构特性,搜索过程从根节点开始,根据目标值与当前节点值的大小关系决定向左子树或右子树移动。每一步比较后仅进入一个子树,路径唯一。访问的节点数等于搜索路径上的节点总数。树的高度由节点插入顺序决定,可能为平衡状态下的O(log n),也可能退化为链状结构时的O(n)。搜索过程中不进行回溯,也不访问无关分支。访问节点数取决于树的实际形态和目标值所在位置。
题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

以下函数 createTree() 构造的树是什么类型?

A

满二叉树

B

完全二叉树

C

二叉排序树

D

其他都不对

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
17 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

已知二叉树的 中序遍历 是 [D, B, E, A, F, C],先序遍历 是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是( )。

A

[D, E, B, F, C, A]

B

[D, B, E, F, C, A]

C

[D, E, B, C, F, A]

D

[B, D, E, F, C, A]

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
18 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

完全二叉树可以用数组连续高效存储。如果节点从 1 开始编号,则对有两个孩子节点的节点 i ,()。

A

左孩子位于 2i ,右孩子位于 2i+1

B

完全二叉树的叶子节点可以出现在最后一层的任意位置

C

所有节点都有两个孩子

D

左孩子位于 2i+1 ,右孩子位于 2i+2

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

设有字符集 {a, b, c, d, e, f} ,其出现频率分别为 {5, 9, 12, 13, 16, 45} 。哈夫曼算法构造最优前缀编码,以下哪一组可能是对应的哈夫曼编码?(非叶子节点左边分支记作 0,右边分支记作 1,左右互换不影响正确性)。

A

a: 00;b: 01;c: 10;d: 110;e: 111;f: 0

B

a: 1100;b: 1101;c: 100;d: 101;e: 111;f: 0

C

a: 000;b: 001;c: 01;d: 10;e: 110;f: 111

D

a: 10;b: 01;c: 100;d: 101;e: 111;f: 0

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
20 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

请将下列树的深度优先遍历代码补充完整,横线处应填入( )。

A

vector=[]

B

list=[]

C

queue=[]

D

stack = []

答案与解析
正确答案:D
这道题暂未补解析。
题目详情