Data-Structures
Question 1 |
Finding the diameter of the graph | |
Finding the bipartite graph | |
Both (a) and (b) | |
None of the above |
Examples
1. Copying garbage collection, Cheney's algorithm
2. Find the diameter of the graph
3. Testing bipartiteness of a graph.
4. Finding the shortest path between two nodes u and v, with path length measured by the number of edges (an advantage over depth-first search)
5. (Reverse) Cuthill–McKee mesh numbering
6. Ford–Fulkerson method for computing the maximum flow in a flow network
7. Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be reconstructed in an efficient manner.
8. Construction of the failure function of the Aho-Corasick pattern matcher.
Question 2 |

X→ Bwd→ Fwd = X→ Fwd; X→ Fwd → Bwd = X→ Bwd ; | |
X→ Bwd.Fwd = X→ Fwd ; X.Fwd→ Bwd = X→ Bwd ; | |
X.Bwd→ Fwd = X.Bwd ; X→ Fwd.Bwd = X.Bwd ; | |
X→ Bwd→ Fwd = X→ Bwd ; X→ Fwd→ Bwd = X→ Fwd; |
we need x→ Bwd→ Fwd = x.
Fwd and in order to link z to y, we need x→ Fwd→ Bwd=x→ Bwd.
Question 3 |

Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence?
Preorder, Postorder | |
Postorder, Inorder | |
Postorder, Preorder | |
Inorder, Preorder |
→ Post order traverses Left, Right, Root.
→ In-order traverses Left, Root, Right.
Tree-1: Post order: GJIHEFBDCA
Tree-2: In order: GJIHEFBDCA
Question 4 |

Delete the last element of the list | |
Delete the first element of the list | |
Add an element after the last element of the list | |
Interchange the first two elements of the list |
Option B: It needs only the operation F=F→ next
Option C: It needs only the operations L→ next=new node, L = new node
Option D: It needs only the operations T=F, F=F→ next, T→ next =F→ next, F→ next=T
→ All these operations do not depend on the length of the list.
→ Indeed in order to delete the last element from the list, we need to first locate the element before the last (which can not be accessed from L). Thus we must parse all the list from the first and till the element just before the last after which we can delete the last element and assign L to the one before.
Question 5 |
14,13,8,12,10 | |
14,12,13,10,8 | |
14,13,12,8,10 | |
14,13,12,10,8 |

Step-2: We have to perform 2 delete operations.
In max-heap (or) min-heap by default we are deleting root element only.
After 1st delete, the heap structure is

Step-3: After 2nd delete operation, the heap structure is

Question 6 |

4 | |
5 | |
6 | |
3 |
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum number of comparisons = 4 + 1 = 5
Question 7 |
I. P has a local variable
II. P has an execution path where it does not call itself
III. P either refers to a global variable or has at least one parameter
I only | |
II only | |
III only | |
II and III only |
→ P has an execution path where it does not call itself
→ P either refers to a global variable or has at least one parameter
Recursion Rules
Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.
The recursive calls must eventually reach a base case, which is solved without further recursion.
Question 8 |
A | |
B | |
C | |
D |
Question 9 |
all zeros | |
all ones | |
both zeros and ones | |
different |
Question 10 |
(i) Insertion of an element should be done at the last node in a circular list
(ii) Deletion of an element should be done at the last node of the circular list
Both are true | |
Both are false | |
First is false and second is true | |
None of the above |
1.Insertion at the front of Circular linked list.
2.Insertion in the middle of the Circular linked list.
3.Insertion at the end of the Circular linked list.
Question 11 |
Stack | |
List | |
Queue | |
None of the above |

Question 12 |
Queue | |
Stack | |
Tree | |
List |
→ While evaluating when left parentheses occur then it pushes into the stack when right parentheses occur pop from the stack. While at the end there is empty in the stack.
Question 13 |
* +a − bc /− de − +fgh | |
* +a −bc − /de − +fgh | |
* +a − bc /− ed + −fgh | |
* +ab − c /− ed + −fgh |


Question 14 |
4 | |
0 | |
1 | |
None of these |
Note: Excluded for evaluation.
Question 15 |
Type COLOGNE : (LIME, PINE, MUSK, MENTHOL); var a : array [COLOGNE] of REAL; | |
var a : array [REAL] of REAL; | |
var a : array [‘A’…’Z’] of REAL; | |
var a : array [BOOLEAN] of REAL; |
Expect the option B, All remaining indexes are not real numbers.
Option A , takes enum value as index which is integer number.
Option C, takes character which is having equivalent decimal value.
Option D, has boolean value as index whose value may be 0 or 1
Question 16 |
15 | |
10 | |
7 | |
9 |
The number of distinct simple graphs with up to three nodes:

So, total 7 unlabeled nodes are possible. Option (C) is correct.
Question 17 |
n2 | |
n * (n-1)/2 | |
n – 1 | |
(n + 1) * n/2 |
Question 18 |
A secondary access path | |
A physical record key | |
An inverted index | |
A primary key |
1. To understand how pointers and their associated data elements are allocated in Microsoft RPC, you have to differentiate between top-level pointers and embedded pointers
2. Top-level pointers are those that are specified as the names of parameters in function prototypes. Top-level pointers and their referents are always allocated on the server.
3. Embedded pointers are pointers that are embedded in data structures such as arrays, structures, and unions. When embedded pointers only write output to a buffer and are null on input, the server application can change their values to non-null. In this case, the client stubs allocate new memory for this data.
4. If the embedded pointer is not null on the client before the call, the stubs do not allocate memory on the client on return. Instead, the stubs attempt to write the memory associated with the embedded pointer into the existing memory on the client associated with that pointer, overwriting the data already there.
Question 19 |
function F(K : integer)
integer;
begin
if (k<3) then F:=k
else F:=F(k-1)*F(k-2)+F(k-3)
end;
5 | |
6 | |
7 | |
8 |
F(4) = F(3)*F(2)+F(1) = 5
F(3) = F(2)*F(1)+F(0) = 2
F(2) = 2
F(1) = 1
F(0) = 0
Question 20 |
b a c | |
b c a | |
c a b | |
a b c |
Option (A):
Pop a from stack A
Push a to stack B
Print b
Print a from stack B
Print c from stack A
Order = b a c
Option (B):
Pop a from stack A
Push a to stack B
Print b from stack A
Print c from stack A
Print a from stack A
Order = b c a
Option (C):
Pop a from stack A
Push a to stack B
Pop b from stack A
Push b to stack B
Print c from stack A
Now, printing a will not be possible.
Question 21 |
O(log n) | |
O(n) | |
O(1) | |
(n2) |
Question 22 |
Deleting a node whose location is given | |
Searching an unsorted list for a given item | |
Inserting a node after the node with a given location | |
Traversing the list to process each node |
Inserting the node after the node with the a given location won’t require of traversing the list to previous nodes or memory locations.In this case also, there is no difference between whether it may be linear linked list or doubly linked list.
The main purpose of double linked list is to traverse the list in both directions so Deleting the node becomes easy while traversing the both directions.
Question 23 |
O(log n) | |
O(n) | |
O(1) | |
O(n2) |
Question 24 |
binary search tree | |
AVL tree | |
completely balanced tree | |
Heap |
Question 25 |
1 | |
2 | |
3 | |
4 |
However, each node of doubly linked list can have only 2 fields, i.e., XOR pointer field, and data field. This XOR pointer field can points both previous node and next node, this is the best case with data field. This is called as memory efficient
doubly linked list, Also, if we remove data node from the XOR linked list, then each node of this doubly linked list can have only 1 field, i.e., XOR pointer field. But, this is without data field so, this doubly linked list does not make sense.
Question 26 |
A+B−C∗D | |
+A∗−BCD | |
ABC−D∗+ | |
A+BC−D∗ |
Given Expression = A + (B – C)* D
Prefix Notation:
A + (- B C) * D
A + (* - B C D)
+ A * - B C D
Question 27 |
7 5 1 0 3 2 4 6 8 9 | |
0 2 4 3 1 6 5 9 8 7 | |
0 1 2 3 4 5 6 7 8 9 | |
9 8 6 4 2 3 0 1 5 7 |
The in-order traversal of BST will gives the elements in the sorted order( ascending order)
Question 28 |
I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?
A heap can be used but not a balanced binary search tree | |
A balanced binary search tree can be used but not a heap | |
Both balanced binary search tree and heap can be used | |
Neither balanced search tree nor heap can be used |
A self-balancing binary search tree containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a self balancing BST, we can easily find out minimum element in O(logn) time which is always the leftmost element.
Question 29 |
2 | |
3 | |
4 | |
6 |

So, height of the tree is defined maximum distance of a leaf node from the root.The root node is “10” and lead node is “5”.The maximum distance is 3
Question 30 |
abc x + def ^ ^ − | |
abc x + de ^ f ^ − | |
ab + c × d − e^f^ | |
− + a × b c^^ def |
The operators in the expression are +,x,- ^
First we will convert e^f ad ef^ (as highest precedence and right associativity) and later
d ^( e f ^ ) to def^^ and so on , you can find the same thing from the below steps.
The postfix expression:
a + b × c − ( d ^( e ^ f))
a + b × c − ( d ^( e f ^ ))
a + b × c − ( d e f ^ ^)
(a + (b × c)) − d e f ^ ^
(a + (b c x)) − d e f ^ ^
(a (b c x) +) − d e f ^ ^
(a b c x +) - (d e f ^ ^)
(a b c x +) - (d e f ^ ^)
a b c x + d e f ^ ^ -
Question 31 |
1267 | |
1164 | |
1264 | |
1169 |
Base or starting address of the array is 1120.
The address of the 49th element = base address of array + number of elements before current element * size of element
= 1120 + 48 * 3 = 1264
Question 32 |
A | |
B | |
C | |
D |

Question 33 |
n nodes | |
log2 n nodes | |
2n-1 | |
2n |

Question 34 |
3230 | |
16230 | |
49152 | |
173458 |
Between * and ^ , operator ‘^’ is highest precedence so it will execute first.
The expression consists of more than one ‘^’ operator is presented then it will follow right to left associativity.
Multiplication operator associativity is left to right.
1 * 2 ^ 3 * 4 ^ 5 * 6 = 1 * (2 ^ 3)* (4 ^ 5) * 6
= 1 * 8 * 1024 * 6
= 49152
Question 35 |
8 2 3 ^ / 2 3 * + 5 1 * –
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are
6,1 | |
5,7 | |
3,2 | |
1,5 |
Rule (1): If the element is a number, Push it into stack.
Rule (2): If the element is an operator, Pop operands from the stack. Evaluate the operator operation and Push the result back into the stack.

Question 36 |
3 | |
4 | |
5 | |
6 |
Hash function = f(key) = key mod 7

Question 37 |
log2n nodes | |
n+1 nodes | |
2n nodes | |
2n+1 nodes |
Note: if two leaves having the same parent are removed from the tree, the number of leaves and non-leaves will decrease by 1 because the parent will be a leaf. That means the difference between them is constant. And for a tree having just one node that difference is 1.
Question 38 |
5 | |
14 | |
24 | |
35 |
So, for 4 distinct nodes, we can have (8C4)/5 = 14 distinct BSTs
Question 39 |
0 | |
3 | |
4 | |
None of the above |
According to question, there is no information regarding children nodes of node “A”. So the degree of A is 0.
Question 40 |
x:=1;
i:=1;
while (x ≤ 500)
begin
x:=2x ;
i:=i+1;
end
What is the value of i at the end of the pseudocode?
4 | |
5 | |
6 | |
7 |
After completion of second iteration x and i values are : x = 4 and i = 3
After completion of third iteration x and i values are : x = 16 and i = 4
After completion of fourth iteration x and i values are : x =256 and i = 5
After completion of fifth iteration x and i values are : x = 65536 and i = 6(Condition is false)
Then the value of “i” is 5
Question 41 |
O(n0.5) | |
O(n) | |
O(log n) | |
O(n log n) |
The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.
The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.
The average depth of a binary search tree is log(n)
Question 42 |
FGBDECA | |
ABFGCDE | |
BFGCDEA | |
AFGBDEC |
→ Pre order properties are root,left and right
→ Based on the given sequence, we will get binary tree is

→ Based upon the inorder traversal, we will get preorder sequence is ABFGCDE.
Question 43 |
0.164 | |
127 | |
8.06 | |
6.08 |
Symbol table length=152,
Number of entries=25,
Occupation density=?
Step-1: To find Occupation density require number of entries and length of symbol table.
Occupation Density = Number of entries/ Length of symbol table
= 25/152
= 0.164
Question 44 |
p = getnode()
info (p) = 10
next (p) = list
list = p
result in which type of operation?
pop operation in stack | |
removal of a node | |
inserting a node | |
modifying an existing node |
info (p) = 10 // Storing the value of 10 into the info field of new node
next (p) = list // adding new node to the existing list.
list=p // the starting address of the list will
point to the new node
Question 45 |
8 | |
15 | |
14 | |
13 |

Question 46 |
1 | |
2 | |
N/2 | |
2N-1 |
Array=2N elements
Elements are used 2-ordered and 3-ordered
Step-1: If array used 2-ordered, if it contains an element which is at most two positions away from its original position in a sorted array.
Sep-2: Maximum number of positions that an element can be from its position if the array were
1-ordered = 1
Question 47 |
2 | |
3 | |
4 | |
5 |
The “current” binding for a given name is the one encountered most recently during execution
Dynamic scoping :
The scope of bindings is determined at run time not at Compile time .
→ For deep binding, the referencing environment is bundled with the subroutine as a closure and passed as an argument. A subroutine closure contains
– A pointer to the subroutine code
– The current set of name-to-object bindings
→ By considering dynamic scoping with deep binding when add is passed into second the environment is x = 1, y = 3 and the x is the global x so it writes 4 into the global x, which is the one picked up by the write_integer.
Question 48 |
0 | |
1 | |
2 | |
3 |


Question 49 |
1200 | |
1408 | |
33 | |
1050 |
In the given question, Array is represented with lower bound and upper bound.
The following ARRAY statement defines an array containing a total of five elements, a lower bound of 72, and an upper bound of 76. It represents the calendar years 1972 through 1976: array years{72:76} first second third fourth fifth.
The following ARRAY statement arranges the variables in an array by decades. The rows range from 6 through 9, and the columns range from 0 through 9.
array X{6:9,0:9} X60-X99.

Question 50 |
q[0] | |
q[1] | |
q[9] | |
q[10] |
The front and rear pointers are initialized to point at q[2] which means third element.
First element will add at q[3] , second element will add at q[4] and so on eight element will add at q[10].
Q[10] is the end of the queue which is connected to q[0]
So ninth element can be added at q[0] pointer
Question 51 |

Q | |
V | |
W | |
X |
The in-order traversal of the above tree is UQXWPVZY
So the fourth smallest element is 4th element of the inorder which is W
Question 52 |
A | |
B | |
C | |
D |

Question 53 |
0 | |
1 | |
11 | |
12 |
661 mod 13 = 11
182 mod 13 = 0
24 mod 13 = 11, already filled, so after linear probing it will get index 12
103 mod 13 = 12, already filled, so after linear probing it will get index 1
Question 54 |
30 | |
60 | |
90 | |
None of the above |
n=4. Here, n is number of nodes.
44-2=16.
Given options are wrong options.
Note: Correct answer is 16
Question 55 |
Values of local variables | |
Return address | |
Heap area | |
Information needed to access non local variables |
Variables allocated on the stack are stored directly to the memory and access to this memory is very fast, and it's allocation is dealt with when the program is compiled
Variables allocated on the heap have their memory allocated at run time and accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory . Element of the heap have no dependencies with each other and can always be accessed randomly at any time
Question 56 |

Delete the first element of the list | |
Interchange the first two elements of the list | |
Delete the last element of the list | |
Add an element at the end of the list |
2. In order to delete first element , change first pointer to the next element.It won’t require length of the linked list.
3. To interchange first two elements also, We need to work with only first two nodes only.Here also no need of length of linked list.
4. To add an element at the last node, we already has one pointer which is pointing to the last node, simple add new node to last node by storing last pointer next address to new node.
5. But in order to delete last node , we need to traverse the entire list , So it requires length of the linked list. By using the last node pointer , we can’t move to previous node in the single linked list.
Question 57 |
Consider the array A = 〈4, 1, 3, 2, 16, 9, 10, 14, 8, 7〉. After building heap from the array A, the depth of the heap and the right child of max-heap are and respectively. (Root is at level 0).
3, 14 | |
3, 10 | |
4, 14 | |
4, 10 |
Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max-heapify operation from the largest index parent node (node having 1 or more children).






The above Heap is the max-heap where each root node have maximum value.
Now depth of the Max-heap is 3 and right child of the Root node is 10.
Question 58 |
A hash function h defined h(key) = key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?
3 | |
4 | |
5 | |
6 |
h(44) = 44 mod 7 ⇒ 2
h(45) = 45 mod 7 ⇒ 3
h(79) = 79 mod 7 ⇒ 2 (collision occurred)
h(79) = (79+1) mod 7 ⇒ 3 (collision occurred)
h(79) = (79+2) mod 7 ⇒ 4
h(55) = 55 mod 7 ⇒ 6
h(91) = 91 mod 7 ⇒ 0
h(18) = 18 mod 7 ⇒ 4 (collision occurred)
h(79) = (18+1) mod 7 ⇒ 5
h(63) = 63 mod 7 ⇒ 0 (collision occurred)
h(63) = (63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations.

Question 59 |
Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ?
Here “__” denotes an empty location in the table.
3, 10, 1, 8, ___ , ___, ___.
| |
1, 3, 8, 10, ___, ___, ___.
| |
1, ___, 3, ___, 8, ___, 10
| |
3, 10, ___, ___, 8, ___, ___. |
h(3) = ((7*3)+3) mod 4 = 0
h(8) = ((7*8)+3) mod 4 = 3
h(10) = ((7*10)+3) mod 4 = 1

Question 60 |
n/2 | |
(2n+1)/3 | |
(n-1)/n | |
(n-1) |
[ Where L is the number of leaf nodes and I is the number of internal nodes]
→ Given data n=3.
L=(3-1)I +1
=2I +1 ------------> 1
→ To find total number of nodes is nothing but sum of leaf nodes and internal nodes
n=L+I ------------> 2
With the help of 1 and 2, we get L =(2n+1)/3/
Question 61 |
Array | |
Tree | |
Stack | |
Queue |
→ Stack to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes.
→ The functions follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls.
→ This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
Question 62 |
10 10 +60 6 / * 8 - is:
192 | |
190 | |
110 | |
92 |


Question 63 |
Preorder and Inorder | |
Postorder and Inorder | |
Postorder and Preorder | |
None of these |
Consider two different trees,
TREE-1
root=a;
root→ left=b;
root→ left→ right=c;
TREE-2
root=a;
root→ right=b;
root→ right→ left=c;
Both the trees are different, but have same pre-order and post-order sequence.
pre-order - a b c
post-order - c b a
Because we cannot separate the left subtree and right subtree using the pre-order or post-order traversal alone
Question 64 |
Two stacks are required | |
One stack is needed | |
Three stacks are required | |
More than three stacks are required |
Converting infix expression into post/prefix expression
Evaluating post/pre-fix expression
Parenthesis matching
With one stack also we can easily evaluate the expression.
Question 65 |
1 | |
2 | |
3 | |
4 |
push(s,x)
1) Enqueue x to q1 (assuming size of q1 is unlimited). pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
→ Implementing queue by using two stack:
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
Question 66 |
4 | |
8 | |
16 | |
32 |
Question 67 |
Circular queue | |
Priority queue | |
Stack | |
Dequeue |
● What makes a deque different is the unrestrictive nature of adding and removing items.New items can be added at either the front or the rear.
● Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
Question 68 |
Queue | |
Stack | |
List | |
None of above |
Question 69 |
Depth First | |
Breadth First | |
Width First | |
Depth Limited |
● Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 70 |
log 2 n nodes | |
n+1 nodes | |
2n nodes | |
2n+1 nodes |
● In a binary tree - a tree where each non-leaf node has exactly two sons - number of leaves is n+1. Total number of nodes is 2n+1.
Full Binary Tree:

In the above tree,non-leaf nodes are 7 so total nodes are 2x7+1=15
Question 71 |
O(logn) | |
O(n) | |
O(nlogn) | |
O(n 2 ) |
Possibility-2: If you inserted one after the other then time complexity will be O(nlogn). For one insertion it will take O(logn) because need to apply maxHeapify. For n elements it will be O(nlogn)
Note: We can also insert all the elements once, there will be no difference on time complexity.
But according GATE solution they given possibility-1.
Question 72 |
O(log 2 n) | |
O(nlog 2 n) | |
O(n) |
Note: If you apply linear search it will take O(logn) and binary search it will take O(loglogn). If you want to insert an element into already created heap is O(logn) because you need to apply maxheapify.
Question 73 |
no pointer | |
1 pointer | |
2 pointer | |
3 pointer |
x → next = n1 → next
n1 → next = x
So, we need to modify two pointers only to insert node into the linked list.
Question 74 |
is far less than one | |
equals one | |
is far greater than one | |
none of these |
Load factor= n / k
where
● n is the number of entries occupied in the hash table.
● k is the number of buckets.
As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used)
The load factor is the number of keys stored in the hash table divided by the capacity. The size should be chosen so that the load factor is less than 1
Question 75 |
6 | |
5 | |
4 | |
3 | |
None of the above |
Question 76 |
In a ternary tree, the number of internal nodes of degree 1,2 and 3 is 4,3 and 3 respectively. The number of leaf nodes in the ternary tree is
11 | |
12 | |
10 | |
9 |
Number of leaf nodes = Sum of degrees of all internal nodes - number of internal nodes +1
= (4*1 + 3*2 + 3*3 ) - 10 + 1
= 19 - 10 + 1
= 10
Formula: nd - n + 1 where n is number of nodes and d is degree of the tree.
Question 77 |
An attribute A of data type varchar(20) has the value ‘xyz’ and attribute B of data type char(20) has the value “Imnop” , then the attribute A has ________ spaces and attribute B has ________ spaces.
20, 20
| |
3, 20 | |
3, 5
| |
20, 5
|
→ varchar is a variable-length data type, the storage size of the varchar value is the actual length of the data entered, not the maximum size for this column.
→ So, A varchar(20) has only 3 spaces because its initialized to 'xyz' and B char(20) has 20 spaces as char data type occupies the storage space equivalent to the maximum size.
Question 78 |
A binary search tree is constructed by inserting the following numbers in order:
60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34
The number of nodes is the left subtree is
7 | |
6 | |
3 | |
5 |

Question 79 |
Consider the singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list ?
O(1) | |
O(lg n)
| |
O(n) | |
O(n lg n)
|
Question 80 |
Consider the following postfix expression with single digit operands :
6 2 3 * / 4 2 * + 6 8 * -
The top two elements of the stack after second * is evaluated, are :
6, 3 | |
8, 1 | |
8, 2 | |
6, 2 |
While traversing the expression if you find an element value then push it on the top of stack this way the top element of the stack will represent the second operand of an operation and the element presents after top element will represent the first operand of the operation.
While traversing the postfix expression if you find an operation symbol then pop 2 elements from the top of the stack and then after performing operation store it’s result on the top of stack.
Step 1:

Step 2:

Step 3:

Step 4:

So Pop top 2 elements from stack and save the result on the top of stack.
2*3=6

Step 5:

Again Repeat step-4.
6/6=1

Step 6:


Step 7:


Step 8:

Do what we did in step-4.
4*2 = 8

Question 81 |
The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as
<42, 35, 40, 22, 25, 26, 30> | |
<42, 35, 40, 22, 25, 30, 26>
| |
<42, 40, 35, 25, 22, 26, 30>
| |
<42, 40, 35, 25, 22, 30, 26> |
The resultant MAX_Heap will look like

<42, 40, 35, 25, 22, 30, 26>
Question 82 |
Consider the following minimax game tree search

What will be the value propagated at the root ?
6 | |
3 | |
5 | |
4 |

Question 83 |
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
Prints all nodes of linked lists | |
Prints all nodes of linked list in reverse order | |
Prints alternate nodes of Linked List | |
Prints alternate nodes in reverse order |
Input : Head of following linked list
1->2->3->4->NULL
Output : Linked list should be changed to,
4->3->2->1->NULL
Algorithm:
1. Initialize three pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr->next
// Now change next of current
// This is where actual reversing happens
curr->next = prev
// Move prev and curr one step forward
prev = curr
curr = next
Question 84 |
void fun(struct node **head_ref)
{
struct node *temp=NULL;
Struct node *current=*head_ref;
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
if(temp!=NULL)
*head_ref=temp → prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <--> 2 <--> 3 <--> 4<--> 5 <--> 6. What should be the modified linked list after the function call?
1<-->2<-->4<-->3<-->6<-->5 | |
5<-->4<-->3<-->2<-->1<-->6 | |
6<-->5<-->4<-->3<-->2<-->1 | |
6<-->5<-->4<-->3<-->1<-->2 |
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
The loop meant for traversing the entire list till to end by changing prev and next pointers of all nodes.
Change prev of the head (or start) and change the head pointer in the end.
Question 85 |
void fun(int n)
{
Stack s;//Say it creates an empty stack S
while(n>0)
{
// This line pushes the value of n%2 to
Stack S;
Push(&S,n%2);
n=n/2l
}
// Run while Stack S is not empty
while(!is Empty(&S)) Printf(%d",pop(&S));//pop an element from S and print it
}
What does the above function do in general order
Prints binary representation of n in reverse order | |
prints binary representation of n | |
Prints the value of Logn | |
Prints the value of Logn in reverse order |
1) Let us take number 'NUM' and we want to check whether it's 0th bit is ON or OFF
bit = 2 ^ 0 (0th bit)
if NUM & bit == 1 means 0th bit is ON else 0th bit is OFF
2) Similarly if we want to check whether 5th bit is ON or OFF
bit = 2 ^ 5 (5th bit)
if NUM & bit == 1 means its 5th bit is ON else 5th bit is OFF.
Let us take unsigned integer (32 bit), which consist of 0-31 bits. To print binary representation of unsigned integer, start from 31th bit, check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”. Now check whether 30th bit is ON or OFF, if it is ON print “1” else print “0”, do this for all bits from 31 to 0, finally we will get binary representation of number. void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i > 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
}
Question 86 |
abc x+def^^- | |
abc xde^f^- | |
ab +c xd -e^f ^ | |
-+ a x bc ^^def |
⟶ left to right
Step 1: abc+

Question 87 |
What rotation to make | |
if all childs nodes are at same level | |
when the last rotation occurred | |
if the tree is unbalanced |
Question 88 |
10,8,7,3,2,1,5 | |
10,8,7,2,3,1,5 | |
10,8,7,1,2,3,5 | |
10,8,7,5,3,2,1 |

10, 8, 7, 3, 2, 1, 5.
Question 89 |
Both operations can be performed in O(1) time |
Question 90 |
O(n) | |
O(m+n) | |
O(n^2) | |
O(mn) |
Question 91 |
nk | |
(n-1)k+1 | |
n(k-1)+1 | |
n(k-1) |
Leaves = total nodes - internal nodes
= nk+1-n
= n(k-1)+1
Question 92 |
Binary search | |
Linear Search | |
Insertion sort | |
Merge Sort |
→ Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
→ Insertion sort & Linear search can use linked list. Note:But Binary search also can implement using linked list but it takes O(n) time complexity.
Question 93 |
An array of 50 numbers | |
An array of 100 numbers | |
An array of 500 numbers | |
A dynamically allocated array of 550 numbers |
→ Then using array of 50 numbers is the best way to store the frequencies.
Question 94 |
!2n / (!n*!(n+1)) | |
C(n,2n) (n+1) | |
!n*C(2n,n) (n+1) | |
C(2n,n)/ !n |
→ Total number of possible Binary Search Trees with n different keys
BST(n)=Cn=(2n)!/(n+1)!*n!
For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ….
So are numbers of Binary Search Trees.
→ Total number of possible Binary Trees with n different keys BT(n)=BST(n)*n!
Question 95 |
5,4,10,8,6,49,31,43,19,17,11 | |
4,5,6,8,10,11,19,17,43,31,49 | |
4,5,8,10,6,17,31,49,43,19,11 | |
5,4,10,8,6,17,31,49,43,19,11 |

Post order: 5,4,10,8,6,17,31,49,43,19,11
Question 96 |
B+ tree | |
Threaded binary tree | |
Heap | |
AVL tree |
Question 97 |
Pass by value | |
Pass by name | |
Pass by reference | |
Pass by pointer |
Pass by reference: An alias or reference to the actual parameter is passed to the method.Passing a pointer to the actual parameter, and indirect through the pointer
Pass by name: re-evaluate the actual parameter on every use. For actual parameters that are simple variables, this is the same as call by reference. For actual parameters that are expressions, the expression is re-evaluated on each access.
There is no parameter passing method with the name “ Pass by pointer”
Question 98 |
A+i*N*S | |
A+(i*N+j)*S | |
A+(i*N+j*M)*S | |
A+(i*M+j*N)*S |
M is number of the rows and N is number of Columns and S is size of the element.
The elements are storing row major order. So the elements are in the following order.
A[1,1],A[1,2],A[1,3] ….. A[1,N]
A[2,1],A[2,2],A[2,3]........A[2,N]
……
….
A[M,1],A[M,2],A[M,3]........A[M,N]
We will get the location of A[i,j] by using formula A+(i*N+j)*S where “i” is the index of the row and “j” index of the column and “N” is number of columns.
Question 99 |
3 | |
4 | |
5 | |
6 |
37%7=2
38%7=3
72%7=2. Here, collision happened because already index 2 is already filled by 37.
According to linear probing, increment index value by 1.
2+1=3 but index 3 also filled with 38 element. So, again increment by 1.
72%7=2( getting index position in hash table 4 )
48%7=6
98%7=0
11%7=4. Here, collision happened because already index 4 is already filled by 72.
According to linear probing, increment index value by 1.
11%7=4 (getting index position in hash table 5 )
56%7=0Here, collision happened because already index 0 is already filled by 98.
According to linear probing, increment index value by 1.
56%7=0 (getting index position in hash table 1 )
Question 100 |
postorder | |
preorder | |
inorder | |
none of these |
Pre order: The root node is visited first, then the left subtree and finally the right subtree.
Post order: First we traverse the left subtree, then the right subtree and finally the root node.
Question 101 |
0.45 | |
0.5 | |
0.3 | |
0.34(approximately) |
So, 1- (100*99*98*97*96*95*94*93*92*91)/100 10 ⇒ 0.37(approximately)
Question 102 |
O(n) | |
O(logn) | |
O(loglogn) | |
O(A) |
Question 103 |
Simulation of recursion | |
Simulation of arbitrary linked list | |
Simulation of limited resources allocation | |
Expression evaluation |
Question 104 |
20 , 20 | |
3 ,20 | |
3, 5 | |
20, 5 |
→ varchar is a variable-length data type, the storage size of the varchar value is the actual length of the data entered, not the maximum size for this column.
→ So, A varchar(20) has only 3 spaces because its initialized to 'xyz' and B char(20) has 20 spaces as char data type occupies the storage space equivalent to the maximum size.
Question 105 |
60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34
The number of nodes is the left subtree is
7 | |
6 | |
3 | |
5 |

Question 106 |
6 2 3 * / 4 2 * + 6 8 * -
The top two elements of the stack after second * is evaluated, are :
6, 3 | |
8, 1 | |
8, 2 | |
6, 2 |
While traversing the expression if you find an element value then push it on the top of stack this way the top element of the stack will represent the second operand of an operation and the element presents after top element will represent the first operand of the operation. While traversing the postfix expression if you find an operation symbol then pop 2 elements from the top of the stack and then after performing operation store it’s result on the top of stack.



Question 107 |
<42, 35, 40, 22, 25, 26, 30> | |
<42, 35, 40, 22, 25, 30, 26> | |
<42, 40, 35, 25, 22, 26, 30> | |
<42, 40, 35, 25, 22, 30, 26> |
The resultant MAX_Heap will look like

< 4 2, 40, 35, 25, 22, 30, 26 >
Question 108 |

What will be the value propagated at the root ?
6 | |
3 | |
5 | |
4 |

Question 109 |
Search tree | |
Heap | |
AVL tree | |
B tree |
Question 110 |
2 k +1 | |
2 k-1 | |
2 k -1 | |
2 k-1 -1 |
For example

The minimum number of nodes 2 2 -1=3
Question 111 |
In adjacency list representation, space is saved for sparse graphs. | |
Deleting a vertex in adjacency list representation is easier than adjacency matrix representation | |
Adding a vertex in adjacency list representation is easier than adjacency matrix representation. | |
All of the option |
● Uses O(n 2 ) memory
● It fast to lookup and check for presence or absence of a specific edge between any two nodes O(1)
● It slow to iterate over all edges
● It slow to add/delete a node is a complex operation O(n 2 )
Adjacency List
● Use memory pending on the number of edges (not number of nodes), Which might save a lot of memory if the adjacency matrix is a sparse
● Finding the presence or absence specific edge between any two nodes Is slightly slower than with the matrix O(k) where k number of neighbors nodes
● It is fast to iterate over all edges,because you can access any node neighbors directly
● It is fast to add/delete a node is easier than the matrix representation
Question 112 |
Stack for BFS and Queue for DFS | |
Queue for BFS and Stack for DFS | |
Stack for BFS and Stack for DFS | |
Queue for BFS and Queue for DFS |
● Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 113 |

i)abeghf
ii)abfehg
iii)abfhge
iv)afghbe
Which are depth first traversals of the above graph?
I,II and IV only | |
I and IV only | |
II,III and IV only | |
I,III and IV only |
● Pick a starting node and push all its adjacent nodes into a stack.
● Pop a node from stack to select the next node to visit and push all its adjacent nodes into a stack.
● Repeat this process until the stack is empty. However, ensure that the nodes that are visited are marked.
● This will prevent you from visiting the same node more than once. If you do not mark the nodes that are visited and you visit the same node more than once, you may end up in an infinite loop.
Question 114 |
2,2,1,1,2 | |
2,2,1,2,2 | |
2,1,2,2,1 | |
2,1,2,2,2
|

Final Pop sequence: 22112
Question 115 |

4 | |
5 | |
6 | |
3 |
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisons = 4+1
= 5
Question 116 |
It cannot be implemented | |
2 stacks | |
4 stacks | |
1 stack |
For this,
int x=element=stack-1,pop();
stack-2.push(element);

Step-2: Once the complete stack-1 gets copied to Stack-2, then we can simply call pop() on s2, it will remove the element-1.
So, A queue can be implemented using 2 stacks.
Question 117 |
Considering 0-address instructions machine, what will be the top of the stack after executing the following sequence of instructions?
PUSH 15, PUSH 4, PUSH 6, MULT, PUSH 30, ADD, ADD
30 | |
69 | |
54 | |
10 |
Step-1: PUSH 15,PUSH 4 and PUSH 6 from bottom to top. Now top of the stack value is 6.
Step-2: Perform MULT operation. 6*4=24. Now present stack values are from bottom is 15 and 24.
Step-3: Next again PUSH 30. Now top of the stack is 30.
Step-4: Perform ADD operation. 30+24=54
Step-5: Now present stack values are from bottom is 15 and 54. Perform ADD operation.
Step-6: 15+54=69
Question 118 |
Which of the following data structures is used in level order traversal of a binary tree?
Skip list | |
Stack | |
Array
| |
Queue
|
Example:
Level order traversal of binary tree.
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.
printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
a) print temp_node->data
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node
Note:
Level order traversal of binary tree is time Complexity is O(n) where n is number of nodes in the binary tree.
Question 119 |
In a full binary tree of height 10, the number of nodes with degree 0,1, and 2 will be ____,____ and ____ respectively.
Note: Consider height of a tree as the number of nodes in the longest path from root to any leaf node
512, 0, 511
| |
512, 1, 510 | |
511, 0, 512
| |
511, 1, 511 |
Full binary tree consists of either 0 or 2 childs . So one child to the node is not possible.
The number of nodes with the degree of 1 is 0.
The nodes with degree 0 are leaf nodes, 2h-1 = 29 = 512.
The nodes with degree 2 are internal nodes 2h-1 - 1 = 511.
Question 120 |
Consider an AVL tree constructed by inserting the elements 18, 10, 5, 3, 27, 7, 35, 43, 32 one by one. Which of the following options give the number of comparisons to search the key value 45 in this AVL tree?
5 | |
4 | |
3 | |
2 |

Question 121 |
2 h | |
2 h-1 -1 | |
2 h+1 -1 | |
2 h+1 |
● The number of leaf nodes l in a perfect binary tree, is l = ( n + 1 )/2 because the number of non-leaf (a.k.a. internal) nodes

● This means that a perfect binary tree with l leaves has n = 2 l − 1 nodes. ● In a balanced full binary tree, h = ⎡ log 2 (l)⎤ + 1 = ⎡ log 2 ((n + 1 )/2)⎤ + 1 = ⎡ log 2 (n + 1 )⎤
● In a perfect full binary tree, l = 2 h thus n = 2 h+1 − 1
● The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is ( n + 1 ) , where only 1 node exists in bottom-most level to the far left.
●The number of internal nodes in a complete binary tree of n nodes is ⎣ n/2⎦ .
Question 122 |
Stack | |
Set | |
List | |
Queue |
Question 123 |
O(n), O(n) | |
O(n), O(1) | |
O(1), O(n) | |
O(1), O(1) |
Question 124 |
12 | |
13 | |
14 | |
15 |

Question 125 |
Is far less than one | |
Equals one | |
Is far greater than one | |
None of the above |
Question 126 |
2 | |
4 | |
3 | |
5 |
→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.
→ So number of probes = ⌈(log2 31)⌉
= ⌈4.954196310386876⌉
⇒5
Question 127 |
11,31,23,50,73,62,41 | |
31,11,23,50,41,62,73 | |
11,31,50,23,73,62,41 | |
11,31,23,50,62,73,41 |
According to pre order we will get below graph based on Inorder is 11,23,31,41,50,62,73.

Question 128 |
*(x+i) is same as *(&x[i]) | |
&x[i] is same as x+i-1 | |
*(x+i) is same as *x[i] | |
*(x+i) is same as *x+i |
⇒* is nothing but Value at address location
⇒&x[i] means address of ith element
⇒*(&x[i]) means Value at “i” location of “ x address”.
We can also write it into *(X+i) = X[i] =*(&x[i])
Question 129 |

Commutative but not associative | |
neither commutative nor associative | |
Both commutative and associative | |
Associative but not commutative |
Question 130 |
Inorder | |
Preorder | |
Postorder | |
None of the above |
(i) Traverse the left most subtree starting at the left external node,
(ii) Visit the root, and
(iii) Traverse the right subtree starting at the left external node.
The Inorder traversal of the above tree will outputs: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Question 131 |
Linked allocation
| |
Indexed allocation
| |
Contiguous allocation | |
None of the options |
Advantages:
Faster access as all blocks are nearby.
Suitable for small sequentially accessed file
Disadvantages:
Poor performance if file grows or shrinks.
Linked Allocation:Each block stores pointer to next block
Advantages:
No fragmentation.
Suitable for large sequentially accessed file
Disadvantages:
Random access is not possible, If one link is lost, cannot access subsequent blocks
Note: In File Allocation Table (FAT) all links are cached in a table for faster access.
Indexed Allocation:A single bock stores indexes of all blocks of a file.
Advantage:
Suitable for large randomly accessed file
Eg: UNIX inode stores the first 12 or so data block pointers and then singly, doubly, and triply indirect pointers.
Question 132 |
2 | |
4 | |
3 | |
6 |
=log263
=6
Question 133 |
2-4 tree | |
B+ tree
| |
B-Tree | |
None of the options
|
The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:
→ a 2-node has one data element, and if internal has two child nodes;
→ a 3-node has two data elements, and if internal has three child nodes;
→ a 4-node has three data elements, and if internal has four child nodes.
Question 134 |
is far less than 1 | |
equals 1 | |
is far greater than 1 | |
none of the options |
Question 135 |
char*str="Raj is a research scholar"; | |
charstr[25]="Raj is a research Scholar"; | |
charstr[40]="Raj is a research Scholar";
| |
char[] str="Raj is a research Scholar"; |
Variable initialization syntax : Datatype varible_name[size]="sring"
(or)
Datatype variable_name[ ]=”string”
Question 136 |
contain address of next node | |
may contain null character
| |
contain address of next pointer | |
both (A) and (B) |
→ The field of each node that contains the address of the next node is usually called the 'next link' or 'next pointer'.
→ The remaining fields are known as the 'data', 'information', 'value', 'cargo', or 'payload' fields. Note: Option C is also correct.
Question 137 |
'-' is left associative and '*' has precedence over '-'
| |
'-' is right associative and '*' has precedence over '-' | |
'-' is right associative and '-' has precedence over '*' | |
'-' is left associative and '-' has precedence over '*' |
Step-1: 5-2-3*5-2 will be 19.
Step-2: if it is treated as (5-(2-3))*(5-2)
Step-3: - has precedence over * and if it associates from the right.
Question 138 |
Struct node* { Int data; node*link; } | |
Struct node { int data; Struct node*link; } | |
Struct node { int data; node link; } | |
Struct node* { int data; struct node*link; } |
Struct tag_name
{
Datatype variable_name;
Struct tag_name *pointer_variable;
};
Question 139 |
O(lgn) | |
O(nlogn) | |
O(n2) | |
O(n) |
→ The worst-case time complexity of a search in a binary search tree is O(n).
Question 140 |
(a) Parenthesis balancing program
(b) Process scheduling operating system
(c) Conversion of infix arithmetic expression to postfix form
(a) and (b) | |
(b) and (c) | |
(a) and (c) | |
(a),(b) and (c) |
Question 141 |

(i) (iii) (ii)
| |
(ii) (i) (iii) | |
(iii) (ii) (i) | |
(ii) (iii) (i) |
→ Scheduling can be implemented using Queue.
→ The inorder traversal of binary search gives sorting order.
Question 142 |
(a) Binary search in an array
(b) Breadth first search
(c) Implementing function calls
(d) Process scheduling
(b) and (d) | |
(b) and (c) | |
(a) and (c) | |
(c) and (d) |
Binary search can be implemented by using recursion. So Stack is suitable for implementing function calls.
Question 143 |
Front=rear=null | |
Front=Rear!=null | |
Front=Rear+1 | |
Front=Rear-1 |
Question 144 |
(i-1)/2 +j | |
((i-1)*i)/2 +j | |
(i*i)/2 +j | |
(i*j-1)/2 |
Question 145 |
5 3 1 2 4 7 8 6 | |
5 3 1 2 6 4 9 7 | |
5 3 2 4 1 6 7 8 | |
5 3 1 2 4 7 6 8 |
Option D:
Let draw binary search tree for the given sequence,

After traversing through this tree we will get same sequence.
Question 146 |
Probably the most widely used data structure | |
A homogeneous structure | |
A random access structure | |
All of these |
● An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.
● Memory is allocated homogeneously and we can access any element by using index value.
Question 147 |

Binary tree | |
Recursive tree | |
Insert sort | |
Unitary tree |
Question 148 |
Average path length | |
Median path length | |
Mode path length | |
Simple deviation path length |
Question 149 |

Heap | |
Bubble | |
Splay | |
Binary |
Question 150 |
Recursive | |
Abstract data type | |
Storage Structure | |
File structure |
Question 151 |
Lower bound | |
Range | |
Upper bound | |
All of these |
Question 152 |
Control array | |
Primary array | |
Secondary array | |
An integer array |
A control array can be created only at design time, and at the very minimum at least one control must belong to it.
Features:
1. Controls that belong to the same control array share the same set of event procedures; this often dramatically reduces the amount of code you have to write to respond to a user's actions.
2. We can dynamically add new elements to a control array at run time; in other words, you can effectively create new controls that didn't exist at design time.
3. Elements of control arrays consume fewer resources than regular controls and tend to produce smaller executables. Besides, Visual Basic forms can host up to 256 different control names, but a control array counts as one against this number. In other words, control arrays let you effectively overcome this limit.
Question 153 |
Tree | |
Stack | |
Linked List | |
Queue |
Algorithm
We have Postfix[ ] Array, Stack, Infix[ ] Array
1. Scan the given expression (Infix ) from Left to Right [ one character at a time].
2. Check Whether the given character is an operator [+, -, *, /, ^ etc] or operand.
3. If it is an operand, then copy it in the Prefix Array.
4. If it is a operator then,
1. Check whether, Stack is empty or not
2. If it is empty then, push the operator in the stack and go to step
3. If Stack is not empty then compare the precedence of Top of stack with operator.
4. If the Top of Stack has higher or equal precedence then pop it and copy in the postfix array.
5. If the operator has higher precedence, push it in the stack and go to step 5.
6. If Stack is not empty go back to step 4(1).
5. Continue solving the expression in usual manner until the expression come to end.
6. Pop the remaining operand in the stack and copy it to postfix array.
Question 154 |
String | |
Queue | |
Stack | |
Linked list |
→ When the called procedure is done, it issues a return instruction, which pops the address from the top of the stack and transfers control there.
→ That’s just the basic processor mechanism that makes it easy to implement procedure calls. The actual details of identifying the parameters, placing them on the stack, executing a call instruction are up to the compiler.
→ In the called function, the compiler is responsible for ensuring any registers that may be clobbered are saved, allocating stack space for local variables, and then restoring the registers and stack prior to a return.
Question 155 |
5 | |
2 | |
3 | |
4 |
Step-2: According to BST, the properties are left child is smaller than his root node and right subtree is greater than his root node.
Step-3: They given characters B,I,N,A,R,Y. And corresponding alphabetical number are B=2,I=9,N=14,A=1,R=18,Y=25.

Question 156 |

-+*/abdef | |
a+bd*-ef/ | |
abdef*/+- | |
a+b*d-e/f |
Inorder→ left,root and right.
a+b*d-c/f
Question 157 |
S | |
P | |
Q | |
R |
Step-2: Then we have to pop 4 elements. So, present having only one element,that is P.
Step-3: 4 elements we have to insert into a Queue. Queue follows FIFO manner.
Step-4: Again we have to delete two elements from queue and inserted into stack.
Step-5: The inserted elements are T and S.
Step-6: Final pop element is S.
Step-7: Stack having only two elements. P and T.
Question 158 |
Which of the following is wrong while inserting a node in the beginning of list?
Obtain a node from available list
| |
Make the next pointer of the current head pointer to new node | |
Make the node pointer of the list pointer to new node
| |
Make the next pointer of the new node pointer to current head of the list
|
• Option B, C and D: It shows actual procedure to insert a node at beginning. So, Option A is wrong
Question 159 |
Row major order | |
Column major | |
Matrix major | |
Simple |
→First element address is 1000 and Second element address is 1002 and so on
→A[2][1] means Second row first element whose address is 1010.
Question 160 |
3,2 | |
0,2 | |
3,0 | |
0,4 |
→The first value is 3 and a[4] value is 0
Question 161 |
A0 + 15s(i-1)+(j-1) | |
A0 + 8s(i-1)+(j-1) | |
A0 + 15s(j-1)+(i-1) | |
A0 + 8s(j-1)+(i-1) |
A[i,j]=Base address+ j*sizeof the array(i-1)+(j-1)
Question 162 |

If nA is the number of elements in stack A and nB is the number of elements in stack B, then overflow occurs when Push Operation is performed on either stack and
nA=nB | |
nA=nB=n | |
nA+nB=n | |
nA+nB>=n |
→The sum of the nA and nB is equal to the number of elements there is no possibility of inserting element into stack.
Question 163 |
abc*+deh/*- | |
ab+c*de/h*- | |
(a b c*)+(de/h*-) | |
abc*+de/h*- |
=a+[bc*]-d/e*h // Select highest priority operators and convert into postfix form,If same priority then go for associativity
=a+[bc*]-[de/]*h
=a+[bc*]-[de/h*]
=[abc*+]-[de/h*]
=abc*+de/h*-
Question 164 |
a) Implementation breadth first search
b) Implementation depth first search
c) Process scheduling
Which of the following is the correct option?
a and b | |
a and c | |
b and c | |
a,b and c |
→Queue is also used for Breadth first traversal also
Question 165 |
2h-1 | |
2h+1 | |
2h+1-1 | |
2h+1+1 |
→The height of the binary tree is the longest path from root node to any leaf node in the tree
Question 166 |
(n-1)x+1 | |
(n-1)x-1 | |
nx+1 | |
nx-1 |
Then n value is 2 and internal node is 1 then the number of leaves are (2-1)1+1=2 leaves.
Question 167 |
Always appends list ‘m’ at the end of list ‘n’ | |
Always appends list ‘n’ at the end of list ‘m’ | |
Append list ‘m’ at the end of list ‘n’ with possibility of error | |
Appends list ‘n’ at the end of list ‘m’ with possibility of error |
→Non-availability of the any one of the linked list leads to possibility of error.
Question 168 |
2k-1 | |
2*(k-1) | |
2k+1 | |
2((k+1) |
According to the handshaking lemma , the sum of the degree is 2* number of edges So the option B is suitable one.
Question 169 |
Insertion – 0(1), Deletion – 0(1), Maximum – 0(1), Minimum – 0(l) | |
Insertion – 0(1), Deletion – 0(1), Maximum – 0(n), Minimum – 0(n) | |
Insertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1) | |
Insertion – 0(n), Deletion – 0(n), Maximum – 0(n), Minimum – 0(n) |
→ Deletion will take O(n). Let, 1,2,3,4,5. Suppose we want to delete last element in the array, It will traverse end of the array. So, it takes worst case O(n) and best case O(1). But we always consider worst case time complexity.
→ Maximum will take O(1) because we know location of maximum element. So it requires only constant amount.
→ Minimum will take O(1) because we know location of maximum element. So it requires only constant amount.
Question 170 |
A | |
B | |
F | |
G |

Step-2: Stack is pooped five elements then stack is look like

Step-3: Popped five elements are inserted into a queue then queue is look like

Step-4: Two elements are deleted from the queue

Step-5: deleted queue elements are pushed back onto the stack

Top of the stack is B.
Question 171 |

A | |
B | |
C | |
D |
Option B is satisfied max heap property.
Option C is violated max heap property because 7 is greater than his root.
Option D is violated max heap property because 9,10,8,7 elements are greater than his root.
Question 172 |
1 | |
1/n | |
1/m | |
n/m |
Question 173 |
(A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
(B) Breadth-first search cannot be used to find connected components of a graph.
(C) Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely.
(D) Depth-first-search can be used to find the connected components of a graph.
A | |
B | |
C | |
D |
→ A connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
1. Kosaraju’s algorithm for strongly connected components.
2. Tarjan’s Algorithm to find Strongly Connected Components Time complexity for both algorithms are O(V+E).
Question 174 |
726 | |
796 | |
506 | |
616 |
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8. From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012=2*E
⇒ E=506
Question 175 |
S1: A queue can be implemented using two stacks.
S2: A stack can be implemented using two queues.
Which of the following is correct?
S 1 is correct and S 2 is not correct. | |
S 1 is not correct and S 2 is correct. | |
Both S 1 and S 2 are correct. | |
Both S 1 and S 2 are incorrect. |
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
→ A stack can be implemented using two queues
Question 176 |

If we remove the root node, which of the node from the left subtree will be the new root?
11 | |
12 | |
13 | |
16 |
After removing root element, binary search tree is looks like

Question 177 |
Underflow occurs | |
Stack operations are performed smoothly | |
Overflow occurs | |
None of the above |

Question 178 |
(n/2) -1 | |
(n/2) +1 | |
(n–1) / 2 | |
(n+1) / 2 |
→ The maximum height of the tree will be (n–1) / 2. It is standard property of full binary tree.
Question 179 |
Implementation of recursion | |
Evaluation of a postfix expression | |
Job scheduling | |
Reverse a string |
1. Implementation of recursion
2. Evaluation of a postfix expression
3. Expression evaluation and syntax parsing
4. Backtracking
5. Compile time memory management
6. Reverse a string
Question 180 |
15 | |
14 | |
13 | |
12 |
Step-1: Total number of letters/operands with duplication is 5.
Step-3: To find total number of ways, we have catalan formula.
Here, n=5
Catalan number = (2n)! / (n! * (n+1)!)
= (2*5)! / (5! * (5+1)!)
= 10! / (5! * 6!)
= 14
Note: We used catalan formula because they given in fully parenthesized to yield an infix expression.
Question 181 |
P + 1 | |
P – 1 | |
P – 2 | |
P + 2 |
2. V(G),Flow graph is defined as V(G)=E-N+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G.
Question 182 |
&A[0][0][0] + w(y* z* q + z* p + r) | |
&A[0][0][0] + w(y* z* p + z*q + r) | |
&A[0][0][0] + w(x* y* p + z* q+ r) | |
&A[0][0][0] + w(x* y* q + z* p + r) |
Question 183 |
h (k, i) = (h 1 (k) + h 2 (k) + i) mod m | |
h (k, i) = (h 1 (k) + h 2 (k) - i) mod m | |
h (k, i) = (h 1 (k) + i h 2 (k)) mod m | |
h (k, i) = (h 1 (k) - i h 2 (k)) mod m |
h 1 → hash function
h 2 → Step function
First try h(k,0) = h 1 (k), if it is occupied, try h(k,1) etc..,
Advantage: less clusters, uses Θ(m*m) permutations of index addressing sequences.
Question 184 |
θ(log n h*t) | |
θ(log t n*h) | |
θ(log h n) | |
θ(log t n) |
Note: B-Tree search operation best,average and worst case will take θ(logn).
Question 185 |

2 3 4 6 7 13 15 17 18 18 20 | |
20 18 18 17 15 13 7 6 4 3 2 | |
15 13 20 4 7 1718 2 3 6 18 | |
2 4 3 13 7 6 15 17 20 18 18 |

Question 186 |
(a) Depth first search is used to traverse a rooted tree.
(b) Preorder, Postorder and Inorder are used to list the vertices of an ordered rooted tree.
(c) Huffman’s algorithm is used to find an optimal binary tree with given weights.
(d) Topological sorting provides a labelling such that the parents have larger labels than their children.
Which of the above statements are true?
(a) and (b) | |
(c) and (d) | |
(a), (b) and (c) | |
(a), (b), (c) and (d) |
→ Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
→ The optimal binary tree, which has minimum weighted path length when the characters of the alphabet are stored at its n terminal nodes.An optimal binary tree generates what is called a Huffman code
→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.
A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.
Question 187 |
dbefacg | |
debfagc | |
dbefcga | |
debfgca |
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g

Pre order: a b d e c f g
Post order: d e b f g c a
Question 188 |
Breadth First Search | |
Depth First Search | |
Root Search | |
Deep Search |
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 189 |
1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2, ?
1 | |
2 | |
4 | |
8 |




Question 190 |
2 | |
3 | |
9 | |
97 |
-- Hash(y)=X mod 100
-- Key=4594
-- First 3 locations are already occupied.
-- Next cell=?
Step-1: Quadratic Probing function is h(k,i) = (h'(k) +c 1 i+c 2 i 2 )mod m 0≤ i ≤ m-1
where c1 and c2 constants ≠0
Step-2: First pass: 4594 % 100
= 94
Sep-3: Second pass: (4594 + 1 2 ) % 100
= (94 + 1) % 100
= 95
Step-3: Third pass: (4594 + 2 2 ) % 100
= (94 + 4) %100
= 98
Step-4: Fourth pass: (4594 + 1 2 ) % 100
= (94 + 9) %100
= 103 % 100
= 3
Question 191 |
Is a bi-directional graph | |
Is directed graph | |
Is graph in which number associated with arc | |
Eliminates table method |
→ A weighted graph is therefore a special type of labeled graph in which the labels are numbers.
Question 192 |
Advance | |
Backup | |
First | |
Retrieve |
Question 193 |
Hash addressing | |
Chaining | |
Both (A) and (B) | |
Indexing |
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 194 |
Binary search tree | |
AVL - tree | |
Threaded binary tree | |
Complete tree |
1. Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right).
2. Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right).
Question 195 |
3 | |
4 | |
5 | |
6 |
Hash function = f(key) = key mod 7

Question 196 |

ABCD | |
BACD | |
BADC | |
ABDC |
1. Using DFS method
2. Using indegree elimination method
The simplest method is indegree elimination method.
Indegrees:
A →0
B →1
D →2
C → 1 (Final)
We can assume that indegree value of A is ‘0’. So, it is starting point.
Step-1: Remove ‘A’ from graph, then indegrees are
B →0
D →1
C →1
Sequence:

Step-2: Remove ‘B’ from graph, then indegrees are
D →0
C →1
Sequence:

Step-3: Remove ‘C’ from graph then indegrees are
C →0
Sequence:

Question 197 |
2 deletions, 3 additions | |
3 deletions, 2 additions | |
3 deletions, 4 additions | |
3 deletions, 3 additions |

Step-1: Delete ‘a’ from queue. The deletion operation performs First In First Out.We will perform the deletion at front end
After deleting queue will become

Step-3: Delete ‘b’ from queue. The deletion operation performs First In First Out.
After deleting queue will become

Step-3: Delete ‘c’ from queue. The deletion operation performs First In First Out.
After deleting queue will become

Step-4: Insert the element “c” into the queue, We will perform the insertion at rear end
The elements of queue after inserting the element ”c” are

Step-5: Insert the element “b” into the queue,then the elements of queue after inserting the element ”b” are

step-6: Insert the element “a” into the queue,then the elements of queue after inserting the element ”a” are

→ Step-1,step-2 and step-3 are deletion operations and step-4,step-5 and step-6 are deletions operations.
→ So total 3 deletions and 3 insertions are required to get required configuration.
Question 198 |
post – order | |
in - order | |
pre - order | |
linear - order |
Example:

In this traversal method, the left subtree is visited first, then the root and later the right subtree. We should always remember that every node may represent a subtree itself.
Question 199 |
Hash addressing | |
Chaining | |
Indexing | |
None of these |
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 200 |
O (log 2 n) | |
O (n) | |
O (n log 2 n) | |
O (1) |

Question 201 |
Every tree is a bipartite graph | |
A tree contains a cycle | |
A tree with n nodes contains n-1 edges | |
A tree is a connected graph |
Note: Minimum 1 edge and maximum n-1 edges.
Question 202 |

1 | |
3 | |
7 | |
8 |

a, c, d are going to unbalance.
Question 203 |
(A-(B+C))*D | |
((A-B)+C)*D | |
((A+B)-C)*D | |
(A+(B-C))*D |

Question 204 |
Quick sort | |
Bubble sort | |
Merge sort | |
Selection sort |
Bubble sort will give best complexity, when the array is very sorted. Here the number interchanges are very less.
Merge sort will will gives best time complexity but not like bubble in this case. Here the number interchanges are more.
Selection sort will always gives worst performance, whether it is sorted order or not.
Question 205 |
Divide and conquer technique | |
Greedy algorithm | |
Back tracking | |
Dynamic Programming |
Procedure:
1. Divide: select lower or upper half
2. Conquer: search selected half
3. Combine: None
Recurrence relation : T(n)=T(n/2)+Θ(1)
Using masters theorem,
a=1, b=2, k=0,p=0
T(n)=Θ(logn)
Question 206 |
O (log 2 n) | |
O (n) | |
O (n log 2 n) | |
O (1) |

Worst case in linked list:

Question 207 |
defbc/++* | |
def+/bc+* | |
def+/bc *+ | |
None of these |

Postfix expression: d ef + / bc * +
Question 208 |
Array | |
Linked lists | |
Stacks | |
Tables |
→ Elements are accessed using an integer index to specify which element is required. Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixed-length or resizable.
Note: Arrays are directly stored in a memory location. Linked list, Stacks and table(using array) are used logical memory rather than physical memory.
Question 209 |

1 | |
3 | |
7 | |
8 |

a, c, d are going to unbalance.
Question 210 |
Depth first order | |
Breadth first order | |
Topological order | |
Linear order |
Question 211 |
Every tree is a bipartite graph | |
A tree contains a cycle | |
A tree with n nodes contains (n-1) edges | |
A tree is connected graph |
Note: Minimum 1 edge and maximum n-1 edges.
Question 212 |
(A-(B+C))*D | |
((A-B)+C)*D | |
((A+B)-C)*D | |
(A+(B-C)*D) |

Question 213 |
Level wise printing of tree | |
Implementation of priority queues | |
Function call implementation | |
Depth first search in a graph |
Applications:
1.Bandwidth management
2.Discrete event simulation
3.Dijkstra's algorithm
4.Huffman coding
5.Best-first search algorithms
6.ROAM triangulation algorithm
7.Prim's algorithm for minimum spanning tree
Question 214 |
4 PUSH and 3 POP instructions | |
5 PUSH and 4 POP instructions | |
6 PUSH and 2 POP instructions | |
5 PUSH and 3 POP instructions |
after converting postfix notation the notations are ab* cde /* +

Total 5 PUSH and 4 POP operations performed.
Question 215 |
ABD^ + EF – / G+ | |
ABD + ^EF – / G+ | |
ABD + ^EF / – G+ | |
ABD^ + EF / – G+ |
→ Actual tree structure is

Question 216 |
n nodes | |
log 2 n nodes | |
2n –1 nodes | |
2 n nodes |

There are 4 leaf nodes in the above tree.
So, total number of nodes are 2*4-1
=8-1
=7
Question 217 |
2d – 1 | |
2d + 1 – 1 | |
d + 1 | |
d |
Properties:
→The number of nodes at depth d in a perfect binary tree = 2d
→A perfect binary tree of height h has 2h+1 -1 nodes
→Number of leaf nodes in a perfect binary tree of height h = 2h
→Number of internal nodes in a perfect binary tree of height h = 2h -1
→The minimum number of nodes in a binary tree of height h = h+1
→The maximum number of nodes in a binary tree of height h = 2h+1 -1
Question 218 |
Queue | |
Linked list | |
Doubly linked list | |
Binary tree |

Question 219 |
In-order : j e n k o p b f a c l g m d h I
Post-order : j n o p k e f b c l m g h i d a
The Pre-order traversal of the tree shall be
a b f e j k n o p c d g l m h i | |
a b c d e f j k n o p g l m h i | |
a b e j k n o p f c d g l m h i | |
j e n o p k f b c l m g h i d a | |
None of the above |

Step-2:

Step-3: Final tree is

Step-4: Preorder traversal is Root,left and right
preorder= a b e j k n p o f d g l c m i h
Note: Given options are wrong. Excluded for evaluation.
Question 220 |
Binary Search | |
Polynomial Manipulation | |
Insertion | |
Radix Sort |
Note: We can also implement binary search using linked list but it will give time complexity is O(n) instead of O(logn).
Question 221 |
Search and Insert Operations | |
Search and Delete Operations | |
Insert and Delete Operations | |
Search, Insert and Delete Operations |

Question 222 |
Binary search tree | |
AVL tree | |
Threaded Binary Tree | |
Complete Binary Tree |
→ ALV tree
Question 223 |
1 | |
2 | |
3 | |
4 |

Question 224 |

Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree.
d & h | |
c & k | |
g, b, c, h, i, m | |
c & h |

Eccentricity of a vertex u, is
E(u) = maxu∈v(G) d(u, v)
i.e., the maximum distance of a node to other nodes is the eccentricity of that node

Radius: The minimum eccentricity from all the vertices is considered as the radius of the Graph G denoted by r(G).
Here radius of the graph, r(G)=3
Center:- If the eccentricity of a graph is equal to its radius, then it is known as the central point of the graph.
And in above graph vertex "h" and " c" have eccentricity equal to the radius of the graph. So vertex h and c are the center of graph.
Hence correct answer is option (D).
Question 225 |
4 | |
3 | |
2 | |
1 |

Question 226 |
3, 14 | |
3, 10 | |
4, 14 | |
4, 10 |
Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max- heapify operation from the largest index parent node(node having 1 or more children).



The above Heap is the max-heap where each root node have maximum value. Now depth of the Max-heap is 3 and right child of the Root node is 10.
Question 227 |
3 | |
4 | |
5 | |
6 |
h(44)=44 mod 7 ⇒ 2
h(45)=45 mod 7 ⇒ 3
h(79)=79 mod 7 ⇒ 2 (collision occurred)
h(79)=(79+1) mod 7 ⇒ 3 (collision occurred)
h(79)=(79+2) mod 7 ⇒ 4
h(55)=55 mod 7 ⇒ 6
h(91)=91 mod 7 ⇒ 0
h(18)=18 mod 7 ⇒ 4 (collision occurred)
h(79)=(18+1) mod 7 ⇒ 5
h(63)=63 mod 7 ⇒ 0 (collision occurred)
h(63)=(63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations

Question 228 |
cannot have more than 37 nodes | |
has exactly 37 nodes | |
has exactly 35 nodes | |
cannot have more than 35 nodes |
Where, L= Number of leaf nodes
n= N-ary tree
I = Number of intermediate nodes
Now, 19 = I(2-1)+1
19 = 2I-I+1
19 = I+1
I = 18
Total Number of nodes in a tree = Number of Intermediate nodes+Number of Leaf nodes
Total Number of nodes in a tree = 19+18
Total Number of nodes in a tree = 37
Question 229 |
30 | |
33 | |
45 | |
None of the above |
Where, L= Number of leaf nodes
n= N-ary tree
I = Number of intermediate nodes
Now, L =8(5-1)+1
L =8(4)+1
L =33
Total Number of nodes in a tree = Number of Intermediate nodes+Number of Leaf nodes
Total Number of nodes in a tree = 8+33
Total Number of nodes in a tree = 41
Question 230 |
3, 10, 1, 8,___ ,___,___. | |
1, 3, 8, 10,___,___,___. | |
1,___,3,___, 8,___,10 | |
3,10,___,___, 8,___,___. |
h(3)= ((7*3)+3) mod 4 = 0
h(8)= ((7*8)+3) mod 4 = 3
h(10)= ((7*10)+3) mod 4 = 1

Question 231 |
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5)
–3/8 | |
–8/3 | |
24 | |
–24 |

Question 232 |
Neither of the pointers change | |
Only front pointer changes | |
Only rear pointer changes | |
Both of the pointers changes |

Observe 1, 2, 3 whenever we are inserting an element into a queue (singly linked list) we are updating Rear pointer.
Question 233 |
stack | |
tree | |
queue | |
linked list |

Question 234 |
ABFCDE | |
ADBFEC | |
ABDECF | |
None of the above |

Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 235 |
All items in the left subtree are less than root | |
All items in the right subtree are greater than or equal to the root | |
Each subtree is itself a binary search tree | |
All of the above |
2. All items in the right subtree are greater than or equal to the root
3. Each subtree is itself a binary search tree
Question 236 |
Strings | |
Lists | |
Queues | |
All of the above |
Examples:
1. Array
2. Linked List
3. Stacks
4. Queues
Question 237 |
Dequeue | |
Priority | |
Tree | |
All of the above |

Priority Queue is like a regular queue or stack data structure, but here each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Tree: A tree is a data structure containing a collection of nodes. Here a node can have any number of children. A node with no child is called as leaf node and a node with 1 or more child is called parent node. Each parent node have a pointer to its children.

Question 238 |
Strings | |
Lists | |
Stacks | |
None of the above |
Examples:
1. Array
2. Linked List
3. Stacks
4. Queues
Question 239 |
Factorial | |
Fibonacci numbers | |
Tower of Hanoi | |
Tree traversal |
Condition: fibonacci(n-1) + fibonacci(n-2)
Recurrence relation is: T(n)=2T(n-1)+C
Time Complexity: O(2n)
→ Factorial number using recursion is
Condition: fact(n-1)*n
Recurrence relation is: T(n)=T(n+1)+1
Time Complexity: O(n)
→ Tower of Hanoi using recursion is
Step-1: Hanoi(disk - 1, source, aux, dest)
Step-2: move disk from source to dest
Step-3: Hanoi(disk - 1, aux, dest, source)
Recurrence relation is: T(n)=2T(n-1)+C
Time Complexity: O(2n)
→ Tree traversals like Preorder,Postorder and Inorder using recursion only
Note: Recursion is best in the case of Tower of Hanoi,Factorial number and Tree traversals but it is not give good performance to fibonacci numbers.
Question 240 |
ABFCDE | |
ADBFEC | |
ABDECF | |
ABDCEF |

Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 241 |
20 + 21 + ….. 2h | |
20 + 21 + ….. 2h – 1 | |
20 + 21 + ….. 2h + 1 | |
21 + ….. 2h + 1 |
Suppose, in level-3, it have 23=8 nodes.
Question 242 |
256 | |
255 | |
248 | |
None of these |
-- nodes=8
-- Total number of trees=?
Possibility-1: To find total number of trees using nn-2.
= 88-2
= 262144 trees are possible.
Possibility-2: According to given problem, they are using binary tree based on below formula
= 2n -n
= 28 -8
= 248
Note: They are not given proper input.
Question 243 |
In order : E I C F B G D J H K
Preorder : B C E I F D G H J K
The post order traversal of the above binary tree is
I E F C G J K H D B | |
I E F C J G K H D B | |
I E F C G K J H D B | |
I E F C G J K D B H |

Question 244 |
46 | |
47 | |
41 | |
43 |
-- size m=10000
-- hash function h(k) = ⌊m(kA mod 1)'⌋
-- A=(√5 – 1)/2
-- key k=123456 location =?
Step-1: Find out h(123456) = ⌊(10000 * (123456 * (√5 − 1) / 2) mod 1)⌋
= ⌊(10000 * (76300.004115 mod 1)⌋
= ⌊(10000 * (.004115))⌋
= ⌊41.15⌋
= 41
Question 245 |
θ(n) and θ(1) respectively | |
θ(n) and θ(n) respectively | |
θ(1) and θ(1) respectively | |
None of the above |

Question 246 |
At most (1/α) ln ((1–α)/α) | |
At most (1/α) ln (1/(1–α)) | |
At least (1/α) ln (1/(1– α)) | |
At least (1/α) ln (α/(1– α)) |
→ Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.
→ Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.
Question 247 |
O(log n) | |
O(n) | |
O(n logn) | |
O(n2) |
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heap-size[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 Max-Heapify(A, i)
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.
→ Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.
Question 248 |
8 3 4 + – 3 8 2 / + * 2 $ 3 + is
17 | |
131 | |
64 | |
52 |

Question 249 |
S1 : It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2 : The elements of a priority queue may be complex structures that are ordered on one or several fields.
Which of the following is correct ?
Both S1 and S2 are incorrect. | |
S1 is correct and S2 is incorrect. | |
S1 is incorrect and S2 is correct. | |
Both S1 and S2 are correct |
S2: TRUE: The elements of a priority queue may be complex structures that are ordered on one or several fields.
Question 250 |
54 | |
27 | |
26 | |
None of the above |
Question 251 |
O(1) | |
O(lgn) | |
O(n) | |
O(nlgn) |
Build-Max-Heap(A)
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heap-size[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 Max-Heapify(A, i)
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.
→ Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.
Question 252 |
Secondary clustering | |
Primary clustering | |
Both (A) and (B) | |
None of these |
Example: Linear probing
→ Secondary clustering is less severe, two records do only have the same collision chain if their initial position is the same.
Example: Quadratic probing
Question 253 |
90, 40, 65, 50, 88 | |
90, 110, 80, 85, 88 | |
190, 60, 90, 85, 88 | |
65, 140, 80, 70, 88 |
1. Left subtree is smaller than his root node
2. Right subtree is greater than or equal to his root
Based on above rules, the search operation will perform


Note: The sequence of searching should be continuous.
Question 254 |
ABC | |
CBA | |
BAC | |
CAB |

Option-A: According to constraint,
Push(A) then Pop(A)
Push(B) then Pop(B)
Push(C) then Pop(C)
Then the possible pop sequence is ABC. So, it is TRUE
Option-B: According to given constraint, Push(A),Push(B) and Push(C) then Pop(C),
Pop(B) and Pop(A). The possible Pop sequence is CBA. So, it is TRUE
Option-C: According to given constraint, Push(A) and Push(B) then Pop(B) and Pop(A)
then push(C) and Pop(C). The possible Pop sequence is BAC. So, it is TRUE
Option-D: This is not possible.
Question 255 |
Heap | |
Circular array | |
Linked list | |
Binary tree |
→ In a priority queue, an element with high priority is served before an element with low priority.
→ In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.
→ While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map".
→ just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
Question 256 |
About log2n | |
About 2 log2n | |
About n log2n | |
About 2n |
level-1: 1 and 2
level-2: 3 and 6.
[Note: Assume that root starts from level-0]

The height of the binary tree is O(log2n). As per the given constraint, we have to calculate individually of left farthest node and right farthest node height.
=log2n*log2n
=2*log2n or (log2n)2
Question 257 |
100 | |
200 | |
10000 | |
There is no upper limit |
1. They given chained hash. It is like linked list.
2. Maximum number of entries that can be placed in the table.
In chained hash, we adding new element when collisions are happened.
Question 258 |
LIFO | |
LILO | |
FILO | |
FIFO |
Question 259 |
2k-1
| |
2k-1 | |
2k | |
2k+1 |
→ A Binary Tree is full if every node has 0 or 2 children.
→ In a Full Binary, number of leaf nodes is number of internal nodes plus 1
L = I + 1
Where,
L = Number of leaf nodes,
I = Number of internal nodes.
Question 260 |
from leaf to root are non–increasing | |
from leaf to root are non–decreasing | |
from root to leaf are non–decreasing | |
from root to leaf are non–increasing |
Question 261 |
First in first out-order | |
Last in first out-order | |
Parallel fashion | |
Load balancing |
Question 262 |
It is an odd number. | |
It is an even number. | |
It cannot be equal to the number of leaves. | |
It is always greater than twice the number of leaves. |
Ex: n=5
= (2*5)-1
= 9
Question 263 |
An array | |
A stack | |
A queue | |
A linked list |
Question 264 |
An algorithm to search for an element in a singly linked list requires 0(n) operations in the worst case. | |
An algorithm for deleting the first element in a singly linked list requires 0(n) operations in the worst case. | |
An algorithm for finding the maximum value in a circular linked list requires 0(n) operations. | |
An algorithm for deleting the middle node of a circular linked list requires 0(n) operations. |
Question 265 |
3 | |
4 | |
5 | |
6 |
Hash function = f(key) = key mod 7

Question 266 |
maximum | |
minimum | |
sum | |
product | |
None of the above |
In Max heap→ The root element is greater than of his all childs.
In Min heap→ Te root element is smaller than of his all childs.
Question 267 |
Circular Queue | |
Linear Queue | |
Stack | |
Deque |
Question 268 |
A tree is a connected acyclic graph. | |
A tree is a connected graph with n-1 edges where ‘n’ is the number of vertices in the graph. | |
A tree is an acyclic graph with n-1 edges where ‘n’ is the number of vertices in the graph. | |
A tree is a graph with no cycles. |
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas "A tree is a graph with no cycles." is not always correct as it can be bipartite.
Hence D does not define a tree.
Question 269 |
Linked list | |
Stack | |
Array | |
Tree |

Question 270 |
100,50,75, 60, 98
| |
100, 120, 90, 95, 98 | |
200,70,100, 95, 98 | |
75, 150, 90, 80, 98 |
1. Left subtree is smaller than his root node
2. Right subtree is greater than or equal to his root
Based on above rules, the search operation will perform


Question 271 |

for (p=list; p !=NULL; p=p →next);
p=q;
| |
for (p=list; p !=NULL; p=p →next);
p →next=q;
| |
for (p=list; p →next!=NULL; p=p→next);
p=q;
| |
for (p=list; p →next !=NULL; p=p →next);
p →next=q;
|
→ To the traverse the list, we will take one pointer.
→ We will traverse the list till the end by moving the pointer to next node.
→ The pointer will point to the last node and from there the pointer next address will point to the new node.
Option D will provide the above steps.
Q
Question 272 |
3i | |
3i | |
3 | |
3i + 1 |
Given condition is every node has at least three children.
the root node is present at level 0, here only one is present(30)
at level 1, three nodes are present based upon the condition( 31 nodes)
at level 2, nine nodes will be present (32 nodes ) [Each node has at least three children]
and so on the at level "i", 3i nodes will be present.
Question 273 |
Arrays
| |
Stacks | |
Queues | |
Linked lists |
→ Recursion is one the application of stack. It supports many applications.
Applications:
1. Expression Evaluation
2. Expression Conversion
3. Syntax Parsing
4. Backtracking
5. Parenthesis Checking
6. String Reversal
Question 274 |
O(log n) | |
O(n) | |
Ω(n log n) | |
Ω (n2) |

Question 275 |

A B C D E F | |
A B D E F C | |
A C E B D F | |
None of the above |
Option-A: It is ruled out because we can’t move after C to D. It is violating DFS property.
Option-B: It is following actual DFS structure.

Option-C: It is ruled out because after visiting E we can’t visit B again. It is violating DFS properties.
Question 276 |
1024 | |
210 - 1 | |
1000 | |
None of the above |
→ To find maximum number of nodes in a binary tree of depth using formula is
= 2h+1 -1
= 211 -1
= 2048-1
= 2047

Question 277 |
Depth first order | |
Breadth first order | |
Topological order | |
Linear order |
→ A depth-first order is defined to be the reverse of the order in which we last visit the nodes of the control graph when we create the Depth first spanning tree(DFST).
Question 278 |
defbc/+ + | |
def+/bc+* | |
def+/bc*+ | |
None of these |

Question 279 |
Level wise printing of tree. | |
Implementation of priority queues. | |
Function call implementation | |
Depth first search in a graph |
1. CPU scheduling
2. Disk Scheduling
3. synchronization(IO Buffers, pipes, file IO, etc.)
4. Breadth First search
5. Implementation of priority queues.
Question 280 |
Indexed addressing mode | |
Base Register addressing mode | |
Relative address mode | |
Displacement mode |
The address of the operand is obtained by adding to the contents of the general register (called index register) a constant value. The number of the index register and the constant value are included in the instruction code.
→ Index Mode is used to access an array whose elements are in successive memory locations (or) contiguous memory locations.
Question 281 |
e = i+n | |
e = i+2n | |
e = 2i+n | |
e = 2n+i |
→ The root has path length zero and the maximum path length in a tree is called the tree's height.
→ The sum of the path lengths of a tree's internal nodes is called the internal path length and the sum of the path lengths of a tree's external nodes is called the external path length.
External Path Length:

The sum over all external (square) nodes of the lengths of the paths from the root of an extended binary tree to each node. For example, in the tree above, the external path length is 25 (Knuth 1997, pp. 399-400). The internal and external path lengths are related by
E = I + 2n,
where n is the number of internal nodes.
Question 282 |
h(m) = k, if m = 0
= 1, if m = 1
= 2 h(m – 1) + 4h(m – 2), if m ≥ 2
If the value of h(4) is 88 then the value of k is :
0 | |
1 | |
2 | |
-1 |

Each iteration:
h(2) = 2h(1) + 4h(0) = 2 + 4k
h(3) = 2h(2) + 4h(1) = 4 + 8k + 4 = 8 + 8k
h(4) = 2h(3) + 4h(2) = 16 + 16k + 8 +16k = 32k + 24 = 88 (if k=2)
Question 283 |
6 | |
42 | |
132 | |
256 |
Here, n=6
= (2*6)! / (6! * (6+1)!)
= (12)! / (6! * (7)!)
= 479001600 / (720*5040)
= 132
Question 284 |
[26, 13, 17, 14, 11, 9, 15] | |
[26, 15, 14, 17, 11, 9, 13] | |
[26, 15, 17, 14, 11, 9, 13] | |
[26, 15, 13, 14, 11, 9, 17] |


Question 285 |
925, 221, 912, 245, 899, 259, 363, 364 | |
3, 400, 388, 220, 267, 383, 382, 279, 364 | |
926, 203, 912, 241, 913, 246, 364 | |
3, 253, 402, 399, 331, 345, 398, 364 |



