Chapter 6 Questions
Multiple Choice Questions
1. What is the corrected input if the line
yww<dshr<<wd<e
is typed on a keyboard, where < represents the backspace character?
a. ywdswe
b. ywwdwde
c. ywdshwe
d. ywdswd
2. If the array
6, 2, 7, 13, 5, 4
is added to a stack, in the order given, which number will be the first number to be removed from the stack?
a. 6
b. 2
c. 5
d. 4
3. The item that is removed first from a stack is called the ______ of the stack.
a. front
b. top
c. base
d. prime
4. If the array
6, 21, 35, 3, 6, 2, 13
is added to a stack, in the order given, which of the following is the top of the stack?
a. 2
b. 6
c. 3
d. 13
e. 35
5. What behavior does the ADT stack exhibit?
a. first in, first out
b. first in, never out
c. last-in, first-out
d. last in, last out
6. The ______ operation of the ADT stack adds an item to the top of the stack.
a. isEmpty
b. push
c. pop
d. peek
Chapter 6 Questions
7. The ______ operation of the ADT stack retrieves and then removes the top of the stack.
a. isEmpty
b. push
c. pop
d. peek
8. The ______ operation of the ADT stack retrieves the top of the stack, but does not change the stack.
a. isEmpty
b. push
c. pop
d. peek
9. Which of the following operations of the ADT stack accepts a parameter?
a. push
b. isEmpty
c. peek
d. destroyStack
10. Which of the following strings contains balanced braces?
a. ab{cde{fg}hi{jkl}
b. ab{cde{fghi}j}kl}
c. {abc{de}{fg}hij}kl
d. {ab{cde{fgh}ijkl}
11. If a stack is used by an algorithm to check for balanced braces, which of the following is true of a balanced
braces string once the end of the string is reached?
a. the stack is empty
b. the stack has one “{”
c. the stack has one “}”
d. the stack has one “{” and one “}”
12. Given the language L, where:
L = {w$w’ : w is a possibly empty string of characters other than $, w’ = reverse(w) }
which of the following strings is NOT in L?
a. XY$YX
b. Z$Z
c. $
d. XYZ$ZXY
13. Which of the following is NOT true about converting infix expressions to postfix expressions?
a. the operands always stay in the same order with respect to one another
b. the operators always stay in the same order with respect to one another
c. an operator will move only “to the right” with respect to the operands
d. all parentheses are removed
14. Which of the following is the postfix form of the infix expression: (a + b) * c / d
a. a b + c * d /
Chapter 6 Questions
b. a b * c / d +
c. a + b * c / d
d. a b + c d * /
15. What is the value of the following postfix expression: 5 2 – 8 4 + *?
a. -9
b. 28
c. 35
d. 36
16. In a graph that represents the flight map for the HPAir problem, if a flight exists from city C1 to city C2, C2 is
said to be ______ C1.
a. adjacent to
b. similar to
c. related to
d. bordering
17. In a graph that represents the flight map for the HPAir problem, if a flight exists from city C1 to city C2, the
path from C1 to C2 is called a _______.
a. relation
b. neighborhood
c. directed path
d. connecting path
18. ______ are considered when choosing the next city to visit in a stack-based nonrecursive solution to the HPAir
problem.
a. All cities
b. All unvisited cities adjacent to the destination city
c. All cities adjacent to the city on the top of the stack
d. All unvisited cities adjacent to the city on the top of the stack
19. An algorithm that uses a stack to implement a nonrecursive solution to the HPAir problem reaches the
conclusion that there is no path from an origin city to a destination city only after ______.
a. the algorithm has backtracked to the origin
b. the algorithm has backtracked to the origin and there remain no unvisited cities to fly to from the origin
c. the algorithm has reached a city and there remain no unvisited cities to fly to from that city
d. the algorithm has reached the destination and there remain no unvisited cities to fly to from the
destination
20. Typically, ______ are used by a compiler to implement recursive methods.
a. linked-lists
b. arrays
c. stacks
d. queues
21. When a recursive call to a function occurs, the compiler’s implementation must remember all of the following
information EXCEPT ______.
a. values of parameters
b. values of local variables
Chapter 6 Questions
c. values of global variables
d. a reference to the point from which the recursive call was made
22. The ______ operation of the ADT stack retrieves and then removes the top of the stack.
a. isEmpty
b. push
c. pop
d. peek
23. A stack is initially empty, then the following commands are performed:
push 5, push 7, pop, push 10, push 5, pop
which of the following is the correct stack after those commands (assume the top of the stack is on the
left)?
a. 5 10 7 5
b. 5 10
c. 7 5
d. 10 5
26. Consider the peek() operation for the ADT Stack as described by the author. What is its output?
a. true or false
a. there is no output
b. the object that is at the top of the stack
c. the number of items left on the stack
28. Which of the following is a good analogy of the ADT Stack?
a. people standing in a cafeteria line
b. a paper bag with colored poker chips
c. a group of people playing musical chairs
d. a pile of textbooks on your desk
29. Consider the push(newEntry) operation of the ADT Stack. What is the output of the operation?
a. true or false
b. there is no output
c. the object that is at the top of the stack
d. the number of items left on the stack
30. Why would axioms be specified for an ADT.
a. to determine the cost of development
b. specify the behavior of the ADT
c. to determine possible uses of the ADT
d. to determine which ADT should be used
31. Which of the following is not a listed outcome of the exhaustive search strategy described in the text?
a. You go around in circles forever
b. It is impossible to reach a city because no flights go there
c. You eventually reach the destination city
Chapter 6 Questions
d. You reach a city C from which there are no departing flights
Chapter 6 Questions
True/False Questions
1. If 5 items are added to a stack, the first item to be removed from the stack is the first item that was added to the
stack.
2. A stack has a first in, first out property.
3. The peek operation of the ADT stack changes the stack.
4. A program can use the operations of the ADT stack without knowing how the operations are implemented.
5. If the characters in a string are added to a stack one at a time, characters removed from the stack will occur in
the order in which they appear in the original string.
6. When infix expressions are converted to postfix expressions, the operands always stay in the same order with
respect to one another.
7. According to the author, the LIFO property of stacks seems inherently unfair.
Chapter 6 Questions
Short Answer Questions
1. What is meant by the last-in, first-out (LIFO) property?
2. What is the difference between the stack pop and peek operations?
3. In a program that uses a stack to check for balanced braces in an string, what condition indicates that the braces
are balanced when the end of the string is reached?
4. What restriction does the array-based implementation of a stack place on the push operation?
5. What are the three facts about converting from infix expressions to postfix expressions?
6. What factors determine the placement of operators when an infix expression is converted to a postfix
expression?
7. What is a directed path?
8. What is an exhaustive search?
9. If a stack is used in a nonrecursive solution to the HPAir problem, when is it necessary to backtrack from a city?
10. What is an activation record?
15. What operations were identified for the ADT Stack?
16. Following are the steps in the process to convert from infix to postfix form. Put them in the correct order by
writing the number of the step in the blank to the left.
Chapter 6 Questions
_____ When you encounter a “)”, pop operators off the stack and append them to the end of postfixExp until you
encounter the matching “(“
_____ Push each “(“ onto the stack
_____ When you reach the end of the string, pop the remaining contents off the stack and append them to the end of
postfixExp.
_____ When you encounter an operand, append it to postfixExp
_____ When you encounter an operator, if the stack is empty, push the operator onto the stack. However, if the
stack is not empty, pop operators of greator or equal precedence from the stack and append them to postfixExp,
stopping when you encounter a “(“ or an operator of lower precedence or when the stack becomes empty. You then
push the current operator in the expression onto the stack.