Name_________________
                         CIS 350 Exam 1
                           Winter '97
(2 points)

 1. Use the rules for order arithmetic to evaluate:

      O((n + 2) * (2n + log(n) - 50))





(3 points)
 
 2. Describe circumstances under which the big-Oh complexity
  for searching a list would be O(1) rather than O(n).












 3. What is an abstract data type?












 
 4. Describe how object-oriented programming supports code
    reuse.

 

 
 
 
 
 

 
                                            Name_________________

 5. Briefly describe the operations required to simulate a 
    recursive function call.

 
 
 


 
 
 



6.  Briefly describe how the use of buckets can improve the 
   average search complexity for a hash table.












(4 points)

 7. Determine the big-Oh complexity for the algorithm below.
    Justify your answer, assume S is an instance of class Stack.

      cin >> N;
      for (I = 1; I <= N; I++)
      {
        cin >> X;
        S.push(X);
      }

      Y = S.stacktop( );
      while (!S.Empty( ))
      {
        S.pop(X);
        if (X > Y)
          Y = X;
      }
      cout << Y;





                                            Name_________________ 
                   
8. Using the hash function H(key) = key mod 5, and 
  linear probing, show the contents of the hash table 
  (array[4] having subscripts 0 to 4) after hashing the
  keys: 37, 17, 7, 12 (in the order shown).



















 9. Assuming these methods have the actions described in class, 
    draw pictures showing the contents of List1 and List2 after 
    the execution of the following statements.

      LinkList List1;
      LinkList List2;
      List1.Insert(3);
      List1.InsertAfter(4);
      List1.DeleteNode(Q);
      List2.Insert(5);
      List2.Insert(Q);
      List2.DeleteNode(Q); 


















                                           Name_________________
(6 points)

10. Write a non-recursive version of the function shown below.

      int Fcn(NodePtr L)
      {
        if(L == NULL)
          return 0;
        else
          return L->Info + Fcn(L->Next);
      }  
       
   
 












11. Write a function which takes as input a queue of characters 
    containing an infix expression and uses a stack to check the 
    expression for correctly nested parentheses (the function 
    should return 1 if yes and 0 if not). You may assume the 
    existence of declarations for classes Stack and Queue and 
    that the usual constructors and methods have been defined for 
    each: EmptyStk, EmptyQ, Pop, Push, Enq, Deq, StackSize,
    QueueSize.