Suppose you are given arrays p[1…..N] and q[1…….N] both uninitialized (that…
PYQ GATE 2000
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 iset:
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.
Sign up free to check your answer
Sign up freeLoading lesson…

