CS21: Quiz 6 Study Guide

In addition to the concepts below, you should also know the concepts that were tested on all of the previous quizzes: Quiz 1, Quiz 2, Quiz 3, Quiz 4, Quiz 5.

You should be able to define and explain the following terms:

You should understand and be able to use the following Python concepts:

Practice problems:

  1. If you are running selectionSort() on the following list, L: 
    L = [9, 35, 18, 200, 0, 6, 43, 21]
    Which of the following represents L after 3 iterations of the outer loop in selectionSort()? 
    A. [0, 6, 9, 18, 21, 35, 43, 200]
B. [0, 6, 9, 200, 18, 35, 43, 21]
C. [0, 9, 35, 18, 200, 6, 43, 21]
D. [0, 6, 9, 35, 200, 18, 43, 21]
  2. Describe the sorting algorithms we studied in class and show the above list, L, as it is being sorted, using each algorithm.
  3. Write two versions of each of the following functions...one version using iteration and one using recursion:
    • sum all values in a given list of integers
    • return True if a list is sorted/in order, False if not
    • count/return how many times a given value (v) is found in a list (L)
    • find the largest number in a list
  4. Draw a stack diagram for the following program. Show what the stack would look like at it's largest point. 
    def main():
    n = 5
    ans = factorial(n)
    print ans

def factorial(x):
    if x == 0:
      return 1
    else:
      return x * factorial(x-1)

main()
    [Answer (but red arrows aren't needed -- they just show where things get returned)]