Multiple Choice Multiple Choice Sections 6.1-6.2 Stacks and Their Applications E
ID: 3537396 • Letter: M
Question
Multiple Choice
Multiple ChoiceSections 6.1-6.2
Stacks and Their
Applications Entries in a stack are "ordered". What is the meaning of this statement? A. A collection of Stacks can be sorted. B. Stack entries may be compared with the '<' operation. C. The entries must be stored in a linked list. D. There is a first entry, a second entry, and so on. The operation for adding an entry to a stack is traditionally called: A. add B. append C. insert D. push The operation for removing an entry from a stack is traditionally called: A. delete B. peek C. pop D. remove Which of the following stack operations could result in stack underflow? A. is_empty B. pop C. push D. Two or more of the above answers Which of the following applications may use a stack? A. A parentheses balancing program. B. Keeping track of local variables at run time. C. Syntax analyzer for a compiler. D. All of the above. Consider the following pseudocode: declare a stack of characters while ( there are more characters in the word to read ) { read a character push the character on the stack } while ( the stack is not empty ) { pop a character off the stack write the character to the screen } What is written to the screen for the input "carpets"? A. serc B. carpets C. steprac D. ccaarrppeettss Here is an INCORRECT pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced: declare a character stack while ( more input is available) { read a character if ( the character is a '(' ) push it on the stack else if ( the character is a ')' and the stack is not empty ) pop a character off the stack else print "unbalanced" and exit } print "balanced" Which of these unbalanced sequences does the above code think is balanced? A. ((()) B. ())(() C. (()())) D. (()))() Consider the usual algorithm for determining whether a sequence of parentheses is balanced. What is the maximum number of parentheses that will appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))? A. 1 B. 2 C. 3 D. 4 E. 5 or more Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). What is the maximum number of parentheses that will ever appear on the stack AT ONE TIME during the computation? A. 1 B. 2 C. 3 D. 4 E. 5 or more Multiple Choice Section 6.3 Implementations of the Stack ADT Suppose we have an array implementation of the stack class, with ten items in the stack stored at data[0] through data[9]. The CAPACITY is 42. Where does the push method place the new entry in the array? A. data[0] B. data[1] C. data[9] D. data[10] Consider the implementation of the Stack using a partially-filled array. What goes wrong if we try to store the top of the Stack at location [0] and the bottom of the Stack at the last used position of the array? A. Both peek and pop would require linear time. B. Both push and pop would require linear time. C. The Stack could not be used to check balanced parentheses. D. The Stack could not be used to evaluate postfix expressions. In the linked list implementation of the stack class, where does the push method place the new entry on the linked list? A. At the head B. At the tail C. After all other entries that are greater than the new entry. D. After all other entries that are smaller than the new entry. In the array version of the Stack class, which operations require linear time for their worst-case behavior? A. is_empty B. peek C. pop D. push when the stack is below capacity E. None of these operations require linear time. In the linked-list version of the Stack class, which operations require linear time for their worst-case behavior? A. is_empty B. peek C. pop D. push E. None of these operations require linear time. Multiple Choice Section 6.4 More Complex Stack Applications What is the value of the postfix expression 6 3 2 4 + - *: A. Something between -15 and -100 B. Something between -5 and -15 C. Something between 5 and -5 D. Something between 5 and 15 E. Something between 15 and 100 Here is an infix expression: 4+3*(6*3-12). Suppose that we are using the usual Stack algorithm to convert the expression from infix to postfix notation. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression? A. 1 B. 2 C. 3 D. 4 E. 5 Multiple Choice
Sections 6.1-6.2
Stacks and Their
Applications
Explanation / Answer
Entries in a stack are "ordered". What is the meaning of this statement?
D. There is a first entry, a second entry, and so on.
The operation for adding an entry to a stack is traditionally called:
D. push
The operation for removing an entry from a stack is traditionally called:
C. pop
Which of the following stack operations could result in stack underflow?
B. pop
Which of the following applications may use a stack?
D. All of the above.
Consider the following pseudocode:
declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}
What is written to the screen for the input "carpets"?
C. steprac
Here is an INCORRECT pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced:
declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')' and the stack is not empty )
pop a character off the stack
else
print "unbalanced" and exit
}
print "balanced"
Which of these unbalanced sequences does the above code think is balanced?
A. ((())
Consider the usual algorithm for determining whether a sequence of parentheses is balanced. What is the maximum number of parentheses that will appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))?
C. 3
Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). What is the maximum number of parentheses that will ever appear on the stack AT ONE TIME during the computation?
B. 2
Suppose we have an array implementation of the stack class, with ten items in the stack stored at data[0] through data[9]. The CAPACITY is 42. Where does the push method place the new entry in the array?
D. data[10]
Consider the implementation of the Stack using a partially-filled array. What goes wrong if we try to store the top of the Stack at location [0] and the bottom of the Stack at the last used position of the array?
B. Both push and pop would require linear time.
In the linked list implementation of the stack class, where does the push method place the new entry on the linked list?
A. At the head
In the array version of the Stack class, which operations require linear time for their worst-case behavior?
E. None of these operations require linear time.
In the linked-list version of the Stack class, which operations require linear time for their worst-case behavior?
E. None of these operations require linear time.
What is the value of the postfix expression 6 3 2 4 + - *:
A. Something between -15 and -100
Here is an infix expression: 4+3*(6*3-12). Suppose that we are using the usual Stack algorithm to convert the expression from infix to postfix notation. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
B. 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.