Skip to main content

第9章 树和图

教材结构说明

本章在原教材中同样以 练习题/选择题 为主，没有独立的知识讲解部分。以下按教材原有顺序整理。

1. 二叉树遍历​

二叉树 T，已知其前序遍历序列为：

1 2 4 3 5 7 6

中序遍历序列为：

4 2 1 5 7 3 6

则其后序遍历序列为（ ）。

  • A. 4 2 5 7 6 3 1
  • B. 4 2 7 5 6 3 1
  • C. 4 2 7 5 3 6 1
  • D. 4 7 2 3 5 6 1
查看答案

答案：B

2. 前序遍历与后序遍历​

前序遍历序列与后序遍历序列相同的二叉树为（ ）。

  • A. 非叶子结点只有左子树的二叉树
  • B. 只有根结点的二叉树
  • C. 根结点无右子树的二叉树
  • D. 非叶子结点只有右子树的二叉树
查看答案

答案：B

3. 完全二叉树的高度​

如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ ）。

  • A. 5
  • B. 6
  • C. 7
  • D. 8
查看答案

答案：B

4. 满二叉树的结点数​

一棵具有 5 层结点的满二叉树的结点数为（ ）。

  • A. 31
  • B. 32
  • C. 33
  • D. 16
查看答案

答案：A

5. 表达式的后缀形式​

表达式：

a * (b + c) * d

的后缀形式是（ ）。

  • A. a b c d * + *
  • B. a b c + * d *
  • C. a * b c + * d
  • D. b + c * a * d
查看答案

答案：B

6. 有向图的度​

有向图中每个顶点的度等于该顶点的（ ）。

  • A. 入度
  • B. 出度
  • C. 入度和出度之和
  • D. 入度和出度之差
查看答案

答案：C

7. 无向图顶点度数之和​

在无向图中，所有顶点的度数之和是边数的（ ）倍。

  • A. 0.5
  • B. 1
  • C. 2
  • D. 4
查看答案

答案：C

8. 完全无向图与生成树​

设 G 是有 6 个结点的完全无向图，要得到一棵生成树，需要从 G 中删去（ ）条边。

  • A. 6
  • B. 9
  • C. 10
  • D. 15
查看答案

答案：C

9. 连通图变成树​

设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树。

  • A. m - n + 1
  • B. m - n
  • C. m + n + 1
  • D. n - m + 1
查看答案

答案：A

10. 简单无向连通图​

由四个没有区别的点构成的简单无向连通图的个数是（ ）。

  • A. 6
  • B. 7
  • C. 8
  • D. 9
查看答案

答案：A