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:
Quiz 1,
Quiz 2,
Quiz 3,
Quiz 4,
Quiz 5,
Quiz 6.
Historically, the final exam includes questions about each of the big
ideas and skills in the course, such as:
- Python expressions and types
- Write a complete program
- Write and test a class
- Trace a program, showing output and the stack diagram
- Recursion and iteration
- Analysis of algorithms
- Searching and sorting
- Linked Lists
Below are some of the new topics covered since the last quiz and
some additional practice problems.
You should be able to define and explain the following terms:
- Object-oriented programming, including
- methods
- an object's instance variables
- the constructor, or __init__ method
- the string, or __str__, method
- access methods, getters, accessors
- update methods, setters, mutators
- Linked lists, including
- the LinkedList class
- the Node class
- the implementation and running time of various LinkedList methods, such as the
constructor, append, prepend, deleteHead, and deleteTail
- how linked lists differ from Python's consecutive-memory Lists
Practice problems:
- Using the LinkedList implementation from class, work through
the code below. You should be able to draw the linked list after every
line of code. Note: some professors use different names for the same methods.
For example, insertAtTail() might be called append(), insertAtHead() might be
prepend(), getData() might be getItem(), and so on...
LL = LinkedList()
LL.insertAtTail(30)
LL.insertAtHead(10)
LL.insertAtHead(100)
LL.insertAtTail(56)
# draw the linked list as it would look here
- Compare the complexity of python lists and Linked Lists for different
operations:
- What is the big-O complexity of searching an unsorted list versus an
unsorted linked list?
- How about if the list or linked list is sorted?
- What is the big-O complexity of inserting an item at the beginning of each list representation?
- How about at the end of each list?
In some cases, python lists and linked lists
may have different complexities for the same operation.
- Write a complete program that
plays a guessing game with numbers. The goal is for the user to guess
a randomly selected number between 1 and 100 as quickly as
possible. The program will inform the user whether the hidden number
is higher or lower than the current guess.
You must break the problem
up into a main function and at least one additional function.
The following is a sample run of the program:
I'm thinking of a number between 1 and 100.
Enter guess: 50
Number is higher than 50
Enter guess: pony
Invalid, try again: 588
Invalid, try again: 75
Number is lower than 75
Enter guess: 62
Number is lower than 62
Enter guess: 56
You guessed it in 4 tries!
- Write a Student class that stores information for a Swarthmore student.
The class should include the following instance variables:
- id, an integer identifier for the student
- lastName, a string for the student's last name
- credits, an integer representing the number of course-credits
the student has earned
- courseLoad, an integer representing the current number of
credits in progress
Write the following methods for your Student class: