【数据结构】在线测试1

三道题相对都比较水，T1 和 T2 一遍过，T3 wa 了一发，错的特别蠢。

T1 (20 分)#

删除在 (minD, maxD) 范围内的数。可以双指针做，用 i 遍历数组，j 表示当前该覆盖的位置，因为只可能往前挪动，在一个数组中操作不会冲突。

1
List Delete(List L, ElementType minD, ElementType maxD) {
2
    int i, j;
3
    for (i = 0, j = 0; i <= L->Last; ++i) {
4
        if (L->Data[i] >= maxD || L->Data[i] <= minD) {
5
            L->Data[j++] = L->Data[i];
6
        }
7
    }
8
    L->Last = j - 1;
9
    return L;
10
}

T2 (30 分)#

需要实现

链表查找第一个大于 val 的数，并在前面插入 val；
链表翻转。

很简单的模拟，注意边界别挂就好。

1
void Insert(List L, ElementType val) {
2
    List pre = L;
3
    L = L->Next;
4
    while (L && L->Data < val) pre = L, L = L->Next;
5
    List cur = (List)malloc(sizeof(struct LNode));
6
    cur->Data = val;
7
    cur->Next = pre->Next;
8
    pre->Next = cur;
9
}
10

11
void Reverse(List L) {
12
    List p = L->Next, pre = NULL, tmp = NULL;
13
    while (p) {
14
        tmp = p->Next;
15
        p->Next = pre;
16
        pre = p;
17
        p = tmp;
18
    }
19
    L->Next = pre;
20
}

T3 (20 分)#

计算 n 以内的所有 Fibonacci 数，并统计递归暴力计算一个 Fibonacci 数过程中，每个下标经过的次数。

实话说，这拓展题比前面的简单，因为 Fibonacci 数增长是指数级的，在限制 c 语言并且不取模的情况下数据量大概在三四十，直接暴力统计就能做。

~~没把数据拉到 1e6 再加个模 998244353 不是很认可~~

1
#include <stdio.h>
2
#define N 100
3

4
int f[N];
5

6
void work(int n) {
7
    f[n]++;
8
    if (n == 1 || n == 0) return;
9
    else work(n - 1), work(n - 2);
10
}
11

12
int main() {
13
    int n;
14
    scanf("%d", &n);
15
    work(n);
16
    int a = 0, b = 0, c;
17
    for (int i = 0; i <= n; ++i) {
18
        if (i >= 2) {
19
            c = a + b;
20
            a = b;
21
            b = c;
22
        }
23
        printf("Fib(%d)=%d,spn=%d\n", i, i == 0 ? 0 : b, f[i]);
24
    }
25
    return 0;
26
}

Star's Blog

T1 (20 分)#

T2 (30 分)#

T3 (20 分)#