CSCI-1200 Data Structures
Test 2 — Practice Problems
Note: This packet contains practice problems from three previous exams. Your exam will contain approximately
one third as many problems.
1
1 Checking It Thrice [ / 22 ]
Each row in the table below contains two statements labeled A and B. Put a checkmark 2 in up to three
boxes per row. Each correct checkmark is worth +1, each blank checkbox is worth +0, and to discourage
random guessing each incorrect checkmark is worth −2 points. Your score on this problem will not go
below 0. Only two A statements are true because of their corresponding B statements.
A is B is A is true
because of B
Statemtents True False True False
2 2 2 2 2
A: STL vector erase() may invalidate an iterator.
B: For programs that need to do a lot of erasing, you should
use an STL list instead of an STL vector.
2 2 2 2 2
A: A memory debugger like Valgrind or Dr. Memory can
help find leaked memory.
B: A memory debugger like Valgrind or Dr. Memory shows
you the line you should have written delete/delete[] on to fix
the memory leak.
2 2 2 2 2
A: Vec push back() on average takes O(n)
B: Vec push back() sometimes has to allocate a new array
that’s 2*m alloc
2 2 2 2 2
A: If std::list::iterator itr points to a valid location in
list l1, writing l1.erase(itr)++ may cause a memory error.
B: Incrementing the end() iterator in any STL list has
undefined behavior
2 2 2 2 2
A: STL lists / dslist do not have operator[] defined
B: Using operator[] on a pointer is the same as using pointer
arithmetic and then dereferencing the result.
2 2 2 2 2
A: Assuming std::vector::iterator itr points to a
valid location in vector v1, writing v1.insert(itr,5);
std::cout << *itr; will always cause a memory error.
B: std::vector::insert() returns an iterator because
insert() may invalidate the iterator passed in.
2 2 2 2 2
A: If std::vector v1 is an empty vector, v1.end()--
will result in undefined behavior.
B: Decrementing the end() iterator in any STL vector has
undefined behavior.
2 2 2 2 2
A: If a recursive function does not use array indexes or
pointers, and there’s a segmentation fault in that function, it
means you must have infinite recursion.
B: Infinite recursion can result in a segmentation fault.
2 2 2 2 2
A: Writing int* x=5; will result a compiler error.
B: Memory addresses are not numbers, so you cannot store
a number in a pointer.
2 2 2 2 2
A: Writing dslist x; x.push back(5);
dslist y = x; will not result in calling
y.operator=(x) even though there is an = sign in the
last statement.
B: operator= can only be called on objects that are already
constructed.
2
2 Hop Lists [ / 37 ]
In this problem we will consider “hop lists”, a made-up data structure based on “skip lists”. A hop list is
a linked list using the Node class listed below. For simplicity we will not make it templated and our Nodes
will only contain integers. The next pointer works the same way as in the singly and doubly-linked lists
we have studied so far. However, the prev odd pointer is NULL for the 1st element in the list, and for all
other elements in an odd position (3rd in the list, 5th in the list, and so on), the prev odd pointer points
two elements back. There is a diagram below to illustrate how this would look for a list with five nodes
containing the values 10, 20, 30, 40, 50 in that order.
class Node{
public:
Node(int v) : val(v), next_(NULL), prev_odd_(NULL) {}
Node(int v, Node* next) : val(v), next_(next), prev_odd_(NULL) {}
int val;
Node* next_;
Node* prev_odd_;
};
val 10 20 30 40 50
next_
prev_odd_
In the following sections you will write two different versions of AddPrevOddPointers. Both versions take
a Node pointer called head which points to the first Node in a hop list, and a Node pointer called tail.
After the function is done, all of the prev odd pointers should be set correctly, and tail should point to
the last element (furtherst from head) that is in an odd position. If there are not at least 3 Nodes in the
list, then tail should be NULL. You can assume that all Nodes have their next pointer correctly set before
AddPrevOddPointers is called.
An example of calling the function might look like:
//Start a new list
Node* head = new Node(2561);
/////Code to make the rest of the nodes/link forward omitted
PrintListForward(head); //"Printing forward list..."
Node* tail;
AddPrevOddPointers(head,tail);
PrintHopListBackwards(tail); //"Printing backwards..."
std::cout << std::endl;
Here are two examples:
Printing forward list: 10 20 30 40 50 60 70 80 90 100 110
Value at tail: 110
Printing backwards every-other list: 110 90 70 50 30 10
Printing forward list: 31 32 33 34 35 36 37 38 39 301
Value at tail: 39
Printing backwards every-other list: 39 37 35 33 31
3
2.1 AddPrevOddPointers (Recursive Version) [ / 18 ]
Write a version of AddPrevOddPointers that uses recursion.
sample solution: 23 line(s) of code
4
2.2 AddPrevOddPointers (Iterative Version) [ / 15 ]
Write a version of AddPrevOddPointers that does not use any recursion.
sample solution: 20 line(s) of code
2.3 AddPrevOddPointers Complexity [ / 4 ]
If the hop list has n elements, what is the running time order notation of the iterative version of
AddPrevOddPointers? What about for the recursive version?
5
3 Shape Overlays [ / 14 ]
Given a series of Shape objects in a vector shapes, the code below should allocate and fill a 2D
dynamic array of integers, overlay that represents an overlay of all the shapes. If all of the shapes were
to be put on top of each other, an overlay would show for every position (x,y) how many shapes had a
pixel on at that position. You can assume that shapes is not empty and each shape is at least 1x1 in size.
The coordinates use the Cartesian coordinate system, where (0,0) is the origin, x = 1 is to the right of the
origin, and y = 1 is above the origin. You can also assume non-negative x,y coordinates for everything and
that the overlay starts with the bottom left corner at (0,0). The example shapes and overlay output have
(0,0) in the bottom left corner for easy visualization.
Shape 1 (outline rectangle)
Printing 4 x 4 overlay:
XXXX
X..X
X..X
XXXX
Lower left is at (0, 1)
Shape 2 (outline rectangle)
Printing 4 x 4 overlay:
XXXX
X..X
X..X
XXXX
Lower left is at (1, 1)
Shape 3 (filled in rectangle)
Printing 5 x 2 overlay:
XX
XX
XX
XX
XX
Lower left is at (1, 0)
Printing 5 x 5 overlay:
13321
12111
12111
13321
01100
class Point{
public:
Point(int x=0, int y=0) : m_x(x), m_y(y) {}
int m_x, m_y;
};
class Shape{
public:
bool pixelOn(int x, int y) const;
void getDimensions(int& width, int& height, Point& corner) const;
...
};
(1,0)
(0,1)
(1,1)
+ +
(0,0)
int** overlay
=
Shape 1 Shape 2 Shape 3
void MakeOverlay(int**& overlay, int& height, const std::vector& shapes){
int shape_height, shape_width, width;
height = width = 0; //Start by assuming a 0x0 overlay
Point shape_corner; //Holds the lower left corner of the shape
//Cycle through each shape and find the further-upper-right point
for(unsigned int i=0; i