CSE1030Z Sample Exam Questions

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.

Random

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?

Inheritance

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).

GUIs

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).

Recursion

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.

Data Structures

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:

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)