資料結構›Ch8 雜湊
第 26 題/共 37 題
◀ DS 26/37
26. Bloom Filter、程式維護
#DS-08-026易Bloom Filter程式維護
題組題幹(本題:(d),共 4 小題)點擊展開

A firewall uses a fast pre-check before running an exact check. All input integers are non-negative. You must answer Questions 1-4 based on the program below.

static inline uint32_t f1(int x) { return (uint32_t)(x % 8); }
static inline uint32_t f2(int x) { return (uint32_t)((x / 2) % 8); }
static inline void set1(uint32_t *b, uint32_t p) { *b |= (1u << p); }
static inline int get1(uint32_t b, uint32_t p) { return (b >> p) & 1u; }
static int precheck(uint32_t bits, int x) {
    return get1(bits, f1(x)) && get1(bits, f2(x));
}
static int exact_check(int x) {
    return (x == 10) || (x == 22);
}
int main(void) {
    int base[] = {10, 22};
    uint32_t bits = 0;
    for (int i = 0; i < (int)(sizeof(base)/sizeof(base[0])); i++) {
        set1(&bits, f1(base[i]));
        set1(&bits, f2(base[i]));
    }
    int n;
    scanf("%d", &n);
    int exact_checks = 0, blocked = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        if (precheck(bits, x)) {
            exact_checks++;
            if (exact_check(x)) blocked++;
        }
    }
    printf("%d %d\n", exact_checks, blocked);
    return 0;
}

[3%] Assume the blacklist policy of the firewall changes and the blacklist becomes {10, 14, 22}. To correctly apply the new policy, which parts of the program must be updated?

📄 成大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch8 雜湊
本章題號 · 21–37 / 37