EE 312 - Final Exam Review Solutions
1. Rework midterm 1 without looking at your answers or answers
provided in class. Write your answers on paper, and then test them
with a compiler. Code trace questions and big-O questions were
commonly missed on this exam. You are likely to see similar
questions on the final exam.
2. Rework midterm 2. Same recommendations as in #1.
3. Rework the practice sheets you've been given for the midterms and
recitation practice.
4. Review the class lecture slides and your notes on the uses of const. Review the
class lecture slides on reference variables and reference
parameters. You should, for example, understand our use of reference
parameters in the classes that we wrote in class the past two weeks.
5. Review the use of this
in classes and objects in C++. What is the meaning of this? When is it
necessary to use this?
How is it used?
6. Make sure that you understand new and delete and delete [].
7. You practiced using vector, set, map and pair on projects 9
and 10. Review those assignments. If you want more practice with the
STL containers, there are some programming questions on Hackerrank
that you may find helpful, e.g., https://www.hackerrank.com/challenges/cpp-maps/problem
8. Create a map that maps the name of an assignment to a score (0 to
100). E.g., "quiz1" might be mapped to 85. Create a text file that
contains lines that each contain the name of an assignment, blank
space, and the score on that assignment. Write a program that takes
the name of the text file on the command line and reads the pairs of
values on each line into a map. Then iterate over the map and
computer and print the average score on all assignments.
9. Suppose you have a vector of ints. Use a reverse iterator to
iterate over the vector in reverse order and printing the vector's
elements in reverse order. Note that it is difficult to do this
correctly with a plain old iterator, and you should not attempt to
do so (here or on the final exam.) Once your reverse iterator is
working correctly, re-do this problem with a for loop and indexing
(no iterator.)
vector<int> v(10, 3);
v.resize(15, 2);
for(vector<int>::reverse_iterator it =
v.rbegin(); it != v.rend(); it++){
cout << *it << " ";
}
cout << endl;
for(int i = v.size() - 1; i >= 0; i--) cout
<< v[i] << " ";
cout << endl;
10. Write a String class that contains as its instance variables a
char pointer (to the string) and an int that equals the length of
the string. Write the following member functions:
String::String(const
char* s): constructs a string object that represents s. If
nothing is passed to the constructor, set the char pointer to NULL,
using a default parameter value.
copy constructor, copy assignment operator, destructor
This String class is in the lecture slides on copy constructors,
destructors, and copy assignment operators.
8. Two types of questions have been widely missed on the midterms:
code trace questions and big-O questions. Make sure that you re-work
these questions from the midterms, practice sheets, and weekly
exercises. Draw pictures when doing the code traces.
9. Re-write the binary search tree class that we wrote in lecture,
without looking at any of the code. Write both the interface
(e.g., BST.h) and the implementation (e.g., BST.cpp).
10. In the implementation of a hash table, what do the terms bucket
and collision mean?
See the lecture slides.
11. Add a member function findNode to our BST implementation. The
function takes a node pointer and a key, and returns NULL if the key
isn't found in the binary search tree, and returns a pointer to the
node containing the key if it is found. To find the node containing
a value in the entire tree, findNode(root, value) would be called.
Your implementation should take advantage of the fact that we are
working with a tree that is a binary search tree, not just any
binary tree.
TreeNode*
BST::findNode(TreeNode* node, int value) {
while(node != NULL) {
if(value == node->data)
return node;
else if(value <
node->data) node = node->left;
else if(value >
node->data) node = node->right;
}
return NULL;
}
12. In class, we wrote a print member function for our binary tree
class that printed the nodes during an in-order traversal. Write a
member function printPostOrder that prints the nodes during a
post-order traversal.
void
BST::printPostOrder() const {
print(root);
}
void BST::printPostOrder(TreeNode* node) const {
// implicit base case: do nothing if node is
NULL
if(node != NULL) {
print(node->left);
print(node->right);
cout << node->data
<< endl;
}
}
13. Recall that the STL implements maps with binary search trees.
What is the big-O runtime of the count() function for map?
count returns 1 if the argument is a key in the map, and 0
otherwise. It searches the map for the specified argument. In the
average case, the underlying binary search tree yields O(logN)
performance. In the worst case, the underlying binary search tree
degrades to a linked list, and the performance is O(N).
14. Write a function
set<int>
makePrimeSet(int max)
which returns a set of all the prime numbers between 2 and max.
Recall that to determine if k is a prime, you only need to check
which primes between 2 and the square root of k are divisors of k.
set<int>
makePrimeSet(int max) {
set<int> facts;
for(int i = 2; i <= max; i++) {
if(i == 2) facts.insert(2);
else{
int numDivs =
0;
for(int j = 2;
j <= sqrt(i); j++)
if(i % j == 0) numDivs++;
if(numDivs ==
0) facts.insert(i);
}
}
return facts;
}