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. 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
  2. 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()
    

  3. 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]
    

  4. Show all output for the following program:
    def printline():
      print("-"*20)
    
    def mystery(L):
      while True:
        nswaps = 0
        for i in range(len(L)-1):
          if L[i] > L[i+1]:
            L[i],L[i+1] = L[i+1],L[i]
            print(L)
            nswaps = nswaps + 1
        if nswaps == 0:
          return
        printline()
    
    L = [22,57,3,30]
    print("initial list:")
    print(L)
    printline()
    mystery(L)
    printline()
    print("final list:")
    print(L)