CISC220, 06J, Midterm Exam 1—June 28,29 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. (4 pts)

      for (int i=0; i<n; i++)
        cout << a[i] << endl;
      

   2. (4 pts)

      for (int i=0; i<n; i++)
      {
          for int j=0; j<n; j++)
          { 
            cout << b[i][j] << " ";
          }
          cout << endl;
      }

   3. (4 pts)

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

   4. (4 pts)

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

   5. (4 pts) Given the following struct definition:

      struct Node
      {
         int data;
         Node *next;
      };

      and given that head is a variable of type Node * that points to a list of n nodes, analyze the time complexity of the following code:

      
      
      for (Node *p = head; p!=NULL; p=p->next)
      {
         cout << p->data << endl;
      }
      

2. Below you will find a listing for a main program, with one function definition. Parts of this file are missing. Fill in the missing parts. Sample output is also given.

   Fill in the blanks in the code

   // twoToTheN.cc 181 Final Exam
   // Calculate 2 to the nth power
       
   #include <iostream>
   using namespace std;
   
   int twoToTheN(int n)
   {
     //** (a) (3 pts) handle error case: if a negative value is passed in,
     //** print an error message and stop the program immediately
       
        
        
        
        
        
     //** (b) (8 pts) Insert your code here for the two parts that a correct recursive
     //** function typically needs:
     
       
        
        
    }
    
   int main(void)
   {
     int n;
     cout << "Enter n: ";
     cin >> n;
     cout << twoToTheN(n) << endl;
     return 0;
   }
   

   Sample output:recursion/twoToTheN.output

   	
         Script started on Tue Jun 27 13:38:45 2006
         %make twoToTheN
         CC -o twoToTheN twoToTheN.cc 
         %./twoToTheN
         Enter n: 4
         16
         %./twoToTheN
         Enter n: 3
         8
         %./twoToTheN
         Enter n: -2
         Fatal error: passed negative value to twoToTheN 
         %./twoToTheN
         Enter n: 0
         1
         %./twoToTheN
         Enter n: 16
         65536
         %exit
         exit
         script done on Tue Jun 27 13:39:14 2006
   

3. (4 pts) What is the time complexity of one call to the recursive function defined in the previous problem?

4. Below you will find a listing for a main program, with one function definition. Parts of this file are missing. Fill in the missing parts. Sample output is also given.

   Fill in the blanks in the code from: recursion/printArray.cc

       
   // printArray.cc 181 Final Exam
   // Calculate sum of digits (provided n is non negative)
   #include <iostream>
   using namespace std;
   void printArray(int nums[], int count)
   {
     //** (a) (8 pts) Fill in a recursive definition for this function
     //** Label the base case and recursive step with comments
     //** indicating which is which.
       
        
        
        
        
        
        
        
        
        
   }
   
   int main(int argc, char *argv[])
   {
     if (argc < 2)
     {
        cerr << "Usage: " << argv[0] << " a[0] a[1] a[2] ... a[n-1]" << endl;
        exit(1);
     }
     int n = argc - 1; // size of the array
   
     //** (b) (3 pts) Fill in a line of code that allocates an array of integers
     //** called a, that lives in space on the heap. The array should
     //** have exactly n elements in it.
       
   
   
   
        
     // fill in the array from the command line arguments
     for (int i=0; i<n; i++)
        a[i] = atoi(argv[i+1]);
     
     printArray(a,n);
     return 0;
   }
         

   Sample output:recursion/printArray.output

       Script started on Tue Jun 27 13:42:27 2006
         %make printArray
         CC -o printArray printArray.cc 
         %./printArray 2 4 5
         nums[0]=2
         nums[1]=4
         nums[2]=5
         %./printArray 2 3
         nums[0]=2
         nums[1]=3
         %./printArray 1 3 6 7
         nums[0]=1
         nums[1]=3
         nums[2]=6
         nums[3]=7
         %./printArray 
         Usage: ./printArray a[0] a[1] a[2] ... a[n-1]
         %./printArray -1
         nums[0]=-1
         %exit
         exit
       script done on Tue Jun 27 13:43:05 2006
       
        
        
    
        
         

5. (4 pts) What is the time complexity of the printArray function defined in the previous problem?
   
   
   
   
6. (5 pts) If the programmer does not provide a copy constructor for a class, the compiler creates a copy constructor. Describe what this "compiler provided" copy constructor does, and give a specific example of a case where such a "compiler-provided copy constructor" would be perfectly appropriate.
   
   
   
   
   
   
   
   
   
   
   
   
   
7. (10 pts) Now describe a case where such a compiler provided copy constructor is not appropriate, and why. Be specific, but also consise—write just enough detail that I can know for sure that you understand the point.
   
   
   
   
   
8. (5 pts) Suppose the class Foo_C has exactly one private data member called name, which is a pointer to a C-string allocated from the heap. Write the definition of the destructor for this class, as it would appear in the file foo.cc.
   
   
   
   
   
   
   
   
   
9. (10 pts) For the same class Foo_C, write the definition of an overloaded assignment operator as it would appear in the file foo.cc.
   
   
   
   
   
   
   
   
   
10. Suppose I have the following struct definition as a private definition inside class PersonList_C.
    
    

    struct Node_S
    {
       char *name; // a name, stored as a C string
       Node_S *next;
    };
      

    An object of class PersonList_C maintains a list of such nodes, in no particular order. Duplicate names are permitted.
    
    1. (4 pts) The class will need to maintain a pointer to the head of this list. Is it also necessary to maintain a tail pointer, yes or no? Explain your answer.
       
       
       
       
       
    2. (5 pts) Based on your answer to part a, write a member function void add(const char * const newName); that adds one name to the list. Write the function definition as it would appear in the file personList.cc
       
       
       
       
       
       
       
       
       
       
       
    3. (5 pts) Based on your answer to part a, write a function int countNames(const char * const nameToCount) const; that indicates how many instances of a particular name are in the list. For example, countNames("Mary") would return how many times the name "Mary" appears in the list.
       
       
       
       
       
       
       
       
    4. (6 pts) In the function prototype below, the keyword const appears three times. In each case, the meaning is slightly different. Explain the meaning of each appearance of const.
       int countNames(const char * const nameToCount) const;
       
       
       
       
       
       

End of Exam, total points = 100