IBDP Computer Science B2.2 Data structures HL Paper 1 - New Syllabus
▶️ Answer/Explanation
(a)
Three features of a dynamic data structure are:
• Its size is not fixed in advance and can change while the program is running.
• Memory is allocated dynamically as elements are added, reducing unnecessary reserved memory.
• Elements can generally be inserted or deleted more flexibly than in a fixed-size structure.
Dynamic data structures are especially useful when the amount of data that will be stored is not known before the program starts.
Answer: Variable size, dynamic memory allocation and flexible insertion/deletion.
(b)(i)
A circular linked list consists of nodes. Each node contains a data field and a pointer/reference to the next node.
The last node does not point to null. Instead, it points back to the first/head node, forming a continuous circular structure.
$\text{Node}_1 \rightarrow \text{Node}_2 \rightarrow \text{Node}_3 \rightarrow \cdots \rightarrow \text{Node}_1$
An external pointer can be used to identify the first node in the list.
Answer: Each node stores data and a pointer to the next node, while the final node points back to the first node.
(b)(ii)
Two applications of circular linked lists are:
• Round-robin scheduling: processes can be handled repeatedly in a continuous cycle.
• Media playlists: after the last item is reached, processing can return to the first item automatically.
Other acceptable examples include multiplayer turn systems, circular queues, memory management and repeated navigation systems.
Answer: Round-robin scheduling and repeating playlists.
(c)(i)
A stack follows the last in, first out (LIFO) principle, meaning the most recently inserted item is removed first.
A queue follows the first in, first out (FIFO) principle, meaning the item inserted earliest is removed first.
There is also a difference in the access points:
• A stack inserts and removes items at the top, using operations such as push() and pop().
• A queue inserts items at the rear using enqueue() and removes items from the front using dequeue().
Answer: A stack is LIFO and inserts/removes at the same end, whereas a queue is FIFO and inserts at the rear but removes from the front.
(c)(ii)
The algorithm repeatedly removes the top customer from the stack. The first letter of the name is checked and the customer is then added to the appropriate queue.
The loop continues until CUSTOMERS.isEmpty() is true.
For every iteration:
• CUSTOMERS.pop() removes the item currently at the top of the stack.
• firstletter(X) obtains the first character of the customer’s name.
• If the first letter is between ‘A’ and ‘M’ inclusive, ONE.enqueue(X) places the name at the rear of queue ONE.
• Otherwise, TWO.enqueue(X) places the name at the rear of queue TWO.
Because the names are popped from the stack in top-to-bottom order and enqueued at the rear of each queue, the required order of the names is preserved.