1.A push(3) operation into a stack yields ( )

A.		top, ... first , 3
B.		3, top, ... , first

2. An algorithm takes 0.5ms for input size of 100. How long will it take for input size of 500 if the running time is (i) Linear, and (b) O(NlogN)?

A.		6 and 4 +logN
B.		5 and 5 + NlogN
C.		5 and 5+some value
D.		4 & 6 +logN

3.Analyze the following algorithm S and provide its worst case time complexity measures if 1) the pivot p splits the array and 2) if the pivot p is at the end. Data is a global array of elements of type keytype. Initial call to S is made: S(0, n)

public static void S (index i, index j) {

index p;

if (j > i) {

p = subAlgoS (i, j);

S (i, p - 1);

S (p + 1, j);

}

}

public static void subAlgoS (index i, index j) {

index x, y, p;

keytype z;

z = Data[i];

y = i;

for (x = i + 1; x <= j; x++)

if (Data[x] < z) {

y++;

exchange Data[x] and Data[y];

}

p = y;

exchange Data[i] and Data[p];

return p;

}

A.		O(nlogn) and O(nlogn)
B.		O(n^2) and O(n^2)
C.		O(n^2) and O(nlogn)
D.		O(nlogn) and O(n^2)

4. If an expression tree contains 4 operators, it will contain _______ operands.

5.A simple and direct COUT statement is enough to print out elements from all ADTs. ( )

		A.True
B.		False

6. Algorithm A uses 10nlog n operations, while algorithm B uses n^2 operations. Which of these values is approximately n_0 such that A is better than B for n>=n_0?

	A.	n_0 cannot be determined
	B.	58 or log n <=n/10
	C.	n_0 = 0 or n= 0
	D.	n_0 =58n/10