CP164 : Midterm Practice Questions

General Comments

This document contains a list of sample questions for the Midterm. Some of these questions, or questions very much like them, will appear on the Midterm.

The important difference between the midterm and the labs and assignments is that you have the Python interpreter during labs and assignments. So to prepare for the midterm it is worthwhile writing some code without an interpreter. Then, obviously, use the interpreter to see if you were right and, importantly, learn where you went wrong.

The questions are of varying difficulty, so don't expect them all to be straightforward. Some are actually quite challenging. And, no, we will not be providing any solutions (but you knew that, didn't you?). SOME OF THE QUESTIONS ARE HARDER AND LONGER THAN THOSE ON THE MIDTERM. DON'T PANIC IF SOME SEEM HARD. On the plus side, if you can do them you'll be very well-prepared for the midterm.

Write Python code for each of the problems. Either type it in NotePad or use a pencil and paper. Do not use Eclipse. When you have checked over your code and are sure it will work, enter it into Eclipse and run the Python interpreter. For the larger problems it is acceptable to test each function separately.


You are expected to know the basic differences between a Stack, Queue, and Priority Queue in terms of how items are added and removed from these structures. I do not expect you to have memorized the code, but you must know that a Stack is a LIFO (Last In First Out) data structure, a Queue is a FIFO (First In First Out) data structure, a Priority Queue removes items according to their priority, etc. You are also expected to know the basic operations of these data structures, such as pop and push for Stacks, insert and remove for Queues, is_empty for all of them, etc.

You may not use any Python shortcuts for any of the following questions, such as the list reverse, sort, etc.

Know the difference between use and extend!


  1. You only want to watch low calorie food. Write the following function:

    def low_cal(foods, count):
        """
        -------------------------------------------------------
        Returns a list of foods with a calorie count less than count.
        Use: low_cal_foods = low_cal(foods, count)
        -------------------------------------------------------
        Parameters:
            foods - a list of Food objects (list of Food)
            count - foods must have calories below count (int)
        Returns:
            returns
            low_cal_foods - a list of Food (list of Food)
        -------------------------------------------------------
        """
    

  2. Write the function:

    def has_balanced_brackets(s):
        """
        -------------------------------------------------------
        Determines whether a string contains balanced brackets or not.
        Must use a Stack to do so.
        Use: b = balanced_brackets(s)
        -------------------------------------------------------
        Parameters:
            s - a string (str)
        Returns:
            balanced - True if s contains balanced brackets, False otherwise (boolean)
        -------------------------------------------------------
        """
    

  3. Write the function:

    def postfix(s):
        """
        -------------------------------------------------------
        Evaluates a string as postfix expression.
        Must use a Stack to do so.
        Use: b = postfix(s)
        -------------------------------------------------------
        Parameters:
            s - a postfix expression in a string (str)
        Returns:
            result - the result of evaluating the postfix expression in s (float)
        -------------------------------------------------------
        """
    

    The function must use a single stack to do its work.

    In a postfix expression, operators follow operands. Thus the infix expression:

    5 + 12
    

    is written as postfix expression:

    5 12 +
    

    There are no parentheses used in postfix expressions as the operations are performed in the order that they appear. Thus the infix expression:

    (4 + 5) * 12 - 2 * 3
    

    is written as postfix expression:

    4 5 + 12 * 2 3 * -
    

    The answer in both cases is 102.

    Hint: use the stack to store the numbers being processed, and pop them off when an operation (+, -, *, /) appears.


  4. A walk-in clinic has only a limited amount of time to process patients. Patients with more severe problems take longer to process than patients with less severe problems. Assume that priority is based upon integers, and that the lower the integer the higher the priority. The clinic wants to know what the total priority of everyone in the priority queue is at any time. Assume that the contents of the priority queue data is a simple integer.

    def total_priority(pq):
        """
        -------------------------------------------------------
        Returns the total priority of all elements of a priority queue.
        Use: n = total_priority(pq)
        -------------------------------------------------------
        Parameters:
            pq - a priority queue with integer priorities (PriorityQueue)
        Returns:
            n - the sum of all priority values in pq (int)
        -------------------------------------------------------
        """
    

  5. Implement the previous question as a class method.

    def total_priority(self):
        """
        -------------------------------------------------------
        Returns the total priority of all elements of a priority queue.
        Use: n = pq.total_priority()
        -------------------------------------------------------
        Returns:
            n - the sum of all priority values in pq (int)
        -------------------------------------------------------
        """
    

  6. A Set is a data structure that allows only one occurrence of a value to be stored in it at any one time. An attempt to insert a second copy of a value is rejected. Note that data is not stored in any particular order in the Set. Define the following methods for an array-based Set.

    class Set:
    
        def __init__(self):
            """
            -------------------------------------------------------
            Initializes an empty Set.
            Use: s = Set()
            -------------------------------------------------------
            Returns:
                Initializes an empty set.
            -------------------------------------------------------
            """
            
            # your code here
            
            return
    
        def is_empty(self):
            """
            -------------------------------------------------------
            Determines if the set is empty.
            Use: b = s.is_empty()
            -------------------------------------------------------
            Returns:
                True if the set is empty, False otherwise.
            -------------------------------------------------------
            """
            return len(self._values) == 0
    
        def __len__(self):
            """
            -------------------------------------------------------
            Returns the size of the set.
            Use: n = len(s)
            -------------------------------------------------------
            Returns:
                the number of values in the set.
            -------------------------------------------------------
            """
            return len(self._values)
    
        def _linear_search(self, key):
            """
            -------------------------------------------------------
            Searches for the first occurrence of key in the set.
            Private helper method - used only by other ADT methods.
            Use: i = self._linear_search(key)
            -------------------------------------------------------
            Parameters:
                key - a partial data element (?)
            Returns:
                i - the index of key in the set, -1 if key is not found (int)
            -------------------------------------------------------
            """
            
            # your code here
            
            return i
    
        def insert(self, i, value):
            """
            -------------------------------------------------------
            Inserts value at the proper place in the set.
            Use: b = s.insert(i, value)
            -------------------------------------------------------
            Parameters:
                i - index value (int)
                value - a data element (?)
            Returns:
                inserted - True if the value was inserted at i, False otherwise.
                    value is inserted at position i or appended to the end of the set
                    if i > len(s) only if value is unique in the set (boolean)
            -------------------------------------------------------
            """
            
            # your code here
            
            return
    
        def remove(self, key):
            """
            -------------------------------------------------------
            Finds, removes, and returns the value in the set that matches key.
            Use: value = s.remove( key )
            -------------------------------------------------------
            Parameters:
                key - a partial data element (?)
            Returns:
                value - the full value matching key, otherwise None (?)
            -------------------------------------------------------
            """
            
            # your code here
            
            return value
    
        def find(self, key):
            """
            -------------------------------------------------------
            Finds and returns a copy of value in the set that matches key.
            Use: value = s.find( key )
            -------------------------------------------------------
            Parameters:
                key - a partial data element (?)
            Returns:
                value - a copy of the full value matching key, otherwise None (?)
            -------------------------------------------------------
            """
            assert len(self._values) > 0, "Cannot find in an empty set"
            
            # your code here
            
            return value
    
        def peek(self):
            """
            -------------------------------------------------------
            Returns a copy of the first value in list.
            Use: value = s.peek()
            -------------------------------------------------------
            Returns:
                value - a copy of the first value in the set (?)
            -------------------------------------------------------
            """
            assert len(self._values) > 0, "Cannot peek at an empty set"
            
            # your code here
            
            return value
    
        def index(self, key):
            """
            -------------------------------------------------------
            Finds the location of the first occurrence of key in the set.
            Use: n = s.index( key )
            -------------------------------------------------------
            Parameters:
                key - a data element (?)
            Returns:
                i - the location of the full value matching key, otherwise -1 (int)
            -------------------------------------------------------
            """
            
            # your code here
            
            return i
    
    
        def _valid_index(self, i):
            """
            -------------------------------------------------------
            Private helper method to validate an index value.
            Python index values can be positive or negative and range from
              -len(set) to len(set) - 1
            Use: assert self._valid_index(i)
            -------------------------------------------------------
            Parameters:
                i - an index value (int)
            Returns:
                True if i is a valid index, False otherwise.
            -------------------------------------------------------
            """
            n = len(self._values)
            return -n <= i < n
    

  7. For all functions and methods above, identify their Big-O notation, and give a brief explanation for your choice.