假设给定数组 p[1......N] 和 q[1......N] 均未初始化，即每个位置可能包含任意值），

Question

假设给定数组p[1......N]和q[1......N]都未初始化，即每个位置可能包含任意值）和一个全局变量count，初始化为0。考虑下面的程序set and 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;
}

一个。假设我们进行以下调用序列：

 set(7); set(3); set(9);

在这一系列调用之后，count的值是多少，q[1]、q[2]、q[3]、p[7]、p[3]和p[9]的作用是什么包含？

乙。完成以下语句 "The first count elements of __________contain values i such that set (_________________) has been called".

C.表明如果没有为某些 i 调用 set(i)，那么无论 p[i] 包含什么，is_set(i) 都会 return 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),... n 次。

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

然后你调用 is_set(i)，i 不同于所有 i_n。首先你访问 p[i] 仍然包含一个任意值 v.

if v <= 0 or v > count, is_set(i) return false
否则 (1 <= v <= count) 我们检查之前用 i_v 赋值的 q[v]。又因为i不同于all all i_n，i不同于i_v，因此 is_set(i) returns false 也是

Answer 2

（注意，因为这个问题被标记为 C：这个答案假设 p 和 q 的元素表现得好像它们具有固定但在执行开始时未知的值。C标准不提供此保证；它允许未初始化的对象在每次使用时表现得好像它具有不同的值。）

考虑一个呼叫 is_set(i)，之前没有 set(i)。假设 is_set(i) return 为真。然后 p[i] ≤ 0 or p[i] > count 必须评估为 false（或者 return false 将被执行），因此 p[i] 有一些值 c 是 count 在之前的一些值调用 set(x)（尽管 p[i] 可能由于其初始化状态而具有此值，而不是由于调用 set(x)）。

调用 set(x) 将 q[c] 设置为 x。因此 q[p[i]] 计算为 q[c]，然后计算为 x，所以 q[p[i]] ≠ i 是 x ≠ i，这是真的，因为之前有一个 set(x) 调用但是根据我们的前提，不是之前的 set(i) 调用。这会导致 return false 被执行。这与我们的假设相矛盾 is_set(i) return 是正确的，因此假设是错误的。

is_set(i) 不能 return 当没有之前的 set(i) 调用时为真。

Answer 3

p[i] 是一些任意值，称它为 x。

如果 x <= 0 或 > 计数，则 is_set 的第一个 "if" 触发，结果为 false。

否则，当 count 开始等于 x - 1 时，会调用 set() 。此时将 y 设为 set() 的参数。那么 q[x] 等于 y。但是我们知道没有用参数 i 调用 set()，所以 y != i。因此 q[x] != i。但是 x 是 p[i]，所以 q[p[i]] != i 和第二个 if 触发器和 returns false.

假设给定数组 p[1......N] 和 q[1......N] 均未初始化，即每个位置可能包含任意值），

Suppose you are given arrays p[1......N] and q[1......N] both uninitialized, that is, each location may contain an arbitrary value),

c

arrays

pseudocode