10年数据结构A卷

这一张试卷只记录一些没有怎么留意过的知识点，之前已经出现过的知识点就不记录在内了。

树的高度

The height of a complete binary tree with k nodes is 「log2(k+1)」. (1-node tree has height 1). (2 scores)

Answer:

Answer: The height of a complete binary tree with $ k $ nodes is given by $ _2(k+1) $.

Explanation:

In a complete binary tree, every level of the tree is fully filled except possibly for the last level, which is filled from left to right.

  • Height of a binary tree: The height of a binary tree is defined as the length of the longest path from the root to any leaf. The height of a tree with only one node is 1, and as nodes are added, the height increases when the tree grows in depth.

For a complete binary tree with $ k $ nodes:

  1. The number of nodes in a complete binary tree at level $ h $ (starting from 0) is $ 2^h $.
  2. The height $ h $ is the total number of levels in the tree. For $ k $ nodes, the height $ h $ can be approximated by $ _2(k) $, because in the worst case, the tree will have a height of $ _2(k+1) $.

So, if you have $ k $ nodes:

  • $ _2(k+1) $ gives the theoretical height, but since the height is an integer, we use the floor function $ _2(k+1) $ to ensure that the height is a whole number.

Example:

  • For $ k = 7 $ nodes, $ _2(7 + 1) = _2(8) = 3 $. The tree has 3 levels (height = 3).
  • For $ k = 15 $ nodes, $ _2(15 + 1) = _2(16) = 4 $. The tree has 4 levels (height = 4).

Important Notes:

  • A tree with just 1 node (a single root) has a height of 1, which is consistent with the formula $ _2(1 + 1) = _2(2) = 1 $.

二叉搜索树：

手动跟踪执行创建一个二叉搜索树（BST），输入序列为：{46, 25, 78, 62, 12, 37, 70, 29}，初始时树为空。(6 分)

image-20241203195253347

最小生成树和最短路问题：

给定以下图表示的通信网络，边的权重表示连接两个城市之间的通道费用。如何选择最便宜的路径以连接所有城市？并且如何获取连接每对城市之间的最便宜路径？如果有多个路径，请绘制所有的选择。

image-20241203200203680

解答过程：

1. 选择最便宜的路径连接所有城市：

image-20241203200328079

2. 获取连接每对城市之间的最便宜路径：

A B C D E F G
A 1 B: 6 BC: 9 BC: 10; 2 BC: 13
B 1 5 C: 8; C: 9; A: 3; C: 12;
C B: 6 5 3 4 6 7
D BC: 9 C: 8 3 C: 7; C: 9 C: 10;
E BC: 10; C: 9; 4 C: 7; C: 10 3
F 2 A: 3; 6 C: 9 C: 10 C: 13;
G BC: 13 C: 12; 7 C: 10; 3 C: 13;