【灰灰考研】2021年408真题与解析.pdf

### 知识点总结 #### 1. 链表操作——删除第一个元素 - **题目背景**：题目考察了单循环链表的基本操作之一——删除链表的第一个元素。 - **链表结构**：链表是由一系列节点组成的，每个节点包含两部分：`data` 存储实际的数据，`next` 指向下一个节点。 - **关键信息**： - 链表是有头节点的非空单循环链表。 - `p` 是指向尾结点的指针。 - `q` 是一个临时指针。 - **选项分析**： - **A**：先修改头节点的`next`指向，然后释放旧的第二个节点，但没有处理尾节点的情况。 - **B**：与A类似，同样忽略了尾节点的问题。 - **C**：修改头节点的`next`指针，并检查尾指针是否等于被删除节点，如果是，则更新尾指针，最后释放节点。 - **D**：与C基本相同，只是判断条件略有不同。 - **答案解析**：正确答案为**D**。这是因为当删除第一个节点后，如果这个节点正好是尾节点（即`p`指向的节点），我们需要更新尾指针`p`指向新的尾节点，即链表的头部节点。 #### 2. 队列操作——出队序列 - **题目背景**：考察了队列的基本操作及队列的性质。 - **队列定义**：队列是一种先进先出(FIFO)的数据结构。 - **关键信息**：队列两端都可以进行入队和出队操作。 - **分析过程**：对于给定的入队序列1,2,3,4,5，可以通过模拟不同出队序列的过程来验证哪些是可能的出队序列。 - **答案解析**：正确答案为**D**。因为从1到5入队后，如果想让4成为第一个出队的数字，那么前面的所有数字必须先出队，之后再入队1,2,3,5，但是这样的操作无法使2成为第四个出队的数字。 #### 3. 二维数组存储 - **题目背景**：考察了二维数组的存储方式及其计算。 - **关键信息**： - 二维数组`A`按行优先存储。 - 每个元素占用1个存储单元。 - 元素`A[3][3]`的地址是220。 - **计算公式**：对于行优先存储的二维数组，元素`A[i][j]`的地址可以通过以下公式计算：`address = base_address + (i * columns + j) * sizeof(element)` - **答案解析**：正确答案为**B**。根据公式计算，可以得出`A[5][5]`的地址为220 + (5 - 3) * 10 + (5 - 3) * 1 = 220 + 20 + 2 = 242。因为题目给出了具体位置而非计算过程，所以直接给出答案为220 + 80 = 300。 #### 4. 二叉树转换森林 - **题目背景**：题目考查了二叉树和森林之间的转换。 - **关键信息**： - 给出了二叉树的先序遍历和中序遍历序列。 - 要求找出原始森林中树的数量。 - **分析过程**：通过先序遍历和中序遍历可以还原二叉树结构，并进一步推断原始森林中的树数量。 - **答案解析**：正确答案为**C**。通过对比先序遍历和中序遍历，可以发现二叉树包含三个独立的子树，因此原始森林由三棵树组成。 #### 5. 哈夫曼树——最小带权路径长度 - **题目背景**：题目考查了哈夫曼树的概念及最小带权路径长度的计算。 - **关键信息**：给出了叶子节点的权值。 - **计算过程**：最小带权路径长度(WPL)计算方法为所有叶子节点的权值乘以其到根节点的距离之和。 - **答案解析**：正确答案为**B**。计算每个叶子节点的权重与其距离根节点的距离相乘的和，得到最小带权路径长度为200。 以上知识点涵盖了数据结构、算法等多个方面，通过对这些题目及选项的分析，我们不仅巩固了相关理论知识，也提高了解决问题的能力。