The exam will consist of short-answer questions, multiple choice questions, understanding written code, and writing your own code. The emphasis is on reading and writing code, especially with linked lists.
The review below, in addition to the code you wrote for your labs, is intended to be comprehensive. There will be no topics which aren't either below or in the labs which will be on the exam.
If you're pushed for time, my personal recommendation is to spend the majority of your time studying the code you wrote for your labs. The best next thing to look at would be the materal below in the “New Concepts” section. From there, the content in the “C-Like Review” would be best. Overall, my philosophy with programming is that reading and writing code are the best ways to learn, and my questions tend to reflect this.
These questions are on old concepts which should already be familiar to you from CS16. The majority of the points will not be on these sort of questions, but a non-trivial number of points will be on these questions (10-20%). Specifically, you should be familiar with pointers and stack versus heap allocation. I say this section is “C-Like” because it jumps between C and C++, but the overall concepts are all endemic to C.
Consider the following definitions, where ... is a
placeholder for some valid initialization code:
char c = ...; char* p = ...; char** pp = ...;
With respect to the above definitions, what is the type of each of the following expressions? Mark either the appropriate type, or say “ill-typed” if it won't typecheck:
&cc*c&pp*p&pppp*ppConsider the following code:
int x = 7; int* p1 = &x; int* p2 = malloc(sizeof(int)); int* p3 = p2;
For each of the questions below, answer either “heap” or “stack”:
x allocated?p1 itself allocated?p1 points to allocated?p2 itself allocated?p2 points to allocated?p3 itself allocated?p3 points to allocated?Name one advantage of allocating data on the stack.
Name one advantage of allocating data on the heap.
Consider the following C++ code, in a file named main.cpp:
#include <iostream>
int main(int argc, char** argv) {
std::cout << argc << std::endl;
return 0;
}
Say we compile the above code like so:
clang -o args main.cpp
What is printed out by the program for each of the following command-lines?
./args
./args foo
./args foo bar
Consider the following C++ code, in a file named main.cpp:
#include <iostream>
int main(int argc, char** argv) {
for(int x = 0; x < argc; x++) {
std::cout << argv[x] << std::endl;
}
return 0;
}
Say we compile the above code like so:
clang -o args main.cpp
What is printed out by the program for each of the following command-lines?
./args
./args foo
./args foo bar
Name one reason why we would use a value as opposed to a pointer.
Name one reason why we would use a pointer as opposed to a value.
Consider the following C++ code:
int* arr = new int[3]; int* p = arr + 1; arr[0] = 1; arr[1] = 2; arr[2] = 3;
Draw a diagram showing what the memory looks like after
the above code has executed.
The array, arr, and p must be
contained in the diagram for full credit.
The following program does not compile. Why?
int *p1 = new int[5]; void* p2 = (void*)p1; p2[0] = 1;
Why can't void pointers be dereferenced?
Why would someone ever use a void pointer?
What is wrong in this snippet of code? Specifically, what is the name for this kind of bug?
int* foo() {
int x = 7;
return &x;
}
What is wrong in this snippet of code? Specifically, what is the name for this kind of bug?
void foo() {
int* x = new int;
*x = 7;
}
What is an array?
What is a struct?
The code below makes use of square brackets and the arrow
(->) operator. Rewrite it in terms of only
dereferencing (*) and pointer addition
(+).
typedef struct _foo {
int a;
char b;
} foo;
foo* arr[5];
int x;
for(x = 0; x < 5; x++) {
arr[x] = malloc(sizeof(foo));
arr[x]->a = 0;
arr[x]->b = 'b';
}
Everything in this section is expected to be new material. The majority of the exam will cover these sort of questions.
What does the logical/abstract level of an ADT define?
Abstract data types (ADTs) allow us to vary the implementation of a particular data structure without forcing application code that uses the ADT to change. Why is this advantageous?
Name one advantage of an array-based implementation of a list ADT, as opposed to a linked-list representation.
Name one advantage of a linked-list implementation of a list ADT, as opposed to an array-based representation.
In C++, the methods below can be concurrently defined (i.e., all can exist without interferring with each other). Why? What is this called?
int foo(int x); int foo(int x, int y); int foo(int* p);
At a high-level, what does const do? Why is this
useful?
Consider the class definition below, where the different
uses of const have been marked with the numbers
1, 2, and 3.
#include <iostream>
class Foo {
public:
// 1 2 3
void doSomething(const int* const p) const {
std::cout << *p << std::endl; // ???
*p = 8; // ???
x = p; // ???
p = NULL; // ???
std::cout << x << std::endl; // ???
}
private:
int* x;
};
There are five positions marked with ??? in
the above code. Fill in which use of const makes
the line disallowed. If the line isn't disallowed, mark it
with “ok”.
Why would a programmer prefer a reference over a pointer?
In your own words, define each of the following object-oriented programming (OOP) terms:
Why might the encapsulation of internal state a good thing?
What is the difference between a class and an object (AKA, an instance of a class)?
Consider the code below:
class Bar {
public:
Bar(); // ???
Bar(int x); // ???
Bar(const Bar& b); // ???
int getX() const; // ???
void setX(int to); // ???
~Bar(); // ???
private:
int x; // ???
};
There are several positions in the above code which are
marked with ???. Fill in these positions with
the appropriate term which most accurrately defines
what the particular entry is. Below are the possible choices:
Consider the snippet of code below, where the constructors of
Baz have been labeled 1, 2,
3, and 4:
class Baz {
public:
Baz(); // 1
Baz(int x); // 2
Baz(int x, int y); // 3
Baz(const Baz& b); // 4
};
int main() {
Baz b1(10); // ???
Baz* p = new Baz(11); // ???
Baz arr[10]; // ???
Baz b2 = b1; // ???
return 0;
}
Replace ??? in the code above to reflect which
constructor is called in these different cases.
Consider the class definition below:
class Copy {
public:
Copy() { p = new int[10]; }
Copy(const Copy& c);
~Copy() { delete[] p; }
private:
int* p;
};
Write two implementations of the copy constructor.
The first should perform a shallow copy of the provided
instance of Copy, whereas the second should
perform a deep copy.
Consider the code below:
#include <iostream>
using namespace std;
class Des {
public:
Des(int x) { this->x = x; cout << x << endl; }
~Des() { cout << x << endl; }
private:
int x;
};
void test() {
Des d(1);
}
int main() {
Des* p = new Des(0);
test();
delete p;
return 0;
}
If the above code is compiled and run, what is the output?
In one of your labs, you implemented a function in C with the following prototype:
int compare(card* c1, card* c2);
When you implemented this in C++, the above code ended up having a prototype similar to the one below:
int compare(Card* c);
Why aren't there two parameters in the C++ version?
Consider the class definition below:
class Simple {
public:
Simple(int x) { y = x; }
int getY() const { return y; }
void setY(int x) { y = x; }
private:
int y;
};
Rewrite the code above to explicitly use this.
Name and describe two operations which are typical of a stack ADT.
Name and describe two operations which are typical of a queue ADT.
Consider the following code:
#include <iostream>
using namespace std;
class Stack {
public:
Stack(); // creates a new, empty stack
void push(int item); // adds an item to the stack
int pop(); // removes an item from the stack
};
class Queue {
public:
Queue(); // creates a new, empty queue
void enqueue(int item); // adds an item to the end of the queue
int dequeue(); // removes an item from the front of the queue
};
int main() {
Stack s;
Queue q;
s.push(1);
s.push(2);
s.push(3);
q.enqueue(4);
q.enqueue(5);
q.enqueue(6);
for(int x = 0; x < 3; x++) {
cout << s.pop() << " " << q.dequeue() << endl;
}
}
If the program above is compiled and run, what is the output?
In ??? testing, one has access to the source code.
In ??? testing, one does not have access to the source code.
Consider a linked-list holding the elements 1,
2, and 3 in that order. Draw a memory
diagram illustrating the same list after adding 0 as
the first node and 4 as the last node. Be sure to
show the head pointer. You need only show the diagram
of the list after all the operations have occurred.
Consider the code below:
class Node {
public:
Node(int i) { item = i; next = NULL; }
int getItem() const { return item; }
Node* getNext() const { return next; }
void setItem(int i) { item = i; }
void setNext(Node* n) { next = n; }
private:
int item;
Node* next;
};
class List {
public:
List(); // creates a new, empty list
void addItemToFront(int item);
int getLargestItem() const;
private:
Node* head;
};
Assume that the constructor for the empty list and
addItemToFront have been implemented
elsewhere. Implement the getLargestItem
method, which should return the largest item in the list.
If the list is empty, it should return -1 (even though
this is a poor solution).