581325-0 Data Structures, 1st intermediate exam March 3 2000/AW

1. Describe exactly and graphically what the function classes O(f(n)) mean, and how they can be used to describe the object time of algorithms. How is the time used by an algorithm determined?

                                                                 (9 points)
   

2. A list is linked in one direction and has no header. A pointer is kept at its beginning and end. The beginning of the list specification is as follows:

      public class List {
   
        private class Element {
          private Comparable data;
          private element link;
        }
   
        private Element start, end;   // beginning and end of list
        private int no;               // number of elements
        ...
   

   Implement the list operations:
   • public boolean add(Comparable element, int place) adds an 'element' after the element at 'place'. Adding to place 0 means adding at the beginning of the list; the method's value is true if the addition succeeds, and false if the place was impossible.
   • public void removeSmall(Comparable value) removes the elements smaller than the 'value' given.
   • public List append(List another) appends another list after the first one; the appended list, 'another,' becomes empty.
   • public List removeEnd(Comparable element) removes the end of the list from the first 'element' on; thus, the original list is shortened; the method's value is that of the removed list; if there is no 'element' the method's value is the empty list.

                                                                 (8 points)
   

3. The specification of a binary tree starts thus:

      public class BinTree {
   
        private class Node {
          Object data;
          Solmu left, right;
        }
   
        private Node root;
   
        public BinTree() {
          root = null;
        }
        ...
   

   Into the class, program the methods:
   • public int height() returns the height of the binary tree
   • private int depth(Node d) returns the depth of the given node
   • public void printLeaves() prints the leaves of the tree from left to right

                                                                 (8 points)