The final exam is cumulative. In addition to the concepts
below, you should know the concepts that were tested on all the
quizzes in the course:
You should be able to define and explain the following terms:
- Recursion and iteration
- Imperative programming
- Object-oriented programming, including
- an object's instance variables
- the constructor, or __init__ method
- the string, or __str__, method
- access methods, getters
- update methods, setters
- Linked lists, including
- the LinkedList class
- the Node class
- the implementation and running time of various LinkedList methods, such as the constructor, insertAtTail, insertAtHead, deleteHead, and getItemAtPosition
- how linked lists differ from Python's consecutive-memory ArrayLists
You should understand and be able to use the following Python concepts:
- How variables are stored and function arguments are passed on the stack for recursive functions.
- How to create a Python object, including its constructor, string method, and the instance variables that it uses.
- How to implement a LinkedList in Python
- Write a recursive sumList function that takes a list as an argument and returns the sum of the items in the list. What is the base case of your function? What is the recursive case?
- Using your sumList function above, draw a complete stack diagram for the following program:
ls = [2, 3, 5]
x = sumList(ls)
- Write a recursive binarySearch function that takes as
arguments: a list, an item to search for, a low index, and a high
index. It should return the position of the item in the list, or -1
if the item is not in the list.
- Write a Student class that stores information for a Swarthmore student. The class should include the following instance variables:
Write the following methods for your Student class:
- id, an integer identifier for the student
- firstName, a string
- lastName, a string
- courses, a list of strings, the course names that the student is enrolled in
- hobbies, a list of strings, the student's hobbies
- A constructor that, given an id, a first name, and a last name, creates a Student with those values and empty lists of courses and hobbies.
- A string method that returns a string representing the student.
- Getter methods for each of the instance variables in the class.
- An addCourse method that, given a course name, adds that course to the student's course list.
- An addHobby method that, given a hobby name, adds that hobby to the student's hobby list.
- A getCredits method that returns the number of courses a student is enrolled in.
- A getFreeTime method that returns the value 55 - 12*number-of-courses - 5*number-of-hobbies. (Alternatively, this method could just return 0.)
- Write a LinkedList deleteTail method that deletes the
tail of a linked list and returns the value of the item that was
stored at the tail. Before attempting this, write pseudocode for
the deleteTail method; it's harder than
the deleteHead method from class! To delete the tail, you
need to set the new tail to be the Node before the current tail; to do
that, you need to find that Node by traversing through the list.