2. 算法设计题：设计广义表首尾表示法的存储结构，并基于该结构设计求解广义表深度的算法。（25分）

在算法设计中，广义表是一种非线性的数据结构，可以看作是一个节点的链式集合，其中每个节点可以包含其他广义表作为其元素。为了有效地存储广义表并支持深度计算，我们可以采用递归链表（Recursive List）或层次化的树形结构。

一种常见的存储结构是“头尾链接”（Head-Tail Link），它包含两个指针，头部指向前一个节点，尾部指向当前节点的最后一个元素。如果元素是另一个广义表，则尾部指向下一个广义表的头部。这种设计方便了对整个列表的操作，同时也能清晰地追踪深层结构。

以下是基于头尾链接的广义表存储结构以及求解深度的算法设计：

1. **存储结构**：
- `Node` 类：包含数据域 `data`，一个指向前一个节点的引用 `prev` 和一个指向最后一个元素的引用 `tail`。
- 如果元素是广义表，`tail` 指向另一个 `Node` 的头部，否则为 `null`。

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.tail = None

2. **求解深度**的算法：
- 对于普通元素（非列表），深度为1。
- 对于列表，递归计算第一个元素的深度加上1。

   def depth(node):
       if node is None:
           return 0
       elif isinstance(node.data, list):  # 判断是否是广义表
           return 1 + depth(node.tail)  # 遍历内部列表
       else:
           return 1