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 free

Explore the full course: Zero To Hero

Loading lesson…