### 2018年浙江大学878考研专业课试题知识点总结
#### 一、C语言基础知识
**1. strlen() 和 sizeof() 的区别**
- **strlen()**: 该函数用于计算字符串的实际长度（不包括末尾的空字符'\0'）。它适用于字符串，返回的是字符串中实际字符的数量。
- **sizeof()**: 这个运算符可以计算变量或数据类型的字节数。对于字符串来说，它计算的是包括空字符'\0'在内的整个数组的大小。
**示例**:
```c
char str[] = "Hello";
int len1 = strlen(str); // 返回 5
int len2 = sizeof(str); // 返回 6
```
**2. static 关键字**
- 在C语言中，`static`关键字主要有以下用途：
- **局部静态变量**: 当在一个函数内声明为`static`时，该变量的生命周期与程序相同，即使函数退出，其值也会被保留。
- **全局静态变量**: 在文件作用域中使用`static`，该变量只在当前文件中可见，并且默认初始化为零。
- **静态函数**: `static`修饰的函数只在当前文件中可见。
**3. stdin 和 stdout 流**
- **stdin**: 标准输入流，通常指向键盘。
- **stdout**: 标准输出流，通常指向显示器。
#### 二、C语言编程题目解析
**1. 插入排序实现**
代码段展示了使用插入排序对整数数组进行排序的过程。插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体步骤如下：
- 将数组的前两个元素视为已排序的部分。
- 然后，遍历未排序的数组部分。
- 对于每个元素，将其与已排序部分的元素比较，并逐位移动较大的元素，直到找到正确的位置插入该元素。
**示例代码**:
```c
void F(int i, int A[], int n) {
int tmp = A[i];
for (int j = i + 1; j > 0 && A[j - 1] > tmp; j--) {
A[j] = A[j - 1];
}
A[j] = tmp;
}
// 主函数调用
int main() {
int A[] = {6, -1, 7, 2, 5, 8, 9, 4};
int n = sizeof(A) / sizeof(A[0]);
for (int i = 1; i < n / 2; i++) {
F(i, A, n);
}
for (int i = 0; i < n; i++) {
printf("%d", A[i]);
}
return 0;
}
```
**输出结果**:
- 经过排序后的数组输出结果应为：`-1 2 6 7 5 8 9 4`
**2. 十六进制转换**
这段代码实现了将一个字符串中包含的有效十六进制数字转换为对应的十进制数的功能。程序通过宏定义检查字符是否属于十六进制数字，并根据十六进制规则计算出最终的十进制数值。
**示例代码**:
```c
#define D(x) x <= '9' && x >= '0'
#define C(x) x <= 'f' && x >= 'a'
int main() {
char A[] = "-12-bBb-";
int n = strlen(A);
int num = 0, flag = 0;
for (int i = 0; i < n; i++) {
if (D(A[i])) {
num = 16 * num + A[i] - '0';
} else if (C(A[i])) {
num = 16 * num + 10 + A[i] - 'a';
} else if (A[i] == '-') {
flag = -flag;
} else {
break;
}
}
printf("%d", num * flag);
return 0;
}
```
**输出结果**:
- 最终输出的十进制数值为：`299`
**3. 数组倒置计数与位操作**
此题涉及数组元素的比较和交换，以及位运算。通过两层循环计算数组中逆序对的数量；接着，利用位运算实现两个元素的交换。
**示例代码**:
```c
#define F(a, b) (a ^= b ^= a ^= b)
int Fnc(int A[], int n) {
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (A[i] > A[j]) count++;
return count;
}
int main() {
int A[] = {5, 1, 7, 4, 3, 6, 2};
printf("%d", Fnc(A, 7));
F(A[1], A[2]);
printf("%d", Fnc(A, 7));
return 0;
}
```
**输出结果**:
- 倒置计数输出结果为：`12 13`
**4. 格式化输出**
本题考查字符串格式化输出。通过`printf`函数和指定的格式控制符输出特定格式的字符串。
**示例代码**:
```c
char format[] = "%d%c";
printf(format, sizeof(format), "abcdef"[2] + 1);
```
**输出结果**:
- 输出结果为：`5d`
#### 三、数据结构题目解析
**1. 二叉树遍历**
给定中序和后序遍历结果，构造二叉树并给出先序遍历。
- **中序遍历**：6 5 1 2 8 9 4 3 7
- **后序遍历**：6 5 8 2 9 1 7 3 4
**二叉树构造**:
```
4
/ \
1 3
/ \ \
2 5 7
/ \ / \
6 8 9 0
```
**先序遍历**：4 1 2 6 8 5 3 7 9
**2. 散列表构造与分析**
本题考察散列表的构造过程以及散列函数的应用。
- **散列函数**：`H(key) = key MOD 11`
- **处理冲突**：线性探测再散列法
**散列表构造**:
| Index | Key |
|-------|-----|
| 0 | 11 |
| 1 | 2 |
| 2 | 3 |
| 3 | 23 |
| 4 | 19 |
| 5 | 27 |
| 6 | 18 |
| 7 | 7 |
| 8 | 20 |
| 9 | 42 |
| 10 | - |
**填装因子 α**:
- 填装因子计算公式：`α = (填充的槽数) / (总槽数)`
- 结果：`α = 5/11`
**3. Floyd 算法**
Floyd算法用于求解所有顶点对之间的最短路径问题。算法的核心思想是动态规划。
**示例代码**:
```c
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
if (d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
path[i][j] = path[i][k];
}
}
```
**4. 二叉排序树最近公共祖先**
题目要求设计程序找出二叉排序树中两个节点的最近公共祖先。这可以通过递归方式实现。
**示例代码**:
```c
int Ancestor(Tree T, int n, int length[]) {
TreeNode *p = T;
InitStack(S);
push(S, p);
while (!IsEmpty(S)) {
push(S, p);
// 递归逻辑
if (p->data == n) {
// 处理找到节点的情况
int i = 0;
while (!IsEmpty(S)) {
// 按顺序出栈
}
}
}
}
```
以上是对2018年浙江大学878考研专业课试题的相关知识点的详细解析。这些问题涵盖了C语言的基础知识和高级特性、数据结构的基本概念以及算法的设计与实现等多个方面，有助于考生系统地复习和掌握相关知识。
