Here are some sample exam type questions. You might also see questions where you are given some Java code and asked to explain the output or result of running the code.

1. Explain why a static method cannot use the non-static attributes of an object using `this`

.

2. What is a singleton?

3. What is the difference between an overloaded method and an overridden method? Can you override an overloaded method?

4. Suppose that you are implementing an immutable class that has a mutable attribute. What must you do to ensure that objects of your class are truly immutable?

5. (too hard for a CSE1030 exam)
When implementing `equals`

you were told to use the
`getClass`

method to check if the two objects being compared
had the same class. Discuss the consequences of using `getClass`

in `equals`

when inheritance is involved.

6. Suppose that you are implementing the group of classes in an
inheritance hierarchy, such as the
`Dog`

hierarchy that we studied. When could the topmost
class (e.g., `Dog`

) be an interface instead of an
abstract class?

7. What is the most important thing to remember when working with static attributes in an inheritance hierarchy?

8. Describe the steps that are taken when trying to prove that a recursive algorithm is correct.

9. What is the purpose of an iterator?

10. What is the solution to the puzzle on Slide 3 from Feb 25?

11. What is the definition of a binary search tree?

12. Why are linked lists and trees considered recursive data structures?

1. What kind of relationship between two classes does inheritance model?

2. Suppose that you have three classes X, Y, and Z, where X is the parent class of Y, and Y is the parent class of Z. Explain what happens when a Z object is created.

3. Suppose that you have two classes X and Y, where X is the parent class
of Y. Suppose that Y overrides a method named `foo`

:

public class Y { // @pre. s begins with the character 'a' public int foo(String s) { // ... }

Give a different and acceptable precondition for `foo`

in class X.

4. Suppose that you have two classes X and Y, where X is the parent class
of Y. Suppose that Y overrides a method named `bar`

:

public class Y { // @return a list of words that start with the string in startsWith public List<String> bar(String startsWith) { // ... }

Give a different and acceptable postcondition for `bar`

in class X.

5. Suppose that you have two classes X and Y, where X is the parent class
of Y. Suppose that Y overrides a method named `baz`

:

public class Y { public void baz() throws Exception { // ... }

Give all of the possible legal signatures plus throw clauses for `baz`

in class X that throw only a single kind of throwable object
(ignoring overloaded versions of `baz`

).

1. Draw the UML class diagram for the dice rolling GUI application
from the Mar 04 lecture:

Your diagram should include the model, view, controller, JLabel,
and JButton classes, plus any other classes that you think are
necessary (do not show any classes related to the image of
the die or any inheritance relationships, however).

1. What is the maximum number of elements that can be held in
a binary search tree of height `m`

? (the height of
a tree is the number of levels of the tree.) Such a tree
is called a full tree.

2. Suppose that you have a full tree. What is an approximate recurrence relation for recursive search of the tree? (see question 4 below if you cannot recall the search algorithm) You can assume that checking the base cases and performing a comparison can be done in one unit of time (or constant time).

3. Solve the recurrence relation from the previous question.

4. The recursive search algorithm for a binary search tree can be stated as follows (the generic type syntax has been removed for simplicity):

boolean contains(E element, Node subtreeRoot) { if (subtreeRoot == null) { return false; } if (element.equals(subtreeRoot.data)) { return true; } boolean result; if (element.compareTo(subtreeRoot.data) < 0) { result = contains(element, subtreeRoot.left); } else { result = contains(element, subtreeRoot.right); } return result; }

(a) Prove that the algorithm terminates.

(b) Prove that the algorithm is correct.

1. Consider the simple linked list implementation that we studied
in this course and Java's `ArrayList`

(which you can
think of as being an array that can grow in size): Which is more
efficient in terms of big-O complexity for the following operations:

- getting an element using an integer index
- inserting an element at the front of the list
- inserting an element at the back of the list
- inserting an element in the middle of the list

2. Describe an algorithm (recursive or otherwise) that searches a linked list for a given value (returns true if the element is in the list, and false otherwise). Your algorithm can use plain English (instead of a programming language).

3. (too hard for a CSE1030 exam) Describe an algorithm for removing an element from a binary search tree. Your algorithm does not need to be efficient but it must preserve the search tree property of the tree.

4. Draw a binary search tree containing 8 unique integers; the root of your tree must have a left and right child. What is the inorder, preorder, and postorder traversals of the tree you have drawn?

5. Explain how to use a stack to check if a sequence of parentheses is correct nested; you only need to consider round brackets ().

6. (From Introduction to Programming in Java, Sedgewick and Wayne)
Suppose that a client performs an intermixed sequence of enqueue
and dequeue operations on a queue. The enqueue operations put the
integers 0 through 9 in order on the queue; the dequeue operations
print out the returned value. Which of the following sequence(s)
could not occur?

a. 0 1 2 3 4 5 6 7 8 9

b. 4 6 8 7 5 3 2 9 0 1

c. 2 5 6 7 4 8 9 3 1 0

d. 4 3 2 1 0 5 6 7 8 9

7. See previous question: Which sequence(s) could have been produced using a stack instead of a queue, and what order of commands must have been given to produce the output? (for the stack, the pop operations print out the returned value)