4.2.2.1 Linear, circular and priority queues Quiz: AQA Computer Science, Unit 2

The 20 questions

1. What is a queue?

   • A list of key-value pairs, where each key is unique and maps to exactly one value in the list
   • A tree with one root and no children, where each node holds one value and a pointer to its parent
   • An ADT in which the last item added is removed first, with items added and removed at the top
   • An ADT in which items are added at one end and removed from the other

2. What is the order of removal in a linear queue?

   • First in, first out
   • Last in, first out
   • Alphabetical
   • Random

3. Which operation adds an item to a queue?

   • Pop (remove from the top)
   • Peek at the root
   • Enqueue (add to the rear)
   • Push onto the stack

4. Which test is needed before removing an item from a queue?

   • Test whether the queue is a tree
   • Test whether the queue contains a hash
   • Test whether the queue is empty
   • Test whether the queue is a palindrome

5. A linear queue has a fixed-size array of 5 places. How many items can it hold at most?

   • 4
   • 5
   • 6
   • 10

6. Why does a linear queue need a full test?

   • To sort the items, so that the item with the highest value is placed at the front of the queue
   • To prevent adding an item when there is no space left
   • To remove the item at the front, so that a space is freed before the next item is added
   • To count the items in the queue, so that the program knows how many items are waiting to be served

7. What is a problem with a linear queue implemented in an array as items are removed and added over time?

   • The array grows without any limit, so the queue never reports that it is full or empty
   • The queue becomes a stack automatically, so the items leave in last-in, first-out order
   • Space at the front can be left unused, so the queue appears full when it is not
   • Items become constants once they are added, so they can no longer be removed from the array

8. What does a circular queue do to solve the problem of unused space in a linear queue?

   • It reuses the empty spaces at the start by wrapping the pointers around the array
   • It stores items in a random order, so that no item is always found at the front of the queue
   • It removes the array completely, so items are stored only in a single linked chain of nodes
   • It stops items being added at all, so the queue is never full and never needs a full test

9. In a priority queue, which item is removed first?

   • The item added first regardless of priority
   • The item added most recently
   • The item with the highest priority
   • A random item

10. A queue holds items A, B and C, added in that order. Which item is removed first?

    • A
    • B
    • C
    • Any one of them

11. A queue is empty. The program tries to remove an item. Which is the best response?

    • Terminate the operating system, which stops the error by closing every program on the machine
    • Add an item and then remove it, so that the queue is never empty when a removal is attempted
    • Report that the queue is empty and do not remove anything
    • Remove a random value from memory, so that the queue always returns an item for the program

12. A circular queue has 8 places. Front is at index 6 and it contains 5 items. Where is the rear after the 5 items are in place, if the first item was added at the front position?

    • Index 8, which is one past the end of the array, showing where the next item would be added
    • Index 2, wrapping around the array
    • Index 0 always, because a circular queue resets its rear pointer to the start after each addition
    • Index 6, because the rear stays at the same position as the front while the queue is in use

13. What is the effect of a queue used for printer jobs when each job arrives?

    • Jobs are printed at random, so each print job is chosen by the printer as it becomes free
    • Jobs are printed in the order they were received
    • Jobs are never printed, because a queue only stores jobs and cannot pass them to a device
    • Jobs are printed in reverse order, so the most recent job is always the first to come out

14. Which data type is a typical implementation for a queue in a language without built-in queues?

    • An array with front and rear pointers
    • A single integer variable only
    • A string constant
    • A Boolean value

15. Why might a priority queue be used for emergency room patient management?

    • More urgent patients are treated before those with less urgent conditions
    • Patients are removed at random
    • All patients are treated in the order they arrived regardless of need
    • Patients are never removed from the queue

16. A linear queue of capacity 4 has 4 items in it. What is the result of trying to add another item?

    • The first item is silently overwritten
    • The item is added and the queue has 5 items
    • An overflow, because the queue is full
    • The queue is emptied

17. Which statement compares a queue with a stack correctly?

    • A queue uses a peek but a stack does not
    • A queue removes the oldest item, while a stack removes the most recent item
    • A queue removes the most recent item, while a stack removes the oldest
    • They remove items in exactly the same order

18. Which operation tests whether a circular queue is full?

    • Compare the number of items with the capacity, or check whether the rear is next to the front
    • Count the characters in the queue, which tells the program how many letters are waiting
    • Test whether the items are numbers, so that the program knows whether the queue can hold more
    • Check the queue's colour, which changes from green to red when the queue reaches capacity

19. A queue is used to schedule tasks on a server. Which description of the queue's behaviour is correct?

    • Tasks are discarded after one second
    • Tasks are run without any order
    • The newest task is always run first
    • Each task waits its turn behind earlier tasks

20. A program uses a queue with front and rear pointers. Which pointer changes when an item is removed?

    • Front
    • Rear
    • Both always remain the same
    • Neither, because removal is random

Related quizzes

• Data structures and abstract data types Quiz · 4.2.1.1 · 20 questions
• Single- and multi-dimensional arrays Quiz · 4.2.1.2 · 20 questions
• Reading and writing text and binary files Quiz · 4.2.1.3 · 20 questions
• Stack operations Quiz · 4.2.3.1 · 20 questions
• Graphs: weighted, directed and adjacency representations Quiz · 4.2.4.1 · 20 questions
• Trees and binary trees Quiz · 4.2.5.1 · 20 questions
• Hash tables, hashing and collisions Quiz · 4.2.6.1 · 20 questions
• Dictionaries and key-value pairs Quiz · 4.2.7.1 · 20 questions
• Vectors and vector operations Quiz · 4.2.8.1 · 20 questions
• Data types Quiz · 4.1.1.1 · 20 questions