2nd Midterm v22.0102, Marxh 10, 1997, Sam Marateck

  1. Given the interface of the following ADT, as shown below, write a procedure win used in the ADT that determines if a player represented by the current_color wins. A player wins if his/her checkers occupy the diagnol that goes from the lower left to the upper right.
    unit TestADT;
    uses number_unit
      column_type = 1..number; {index for columns}
      square_type = {index for squares}
          column : column_type;
          row : column_type
      color_type = (red,blue);
      value_type = {what a square contains}
          empty : boolean;   {is square empty?}
          color : color_type {if not empty, what color it is}
      array_type = array[column_type,row_type] of value_type;
      board_type = 
            procedure Initialize; 
            procedure Make_Move(column : column_type); 
            procedure Get_Value(square : square_type; Val : value_type); 
            function Get_Current_Color : color_type;
            function Is_Full(column : column_type) : boolean;
            function Win : boolean;
            function Is_Draw : boolean;
            Value : array_type; {the board configuration}
            current_color : color_type; {whose turn it is}
        end; {object board_type}

  2. Given a doubly linked list that has the pointer head to the first node. The list has at least one node. Write a procedure called remove that has head as its only parameter The procedure removes the last node from list. Use the following type definition for the list.
    pointer = ^ node;
    node = record
      info : char;
      left, right : pointer

  3. (a). Write the code for a program named Circular_List that reads in integers from the keyboard and stores them in a linked list whose first node is pointed to by header and last node points to the first node instead of nil. (b). Write a procedure print( list ) that prints the information on the circular linked list.