GateAI
Linear Structures, Trees and Heaps

GATE CSE 2017 Set 2 · Q13

MCQ1 markEasy

Time

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1)O(1) time? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node.

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) II only

Linear Structures, Trees and Heaps

In a circular queue implemented using a singly linked list:

  1. Elements are dequeued from the FRONT and enqueued at the REAR.

  2. In a singly linked circular structure, each node points to its successor node (the next element to be served after it).

  3. Thus, the chain flows from FRONT →\rightarrow second node →⋯→\rightarrow \dots \rightarrow REAR→\rightarrowFRONT.

  4. Therefore, the next pointer of the REAR node points back to the FRONT node (making it circular).

This configuration allows:

  • Enqueue ($O(1)$): Create a new node, set its next pointer to FRONT, update REAR->next to the new node, and update REAR.

  • Dequeue ($O(1)$): Advance FRONT to FRONT->next and update REAR->next = FRONT.

Hence, statement II is correct and statement I is incorrect, making (B) the correct choice.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Linear Structures, Trees and Heaps previous year question is Q13 of the GATE CSE 2017 Set 2 paper. Find more GATE CSE PYQs on Linear Structures, Trees and Heaps in Programming and Data Structures, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Linear Structures, Trees and Heaps PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Linear Structures, Trees and Heaps in GATE CSE

Linear Structures, Trees and Heaps has 14 GATE CSE PYQs across 12 papers from 2012 to 2026. 7 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2017 Set 2.

How GATE tests Linear Structures, Trees and Heaps

More from GATE CSE 2017 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2017 Set 2 · Q13 · MCQ

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node.

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.