Practice Exam 1 - CSC 222: Data Structures and Algorithms, Fall 2006

Practice Exam 1

This exam is open-book and open-note. Please allow some time to check your work. If you need extra space, write on the back.

Show the result after each pass of Insertion Sort on the input E A S Y O N E, where the letters will be sorted in alphabetic order. Fill in only the letters which have moved to a new position from the previous row.

	0	1	2	3	4	5	6
input:	E	A	S	Y	O	N	E
pass 1:	A	E
pass 2:			S
pass 3:				Y
pass 4:			O	S	Y
pass 5:			N	O	S	Y
pass 6:			E	N	O	S	Y

What is the output of the following sequence of operations if x is declared as a stack<char>?


x.push('h');  x.push('e');  x.push('l');
cout << x.top();  x.pop();
cout << x.top();  x.pop();
x.push('l');  x.push('o');
cout << x.top();  x.pop();
cout << x.top();  x.pop();
cout << x.top();  x.pop();

leolh

What would the output be from the same sequence if x were declared as a priority_queue<char> (where characters later in the alphabet have higher priority)?

lhole

Finally, what would the output be from the same sequence if x were declared as a queue<char> and the x.top() operations were replaced by x.front()?

hello

Write a C++ function int countBelow(const vector<int> &v, int n) which will return the number of items strictly less than n found in the vector v. You should not assume anything about the ordering of the items in the vector.

int countBelow(const vector<int> &v, int n)
{
    int count = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] < n) count++;
    }
    return count;
}

Or, use the iterator version below, with the appropriate type changes.

Write a similar function that takes a list<int> argument instead of a vector<int>.

int countBelow(const list<int> &v, int n)
{
    int count = 0;
    for (list<int>::const_iterator it = v.begin(); it != v.end(); it++) {
        if (*it < n) count++;
    }
    return count;
}

For each of the following questions, be sure to justify your answer. Just saying the name of the algorithm without giving a reason will not get full credit.

Which of the sorting algorithms discussed in class would be the best choice for re-sorting a telephone directory containing 100,000 entries, after adding 100 new entries at the end (that is, the 100 new entries are not in their correct sorted positions yet, although the rest of the directory is already in order)?
Insertion sort -- on nearly-sorted data, it is O(N).
Which of the sorting algorithms discussed in class would be the best choice for sorting 100 complex objects, where exchanging a pair of objects requires moving thousands of bytes of data?
Selection sort -- it only does (at most) N-1 exchanges.
Answer the previous question for 100,000 objects instead of 100.
Priority queue sort (note for 2006: we haven't covered priority queues yet) -- it does O(N log N) compares and exchanges, which is much better than the O(N²) compares for either insertion or selection, and not much worse than the O(N) exchanges for selection sort.

Fill in the two missing pieces of the following code so that it handles the dynamically-allocated storage correctly (the context here is that some systems limit the amount of space for stack-allocated variables, so you may not be able to declare a local variable such as int a[N] when N is a million; instead, you can declare a to be an object of class test, and the only space required on the system stack will be for the data pointer--the million ints will be allocated from the heap):

const int N = 1000000;

class test {
public:
    test() : data(new int[N]) { }
    test(const test& x);
    ~test();
    test& operator=(const test& rhs);
    int& operator[](int i) { return data[i]; }
    const int& operator[](int i) const { return data[i]; }
private:
    int *data;
};

test::test(const test& x) : data(new int[N])
{   for (int i = 0; i < N; i++)  data[i] = x[i];
}

test::~test()
{   // FINISH THIS:

    delete[] data;

}

test& test::operator=(const test& rhs)
{   // AND THIS:

    for (int i = 0; i < N; i++) data[i] = rhs[i];
    return *this;

What will be the output from the following program using this class?

void f(test x, test& y) { x[42] = 2 * y[42];  y = x; }

int main()
{   test a;
    a[42] = 17;
    test b = a;
    f(a, b);
    cout << a[42] << " " << b[42] << endl;
}

17 34

How many times will the test destructor be called in the above program?

3 times -- once each for a and b at the end of main, and once for x (which was passed a copy of a) at the end of f.