进化史
0%

2020冬PAT甲级考试总结

发表于

学了两个月的数据结构，今天（2020/12/05）参加PAT测试了一下。这里做下总结。

前段时间集中在学习Java，本来打算用Java来做题的（正好也练练Java的语法），结果看别人的攻略发现PAT系统上并不推荐Java，因为每道题时间卡的比较紧，光一个Scanner在某些数据量较大的测试点就可能会导致超时。所以考前手忙脚乱的又复习了一遍C，到考试时还是出了不少乱子。

第一题 最近的斐波那契数

这道题比较简单，给定一个数，输出离它最近的斐波那契数。

实际上就是求斐波那契数列了，做了很多遍的题目，说是动态规划的思想，但应该也是最简单的那一类了。之前看攻略，有人说第一道的20分的题目很多都是取巧的数学题，没有思路容易卡很久，可以先不做。我一开就看都没看，直接放下了。结果其实这道题是最简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <math.h>

int main()
{
    int N;
    scanf("%d", &N);


    int a = 0;
    int fib = a;
    int diff = abs(N - fib);
    int res = fib;

    int b = 1;
    fib = b;
    if (abs(N - fib) < diff)
    {
        res = fib;
        diff = abs(N - fib);
    }

    while (1)
    {
        fib = a + b;
        if (abs(N - fib) < diff)
        {
            res = fib;
            diff = abs(N - fib);
        }

        if (fib > N)
        {
            break;
        }

        a = b;
        b = fib;
    }

    printf("%d", res);

    return 0;
}

第二题 最短的连续子串

给定一个长字符串S，然后给一个由长字符串元素组成的小字符串P，要求S中包含P的最短连续子串。

这题实际上也挺简单的，没有什么特别的算法或是数据结构的考察点，主要是字符串的操作。很不幸的是我把C语言的字符串处理的函数忘的差不多了，有点尴尬，最后还在现场手写了求字符串长度的函数。字符串的输入输出也不熟练，现场也调试了好久。花费了大量的时间。这里一定要记住教训吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <string.h>

#define MAXSIZE 10001

int len(char S[]) // 现场手写求字符串长度的函数，尴尬
{
    int i = 0;
    while (S[i] != '\0')
    {
        i++;
    }

    return i;
}


int main()
{
    char S[MAXSIZE];
    scanf("%s", &S);

    char P[MAXSIZE];
    scanf("%s", &P);

    int i, j, k;
    int front = 0, rear = 0, L = MAXSIZE, F, R;
    int Slen = len(S);
    int Plen = len(P);
    for (i = 0; i < Slen; i++)
    {
        j = 0;
        if (S[i] == P[j]) 
        { // 这题的关键思路就是通过S和P的一一对比找到所有的符合要求的子串，
          // 然后记录每个子串的长度和下标，最后比较找到最小的子串即可
            front = i;;
            j++;

            for (k = front + 1; k < Slen; k++)
                {
                    if (S[k] == P[j])
                    {
                        j++;
                    }
                    if (j == Plen)
                    {
                        rear = k;
                        break;
                    }
                }
            if (j == Plen)
            {
                if (rear - front < L)
                {
                    F = front;
                    R = rear;
                    L = rear - front;
                }
            }
        }
        
    }

    for (i = F; i <= R; i++)
    {
        printf("%c", S[i]);
    }

    return 0;
}

第三题 输出文件的路径

输入一个文档树结构，以缩进空格的数量表示文件夹的层级，最后要对任意一个指定的文件夹，输出从根目录到它的路径。

这题要稍微动点脑筋。但是我还是先被拦在了字符串处理的这里。在输入一行字符串和处理空格的数量这里花费了大量的调试时间。排除了字符串处理的因素之后，后面思路有了其实相对就简单很多了。首先是开一个结构化数组，每个数组元素存3个数据，本身的文件层级，上级目录，本身的目录名。文件夹层级由每行文件名前面的空格数量得到。上级目录由从下往上遍历已有的数组，找到第一个上层文件夹得到（输入保证是按顺序非矛盾的），本身的目录名就是一个简单的字符串转数字。根据输入构建好一个这样的数组后，对需要查询的目录名，遍历数组得到其位置（可以考虑优化优化），然后递归查找其上层目录直到根目录，把路径存储在一个数组里，最后按照要求输出即可。实际考试中，时间比较紧，这里代码比较乱，很多循环指针重复使用了，先将就看看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <math.h>
#define MAXSIZE 1010

struct SNode
{
    int Root;
    int Level;
    int Name;
};
typedef struct SNode Set;


int main()
{
    int N;
    scanf("%d\n", &N);

    Set file[N];
    char path[MAXSIZE];
    int i, j, k;
    for (i = 0; i < N; i++)
    {
        gets(path);
        j = 0;
        while (path[j] == ' ')
        {
            j++;
        }

        file[i].Level = j;
        
        for (k = i - 1; k >= 0; k--)
        {
            if (file[k].Level == file[i].Level - 1)
            {
                file[i].Root = k;
                break;
            }
        }

        if (k == -1)
        {
            file[i].Root = k;
        }

        file[i].Name = 0;
        for (k = 3; k >= 0; k--)
        {
            file[i].Name += pow(10, k) * (path[j] - '0');
            j++;
        }
    }

    int K, r;
    scanf("%d", &K);
    int id;
    int id_path[MAXSIZE];

    for (i = 0; i < K; i++)
    {
        scanf("%d", &id);
        for (j = 0; j < N; j++)
        {
            if (file[j].Name == id)
            {
                id_path[file[j].Level] = file[j].Name;
                r = file[j].Root;
                k = file[r].Level;
                while (k != -1)
                {
                    id_path[k] = file[r].Name;
                    r = file[r].Root;
                    k--;
                }

                for (k = 0; k < file[j].Level; k++)
                {
                    printf("%04d->", id_path[k]);
                }
                printf("%04d\n", id_path[file[j].Level]);
                break;
            }
        }

        if (j == N)
        {
            printf("Error: %04d is not found.\n", id);
        }
    }
    
    return 0;
}

最后的测试有两个测试点没过，显示的是栈错误，似乎又不像优化不佳导致大量数据处理的时候超时。可能是中间某部分代码数组越界，因为这两个测试点只有3分，所有后来就没有再仔细debug了。

第四题 化学方程式

前面两题由于字符串处理的不熟练花费了大量的时间，到这里只剩下40分钟。做的时候看了下这题的通过率，只有0.04，心里就咯噔一下担心写不完。结果真的还是，光读题就花了20分钟。这题的表述十分抽象，以化学方程式为引子，但是实际上跟化学反应没啥关系，题目写的太长，要结合样例输出反复揣摩题目要求。

给定一个反应物的集合，给定一个产物的集合，给定已知的可以反应的化学方程式（即左边某几个元素结合可以得到右边），要求按给定的产物顺序，输出仅使用反应物集合中的物质的最小反应方程（当时这个最小没怎么理解，似乎是比较第一个不相同的反应元素的下标？），并且每个反应物只能使用一次。

这题似乎也没有考到标准的数据结构和算法，当时的思路是用一个类似邻接表的结构表示所有的反应方程的集合。对每一个反应产物构建多个链表按照定义的大小顺序存储存在的反应方程。输出时，依次检查每个链表的元素是否存在于反应物集合中，输出最小并将元素标记为已访问，然后处理下一个元素。

总结

  1. Java语言做题，要考虑Java启动时间和Scanner花费的时间。C语言则过于繁琐，很多结构要自己实现。C++最合适，有现成的STL库可以调用，并且时间花费最小。这里是考虑做这种严卡时间的算法考试。
  2. PAT甲级还是比较基础的。自我感觉准备的不好，但每个题也都有思路，然后就是对语言的细节要熟练。
  3. 多练习，多码代码，不可划水，仅理解是不够的，一定要自己写出来。
相关文章