#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
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