Chapter 5 Questions
Multiple Choice
1. What program sees whether a given string is a member of the language?
a. The compiler
b. A word processor
c. An encryption program
d. A text editor
2. What states the rules of a language?
a. The compiler
b. The grammar
c. The English teachers
d. The computer teachers
3. From the symbols of grammar given by the text, what is used to signify “x or y”?
a. x ^ y
b. x % y
c. x | y
d. x && y
4. Given the expression a + b. What type of expression is this?
a. prefix
b. postfix
c. outfix
d. infix
5. Term “infix” indicates that every binary operator appears where?
a. between its operands
b. after its operands
c. before its operands
d. before each operand
6. In what type of expression does an operator precede its operands?
a. postfix
b. prefix
c. outfix
d. infix
7. Given infix expression a + b Which of the following is the equivalent postfix expression?
a. b + a
b. + a b
c. a b +
d. + a b +
Chapter 5 Questions
8. Given the infix expression a + (b * c) Which of the following is the equivalent prefix
expression?
a. a b c * +
b. c * b + a
c. a b c * +
d. + a * b c
9. What do we call the strategy used for guessing at a solution and backing up when an impasse is
reached?
a. backtracking
b. impasse resolution
c. modified guessing
d. back guessing
10. Which of the following has the more involved grammar?
a. postfix
b. infix
c. prefix
d. reflex
Chapter 5 Questions
True or False
1. All programs are strings, but not all strings are programs.
2. The language Algebraic Expressions is the set of strings that meets certain rules of syntax and
that definition also gives the rules of the syntax.
3. A given word, s, is a palindrome if and only if, the first and last characters of s are the same and s
minus its first and last characters is a palindrome.
4. The stricter a definition, the harder it is to recognize a syntactically legal expression.
5. The following expression is a prefix expression + a b – c d
6. Subproblems that a recursive search solution generates need not reach a base case.
7. You can use induction to prove that a recursive algorithm either is correct or performs a certain
amount of work.
8. Little relationship exists between mathematical induction and recursion.
Chapter 5 Questions
Short Answer
1. According to the text of what elements make up a language such as English or C++ ?
2. It is possible to write a straightforward recursive algorithm that determines whether a given string
is in the language. Such an algorithm is called a(n) ____________________________ for the
language.
11. Given this syntax diagram:
It is a diagram for what in the
C++ language?
3. Give two examples of words that are palindromes
4. To use infix expressions, what other rules does this convention necessitate?
5. Given the infix expression (( a + b) * c Convert it to a prefix expression.
6. What two things must be true for an expression to be in prefix form?
7. Evaluate this postfix instruction 3 5 + 2 *
8. Evaluate this postfix expression 67 42 – 5 /
9. Evaluate this postfix expression 3 16 6 – * 5 /
10. Evaluate this prefix expression + 6 * – 3 2 4
11. Evaluate this prefix expression: * 4 – 5 6
12. What possible wrong choices might an algorithm make when searching for a sequence of flights
between cities?
Chapter 5 Questions
13. How many moves are required to solve the Towers of Hanoi problem with 5 disks?
14. What are the three steps for a proof by induction?