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

1. 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(n²) and O(2ⁿ). Justify your answer.

                                                                 (7 points)
   
   

2. A train is presented as a double-linked list. The locomotive and the cars are Strings. Program the class Train with the operations:
   • public Train(String locomotive)
     creates a train consisting of only the locomotive
   • public void addBehind(String car)
     adds a car at the back of the train
   • public Train add(Train another)
     adds another train's cars at the back of the train; the string of cars are detached from another locomotive; the method returns the extended train; the locomotive from the other train is not included
   • public Train detachRear(int carNo, String locomotive)
     starting from carNo number car, detaches the rear end cars of the train, and they become a separate train for whose locomotive is given as parameter; the method returns the train detached from the rear with its locomotive; the original train also changes
   • public int which(String car, int fromWhere)
     returns the order number of the first train car, when the search is begun from the car whose order number is given as parameter; the cars are numbered starting from one.
   • public int length()
     the number of cars in the train
   • public String toString()
     creates the train's string representation

   Specify the behaviour of the methods, in error situations, as well, and implement the class Train.

   With the help of the class Train, create the separate class Tools with library functions for the foreman of a railway station. The class Tools should contain the following tools.

   • count the number of cars by the given name in the train (eg. "sleeping car")
   • delete the cars with the given name from the train (eg. "container")
   • switch the order of the cars to the opposite (for the 'return journey'... :-)
   Please note! The tools must be implemented only with the help of the public methods listed above.

                                                                 (7 points)
   
   

3. Specify a list, a stack and a queue as an abstract data type (ADT).

                                                                 (4 points)
   
   
   

4. 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).
   • public int oldestAncestor() returns the length of the longest path in the tree from 'me' to an ancestor.
   • public String relation(String ancestor) returns the relation between 'me' and the given ancestor in the form "mother's father's father's mother's father's mother's mother". You may assume that the persons in the tree have unique names.
   • public void printOldestBirthGiver() prints the name of the ancestor who has given birth at the oldest age. If this person is not unique, they are all printed.

                                                                 (7 points)