数据结构常考应用典型例题

一、队列

问题1：

请设计一个队列，满足以下要求：

初始时队列为空。
入队时，允许增加队列占用空间。
出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减。
入队操作和出队操作的时间复杂度始终保持为 $O(1)$。

（1）该队列是应选择链式存储结构，还是应选择顺序存储结构？

答案：
选择链式存储结构。

解释：

顺序存储结构的队列在进行入队操作时，如果达到容量限制，需要扩容并复制现有元素，这会导致时间复杂度不再是 $O(1)$。
链式存储结构允许动态增加节点的空间，并且可以通过指针来管理节点的链接。在出队操作中，出队元素所占用的空间可以循环利用，不需要立即释放。因此，链式存储结构能够更好地满足所有要求。

（2）画出该队列的初始状态，并给出判断队空和队满的条件。

初始状态：

1 2	[front] --> NULL [rear] --> NULL

判定条件：

队空条件：front == rear，表示队头和队尾指针指向同一个位置。
队满条件：front == rear->next，表示队头指针指向的节点的下一个节点与队尾指针指向的节点重合，意味着没有空闲节点可用。

（3）画出第一个元素入队后队列状态。

插入第一个元素后的状态：

1 2	[front] --> [rear] --> NULL [data1]

解释：

在插入第一个元素后，front 和 rear 都指向新插入的节点。
此时队列只有一个节点，且指向的下一个节点为空。

（4）给出入队操作和出队操作的基本过程。

// 定义节点结构
typedef struct Node {
    int data;                // 存储数据
    struct Node *next;      // 指向下一个节点
} Node;

// 入队操作
void Enqueue(Node **front, Node **rear, int value) {
    if ((*front) == (*rear)->next) { // 队满
        Node *newNode = (Node *)malloc(sizeof(Node)); // 创建新节点
        newNode->next = NULL;
        (*rear)->next = newNode; // 在 rear 后面插入新节点
    }

    // 保存入队元素到 rear 所指结点中
    (*rear)->data = value;
    (*rear) = (*rear)->next; // 更新 rear 指针
}

// 出队操作
int Dequeue(Node **front, Node **rear) {
    if ((*front) == (*rear)) { // 队空
        printf("队列为空，出队失败\n");
        return -1; // 返回失败标志
    }

    int value = (*front)->data; // 取出 front 所指结点中的元素
    (*front) = (*front)->next; // 更新 front 指针
    return value; // 返回出队元素
}

解释：

入队操作： 首先检查队列是否已满。如果满，则创建一个新节点，并将其添加到队尾；然后将入队元素保存到 rear 所指的节点中，并更新 rear 指针。
出队操作： 首先检查队列是否为空。如果为空，返回失败标志；否则，取出 front 所指的节点数据，并更新 front 指针。

问题2：

（1）队列在顺序存储时的 “假溢出” 现象指什么?

答案：
“假溢出”现象是指在顺序存储结构的队列中，虽然队列中仍有可用的存储空间，但由于队头和队尾指针仅向后移动而不回退，可能导致无法执行入队操作。这是因为当队尾指针达到数组的末尾后，即使队头指针已经向前移动，队尾指针仍无法重新使用之前出队后空出的存储空间，从而造成队列“满”的假象。

（2）简述一种可行的假溢出的解决方法。

答案：
解决“假溢出”现象的一种方法是采用 循环队列。循环队列通过将队列的尾指针（rear）和头指针（front）在数组的边界处重新连接，使得它们能够在数组的头部和尾部循环使用存储空间。

入队操作时：
- 检查队列是否已满：如果 (rear + 1) % m == front，则队列满。
- 否则，将新元素插入到 rear 所指位置，并更新尾指针为 rear = (rear + 1) % m。
出队操作时：
- 检查队列是否为空：如果 front == rear，则队列空。
- 否则，将 front 所指的元素出队，并更新头指针为 front = (front + 1) % m。

（3）若用数组 q[1..m] 表示队列，队列头指针 front、尾指针 rear 的初值均为1，基于（2）中的方法，如何求队列的当前长度？如何判定队空？如何判定队满？

答案：

队列长度：
当前队列的长度可以通过以下公式计算： $ = (rear - front + m) % m $ 其中 length 表示队列中元素的个数。由于 front 和 rear 都是从1开始计数，使用模运算可以确保结果始终为非负。
判定队空：
当 front 和 rear 指针相等时，表示队列为空： $ front == rear $
判定队满：
当 rear 的下一个位置等于 front 时，表示队列已满： $ (rear + 1) % m == front $

二、树

（一）二叉排序树

题目： 利用逐点插入法建立序列(50，72，43, 87, 75，20, 34，53, 65, 30)对应的二叉排序树，并求出这10个元素基于该二叉排序树的组织，在等概率情况下查找成功时的平均查找长度(ASL)。

1. 建立二叉排序树

根据二叉排序树的定义，逐点插入法构建树的过程如下：

计算查找长度的加权总和： $ = (1 ) + (2 ) + (3 ) + (4 ) + (5 ) $ 计算如下：
- 层 1: $1 \times 1 = 1$
- 层 2: $2 \times 2 = 4$
- 层 3: $3 \times 3 = 9$
- 层 4: $4 \times 3 = 12$
- 层 5: $5 \times 1 = 5$
$ = 1 + 4 + 9 + 12 + 5 = 31 $
计算平均查找长度（ASL）： $ = = = 3.1 $