1

GATE CSE 2018

MCQ (Single Correct Answer)

+2

-0.6

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?

2

GATE CSE 2013

MCQ (Single Correct Answer)

+2

-0.6

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

3

GATE CSE 2010

MCQ (Single Correct Answer)

+2

-0.6

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

```
typedef struct node {
int value;
struct node *next;
} Node;
Node *move_to_front(Node *head) {
Node *p, *q;
if ((head = = NULL: || (head->next = = NULL)) return head;
q = NULL; p = head;
while (p-> next !=NULL) {
q=P;
p=p->next;
}
return head;
}
```

Choose the correct alternative to replace the blank line. 4

GATE CSE 2008

MCQ (Single Correct Answer)

+2

-0.6

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution?

```
struct node {
int value;
struct node *next;
};
Void rearrange (struct node *list ){
struct node *p, * q;
int temp;
if( !list || !list-> next) return;
p = list; q = list->next;
while (q) {
temp = p->value;
p-> value = q ->value;
q-> value = temp;
p = q-> next;
q = p ? p->next : 0;
}
}
```

Questions Asked from Linked List (Marks 2)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages