SUNY Geneseo, Department of Computer Science

Practice Questions for Hour Exam 2

CSci 141 , Fall 2003

Prof. Doug Baldwin

These are the questions from the second hour exam in my previous offering of CSci 141 (last Spring). As usual, these questions may not be perfects fits with the timing, emphasis, or presentation of material this semester, but they are none the less useful things to practice on as your prepare for our exam. (In particular, question 4 is based on extra material that we had time for last Spring, but that we haven't done this semester.)

I have also prepared Solutions to these questions.

Question 1

Write (pseudocode is fine) a recursive algorithm that tests whether all the items in a list are equal to each other. Your algorithm should be a method of an “ExtendedList” subclass of “List”. It should return True if all the items in the list are equal, and False if not. For example, if run on the list of strings [“dog” [“dog” [“dog” [] ]]], your algorithm would return True, while if run on the list [“dog” [“cat” [“dog” [] ]]], it would return False.

Question 2

Suppose you have a list whose items are numbers. The following algorithm supposedly computes the sum of all the numbers in such a list (the sum of all the numbers in an empty list is defined to be 0):

    // In class NumberList
    sum()
        if this.isEmpty()
            return 0
        else
            return this.first() + this.rest().sum()

Prove that this algorithm really does return the sum of the items in a list.

Question 3

Here are some list sizes and average running times for a list search algorithm:

Are these times consistent with a Theta(n) running time for the search algorithm? Why or why not?

Question 4

Consider lists as data structures built from nodes and links. Suppose you wanted such a list in which each node had a link to both the next node in the list and to the one after that. For example, here is a sketch of such a list with four nodes:

Show (pseudocode is fine) how you would declare a “Node” class for such lists. Assume that nodes contain one data member, of type “Object”. Briefly explain which members in your class are links to other nodes, and how you intend them to be used.