Helsingin yliopisto / Tietojenkäsittelytieteen laitos / Tietorakenteet / Copyright © 2002 Arto Wikla.

581325-0 Data Structures, 1. Course Examination 11.3.2002/AW

Write the name of the course, the date of the exam, and your name, personal number and signature on each paper. Write each answer on a separate sheet of paper!
  1. An array of Objects that has "variable size" would sometimes be a handy tool for programmers. Let us make one! We define the class Vector as the following operations: (this comes from JavaTM 2 Platform Std. Ed. v1.3 ) (Do not program all of these!)

    1. public Vector(): Constructs an empty vector.
    2. public int size(): Returns the number of components in this vector.
    3. public boolean isEmpty(): Tests if this vector has no components.

    4. public int indexOf(Object elem): Searches for the first occurence of the given argument, testing for equality using the equals method.
    5. public int lastIndexOf(Object elem): Returns the index of the last occurrence of the specified object in this vector.

    6. public Object get(int index): Returns the element at the specified position in this Vector.
    7. public Object set(int index, Object element): Replaces the element at the specified position in this Vector with the specified element.

    8. public boolean add(Object o): Appends the specified element to the end of this Vector.
    9. public boolean remove(Object o): Removes the first occurrence of the specified element in this Vector If the Vector does not contain the element, it is unchanged.
    10. public void add(int index, Object element): Inserts the specified element at the specified position in this Vector. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
    11. public Object remove(int index): Removes the element at the specified position in this Vector. Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the Vector.
    1. Design the implementation of class Vector so that the components are kept sequentially in an array and implement the operations 1, 2, 4, 7, 9 and 10. If the default array (let us say 10 elements) becomes too small, it is replaced by a bigger one. Try to program effective implementations.
    2. Design the implementation of class Vector as a linked list and implement the operations 1, 2, 5, 6, 8 and 11. Try to program effective implementations.
    3. List the O-classes of all the operations 4-11 in both of the implementations. If some operation is very effective, give the reasons. (This means that, if you have invented some very clever implementation, you must take care that your solution is understood.) 
                                                                  (8 points)

  2. Explain exactly and with examples how O(f(n)) is defined and how it can be used when mapping out the execution time of algorithms. Give examples of algorithms that belong to O(1), O(log n), O(n), O(n2) and O(2n). Justify your answer. 
                                                                  (8 points)

  3. A binary tree represents a family tree, where the root is 'me'. The subtrees of the root are 'mother', 'father' etc. The specification of the tree starts as follows. 
      class Relative {
    String name;
    int yearOfBirth;
    Relative mother, father;
  }

  public class FamilyTree {

     private Relative root;

     public FamilyTree() {
       root = null;
     }
     ...
    Program the methods for the class (specify their function in error situations, as well). 

                                                                  (8 points)