Sample Final for Introduction to Computer Science II

  1. Write a procedure that copies a linked list pointed to by List1 to another pointed to by List2 such that the nodes in the copied list are in the reverse order to those in the original list. You may assume that an object stack exists with the following methods: push(x) , a procedure, and the functions pop, full , and empty . The nodes of the list are defined by:

    type
      pointer = ^node;
      node = record
          info : integer;
          next : pointer
        end;
    
  2. (a) Write a procedure called check that checks whether a tree is a BST , (binary search tree). The pointers to the nodes are defined by:

    type
      pointer = ^node;
      node = record
          info : integer;
          right, left : pointer
        end;
    
    Use the following heading: procedure check(T : pointer; var valid : boolean);

    (b)What is the time analysis for this process?

  3. (a) procedure Correct , shown below, is used to set the balance field for each node of a tree. This field is defined as the difference of the heights of the left and right subtrees for each node. Express the time analysis of this algorithm for a full tree of 15 nodes as a sum of the contributions of each generation. How does each generation's contribution compare approximately for large N? What is the time analysis in big Oh notation for this algorithm for a bushy tree of N nodes.

    FUNCTION Height(T : pointer) :integer;
    {pre: A tree exists and T originally points to the root.
     post: the function returns the height of the tree. 
    FUNCTION Max(A, B:integer):integer;
    begin
         if A > B then Max:= A
         else Max:= B
    end (* Max *);
    begin  (* Height *)
         if T = NIL then Height:= -1
         else Height:= 1 + Max(Height(T^.Left), Height(T^.Right))
    end (* Height *);
    
    procedure correct(T : pointer);
    {pre: a binary tree with a node definition that includes a balance field.
     post: the balance field for each node is assigned. 
     begin
        if T <> nil then begin
           correct(T^.left);
           T^.balance := height(T^.left) - height(T^.right);
           correct(T^.right)
        end
    end;
    
    (b)What is the time analysis for this algorithm for a BST formed from a list of sorted numbers. (c) Rewrite function height as a procedure called set\_balance so that it does not use procedure Correct and sets the balance field in O(n). Use the following heading: procedure set_balance(T : pointer; var height : integer);

  4. Draw a 2-3 tree for the following data: k, a, t, u, b, s, c, d, m, p, n

  5. Draw a Huffman tree for the following sets of letters and frequencies: (H, 4), (G, 9), (B, 2), (A,11) Using this tree decode 100011?

  6. Given a binary tree such that if the node number of the parent is j , then the node number of the left child is 2*j and that of the right child is 2*j + 1 . This number is stored in the node_number field given in:

    tree = ^ node_rec
    node_rec = record
      node_number : integer;
      left, right : tree
    end;
    
    (a)Write a recursive procedure to insert the node numbers in the node_number field using: procedure insert(T : tree; n : integer);

    (b)The compression code ( Huffman code ) associated with, for instance, node number 9 is 001 as shown in the diagram. This code in reverse order (100) can be obtained by continuously mod ing and div ing the node number by two, storing the result of the mod in a variable called digit , until the value of node number becomes 1. Write a procedure that takes the node number from the node_number field and using the above mentioned algorithm, displays the compression code for each leaf. Use the following heading, and the object stack refered to in problem 1. procedure code(T : tree);

  7. Given the following definitions for a coalesced hashing problem for a set of data with unique keys. When a collision occurs, the search for a vacant slot is performed by decreasing a global variable finger until an empty slot is found ( x[finger].key = 0 ) or the value of finger is less than zero (meaning that the hash table is full). The original value of finger is capacity , the type of x is array_type , and all the link values are initialized to -1.

    const capacity = 10;
    type 
        range =  0..capacity;
        hash_rec = record
            key : integer;
            deposit : real;
            branch : integer;
            link : -1..capacity
        end {hash_rec ;
        array_type = array[range] of hash_rec;
    
    
    Fill in the following table for the keys: 1643, 1183, 1241, 1792, 1647, 1123, 677. The slot numbers should go from 0 to 9.

    slot     key       Link     
    __________________________________
    __________________________________
    __________________________________
    __________________________________
    __________________________________
    __________________________________
    __________________________________
    __________________________________
    __________________________________
    __________________________________
    __________________________________