### 数据结构知识点总结
#### 第一章 绪论课后作业
**1. 简述线性结构与非线性结构的不同点。**
- **线性结构：** 在线性结构中，数据元素之间存在着一对一的关系。例如，数组、链表等都属于线性结构。在线性结构中，除了第一个元素没有前驱外，每个元素都有一个前驱和一个后继。
- **非线性结构：** 非线性结构指的是数据元素之间存在一对多或者多对一的关系。如树形结构和图状结构等。在非线性结构中，元素之间的关系更加复杂多样，可以有多重层次和分支。
**2. 分析下面各程序段的时间复杂度（每小题5分，共20分）**
这一部分的具体代码未给出，因此无法直接分析时间复杂度。通常来说，时间复杂度的分析主要关注循环结构的嵌套层数、递归调用的次数等因素。例如，一个简单的for循环的时间复杂度通常是O(n)，而两层嵌套循环的时间复杂度则是O(n^2)。
#### 第二章 线性表课后作业
**1. 填空题**
- （1）在顺序表中插入或删除一个元素，需要平均移动 **n/2** 个元素，具体移动的元素个数与表长和该元素在表中的位置有关。
- （2）线性表中结点的集合是有限的，结点间的关系是一对一的。
- （3）向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 **n-i+1** 个元素。
- （4）顺序表中逻辑上相邻的元素的物理位置 **相邻** 。单链表中逻辑上相邻的元素的物理位置不一定相邻。
**2. 试写一算法，对单链表实现就地逆置。**
实现单链表的逆置可以通过三个指针：`prev`、`current` 和 `next` 来完成。初始时，`prev` 指向 `NULL`，`current` 指向头节点，`next` 指向 `current` 的下一个节点。然后不断更新这三个指针的位置，直到 `current` 变为 `NULL`。具体的算法步骤如下：
```c
void reverseList(Node* &head) {
Node* prev = NULL;
Node* current = head;
Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
```
#### 第三章 栈和队列课后作业
**1. 填空题**
- （1）栈是一种特殊的线性表，允许插入和删除运算的一端称为 **栈顶** ，不允许插入和删除运算的一端称为 **栈底** 。
- （2）**队列** 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
- （3）在具有n个单元的循环队列中，队满时共有 **n-1** 个元素。
**2. 计算题**
- ① 当 `front=11`，`rear=19` 时，循环队列中有 **8** 个元素。
- ② 当 `front=19`，`rear=11` 时，考虑到循环队列的特点，此时队列中有 **22** 个元素。
**3. 写出下列程序段的输出结果**
这段程序的主要功能是将字符 `'c'`, `'a'`, `'k'` 入栈，然后出栈 `'a'`，接着再入栈 `'t'` 和出栈的 `'a'`，之后继续入栈 `'s'`，最后将栈中所有元素依次出栈并打印。根据栈先进后出的特性，最终输出的结果为 `'skatc'`。
#### 第四章 串课后作业
**1. 算法填空题**
这部分的算法主要是字符串匹配算法，用于寻找子串在主串中的位置。关键点在于填充条件判断语句。
- ① `i <= strlen(s)-strlen(t)`，确保子串t能在主串s中完全匹配。
- ② `i++`，移动主串索引。
- ③ `j=0`，重置子串索引。
- ④ `j==strlen(t)`，当子串完全匹配时。
**2. 写出子串t="ABCABCACAB"的next值和nextval值**
对于字符串 "ABCABCACAB"，其`next`和`nextval`数组分别为：
- `next`: [0, 0, 0, 1, 2, 3, 4, 5, 3, 4]
- `nextval`: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
#### 第五章 数组和广义表课后作业
**1. 选择题**
- （1）数组 `a[1…60, 1…70]` 的基地址为2048，每个元素占2个存储单元，以列序为主序顺序存储，则元素 `a[32,58]` 的存储地址为 **2048 + 57 * 60 * 2 + 31 * 2 = 7420** 。
- （2）一个二维数组 `A`，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 **6 * 8 * 6 = 288** 个字节。
- （3）三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 **行号**、**列号** 和 **值** 。
- （4）对于广义表 `((a,b),(c,d))`：
- ① `GetHead[((a,b),(c,d))] = (a,b)`
- ② `GetHead[GetTail[((a,b),(c,d))]] = (c,d)`
- ③ `GetHead[GetTail[GetHead[((a,b),(c,d))]]] = b`
- ④ `GetTail[GetHead[GetTail[((a,b),(c,d))]]] = d`
**2. 递归算法比非递归算法花费更多的时间，对吗？为什么？**
递归算法与非递归算法的效率问题取决于具体情况。通常情况下，递归算法会因为额外的函数调用开销而略慢于非递归算法。但是，当问题规模较小时，这种差异可能并不明显。此外，现代编译器和解释器可以通过优化技术减少这种差异，甚至在某些场景下使递归版本更为高效。因此，是否递归算法花费更多的时间并非绝对，而是取决于具体的应用场景和实现细节。
#### 第六章 树和二叉树课后作业
**1. 填空题**
- （1）一棵完全二叉树有1000个结点，则它必有 **500** 个叶子结点，有 **499** 个度为2的结点，有 **1** 个结点只有非空左子树，有 **0** 个结点只有非空右子树。
- （2）用二叉链表存储n个结点的二叉树(n>0)，共有 **n+1** 个空指针域；采用三叉链表存储，共有 **2n+1** 个空指针域。
- （3）由3个结点所构成的二叉树有 **5** 种形态。
**2. 假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。**
根据给定的层序序列和中序序列，可以推断出该二叉树的结构。根节点为A，其左子树为DBGEHJ，右子树为CIF。通过中序序列可知，左子树的根节点为G，右子树的根节点为I。进一步分析可得完整的二叉树结构。
**3. 编写递归算法，计算二叉树中叶子结点的数目。**
```c
int countLeaves(Node* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
```
#### 第七章 图课后作业
**1. 填空题**
- （1）图有 **邻接矩阵**、**邻接表** 等存储结构，遍历图有 **深度优先搜索**、**广度优先搜索** 等方法。
- （2）有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 **出度** 。
- （3）如果n个顶点的图是一个环，则它有 **n** 棵生成树。
- （4）图的逆邻接表存储结构只适用于 **有向图** 。
- （5）用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 **递增** 的次序来得到最短路径的。
- （6）拓扑排序算法是通过重复选择具有 **0** 个前驱顶点的过程来完成的。
**2. 求解下图的最小生成树，并计算出它的权值。**
这一部分的具体图形未给出，因此无法直接求解最小生成树及其权值。通常，求解最小生成树的方法有Prim算法和Kruskal算法等。
#### 第九章 查找课后作业
**1. 填空题**
- （1）具有11个元素的有序表进行折半查找，则平均查找长度为 **3** 。
- （2）在各种查找方法中，**二分查找** 适用于已排序的线性表；**散列查找** 适用于键值映射关系；**顺序查找** 适用于无序的线性表。
以上是针对给定文件中提到的一些知识点的详细解释和拓展。希望这些内容能够帮助您更好地理解和掌握数据结构的相关知识。
