CSE 428: Exercises on abstract data types and
The superscript "(d)" stands for "difficult".
Exercises similar to those marked with "(d)"
might appear in
candidacy exams, but not in the standard exams of CSE 428.
The superscript "(s)" stands for "solution
You can find the solution of these exercises
Consider the implementation of the ADT "simple list"
seen in Lecture 10 (CSE 428 Spring 99, see
Assume that the data are somehow protected, so that it is
possible to access to lists only via the operations of the ADT.
- Is it possible to create "circular lists", i.e. lists in which
it is possible, following the links from an element, to come back to the
- Is it possible to create "shared lists", i.e.
lists which have a part in common?
- Is it possible that an operation done on a list affects
Suppose that the above implementation of "simple lists"
is done in a language like Pascal Standard or C, which do not
offer a mechanism for data protection.
- Would the creation of
circular lists, shared lists and side effects be possible?
- Would it be possible to create lists with multiple links
in their elements,
for instance tree-like structures or two-dimentional structures?
Describe briefly the advantages of having a mechanism for data protection.
What are the mechanism offered in Modula 2 and in C++
for data protection?