TOC PREV NEXT

Quiz — Data structure design

This quiz gives you practice with choosing from among all the data structures you've worked with so far: sorted arrays, balanced binary search trees, hash tables, heaps, and graphs, all possibly augmented with threads (links between elements).

Readings

Weiss chapters 10 through 14 contain problem-oriented material that is nice background for this quiz. Other material in Weiss that focuses on individual data structures will also be good to review.

Sample questions for the "Data structure design" quiz

  1. Describe the implementation of a generalized vector class called GenVector that, like Vector, associates integer indexes with contents values but, unlike Vector, does not require that the index values be consecutive. Your implementation should allow fast execution of the following operations for large subscript sets:
It should also not use an extravagant amount of memory when the subscript set is small.
Along with the implementation, you should describe how the three given operations are executed and give a big-Oh expression for their running time. These descriptions should be in terms suitable for another CS 47B student to understand how they would be translated into code.
  1. Suppose that an additional operation is to be supported by GenVector objects:
    • Enumeration elements (int rangeBegin, int rangeEnd)
      initializes an enumeration of elements whose indexes are between rangeBegin and rangeEnd, inclusive, in increasing index value. The initialization of the enumeration must be executed in at most log N time, where N is the number of key-value associations in the GenVector; each call to nextElement are to be executed in constant time, and the operations listed for exercise 1 are still to be executed as quickly as possible.
Modify your implementation of exercise 1 to accommodate this new requirement. As in exercise 1, describe your modified implementation and how the required operations are executed, and give runtime estimations for all operations.

Answers to sample questions for the "Data structure design" quiz

  1. A hash table (assuming a reasonable hash function) works fine for this application. In Java, you would need to convert integer index values to Integer objects, then use java.util.HashTable. 
	Object elementAt (int k) {
		return get (new Integer(k));
	}
	
	void setElementAt (int k, Object value) {
		put (new Integer(k), value);
	}
	
	boolean isLegalIndex (int k){
		return get (new Integer(k)) != null;
	}
All these operations will execute in constant time on the average.
  1. A hash table does not provide fast enough access to entries whose keys lie in a specified range. Thus a different structure is necessary. If all the keys were known in advance, an array of key-value pairs sorted by key would work. However, the setElementAt operation, which may add new associations, requires a dynamic structure. A balanced binary search tree, ordered by key value, makes the operations of exercise 1 and the enumeration initialization all execute in log N time, where N is the number of key-value associations.
To achieve constant time for each call to nextElement, the tree entries must be threaded, i.e. each tree node must be linked to its inorder successor. That requires a more complicated insertion operation that keeps track of the current node's inorder successor as it goes down the tree. Going down the right subtree uses the same inorder successor; going down a left subtree, the root is the inorder successor. Insertion is still O(log N) with this extra processing, however.
TOC PREV NEXT