【数据结构】C语言测试题

📢 Annoucnement#

这场不计分，如果计分会在结束后发博客，如果题目太多会开个仓库发。
因为题比较多，每道题都比较简单，所以只大概说说思路。

另外说一下感受吧，我感觉虽然一直训练，但是感觉遇到瓶颈了，越打越乏力，想切几道水题释放释放压力，十道题竟然做了一个多小时，属实不应该。这套题非常基础，如果有一定的底子应该是可以直接秒的。很多题数据范围不给，让用户猜。

函数题#

长整数转化成16进制字符串#

开一个栈先从低位到高位存一下，然后不断取栈顶存到 p 里面就行。

1
void f( long int x, char *p ) {
2
    if (x == 0) {
3
        p[0] = 48, p[1] = 0;
4
        return;
5
    }
6
    int l = 0;
7
    if (x < 0) p[l++] = '-', x = -x;
8
    char tt[34] = {0};
9
    int len = 0;
10
    while (x) {
11
        int t = x % 16;
12
        char c;
13
        if (t < 10) c = t + 48;
14
        else c = t - 10 + 'A';
15
        tt[len++] = c;
16
        x /= 16;
17
    }
18
    for (int i = len - 1; i >= 0; --i) p[l++] = tt[i];
19
    p[l] = 0;
20
}

数组循环右移#

开个临时数组存一下右移之后的结果，然后复制回来，注意 m 可能大于 n，最好先取个模。

1
void ArrayShift( int a[], int n, int m ) {
2
    m %= n;
3
    int b[MAXN], i;
4
    for (i = 0; i < n - m; ++i) {
5
        b[i + m] = a[i];
6
    }
7
    for (i = 0; i < m; ++i) {
8
        b[i] = a[i + n - m];
9
    }
10
    for (i = 0; i < n; ++i) {
11
        a[i] = b[i];
12
    }
13
}

有序表的增删改查操作#

除了二分，上课都讲了，需要灵活应用一下，二分记一下板子就行，我这里二分写挂一次。

1
int lower_bound(int a[], int value) {
2
    int l = 0, r = Count;
3
    while (l < r) {
4
        int mid = l + r >> 1;
5
        if (a[mid] >= value) r = mid;
6
        else l = mid + 1;
7
    }
8
    return l;
9
}
10

11
int insert(int a[ ], int value) {
12
    int p = lower_bound(a, value);
13
    if (a[p] == value) return -1;
14
    for (int i = Count; i > p; --i) {
15
        a[i] = a[i - 1];
16
    }
17
    a[p] = value;
18
    Count++;
19
    return 0;
20
}
21

22
int del(int a[ ], int value) {
23
    int p = lower_bound(a, value);
24
    if (a[p] != value) return -1;
25
    for (int i = p; i < Count - 1; ++i) {
26
        a[i] = a[i + 1];
27
    }
28
    Count--;
29
    return 0;
30
}
31

32
int modify(int a[ ], int value1, int value2) {
33
    if (a[lower_bound(a, value1)] != value1 || a[lower_bound(a, value2)] == value2) return -1;
34
    del(a, value1), insert(a, value2);
35
    return 0;
36
}
37

38
int query(int a[ ], int value) {
39
    int p = lower_bound(a, value);
40
    if (a[p] != value) return -1;
41
    else return p;
42
}

建立学生信息链表#

按要求模拟即可。

1
void input() {
2
    int num, score;
3
    char name[20];
4
    while (scanf("%d%s%d", &num, name, &score), num) {
5
        struct stud_node *cur = malloc(sizeof(struct stud_node));
6
        cur->num = num, cur->score = score;
7
        strcpy(cur->name, name);
8
        if (!head) head = cur;
9
        else tail->next = cur;
10
        tail = cur;
11
    }
12
}

链表逆置#

开个变量存一下前驱，顺着遍历一遍，依次把 next 指向前驱。

1
struct ListNode *reverse( struct ListNode *head ) {
2
    struct ListNode *pre = NULL;
3
    while (head) {
4
        // printf("%p ", head);
5
        struct ListNode *tmp = head->next;
6
        head->next = pre;
7
        pre = head;
8
        head = tmp;
9
    }
10
    return pre;
11
}

求自定类型元素序列的中位数#

数据量有点大，不能直接暴力，因为他限制 c 语言，只能自己写一个 $n\log n$ 的排序了，我感觉归并排序好写，就写的归并排序。

1
ElementType b[MAXN];
2

3
void msort(ElementType a[], ElementType b[], int l, int r) {
4
    if (l == r) return;
5
    int mid = l + r >> 1;
6
    msort(a, b, l, mid), msort(a, b, mid + 1, r);
7
    int h = l, h1 = l, h2 = mid + 1;
8
    while (h1 <= mid && h2 <= r) {
9
        if (a[h1] <= a[h2]) b[h++] = a[h1++];
10
        else b[h++] = a[h2++];
11
    }
12
    while (h1 <= mid) b[h++] = a[h1++];
13
    while (h2 <= r) b[h++] = a[h2++];
14
    for (int i = l; i <= r; ++i) a[i] = b[i];
15
}
16

17
ElementType Median( ElementType A[], int N ) {
18
    msort(A, b, 0, N - 1);
19
    return A[N / 2];
20
}

使用函数输出一个整数的逆序数#

参考第一道的思路，甚至比第一道还简单，不用转进制，不断取最后一位加到结果的最后一位即可。

1
int reverse( int number ) {
2
    int res = 0;
3
    while (number) {
4
        res = res * 10 + number % 10;
5
        number /= 10;
6
    }
7
    return res;
8
}

编程题#

素数对猜想#

如果不会筛法，暴力判素数 $O(n\sqrt{n})$ 理论能过，我代码用的线筛。

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

4
int v[N], prime[N], l;
5

6
int main() {
7
    int n, res = 0;
8
    scanf("%d", &n);
9
    for (int i = 2; i <= n; ++i) {
10
        if (v[i] == 0) {
11
            v[i] = i;
12
            if (i - prime[l] == 2) res++;
13
            prime[++l] = i;
14
        }
15
        for (int j = 1; j <= l; ++j) {
16
            if (prime[j] > v[i] || prime[j] > n / i) break;
17
            v[i * prime[j]] = prime[j];
18
        }
19
    }
20
    printf("%d\n", res - 1);
21
    return 0;
22
}

数列求和-加强版#

答案非常大，需要高精，但是这道题比较特殊，可以先认为，从低到高第 i 位（从 0 计数）为 a * (n - i)，然后模拟一下进位，逆序输出。

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

4
int res[N];
5

6
int main() {
7
    int a, n;
8
    scanf("%d%d", &a, &n);
9
    for (int i = 0; i < n; ++i) {
10
        res[i] = a * (n - i);
11
    }
12
    for (int i = 0; i < n * 2; ++i) {
13
        res[i + 1] += res[i] / 10;
14
        res[i] %= 10;
15
    }
16
    int f = 0;
17
    for (int i = n * 2; i >= 0; --i) {
18
        if (res[i]) f = 1;
19
        if (f) putchar(res[i] + 48);
20
    }
21
    if (!f) putchar(48);
22
    putchar('\n');
23
    return 0;
24
}

乘法口诀数列#

按要求模拟即可，但是要注意，行末不能输出空格，会格式错误。

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

4
int a[N];
5

6
int main() {
7
    int n;
8
    scanf("%d%d%d", &a[1], &a[2], &n);
9
    for (int i = 1, j = 2; j <= n; ++i) {
10
        int t = a[i] * a[i + 1];
11
        if (t < 10) a[++j] = t;
12
        else a[++j] = t / 10, a[++j] = t % 10;
13
    }
14
    for (int i = 1; i <= n; ++i) {
15
        if (i == 1) printf("%d", a[i]);
16
        else printf(" %d", a[i]);
17
    }
18
    return 0;
19
}

Star's Blog