資料結構›Ch8 雜湊
第 25 題/共 37 題
◀ DS 25/37
25. Bloom Filter、False Positive
#DS-08-025易Bloom FilterFalse Positive
題組題幹(本題:(c),共 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%] For the current program (base = {10, 22}), what is the smallest integer x such that precheck(bits, x) returns 1 and exact_check(x) returns 0?

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