Skip to content

Course home

Data structures

Data structures

EasyMedium
12345678910111213
Question 9

A circular queue of capacity 5 is implemented using a 0-indexed array of size 5. The queue uses two pointers:

  • front\text{front}front: the index of the element currently at the front of the queue.
  • rear\text{rear}rear: the index of the last element added to the queue.

Initially, the queue is empty, with front=0\text{front} = 0front=0 and rear=4\text{rear} = 4rear=4.

The operations to enqueue and dequeue are defined as follows:

  • Enqueue(xxx): rear=(rear+1)(mod5)\text{rear} = (\text{rear} + 1) \pmod 5rear=(rear+1)(mod5), then array[rear]=x\text{array}[\text{rear}] = xarray[rear]=x.
  • Dequeue(): x=array[front]x = \text{array}[\text{front}]x=array[front], then front=(front+1)(mod5)\text{front} = (\text{front} + 1) \pmod 5front=(front+1)(mod5), and return xxx.

The following sequence of operations is performed on the empty queue:

  1. Enqueue('A')
  2. Enqueue('B')
  3. Enqueue('C')
  4. Dequeue()
  5. Enqueue('D')
  6. Dequeue()
  7. Enqueue('E')
  8. Enqueue('F')

Which of the following correctly identifies the final values of front\text{front}front and rear\text{rear}rear, and the sequence of active elements in the queue (from front to rear)?

A

front=2\text{front} = 2front=2, rear=0\text{rear} = 0rear=0; active elements = [’C’,’D’,’E’,’F’][\text{'C'}, \text{'D'}, \text{'E'}, \text{'F'}][’C’,’D’,’E’,’F’]

B

front=1\text{front} = 1front=1, rear=0\text{rear} = 0rear=0; active elements = [’B’,’C’,’D’,’E’,’F’][\text{'B'}, \text{'C'}, \text{'D'}, \text{'E'}, \text{'F'}][’B’,’C’,’D’,’E’,’F’]

C

front=2\text{front} = 2front=2, rear=4\text{rear} = 4rear=4; active elements = [’C’,’D’,’E’][\text{'C'}, \text{'D'}, \text{'E'}][’C’,’D’,’E’]

D

front=0\text{front} = 0front=0, rear=3\text{rear} = 3rear=3; active elements = [’F’,’E’,’D’,’C’][\text{'F'}, \text{'E'}, \text{'D'}, \text{'C'}][’F’,’E’,’D’,’C’]

Markscheme

Data structures Questions

  1. GCSE
  2. /Computer Science
  3. /Data structures

36 exam-style questions on AQA GCSE Computer Science Data structures. Each one has a worked solution and a mark scheme showing where the marks go.

Question bank