Computer Science and Information Technology
GATE CSE concept:linked-lists PYQs
Build your understanding with focused practice from past exam papers.
How to practice concept:linked-lists
Attempt a question, record the concept and assumptions, then check the available answer. Rework mistakes after revising the relevant concepts. Topic tags can overlap; review the question context.
Questions 1–10 of 10. Imported answers require independent review unless marked reviewed.
Question 39
Open questionCSMCQ2 marksNeeds review
Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.
struct node{
int elt;
struct node *next;
};
int getListSize (struct node *head)
{
if( E1 ) return 1;
return E2;
}
Which one of the following options gives the correct replacements for the expressions E1 and E2?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 38
Open questionCSMCQ2 marksNeeds review
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size
of these data structures?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 62
Open questionCSNAT2 marksNeeds review
Let LIST be a datatype for an implementation of linked list defined as follows:
typedef struct list {
int data;
struct list *next;
} LIST;
Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes.

Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is ______ . (Answer in integer)
int find (int query, LIST *list) {
while (list != NULL){
if(list->data == query) return 1;
list = list->next;
}
return 0;
}
int main () {
... ... ...
ptr1=L1; ptr2=L2;
while (ptr1->next != NULL){
query = ptr1->next->data;
if (find (query, L2))
ptr1->next = ptr1->next->next;
else ptr1 = ptr1->next;
}
... ... ...
return 0;
}
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 13
Open questionCSMCQ1 markNeeds review
Let SLDel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLDel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list.
Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLDel and DLDel?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 15
Open questionCSMCQ1 markNeeds review
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in
space?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 35
Open questionCSMCQ2 marksNeeds review
Consider the following ANSI C program:
#include <stdio.h>
#include <stdlib.h>
struct Node{
int value;
struct Node *next;};
int main(){
struct Node *box, *head, *boxN; int index = 0;
box = head = (struct Node *) malloc(sizeof(struct Node));
head->value = index;
for (index = 1; index <= 3; index++){
boxN = (struct Node *) malloc(sizeof(struct Node));
box->next = boxN;
boxN->value = index;
box = boxN; }
for (index = 0; index <= 3; index++) {
printf("Value at index %d is %d\n", index, head->value);
head = head->next;
printf("Value at index %d is %d\n", index+1, head->value); } }
Which one of the statements below is correct about the program?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 16
Open questionCSMCQ1 markNeeds review
What is the worst case time complexity of inserting
elements into an empty linked list, if the linked list needs to be maintained in sorted order?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 3
Open questionCSMCQ1 markNeeds review
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 8
Open questionCSMCQ1 markNeeds review
Consider the C code fragment given below:
typedef struct node {
int data;
node* next;
} node;
void join(node* m, node* n){
node* p = n;
while(p->next != NULL) {
p = p->next;
}
p->next = m;
}
Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 13
Open questionCSMCQ1 markNeeds review
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
time?I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer