2nd Midterm v22.0102, April 21, 1997, Sam Marateck

  1. Given a pointer List to a linked list, write a program segment that deletes the last node in the list. Use the following type:
      class Node
      {
          char info;
          Node next;
      }
    
    What is the the time analysis for this process in big Oh notation?

  2. You are given a pointer t of type Node to a tree. Write a recursive procedure called del that deletes all the nodes of a tree. Use the following header private Node del(Node t) and type definition:
    private class Node
    {
        Object info;
        Node left, right;
    }
    
    What is the the time analysis for this process in big Oh notation?

  3. Suppose that you have a complete tree described by the following type defininition, which is in heap form except for the info part of the root. Write a recursive routine that reheapifies it. You may use the heading private void reheap(Node parent, Node L, Node R)
    private class Node
    {
        Object info;
        Node left, right;
    }
    
    What is the time analysis of this procedure in big Oh notation?

  4. Write a procedure called insertBal that inserts the balance factor in each node of a tree in Oh(nlogn). The balance factor is obtained by subtracting the height of the left part of the tree from the height of the right side. The header is: private void insertBal(Node t). Then do this operation in Oh(n) using private int adjust(Node t). Use the following class definition for the tree.
    private class Node
    {
        Object info;
        int balance;
        Node left, right;
    }
    
    What is the time analysis of this procedure in big Oh notation for your algorithm?