Data Structures | Subject Wise Solved Questions

Application of Breadth First Search

• Shortest Path and Minimum Spanning Tree for unweighted graph
• Peer to Peer Networks
• Finding the bipartite graph
• Finding the diameter of the graph
• Crawlers in Search Engines
• Social Networking Websites
• GPS Navigation systems
• Broadcasting in Network
• In Garbage Collection
• Cycle detection in undirected graph
• Ford–Fulkerson algorithm
• To test if a graph is Bipartite
• Path Finding
• Finding all nodes within one connected component

Just before deleting we need to link
X → Bwd → Fwd = X → Fwd
and  X → Fwd → Bwd = X → Bwd

None of the option are matching
InOreder  : Left, Root, Right
PreOrder  : Root, Left, Right
PostOrder :Left, Right, Root

Tree1
PreOrder: ABDEGHIJFC
InOrder: BGEHIJDFAC
PostOrder: GJIHEFDBCA

Tree2
PreOrder: GFEIJHCDBA
InOrder: GJIHEFBDCA
PostOrder: JHIEBDACFG

option(A): Delete the last element of the list depends on the length of the list because you need to find the
last before element and last before element not accessible from the L pointer because it single list not double list
For finding last before element we need to linear search the linked list and so it depends on the length of the linked list.
After finding you need to perform the below operation
(Last before Node)−>next = NULL

option(B) : Deleting first Element does not depend on the length of the list you can simple delete by using the F pointer
i.e, F = F -> next;

option(C) : Add an element at the end of the list
we know the Address of the last Element of the list i.e L . So Just perform the following operations
L->next=new node
now L=new node

option(D) : Interchange the first two elements of the list
this can be performed using a temp node and does not depends on the length of the list.
Temp =F
F=F->next
Temp->next=F->next
F->next=Temp

The adjacency matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position (v_i,v_j) according to whether v_i and v_j  are adjacent or not.
For a simple graph with no self-loops, the adjacency matrix must have 0's on the diagonal. For an undirected graph, the adjacency matrix is symmetric.

After deletion the array became 14 , 13, 12, 8 , 10

→In Worst case Total Number of Comparisons for an element to find whether element is present or not in hash table depends on the Maximum size of the cluster in hash table + 1
→In Linear probing whenever empty slot found we stop probe
→So, Max Number of comparisons = Large cluster + 1
→Large cluster = 4 (S6,S3,S7,S1)
→Maximum Number of comparisons = 4+1=5

P has an execution path where it does not call itself -- TRUE
In any recursive procedure it require base condition to terminate the recursive procedure. otherwise it keep on calling itself it may leads to infinity

P either refers to a global variable or has at least one parameter --TRUE
Recursive function should either refers to a global variable or has at least one parameter so that it can be recursively called creating a new copy of local variables in the stack. In the absence of these, there would be no purpose of a recursive procedure as it will not be able to execute.

→Array index should be integers not real numbers.
→Enumerators, characters and boolean values can be used in place of an integer

option(A) : Type COLONGE : (LIME, PINE, MUSK, MENTHOL); var a : array [COLONGE] of REAL;
Takes enum values as index

option(B) : var a : array [REAL] of REAL;
Takes real number values as index

option(C): var a : array [‘A’…’Z’] of REAL;
Takes characters values as index

option(D): var a : array [BOOLEAN] of REAL;
Takes boolean values as index

→Insertion operation can be performed in 3 ways in a circular linked list. they are listed below

1. Inserting At Beginning of the circular linked list
2. Inserting At End of the circular linked list
3. Inserting At Specific location in the circular linked list

→Deletion operation can be performed in 3 ways in a circular linked list. they are listed below

1. Deleting from Beginning of the circular linked list
2. Deleting from End of the circular linked list
3. Deleting a Specific Node in circular linked list

→ Breadth-First Search performs level-order traversal by which using a queue data structure.
→ Depth First Search using a stack data structure.

Assume Vertices are un-labelled. Total number of distinct simple graphs upto 3 nodes in un-labelled graph = 1+2+4=7.
Total number of distinct simple graphs upto 3 nodes in labeled graph = 11

→The graph containing maximum number of edges in a n-node undirected graph without self loops is called complete graph.
→Complete Graph : A Complete Graph is a graph in which every pair of vertices is connected by an edge
→Total number of edges in a complete graph of N vertices = ( n * ( n – 1 ) ) / 2

→There are 3 types of parentheses [ ] { } ().
→Stack is a straightforward choice for checking if left and right parentheses are balanced.
→Stack follows last in first out. Open parenthesis is pushed into the stack and a closed parenthesis pops out elements till the top element of the stack is its corresponding open parenthesis. If the stack is empty, parenthesis is balanced otherwise it is unbalanced.

Embedded Pointer are Pointer Set in a data record which points to another data set.. So it provides a secondary access path.

(a + (b − c))* ((d − e)/(f + g − h))
= (a + (- b c)) * ((- d e) / ( + f g – h))
= (+ a – b c) * ((- d e) / (- + f g h)
= (+ a – b c) * (/ – d e – + f g h)
= * + a – b c / – d e – + f g h
So option(A) is correct one

→ It is not given that where are we going to insert the node in linked list. If we insert at the middle node will affect 4 pointers whereas at the head or tail will affect only 2 pointers.
→So it totally depends on where you are going to insert a new node at first or middle or last

→Here f(1)=1 ; f(2)=2 ; f(0)=0
f(4) = f(3)*f(2)+f(1)  = 2*2+1 = 5
f(3)  = f(2)*f(1)+f(0)  =2*1+0 = 2

Follow these steps to print bac.
1) POP element ‘a’ from stack A, push ‘a’ to Stack B.
2) POP element ‘b’ from stack A, print it.
3) POP element ‘a’ from stack B, and print it.
4) POP element ‘c’ from stack A, and print it.

Follow these steps to print bca.
1) POP element ‘a’ from stack A, push ‘a’ to Stack B.
2) POP element ‘b’ from stack A, print it.
4) POP element ‘c’ from stack A, and print it.
3) POP element ‘a’ from stack B, and print it.

Follow these steps to print cab.
1) POP element ‘a’ from stack A, push ‘a’ to Stack B.
1) POP element ‘b’ from stack A, push ‘b’ to Stack B.
3) POP element ‘c’ from stack A, and print it.
4) now you can print b not a in stack B

Option(c) is not possible

In the worst case, the element to be searched is present at end of the list then you have to compared with all elements of linked list.
For that it takes O(n) if linked list length is n

We can simply discard option(B) and option(D)  because in both cases we need to visit every node one after other.
Even in Doubly Linked List we won't get any better performance  in these two cases as we need to proceed from starting node and go until the last note in Linked List or Doubly Linked List.

We can ignore option(C)  also because To insert a new node in the Linked List after some specific node, no need not go back to the previous node in the Linked List but incase of doubly Linked List we need to go back and make connection (extra burden compared to single linked list).

In the case of option(A) we are supposed to delete the node (say x) whose location is given. Which means that before we remove node x from the Linked List we need to store the address of next node in the list, linked to node x in the address field of node just before node x (which currently store the address of node x).
Since we need to go back-and-forth in the list during this operation, doubly linked list will be a good help in increasing the efficiency by decreasing the time required for the operation.

Click this link for  explanation : https://academyera.com/isro-cs-2008-searching

Heap is a complete binary tree. Heaps are of 2 types

1. Min Heap
2. Max Heap

In Min Heap the value of each node is either greater or equal to its parents value and Root having the minimum value
In Max Heap the value of each node is equal or lesser to its parents value and Root having the maximum value

→In doubly linked list the minimum number of fields in a single node are 3
2 link fields
1 data field
→2 link fields name as previous and next both are points previous node and next node in sequence of node
→The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.
→If there is only one sentinel node, then the list is circularly linked via the sentinel node.

Given Expression = A + (B – C)* D
Prefix Notation 
A+(−BC) *D
A + ( (−BC) *D) )
A+( *−BCD )
( A+(*−BCD) )
+A*−BCD

To evaluate postfix expression:
1) if the element is operand then Push it on the stack.
2) if the element is operator then Pop top 2 elements from the stack.
3) compute the result, i.e. B operator A.
4) Finally, Push the result back on the stack.

Given expression: 8 2 3 ^ / 2 3 * + 5 1 * –

• 8 is operand So, push 8 to stack, Now stack contains 8
• 2 is operand So, push 2 to stack, Now stack contains 8 2
• 3 is operand So, push 3 to stack, Now stack contains 8 2 3
• ^ is operator So, pop 3 and 2 perform operation 2^3=8 and push 8 back to stack, Now stack contains 8 8
• / is operator So, pop 8 and 8 perform operation 8/8=1 and push 1 back to stack, Now stack contains 1
• 2 is operand So, push 2 to stack, Now stack contains 1 2
• 3 is operand So, push 3 to stack, Now stack contains 1 2 3
• * is operator So, pop 3 and 2 perform operation 3*2=6,Push results back to stack, Now stack contains 1 6

So option(A) is correct one 

---

• + pop 1 6 and perform 1+6=7 , Now push 7 back to stack 7
• push 5, stack contains 7,5
• push 1, stack contains 7,5,1
• * pop 1,5 and perform 1*5=5,push 5 back to stack 7,5
• - pop 7,5 and perform 7-5=2,push 2 back to stack 2

Given
Hash function = f(key) = key mod 7
Insertion order= 37, 38, 72, 48, 98, 11, 56

37, 38, 72, 48, 98, 11, 56

• 37 mod 7 = 2 ; 37 is stored at location 2
• 38 mod 7 = 3 ; 38 is stored at location 3
• 72 mod 7 = 2 ; location 2 is already occupied, so after linear probing 72 is stored in location 4
• 48 mod 7 = 6 ; 48 is stored at location 6
• 98 mod 7 = 0 ; 98 is stored at location 0
• 11 mod 7 = 4 ; again collision, so so after linear probing 11 is stored in location 4is stored in location 5

Finally 

Location	Key
0	98
1	56
2	37
3	38
4	72
5	11
6	48

Key 11 is stored in location 5

only 1 non leaf node means root node for a full binary tree it has left child and right child
For n =1 = (root + left + right)= 3 nodes = (2*1 +1)
if n is 3 each left and right have 2 child each = 7 nodes =2*3+1
So option(D) is the correct one 2n+1 nodes

Note : In a binary tree where each non-leaf node having exactly 2 children's then it contains
n+1 leaf nodes,
2n+1 total number of node ,
(2n+1)  - (n+1) non-leaf nodes

In-order traversal of Binary Search Tree always returns keys in increasing order(Ascending order)

Min Heap
1) Insertion    = O(log n)
2) Delete Min = O(log n) (Replace root node with INT_MAX and heapify)
3) Find = O(n)

Balanced BST : Balanced search tree have height log n
1) Insertion = O(log n)
2) Delete Min = O(log n)
3) Find = O(log n)

Deletion of smallest element can be done in O(log n) in both min heap and balanced BST

Insertion of an element if it is not already present in the set
→In heap, this operation takes O(n) because we have to find that element is present or not then insert then balancing.
So, Finding only takes O(n),balancing take O(log n). total O(n)+O(log n) = O(n).
→In Balanced BST we can perform this in O(log n)

Height is 3

1.  Add brackets as per precedence and order of evaluation
2.  ^, ×, +, −  high precedence from right to left
3. +, −, × are left associative and ^ is right associative.
4. Move operators to the right of immediate Parenthesis for postfix.

After adding brackets
( (a+(b*c))-(d^(e^f)) )
Now move operators to immediate right parenthesis then we obtain
( (a+(b*c))-(d^(ef ^)) )
( (a+(b*c))-(def ^^) )
( (a+(bc*))-(def ^^) )
( (abc *+  ) - (def ^^) )
(  (abc *+  ) - (def ^^)  )
abc *+  def ^^ -

Start address of the element = 49
Array Base address = 1120
size of each element = 3
Number of elements =48 if index start from 1(index vaue-1)
Number of elements =49 if index start from 0 (index value)

Start address of the element = Array Base address + Number of elements * size of each element

A[49] = 1120 + 48 * 3 = 1264

A full binary tree is a tree in which every node other than the leaves has two children
A full binary tree with n leaves contains 2n-1 nodes( total number of node)

• In figure 1 number of leaf nodes =2 ; so, 2n-1 = 2*2-1=Total number of node =3
• In figure 2 number of leaf nodes =4 ; so, 2n-1 = 2*4-1=Total number of node =7

• ∧ High priority then * +
• ∧ Right Associativity
• +,* left Associativity

Given Expression : 1*2^3*4^5*6
( 1*2^3*4^5*6 )
= 1 * (2^3) * (4^5 ) * 6
=1 * 8 * 1024 * 6
=49152

Number of Binary Search trees for n nodes is  calculated by using  = ( 2n_Cn / (n+1) )

For 4 keys or nodes  = 8_C4/5 =14

Therefore 14 distinct binary search trees possible for 4 keys.

• A has three siblings and B is parent of A, but no information is given whether node A is an internal node or leaf node and also total number of node in the graph is not given.
• As the information given is insufficient to decide what should be the degree of node A.

• Initial  values of x=1 and i=1
• After 1st iteration   :   x = 2 and i = 2
• After 2nd iteration :   x=4 and   i =3
• After 3rd iteration :   x=16 and  i = 4
• After  4th iteration : x=2¹⁶ and  i = 5
• During 5th iteration :  x=2¹⁶  < 500  Condition fails ; So, loop doesn't execute.
• So the answer is i = 5

Depth of a binary search tree

In this Question they are not mentioned whether the tree is  Binary tree or Binary Search Tree(BST)

• If it the Binary tree, we can't find Preorder of tree given In-order or Post-order of a tree. For finding any of a traversal out of three traversals (In-order, Preorder, Post-order) we need atleast any two of them.
• If it Binary Search Tree(BST) then it is possible to get pre-order

According the options I assuming it is BST
In-order = FBGADCE
Pre-order = ABFGCDE

Occupation Density = Number of Entries / Length of Symbol Table
Occupation Density = 25 / 152 = 0.164473
Occupation Density = 0.164

Length of the symbol table given = 152 and entries = 25
Occupation Density = Number of Entries / Length of Symbol Table
Occupation Density = 25 / 152 = 0.164473
Occupation Density = 0.164

A node have 2 fields associate with it in single linked list

1. Data : Data field contains the information
2. Next : Next filed contains address of the next node in the sequence which points to the next node

P = get node () :
get node() will create a node then P will point to that newly created node

info(p)=10 :
New node contains the data value of 10

next (p) = list :
adding new node at beginning of link list

In full binary tree is a binary tree in which all nodes except leaves have two children. A full binary tree with n leaves contains 2n-1 nodes( total number of node)

• In figure 1 number of leaf nodes =2 ; so, 2n-1 = 2*2-1=Total number of node =3
• In figure 2 number of leaf nodes =4 ; so, 2n-1 = 2*4-1=Total number of node =7

• An array is k-ordered array it means that array contains an element which is atmost k positions away from its original position in a sorted array.
• In 2-ordered array it means that array contains an element which is atmost 2 positions away from its original position in a sorted array.
• Maximum No of positions that an element can be from its position if the array is 1-ordered array = 1

• Deep binding binds the environment at the time the procedure is passed as an argument
• Shallow binding binds the environment at the time the procedure is actually called
• So for dynamic scoping with deep binding when add is passed into a 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.
• Shallow binding just traverses up until it finds the nearest variable that corresponds to the name so the answer would be 1.

Insert a sequence = 9,6,5,8,7,10

Given A(1:8, -5:5, -10:5)

• (1:8)    :   means having 8 elements => (upper limit – lower limit + 1) = 8 – 1 + 1 =8
• (-5 :5)  : means having 11 elements => (upper limit – lower limit + 1) = 5 – (-5) + 1 = 11
• (-10:5) : means having 16 elements => (upper limit – lower limit + 1) = 15 – (-10) + 1 = 16

So total number of elements = 8 * 11 * 16 = 1408

In circular queue

• Front = Rear then queue is empty
• (Rear+1) mod n == Front then queue is full
• For enqueue, we increment the REAR pointer and then insert an element
• For dequeue, we increment the FRONT and then remove the element at that position.

1^st element inserted at q[3]
2nd element at q[4]
3rd element at q[5]
and so on so 9th element inserted at q[0]
Front and Rear pointers are initialized to point at q[2]

Inorder traversal of Binary Search Tree produces the elements in Ascending order.
Inorder traversal = UQXWPVZY
Fourth smallest element in T = W

661 mod 13 = 11
182 mod 13 = 0
24 mod 13 = 11 collision, After performing linear probing it will get index 12
103 mod 13 =12 collision, After performing linear probing it will get index 1

Different trees possible for n nodes = nⁿ⁻²
Given n=4(A,B,C,D)
Different trees possible with 4 nodes =4^4-2=4²=16

Portion of the stack used for an invocation of a function is called the function’s stack frame or activation record.
Stack frame is also known as activation record it is a collection of all data on the stack associated with one subprogram call.

Stack frame contains listed below components :

1. Argument variables passed on the stack
2. Local variables
3. Return Address
4. Registers copies modified by the subprogram that need to be restored

Stack is used for static memory allocation and Heap for dynamic memory allocation

Click this link for explanation already solved : https://academyera.com/isro-2018-linked-list

Given
Hash function h(key) = key mod 7
Keys  : 44, 45, 79, 55, 91, 18, 63

• h(key) = key mod 7
• h(44) = 44 mod 7 = 2
• h(45) = 45 mod 7 = 3
• h(79) = 79 mod 7 = 2 collision occurred location 2 is filled with 44,So Apply linear probing (79+1) mod 7= 3 is also filled. So, again apply linear probing (79+2) mod 7= 4 So, 79 will occupy 4.
• h(55) = 55 mod 7 = 6
• h(91) = 91 mod 7 = 0
• h(18) = 18 mod 7 = 4   but 4 is occupied by 79 So, Apply linear probing then you get location 5.
• h(63) = 63 mod 7 = 0. but 0 is also occupied by 91 So, Apply linear probing then you get location 1.

Given
Hash function (7x+3) mod 4.
Keys are 1, 3, 8, 10.
h(x) = (7*x + 3) mod 4
h(1) = (7*1 + 3) mod 4 = (7 + 3) mod 4 = (10 mod 4) = 2
h(3) = (7*3 + 3) mod 4 = (21 + 3) mod 4 = (24 mod 4) = 0
h(8) = (7*8 + 3) mod 4 = (56 + 3) mod 4 = (59 mod 4) = 3
h(10)= (7*10+ 3) mod 4 = (70 + 3) mod 4 = (73 mod 4) = 1

Number of leaf nodes for an n-ary tree where each node having "n" children or "0" children is L = (n-1)I + 1
Where,
Let Capital N = Total Number of nodes
L = Number of leaf nodes
I = Number of internal nodes
N = Number of leaf nodes + Number of internal nodes
N = L+I

Given 3 children or 0 children in this Question i.e n=3
L = (n-1)I + 1
L = (3 -1)I + 1
L = 2I + 1
we know that Total Number of nodes = Number of leaf nodes + Number of internal nodes
so Number of internal nodes I = N - L

Coming into the problem
L = 2I + 1 substitute I = N - L
L = 2 (N - L) + 1
L = 2n - 2L + 1
3L = 2N + 1
Thus, L = (2N +1)/3

Refer this link : https://academyera.com/kvs-30-2018-part-b-trees

Since recursive algorithms, the execution order based on the the reverse of the order in which it goes forward during execution i.e function calls are executed in Last In First Out order. So, Stack is the best data structure for converting Recursive to Iterative implementation.

Push the operands into the stack whenever you see operator then pop last 2 operands on the stack  and perform operations(+,-,*/) on last 2 operands in the stack  and push the results back into stack.

10 10 +60 6 / * 8 -

Symbol  Stack 
10              10            operand push into the stack
10             10 10       operand push into the stack
+               20            Now stack contains 15; Apply operator(+) on last 2 operands in stack i.e 10+10=20
60            20 60      operand push into the stack
6              20 60 6   operand push into the stack
/              20 10       60/6=10
*              200           20*10=200
8             200 8       operand push into the stack
-             192            Apply operator(-) on last 2 operands in stack i.e 200-8 =192

Following combination can uniquely identify a binary tree.

1. In-order and Post-order.
2. In-order and Pre-order.
3. In-order and Level-order.

And following will not helpful to uniquely identify a binary tree.

1. Post-order and Pre-order.
2. Post-order and Level-order.
3. Preorder and Level-order.

Note : We can't build a unique Binary tree without In-order

Deque generally called as double-ended queue Deque is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

• In Input-restricted deque the deletion can be made from both ends but insertion can be made at one end only.
• In output-restricted deque the insertion can be made at both ends but deletion can be made from one end only.

Stack is data structures is used for implementing depth first traversal(DFS) of a graph

• In depth-first traversal  generally we investigate one child’s descendants before exploring its right siblings.
• In breadth-first traversal generally we explore all nodes at the same depth before moving on to any deeper nodes.

• fun1(head → next);
• printf("%d".head → data);

Recursive call of function fun1 pushed into top of the stack before entering in to printf statement, hence last recursive call in top of the stack executes printf statement first and then second to last function which is on top of stack is popped and executed and so on.
So it Prints all nodes of linked list in reverse order

Example 1,2,3,4,5 , null

stack

1. fun1
2. fun1
3. fun1
4. fun1
5. fun1

Now Top of the stack is 5.fun1
5. fun1 point to element 5 and print 5
4. fun1 point to element 5 and print 4
3. fun1 point to element 5 and print 3
2. fun1 point to element 5 and print 2
1. fun1 point to element 5 and print 1
output : 5,4,3,2,1

The given code snippet reverses a doubly linked list. In a doubly-linked list, each node has three fields namely data field, previous field, and next field.
The data field holds the data of the current node, the previous field holds the address of the previous node and the next field holds the address of the next node.
In order to reverse a doubly-linked list, we need to swap the previous and the next fields of all the nodes, change the previous field of the head node and the next field of the last node.

• Initially current pointer is pointed to head of the linked list.
• while loop in the program traverses the entire list till end by swapping prev and next pointers of all the nodes.
• After first iteration prev of element 1 points to next of element 1 i.e. element 2 and next of element 1 points to prev of element 1.
• After executing the while loop, the head pointer is pointed to the prev of last element i.e. 6th element. Thus making the last element as first. Hence the whole list now is reversed.

Prints binary representation of n using recursive method
step 1) if NUM > 1
a) push NUM on stack
b) recursively call function with 'NUM / 2'
step 2)
a) pop NUM from stack, divide it by 2 and print it's remainder

Given
+, -, x  are left associative
^          is right associative.

order of precedence from highest to lowest
^
x
+
-

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 ^ ^ -

• Every node in an AVL tree need to store the balance factor (-1, 0, 1)
• Get the balance factor (left subtree height – right subtree height) of the current node.
• If balance factor is > 1, then we can say that current node is unbalanced and we are either in Left Left case or left Right case. To check whether it is left left case or not, compare the newly inserted key with the key in left subtree root.
• If balance factor is < -1, then we can say that current node is unbalanced and we are either in Right Right case or Right-Left case. To check whether it is Right Right case or not, compare the newly inserted key with the key in right subtree root.

Refer this Link : https://academyera.com/isro-cs-2009-binary-trees-2     Figure 2

• A full binary tree with n leaves contains 2n-1 total nodes =2(4)-1=Total number of nodes is 7
• A full binary tree with n non-leaves contains 2n+1 total nodes  =2(3)+1=Total number of nodes is 7

Figure 1

• A full binary tree with n leaves contains 2n-1 total nodes =2(2)-1=Total number of nodes is 3
• A full binary tree with n non-leaves contains 2n+1 total nodes  =2(1)+1=Total number of nodes is 3

Initially heap has 10, 8, 5, 3, 2 So, Finally we get the heap whose level order traversal is 10,8,7,3,2,1,5

In this question the hint is "not necessarily one after another" It means that we can insert n elements at once and not necessarily have to wait for first insert to be completed before doing second insert

The worst case time complexity for insertion in a binary heap is O(Logn) So inserting n elements in a heap of size n should take Θ(nlogn) time.

So alternative approach we can use hear is just insert n elements in heap without any computation i.e. in constant time we can insert all elements and  after which we can apply Heapify() operation(this operation creates heap in linear time) on the array of those element and Hence we can obtain a Heap in O(n) time complexity.

Suppose we want to insert node x after node y then
In Insertion only 2 pointers needs to be modified.
x→next = y→next // node x is inserted
y→next = x // node y is pointing to node x

Load factor is ratio  between Number of entries  that are currently occupied in hash table  and the total number of entries that are present in hash table.
Load factor  = Number of entries occupied /  Total number of entries 
If the load factor is less, tree space will be more this means probability of collision is less. So the search time will be less

Click this link for explanation : https://academyera.com/isro-2018-hashing

Click this link for explanation : https://academyera.com/nielit-scientist-2016-march-linked-list

Click this link for explanation  : https://academyera.com/nielit-scientist-c-2016-hashing-3

Click this link for explanation : https://academyera.com/isro-2018-hashing

• Depth First Search(DFS) of a graph takes O(m+n) time when the graph is represented using adjacency list.
• Depth First Search(DFS) of a graph takes O(n)² time when the graph is represented using adjacency matrix
• Graph is represented as an “n x n” matrix in adjacency matrix. O(n) calls are made to DFS visit and in DFS visit, examining neighbours of each vertex takes O(n) times so total time O(n²)

Total Number of Nodes= nk+1
where
n= internal nodes
k=k-arry
1=only 1 root node

We know that
Total number of nodes = Internal nodes + leaf nodes
leaf node = Total number of nodes - Internal nodes
=nk+1 - n // Total Number of Nodes= nk+1
=n(k-1)+1

• Binary search is possible on linked list but there is no point of using it becoz at the end it would take same time as normal linear search.
• Binary search needs  access to any random element  in constant time. With linked list the this is not satisfied as any random element in linked list cannot be accessed in constant time, but it must be traversed completely.
• Both Merge sort and Insertion sort can be used for linked lists. The slow random-access performance of a linked list makes other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. Since worst case time complexity of Merge Sort is O(nLogn) and Insertion sort is O(n²), merge sort is preferred.

Click this link for explanation : https://academyera.com/isro_1995-7

Click this link for explanation : https://academyera.com/isro-2016-hashing-2

Pre-order   : ROOT NODE,LEFT NODE,RIGHT NODE
In-order     : LEFT NODE,ROOT NODE,RIGHT NODE
Post-order : LEFT NODE,RIGHT NODE,ROOT NODE

Post-order traversal for binary search tree : 5,4,10,8,6,17,31,49,43,19,11

To make Hash table 10% full then we have to insert at least ceil(100x10/100) = 10 values.
Probability of no collision for first 10 entries =100 _P10 /100¹⁰ = (100*99*98*97*96*95*94*93*92*91)/100¹⁰
Therefore, at least 1 collision occurs in 10 entries
=1 − Probability of no collision for first 10 entries
=1 - (100*99*98*97*96*95*94*93*92*91)/100¹⁰
= 0.34(approximately)

Max-heap is a complete binary tree in which Each node(Kc) in a tree has a key which is less than or equal to the key of its parent node(Kn).

Pass by value means you are making a copy in memory of the actual parameter's value that is passed in, a copy of the contents of the actual parameter. Use pass by value when when you are only "using" the parameter for some computation, not changing it for the client program.

Pass by reference is also called pass by address and  a copy of the address of the actual parameter is stored.
Use pass by reference when you are changing the parameter passed in by the client program.

The location of A[i,j] elements can be obtained in row major order by using the below expression

location of A[i,j] = Base_address + S[N(i)+(j)]

Base Address = Address of the first element in array
Hear Base Address =A
S = Size of each element in the array
M = Number of rows in the array
N = Number of columns in the array

location of A[i,j] = A + S[N(i)+(j)]

Degree of the node is the total number of its children the total number nodes that originate from it. The leaf of the tree does not have any child so its degree of leaf node is 0.

Given
The nodes with degree 1 is 4.
The nodes with degree 2 is 3.
The nodes with degree 3 is 3.
--------------------------------------------
∴ Number of internal nodes = 4+3+3 = 10
----------------------------------------------
Number of leaf node = ( sum of degree of all internal nodes - number of internal nodes + 1 )
Number of leaf node  = (4*1+3*2+3*3) - 10 +1
Number of leaf node  =10

VARCHAR is variable length, while CHAR is fixed length.

Attribute B size is based on maximum size of the column because it is fixed length i.e 20

Attribute A size is based on values entered in the variable i.e xyz total 3 values

therefore Attribute A has 3 spaces and Attribute b has 20 spaces

Note: only difference is variable length and fixed length
If it is variable length count the values entered in the variable
If it is fixed length then take given data size

Given Sequence of insertion is 60,25,72,15,30,68,101,13,18,47,70,34
Elements 13, 15, 18, 25, 30, 34, 47 are less than 60 and 68, 70, 72, 101 are grater than 60.

Nodes to the left subtree of Binary Search Tree are 13 15 18 25 30 34 47
Therefore The number of nodes in the left subtree is 7

In Worst case node "a" could be the last node or second last node, In that case full traversal of the list is required. which takes O(n)
IF node a is intermediate node then simply copy the data from the next node to the node to be deleted and delete the next node. which takes O(1)

// temporary node pointing to next pointer to be deleted
struct node *temp = node_a_ptr -> next;

// Copy data of next node to this node
node_a_ptr->data = temp->data;

// Now Unlink next node
node_a_ptr->next = temp->next;

// Delete the next node
free(temp);

To evaluate postfix expression:
1) if the element is operand then Push it on the stack.
2) if the element is operator then Pop top 2 elements from the stack.
3) compute the result, i.e. B operator A.
4) Finally, Push the result back on the stack.

Given expression: 6 2 3 * / 4 2 * + 6 8 * -

• 6 is operand So, push 6 to stack, Now stack contains 6
• 2 is operand So, push 2 to stack, Now stack contains 6 2
• 3 is operand So, push 3 to stack, Now stack contains 6 2 3
• *  is operator So, pop 3 and 2 perform operation 2*3=6 and push 6 back to stack, Now stack contains 6 6
• /  so, 6/6 =1,Now stack contains 1
• 4 is operand So, push 4 to stack, Now stack contains 1 4
• 2 is operand So, push 2 to stack, Now stack contains 1 4 2
• * so pop top 2 operands in stack and perform the operation using given operator 2*4=8,, stack=1 8

So option(B) is correct one   stack contains 1 , 8.. below will the continuation

---

• + , so 1+8=9
• 6 stack contains 9 6
• 8, now stack contains 9. 6 ,8
• * so 6*8=48, so stack contains 9,48

Given sequence 42, 25, 30, 40, 22, 35, 26 resultant max-heap is stored in an array = 42, 40, 35, 25, 22, 30, 26

In a max heap, the smallest element is always present at a leaf node. So we need to check all leaf nodes there can be up to n/2 leaf nodes which takes O(n) time complexity

Click this link for explanation : https://academyera.com/nielit-sta-2016-march-2016-heap-tree-2

Root node wii be 5

• B-Tree is known as self-balancing tree
• B-Trees need not be the binary tree
• In B-Tree the nodes are sorted in in-order traversal Unlike binary tree
• In B-tree a node may have more than 2 children.

Maximum number of nodes  in a binary tree of level k is  2^k -1   = 2³-1 =7 nodes

True : In adjacency list representation, space is saved for sparse graphs.

True : Deleting a vertex in adjacency list representation is easier than adjacency matrix representation because
For deleting a vertex in adjacency list, we need to search for the vertex in adjacency list which takes o(|v|) time after deleting edge traversal which takes O(|E|), finally,
For deleting a vertex in adjacency list takes O(|V|+|E|)
For deleting a vertex in adjacency matrix will takes O(V²)

True : Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
Insertion of a vertex can be done directly in O(1) in adjacency list time
Insertion of a vertex can be done in matrix it will require O(V²)

BFS

• BFS  also called as Breadth First Search.
• BFS uses  the Queue as the data structure for finding the shortest path in graph.
• In BFS one vertex is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue.
• BFS is vertex based technique

DFS

• DFS also called as Depth First Search.
• Depth First Search(DFS) uses the Stack as the data structure and performs 2 stages, 1^st visited vertices are pushed into stack and second if there is no vertices then visited vertices are popped.
• DFS is is edge based technique

In DFS(Depth First Search) we traverse one node to another in depth first order.
So, abfehg is not possible  because we can not go from f to e directly.
Remaining all options we can reach directly from the node to the next node.

push means inserting the element into stack and pop means delete the element in stack
Given

• push(1)    : push the element into stack now stack contains 1
• push(2)   : push the element into stack now stack contains 1,2 (2 is the top of the stack)
• pop          :  pop the top element from stack now stack contains 1
• push(1)   :  push the element into stack now stack contains 1,1
• push(2)  :  push the element into stack now stack contains 1,1,2
• pop         : pop the top element from stack now stack contains 1,1
• pop         : pop the top element from stack now stack contains 1
• pop         : Now stack is empty
• push(2) : stack contains 2
• pop        :  Now stack is empty

POP  sequence elements are 2,2,1,1,2

Click this link for explanation already solved : https://academyera.com/isro-2018-hashing-2

We can implement queue using 2 stacks
Queue fallows first in first out manner (FIFO)
Stack fallows Last in first out manner (LIFO)

Accumulator implicitly treated as the top-of-stack location, and for successive load orders to push previously loaded operands down into the stack automatically. Arithmetic orders then operate between the two most recently loaded operands, and leave their result on the stack, so that no address specification is required. These are therefore 0-address instructions and systems which use this arrangement are frequently known as stacking machines. Given

• PUSH 15  : Now stack contains 15
• PUSH 4    : Now stack contains 15,4
• PUSH 6    : Now stack contains 15,4,6(6 is the top of the stack)
• MULT       : POP last 2 operands and perform the operation 4*6=24 , Now stack contains 15,24
• PUSH 30 :  Now stack contains 15,24,30
• ADD          : 24+30=54 ,    Now stack contains 15,54
• ADD          : 15 + 54  =69 Now stack contains 69

Level order traversal of a tree is also know as breadth first traversal
So BFS Uses Queue as the data structure  while DFS uses stack

Number of nodes in a binary tree of height h is at least h + 1  and at most 2^h+1 -1  where h is the depth of the tree.
Depth of the tree : Maximum number of edges from root to leaf path.
2^h+1 -1  is Maximum number of nodes in a complete binary tree.

BFS = QUEUE
DFS = Stack

We can use circular queue to implement enqueue operations and dequeue operations in O(1) time

Given n=4
Number of Binary Trees possible are = (2n)!/(n+1)!n!
Number of Binary Trees possible are = (2*4)!/(4+1)!4!
Number of Binary Trees possible are = 8!/5!*4!
Number of Binary Trees possible are = 14

• They mentioned in the question that sequence of 0's are followed by 1's so it means the Array is already sorted
• So you can apply binary search hear because of the sorted array
• At every stage you need to compare (low element index + high element index)/2 and if you get results as 1 then binary search will check Left array. If it 0 then binary search will check right array
• Total number of probes in worst case = ceil(log₂ 31)=5

In-order of BST is in Ascending order
Pre-order = 41,23,11,31,62,50,73
In-order   = 11,23,31,41,50,62,73
Draw the BST using In-order and pre-order

                   41
                 /    \
                23     62
               /  \    / \
              11  31  50  73

Post order : 11,31,23,50,73,62,41

*(X+i)=*(&x[i]) - option(A) is TRUE  

*(X+i) means value at "i" location of base "x" address

*  is nothing but value at address location

&x[i] is equivalent to x+i and x[i] is equivalent to *(x+i).

&x[0] and x is the same

*(X+i)=X[i]=*(&x[i])

In a Full Binary Tree Every node contains Exactly 2 children's except leaf nodes

In this Question they mention degree 0, degree 1,degree 2

• Degree 0 is allowed because it is leaf node in Full Binary Tree
• Degree 2 is allowed in Full Binary Tree because it contains Exactly 2 children's which is internal nodes
• Degree 1 is nothing but A node with 1 child is not allowed

So, we can eliminate Option(B) and option(D)

We know that

• A full binary tree of a given Height h has  2^h-1 nodes
• Internal nodes = leaf nodes-1

Number of leaf nodes(degree 0)= 2^h-1 =2⁹=512
Number of Nodes with degree 1 = 0
Number of internal nodes(degree 2) =2^h-1 -1=2⁹-1=511

Click this link for explanation : https://academyera.com/nielit-scientist-c-2016-march-hashing

45 is not present

Inorder traversal of Binary Search Tree(BST) prints all the keys in Ascending order or Increasing order.

There are 3 major methods of storing files on the disks
1) Contiguous allocation
2) Linked allocation
3) Indexed allocation

Contiguous Allocation

• All blocks of a file are kept together contiguously.
• Fast Performance
• Problems can arise when files grow or if the exact size of a file is unknown at creation time
• Suitable for small sequentially accessed file

Linked Allocation

• Disk files can be stored as linked lists with the expense of the storage space consumed by each link.
• No external fragmentation
• Suitable for large sequentially accessed file
• Random access is not possible  If one link is lost then cannot access subsequent blocks

Indexed Allocation

• Indexed Allocation combines all of the indexes for accessing each file into a common block ( for that file )
• opposed to spreading them all over the disk or storing them in a FAT table
• Suitable for large randomly accessed file

A Full Binary Tree of height h has 2^h-1 nodes
2^h-1 = 63
Apply log on both sides
log₂ 2^h-1  = log₂63
h= 6
Note :  simply use cell(log₂n) then you will get the height h

2–3–4 tree is also called 2–4 tree Tress
It is self-balancing data structure that is commonly used to implement dictionaries
2–3–4 means Every node with children's which is internal node in the tree having Either 2 children's or 3 or 4 child nodes

• 2-node have 1 data element and  if internal has 2 children's
• 3-node have 2 data elements and if internal has 3 children's
• 4-node have 3 data elements and if internal has 4 children's

Click this link for explanation : https://academyera.com/nielit-scientist-c-2016-march-hashing

Initialization of variable in option(d) is not valid in C
char[] str is a declaration in Java but not in C language.

Every node in single linked list contains 2 fields
1.Address Filed : This field contains address of the next node in linked list
2.Data Filed : This field stores information i.e data

5 - 2 -3 *5 -2 will give results as 18
If we evaluate the expression as   (5-(2-3)) * (5-2).
- has precedence over * and if it associates from the right.

In order to search the element 4 we need to traverse all elements in order 6, 5, 4
So in worst case searching in binary search tree takes O(n) Time complexity