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:
    type pointer = ^node_type;
      node_type = record
          info : char;
          next : pointer
        end;
    
    What is the the time analysis for this process in big Oh notation?

  2. You are given a pointer T of type Tree to a tree. Write a recursive procedure called delete that deletes all the nodes of a tree. Use the following type definition:
    type
      pointer = ^Tree;
      Tree =  record
          info : integer;
          left, right : pointer
        end;
    
    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 procedure reheap( tree, left, right : pointer );
    type
      pointer = ^heap;
      heap =  record
          info : integer;
          left, right : pointer
        end;
    
    What is the time analysis of this procedure in big Oh notation?

  4. Write a procedure called insert that inserts the balancefactor in each node of a tree. The balance factor is obtained by subtracting the height of the left part of the tree from the height of the right side.
    type
      pointer = ^Tree;
      Tree =  record
          balance, info : integer;
          left, right : pointer
        end;
    
    What is the time analysis of this procedure in big Oh notation for your algorithm?