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.