1. suppose that we are using a stack to check for balanced delimiters in the following expression:

((a+b)-({c}+d)*f)

What would be the content of the stack during the scan of the expression (suppose that the right most delimiter is at the top of the stack):

a (

((

(

((

(({

((

(

empty ===>The expression is balanced

b

(

()

({

({}

(

===> The expression is unbalanced

c

(

((

(()

(()({

(()({}

(()({})

(()({}))

==> The expression is balanced

d

((

(

({}

()

==>The expression is balanced

2.

Which of the following are true, regarding recursion and recursive algorithms? (Select all that apply, but be cautious -- points will be deducted for incorrect answers!).

	a.	In efficient recursion, each recursive call should operate on a smaller version of the original problem.
	b.	A recursive solution is always more efficient than its corresponding iterative solution.
	c.	All recursive algorithms have O(log N) running times, due to the repeated halving property of recursion.
	d.	A recursive algorithm can often be rewritten in an iterative manner using a stack.

3.Given the following array:

a=[6 9 10 15 18 20 25]

How many comparisons the binary search algorithm performs to look for the item "11" ?

		2
		3
		1
		None, item 11 is not in the array

4.Which of the following are true concerning the Map data structure (check all that apply)?

	a.	duplicate items are not allowed
	b.	duplicate keys are allowed
	c.	a given key may map to only one item
	d.	a given key may map to more than one item
	e.	items are not associated with keys
	f.	duplicate items are allowed
	g.	items are associated with keys
	h.	duplicate keys are not allowed