Q15

MCQMarks unknown

Suppose you are given arrays $p [1......N]$ and $q [1......N]$ both uninitialized, that is, each location may contain an arbitrary value), and a variable count, initialized to $0$ . Consider the following procedures $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; }

(A)

Suppose we make the following sequence of calls: $set(7)$ ; $set(3)$ ; $set(9)$ ; After these sequence of calls, what is the value of count, and what do $q[1], q[2] ,q[3], p[7], p[3]$ and $p[9]$ contain?

(B)

Complete the following statement "The first count elements of __________contain values i such that set (_________________) has been called".

(C)

Show that if $set(i)$ has not been called for some $i$ , then regardless of what $p[i]$ contains, $is\_set(i)$ will return false.

Loading…