$ mkdir ~/cs170/labs/lab25 $ cd ~/cs170/labs/lab25
In addition to the written portion of the test, there will be a coding portion. This will be done on the computers. For practice, attempt the following exercises in a file called test_review.py, alone:
Write a function recursive_search, which takes
a linked list node as a parameter, and an item being
searched for. It will return True if the item is in the
linked list, and False otherwise. You must use
recursion for this exercise
>>> my_linked_list = linked_list.LinkedList() >>> for i in range(20, -1, -1): ... my_linked_list.append(i) >>> print(recursive_search(my_linked_list.head, 0)) True >>> print(recursive_search(my_linked_list.head, -1)) False >>> print(recursive_search(my_linked_list.head, 20)) True >>> print(recursive_search(my_linked_list.head, 21)) False
Write a function permutations(a_set), which takes a
list of data as its sole parameter. This function should print
all possible permutations of the set a_set. A
permutation of a_set is any ordering of items
from a_set.
Permutations can be computed using a backtracking algorithm. A permutation can be found by selecting an element from the list, finding all permutations of the rest of the list. Then, select the next element from the list, and finding all permutations of the rest of that list. This continues until the the list is exhausted.
>>> permutations([1, 2, 3, 4])
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]