1- What is Breadth First Search(BFS) Traversal and Depth First Search(DFS)
Traversal?
Or
How to construct BFS Tree and DFS Tree for a given graph?
Or
How to find the shortest path in an undirected unweighted connected graph
using BFS?
Learn
2- How to construct a Binary Search Tree using Preorder/Postorder?
Or
Can we construct a unique Tree using Preorder/Postorder?
Learn
3- What is Queue and Stack?
Learn
4- What is Max Heap/ Min Heap?
Or
What is Complete Binary Tree?
Learn
5- What is Topological Ordering?
Learn
6- How to construct an Expression Tree for a given Postfix/Prefix expression?
Learn
7- What are the minimum and maximum number of nodes that can be inserted
in a binary tree of given hight ‘h’?
Learn
8- What is Young Tableau Puzzle?
Learn
9- What is Hash Table and Hash Function?
Or
What is Open Addressing and Linear Probing?
Learn
10- What is Load Factor in Hash Table?
Learn
11- What is Infix, Prefix and Postfix expression?
Learn
12- What is Priority Queue?
Learn
13- Height of a Binary Tree.
Or
Height of a Binary Tree using Recursion.
Learn
14- What is Circular Queue?
Learn
Q1- Topic:- BFS/DFS
Breath First Search(BFS) has been implemented using queue data structure.
Which one of the following is a possible order of visiting the nodes in the graph
above.
(A) MNOPQR
(B) NQMPOR
(C) QMNROP
(D) POQNMR
Option: D
Solution
Q2- Topic:- Preorder/ Postorder
The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10,
16, 15, 19, 17, 20.
Then the post-order traversal of this tree is:
(A) 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
(B) 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
(C) 7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
(D) 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12
Option: B
Solution
Q3- Topic:- Queue + Stack
Let Q denote a queue containing sixteen numbers and S be an empty stack.
Head(Q) returns the element at the head of the queue Q without removing it
from Q. Similarly Top(S) returns the element at the top of S without removing it
from S. Consider the algorithm given below.
while Q is not Empty do
if S is Empty OR Top(S) ≤ Head (Q) then
x:= Dequeue (Q);
Push (S, x);
else
x:= Pop(S);
Enqueue (Q, x);
end
end
The maximum possible number of iterations of the while loop in the algorithm
is_________.
Answer: 256
Solution
Q4- Topic:- Min Heap
A complete binary min-heap is made by including each integer in [1, 1023]
exactly once. The depth of a node in the heap is the length of the path from the
root of the heap to that node. Thus, the root is at depth 0. The maximum depth
at which integer 9 can appear is _____________
(A) 6
(B) 7
(C) 8
(D) 9
Option: C
Solution
Q5- Topic:- Topological Order
Consider the following directed graph.
The number of different topological orderings of the vertices of the graph
is___________.
Answer: 6
Solution
Q6- Topic:- Breadth First Search
Breadth First Search (BFS) is started on a binary tree beginning from the root
vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex
in this BFS traversal, then the maximum possible value of n is ___________.
Answer: 31
Solution
Q7- Topic:- New Order Traversal
Consider the following New-order strategy for traversing a binary tree:
Visit the root;
Visit the right subtree using New-order
Visit the left subtree using New-order
The New-order traversal of the expression tree corresponding to the reverse
polish expression 3 4 * 5 – 2 ˆ 6 7 * 1 + – is given by:
(A) + – 1 6 7 * 2 ˆ 5 – 3 4 *
(B) – + 1 * 6 7 ˆ 2 – 5 * 3 4
(C) – + 1 * 7 6 ˆ 2 – 5 * 4 3
(D) 1 7 6 * + 2 5 4 3 * – ˆ –
Option: C
Solution
Q8- Topic:- Binary Search Tree
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.
Answer: 64
Solution
Q9- Topic:- Binary Tree
The height of a tree is the length of the longest root-to-leaf path in it. The
maximum and minimum number of nodes in a binary tree of height 5 are
(A) 63 and 6, respectively
(B) 64 and 5, respectively
(C) 32 and 6, respectively
(D) 31 and 5, respectively
Option: A
Solution
Q10- Topic:- Max Heap
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.
Now consider that a value 35 is inserted into this heap. After insertion, the new
heap is
(A) 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
(B) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
(C) 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
(D) 40, 35, 20, 10, 15, 16, 17, 8, 4, 30
Option: B
Solution
Q11- Topic:- Hash Function
Which one of the following hash functions on integers will distribute keys most
uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
(A) h(i) = (12 ∗ i) mod 10
(B) h(i) = (11 ∗ i2) mod 10
(C) h(i) =i3 mod 10
(D) h(i) =i2 mod 10
Option: C
Solution
Q12- Topic:- Young Tableau
A Young tableau is a 2D array of integers increasing from left to right and from
top to bottom. Any unfilled entries are marked with ∞, and hence there cannot
be any entry to the right of, or below a ∞. The following Young tableau consists
of unique entries.
1 2 5 14
3 4 6 23
10 12 18 25
31 ∞ ∞ ∞
When an element is removed from a Young tableau, other elements should be
moved into its place so that the resulting table is still a Young tableau (unfilled
entries may be filled in with a ∞). The minimum number of entries (other than 1)
to be shifted, to remove 1 from the given Young tableau is ____________
(A) 2
(B) 5
(C) 6
(D) 18
Option: B
Solution
Q13- Topic:- Load Factor
Given a hash table T with 25 slots that stores 2000 elements, the load factor α
for T is ____________.
(A) 80
(B) 0.0125
(C) 8000
(D) 1.25
Option: A
Solution
Q14- Topic:- Max Heap
Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6,
9, 100〉. The minimum number of interchanges needed to convert it into a max-
heap is
(A) 4
(B) 5
(C) 2
(D) 3
Option: D
Solution
Q15- Topic:- Binary Search Tree
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
Option: B
Solution
Q16- Topic:- Postfix Expression
The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is
(A) 284
(B) 213
(C) 142
(D) 71
Option: C
Solution
Q17- Topic:- Binary Tree
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T
that have exactly two children are _________.
(A) 199
(B) 200
(C) Any number between 0 and 199
(D) Any number between 100 and 200
Option: A
Solution
Q18- Topic:- Shortest Path Using BFS
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
Option: B
Solution
Q19- Topic:- Priority Queue
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The
level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are
inserted into the heap in that order. The level-order traversal of the heap after
the insertion of the elements is:
(A) 10, 8, 7, 3, 2, 1, 5
(B) 10, 8, 7, 2, 3, 1, 5
(C) 10, 8, 7, 1, 2, 3, 5
(D) 10, 8, 7, 5, 3, 2, 1
Option:- A
Solution
Q20- Topic:- Hash Table
Consider a hash table with 9 slots. The hash function is ℎ(k) = k mod 9. The
collisions are resolved by chaining. The following 9 keys are inserted in the
order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average
chain lengths in the hash table, respectively, are-
(A) 3, 0, and 1
(B) 3, 3, and 3
(C) 4, 0, and 1
(D) 3, 0, and 2
Option: A
Solution
Q21- Topic:- Topological Order
Consider the directed graph given below. Which one of the following is TRUE?
(A) The graph doesn’t have any topological ordering
(B) Both PQRS and SRPQ are topological ordering
(C) Both PSRQ and SPRQ are topological ordering
(D) PSRQ is the only topological ordering
Option: C
Solution
Q22- Topic:- Circular Queue
Suppose a circular queue of capacity (n – 1) elements is implemented with an
array of n elements. Assume that the insertion and deletion operation are carried
out using REAR and FRONT as array index variables, respectively. Initially,
REAR = FRONT = 0. The conditions to detect queue full and queue empty are-
(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
(B) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
(C) Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
(D) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
Option: A
Solution
Q23- Topic:- Binary Tree
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)
Option: A
Solution
Q24- Topic:- Preorder/ Postorder
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?
(A) 10, 20, 15, 23, 25, 35, 42, 39, 30
(B) 15, 10, 25, 23, 20, 42, 35, 39, 30
(C) 15, 20, 10, 23, 25, 42, 35, 39, 30
(D) 15, 10, 23, 25, 20, 35, 42, 39, 30
Option: D
Solution
Q25- Topic:- Max Heap
A max-heap is a heap where the value of each parent is greater than or equal to
the values of its children. Which of the following is a max-heap?
(A) A
(B) B
(C) C
(D) D
Option: B
Solution
Q26- Topic:- Binary Search Tree
We are given a set of n distinct elements and an unlabelled binary tree with n
nodes. In how many ways can we populate the tree with the given set so that it
becomes a binary search tree?
(A) 0
(B) 1
(C) n!
(D) (1/(n+1)).2nCn
Option: B
Solution
Q27- Topic:- Linked List
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. Choose the correct alternative
to replace the blank line.
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;
(A) q = NULL; p->next = head; head = p;
(B) q->next = NULL; head = p; p->next = head;
(C) head = p; p->next = q; q->next = NULL;
(D) q->next = NULL; p->next = head; head = p;
Option: D
Solution
Q28- Topic:- Binary Tree
In a binary tree with n nodes, every node has an odd number of descendants.
Every node is considered to be its own descendant. What is the number of
nodes in the tree that have exactly one child?
(A) 0
(B) 1
(C) (n-1)/2
(D) n-1
Option: A
Solution
Q29- Topic:- Spanning Tree
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in
the matrix W below is the weight of the edge {i, j}.
What is the minimum possible weight of a spanning tree T in this graph such
that vertex 0 is a leaf node in the tree T?
(A) 7
(B) 8
(C) 9
(D) 10
Option: D
Solution
Q30- Topic:- Hash Table
A hash table of length 10 uses open addressing with hash function h(k)=k mod
10, and linear probing. After inserting 6 values into an empty hash table, the
table is as shown below.
Which one of the following choices gives a possible order in which the key
values could have been inserted in the table?
(A) 46, 42, 34, 52, 23, 33
(B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33
(D) 42, 46, 33, 23, 34, 52
Option: C
Solution
Q31- Topic:- Hash Table
How many different insertion sequences of the key values using the same hash
function and linear probing will result in the hash table shown above?
(A) 10
(B) 20
(C) 30
(D) 40
Option: C
Solution
