1. In processing a prefix expression, which part of the process was recursive?

		Finding the end of a prefix expression
		Checking the syntax of the prefix expression
		Determining the complexity of the prefix expression
		Calculating the value of the prefix expression

2.

Which of these describes a postfix expression?

An expression where an operator precedes its operands

An expression where an operator follows its operands

None of these

An expression where every binary operator appears between its operands

3.

Which of these is the grammar for a languate AnBn, a string that has n consecutive A's followed by n consecutive B's?

= empty string | A B | AA BB | ...

= empty string | A B

= A B

= empty string | A B | AABB | AAABBB | ..

4.

What does the following describe:

The first and last characters of string s are the same String s minus its first and last characters is a palindrome

		a recognition algorithm for a palindrome
		a grammar
		a palindrome
		the base case of a recursive grammar

5.

What can be done to an infix expression to make it easier to evaluate in a program?

Nothing, they are always very complex to process

Perform backtracking

Add all of the parenthesis making it a fully parenthesized infix expression

Convert to prefix, then to postfix, then it can be easily evaluated

6.

Which of these does not belong in the grammar for the language C++ Identifiers?

		= * | / | + | -
		= 0 | 1 | ... | 9
		= a | b | ... | z | A | B | ... | Z | _
		= | |

7.

Which of these describes an infix expression?

None of these

An expression where an operator precedes its operands

An expression where an operator follows its operands

An expressionwhere every binary operator appears between its operands

8.

The strategy of retracing steps in reverse order and trying sequences already explored to expose new sequences is called _____________.

		none of these, it is nonsense
		backtracking
		forwardtracking
		exploring