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

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 log₂(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, n².
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.
   [a.] a list
   [b.] a set
   [c.] a dictionary
   [d.] None of the above
   
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 ?
   [a.] a list
   [b.] a set
   [c.] a dictionary
   [d.] None of the above
   
3. If we attempt to open a file for reading by calling open() and the file does not exist, what action is taken?
[a.] a new file is created.
[b.] an error message is issued.
[c.] a NULL value is returned.
[d.] an EOF is returned.

4. When using command line arguments, what is the content of argv[0] ?
[a.] The name of the input data file.
[b.] The name of the executable file.
[c.] The name of the output data file.
[d.] None of the above.

5. The correct ordering of running times from slowest to fastest is:
[a.] n, log₂(n), n * log₂(n), n²
[b.] n², n, n * log₂(n), log₂(n)
[c.] n², n * log₂(n), n, log₂(n)
[d.] log₂(n), n, n * log₂(n), n²
[e.] None of the above

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
   

   • Describe what this code will return and when it does so ?
   • What is the name of the algorithm implemented here ?
   • What is the running time of this algorithm ?
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.

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 _____________

10. 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._____________()
    

11. Refer to the following code to anwer these questions.

    def foo(a):
    
        if a == 0:
            return 1
        else:
            return a * foo(a - 1)
    

    • Describe what this code will return ?
    • What is the name of the algorithm implemented here ?
12. Write a constructor for a class named Book which contains three data attributes:
    • a string title
    • a string author
    • a boolean checkedOut
13. Write a program that gets 4 integers as command-line arguments, prints the values and their total.
14. Discuss the design of a recursive function, including the definitions of base case and general rule.
15. What is an accessor ?
16. What is a mutator ?

17. 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 ?
18. What is the purpose of the call stack ?
19. 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)
20. Explain the usage of a docstring.
21. When discussing program design, what is coupling ?
22. When discussing program design, what is cohesion ?

---

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

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

---

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

---

25. Continuing from the previous question ...

    >>> colleagues.difference(friends)
    

---

26. Continuing from the previous question ...

    >>> friends.difference(colleagues)
    

---

27. Continuing from the previous question ...

    >>> colleagues.intersection(friends)
    

---

28. Continuing from the previous question ...

    >>> acquaintences.issuperset(friends)