### 数据结构期末试题知识点解析
#### 一、填空题解析
1. **完全二叉树的节点数量**
- 深度为 \(k\) 的完全二叉树至少有 \(2^{k-1}\) 个结点。这是因为完全二叉树的定义是除了最后一层外，其他层都是满的，而最后一层的结点尽可能地集中在左侧。最极端的情况下，只有根结点，即深度为 1 的完全二叉树至少有一个结点。
- 对于具有 10 个叶结点的二叉树来说，假设这棵树是满的，则除了叶子结点外，每个结点都有两个子结点。因此，如果有 \(n\) 个度为 2 的结点，那么就有 \(n+1\) 个叶子结点。根据题目中的描述，这里 \(n+1 = 10\)，解得 \(n = 9\)。
2. **数组元素的存储地址计算**
- 给定数组 \(a[1..5,1..8]\) 的基地址为 200，每个元素占 2 个存储单元，以行序为主序顺序存储。根据公式 \(Address = BaseAddress + (Row * ColumnSize + Column) * ElementSize\)，其中 \(Row = 4-1 = 3\), \(Column = 6-1 = 5\)，可以计算出 \(a[4,6]\) 的存储地址为 \(200 + (3 * 8 + 5) * 2 = 200 + 29 * 2 = 200 + 58 = 258\)。
3. **算法评价指标**
- 数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。时间复杂度衡量算法运行时间的增长率，而空间复杂度衡量算法执行过程中占用内存空间的增长率。
4. **存储结构特点**
- 顺序存储结构是通过物理位置相邻的元素来表示元素之间的逻辑关系的。链式存储结构则是通过指针（或链接）指向下一个元素来表示元素之间的逻辑关系的。
5. **单链表中插入子链表的操作**
- 若要在一个单链表中 \(p\) 所指结点之后插入一个子链表，子链表第一个结点的地址为 \(s\)，子链表最后一个结点的地址为 \(t\)，则正确的操作步骤是：首先更新子链表最后一个结点的指针，使其指向原链表中 \(p\) 结点之后的结点，即 \(t \rightarrow next = p \rightarrow next\)；然后将 \(p\) 结点的指针指向子链表的第一个结点，即 \(p \rightarrow next = s\)。
6. **有向图的出度和入度**
- 在有向图 \(G\) 中，邻接矩阵 \(A\) 中第 \(i\) 行中所有非零元素个数之和等于顶点 \(i\) 的出度，第 \(i\) 列中所有非零元素个数之和等于顶点 \(i\) 的入度。
7. **顺序表的操作复杂度**
- 访问顺序表中的任意结点的时间复杂度为 \(O(1)\)，因为可以直接通过索引访问。删除结点的时间复杂度为 \(O(n)\)，因为可能需要移动后续的所有元素。
8. **完全二叉树的编号问题**
- 完全二叉树从根开始编号，每一层从左到右编号。对于一个有 100 个结点的完全二叉树，编号最大的非叶结点的编号可以通过以下方式计算：对于完全二叉树，最后一个非叶结点的编号可以通过公式 \(floor(n/2)\) 计算得出，这里 \(n=100\)，所以编号最大的非叶结点的编号为 \(50\)。
9. **折半查找法的应用**
- 给定有序表为 \((12, 18, 24, 35, 47, 50, 62, 83, 90, 115, 134)\)，使用折半查找法查找 100，需要比较 3 次才能确定 100 不在列表中。第一次比较 62，第二次比较 83，第三次比较 90。
10. **Dijkstra 最短路径算法**
- Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按照距离的递增次序依次产生。
11. **树转换为二叉树后的遍历顺序**
- 如果 \(T_2\) 是由树 \(T_1\) 转换而来的二叉树，那么 \(T_1\) 中结点的后序遍历就是 \(T_2\) 中结点的中序遍历。这是因为在二叉树中，左孩子代表兄弟关系，右孩子代表孩子关系。
12. **广义表的操作**
- 广义表 \(A=(d)\) 中，Head(Tail(Head(Tail(Tail(A))))) 的值为 \(d\)。这是因为 Tail 运算会去除广义表的第一个元素，而 Head 运算会返回广义表的第一个元素。
13. **无向连通图的边数范围**
- 无向连通图的顶点个数为 \(n\)，则该图最少有 \(n-1\) 条边，此时图形成一棵树；最多有 \(n(n-1)/2\) 条边，此时图形成一个完全图。
#### 二、选择题解析
1. **排序算法的选择**
- 选项 C 正确。归并排序是一种稳定的排序算法，其时间复杂度为 \(O(n\log n)\)。
2. **合法的出栈序列**
- 选项 B 不是合法的出栈序列。因为在栈中，元素是以后进先出的原则出栈的。对于序列 4,5,3,1,2，当 5 出栈后，3 应该紧接着出栈，而不是先出 4 再出 3。
3. **深度优先遍历的顶点序列**
- 选项 D 正确。根据无向图的结构，从 a 开始的深度优先遍历顺序可以是 a, e, d, f, c, b。
4. **链表的特点**
- 选项 B 错误。链表不具备随机访问任一元素的特点。链表的访问需要从头结点开始，逐一跟随指针访问各个结点。
5. **三叉树的度为 0 的结点数量**
- 选项 A 正确。在一棵三叉树中，度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为 4 个。这个结果可以通过树的度数与结点数的关系推导得出。
以上是对给定文件中涉及的数据结构知识点的详细解析。这些知识点覆盖了数据结构的基础概念、算法评价标准、链表操作、图的遍历等重要内容，有助于学生更好地理解和掌握数据结构的核心原理和技术。
