Datastructures Midterm

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...