Show the data structure that results and the answers returned by the FIND-SET op

Question

Show the data structure that results and the answers returned by the FIND-SET operations in the following program. Use the linked-list representation with the weighted-union heuristic.
1 for i ? 1 to 16
2 do MAKE-SET(xi)
3 for i ? 1 to 15 by 2
4 do UNION(xi, xi+1)
5 for i ? 1 to 13 by 4
6 do UNION(xi, xi+2)
7 UNION(x1, x5)
8 UNION(x11, x13)
9 UNION(x1, x10)
10 FIND-SET(x2)
11 FIND-SET(x9)
Assume that if the sets containing xi and xj have the same size, then the operation UNION(xi, xj) appends xj's list onto xi's list.

Explanation / Answer

At the end of the execution, there is only one set which contains all elements {x1, x2, ...x16}. In this set, for each i, xi is linked to xi+1. The set’s representative is x1. So both of the two FIND-SET operations return the pointer to x1.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.