Preview

06 - Stacks

 1. A stack is a ____________________ data structure
Note: The following presentation is available on www.teachingcomputing.com

  FILO (First in last out)

  LILO (Last in last out)

  LIFO (Last in first out)

  FIFO (First in first out)

 2. A stack is a static (not a dynamic) data structure

  TRUE

  FALSE

 3. A stack can ______________________________

  be accessed at both ends

  only have elements deleted from it, not added to it

  only be accessed at one end

  only have elements added to it, not deleted from it

 4. A stack can be programmed using a __________, for instance, one that points to the top of the stack.

  pointer

  binary value

  boolean flag

  single bit

 5. With a stack, it is the _______ that was put on to the stack that can be retrieved.

  last

  middle

  empty

  first

 6. Another word for retreiving an item from the top of the stack is to _____ an item.

  pull

  stack

  push

  pop

 7. It is possible to think of a stack as a _______________ where the first item that was added is at the bottom and the latest item at the top.

  3d matrix

  binary tree

  graph

  vertical queue

 8. Adding an item to the top of the stack is referred to as:

  stackifying

  gradiating

  pushing

  popping

 9. A stack can be used to control the calling of subroutines in a program.Read the following excerpt and fill in the blanks.
1. A CALL is made for a particular function or subroutine
2. The address of the line that made the call is stored in a stack (using a PUSH command)
3. The CPU executes the subroutine or function. 
4. Once the subroutine or function has been executed, the question is - "What do I do next?"
5. The original address is retreived from the stack with a ________________and the program
can then continue from wherever it had left off.

  PUSH command

  FILTER command

  STACKO command

  POP command

 10. A stack can be easily implemented either through an array or a linked list

  FALSE

  TRUE

 11. Calculators employing ____________________ use a stack structure to hold values

  BODMAS

  simple addition (SA) features

  reverse polish notation (RPN)

  Backas Naur Form (BNF)

 12. The following excerpt explains an example that utilises ___________. This is a very important application of stacks. Fill in the blanks.
________________ is a general algorithm for finding all
(or some) solutions to some computational problems, 
notably constraint satisfaction problems, that incrementally 
builds candidates to the solutions, and abandons a 
candidate ("backtracks") as soon as it determines 
that the candidate cannot possibly be completed to a 
valid solution.

The classic textbook example of the use of ______________ is
the eight queens puzzle, that asks for all arrangements of
eight chess queens on a standard chessboard so that no queen
attacks any other. In the common _________________ approach, 
the partial candidates are arrangements of k queens in the
first k rows of the board, all in different rows and columns.
Any partial solution that contains two mutually attacking 
queens can be abandoned

  backtracking

  A* Algorithm tracking

  heursitism

  algorithmic heuristics

 13. Follow the logic in the code below and predict the final output when the stack is printed.
mystack=[1,2,5]
mystack.pop()
mystack.append(7)
mystack.pop()
mystack.append(8)
mystack.append(9)
print(mystack)
#Note: The 'append' command is pushing an item on to the stack

  [9]

  [8,9]

  [1, 2, 8, 9]

  [9,8,2,1]

 14. In Pseudocode, if you perform a check to see if the 'top' pointer is equal to the maximum size, then this would suggest that __________________________

  the stack is empty

  the stack has a single item held in it

  the stack has a top pointer value of x (where x is always <4)

  the stack is full

 15. The following image is illustrating a depth first search on a graph. What happens next?
d_first_search_stack.png

  D is pushed on to the stack

  C is pushed on to the stack

  S is popped from the stack and H is pushed onto the stack

  B is popped from the stack and S is pushed on to the stack

 16. This shows an OOP python implementation of a stack. What is the output on execution of this code?
#A stack lends itself to the creation of a new class
#Here we create a stack class, where stack operations are methods
class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self): #if the stack is empty then return True
         return self.items == []

     def push(self, item):
         self.items.append(item) #appending items

     def pop(self):
         return self.items.pop() #popping an item off the stack 

     def peek(self):
         return self.items[len(self.items)-1] #peek at the top most item (it remains in the stack)

     def size(self): #returns the size of the stack
         return len(self.items)

     def getStackItems(self):
          return self.items

s=Stack()
s.push("x")
print(s.isEmpty())
s.pop()
print(s.isEmpty())
s.push(1)
s.push(2)
s.push(3)
print(s.peek())

  1,2,3

  False, True,3

  True,False,1

  True,True,3

 17. Stacks are an important way of supporting nested or ________ function calls

  deletable

  final

  initial

  recursive

 18. In the following example, that uses a class implementation of a stack, what will the output be if mysteryfunction is called with "marvin"?
class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self): #if the stack is empty then return True
         return self.items == []

     def push(self, item):
         self.items.append(item) #appending items

     def pop(self):
         return self.items.pop() #popping an item off the stack 

     def peek(self):
         return self.items[len(self.items)-1] #peek at the top most item (it remains in the stack)

     def size(self): #returns the size of the stack
         return len(self.items)

     def getStackItems(self):
          return self.items


def mystery_function(mystr):
     s=Stack()
     holding_letters=[]#create a list that will store the string characters as they come in
     for i in range (len(mystr)): #for every element in the total length of the string
          holding_letters.append(mystr[i]) #append each character to the holding_letters list
     
     for i in range(len(holding_letters)):
          s.push(holding_letters[i]) 
     reversed_string=""
     #for every element in the stack, pop each one out
     for i in range(len(holding_letters)):
          reversed_string+=holding_letters.pop()
     print(reversed_string)


mystery_function("marvin")

  mar

  niv

  marvinmarvinnivramnivram

  nivram

 19. In the following very simplistic code implementation (python) of the towers of Hanoi, what is happening on line 11?
def hanoi(n, P1, P2, P3):
    """ Move n discs from pole P1 to pole P3. """
    if n == 0:
        # No more discs to move in this step
        return

    global count
    count += 1

    # WHAT IS HAPPENING HERE?
    hanoi(n-1, P1, P3, P2)

    if P1:
        # move disc from P1 to P3
        P3.append(P1.pop())
        print(A, B, C)

    # move n-1 discs from P2 to P3
    hanoi(n-1, P2, P1, P3)

# Initialize the poles: all n discs are on pole A.
n = 3
A = list(range(n,0,-1))
B, C = [], []

print(A, B, C)
count = 0
hanoi(n, A, B, C)
print(count)

  move n-1 discs from P3 to P1

  move 1 disc from P1 to P3

  move n discs from P2 to P1

  move n-1 discs from P1 to P2

 20. This question requires some understanding of RPN |(reverse polish notation). Read the excerpt and answer question below.
Consider the following commands and context:
--------------------------------------------

In this context, you are evaluating the 
following expression using a stack: 
(9 3 - 2 / ) would give a result of?

You would start off with the following:
Push(9) 
Push(3) 


,,,,in the given context, what would the
output be?

  18

  6

  3

  4