Deck 7: Stacks

Question 1

The ______ method of the ADT stack retrieves the top of the stack,but does not change the stack.

A)createStack
B)push
C)pop
D)peek

Answer 1

D

Question 2

If the array: 6,2,7,13,5,4
Is added to a queue,in the order given,which number will be the first number to be removed from the queue?

A)6
B)2
C)5
D)4

Answer 2

A

Question 3

In the StackInterface class,the push method accepts as its parameter an item that is an instance of ______.

A)Integer
B)Double
C)String
D)Object

Answer 3

D

Question 4

If a stack is used by an algorithm to check for balanced braces,which of the following is true 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 "}"

Question 5

Which of the following operations of the ADT stack does not throw a StackException?

A)push
B)pop
C)popAll
D)peek

Question 6

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}

Question 7

The pop operation throws a StackException when it tries to ______.

A)add an item to an empty stack
B)add an item to an array-based implementation of a stack that is already full
C)delete an item from an array-based implementation of a stack that is already full
D)delete an item from an empty stack

Question 8

StackInterface provides the specifications for ______.

A)only the array-based implementation of a stack
B)only the reference-based implementation of a stack
C)only an implementation of a stack that uses the ADT list
D)all the implementations of a stack

Question 9

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

Question 10

The ______ method of the ADT stack adds an item to the top of the stack.

A)createStack
B)push
C)pop
D)peek

Question 11

What is the corrected input if the following line is typed on a keyboard: yww←dshr←←wd←e
(where ← represents the backspace character)?

A)ywdswe
B)ywwdwde
C)ywdshwe
D)ywdswd

Question 12

Which of the following methods of the ADT stack accepts a parameter?

A)push
B)pop
C)createStack
D)peek

Question 13

In the StackInterface class,the pop method returns an item that is an instance of ______.

A)Integer
B)Double
C)String
D)Object

Question 14

The item that is removed first from a stack is called the ______ of the stack.

A)front
B)top
C)base
D)prime

Question 15

The first in,first out (FIFO)property is found in the ADT ______.

A)list
B)stack
C)queue
D)tree

Question 16

The ______ method of the ADT stack retrieves and then removes the top of the stack.

A)createStack
B)push
C)pop
D)peek

Question 17

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

Question 18

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

Question 19

The push operation throws a StackException when it tries to ______.

A)add an item to an empty stack
B)add an item to an array-based implementation of a stack that is already full
C)delete an item from an array-based implementation of a stack that is already full
D)delete an item from an empty stack

Question 20

The last-in,first-out (LIFO)property is found in the ADT ______.

A)list
B)stack
C)queue
D)tree

Question 21

In a reference-based implementation of a stack,it is necessary to call the isFull method before calling the push method.

Question 22

In a reference-based implementation of a stack,the stack can grow and shrink dynamically.

Question 23

Calls to methods that throw StackException must be enclosed in try blocks.

Question 24

When a recursive call to a method occurs,the compiler's implementation must remember all of the following information EXCEPT ______.

A)values of parameters
B)values of local variables
C)values of global variables
D)a reference to the point from which the recursive call was made

Question 25

The push operation of the ADT stack can throw a StackException.

Question 26

______ 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

Question 27

Typically,______ are used by a compiler to implement recursive methods.

A)linked-lists
B)arrays
C)stacks
D)queues

Question 28

A client can access all the elements of a stack.

Question 29

In a graph that represents the flight map for the HPAir problem,if a flight exists from city C1 to city C2,then C2 is said to be ______ C1.

A)adjacent to
B)similar to
C)related to
D)bordering

Question 30

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

Question 31

What is the value of the following postfix expression: 5 2 - 8 4 + *?

A)-9
B)28
C)35
D)36

Question 32

When infix expressions are converted to postfix expressions,the operands always stay in the same order with respect to one another.

Question 33

A program can use the operations of the ADT stack without knowing how the operations are implemented.

Question 34

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.

Question 35

The peek operation of the ADT stack changes the stack.

Question 36

Which of the following methods is NOT called by the nonrecursive stack version of the isPath method?

A)insertAdjacent
B)unvisitAll
C)markVisited
D)getNextCity

Question 37

A stack has a first in,first out property.

Question 38

In a graph that represents the flight map for the HPAir problem,if a flight exists from city C1 to city C2,then the path from C1 to C2 is called a _______.

A)relation
B)neighborhood
C)directed path
D)connecting path

Question 39

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

Question 40

Which of the following is the postfix form of the infix expression: (a +b)* c / d

A)a b + c * d /
B)a b * c / d +
C)a + b * c / d
D)a b + c d * /

Question 41

What is the difference between the stack pop and peek operations?

Question 42

Suppose we begin with an empty stack,and perform the following operations: push 7,push 2,push 9,push 6,pop,pop,peek,push 1,push 3,peek,push 8,pop,peek,pop,pop,push 5,push 4,pop,pop,pop,push 8.What is contained on the stack when we are done? Write out the contents from top to bottom.

Question 43

Explain how a stack can be used to determine if an infix expression is correctly parenthesized.

Question 44

What is an activation record?

Question 45

What are the factors which determine the placement of operators when an infix expression is converted to a postfix expression?

Question 46

What are the three facts about converting from infix expressions to postfix expressions?

Question 47

Describe an example of a game in which the logic of the game makes use of a stack.

Question 48

What is the restriction that the array-based implementation of a stack places on the push operation?

Question 49

What is meant by the first in,first out (FIFO)property?

Question 50

When does the push operation throw a StackException?

Question 51

Write the axiom for specifying that the last item inserted into a stack is the first item to be removed.

Question 52

What is meant by the last-in,first-out (LIFO)property?

Question 53

What is a directed path?

Question 54

Why does the ADT stack not define a get( )method?

Question 55

Suppose an infix expression contains parentheses as grouping symbols.Is it still possible to convert this expression into postfix notation?

Question 56

How can a StackException be avoided in an array-based implementation of a stack when a fixed-size array is used?

Question 57

What is the advantage of an implementation of a stack that uses the ADT list over an implementation that uses a linked list?

Question 58

What is an exhaustive search?

Question 59

How can the condition,when you reach the end of the string,you have matched each "{",be verified in a program that uses a stack to check for balanced braces?

Question 60

If a stack is used in a nonrecursive solution to the HPAir problem,when is it necessary to backtrack from a city?