07年数据结构B卷

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

计算二叉树的类型

是不是有点像同分异构体（bushi

### Problem : Calculate the number of binary trees in different shapes with 3 nodes and 4 nodes. (4 scores)

Explanation and Solution:

The number of different binary tree shapes with n nodes can be calculated using Catalan numbers. The formula for the n-th Catalan number is given by:

$ C_n = $

Where:

$C_n$ is the nth Catalan number.
$\binom{2n}{n}$ is the binomial coefficient, also known as "2n choose n."

The Catalan number gives the number of distinct binary trees that can be formed with n nodes. Let's apply this formula to calculate the number of binary trees for 3 and 4 nodes.

1. Number of binary trees with 3 nodes:

Using the formula for n = 3:

$ C_3 = = $

First, calculate $\binom{6}{3}$:

$ = = 20 $

Now, apply this to the Catalan formula:

$ C_3 = = 5 $

So, the number of binary trees with 3 nodes is 5.

2. Number of binary trees with 4 nodes:

Using the formula for n = 4:

$ C_4 = = $

First, calculate $\binom{8}{4}$:

$ = = 70 $

Now, apply this to the Catalan formula:

$ C_4 = = 14 $

So, the number of binary trees with 4 nodes is 14.

Final Answer:

The number of binary trees with 3 nodes is 5.
The number of binary trees with 4 nodes is 14.

These numbers are derived using the Catalan numbers formula, and they correspond to the distinct shapes of binary trees that can be formed with 3 and 4 nodes.

关于非O(n)建堆

对于O(n)建堆大家都有所了解，但是对于非O(n)是否熟练？

转换树

一遍可能还是不够熟练，如果两遍就可能刚刚好了，注意一点，左孩子右兄弟，只要是第一个孩子就放在左孩子，如果是兄弟，就放在右孩子。

关于图

注意细心一点就好了，这一道题只要考了就是送分题啊。

依然是这张图啊。

Given the graph with the following adjacency matrix and adjacency list, perform the following tasks:

(a) Draw the adjacency matrix and adjacency list representation for the graph (6 points)
(b) Use Dijkstra’s Algorithm to find the shortest paths from Vertex 1 to all other vertices (6 points)
(c) Use Kruskal’s algorithm to find the minimum-cost spanning tree (4 points)

Adjacency Matrix Representation:

The graph is represented by an adjacency matrix. Here is the given matrix:

   1   2   3   4   5   6
----------------------------
1 |    10     20    2    |
2 |  10     3   5          |
3 |    3          15      |
4 |  20  5       11  10   |
5 |        15  11      3   |
6 |  2        10     3    |
----------------------------

Adjacency List Representation:

From the matrix, the adjacency list representation is:

1 -> 2(10) -> 4(20) -> 6(2) 
2 -> 1(10) -> 3(3) -> 4(5) 
3 -> 2(3) -> 5(15) 
4 -> 1(20) -> 2(5) -> 5(11) -> 6(10) 
5 -> 3(15) -> 4(11) -> 6(3) 
6 -> 1(2) -> 4(10) -> 5(3)