#cspjcSt. 树和图

树和图

树和图真题

2019真题

1.(2019-8)一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为 1,若某结点的下标为 i,则其左孩子位于下标 2i处、右孩子位于下标 2i+1 处),则该数组的最大下标至少为()? {{ select(1) }}

  • 6
  • 10
  • 15
  • 12

2.(2019-14)假设一棵二叉树的后序遍历序列为 DGJHEBIFCA,中序遍历序列为 DBGEHJACIF,则其前序遍历序列为()。{{ select(2) }}

  • ABCDEFGHIJ
  • ABDEGHJCFI
  • ABDEGJHCFI
  • ABDEGHJFIC

2020真题

3.(2020-8)有 10个顶点的无向图至少应该有( )条边才能确保是一个连通图。{{ select(3) }}

  • 9
  • 10
  • 11
  • 12

4.(2020-8)独根树的高度为 1。具有 61 个结点的完全二叉树的高度为( ){{ select(4) }}

  • 7
  • 8
  • 5
  • 6

2021真题

5.(2021-6)对于有 n 个顶点、m 条边的无向连通图 (m>n),需要删掉( )条边才能使其成为一棵树。{{ select(5) }}

  • n−1
  • m−n
  • m−n−1
  • m−n+1

6.(2021-8)如果一棵二叉树只有根结点,那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有 ( )种不同的形态?{{ select(6) }}

  • 16
  • 15
  • 17
  • 32

7.(2021-9)表达式 a*(b+c)*d 的后缀表达式为( ),其中 * 和 + 是运算符。{{ select(7) }}

  • **a+bcd
  • abc+*d*
  • abc+d**
  • *a*+bcd

8.(2021-14)以 a 为起点,对下边的无向图进行深度优先遍历,则 b,c,d,e 四个点中有可能作为最后一个遍历到的点的个数为( )。 {{ select(8) }}

  • 1
  • 2
  • 3
  • 4

2022真题

9.(2022-6)对表达式 a+(b-c)*d 的前缀表达式为( ),其中 +、-、* 是运算符。{{ select(9) }}

  • *+a-bcd
  • +a*-bcd
  • abc-d*+
  • abc-+d

10.(2022-7)假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%,15%,30%,16%,29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码,字母 d 的编码长度( )位。{{ select(10) }}

  • 1
  • 2
  • 2 或 3
  • 3

11.(2022-8)一棵有 n个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1个位置。若存储在数组第 9个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。{{ select(11) }}

  • 8、18
  • 10、18
  • 8、19
  • 10、19

12.(2022-9)考虑由 N个顶点构成的有向连通图,采用邻接矩阵的数据结构表示时,该矩阵中至少存在( )个非零元素。{{ select(12) }}

  • N−1
  • N
  • N+1
  • N2N^2

2023真题

13.(2023-5)根节点的高度为 1,一棵拥有 2023个节点的三叉树高度至少为()。{{ select(13) }}

  • 6
  • 7
  • 8
  • 9

14.(2023-8)后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是{{ select(14) }}

  • ((6-(2+3))*(3+8/2))^2+3
  • 6-2+3*3+8/2^2+3
  • (6-(2+3))*((3+8/2)^2)+3
  • 6-((2+3)*(3+8/2))^2+3

15.(2023-10)假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为 5%,9%,12%,13%,16%,45%。请问以下哪个选项是字符abcdef分别对应的一组哈夫曼编码? {{ select(15) }}

  • 1111,1110,101,100,110,0
  • 1010,1001,1000,011,010,00
  • 000,001,010,011,10,11
  • 1010,1011,110,111,00,01

16.(2023-11)给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG。请问这棵树的正确后序遍历结果是什么? {{ select(16) }}

  • EDBGFCA
  • EDGBFCA
  • DEBGFCA
  • DBEGFCA

17.(2023-12)考虑一个有向无环图,该图包含 4 条有向边:(1,2),(1,3),(2,4)和 (3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序? {{ select(17) }}

  • 4,2,3,1
  • 1,2,3,4
  • 1,2,4,3
  • 2,1,3,4

2024真题

18.(2024-11)在无向图中,所有顶点的度数之和等于( )。{{ select(18) }}

  • 图的边数
  • 图的边数的两倍
  • 图的顶点数
  • 图的顶点数的两倍

19.(2024-12)已知二叉树的前序遍历为 [A,B,D,E,C,F,G],中序遍历为 [D,B,E,A,F,C,G],请问该二叉树的后序遍历结果是?( ){{ select(19) }}

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

2025真题

20.(2025-4)用 5个权值 10,12,15,20,25构造哈夫曼树,该树的带权路径长度是多少? {{ select(20) }}

  • 176
  • 186
  • 196
  • 206

21.(2025-5)在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和,这个总和等于? {{ select(21) }}

  • 顶点数
  • 边数
  • 顶点数 + 边数
  • 顶点数 ×2