假设您给数组p [1…N]和q [1…N]都未初始化，也就是说，每个位置都可以包含任意值），

Question

假设给定的数组p [1 ...... N]和q [1 ...... N]都未初始化，也就是说，每个位置都可以包含任意值）和变量计数，初始化为0。请考虑以下过程set和is_set：

 set(i) { 
        count = count + 1; 
        q[count] = i; 
        p[i] = count; 
    } 
    is_set(i) {
        if (p[i] ≤ 0 or p[i] > count)
            return false; 
        if (q[p[i]] ≠ i)
            return false;
        return true;
    }

A。假设我们进行以下调用序列：set（7）; set（3）; set（9）;在这些调用序列之后，count的值是什么，q [1]，q [2]，q [3]，p [7]，p [3]和p [9]包含什么？

B。完成以下语句“ __________的第一个计数元素包含已调用set（_________________）的值”。

C。表明如果尚未为某些i调用set（i），则无论p [i]包含什么，is_set（i）都将返回false。

我求解了A部分和B部分，即q [1] = 7 q [2] = 3 q [3] = 9 p [7] = 1 p [3] = 2 p [9] = 3，B将是q的第一个计数元素包含值i，从而已调用set（i）。

我对选项C感到困惑，有人可以帮助我将其可视化有点棘手。

Answer 1

假设您呼叫过set(i_1)，set(i_2)，...次。

现在您有count == n和q[1] == i_1，q[2] == i_2，...，q[count] == i_ count。

然后您以与所有is_set(i) n]不同的i调用i_。首先，您访问p[i]，它仍然包含任意值v。

1. 如果v <= 0或v > count，is_set(i)返回false
2. 否则（1 <= v <=计数），我们检查之前用q[v] v
分配的i_。并且由于i与所有所有i_ n不同，所以i与i_ v不同，因此is_set(i)也返回false