DATA STRUCTURES

SWETA KUMARI
TELEGRAM CHANNEL FOR NOTES :
https://t.me/gatecsitunacademy
 1 YEAR : 14,298/-

27th dec , 2024

Complete Course on TOC at 5:30 PM by

Sweta Kumari

HELLOSONU01
 1 YEAR : 21,999/-

27th dec , 2024

Complete Course on TOC at 5:30 PM by

Sweta Kumari

HELLOSONU01
Benefits of Plus Subscription
1. Daily Live Classes
2. Recorded lectures
3. Daily lectures PDF notes
4. LIVE Doubt clearing session twice a week
5. 5600+ practice questions with detailed solutions
6. 750+ test series including topic wise, subject wise and full length
7. Digital Chapter wise Notes of every subject
8. Daily Practice Problems just after class in a group
9. Access to all 15+ GATE CS IT educators LIVE Classes
10.Access to all Recorded lectures of previous top educators

Benefits of ICONIC SUBSCRIPTION

1. All benefits of Plus Subscription
2. Personal Coach - He or she will personally mentor and clear subject & strategy
related doubts
3. Printed books that will be delivered to your home ( total 12)
HELLOSONU01 HELLOSONU01
 To get Personal Mentoring Of
Sweta Mam

Use Referral code HELLOSONU01

to subscribe Unacademy under
GATE
 BENEFITS
Referral Code
HELLOSONU01
Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the underlying array)
of the maximum element stored in the heap. The number of possible values of k is
1.53
2.52
3.27 GATE 2024
4.1
Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the underlying array)
of the maximum element stored in the heap. The number of possible values of k is
1.53
2.52
3.27 GATE 2024
4.1
B
GATE CSE 2021 Set 2
Numerical
+1
-0
Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing
Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing
Depth-First Search (DFS) starting from the root.
The value of |A - B| is _______
 Given : Binary tree with 7 nodes consider the following
GATE CSE 2021 Set 2 complete binary tree
Numerical
+1
-0
Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting
from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.
The value of |A - B| is _______
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored
using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest
element of the tree is stored at index ___________.
GATE CSE 2022
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored
using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest
element of the tree is stored at index ___________.
GATE CSE 2022
Answer
Correct answer is 509
Explanation
Given a binary search tree with 1000 distinct elements that is also a complete binary tree, it is stored using an
array representation similar to that of binary heap trees, with array indices starting from 0.
The largest element in the binary search tree (BST) is located at the rightmost position in the tree. In the
context of a complete binary tree with 1000 elements, the rightmost element is at index 510, calculated
using 2^9−2, considering that the array index starts at 0.
The second largest element is the parent of the largest element, and the third largest is the left child of the
largest. Therefore, the third largest element is stored at index 509, which is 510−1.
Thus, the third largest element in the tree is located at index 509.
C
GATE CSE 2024 Set 2
MCQ (Single Correct Answer)
+2
You are given a set V of distinct integers. A binary search tree T is created by inserting all elements of V one by
one, starting with an empty tree. The tree T follows the convention that, at each node, all values stored in the left
subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which
these values were inserted into T, and you do not have access to T.

Which one of the following statements is TRUE?

A
Inorder traversal of T can be determined from V
B
Root node of T can be determined from V
C
Preorder traversal of T can be determined from V
D
Postorder traversal of T can be determined from V
GATE CSE 2024 Set 2
MCQ (Single Correct Answer)
+2
You are given a set V of distinct integers. A binary search tree T is created by inserting all elements of V one by
one, starting with an empty tree. The tree T follows the convention that, at each node, all values stored in the left
subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which
these values were inserted into T, and you do not have access to T.

Which one of the following statements is TRUE? A

A
Inorder traversal of T can be determined from V
B
Root node of T can be determined from V
C
Preorder traversal of T can be determined from V
D
Postorder traversal of T can be determined from V
GATE CSE 2023
MCQ (Single Correct Answer)
+2
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The
operation EXTRACT-MAX(A) extracts and deletes the maximum element from A. The operation INSERT(A, key) inserts a new
element key in A. The properties of a max-heap are preserved at the end of each of these operations.
When A contains n elements, which one of the following statements about the worst case running time of these two operations is
TRUE?
A
Both EXTRACT-MAX(A) and INSERT(A, key) run in O(1).
B
Both EXTRACT-MAX(A) and INSERT(A, key) run in O(log(n)).
C
EXTRACT-MAX(A) runs in O(1) whereas INSERT(A, key) runs in O(n).
D
EXTRACT-MAX(A) runs in O(1) whereas INSERT(A, key) runs in O(log(n)).
EXTRACT-MAX(A):
The EXTRACT-MAX(A) operation involves the following steps:
•Remove the root element of the max-heap, which is the maximum element. This step itself takes O(1) time.
•Move the last element of the heap to the root position.
•Restore the max-heap property by "heapifying" the root element, which ensures the new root is correctly placed. Heapifying an
element takes O(log(n)) time because it may need to be compared and swapped down through the height of the heap (which
is log(n) for a complete binary tree).
Therefore, the worst-case running time for EXTRACT-MAX(A) is O(log(n)).

INSERT(A, key):
The INSERT(A, key) operation involves the following steps:
•Add the new element at the end of the heap.
•Restore the max-heap property by "bubbling up" the new element, which ensures it is correctly placed. Bubbling up could
potentially involve comparing and swapping elements up through the height of the heap. This process also takes O(log(n)) time in
the worst case.
Therefore, the worst-case running time for INSERT(A, key) is O(log(n)).

Conclusion:
The correct choice is:
Option B

Both EXTRACT-MAX(A) and INSERT(A, key) run in O(log(n)).

GATE CSE 2023
GATE CSE 2023
First, you'll have to check if the elements a and b are present in the BST or not.
Since the BST is balanced, it will take Θ(log2(n)) time for that.
Traversing the k elements would take additional Θ(k) time.
GATE CSE 2020
Numerical
+2
-0
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of
comparisons required to find the maximum in the heap is _______.
GATE CSE 2020
Numerical
+2
-0
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of
comparisons required to find the maximum in the heap is _______.

If a heap has 1023 elements, it'll contain 512 leaves and since it is a MIN-
HEAP, the maximum will be present in the leaves.

We can visualise it this way. At each level starting with root level, number of
elements are

1−2−4−8−16−32−64−128−256−512 (this is the last level, hence leaves)

So if we have n elements in an array, we know that to find the maximum it

takes n−1 comparisons.

In this case, n=512, so the answer should be 511.

GATE CSE 2019
Numerical
+2
-0
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T
are chosen uniformly and independently at random. The expected value of the distance between a and b in T
(i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.
GATE CSE 2023
MCQ (Single Correct Answer)
+1
-0.33
Let SLLdel 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 DLLdel 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 SLLdel and DLLdel?
A
SLLdel is O(1) and DLLdel is O(n)
B
Both SLLdel and DLLdel are O(log(n))
C
Both SLLdel and DLLdel are O(1)
D
SLLdel is O(n) and DLLdel is O(1)
Here, were given head pointer and
ptr pointer of the node to be
deleted (Here y) We have to
traverse from head node till node
before the one pointed by ptr (here
X ) which take O(n) time in worst
case.
Simply we can do it as :
pt→ prev → next = ptr → next
ptr→ next → prev =ptr→ prev
delete (ptr)
since it can be performed in O(1) time:
Hence, the correct option is (D).
 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:

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 O(1) space?
A
The best algorithm for the problem takes θ(n) time in the worst case.
B
The best algorithm for the problem takes θ(n log n) time in the worst case.
C
The best algorithm for the problem takes θ(n2) time in the worst case.
D
It is not possible to reverse a singly linked list in O(1) space.
GATE CSE 2024 Set 1
Numerical
+1
-0
Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below.

Operator Precedence Associativity

+ Highest Left
− High Right
* Medium Right
/ Low Right

The value of the expression 3+1+5∗2/7+2−4−7−6/2 as per

the above rules is _______
GATE CSE 2024 Set 1
Numerical
+1
-0
Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below.

Operator Precedence Associativity

+ Highest Left 6
− High Right
* Medium Right
/ Low Right

The value of the expression 3+1+5∗2/7+2−4−7−6/2 as per

the above rules is _______
GATE CSE 2021 Set 1 86
Numerical
+1
-0
Consider the following sequence of operations on an empty stack.
push(54); push(52); pop(); push(55); push(62); s = pop();
Consider the following sequence of operations on an empty queue.
enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();
The value of s + q is ______
GATE CSE 2024 Set 2
MCQ (More than One Correct Answer)
+2
Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400,
whereas S2 is empty, as shown below.

Stack S1
400 (Top)
300
200
100
GATE CSE 2024 Set 2
MCQ (More than One Correct Answer)
+2
Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400,
whereas S2 is empty, as shown below.

Stack S1
B,C,D
400 (Top)
300
200
100
D
GATE CSE 2023
Numerical
+2
-0
Consider a sequence a of elements a0=1,a1=5,a2=7,a3=8,a4=9, and a5=2. The following operations are performed on a stack S and a queue Q,
both of which are initially empty.
I: push the elements of a from a0 to a5 in that order into S.
II: enqueue the elements of a from a0 to a5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same
VIII: Repeat operation VII three times.
IX: pop an element from S.
X: pop an element from S.
The top element of S after executing the above operations is ____________.
GATE CSE 2023
Numerical
+2
-0
Consider a sequence a of elements a0=1,a1=5,a2=7,a3=8,a4=9, and a5=2. The following operations are performed on a stack S and a queue Q,
both of which are initially empty.
I: push the elements of a from a0 to a5 in that order into S.
II: enqueue the elements of a from a0 to a5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S. 8
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same
VIII: Repeat operation VII three times.
IX: pop an element from S.
X: pop an element from S.
The top element of S after executing the above operations is ____________.
GATE CSE 2022
Numerical
+2
-0
Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in the figure). The only operations
allowed on these two queues are Enqueue (Q, element) and Dequeue (Q). The minimum number of Enqueue operations on
Q1 required to place the elements of Q1 in Q2 in reverse order (shown as the Final State in the figure) without using any additional
storage is ______________.
GATE CSE 2022
Numerical
+2
-0
Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in the figure). The only operations
allowed on these two queues are Enqueue (Q, element) and Dequeue (Q). The minimum number of Enqueue operations on
Q1 required to place the elements of Q1 in Q2 in reverse order (shown as the Final State in the figure) without using any additional
storage is ______________.

0
6
B
GATE | GATE CS 2021

Consider the following ANSI C program:

#include
#include
struct Node{
int value;
struct Node *next;};
int main( ) {
struct Node *boxE, *head, *boxN; int index=0;
boxE=head= (struct Node *) malloc(sizeof(struct Node));
head → value = index;
for (index =1; index<=3; index++){
boxN = (struct Node *) malloc (sizeof(struct Node));
boxE → next = boxN;
boxN → value = index;
boxE = 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 following statements below is correct about the program?
(A) Upon execution, the program creates a linked-list of five nodes
(B) Upon execution, the program goes into an infinite loop
(C) It has a missing return which will be reported as an error by the compiler
(D) It dereferences an uninitialized pointer that may result in a run-time error
GATE | GATE CS 2021

Consider the following ANSI C program: Answer: (D)

#include Explanation:
#include
struct Node{
int value; When you debug loop 1 you will get the linked list of size 4
struct Node *next;};
int main( ) { In the second loop value will be printed 0 0 1 1 2 2 3 3 after
struct Node *boxE, *head, *boxN; int index=0;
boxE=head= (struct Node *) malloc(sizeof(struct Node)); that head will be pointing to some random location and result
head → value = index; in run-time error.
for (index =1; index<=3; index++){ Correct Option (D)
boxN = (struct Node *) malloc (sizeof(struct Node));
boxE → next = boxN;
boxN → value = index;
boxE = 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 following statements below is correct about the program?
(A) Upon execution, the program creates a linked-list of five nodes
(B) Upon execution, the program goes into an infinite loop
(C) It has a missing return which will be reported as an error by the compiler
(D) It dereferences an uninitialized pointer that may result in a run-time error
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower
bound for the number of operations to convert the tree to a heap is
(A) Ω(logn)
(B) Ω(n)
(C) Ω(nlogn)
(D) Ω(n2)

GATE-CS-2015
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower
bound for the number of operations to convert the tree to a heap is
(A) Ω(logn)
(B) Ω(n)
(C) Ω(nlogn)
(D) Ω(n2)

Answer: (A)
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: Θ(N) delete,O(logN) insert, O(logN) find, and
Θ(N) decrease-key. What is the time complexity of all these operations put together?

What is the time complexity of all these operations put together ?

(A) O(Log2N)
(B) O(N)
(C) O(N2)
GATE 2016
(D) Θ(N2 Log N)
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: Θ(N) delete,O(logN) insert, O(logN) find, and
Θ(N) decrease-key. What is the time complexity of all these operations put together?

What is the time complexity of all these operations put together ?

(A) O(Log2N)
(B) O(N)
(C) O(N2)
GATE 2016
(D) Θ(N2 Log N) Delete - θ(1) time as pointer is directly given
Insert - O(N) time,we may need to insert at the end of the
sorted list..
Find - θ(N) time.. list we need to search sequentially..
Decrease key - θ(N) time, pointer is directly given, delete then
insert

Now using above..

θ(N) * θ(1) + O(logN) * O(N) + O(logN) * θ(N) + θ(N) * θ(N)
using property of asymptotic notation, and removing lower
terms, we get O(N2)..
So Answer O(N2)
GATE CS 1997

A priority queue Q is used to implement a stack S that stores characters. PUSH(C) is

implemented as INSERT(Q, C, K) where K is an appropriate integer key chosen by the
implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations,
the keys chosen are in
(A) Non-increasing order
(B) Non-decreasing order
(C) strictly increasing order
(D) strictly decreasing order
GATE | GATE CS 1997

A priority queue Q is used to implement a stack S that stores characters. PUSH(C) is implemented as INSERT(Q, C, K) where K is an
appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the
keys chosen are in
(A) Non-increasing order
(B) Non-decreasing order
(C) strictly increasing order
(D) strictly decreasing order

Answer: (D)

Explanation: We are implementing a STACK using Priority Queue. Note that Stack implementation is always last in first out (LIFO)
order.

As given “POP is implemented as DELETEMIN(Q)” that means Stack returns minimum element always.

So, we need to implement PUSH(C) using INSERT(Q, C, K) where K is key chosen from strictly-decreasing order(only this order will
ensure stack will return minimum element when we POP an element). That will satify Last In First Out (LIFO) property of stack.

That is answer, option (D) is true.

Option (A) non-increasing order can not be true because two same (identical) numbers can not have same priority as priority
should be distinguishable for each number.
 p

GATE 2014 Q R

The order in which the nodes are visited during in-order

traversal is
(A) SQPTRWUV S T U V
(B) SQPTURWV
(C) SQPTWUVR
(D) SQPTRUWV
W
 p

GATE 2014 Q R

The order in which the nodes are visited during in-order

traversal is
(A) SQPTRWUV S T U V
(B) SQPTURWV
(C) SQPTWUVR
(D) SQPTRUWV
W
GATE | GATE-CS-2007
The following postfix expression with single digit operands is evaluated using a stack:

823^/23*+51*-
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
(A) 6, 1
(B) 5, 7
(C) 3, 2
(D) 1, 5
GATE | GATE-CS-2007
The following postfix expression with single digit operands is evaluated using a stack:

823^/23*+51*-
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
(A) 6, 1
(B) 5, 7
(C) 3, 2
(D) 1, 5

Answer: (A)
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed
efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the
queue)?
GATE 2016
(A) Both operations can be performed in O(1) time
(B) At most one operation can be performed in O(1) time but the worst case time for the other operation
will be Ω(n)
(C) The worst case time complexity for both operations will be Ω(n)
(D) Worst case time complexity for both operations will be Ω(log n)
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently.
Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

(A) Both operations can be performed in O(1) time

(B) At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
(C) The worst case time complexity for both operations will be Ω(n)
(D) Worst case time complexity for both operations will be Ω(log n) GATE 2016
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?
(A) Θ(1), Θ(1)
(B) Θ(1), Θ(n)
(C) Θ(n), Θ(1) …….
(D) Θ(n), Θ(n)

head tail
GATE 2018
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?
(A) Θ(1), Θ(1)
(B) Θ(1), Θ(n)
(C) Θ(n), Θ(1) 1 2 N-1 n
(D) Θ(n), Θ(n)
…….

head tail
Enqueue = Beginning O(1)
Dequeue = End O (n) since it requires
GATE 2018
the address on n-1 node
A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the
array. Variables top1 and top2 (top1< top 2) point to the location of the topmost element in each of the stacks. If
the space is to be used efficiently, the condition for “stack full” is
(a) (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
(b) top1 + top2 = MAXSIZE
(c) (top1= MAXSIZE/2) or (top2 = MAXSIZE)
GATE 2004
(d) top1= top2 -1
A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the
array. Variables top1 and top2 (top1< top 2) point to the location of the topmost element in each of the stacks. If
the space is to be used efficiently, the condition for “stack full” is
(a) (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
(b) top1 + top2 = MAXSIZE
(c) (top1= MAXSIZE/2) or (top2 = MAXSIZE)
GATE 2004
(d) top1= top2 -1
top1+ top2= maxsize

top1 top2

19 21(top2)
12 13 14 15 16 17 18 20
(top1)

here top1= top2-1 shows stack is full only.

It's an array containing the elements

12,13,14,15,16,17,18,19,21 and 20 and top1 and top2 mark
the top of the two stacks respectively where the 1st stack
grows from left to right and the second one vice versa.
 struct item
For a given linked list p, the function f returns 1 if and
only if
{
int data;
GATE 2003
(A) not all elements in the list have the same data value.
(B) the elements in the list are sorted in non-decreasing struct item * next;
order of data value };
(C) the elements in the list are sorted in non-increasing
order of data value int f(struct item *p)
(D) None of them {
return (
(p == NULL) ||
(p->next == NULL) ||
(( P->data <= p->next->data) && f(p->next))
);
}
 struct item
For a given linked list p, the function f returns 1 if and
only if
{
int data;
GATE 2003
(A) not all elements in the list have the same data value.
(B) the elements in the list are sorted in non-decreasing struct item * next;
order of data value };
(C) the elements in the list are sorted in non-increasing
order of data value int f(struct item *p)
(D) None of them {
return (
(p == NULL) ||
(p->next == NULL) ||
(( P->data <= p->next->data) && f(p->next))
);
}

The function f() works as follows

1) If linked list is empty return 1
2) Else If linked list has only one element return 1
3) Else if node->data is smaller than equal to node->next->data and
same thing holds for rest of the list then return 1
4) Else return 0
Suppose each set is represented as a linked list with elements
in arbitrary order. Which of the operations among union,
intersection, membership, cardinality will be the slowest?
GATE 2004
(A) union only
(B) intersection, membership
(C) membership, cardinality
(D) union, intersection
Suppose each set is represented as a linked list with elements
in arbitrary order. Which of the operations among union,
intersection, membership, cardinality will be the slowest?
GATE 2004
(A) union only
(B) intersection, membership
(C) membership, cardinality Membership is linear search - O(n1+n2)
(D) union, intersection

Cardinality is linear - O(n1+n2)

For union we need to ensure no duplicate

elements should be present - O(n1×n2)
for each element we need to check if that
element exists in other set

For intersection also for every element in set1

we need to scan set2 - O(n1×n2)
 The following C function takes a simply-linked list as input
argument. It modifies the list by moving the last element to
typedef struct node
the front of the list and returns the modified list. Some part of
{
the code is left blank. Choose the correct alternative to int value;
replace the blank line. struct node *next;
}Node;
(A) q = NULL; p->next = head; head = p; Node *move_to_front(Node *head)
(B) q->next = NULL; head = p; p->next = head; {
Node *p, *q;
(C) head = p; p->next = q; q->next = NULL; if ((head == NULL || (head->next == NULL))
return head;
(D) q->next = NULL; p->next = head; head = p; q = NULL; p = head;
while (p-> next !=NULL)
{

GATE 2010 }
q = p;
p = p->next;

_______________________________
return head;
}
(A) q = NULL; p->next = head; head = p;
(B) q->next = NULL; head = p; p->next = head; typedef struct node
{
(C) head = p; p->next = q; q->next = NULL; int value;
(D) q->next = NULL; p->next = head; head = p; 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;
}
GATE CSE 2014 Set 3
Numerical
+2
-0

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H
and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T.
If the tightest upper bound on the time to compute the sum is O( na logb n + mc logd n ), the value of a + 10b
+ 100c + 1000d is _______.
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not
known which is which. MBCAFHPYK KAMCBYPFH MABCKYFPH Pick the true statement from the following.
A
I and II are preorder and inorder sequences, respectively
B
I and III are preorder and postorder sequences, respectively
C
II is the inorder sequence, but nothing more can be said about the other two sequences
D
II and III are the preorder and inorder sequences, respectively
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder
traversal of the binary tree is:
A
debfgca
B
edbgfca
C
edbfgca
D
defgbca
GATE | Gate IT 2007
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are
traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur
on the search path from the root to the node containing the value 60?
(A) 35
(B) 64
(C) 128
(D) 5040
GATE | Gate IT 2007
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are
traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur
on the search path from the root to the node containing the value 60?
(A) 35
(B) 64
(C) 128
(D) 5040

Answer: (A)

Explanation: There are two set of values, smaller than 60 and greater than 60. Smaller values 10, 20, 40 and 50 are
visited, means they are visited in order. Similarly, 90, 80 and 70 are visited in order.
= 7!/(4!3!)
= 35
 Gate CS 2012
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the
pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer
root.
The appropriate expression for the two boxes B1 and B2 are
(A) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
(B) B1 : (height(n->right)), B2 : (1 + max(h1,h2))
(C) B1 : height(n->right), B2 : max(h1,h2)
(D) B1 : (1 + height(n->right)), B2 : max(h1,h2)
 Gate CS 2012
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the
pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer
root.
The appropriate expression for the two boxes B1 and B2 are
(A) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
(B) B1 : (height(n->right)), B2 : (1 + max(h1,h2))
(C) B1 : height(n->right), B2 : max(h1,h2)
(D) B1 : (1 + height(n->right)), B2 : max(h1,h2)

Answer: (A)

Explanation: The box B1 gets executed

when left subtree of n is NULL and right
subtree is not NULL. In this case, height of n
will be height of right subtree plus one.
The box B2 gets executed when both left
and right subtrees of n are not NULL. In this
case, height of n will be max of heights of
left and right subtrees of n plus 1.
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305

Gate CS 2008
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes
in the order in which we could have encountered them in the search?
(A) II and III only
(B) I and III only
(C) III and IV only
(D) III only
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305

Gate CS 2008
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes
in the order in which we could have encountered them in the search?
(A) II and III only
(B) I and III only
(C) III and IV only
(D) III only
GATE | Gate IT 2008

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

Which of the following statements is TRUE?

(A) I, II and IV are inorder sequences of three different BSTs
(B) I is a preorder sequence of some BST with 439 as the root
(C) II is an inorder sequence of some BST where 121 is the root and 52 is a leaf
(D) IV is a postorder sequence of some BST with 149 as the root
GATE | Gate IT 2008

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

Which of the following statements is TRUE?

(A) I, II and IV are inorder sequences of three different BSTs
(B) I is a preorder sequence of some BST with 439 as the root
(C) II is an inorder sequence of some BST where 121 is the root and 52 is a leaf
(D) IV is a postorder sequence of some BST with 149 as the root

Answer: (C)

Explanation: A: I and IV are not in ascending order

B: If 439 is root, It should be 1st element in preorder
D: If 149 is root, It should be last element in postorder
What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?
(A) O(n) for all
(B) O(Logn) for all
(C) O(Logn) for search and insert, and O(n) for delete
(D) O(Logn) for search, and O(n) for insert and delete GATE 2015
What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?
(A) O(n) for all
(B) O(Logn) for all
(C) O(Logn) for search and insert, and O(n) for delete
(D) O(Logn) for search, and O(n) for insert and delete GATE 2015
GATE-CS-2016

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such
that the resulting tree has height 6, is _____________
Note: The height of a tree with a single node is 0.
[This question was originally a Fill-in-the-Blanks question]
(A) 2
(B) 4
(C) 64
(D) 32
GATE-CS-2016

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such
that the resulting tree has height 6, is _____________
Note: The height of a tree with a single node is 0.
[This question was originally a Fill-in-the-Blanks question]
(A) 2
(B) 4 So at 1st level, we either can choose 1 or 7(2 choices)

(C) 64 At 2nd level,similarly we can choose 2 or 6(2 choices)

(D) 32 At 3rd level,similarly we can choose 3 or 5(2 choices)

At 4th level,similarly we can choose 4 or 4(2 choices)
At 5th level,similarly we can choose 5 or 3(2 choices)
At 6th level,similarly we can choose 6 or 2(2 choices)
At 7th level, we will have only 1 number remaining.
So total number of BSTs possible=2^6=64
GATE | Gate IT 2008
A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The
degree of a node is defined as the number of its neighbors.
n3 can be expressed as
(A) n1 + n2 – 1
(B) n1 – 2
(C) [((n1 + n2)/2)]
(D) n2 – 1
GATE | Gate IT 2008
A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The
degree of a node is defined as the number of its neighbors.
n3 can be expressed as
(A) n1 + n2 – 1
(B) n1 – 2
(C) [((n1 + n2)/2)]
(D) n2 – 1
 GATE | Gate IT 2008

A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node
is defined as the number of its neighbors.
Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two
neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?
(A) 2 * n1 – 3
(B) n2 + 2 * n1 – 2
(C) n3 – n2
(D) n2 + n1 – 2
A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node
is defined as the number of its neighbors.
Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two
neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?
(A) 2 * n1 – 3
(B) n2 + 2 * n1 – 2
(C) n3 – n2
(D) n2 + n1 – 2

Answer: (A)
Consider the following graph among the following sequences
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e

Which are depth first traversals of the above graph?

(A) I, II and IV only
(B) I and IV only
(C) II, III and IV only
(D) I, III and IV only

GATE 2003
Consider the following graph among the following sequences
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e

Which are depth first traversals of the above graph?

(A) I, II and IV only
(B) I and IV only
(C) II, III and IV only
(D) I, III and IV only

GATE 2003
In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected
components in G is
(A) k
(B) k + 1
(C) n – k – 1
(D) n – k GATE 2004
In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected
components in G is
(A) k
(B) k + 1
(C) n – k – 1
(D) n – k

Answer: (D)

Explanation: Tree edges are the edges that are part of DFS tree. If there are x tree edges in a tree, then x+1 vertices in
the tree.
The output of DFS is a forest if the graph is disconnected.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First
Search of G? Assume that the graph is represented using adjacency matrix.
(A) O(n)
(B) O(m+n)
(C) O(n2)
(D) O(mn)

GATE 2014
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First
Search of G? Assume that the graph is represented using adjacency matrix.
(A) O(n)
(B) O(m+n)
(C) O(n2)
(D) O(mn)

GATE 2014
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph.
The tree T formed by the tree arcs is a data structure for computing.
(A) the shortest path between every pair of vertices.
(B) the shortest path from W to every vertex in the graph.
GATE 2014
(C) the shortest paths from W to only those nodes that are leaves of T.
(D) the longest path in the graph
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph.
The tree T formed by the tree arcs is a data structure for computing.
(A) the shortest path between every pair of vertices.
(B) the shortest path from W to every vertex in the graph.
(C) the shortest paths from W to only those nodes that are leaves of T.
(D) the longest path in the graph
Answer: (B)
BFS always produces shortest paths from source to all other vertices in an unweighted graph. The reason is simple,
in BFS, we first explore all vertices which are 1 edge away from source, then we explore all vertices which are 2
edges away from the source and so on.
The number of different topological orderings of the vertices of
the graph is

Note : This question was asked as Numerical Answer Type.

(A) 1
(B) 2
(C) 4
(D) 6
GATE 2016
The number of different topological orderings of the vertices of
the graph is

Note : This question was asked as Numerical Answer Type.

(A) 1
(B) 2
(C) 4
(D) 6
GATE 2016
Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let
d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during
the breadth-first traversal, which of the following statements is correct?
(A) d(r, u) < d(r, v)
(B) d(r,u) > d(r,v)
(C) d(r,u) <= (r,v)
(D) None of the above
GATE 2001
Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let
d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during
the breadth-first traversal, which of the following statements is correct?
(A) d(r, u) < d(r, v)
(B) d(r,u) > d(r,v)
(C) d(r,u) <= (r,v)
(D) None of the above
GATE 2001
Answer: (C)
Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u
be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following
statements is always true?
(A) {u,v} must be an edge in G, and u is a descendant of v in T
(B) {u,v} must be an edge in G, and v is a descendant of u in T
(C) If {u,v} is not an edge in G then u is a leaf in T
(D) If {u,v} is not an edge in G then u and v must have the same parent in T
GATE 2000
Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u
be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following
statements is always true?
(A) {u,v} must be an edge in G, and u is a descendant of v in T
(B) {u,v} must be an edge in G, and v is a descendant of u in T
(C) If {u,v} is not an edge in G then u is a leaf in T
(D) If {u,v} is not an edge in G then u and v must have the same parent in T
GATE 2000
Answer: (C)
Gate IT 2007
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m
different spanning trees?
(A) 1
(B) 2
(C) 3
(D) n
Gate IT 2007
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m
different spanning trees?
(A) 1
(B) 2
(C) 3
(D) n
Consider the following sequence of nodes for the undirected graph given below.
1.a b e f d g c
2.a b e f c g d
3.a d g e b c f
4.a d b c g e f
A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the
above is (are) possible output(s)?
(A) 1 and 3 only
(B) 2 and 3 only
(C) 2, 3 and 4 only
(D) 1, 2, and 3

Gate IT 2008
Consider the following sequence of nodes for the undirected graph given below.
1.a b e f d g c
2.a b e f c g d
3.a d g e b c f
4.a d b c g e f
A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the
above is (are) possible output(s)?
(A) 1 and 3 only
(B) 2 and 3 only
(C) 2, 3 and 4 only
(D) 1, 2, and 3
Which of the following statement is false?
(A) A tree with n nodes has (n-1) edges.
(B) A labeled rooted binary tree can be uniquely constructed given its postorder and
preorder traversal results.
(C) A complete binary tree with n internal nodes has (n+1) leaves.
(D) The maximum number of nodes in a binary tree of height h is (2^(h+1) -1).

Gate IT 1998
Which of the following statement is false?
(A) A tree with n nodes has (n-1) edges.
(B) A labeled rooted binary tree can be uniquely constructed given its postorder and
preorder traversal results.
(C) A complete binary tree with n internal nodes has (n+1) leaves.
(D) The maximum number of nodes in a binary tree of height h is (2^(h+1) -1).

Answer: (B) (C)

Gate IT 1998
The following numbers are inserted into an empty binary search tree in the
given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree
(the height is the maximum distance of a leaf node from the root)?
(A) 2
(B) 3
(C) 4
(D) 6

Gate IT 2004
The following numbers are inserted into an empty binary search tree in the
given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree
(the height is the maximum distance of a leaf node from the root)?
(A) 2
(B) 3
(C) 4
(D) 6

Answer: (B)

Gate IT 2004
The numbers 1, 2, …. n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the
root contains p nodes. The first number to be inserted in the tree must be
(A) p
(B) p + 1
(C) n – p
(D) n – p + 1

Gate IT 2005
The numbers 1, 2, …. n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the
root contains p nodes. The first number to be inserted in the tree must be
(A) p
(B) p + 1
(C) n – p
(D) n – p + 1

Answer: (C)

Gate IT 2005
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at
X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to
store any binary tree on n vertices the minimum size of X should be.
(A) log2n
(B) n
(C) 2n + 1
(D) 2^n — 1

Gate IT 2006
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at
X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to
store any binary tree on n vertices the minimum size of X should be.
(A) log2n
(B) n
(C) 2n + 1
(D) 2^n — 1

Answer: (D)

Gate IT 2006
The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1
(B) 5
(C) 4
(D) 3

Gate IT 2007
The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1
(B) 5
(C) 4
(D) 3

Answer: (B)

Gate IT 2007
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

1. 3, 5, 7, 8, 15, 19, 25
2. 5, 8, 9, 12, 10, 15, 25
3. 2, 7, 10, 8, 14, 16, 20
4. 4, 6, 7, 9, 18, 20, 25
(A) 1 and 4 only
(B) 2 and 3 only
(C) 2 and 4 only
(D) 2 only

Gate IT 2015
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

1. 3, 5, 7, 8, 15, 19, 25
2. 5, 8, 9, 12, 10, 15, 25
3. 2, 7, 10, 8, 14, 16, 20
4. 4, 6, 7, 9, 18, 20, 25
(A) 1 and 4 only
(B) 2 and 3 only
(C) 2 and 4 only
(D) 2 only

Gate IT 2015
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
(A) Θ(logn) for both insertion and deletion
(B) Θ(n) for both insertion and deletion
(C) Θ(n) for insertion and Θ(logn) for deletion
(D) Θ(logn) for insertion and Θ(n) for deletion

Gate IT 2015
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
(A) Θ(logn) for both insertion and deletion
(B) Θ(n) for both insertion and deletion
(C) Θ(n) for insertion and Θ(logn) for deletion
(D) Θ(logn) for insertion and Θ(n) for deletion

Answer: (B)

Explanation: The time taken by search, insert and delete on a BST is always proportional to height of BST.
Height may become O(n) in worst case.

Gate IT 2015
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower
bound for the number of operations to convert the tree to a heap is
(A) Ω(logn)
(B) Ω(n)
(C) Ω(nlogn)
(D) Ω(n2)

GATE-CS-2015
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower
bound for the number of operations to convert the tree to a heap is
(A) Ω(logn)
(B) Ω(n)
(C) Ω(nlogn)
(D) Ω(n2)

Answer: (A)
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the
element in the lowest level is
(A) 65
(B) 67
(C) 69
(D) 83

GATE-CS-2015
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the
element in the lowest level is
(A) 65
(B) 67
(C) 69
(D) 83

Answer: (B)

GATE-CS-2015
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the
postorder traversal of the tree ?
(A) 10, 11, 12, 15, 16, 18, 19, 20
(B) 11, 12, 10, 16, 19, 18, 20, 15
(C) 20, 19, 18, 16, 15, 12, 11, 10
(D) 19, 16, 18, 20, 11, 12, 10, 15

GATE-CS-2020
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the
postorder traversal of the tree ?
(A) 10, 11, 12, 15, 16, 18, 19, 20
(B) 11, 12, 10, 16, 19, 18, 20, 15
(C) 20, 19, 18, 16, 15, 12, 11, 10
(D) 19, 16, 18, 20, 11, 12, 10, 15

Answer: (B)

GATE-CS-2020