1
GATE CSE 2022
MCQ (Single Correct Answer)
+1
-0.33

Consider the problem of reversing a singly linked list. To take an example, given the linked list below:

GATE CSE 2022 Data Structures - Linked List Question 2 English 1

the reversed linked list should look like

GATE CSE 2022 Data Structures - Linked List Question 2 English 2

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

A
The best algorithm for the problem takes $$\theta$$(n) time in the worst case.
B
The best algorithm for the problem takes $$\theta$$(n log n) time in the worst case.
C
The best algorithm for the problem takes $$\theta$$(n2) time in the worst case.
D
It is not possible to reverse a singly linked list in O(1) space.
2
GATE CSE 2020
MCQ (More than One Correct Answer)
+1
-0
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
A
$$\Theta \left( {{n^2}} \right)$$
B
$$\Theta \left( n \right)$$
C
$$\Theta \left( {nlogn} \right)$$
D
$$\Theta \left( 1 \right)$$
3
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+1
-0.3
$$N$$ items are stored in a sorted doubly linked list. For a $$delete$$ operation, a pointer is provided to the record to be deleted. For a $$decrease$$-$$key$$ operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order:
$$\Theta \left( N \right),\,\,delete,\,\,O\left( {\log N} \right)\,insert,\,$$ $$\,O\left( {\log N} \right)\,fund, and $$ $$\Theta \left( N \right)\,$$ $$decrease$$-$$key.$$ What is the time complexity of all these operations put together?

A
$$O\left( {{{\log }^2}N} \right)$$
B
$$O\left( N \right)$$
C
$$O\left( {{N^2}} \right)$$
D
$$\Theta \left( {{N^2}\log N} \right)$$
4
GATE CSE 2004
MCQ (Single Correct Answer)
+1
-0.3
Let P be a singly linked list, Let Q be the pointer to an intermediate node x in the list.What is the worst-case time complexity of the best known algorithm to delete the node x from the list?
A
O(n)
B
O(log2n)
C
O(log n)
D
O(1)
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12