CMSC201 Final Exam Review
Spring 2012


Picture ID required for the Final Exam

This review list is meant to give you an idea of the types of questions and topics that will be covered. It is by no means an exhaustive list. The actual exam will possibly contain questions and/or coding problems similar to those in this review guide, IN ADDITION to questions and/or coding problems related to any material gone over in lecture, group exercises, labs, homework assignments, course lecture notes, etc.


True/False Questions

Circle TRUE or FALSE for each of the following questions.
  1. TRUE/FALSE
    When using a list, items stay in the order they're inserted with append().
  2. TRUE/FALSE
    Sets are ordered collections of data with no duplicates.
  3. TRUE/FALSE
    Dictionaries are Python's implementation of an associative array.
  4. TRUE/FALSE
    Lists are mutable.
  5. TRUE/FALSE
    Strings are mutable.
  6. TRUE/FALSE
    A stack is a specialized version of a list in which items can be inserted only at the front of the list and deleted only from the end of the list.
  7. TRUE/FALSE
    A queue is referred to as a FIFO data structure because the first item inserted is the first item removed.
  8. TRUE/FALSE
    An abstract data type is a mathematical object and the operations on that object, that we think of in terms of its behavior rather than its implementation.
  9. TRUE/FALSE
    An item should be inserted into a queue in such a way as to maintain the queue in sorted order by the key.
  10. TRUE/FALSE
    Linear search is faster than binary search on sorted lists of size 100.
  11. TRUE/FALSE
    Linear search runs in log2(n) time.
  12. TRUE/FALSE
    Sorted lists can be searched quickly using the binary search algorithm.
  13. TRUE/FALSE
    All of the well-known sorts run in the same running-time, n2.
  14. TRUE/FALSE
    We can write our own modules.
  15. TRUE/FALSE
    Large or complicated methods can be broken into smaller methods, as in top-down design.
  16. TRUE/FALSE
    An item should always be inserted into a list in such a way as to maintain the list in sorted order by some unique key.

Multiple Choice Questions

  1. Which data structure is the most appropriate choice for a program that gets up to 100 numbers from the user and prints out a table showing how many times each number occurred. The table doesn't need to be in numeric order.
  2. Which data structure is the most appropriate choice for a program that gets 7 scores from the user in the range of 0 to 10 and prints the scores in numerical order, as well as the average score after throwing out the lowest and highest score ?
  3. If we attempt to open a file for reading by calling open() and the file does not exist, what action is taken?
  4. When using command line arguments, what is the content of argv[0] ?
  5. The correct ordering of running times from slowest to fastest is:

Short Answers

  1. Refer to the following code to anwer these questions.
    def foo(list, a):
    
        b = 0
        c = len(list) - 1
    
        while b <= c:
            d = (b + c) / 2
    
            if a == list[d]:
                return d
            elif a > list[d]:
                b = d + 1
            else:
                c = d - 1
    
        return -1
    
  2. What is mutability?
  3. What are the differences between a stack and a queue ?
  4. Describe how Selection sort works. Don't show the code.
  5. What are the coordinates of the upper-left corner of a graphics window?
  6. What are the coordinates of the lower-right corner of a graphics window?
  7. What is the purpose of the following code?
        win = GraphWin("Tic-Tac-Toe", 400, 400)
        win.setCoords(0.0, 0.0, 3.0, 3.0)
    
  8. Which method from the time module do we use for animations?
  9. Fill-In-The-Blank  Word Frequency
    The following program gets the name of a file as a command-line argument, opens that file, reads from it and creates a dictionary of the words in the file and the number of times each word occurred.
  10. import _______________
    import sys
    
    NUM_ARGS = ___________
    
    words = {}
    
    if len(sys.argv) != ______________:
        print "This program needs a command-line argument"
        print "that is the name of the file to evaluate."
    
        sys._______________
    
    
    file = open(_______________, 'r')
    
    for line in ____________:
    
        _____________  = string.split(line)
    
        for word in wordList:
            # change word to be in all lower-case
            word = string.lower(word)
    
            # if the word has punctuation after it
        
            if ord(____________) < ord('a') or ord(____________) > ord('z'):
    
                # remove the punctuation mark from the word
    
                word = word[: ___________ ]
    
            # put the word in the dictionary and/or increment the word counter
    
            count = words.___________(word, 0)
    
            words[ ____________ ] = count + 1
            
    file.______________
    
    print _____________
    
  11. An archery target consists of a central circle of yellow surrounded by concentric rings of red, blue, black and white. Each ring has the same "width", which is the same as the radius of the yellow cicle. Objects drawn later will appear on top of objects drawn earlier. Fill in the blanks in the function drawTarget()below that takes a single argument, which is the radius of the central yellow circle. You may assume that graphics.py and time have been imported.
    def drawTarget(radius):
    
        SIZE = 25
        NUM_RINGS = 5
        DELAY = 10
    
        WHITE = 5
        BLACK = 4
        BLUE = 3
        RED = 2
        YELLOW = ________
    
    
        window = ___________("Archery Target", SIZE * radius, SIZE * radius)
    
        ________.setBackground('green')
        
        counter = NUM_RINGS
    
        
        for i in range(radius * NUM_RINGS, _____, -radius):
    
            circle = _________(_______(SIZE * radius / 2, SIZE * radius / 2), ____)
    
            _______.setOutline('black')
    
    
            if counter == WHITE:
    
                circle._____________('white')
    
            elif counter == ___________:
    
                circle.setFill('black')        
    
            ________ counter == BLUE:
    
                circle.setFill('blue')        
    
            elif counter == RED:
    
                circle.setFill('red')
    
            elif counter == YELLOW:
    
                circle.setFill('yellow')
    
            else:
    
                _______ "Error - counter =", _________
    
            circle.draw(___________)
    
            counter _____ 1
    
        time.___________(DELAY)
    
        window._____________()
    
  12. Refer to the following code to anwer these questions.
    def foo(a):
    
        if a == 0:
            return 1
        else:
            return a * foo(a - 1)
    
  13. Write a constructor for a class named Book which contains three data attributes:
  14. Write a program that gets 4 integers as command-line arguments, prints the values and their total.
  15. Discuss the design of a recursive function, including the definitions of base case and general rule.
  16. What is an accessor ?
  17. What is a mutator ?
  18. For the following question, no code is required. Just show what would be printed by the printStack() and printQueue() functions.

    The following values are held in a queue:
    50 25 88 77 21 94 90 23 30 39 10 65 83 96 27
    where the value 50 is at the front of the queue and 27 is at the end. dequeue() these values and push() the even numbers onto one stack and the odd numbers onto another stack. What would be the output from a printStack() function that prints each value as it is popped from the stack if we printed the contents of the even stack ? The odd stack ?
  19. What is the purpose of the call stack ?
  20. Given the following partial class definition:
    class Clock:
    
        def __init__(self, day, hour, min, sec): 
    
               self.day = day
               self.hour = hour
               self.min = min
               self.sec = sec
    
    
    where a Clock is to simulate a 24-hour clock by keeping the time in days, hours, minutes and seconds.
    Write the method incrementTime() which increments the time by one second. (HINT: To keep the time in the correct format, sometimes more has to be done than just incrementing the sec member)
  21. Explain the usage of a docstring.
  22. When discussing program design, what is coupling ?
  23. When discussing program design, what is cohesion ?

  24. Determine the output generated by the following code segments, assuming the surrounding program code (whatever it is) runs correctly.

  25. def foo(n):
    
        print n,
        if n > 0:
            foo(n - 1)
    
    def main():
    
        foo(4)
        print 'done'
    
    main()
    

  26. >>> colleagues = set(['Sam', 'Kostas', 'Dawn', 'Brooke', 'Marie', 'Dan'])
    >>> friends = set(['Dawn', 'Dan'])
    >>> acquaintences = friends.union(colleagues)
    >>> acquaintences
    

  27. Continuing from the previous question ...
    >>> colleagues.difference(friends)
    

  28. Continuing from the previous question ...
    >>> friends.difference(colleagues)
    

  29. Continuing from the previous question ...
    >>> colleagues.intersection(friends)
    

  30. Continuing from the previous question ...
    >>> acquaintences.issuperset(friends)