MskProdComputing
Back to the topic

The mark scheme starts on a new page, so you can print pages one and two for a student and keep the last page yourself. Everything prints in black on white whichever theme you are using.

Python · A Level 4

Stacks and Queues

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 22 marks. Total 32 marks.

Name

Class

Date

Mark  / 32

Section A

Circle the letter of the correct answer. One mark each.

  1. 1Which description matches a stack?1
    1. AThe last item added is the first removed
    2. BThe first item added is the first removed
    3. CItems are removed in alphabetical order
    4. DItems can be removed from either end
  2. 2Which description matches a queue?1
    1. AThe first item added is the first removed
    2. BOnly the highest value is removed first
    3. CItems are removed at random
    4. DThe last item added is the first removed
  3. 3What error occurs when you pop from an empty stack?1
    1. AQueue overflow
    2. BStack underflow
    3. CIndex overflow
    4. DStack overflow
  4. 4A stack is empty. push(1), push(2), push(3), pop() are performed. What is now on top?1
    1. A3
    2. B2
    3. C1
    4. DThe stack is empty
  5. 5Why is a circular queue better than a linear queue in a fixed size array?1
    1. AIt does not need a front pointer
    2. BIt can hold an unlimited number of items
    3. CIt sorts the items as they are added
    4. DPlaces freed at the front can be reused without shifting items
  6. 6A circular queue has 6 places and the rear pointer is at position 5. Where is the next item added?1
    1. APosition 6
    2. BPosition 4
    3. CPosition 0
    4. DPosition 5
  7. 7Which data structure is best for implementing an undo feature?1
    1. AA queue
    2. BA priority queue
    3. CA circular queue
    4. DA stack
  8. 8Which data structure is best for holding print jobs in the order they were sent?1
    1. AA stack
    2. BA binary tree
    3. CA queue
    4. DA hash table
  9. 9How does a priority queue differ from an ordinary queue?1
    1. AIt has no maximum size, so it can never become full or cause an overflow
    2. BThe item removed is the one with the highest priority, not the one that arrived first
    3. CItems can only be added at the front and are only ever removed from the rear
    4. DIt removes the item that arrived last, so it behaves in the same way as a stack
  10. 10What is the postfix form of the infix expression 3 + 4 * 2?1
    1. A+ 3 * 4 2
    2. B3 + 4 2 *
    3. C3 4 + 2 *
    4. D3 4 2 * +

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

  1. 1DescribeDescribe two differences between a stack and a queue.4
  2. 2StateAn empty stack has the following operations performed on it, in order: push(4), push(7), pop(), push(2), push(9), pop(), pop(). State the values returned by each of the three pop operations, and the contents of the stack at the end.4
  3. 3WriteA stack is implemented as an array called items, with a pointer called top that is -1 when the stack is empty. The array has a fixed size of 10. Write the subprograms push and pop, including checks for overflow and underflow.6
  4. 4StateA circular queue is held in an array of size 5. The front pointer is 3 and the queue contains 3 items. State the position of the rear pointer, and the position at which the next item will be added. Explain how the remainder operator is used when a pointer is moved.4
  5. 5ShowThe postfix expression 6 2 3 + * is evaluated using a stack. Show the contents of the stack after each token and state the result.4

Mark scheme

Section A

1A2A3B4B5D6C7D8C9B10D

Section B

1 Describe two differences between a stack and a queue. 4

One mark for each of the following, to a maximum of 4.

  • A stack is last in first out
  • A queue is first in first out
  • Items are added and removed at the same end of a stack, but at opposite ends of a queue
  • An example use of each, such as undo for a stack and a print queue for a queue

Model answer. A stack is last in first out, so the item removed is the one most recently added, whereas a queue is first in first out, so the item removed is the one that has been waiting longest. Items are added to and removed from the same end of a stack, the top, but a queue adds at the rear and removes from the front. A stack is used for undo or the call stack, and a queue for print jobs or process scheduling.

2 An empty stack has the following operations performed on it, in order: push(4), push(7), pop(), push(2), push(9), pop(), pop(). State the values returned by each of the three pop operations, and the contents of the stack at the end. 4

One mark for each of the following, to a maximum of 4.

  • The first pop returns 7
  • The second pop returns 9
  • The third pop returns 2
  • The stack contains only 4 at the end

Model answer. After push(4) and push(7) the stack is 4, 7 with 7 on top, so the first pop returns 7. push(2) and push(9) give 4, 2, 9, so the second pop returns 9 and the third returns 2. The stack then contains only 4.

3 A stack is implemented as an array called items, with a pointer called top that is -1 when the stack is empty. The array has a fixed size of 10. Write the subprograms push and pop, including checks for overflow and underflow. 6

One mark for each of the following, to a maximum of 6.

  • push checks whether the stack is full, when top is 9
  • push reports an error or returns False if it is full
  • push increases top by 1 and stores the item at items[top]
  • pop checks whether the stack is empty, when top is -1
  • pop reads the item at items[top] before changing the pointer
  • pop reduces top by 1 and returns the item

Model answer.

Python
items = [None] * 10
top = -1

def push(item):
    global top
    if top == 9:
        return False
    top = top + 1
    items[top] = item
    return True

def pop():
    global top
    if top == -1:
        return None
    item = items[top]
    top = top - 1
    return item

push(5)
push(8)
print(pop(), pop(), pop())

push first checks whether the pointer is at the last position, and returns False to report the overflow if so. Otherwise it moves the pointer up and stores the item there. pop checks for an empty stack and reports underflow by returning None, otherwise it reads the item at the pointer, moves the pointer down and returns the item. The calls shown print 8 5 None.

4 A circular queue is held in an array of size 5. The front pointer is 3 and the queue contains 3 items. State the position of the rear pointer, and the position at which the next item will be added. Explain how the remainder operator is used when a pointer is moved. 4

One mark for each of the following, to a maximum of 4.

  • The rear is at position 0
  • The next item will be added at position 1
  • The pointer is increased by 1 and the remainder after division by the size of the array is taken
  • So when the pointer passes the last position it wraps round to 0

Model answer. The items are at positions 3, 4 and 0, so the rear pointer is at position 0, and the next item is added at position (0 + 1) MOD 5, which is 1. When a pointer is moved, 1 is added and the remainder after dividing by the size of the array is taken. Since the remainder can never be 5 or more, a pointer that passes the last position wraps round to position 0 at the start of the array.

5 The postfix expression 6 2 3 + * is evaluated using a stack. Show the contents of the stack after each token and state the result. 4

One mark for each of the following, to a maximum of 4.

  • 6 is pushed, then 2, then 3, giving 6 2 3
  • + pops 3 and 2 and pushes 5, leaving 6 5
  • * pops 5 and 6 and pushes 30
  • The result is 30

Model answer. Each number is pushed, so after 6, 2 and 3 the stack holds 6, 2, 3 with 3 on top. The + pops 3 and 2 and pushes their sum, 5, leaving 6, 5. The * pops 5 and 6 and pushes their product, 30. The stack holds only 30, which is the result.