CISC220, 06J, Midterm Exam 1—July20, 2006


Write your name only on this page

Name as you are called in class_____________________________________

Name as on official roster (if different) ________________________________

UD email address_________________________________________________

1. For each of the following sections of code, provide the complexity of the running time,
   e.g. O(1), O(log n), O(n), O(n log n), O(n²).
   1. (5 pts)

      int result = 0;
      
      for (int i=n; i>0; i = i/2)
      {
         result ++;
      }
      return result;
              

   2. (5 pts)

      int result = 0;
      
      for (int i=0; i<5; i++)
      {
         cout a[i];
      }
      
      

      
      
      
2. (10 pts) Suppose you are going to write a program that accepts, as input, a starting odometer reading, and ending odometer reading, the number of gallons of gas used, and the price per mile. Explain how you might go about writing this program using a "conventional" programming approach, vs. a "test-driven development" approach.
   
   Your explanation should convey enough detail so that the grader can know that you understand test-driven development, but not any more detail than that.
   
   
3. (10 pts) Describe (in English and/or pseudocode) how to use a stack to check for matching HTML tags.
   
   
   
   
   
4. (20 pts) Write ONLY THE CLASS DECLARATION (i.e. the .h file) for a stack class that would be appropriate for solving the problem described above (using a stack to check for matching HTML tags). Include the private data members, and also indicate the running time of each of your member functions (i.e. O(1), O(n), etc.). Use variable length C strings allocated on the heap for representing the HTML tags.
   
   Include member function prototypes for the "big three" (copy constructor, overloaded = operator, and destructor).
   
   
5. (10 pts) Now write only the definition of the Copy Constructor as it would appear in the .cc file for the class you just defined.
6. (10 pts) Describe what is meant by an "Abstract Data Type", and (10 pts) give two examples of Abstract Data Types, along with the operations that are usually associated with those data types.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
7. (10 pts) Fill in the code for a selection sort. If you use an additional "helper function", write the code for that function also.
   
   (10 pts) Then show what the effect of your code is on the array that follows (i.e., fill in the successive values that end up at each pass through the array). Use the variable "i" for your outer loop (i.e the "passes" that selection sort makes), and show the value of i for each pass.
   
   Use only as many rows in the table as your implementation performs (you might not need all of the rows.)
   
   

   original values	5	9	3	2	6
   i =

   
   
   void selectionSort(int a[], int n)
{
























}

   

End of Exam, total points = 100