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.

1. 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:
   pass 2:
   pass 3:
   pass 4:
   pass 5:
   pass 6:

2. 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();
   

   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)?

   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()?

3. 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.
4. Write a similar function that takes a list<int> argument instead of a vector<int>.
5. 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.
   1. 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)?
   2. 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?
   3. Answer the previous question for 100,000 objects instead of 100.
6. 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:
   
   

   }
   
   test& test::operator=(const test& rhs)
   {   // AND 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;
   }
   

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

DePauw University, Computer Science Department, Fall 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated