Submitted by: Submitted by forgetx2
Views: 239
Words: 997
Pages: 4
Category: Science and Technology
Date Submitted: 10/11/2012 07:38 PM
Sample Midterm Exam
Name:______________________________________________
Problem
1
2
3
4
5
Total
Points
Possible
10
10
10
10
10
50
Score
When answering questions, please state any and all assumptions you are making.
1. (10 pts) For the following program fragments, give an analysis of the running time
(Big-Oh will do. Note that your answer should be as tight as possible.)
a. (2 pts)
P = 10000;
for ( int i = 1; i < n; i ++)
for ( int j = i; j < n*n; j ++)
if (i > 10 )
for (int k = 0; k < P; k++)
sum++;
O(n3)
b. (2 pts)
int maxSum = 0;
for( int i = 0; i < n; i++ )
for( int j = i; j < n; j++ )
{
int thisSum = 0;
for( int k = i; k maxSum ) maxSum = thisSum;
}
O(n3)
c. (2 pts)
int func(int x, int exp)
{
If (exp = =0)
return 1;
else
return x * func(x, exp-1);
}
Recurrence Relation: T(n) = T(n-1) + C
O(n)
d. (4 pts) Which function grows faster: n log n or (log n)n (Explain your answer)
Taking ‘log’ of both sides
log n log n
vs.
log (log n)n
log 2 n
vs.
n log log n
Since log k n, for k > 0, is o(n), n log log n grows faster.
Thus, (log n)n grows faster.
2. (10 pts) List, Stack and Queue
(a) (5 pts) Convert the following infix notations to postfix notations
I. a / ( b + c * d – e )
abcd*+e-/
II. ( a / ( b – c + d )) * ( e – a ) * c
abc–d+/ea-*c*
III. a / b –c +d * e – a * c
ab/c–de*+ac*(b) (5 pts) Given two linked lists, L1 and L2, write a recursive function to compare the
length of the lists. Your recursive function will return three possible values: 1, 0, or 1, which denote respectively that the length of L1 is greater than, equal to, or less
than the length of L2. Note that the length of a linked list is defined as the total
number of nodes in the list. Assume that a linked list node is defined by the
following structure:
class LinkedListNode
{
int element; // data in the node
LinkedListNode next; // link to the next node
}
int CompLength(LinkedListNode...