2024.8.21洛谷SCP-J1错题分析

一、单项选择题

8. 假设有一组字符{g,h,i,j,k,l}，它们对应的频率分别为 8%,14%,17%,20%,23%,18%。
请问以下哪个选项是字符 g,h,i,j,k,l 分别对应的一组哈夫曼编码？ （C）

C. g: 111, h: 110, i: 101, l: 100, k: 01, j: 00

分析：哈夫曼编码的定义不记得了。

哈夫曼编码：（重点：不为任意其他编码前缀；最短）

给定一串字符串，每种字符出现次数不同，将这串字符串编码成一个二进制数。
若把每个字符用相同长度二进制数编码，简单实用，但不节省空间；可以使用变长编码，频数高的字符用短码表示，频数低的用长码表示。
编码方案不能使某个编码是另一编码的前缀，两个编码又包含关系，就不能进行唯一的解码还原。
哈夫曼编码是前缀编码的一种最优算法。

15. 考虑右图所示的无向图，度最大的结点为（6）号结点。
边为：32,36,34,45,46,56,51,61
度：1：2,2：3,3：1,4：3，5：3，6：4
所以节点6的度最大

二、阅读程序

2.此程序输入一个长度为N的数组，给定k,将a[i]与a[i-k]进行多次比较交换，输出交换后的数组并统计交换次数。

1)在题目限制的输入规模下，counter（即交换次数，int） 可能会溢出。（T）

限制规模为1e5，极端情况（即k=1，正序排列）要交换5e9次，会溢出。

2)该程序的时间复杂度为（O(n^2/k)）。

k=1时，时间复杂度为n^2，k越大,需要的交换次数越少，因此为O(n^2/k)

3.此程序进行bfs搜索从1号点到n+1号点的距离，不可到达则输出“sorry”。

32. 当输入的 n 为偶数，且 r=l+1 时，m 至少为（ n / 2）时输出不为 sorry。

共有偶数个点，n与n+1+1号点间连边，则至少需要连n/2条边。

三、完善程序

2.

1) ③处应填（break）

这是一个质数筛，筛出1~n间的所有质数。

void linear_prime(int n) {
    --n;
    not_prime[0] = not_prime[1] = true;
    for(int i = 2; i <= n; i++) {
        if(not_prime[i] == false) prime[++cnt]=i;//1-
        for(int j = 1; (j <= cnt) && (i * prime[j] <= n); j++){//2-
            not_prime[i * prime[j]] = 1;
            if(i % prime[j] == 0) ③;
        }
    }
}

在1-行，程序将没有被打上非质数标记的i标为下一个质数
在2-行之后，这个质数筛将每一个范围内prime[j]的倍数打上标记，直至超出范围或i即为prime[j]，所以此时应跳出。