讲解 CS 138、C++编程设计辅导
CS 138 - Sample Final Exam
• The exam is 150 minutes long.
• Please read all instructions carefully.
• There are 4 questions on this exam, some with multiple parts. This exam will be graded out of a
maximum of 104 points.
• The exam is a closed book and notes. You are not permitted to access any electronic devices during
the duration of the exam. You are not allowed to consult another person to find out the answers.
Do not open the exam book without the proctor’s permission. Please make sure to sign the exam
book. Please do not talk among yourselves during the exam. If you have any questions, consult the
proctor. Appropriate university policies will apply if you are caught cheating by the proctor.
• Please write your answers in the appropriate space provided in your respective exam books. Please
make sure to write your names and IDs.
• Solutions will be graded on correctness, clarity, completeness and brevity. Most problems have a
relatively simple solution. Partial solutions may be given partial credit.
• Follow the instructions given by the proctor throughout the exam. If you need to step out of the
exam hall for washroom visits, then please talk to the proctor.
NAME:
Email ID:
Student ID:
In accordance with the letter and the spirit of the University of Waterloo honor code, I pledge
that I will neither give nor receive assistance on this examination.
SIGNATURE:
Problem Max points Points Received
Q1 20
Q2 30
Q3 30
Q4 24
Total 104
1
Question 1: True/False questions (20 points)
·Please specify if the following assertions are True or False. Each sub-question is worth 2 points. For
each question you answer False, justify to get full points.
1. Virtual functions in C++ can be static.
Answer:
2. Hash functions are deterministic, meaning the same input will always produce the same hash code.
Answer:
3. An abstract class in C++ can have both concrete (non-pure virtual) and pure virtual functions.
Answer:
4. C++ allows for function overloading based solely on return type.
Answer:
5. Hash functions must be invertible, allowing the original data to be recovered from its hash code.
Answer:
6. Initializer lists allow for uniform initialization syntax in C++, regardless of whether you are initializing a built-in type or a user-defined type.
Answer:
7. Static methods can be used to modify the state of a static field directly without needing an instance
of the class.
2
Answer:
8. Instantiating a template with a user-defined type requires that the type has specific methods or
behaviors defined.
Answer:
9. The end iterator in C++ points to the last element of a container, allowing direct access to that
element.
Answer:
10. Doubly linked lists guarantee constant-time access to elements at arbitrary positions due to their
bidirectional nature.
Answer:
3
Question 2: Short Answer Questions (30 points)
For each of the sub-questions below, provide a concise, correct, and complete answer. Each sub-question
is worth 5 points.
1. What is the difference between a const pointer and a pointer to a const variable?
Answer:
2. 1: #include
2: #include
3: using namespace std;
4:
5: class Vehicle {
6: public:
7: Vehicle();
8: Vehicle(string type);
9: virtual ~Vehicle();
10: void displayType() const;
11: private:
12: string type;
13: };
14:
15: // Method definitions
16: Vehicle::Vehicle() {
17: this->type = "car";
18: }
19:
20: Vehicle::Vehicle(string type) {
21: this->type = type;
22: }
23:
24: Vehicle::~Vehicle() {}
25:
26: void Vehicle::displayType() const {
27: cout << "This is a " << this->type << endl;
28: }
29:
30: int main(int argc, char* argv[]) {
31: Vehicle car {"sedan"};
32: car.displayType();
4
33:
34: Vehicle bike {};
35: bike.displayType();
36:
37: Vehicle* bus = new Vehicle {"bus"};
38: bus->displayType();
39:
40: Vehicle* ptr = bus;
41: ptr->displayType();
42: ptr->type = "truck";
43: ptr->displayType();
44:
45: delete ptr;
46: delete bus;
47:
48: return 0;
49: }
The provided code crashes when executed. Why? Explain your answer. Be specific about where
the problem(s) sites and what exact error(s) will you get.
Answer:
5
3. #include
class Circle {
public:
double radius;
double area();
};
double Circle::area() {
return 3.14159 * radius * radius;
}
int main() {
Circle myCircle;
myCircle.radius = 5.0;
std::cout << "The area of the circle is: " << myCircle.area() << std::endl;
return 0;
}
The Circle class does not have a constructor. Do you think this code will execute ? Explain your
answer.
Answer:
4. class Balloon {
public:
...
Balloon (); // Default ctor
Balloon (string shellColour);
Balloon (string c, int size);
Balloon (int i, string c);
...
};
int main (...) {
Balloon rb {"red"};
6
Balloon rbc1 {rb};
}
Will the last line of the main function execute correctly (note that a copy constructor is not defined)?
Answer:
7
5. What are the advantages of using the heap?
Answer:
6. What is the significance of BSTs in terms of the complexity of insertion, deletion and search?
Answer:
8
Question 3 (30 points)
For each of the sub-questions below, provide a concise, correct, and complete answer. Each of the following sub-questions below is worth 6 points.
In class, we learned about different STL container classes. Suppose this time, we want to create our
own implementation of these classes but with some OO inheritance hierarchy. We start with an Abstract
Base Class Sequence for all sequence containers, and a concrete child class Vector. Internally, Vector
uses a dynamic array to store the elements, with an additional field capacity representing this dynamic
array’s size. The field size indicates how many slots are actually being used in the array.
class Sequence {
private:
int size;
protected:
Sequence(): size {0} {}
void setSize(int size) { this -> size = size; }
public:
virtual ~Sequence() {}
virtual string& at(int index) = 0;
virtual void push_back(const string& item) = 0;
virtual void pop_back() = 0;
int getSize() const { return size; }
};
class Vector: public Sequence {
private:
string* theArray;
int capacity;
void increaseCapacity();
public:
Vector();
~Vector();
virtual void push_back(const string& item) override;
virtual void pop_back() override;
virtual string& at(int index) override;
};
string& Vector::at(int index) {
9
if(index >= 0 && index < getSize()) {
return theArray[index];
}
cerr << "Error: Out of bounds" << endl;
assert(false);
}
1. We want our Vector to be able to change its capacity dynamically. To achieve this, Implement
a private helper method increaseCapacity() that allocates a new dynamic array with double
the original capacity, copies the contents of the original array to the new array, replaces the old
array with the new array, and finally disposes of the old array. You may assume the preconditions
capacity > 0 and capacity == size.
Answer:
2. Implement the push back() and pop back() methods for Vector. Both of these methods should
update the field size. When the Vector is full, push back() should call increaseCapacity() before pushing the new item. You don’t need to shrink the capacity in pop back(). You may assume
your increaseCapacity() is implemented correctly.
Answer:
10
3. The implementation of Vector::at() performs bound checking before returning the item at the
given index. We want to perform the same bound checking for all future child classes of Sequence,
but that would require us to implement bound checking for every new child class. We can save this
effort by using the Template Method design pattern:
class Sequence {
private:
// ...
virtual string& getItemAt(int index) = 0; // virtual helper method
protected:
// ...
public:
// ...
string& at(int index); // template method
};
class vector: public Sequence {
private:
// ...
virtual string& getItemAt(int index) override;
public:
// ...
};
We can do the same for push back() and pop back(), but we will leave them as they are for now.
Implement the template method Sequence::at() and the new helper method Vector::getItemAt()
such that calling Vector::at() has the same behaviour as the original.
Answer:
11
4. Let’s implement a new concrete subclass List that uses a linked list.
class List: public Sequence {
private:
struct Node {
string val;
Node* next;
};
Node* head;
virtual string& getItemAt(int index) override;
public:
// ...
virtual void push_back(const string& item) override;
virtual void pop_back() override;
};
Implement the methods of List. You can choose to let the field head point to the “front” or the
“back” of the linked list, as long as you keep it consistent among your methods. You don’t need to
implement the constructor and the destructor. Your implementation shouldn’t leak any memory.
Answer:
5. Now that we have some Sequence classes, let’s use them to implement something else. We can use
the abstract class Sequence to implement a Stack:
template class Stack {
private:
12
Sequence* theStack;
public:
Stack(): theStack { new T{} } {}
~Stack() { delete theStack; }
void push(const string& value);
void pop();
string top() const;
bool isEmpty();
};
Note that assigning new T to theStack in the constructor forces T to be a concrete sub-type of
Sequence. (We will assume that all subclass of Sequence has a default constructor.)
Implement the remaining methods. Since Sequence::at() already does bound checking, you don’t
need to do it again when you use it here. You may also assume that T::pop back() will abort via
assertion if the Sequence is empty.
Answer:
13
Question 4 (24 points)
For each of the sub-questions below, provide a concise, correct, and complete answer. Each of the following sub-questions below is worth 6 points.
In this question, we will start from an abstract base class Sequence and extend it to a Deque (doubleended queue). A deque is a more complex sequence container that allows insertion and removal of elements
from both the front and the back. For this implementation, internally, Deque will utilize a dynamic array
to manage its elements, similar to Vector, but with the capability to efficiently add or remove elements
at both ends. Starting with the Sequence abstract base class, we will focus on implementing the Deque
class with the necessary modifications to support dynamic resizing and double-ended operations.
class Sequence {
private:
int size;
protected:
Sequence(): size {0} {}
void setSize(int size) { this -> size = size; }
public:
virtual ~Sequence() {}
virtual string& at(int index) = 0;
virtual void push_back(const string& item) = 0;
virtual void pop_back() = 0;
int getSize() const { return size; }
};
class Deque : public Sequence {
private:
std::string* theArray;
int capacity;
int front; // Index of the front element
int rear; // Index just past the last element
void increaseCapacity();
public:
Deque();
~Deque();
void push_front(const std::string& item);
void pop_front();
virtual void push_back(const std::string& item) override;
virtual void pop_back() override;
14
virtual std::string& at(int index) override;
};
1. Implementing increaseCapacity() for Deque: To support dynamic resizing, especially when either
front or rear operations exceed the current capacity, you are asked to implement increaseCapacity().
This method is expected to double the capacity of the deque, properly repositioning elements to
maintain the deque’s order. You are expected to place the elements in the original deque at the
center of the new dequeue to account for insertion in both front and rear of the dequeue.
2. Your second task is to implement double-ended operations push front, pop front, push back and
pop back: These methods adjust the class variables front and rear accordingly. They also call
increaseCapacity() when necessary.
Answer:
15
3. Please adjust the at() method for Deque: Given Deque’s dynamic resizing and double-ended nature, its at() method must consider the front index’s offset when accessing elements.
Answer:
16
4. Lastly, proper resource management is crucial, especially for dynamic array allocation. Please implement the constructor and destructor of Deque. Please implement the constructor as no input
parameters but assume the class receives a default value for the deque capacity of 16.
Answer:
17