Data Structures Quiz

A hospital has asked for a program that will control the order in which the arrivals are seen in the accident and emergency department. (a) A priority queue has been chosen to store the arrival information. (i) State the property of a priority queue that makes it suitable for this application.

A hospital has asked for a program that will control the order in which the arrivals are seen in the accident and emergency department. (a) A priority queue has been chosen to store the arrival information. (i) State the property of a priority queue that makes it suitable for this application.

• It allows for constant time retrieval of the highest priority element.

• It maintains the order of arrival for all elements.

• It provides a way to sort elements in ascending order.

• It ensures that all elements are processed in a first-come, first-served manner.

(ii) The priority queue is implemented using a circular queue. State an advantage of a circular queue which makes it more efficient in use of memory.

• Efficient use of space by reusing empty slots

• Faster insertion and deletion operations

• Simpler implementation compared to linear queues

• Better support for priority-based operations

(b) A test version of the priority circular queue consists of 5 cells. Arrival information consists of a severity rating and a last name. The severity scale is 3 (least severe), 2 (moderately severe), and 1 (most severe). For example, Mr Jones has a severity rating of 2. His arrival record would be ‘2 Jones’. What is the result after the following operations?

• Option A: 1 Smith, 2 Jones, 3 Brown

• Option B: 2 Jones, 1 Smith, 3 Brown

• Option C: 3 Brown, 2 Jones, 1 Smith

• Option D: 1 Smith, 3 Brown, 2 Jones

2. A stack is an important data structure in computer science. Which of the following best defines the term stack?

• A stack is a collection of elements with a Last In, First Out (LIFO) access policy.

• A stack is a collection of elements with a First In, First Out (FIFO) access policy.

• A stack is a type of queue used for breadth-first search.

• A stack is a data structure used to store key-value pairs.

A stack is a last in first out data structure where new items are added to the top of the stack and items are removed from the top of the stack.

• True

• False

A call stack is used when subroutines are called. Which of the following items could each call stack frame hold?

• Local variables

• Return address

• Function parameters

• Global variables

A recursive algorithm could cause a system to crash due to:

• Excessive memory usage

• Insufficient disk space

• Network congestion

• Low battery power

State another use of a stack in a computing system.

• Function call management

• Data encryption

• Network routing

• File storage

In a very busy coffee shop, orders are split between different production lines. One line only makes hot drinks. Another line only makes cold drinks. When an order arrives, items are split out and assigned to different lines. Items are given to customers as soon as the order is complete. An abstract data type list is used to hold the order IDs. What is the difference between a dynamic and a static data structure?

• A dynamic data structure can grow and shrink in size, while a static data structure has a fixed size.

• A static data structure can grow and shrink in size, while a dynamic data structure has a fixed size.

• Both dynamic and static data structures have fixed sizes.

• Both dynamic and static data structures can grow and shrink in size.