Data Structures  Subject Wise
Question 1 
Which of the following is application of Breadth First Search on the graph?
Finding the diameter of the graph  
Finding the bipartite graph  
Both (a) and (b)  
None of the above 
Question 1 Explanation:
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
Question 2 
A doubly linked list is declared as
struct Node {
int Value;
struct Node *Fwd;
struct Node *Bwd;
}
Where Fwd and Bwd represent forward and a backward link to the adjacent elements of the list. Which of the following segments of code deletes the node pointed to by X from the doubly linked list, if it is assumed that X points to neither the first nor the last node of the list?
struct Node {
int Value;
struct Node *Fwd;
struct Node *Bwd;
}
Where Fwd and Bwd represent forward and a backward link to the adjacent elements of the list. Which of the following segments of code deletes the node pointed to by X from the doubly linked list, if it is assumed that X points to neither the first nor the last node of the list?
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; 
Question 2 Explanation:
Just before deleting we need to link
X → Bwd → Fwd = X → Fwd
and X → Fwd → Bwd = X → Bwd
X → Bwd → Fwd = X → Fwd
and X → Fwd → Bwd = X → Bwd
Question 3 
If Tree1 and Tree2 are the trees indicated below :
Which traversals of Tree1 and Tree2, respectively, will produce the same sequence?
Preorder, Postorder  
Postorder, Inorder  
Postorder, Preorder  
Inorder, Preorder  
None 
Question 3 Explanation:
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
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
Question 4 
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A  
B  
C  
D 
Question 4 Explanation:
Question 5 
Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list.
The time of which of the following operations depends on the length of the list?
The time of which of the following operations depends on the length of the list?
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 
Question 5 Explanation:
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
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
Question 6 
Let X be the adjacency matrix of a graph G with no self loops. The entries along the principal diagonal of X are
All zeros  
All ones  
Both zeros and ones  
Different 
Question 6 Explanation:
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 selfloops, the adjacency matrix must have 0's on the diagonal. For an undirected graph, the adjacency matrix is symmetric.
For a simple graph with no selfloops, the adjacency matrix must have 0's on the diagonal. For an undirected graph, the adjacency matrix is symmetric.
Question 7 
Given a binarymax heap. The elements are stored in an array as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?
14,13,8,12,10  
14,12,13,10,8  
14,13,12,8,10  
14,13,12,10,8 
Question 7 Explanation:
After deletion the array became 14 , 13, 12, 8 , 10
Question 8 
A hash table with 10 buckets with one slot per bucket is depicted here. The symbols, S1 to s7 are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is
4  
5  
6  
3 
Question 8 Explanation:
→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
→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
Question 9 
Let P be a procedure that for some inputs calls itself (i.e. is recursive). If P is guaranteed to terminate,
which of the following statement(s) must be true?
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
which of the following statement(s) must be true?
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 
Question 9 Explanation:
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.
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.
Question 10 
Which of the following is an illegal array definition?
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; 
Question 10 Explanation:
→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
→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
Question 11 
Given two statements:
(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
(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 
Question 11 Explanation:
→Insertion operation can be performed in 3 ways in a circular linked list. they are listed below
 Inserting At Beginning of the circular linked list
 Inserting At End of the circular linked list
 Inserting At Specific location in the circular linked list
 Deleting from Beginning of the circular linked list
 Deleting from End of the circular linked list
 Deleting a Specific Node in circular linked list
Question 12 
Which of the following data structure is useful in traversing a given graph by breadthfirst search?
Stack  
List  
Queue  
None of the above 
Question 12 Explanation:
→ BreadthFirst Search performs levelorder traversal by which using a queue data structure.
→ Depth First Search using a stack data structure.
→ Depth First Search using a stack data structure.
Question 13 
The number of distinct simple graphs with up to three nodes is
15  
10  
7  
9 
Question 13 Explanation:
Assume Vertices are unlabelled.
Total number of distinct simple graphs upto 3 nodes in unlabelled graph = 1+2+4=7.
Total number of distinct simple graphs upto 3 nodes in labeled graph = 11
Total number of distinct simple graphs upto 3 nodes in labeled graph = 11
Question 14 
The maximum number of edges in a nnode undirected graph without self loops is
N^{2}  
N * (n1)/2  
N – 1  
(n + 1) * n/2 
Question 14 Explanation:
→The graph containing maximum number of edges in a nnode 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
→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
Question 15 
The best data structure to check whether an arithmetic expression has balanced parenthesis is a
Queue  
Stack  
Tree  
List 
Question 15 Explanation:
→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.
→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.
Question 16 
Embedded pointer provides
A secondary access path  
A physical record key  
An inverted index  
A primary key 
Question 16 Explanation:
Embedded Pointer are Pointer Set in a data record which points to another data set.. So it provides a secondary access path.
Question 17 
Choose the equivalent prefix form of the following expression
(a + (b − c))* ((d − e)/(f + g − h))
(a + (b − c))* ((d − e)/(f + g − h))
* +a − bc /− de − +fgh  
* +a −bc − /de − +fgh  
* +a − bc /− ed + −fgh  
* +ab − c /− ed + −fgh 
Question 17 Explanation:
(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
= (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
Question 18 
In a doubly linked list, the number of pointers affected for an insertion operation will be
4  
0  
1  
None of these 
Question 18 Explanation:
→ 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
→So it totally depends on where you are going to insert a new node at first or middle or last
Question 19 
What is the value of F(4) using the following procedure:
function F(K : integer)
integer;
begin
if (k<3) then F:=k
else F:=F(k1)*F(k2)+F(k3)
end;
function F(K : integer)
integer;
begin
if (k<3) then F:=k
else F:=F(k1)*F(k2)+F(k3)
end;
5  
6  
7  
8 
Question 19 Explanation:
→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
f(4) = f(3)*f(2)+f(1) = 2*2+1 = 5
f(3) = f(2)*f(1)+f(0) =2*1+0 = 2
Question 20 
Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B An entry popped out of the stack B can be only be printed. In this arrangement, which of the following permutations of a, b, c are not possible?
b a c  
b c a  
c a b  
a b c 
Question 20 Explanation:
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
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
Question 21 
The time required to search an element in a linked list of length n is
O(log n)  
O(n)  
O(1)  
(n^{2}) 
Question 21 Explanation:
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
For that it takes O(n) if linked list length is n
Question 22 
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?
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 
Question 22 Explanation:
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 backandforth 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.
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 backandforth 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.
Question 23 
The time required to search an element in a linked list of length n is
O(log n)  
O(n)  
O(1)  
O(n^{2}) 
Question 23 Explanation:
Click this link for explanation : https://academyera.com/isrocs2008searching
Question 24 
A complete binary tree with the property that the value at each node is as least as large as the values at its children is known as
Binary search tree  
AVL tree  
Completely balanced tree  
Heap 
Question 24 Explanation:
Heap is a complete binary tree. Heaps are of 2 types
In Max Heap the value of each node is equal or lesser to its parents value and Root having the maximum value
 Min Heap
 Max Heap
In Max Heap the value of each node is equal or lesser to its parents value and Root having the maximum value
Question 25 
The minimum number of fields with each node of doubly linked list is
1  
2  
3  
4 
Question 25 Explanation:
→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.
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.
Question 26 
The infix expression A+(B–C)*D is correctly represented in prefix notation as
A+B−C∗D  
+A∗−BCD  
ABC−D∗+  
A+BC−D∗ 
Question 26 Explanation:
Given Expression = A + (B – C)* D
Prefix Notation
A+(−BC) *D
A + ( (−BC) *D) )
A+( *−BCD )
( A+(*−BCD) )
+A*−BCD
Prefix Notation
A+(−BC) *D
A + ( (−BC) *D) )
A+( *−BCD )
( A+(*−BCD) )
+A*−BCD
Question 27 
The following postfix expression with single digit operands is evaluated using a stack:
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
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 
Question 27 Explanation:
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 * –
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
 + 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 75=2,push 2 back to stack 2
Question 28 
A Hash Function f is defined as f(key) = key mod 7. With linear probing, while inserting the keys 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0, in which location the key 11 will be stored (Count table index 0 as 0th location)?
3  
4  
5  
6 
Question 28 Explanation:
Given
Hash function = f(key) = key mod 7
Insertion order= 37, 38, 72, 48, 98, 11, 56
37, 38, 72, 48, 98, 11, 56
Key 11 is stored in location 5
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
Location  Key 
0  98 
1  56 
2  37 
3  38 
4  72 
5  11 
6  48 
Question 29 
A complete binary tree with n nonleaf nodes contains
Log_{2}n nodes  
N+1 nodes  
2n nodes  
2n+1 nodes 
Question 29 Explanation:
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 nonleaf node having exactly 2 children's then it contains
n+1 leaf nodes,
2n+1 total number of node ,
(2n+1)  (n+1) nonleaf nodes
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 nonleaf node having exactly 2 children's then it contains
n+1 leaf nodes,
2n+1 total number of node ,
(2n+1)  (n+1) nonleaf nodes
Question 30 
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder traversal sequence of the resultant tree?
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 
Question 30 Explanation:
Inorder traversal of Binary Search Tree always returns keys in increasing order(Ascending order)
Question 31 
A data structure is required for storing a set of integers such that each of the following operations can be done in O(log n) time, where n is the number of elements in the set.
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?
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 
Question 31 Explanation:
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)
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)
Question 32 
The following numbers are inserted into an empty binary search tree in the given order:
10, 1, 3, 5, 15, 12, 16.
What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
10, 1, 3, 5, 15, 12, 16.
What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
2  
3  
4  
6 
Question 32 Explanation:
Height is 3
Question 33 
Assume that the operators +, −, × are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, −. The postfix expression corresponding to the infix expression is a + b × c − d ^ e ^ f
Abc x + def ^ ^ −  
Abc x + de ^ f ^ −  
Ab + c × d − e^f^  
− + a × b c^^ def 
Question 33 Explanation:
 Add brackets as per precedence and order of evaluation
 ^, ×, +, − high precedence from right to left
 +, −, × are left associative and ^ is right associative.
 Move operators to the right of immediate Parenthesis for postfix.
( (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 ^^ 
Question 34 
A one dimensional array A has indices 1….75. Each element is a string and takes up three memory words. The array is stored at location 1120 decimal. The starting address of A[49] is
1267  
1164  
1264  
1169 
Question 34 Explanation:
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 vaue1)
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
Array Base address = 1120
size of each element = 3
Number of elements =48 if index start from 1(index vaue1)
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
Question 35 
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A  
B  
C  
D 
Question 35 Explanation:
Question 36 
A full binary tree with n leaves contains:
N nodes  
Log_{2} n nodes  
2n1  
2^{n} 
Question 36 Explanation:
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 2n1 nodes( total number of node)
A full binary tree with n leaves contains 2n1 nodes( total number of node)
 In figure 1 number of leaf nodes =2 ; so, 2n1 = 2*21=Total number of node =3
 In figure 2 number of leaf nodes =4 ; so, 2n1 = 2*41=Total number of node =7
Question 37 
The expression 1 * 2 ^ 3 * 4 ^ 5 * 6 will be evaluated as
3230  
16230  
49152  
173458 
Question 37 Explanation:
 ∧ High priority then * +
 ∧ Right Associativity
 +,* left Associativity
( 1*2^3*4^5*6 )
= 1 * (2^3) * (4^5 ) * 6
=1 * 8 * 1024 * 6
=49152
Question 38 
How many distinct binary search trees can be created out of 4 distinct keys?
5  
14  
24  
35 
Question 38 Explanation:
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.
For 4 keys or nodes = 8_{C4}/5 =14
Therefore 14 distinct binary search trees possible for 4 keys.
Question 39 
If node A has three siblings and B is a parent of A, what is the degree of A?
0  
3  
4  
None of the above 
Question 39 Explanation:
 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.
Question 40 
Consider the following pseudocode:
x:=1;
i:=1;
while (x ≤ 500)
begin
x:=2^{x} ;
i:=i+1;
end
What is the value of i at the end of the pseudocode?
x:=1;
i:=1;
while (x ≤ 500)
begin
x:=2^{x} ;
i:=i+1;
end
What is the value of i at the end of the pseudocode?
4  
5  
6  
7 
Question 40 Explanation:
 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^{16} and i = 5
 During 5th iteration : x=2^{16 } < 500 Condition fails ; So, loop doesn't execute.
 So the answer is i = 5
Question 41 
The average depth of a binary search tree is:
O(n^{0.5})  
O(n)  
O(log n)  
O(n log n) 
Question 41 Explanation:
Depth of a binary search tree
Question 42 
The inorder traversal of a tree resulted in FBGADCE. Then the preorder traversal of that tree would result in
FGBDECA  
ABFGCDE  
BFGCDEA  
AFGBDEC 
Question 42 Explanation:
In this Question they are not mentioned whether the tree is Binary tree or Binary Search Tree(BST)
Inorder = FBGADCE
Preorder = ABFGCDE
 If it the Binary tree, we can't find Preorder of tree given Inorder or Postorder of a tree. For finding any of a traversal out of three traversals (Inorder, Preorder, Postorder) we need atleast any two of them.
 If it Binary Search Tree(BST) then it is possible to get preorder
Inorder = FBGADCE
Preorder = ABFGCDE
Question 43 
A symbol table of length 152 is processing 25 entries at any instant. What is occupation density?
0.164  
127  
8.06  
6.08 
Question 43 Explanation:
Occupation Density = Number of Entries / Length of Symbol Table
Occupation Density = 25 / 152 = 0.164473
Occupation Density = 0.164
Occupation Density = 25 / 152 = 0.164473
Occupation Density = 0.164
Question 44 
A symbol table of length 152 is processing 25 entries at any instant. What is occupation density?
0.164  
127  
8.06  
6.08 
Question 44 Explanation:
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
Occupation Density = Number of Entries / Length of Symbol Table
Occupation Density = 25 / 152 = 0.164473
Occupation Density = 0.164
Question 45 
The following steps in a linked list
 p = getnode()
 info (p) = 10
 next (p) = list
 list = p
Pop operation in stack  
Removal of a node  
Inserting a node  
Modifying an existing node 
Question 45 Explanation:
A node have 2 fields associate with it in single linked list
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
 Data : Data field contains the information
 Next : Next filed contains address of the next node in the sequence which points to the next 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
Question 46 
Which of the following number of nodes can form a full binary tree?
8  
15  
14  
13 
Question 46 Explanation:
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 2n1 nodes( total number of node)
 In figure 1 number of leaf nodes =2 ; so, 2n1 = 2*21=Total number of node =3
 In figure 2 number of leaf nodes =4 ; so, 2n1 = 2*41=Total number of node =7
Question 47 
In an array of 2N elements that is both 2ordered and 3ordered, what is the maximum number of positions that an element can be from its position if the array were 1ordered?
1  
2  
N/2  
2N1 
Question 47 Explanation:
 An array is kordered array it means that array contains an element which is atmost k positions away from its original position in a sorted array.
 In 2ordered 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 1ordered array = 1
Question 48 
Consider the following pseudocode:
x : integer := 1
y : integer := 2
procedure add
x := x + y
procedure second (P: procedure)
x : integer := 2
P()
procedure first
y : integer := 3
second(add)
first()
write_integer (x)
What does it print if the language uses dynamic scoping with deep binding?
x : integer := 1
y : integer := 2
procedure add
x := x + y
procedure second (P: procedure)
x : integer := 2
P()
procedure first
y : integer := 3
second(add)
first()
write_integer (x)
What does it print if the language uses dynamic scoping with deep binding?
2  
3  
4  
5 
Question 48 Explanation:
 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.
Question 49 
The number of rotations required to insert a sequence of elements 9,6,5,8,7,10 into an empty AVL tree is?
0  
1  
2  
3 
Question 50 
Let A(1:8, 5:5, 10:5) be a three dimensional array. How many elements are there in the array A?
1200  
1408  
33  
1050 
Question 50 Explanation:
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
Question 51 
Consider a standard Circular Queue ‘q’ implementation (which has the same condition for Queue Full and Queue Empty) whose size is 11 and the elements of the queue are
q[0], q[1], q[2]…..,q[10].
The front and rear pointers are initialized to point at q[2] . In which position will the ninth element be added?
q[0], q[1], q[2]…..,q[10].
The front and rear pointers are initialized to point at q[2] . In which position will the ninth element be added?
Q[0]  
Q[1]  
Q[9]  
Q[10] 
Question 51 Explanation:
In circular queue
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]
 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.
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]
Question 52 
Consider the following binary search tree T given below: Which node contains the fourth smallest element in T ?
Q  
V  
W  
X 
Question 52 Explanation:
Inorder traversal of Binary Search Tree produces the elements in Ascending order.
Inorder traversal = UQXWPVZY
Fourth smallest element in T = W
Inorder traversal = UQXWPVZY
Fourth smallest element in T = W
Question 53 
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A  
B  
C  
D 
Question 53 Explanation:
Question 54 
Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if the keys 661, 182, 24 and 103 are inserted in that order?
0  
1  
11  
12 
Question 54 Explanation:
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
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
Question 55 
How many different trees are there with four nodes A, B, C and D ?
30  
60  
90  
16 
Question 55 Explanation:
Different trees possible for n nodes = n^{n−2}
Given n=4(A,B,C,D)
Different trees possible with 4 nodes =4^{42}=4^{2}=16
Given n=4(A,B,C,D)
Different trees possible with 4 nodes =4^{42}=4^{2}=16
Question 56 
Which of the following is NOT represented in a subroutine activation record frame for a stackbased programming language?
Values of local variables  
Return address  
Heap area  
Information needed to access non local variables 
Question 56 Explanation:
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 :
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 :
 Argument variables passed on the stack
 Local variables
 Return Address
 Registers copies modified by the subprogram that need to be restored
Question 57 
Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list.
The time for performing which of the given operations depends on the length of the linked list?
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 
Question 57 Explanation:
Click this link for explanation already solved : https://academyera.com/isro2018linkedlist
Question 58 
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 maxheap are and respectively. (Root is at level 0).
3, 14  
3, 10  
4, 14  
4, 10 
Question 58 Explanation:
Question 59 
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 
Question 59 Explanation:
Given
Hash function h(key) = key mod 7
Keys : 44, 45, 79, 55, 91, 18, 63
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.
Question 60 
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.
Here “__” denotes an empty location in the table.
3, 10, 1, 8, ___ , ___, ___.  
1, 3, 8, 10, ___, ___, ___.  
1, ___, 3, ___, 8, ___, 10  
3, 10, ___, ___, 8, ___, ___. 
Question 60 Explanation:
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
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
Question 61 
___ number of leaf nodes in a rooted tree of n nodes, where each node is having 0 or 3 children.
N/2  
(2n+1)/3  
(n1)/n  
(n1) 
Question 61 Explanation:
Number of leaf nodes for an nary tree where each node having "n" children or "0" children is L = (n1)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 = (n1)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/kvs302018partbtrees
Question 62 
_____ is used to convert from recursive to iterative implementation of an algorithm
Array  
Tree  
Stack  
Queue 
Question 62 Explanation:
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.
Question 63 
Evaluation of the given postfix expression
10 10 +60 6 / * 8  is:
10 10 +60 6 / * 8  is:
192  
190  
110  
92 
Question 63 Explanation:
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 2008 =192
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 2008 =192
Question 64 
___ pairs of traversals is not sufficient to build tree
Preorder and Inorder  
Postorder and Inorder  
Postorder and Preorder  
None of these 
Question 64 Explanation:
Following combination can uniquely identify a binary tree.
 Inorder and Postorder.
 Inorder and Preorder.
 Inorder and Levelorder.
 Postorder and Preorder.
 Postorder and Levelorder.
 Preorder and Levelorder.
Question 65 
A__ is a linear list in which insertions and deletions are made to from either end of the structure.
Circular queue  
Priority queue  
Stack  
Dequeue 
Question 65 Explanation:
Deque generally called as doubleended 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 Inputrestricted deque the deletion can be made from both ends but insertion can be made at one end only.
 In outputrestricted deque the insertion can be made at both ends but deletion can be made from one end only.
Question 66 
What data structures is used for depth first traversal of a graph
Queue  
Stack  
List  
None of above 
Question 66 Explanation:
Stack is data structures is used for implementing depth first traversal(DFS) of a graph
Question 67 
In the __ traversal we process all of a vertex's descendants before we move to an adjacent vertex
Depth First  
Breadth First  
Width First  
Depth Limited 
Question 67 Explanation:
 In depthfirst traversal generally we investigate one child’s descendants before exploring its right siblings.
 In breadthfirst traversal generally we explore all nodes at the same depth before moving on to any deeper nodes.
Question 68 
What does the following functions do for a given Linked list with first node as head?
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
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 
Question 68 Explanation:
 fun1(head → next);
 printf("%d".head → data);
So it Prints all nodes of linked list in reverse order
Example 1,2,3,4,5 , null
stack
 fun1
 fun1
 fun1
 fun1
 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
Question 69 
Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next
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?
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 
Question 69 Explanation:
The given code snippet reverses a doubly linked list. In a doublylinked 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 doublylinked 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.
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 doublylinked 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.
Question 70 
Following is C like Pseudo code of a function that takes a number as an argument, and uses a stack S to do argument, and uses a stack S to do processing.
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/2
}
// 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
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/2
}
// 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 
Question 70 Explanation:
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
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
Question 71 
Assume that the operators +,,x are left associative and ^ right associative. the order of precedence(from highest to lowest) is ^,x,+,.
The postfix expression corresponding to the infix expression a+bxcd^e^f is
The postfix expression corresponding to the infix expression a+bxcd^e^f is
abc x+def^^  
abc xde^f^  
ab +c xd e^f ^  
+ a x bc ^^def 
Question 71 Explanation:
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 ^ ^ 
+, , 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 ^ ^ 
Question 72 
A balance factor in AVL tree is used to check
What rotation to make  
If all childs nodes are at same level  
When the last rotation occurred  
If the tree is unbalanced 
Question 72 Explanation:
 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 RightLeft case. To check whether it is Right Right case or not, compare the newly inserted key with the key in right subtree root.
Question 73 
A full binary tree with n nonleaf nodes contains
Log _{2} n nodes  
N+1 nodes  
2n nodes  
2n+1 nodes 
Question 73 Explanation:
Refer this Link : https://academyera.com/isrocs2009binarytrees2
Figure 2
 A full binary tree with n leaves contains 2n1 total nodes =2(4)1=Total number of nodes is 7
 A full binary tree with n nonleaves contains 2n+1 total nodes =2(3)+1=Total number of nodes is 7
 A full binary tree with n leaves contains 2n1 total nodes =2(2)1=Total number of nodes is 3
 A full binary tree with n nonleaves contains 2n+1 total nodes =2(1)+1=Total number of nodes is 3
Question 74 
A priority queue is implemented as a Maxheap. Initially, it has 5 elements. The levelorder traversal of the heap is: 10,8,5,3,2.
Two new elements 1 and 7 are inserted into the heap in that order. The levelorder traversal of the heap after the insertion of the elements is
Two new elements 1 and 7 are inserted into the heap in that order. The levelorder traversal of the heap after the insertion of the elements is
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 
Question 74 Explanation:
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
Question 75 
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. Total time required for this is
O(logn)  
O(n)  
O(nlogn)  
O(n ^{2} ) 
Question 75 Explanation:
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.
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.
Question 76 
In a circularly linked list organization, insertion of a record involves the modification of
No pointer  
1 pointer  
2 pointer  
3 pointer 
Question 76 Explanation:
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
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
Question 77 
The Average search time of hashing, with linear probing will be less if the load factor
Is far less than one  
Equals one  
Is far greater than one  
None of these 
Question 77 Explanation:
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
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
Question 78 
A hash table with 10 buckets with one slot per bucket is depicted. The symbols, S1 to S7 are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is
6  
5  
4  
None 
Question 78 Explanation:
Click this link for explanation : https://academyera.com/isro2018hashing
Question 79 
In a circularly linked list organization, insertion of a record involves the modification of
No pointer  
1 pointer  
2 pointer  
3 pointer 
Question 79 Explanation:
Click this link for explanation : https://academyera.com/nielitscientist2016marchlinkedlist
Question 80 
The average search time of hashing, with linear probing will be less if the load factor
Is far less than one  
Equals one  
Is far greater than one  
None of these 
Question 80 Explanation:
Click this link for explanation : https://academyera.com/nielitscientistc2016hashing3
Question 81 
A hash table with 10 buckets with one slot per bucket is depicted. The symbols, S1 to S7 are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is
6  
5  
4  
None 
Question 81 Explanation:
Click this link for explanation : https://academyera.com/isro2018hashing
Question 82 
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on DFS of G? Assume that the graph is represented using adjacency matrix
O(n)  
O(m+n)  
O(n^{2})  
O(mn) 
Question 82 Explanation:
 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)^{2} 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^{2})
Question 83 
In a complete karray, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is
Nk  
(n1)k+1  
N(k1)+1  
N(k1) 
Question 83 Explanation:
Total Number of Nodes= nk+1
where
n= internal nodes
k=karry
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(k1)+1
where
n= internal nodes
k=karry
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(k1)+1
Question 84 
Which among the following algorithm can’t be used with linked list?
Binary search  
Linear Search  
Insertion sort  
Merge Sort 
Question 84 Explanation:
 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 randomaccess 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^{2}), merge sort is preferred.
Question 85 
Which among the following algorithm can’t be used with linked list?
Binary search  
Linear Search  
Insertion sort  
Merge Sort 
Question 85 Explanation:
Click this link for explanation : https://academyera.com/isro_19957
Question 86 
A hash function f defined as f(key)=key mod 7, with linear probing, insert the keys 37,38,72,48,98,11,56 into a table indexed from 11 will be stored in the location
3  
4  
5  
6 
Question 86 Explanation:
Click this link for explanation : https://academyera.com/isro2016hashing2
Question 87 
Traversing a binary tree first root and then left and right subtree called__ traversal
Postorder  
Preorder  
Inorder  
None of these 
Question 87 Explanation:
Preorder : ROOT NODE,LEFT NODE,RIGHT NODE
Inorder : LEFT NODE,ROOT NODE,RIGHT NODE
Postorder : LEFT NODE,RIGHT NODE,ROOT NODE
Inorder : LEFT NODE,ROOT NODE,RIGHT NODE
Postorder : LEFT NODE,RIGHT NODE,ROOT NODE
Question 88 
Given the sequence of nodes {11,6,8,19,4,10,5,17,43,49,31} not necessarily in correct order for generating binary search tree. The corresponding postorder traversal of the BST is:
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 
Question 88 Explanation:
Postorder traversal for binary search tree : 5,4,10,8,6,17,31,49,43,19,11
Question 89 
A hash table has space for 100 records. then the probability of collision before the table is 10% full, is
0.45  
0.5  
0.3  
0.34(approximately) 
Question 89 Explanation:
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^{10} = (100*99*98*97*96*95*94*93*92*91)/100^{10}
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^{10}
= 0.34(approximately)
Probability of no collision for first 10 entries =100_{ P10 }/100^{10} = (100*99*98*97*96*95*94*93*92*91)/100^{10}
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^{10}
= 0.34(approximately)
Question 90 
A complete binary tree with the property K_{ni}>=K_{cn} where K_{n} is n^{th}node value and K_{c} be the value of its child node is called:
B+ tree  
Threaded binary tree  
Heap  
AVL tree 
Question 90 Explanation:
Maxheap 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).
Question 91 
___ is a parameter passing method that waits to evaluate the parameter value until it is used?
Pass by value  
Pass by name  
Pass by reference  
Pass by pointer 
Question 91 Explanation:
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.
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.
Question 92 
Suppose that we have an MxN array ‘A’ in row major order, where the size of the elements is S. Then the location of A[i,j] elements is given by:
A+i*N*S  
A+(i*N+j)*S  
A+(i*N+j*M)*S  
A+(i*M+j*N)*S 
Question 92 Explanation:
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)]
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)]
Question 93 
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 
Question 93 Explanation:
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
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
Question 94 
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 
Question 94 Explanation:
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
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
Question 95 
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 is7  
6  
3  
5 
Question 95 Explanation:
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
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
Question 96 
Consider the singly linked list. What is the worst case time complexity of the bestknown 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 96 Explanation:
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);
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);
Question 97 
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 
Question 97 Explanation:
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 * 
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 1+8=9
 6 stack contains 9 6
 8, now stack contains 9. 6 ,8
 * so 6*8=48, so stack contains 9,48
Question 98 
The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a maxheap. The resultant maxheap 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> 
Question 98 Explanation:
Given sequence 42, 25, 30, 40, 22, 35, 26
resultant maxheap is stored in an array = 42, 40, 35, 25, 22, 30, 26
Question 99 
In a binary max heap containing n numbers, the smallest element can be found in time
O(n)  
O(logn)  
O(loglogn)  
O(A) 
Question 99 Explanation:
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
Question 100 
In a binary max heap containing n numbers, the smallest element can be found in time
O(n)  
O(logn)  
O(loglogn)  
O(A) 
Question 100 Explanation:
Click this link for explanation : https://academyera.com/nielitsta2016march2016heaptree2
Question 101 
Consider the following minimax game tree search
What will be the value propagated at the root ?
6  
3  
5  
4 
Question 101 Explanation:
Root node wii be 5
Question 102 
Which of the following need not be a binary tree?
Search tree  
Heap  
AVL tree  
B tree 
Question 102 Explanation:
 BTree is known as selfbalancing tree
 BTrees need not be the binary tree
 In BTree the nodes are sorted in inorder traversal Unlike binary tree
 In Btree a node may have more than 2 children.
Question 103 
The maximum number of nodes in a binary tree of level k, k>=1 is:
2 ^{k} +1  
2^{ k1}  
2 ^{k} 1  
2 ^{k1} 1 
Question 103 Explanation:
Maximum number of nodes in a binary tree of level k is 2^{k }1 = 2^{3}1 =7 nodes
Question 104 
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
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 
Question 104 Explanation:
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^{2})
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^{2})
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^{2})
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^{2})
Question 105 
What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms?
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 
Question 105 Explanation:
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 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
Question 106 
In a given following graph among the following sequences:
i) abeghf
ii) abfehg
iii) abfhge
iv) afghbe
Which are depth first traversals of the above graph?
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 
Question 106 Explanation:
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.
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.
Question 107 
If the sequence of operations – push (1), push (2), pop, push (1), push (2), pop, pop, pop, push (2), pop are performed on a stack, the sequence of popped out values
2,2,1,1,2  
2,2,1,2,2  
2,1,2,2,1  
2,1,2,2,2 
Question 107 Explanation:
push means inserting the element into stack and pop means delete the element in stack
Given
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
Question 108 
A hash table with 10 buckets with one slot per bucket is depicted here. The symbols, S1 to s7 are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is
4  
5  
6  
3 
Question 108 Explanation:
Click this link for explanation already solved : https://academyera.com/isro2018hashing2
Question 109 
The queue data structure is to be realized by using stack. The number of stacks needed would be
It cannot be implemented  
2 stacks  
4 stacks  
1 stack 
Question 109 Explanation:
We can implement queue using 2 stacks
Queue fallows first in first out manner (FIFO)
Stack fallows Last in first out manner (LIFO)
Queue fallows first in first out manner (FIFO)
Stack fallows Last in first out manner (LIFO)
Question 110 
Considering 0address 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
PUSH 15, PUSH 4, PUSH 6, MULT, PUSH 30, ADD, ADD
30  
69  
54  
10 
Question 110 Explanation:
Accumulator implicitly treated as the topofstack 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 0address 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
Question 111 
Which of the following data structures is used in level order traversal of a binary tree?
Skip list  
Stack  
Array  
Queue 
Question 111 Explanation:
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
So BFS Uses Queue as the data structure while DFS uses stack
Question 112 
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is
2 ^{h}  
2 ^{h1} 1  
2^{ h+1} 1  
2 ^{h+1} 
Question 112 Explanation:
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.
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.
Question 113 
Which of the following is useful in traversing a given graph by breadth first search?
Stack  
Set  
List  
Queue 
Question 113 Explanation:
BFS = QUEUE
DFS = Stack
DFS = Stack
Question 114 
If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations?
O(n), O(n)  
O(n), O(1)  
O(1), O(n)  
O(1), O(1) 
Question 114 Explanation:
We can use circular queue to implement enqueue operations and dequeue operations in O(1) time
Question 115 
The number of possible binary trees with 4 nodes is
12  
13  
14  
15 
Question 115 Explanation:
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
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
Question 116 
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________ ?
2  
4  
3  
5 
Question 116 Explanation:
 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_{2} 31)=5
Question 117 
If for a given binary search tree(BST) the pre order traversal is 41,23,11,31,62,50,73. then which of the following is its postorder traversal?
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 
Question 117 Explanation:
Inorder of BST is in Ascending order
Preorder = 41,23,11,31,62,50,73
Inorder = 11,23,31,41,50,62,73
Draw the BST using Inorder and preorder
Post order : 11,31,23,50,73,62,41
Preorder = 41,23,11,31,62,50,73
Inorder = 11,23,31,41,50,62,73
Draw the BST using Inorder and preorder
41 / \ 23 62 / \ / \ 11 31 50 73
Post order : 11,31,23,50,73,62,41
Question 118 
If x is a one dimensional array, then:
*(x+i) is same as *(&x[i])  
&x[i] is same as x+i1  
*(x+i) is same as *x[i]  
*(x+i) is same as *x+i 
Question 118 Explanation:
*(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])
*(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])
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
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 
Question 119 Explanation:
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
We know that
Number of Nodes with degree 1 = 0
Number of internal nodes(degree 2) =2^{h1 } 1=2^{9}1=511
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
We know that
 A full binary tree of a given Height h has 2^{h}1 nodes
 Internal nodes = leaf nodes1
Number of Nodes with degree 1 = 0
Number of internal nodes(degree 2) =2^{h1 } 1=2^{9}1=511
Question 120 
On a set A={a,b,c,d} a binary operation * is defined as given in the following table.
The relation is:
The relation is:
Commutative but not associative  
Neither commutative nor associative  
Both commutative and associative  
Associative but not commutative 
Question 120 Explanation:
Question 121 
The average search time for hashing with linear probing will be less if the load factor
Is far less than one  
Equals one  
Is far greater than one  
None of the above 
Question 121 Explanation:
Click this link for explanation : https://academyera.com/nielitscientistc2016marchhashing
Question 122 
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 122 Explanation:
45 is not present
Question 123 
In binary search tree which traversal is used for getting ascending order values?
Inorder  
Preorder  
Postorder  
None of the above 
Question 123 Explanation:
Inorder traversal of Binary Search Tree(BST) prints all the keys in Ascending order or Increasing order.
Question 124 
If file size is large and if it is to be accessed randomly then which of the following allocation strategy should be best to use in a system ?
Linked allocation  
Indexed allocation  
Contiguous allocation  
None of the options 
Question 124 Explanation:
There are 3 major methods of storing files on the disks
1) Contiguous allocation
2) Linked allocation
3) Indexed allocation
Contiguous Allocation
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
 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 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
Question 125 
In a full binary tree number of nodes is 63 then the height of the tree is :
2  
4  
3  
6 
Question 125 Explanation:
A Full Binary Tree of height h has 2^{h}1 nodes
2^{h}1 = 63
Apply log on both sides
log_{2 }2^{h}1 = log_{2}63
h= 6
Note : simply use cell(log_{2}n) then you will get the height h
2^{h}1 = 63
Apply log on both sides
log_{2 }2^{h}1 = log_{2}63
h= 6
Note : simply use cell(log_{2}n) then you will get the height h
Question 126 
The 234 tree is a self balancing data structure, which is also called:
24 tree  
B+ tree  
BTree  
None of the options 
Question 126 Explanation:
2–3–4 tree is also called 2–4 tree Tress
It is selfbalancing 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
It is selfbalancing 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
 2node have 1 data element and if internal has 2 children's
 3node have 2 data elements and if internal has 3 children's
 4node have 3 data elements and if internal has 4 children's
Question 127 
The average search time of hashing, with linear probing will be less if the load factor:
Is far less than 1  
Equals 1  
Is far greater than 1  
None of the options 
Question 127 Explanation:
Click this link for explanation : https://academyera.com/nielitscientistc2016marchhashing
Question 128 
Which of the following is illegal declaration in C language?
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"; 
Question 128 Explanation:
Initialization of variable in option(d) is not valid in C
char[] str is a declaration in Java but not in C language.
char[] str is a declaration in Java but not in C language.
Question 129 
The address field of linked list:
Contain address of next node  
May contain null character  
Contain address of next pointer  
Both (A) and (B) 
Question 129 Explanation:
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
1.Address Filed : This field contains address of the next node in linked list
2.Data Filed : This field stores information i.e data
Question 130 
The expression 523*52 will evaluate to 18, if:
'' 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 '*' 
Question 130 Explanation:
5  2 3 *5 2 will give results as 18
If we evaluate the expression as (5(23)) * (52).
 has precedence over * and if it associates from the right.
If we evaluate the expression as (5(23)) * (52).
 has precedence over * and if it associates from the right.
Question 131 
The worst case complexity for searching an element in binary search tree is:
O(lgn)  
O(nlogn)  
O(n^{2})  
O(n) 
Question 131 Explanation:
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
So in worst case searching in binary search tree takes O(n) Time complexity
Question 132 
Which of the following applications may use a stack?
(a) Parenthesis balancing program
(b) Process scheduling operating system
(c) Conversion of infix arithmetic expression to postfix form
(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 132 Explanation:
The answer is option(C)  (a) and (c)
(a) Parenthesis balancing program  stack
(b) Process scheduling operating system  queue
(c) Conversion of infix arithmetic expression to postfix form  stack
(a) Parenthesis balancing program  stack
(b) Process scheduling operating system  queue
(c) Conversion of infix arithmetic expression to postfix form  stack
Question 133 
(i)  
(ii)  
(iii)  
(ii) 
Question 133 Explanation:
By using the stack we can Implement recursion
In Binay Search tree Inorder traversal prints the key in sorted order i.e Ascending order
Scheduling jobs can be implemented using Queue data structure
In Binay Search tree Inorder traversal prints the key in sorted order i.e Ascending order
Scheduling jobs can be implemented using Queue data structure
Question 134 
A binary search tree contains the values 1,2,3,4,5,6,7 and 8. The tree is traverses in preorder and the values are printed out. Which of the following sequences is a valid output?
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 
Question 134 Explanation:
Preorder means Root node, Left subtree, Right subtree
We can construct the BST using option(d) only.
We can construct the BST using option(d) only.
5 / \ 3 7 / \ / \ 1 4 6 8 \ 2
Question 135 
For which of the following tasks, stack is not suitable data structure ?
(a) Binary search in an array
(b) Breadth first search
(c) Implementing function calls
(d) Process scheduling
(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) 
Question 135 Explanation:
Correct option is A = (d) and (d)
(a) Binary search in an array  Stack(Recursion will be used in implementation)
(b) Breadth first search  Queue
(c) Implementing function calls  Stack
(d) Process scheduling  Queue
(a) Binary search in an array  Stack(Recursion will be used in implementation)
(b) Breadth first search  Queue
(c) Implementing function calls  Stack
(d) Process scheduling  Queue
Question 136 
When a circular queue is implemented in an array of the following condition holds when there is only one element in the queue?
Front=rear=null  
Front=Rear!=null  
Front=Rear+1  
Front=Rear1 
Question 136 Explanation:
Discuss this question in discussion forum : https://academyera.com/kvs22122018partbqueuesandstacks8
Question 137 
The elements of the triangular array are stored as a vector in the
A[1,1], A[2,1],A[2,2],A[3,1]A[3,2], A[3,3]..A[n,n]
Assuming that A[1,1] is stored at location 1, addressing function for A[i,j] is given by;
A[1,1], A[2,1],A[2,2],A[3,1]A[3,2], A[3,3]..A[n,n]
Assuming that A[1,1] is stored at location 1, addressing function for A[i,j] is given by;
(i1)/2 +j  
((i1)*i)/2 +j  
(i*i)/2 +j  
(i*j1)/2 
Question 137 Explanation:
Discuss this question in discussion forum : https://academyera.com/kvs22122018partbarrays2
Question 138 
An array is
Probably the most widely used data structure  
A homogeneous structure  
A random access structure  
All of these 
Question 138 Explanation:
option(A) : Probably the most widely used data structure  True
option(B) : A homogeneous structure  True
An array is a homogeneous data structure each elements have same data type in array
option(C) : An array can be accesses randomly  True
Example : A[3], A[8]
option(B) : A homogeneous structure  True
An array is a homogeneous data structure each elements have same data type in array
option(C) : An array can be accesses randomly  True
Example : A[3], A[8]
Question 139 
The figure below represents a
Binary tree  
Recursive tree  
Insert sort  
Unitary tree 
Question 139 Explanation:
In the diagram There is Root node(R) and Left child(A) and Right child(B) it is nothing but binary tree
In Binary Tree each node has at most 2 children which is referred as Left child and Right child
In Binary Tree each node has at most 2 children which is referred as Left child and Right child
Question 140 
An important quantitative measure of the complexity of a binary tree is its__. It also provides a measure of the average depth of all nodes in the tree
Average path length  
Median path length  
Mode path length  
Simple deviation path length 
Question 141 
The following figure is a____ tree after zigzig rotations
Heap  
Bubble  
Splay  
Binary 
Question 141 Explanation:
A splay tree is a selfbalancing binary search tree with the additional property that recently accessed elements are quick to access again.
Splay trees are nothing but Binary Search Trees on which "splaying'' operations are performed.
They are 6 operations in Splay tree
Splay trees are nothing but Binary Search Trees on which "splaying'' operations are performed.
They are 6 operations in Splay tree
 Zig Rotation (Right Rotation)
 Zag Rotation (Left Rotation)
 ZigZag (Zig followed by Zag)
 ZagZig (Zag followed by Zig)
 ZigZig
 ZagZag
Question 142 
Representation of data structure in memory is known as
Recursive  
Abstract data type  
Storage Structure  
File structure 
Question 142 Explanation:
Representation of data structure in memory is known as ADT
ADT know as Abstract data type and it is a class for objects whose behavior is defined by a set of value and a set of operations.
ADT know as Abstract data type and it is a class for objects whose behavior is defined by a set of value and a set of operations.
Question 143 
The largest element of an array index is called its
Lower bound  
Range  
Upper bound  
All of these 
Question 143 Explanation:
largest element of an array index is called its upper bond
smallest element of an array index is called its lowerr bond
consider an array A with n elements = A[n]
A[0,1 , , ,n1]
0 is lower bond
n1 is upper bond
smallest element of an array index is called its lowerr bond
consider an array A with n elements = A[n]
A[0,1 , , ,n1]
0 is lower bond
n1 is upper bond
Question 144 
In the context of visual basic, multiple controls of the same type can be grouped into an array, in the same manner as a collection of data items. Such a grouping is known as
Control array  
Primary array  
Secondary array  
An integer array 
Question 144 Explanation:
A control array is a group of controls that share the same name type and the same event procedures. Adding controls with control arrays uses fewer resources than adding multiple control of same type at design time.
A control array can be created only at design time, and at the very minimum at least one control must belong to it. You create a control array following one of these three methods
A control array can be created only at design time, and at the very minimum at least one control must belong to it. You create a control array following one of these three methods
Question 145 
Which of the following data structures is most suitable for evaluating postfix expressions?
Tree  
Stack  
Linked List  
Queue 
Question 145 Explanation:
For evaluating expressions written in notations like prefix ,infix and postfix. Stack is the most suitable data structure
Question 146 
Remove procedure is implemented using
String  
Queue  
Stack  
Linked list 
Question 146 Explanation:
Remove procedure are implemented using function calls so that we can use stack
Question 147 
For a tree just one node, the root node is the height of a binary tree is defined to zero, if there are 2 levels of nodes, the height is 1 and so on. A binary search tree is built according to the usual rules with the following six key inserted one at a time as given B,I,N,A,R,Y. What is the height of the tree?
5  
2  
3  
4 
Question 147 Explanation:
B,I,N,A,R,Y
B position is 2 in alphabet
I position is 9 in alphabet
N position is 14 in alphabet
A position is 1 in alphabet
R position is 18 in alphabet
Y position is 25 in alphabet
B,I,N,A,R,Y = 2,9,14,1,18,25
Now draw the Binary Search Tress and given height starts with 0
B position is 2 in alphabet
I position is 9 in alphabet
N position is 14 in alphabet
A position is 1 in alphabet
R position is 18 in alphabet
Y position is 25 in alphabet
B,I,N,A,R,Y = 2,9,14,1,18,25
Now draw the Binary Search Tress and given height starts with 0
2  h=0 / \ 1 9  h=1 \ 14  h=2 \ 18  h=3 \ 25  h=4
Question 148 
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 
Question 148 Explanation:
Option(B),Option(C),Option(D) are the steps to inserting a node in the beginning of list
Option(A) is irrelevant to the current scenario
Option(A) is irrelevant to the current scenario
Question 149 
+*/abdef  
a+bd*ef/  
abdef*/+  
a+b*de/f 
Question 149 Explanation:
Expression tree is also a binary tree
In Expression tree internal node represents operators and leaf node represents operands.
Inorder traversal of expression tree produces infix version of given postfix expression
option(d) is Inorder traversal of expression tree
a+b*dc/f
In Expression tree internal node represents operators and leaf node represents operands.
Inorder traversal of expression tree produces infix version of given postfix expression
option(d) is Inorder traversal of expression tree
a+b*dc/f
Question 150 
Consider following Scenario 
The five items : P,Q,R,S and T are inserted into stack A one after other starting from T in reverse order
The stack is popped three times and each element is inserted into another stack B.
Then two elements are deleted from the stack B and pushed back onto the stack A.
What are the topmost elements of stack A and Stack B respectively
The five items : P,Q,R,S and T are inserted into stack A one after other starting from T in reverse order
The stack is popped three times and each element is inserted into another stack B.
Then two elements are deleted from the stack B and pushed back onto the stack A.
What are the topmost elements of stack A and Stack B respectively
Q P  
R P  
R Q  
Q R 
Question 150 Explanation:
Initially Stack is empty
The five items : P,Q,R,S and T are inserted into stack A one after other starting from T in reverse order
Now Stack A Contains T,S,R,Q,P (P is the top the stack)
The stack is popped three times and each element is inserted into another stack B.
Now stack A contains T,S
Now stack B contains P,Q,R
Then two elements are deleted from the stack B and pushed back onto the stack A.
Now Stack B contains P
Now stack A contains T,S,R,Q
The five items : P,Q,R,S and T are inserted into stack A one after other starting from T in reverse order
Now Stack A Contains T,S,R,Q,P (P is the top the stack)
The stack is popped three times and each element is inserted into another stack B.
Now stack A contains T,S
Now stack B contains P,Q,R
Then two elements are deleted from the stack B and pushed back onto the stack A.
Now Stack B contains P
Now stack A contains T,S,R,Q
Question 151 
If the address of A[1][1] and A[2][1] are 1000 and 1010 respectively and each element occupies 2 bytes, then the array has been stored in ____ order
Row major order  
Column major  
Matrix major  
Simple 
Question 151 Explanation:
In a Row major order the elements are stored in adjacent locations constitute a row.
In a Column major order, elements are stored in adjacent locations constitute a column.
In a Column major order, elements are stored in adjacent locations constitute a column.
 a[1][1] is 1000 means First row first element whose address is 1000, second element address is 1002,3rd is 1004 and up to 1008.. number of columns equal to 5
 a[2][1] is 1010 means Second row first address whose address is 1010
Question 152 
If an array is declared as Int a[5]={3,0,1,2}, then values assigned to a[0] and a[4] will be
3,2  
0,2  
3,0  
0,4 
Question 152 Explanation:
int a[5]={3,0,1,2}
a[0] is first element = 3
a[1] is second element = 0
a[2] is third element = 1
a[3] is fourth element = 2
a[4] is fifth element = 0
Array is declared for 5 elements a[5], index from 0 to 4=5 elements
only 4 elements are initialized
So, Fifth default value is 0
Question 153 
Array A[8,15] is sorted in row major order with first element A[1,1] stored at location A_{0}. Assuming that each element of the array is size of size s, element A[i,j] can be accessed at
A_{0} + 15s(i1)+(j1)  
A_{0} + 8s(i1)+(j1)  
A_{0} + 15s(j1)+(i1)  
A_{0} + 8s(j1)+(i1) 
Question 153 Explanation:
Integer array of size M∗N and int size is S Bytes.
M = number of rows
N = number of columns
S=size "s" Bytes
Case 1: If array indices start with 0 (default case)
a[i][j], we are supposed to cross i rows each with elements equal to number of columns and j columns.
Case 2: If array indices start with 1
Coming to the question
Given Row major order
Index starts with 1
Base Address = A_{0}
Size = S
Number of rows "M" =8
Number of columns "N" = 15
A[i,j] = Base address + j* size of array(i1)+(j1)
A[8,15] = A_{0 } + 15 * s(i1)+(j1)
M = number of rows
N = number of columns
S=size "s" Bytes
Case 1: If array indices start with 0 (default case)
a[i][j], we are supposed to cross i rows each with elements equal to number of columns and j columns.
 RMO : &a[i][j] = (i∗n+j) ∗ s + base
 CMO : &a[i][j] = (j∗m+i)∗ s + base
Case 2: If array indices start with 1
 RMO : &a[i][j] = ((i−1)∗n+j−1)∗s + base
 CMO : &a[i][j] = ((j−1)∗m+i−1)∗s + base
Coming to the question
Given Row major order
Index starts with 1
Base Address = A_{0}
Size = S
Number of rows "M" =8
Number of columns "N" = 15
A[i,j] = Base address + j* size of array(i1)+(j1)
A[8,15] = A_{0 } + 15 * s(i1)+(j1)
Question 154 
Consider a single dimension array A[n], which houses two stacks as shown in the figures. A[1] is the bottom of stack A and A[n] is the bottom of stack B
If n_{A} is the number of elements in stack A and n_{B} is the number of elements in stack B then overflow occurs when Push Operation is performed on either stack and
n_{A}=n_{B}  
n_{A}=n_{B}=n  
n_{A}+n_{B}=n  
n_{A}+n_{B}>=n 
Question 154 Explanation:
Given
n_{A} is the number of elements in stack A
n_{B} is the number of elements in stack B
n is the total number of elements in Array
overflow occurs when
Sum of the n_{A }Elements in stack A and n_{B }Elements in stack B equal to total number of elements(n) in array i.e n_{A}+n_{B}=n
n_{A} is the number of elements in stack A
n_{B} is the number of elements in stack B
n is the total number of elements in Array
overflow occurs when
Sum of the n_{A }Elements in stack A and n_{B }Elements in stack B equal to total number of elements(n) in array i.e n_{A}+n_{B}=n
Question 155 
Translation of infix string a+b*cd/e*h to postfix form is
abc*+deh/*  
Ab+c*de/h*  
(a b c*)+(de/h*)  
abc*+de/h* 
Question 155 Explanation:
Infix string a+b*cd/e*h
* / have higher priority then +  in precedence table. If same priority then go for associativity
* / +  are left to right associativity
 a+(b*c)d/e*h
 a+(bc*)d/e*h
 a+(bc*)(d/e)*h
 a+(bc*)(de/)*h
 a+(bc*)((de/)*h)
 a+(bc*)((de/)h*)
 (a) + ((bc*)((de/)h*))
 a(bc*)(de/h*) +
 a(bc*de/h*) +
 abc*de/h*+
Question 156 
Queue is an appropriate data structures for
a) Implementation breadth first search
b) Implementation depth first search
c) Process scheduling
Which of the following is the correct option?
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 
Question 156 Explanation:
a) Implementation breadth first search  Queue
b) Implementation depth first search  Stack
c) Process scheduling  Queue
b) Implementation depth first search  Stack
c) Process scheduling  Queue
Question 157 
A full binary tree with height h has _____ nodes.(Assume leaves at h=0)
2^{h}1  
2^{h}+1  
2^{h+1}1  
2^{h+1}+1 
Question 157 Explanation:
Case 1 : height of the root starts with 0
A full binary tree with height h has 2^{h+1} 1 total number of nodes
Case 2 : height of the root starts with 1
A full binary tree with height h has 2^{h} 1 total number of nodes
A full binary tree with height h has 2^{h+1} 1 total number of nodes
Case 2 : height of the root starts with 1
A full binary tree with height h has 2^{h} 1 total number of nodes
Question 158 
A complete nary tree is one in which every node has 0 or n children. If there are x internal nodes in a complete nary tree, the number of leaves is
(n1)x+1  
(n1)x1  
Nx+1  
Nx1 
Question 158 Explanation:
In nary tree where each node has n children or zero children then following relation holds
L = (n1)*X + 1(root)
Where
L is the number of leaf nodes
X is the number of internal nodes.
+1 is for Root node
L = (n1)*X + 1(root)
Where
L is the number of leaf nodes
X is the number of internal nodes.
+1 is for Root node
Question 159 
Given m and n as pointers to two linked lists, what does the following functions do ?
Void op(node *m, node *n)
{
Node *p=m;
while(P→ next !=null)
{
P=P→ next;
}
P→ next=n;
}
Void op(node *m, node *n)
{
Node *p=m;
while(P→ next !=null)
{
P=P→ next;
}
P→ next=n;
}
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 
Question 159 Explanation:
There are 2 list namely m and n
Initially node p is point to list m
After the end of the While loop
Node p reaches to end of the list m,
Now Node p points to end of the list m
Exit after while Loop (P→ next=n;)
node p is append list n to the end of list m
Initially node p is point to list m
After the end of the While loop
Node p reaches to end of the list m,
Now Node p points to end of the list m
Exit after while Loop (P→ next=n;)
node p is append list n to the end of list m
Question 160 
Given a tree with k nodes, the sum of degrees of all nodes is
2^{k1}  
2*(k1)  
2^{k+1}  
2((k+1) 
Question 160 Explanation:
Tree with k vertices which have k−1 edges.
According to Handshaking lemma
Sum of degrees of all vertices = twice the number of edges = 2E
∴ Sum of degree of all vertices ≤ 2E
where E = k−1
∴ Sum of degree of all vertices ≤ 2*(k1)
According to Handshaking lemma
Sum of degrees of all vertices = twice the number of edges = 2E
∴ Sum of degree of all vertices ≤ 2E
where E = k−1
∴ Sum of degree of all vertices ≤ 2*(k1)
Question 161 
Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ?
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) 
Question 161 Explanation:
If it a sorted array and we want to insert or delete then we have to traverse whole array and check which is the most suitable position so it will take O(n) time.
If it a unsorted array then simple insert at the end of the array, no need to search or compare for suitable position which takes O(1)
If it is a sorted array then end position will tell the maximum or minimum, so finding maximum or minimum will take O(1) time.
If it a unsorted array then finding maximum or minimum element take o(n) because u have to search all the array elements
If it a unsorted array then simple insert at the end of the array, no need to search or compare for suitable position which takes O(1)
If it is a sorted array then end position will tell the maximum or minimum, so finding maximum or minimum will take O(1) time.
If it a unsorted array then finding maximum or minimum element take o(n) because u have to search all the array elements
Question 162 
The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is ________.
A  
B  
F  
G 
Question 162 Explanation:
Question 163 
A  
B  
C  
D 
Question 163 Explanation:
In maxheap parent node > child node
In minheap parent node < child node
In minheap parent node < child node
 Option(A) is not valid max heap because key 8 is greater then key 4
 Option(B) is max heap
 Option(C) is not valid max heap because key 7 is greater then key 1
 Option(D) is not valid max heap because key 7 is greater then key 1 and 10 is > then 3
Question 164 
If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key x is less than _______.
1  
1/n  
1/m  
N/m 
Question 164 Explanation:
This is a Universal Hashing theorem
Question 165 
Which of the following statements is false ?
(A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
(B) Breadthfirst 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 reconstructed uniquely.
(D) Depthfirstsearch can be used to find the connected components of a graph.
(A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
(B) Breadthfirst 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 reconstructed uniquely.
(D) Depthfirstsearch can be used to find the connected components of a graph.
A  
B  
C  
D 
Question 165 Explanation:
 option(A)  TRUE
 option(B)  FALSE
Breadthfirst Search can be used to check connectivity of graphs.  option(C)  TRUE
 option(D)  TRUE
Question 166 
Consider an undirected graph G where selfloops are not allowed.
The vertex set of G is {(i, j)  1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c, d) if a – c ≤ 1 or  b–d ≤ 1.
The number of edges in this graph is:
The vertex set of G is {(i, j)  1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c, d) if a – c ≤ 1 or  b–d ≤ 1.
The number of edges in this graph is:
726  
796  
506  
616 
Question 166 Explanation:
Total number of vertices =12×12=144.
The graph formed by the description contains 4(corner) vertices of degree 3 and 40(external) vertices of degree 5 and 100(remaining) vertices of degree 8
According to sum of the degrees theorem(handshaking lemma) :
Sum of degree of all vertices = twice the number of edges = 2E
Sum of the degrees = 2E
4∗3+40∗5+100∗8=2E
1012=2E
2E=1012
E=1012/2=506
∴E=506
The graph formed by the description contains 4(corner) vertices of degree 3 and 40(external) vertices of degree 5 and 100(remaining) vertices of degree 8
According to sum of the degrees theorem(handshaking lemma) :
Sum of degree of all vertices = twice the number of edges = 2E
Sum of the degrees = 2E
4∗3+40∗5+100∗8=2E
1012=2E
2E=1012
E=1012/2=506
∴E=506
Question 167 
Consider the following statements:
S1: A queue can be implemented using two stacks.
S2: A stack can be implemented using two queues.
Which of the following is correct?
S1: A queue can be implemented using two stacks.
S2: A stack can be implemented using two queues.
Which of the following is correct?
S1 is correct and S 2 is not correct.  
S1 is not correct and S 2 is correct.  
Both S1 and S2 are correct.  
Both S1 and S2 are incorrect. 
Question 167 Explanation:
Minimum 2 Stacks are requires to implement Queue
Minimum 2 Queue are requires to implement Stack
Both statements are true
Minimum 2 Queue are requires to implement Stack
Both statements are true
Question 168 
Consider the following operations performed on a stack of size 5 :
Push (a); Pop() ; Push(b) ; Push(c) ; Pop() ; Push(d); Pop() ; Pop(); Push (e)
Which of the following statements is correct?
Push (a); Pop() ; Push(b) ; Push(c) ; Pop() ; Push(d); Pop() ; Pop(); Push (e)
Which of the following statements is correct?
Underflow occurs  
Stack operations are performed smoothly  
Overflow occurs  
None of the above 
Question 168 Explanation:
Question 169 
Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be
(n/2) 1  
(n/2) +1  
(n–1) / 2  
(n+1) / 2 
Question 169 Explanation:
In the Question they are saying about full binary Tree
Following relation holds in full binary tree
Maximum height in full binary tree will be ( n1/ 2) Root height start with 0
Following relation holds in full binary tree
Maximum height in full binary tree will be ( n1/ 2) Root height start with 0
Question 170 
Which of the following is not an inherent application of stack?
Implementation of recursion  
Evaluation of a postfix expression  
Job scheduling  
Reverse a string 
Question 170 Explanation:
Implementation of recursion  Stack
Evaluation of a postfix expression  Stack
Job scheduling  Queue
Reverse a string  Stack
Evaluation of a postfix expression  Stack
Job scheduling  Queue
Reverse a string  Stack
Question 171 
In how many ways can the string A ∩ B – A ∩ B – A be fully parenthesized to yield an infix expression ?
15  
14  
13  
12 
Question 171 Explanation:
The number of ways to fully parenthesize n operands in expression is given by the Catalan numbers:
(2n)!/(n! * (n+1)!)
Where N =total occurrence of any operand in the expression
Hear n=5
=(2*5)!/(5! * (5+1)!)
=(10)! / (5! * 6!)
=14
(2n)!/(n! * (n+1)!)
Where N =total occurrence of any operand in the expression
Hear n=5
=(2*5)!/(5! * (5+1)!)
=(10)! / (5! * 6!)
=14
Question 172 
The cyclomatic complexity of a flow graph V(G), in terms of predicate nodes is: [Where P is number of predicate nodes in flow graph V(G).]
P + 1  
P – 1  
P – 2  
P + 2 
Question 172 Explanation:
It is set of independent paths through the graph diagram.
The Code complexity of the program evaluated using the following formula
V(G) = E  N + 2
Where
E = No. of edges
N = No. of Nodes
V (G) = P + 1
Where
P = No. of predicate nodes (node which has degree more than one i.e Conditional statement)
The Code complexity of the program evaluated using the following formula
V(G) = E  N + 2
Where
E = No. of edges
N = No. of Nodes
V (G) = P + 1
Where
P = No. of predicate nodes (node which has degree more than one i.e Conditional statement)
Question 173 
A three dimensional array in ‘C’ is declared as int A[x][y][z]. Here, the address of an item at the location A[p][q][r] can be computed as follows (where w is the word length of an integer):
&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 173 Explanation:
For array A of size n×m×p , then address of A[i][j][k] = Base Address + i×m×p+j×p+k.
A[i][j][k] = A + i×m×p + j×p + k.
Where Base address = A
If they specify word length then A[i][j][k] = Base Address + word length( i×m×p+j×p+k.)
Coming to the Question
A[p][q][r] = &A[0][0][0]+ w(y*z*p+z*q+r)
A[i][j][k] = A + i×m×p + j×p + k.
Where Base address = A
If they specify word length then A[i][j][k] = Base Address + word length( i×m×p+j×p+k.)
Coming to the Question
A[p][q][r] = &A[0][0][0]+ w(y*z*p+z*q+r)
Question 174 
The hash function used in double hashing is of the form:
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 
Question 174 Explanation:
Hash function used in double hashing :
(hash1(key) + i * hash2(key)) % SIZE_OF_THE_TABLE
hash1() and hash2() are hash functions
SIZE_OF_THE_TABLE = Size of hash table
increment i value when collision occurs
Coming to Question
H (k, i) = (h _{1} (k) + i h_{ 2} (k)) mod m
option(C) is correct
(hash1(key) + i * hash2(key)) % SIZE_OF_THE_TABLE
hash1() and hash2() are hash functions
SIZE_OF_THE_TABLE = Size of hash table
increment i value when collision occurs
Coming to Question
H (k, i) = (h _{1} (k) + i h_{ 2} (k)) mod m
option(C) is correct
Question 175 
The number of disk pages access in BTree search, where ‘h’ is height, ‘n’ is the number of keys, and ‘t’ is the minimum degree, is:
Θ(log _{n} h*t)  
Θ(log _{t} n*h)  
Θ(log _{h} n)  
Θ(log _{t} n) 
Question 175 Explanation:
Question 176 
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 176 Explanation:
Inorder : Left, ROOT, Right
Inorder : 2 4 3 13 7 6 15 17 20 18 18
Inorder : 2 4 3 13 7 6 15 17 20 18 18
Question 177 
Consider the following statements:
(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) 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) 
Question 177 Explanation:
 (a) Depth first search is used to traverse a rooted tree  True
 (b) Pre, Post, Inorder are used to list the vertices of an ordered rooted tree  True
 (c) Huffman’s algorithm is used to find an optimal binary tree with given weights  True
 (d) Topological sorting provides a labelling such that the parents have larger labels than their children  True
Question 178 
The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The postorder Traversal is __________.
Dbefacg  
Debfagc  
Dbefcga  
Debfgca 
Question 178 Explanation:
Preorder : Root Left Right
Inorder : Left Root Right
Postorder : Left Right Root
Given
Preorder : a b d e c f g
Inorder : d b e a f c g
Inorder : Left Root Right
Postorder : Left Right Root
Given
Preorder : a b d e c f g
Inorder : d b e a f c g
a / \ b c / \ / \ d e f gPostorder : d e b f g c a
Question 179 
Level order Traversal of a rooted Tree can be done by starting from root and performing:
Breadth First Search  
Depth First Search  
Root Search  
Deep Search 
Question 179 Explanation:
Level order traversal of a tree is Breadth First Traversal for the tree.
1 / \ 2 3 / \ 4 5For the above tree Level order traversal is 1 2 3 4 5
Question 180 
How many PUSH and POP operations will be needed to evaluate the following expression by reverse polish notation in a stack machine (A * B) + (C * D/E) ?
4 PUSH and 3 POP instructions  
5 PUSH and 4 POP instructions  
6 PUSH and 2 POP instructions  
5 PUSH and 3 POP instructions 
Question 180 Explanation:
(A ∗ B) + (C ∗ D / E)
Remove brackets/punctuation and convert it into postfix form = AB*CD*E/+
 Push A into stack : Stack = A
 Push B into stack : Stack = A B
 Encounter *
 Pop B from stack : Stack = A
 Pop A from stack : Stack = empty
 Perform A * B. Now push back result to stack = A*B
 Push C into stack : Stack =A*B,C
 Push D into stack : Stack =A*B,C,D
 Encounter *
 Pop D from stack : Stack = A*B,C
 Pop C from stack : Stack = A*B,
 Perform C * D. Now push back result to stack = A*B,C*D
 Push E into stack : Stack =A*B,C*D,E
 POP C*D, E and Push the results
 / ; C*D/E : Stack =A*B,C*D/E,
 POP A*B,C*D/E and Push the results
 + Stack =A*B + C*D/E
Question 181 
Convert the following infix expression into its equivalent postfix expression (A + B^ D) / (E – F) + G
ABD^ + EF – / G+  
ABD + ^EF – / G+  
ABD + ^EF / – G+  
ABD^ + EF / – G+ 
Question 181 Explanation:
Given
Infix expression (A + B ^D)/(E – F)+G
=(A+[BD^])/[EF]+G
=[ABD^+]/[EF]+G
=[ABD^+EF/]+G
=ABD^+EF/G+
Postfix Expression = ABD^+EF/G+
Note :
Infix expression (A + B ^D)/(E – F)+G
=(A+[BD^])/[EF]+G
=[ABD^+]/[EF]+G
=[ABD^+EF/]+G
=ABD^+EF/G+
Postfix Expression = ABD^+EF/G+
Note :
 "()" has higher precedence among all operators
 Next higher precedence is "^"
 Next higher precedence is "/"
 +, have same precedence(left to right associativity)
Question 182 
A full binary tree with n leaves contains
N nodes  
Log _{2} n nodes  
2n –1 nodes  
2^{ n} nodes 
Question 182 Explanation:
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 2n1 nodes
A full binary tree with n leaves contains 2n1 nodes
Question 183 
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 
Question 183 Explanation:
Click this link for explanation : https://academyera.com/ugcnet2018adt
Question 184 
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
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 184 Explanation:
Click this link for explanation : https://academyera.com/ugcnetdecpaper2binarysearchtree2
Question 185 
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 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 
Question 185 Explanation:
Click this link for explanation : https://academyera.com/ugcnet2018paperIIprefixpostfixexpression2
Question 186 
The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a maxheap. The resultant maxheap 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> 
Question 186 Explanation:
Click this link for explanation : https://academyera.com/ugcnet2018paper2heaptree2
Question 187 
Consider the following minimax game tree search
What will be the value propagated at the root ?
6  
3  
5  
4 
Question 187 Explanation:
Root node wii be 5
Question 188 
The minimum number of nodes in a binary tree of depth d (root is at level 0) is
2^{d} – 1  
2^{d + 1} – 1  
D + 1  
D 
Question 188 Explanation:
Minimum number of nodes in a binary tree of height h = h + 1
A binary tree can have maximum 2 children
For Minimum number of nodes consider only 1 node at each level. Hence for the depth of d we need d + 1 nodes.
Proof :
Maximum number of nodes in a binary tree of height h = 2^{h+1} − 1
A binary tree can have maximum 2 children
For Minimum number of nodes consider only 1 node at each level. Hence for the depth of d we need d + 1 nodes.
Proof :
Maximum number of nodes in a binary tree of height h = 2^{h+1} − 1
Question 189 
The efficient data structure to insert/delete a number in a stored set of numbers is
Queue  
Linked list  
Doubly linked list  
Binary tree 
Question 189 Explanation:
Using Double linked list you can easily travel next node and previous node easily i.e Forward and Reversion direction both are possible.
Double linked list is the efficient data structure to insert/delete a number in a stored set of numbers
 In Queue : searchO(n), insertO(1), delete takes O(1) time
 In Double linked list : searchO(n), insertO(1), delete takes O(1) time
 In Linked linked list : searchO(n), insertO(1), delete takes O(n) time
 In Binary Tree : searchO(n), insertO(n), delete takes O(n) time
Question 190 
Linked Lists are not suitable for _____.
Binary Search  
Polynomial Manipulation  
Insertion  
Radix Sort 
Question 190 Explanation:
Linked lists are suitable for Insertion sort, Polynomial manipulation, Radix sort
 In Insertion sort no need to swap just find appropriate place and join the link
 Linked List is a natural solution for polynomial manipulation
 In Radix sort we are placing digits according to same position(unit, tens) into buckets; which can be effectively handled by linked lists.
we can implement binary search using linked list but no use in terms time complexity Because finding mid element alone takes O(n) time.
Question 191 
The worst case time complexity of AVL tree is better in comparison to binary search tree for
Search and Insert Operations  
Search and Delete Operations  
Insert and Delete Operations  
Search, Insert and Delete Operations 
Question 191 Explanation:
AVL trees are always selfbalanced tress with height difference at most 1.
So Search will takes O(logn)
Insertion will takes O(logn)
deletions will takes O(logn)
Where
Binary Search Tree Search will take O(n)
Insertion O(n)
Deletions O(n)
So Search will takes O(logn)
Insertion will takes O(logn)
deletions will takes O(logn)
Where
Binary Search Tree Search will take O(n)
Insertion O(n)
Deletions O(n)
Question 192 
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 maxheap are__________ and __________ respectively. (Root is at level 0).
3, 14  
3, 10  
4, 14  
4, 10 
Question 192 Explanation:
Question 193 
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 ?
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 
Question 193 Explanation:
Already solved click this link for Explanation : https://academyera.com/ugcnet20182hashing3
Question 194 
A binary search tree in which every nonleaf node has nonempty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves :
Cannot have more than 37 nodes  
Has exactly 37 nodes  
Has exactly 35 nodes  
Cannot have more than 35 nodes 
Question 194 Explanation:
A strictly binary tree with N leaves nodes always contains 2N – 1 nodes.
Given N= 19
Total Number of nodes = 2N – 1 nodes
Total Number of nodes = 2(19) – 1 nodes
Total Number of nodes = 37 nodes
Given N= 19
Total Number of nodes = 2N – 1 nodes
Total Number of nodes = 2(19) – 1 nodes
Total Number of nodes = 37 nodes
Question 195 
A 5ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be :
30  
33  
45  
125 
Question 195 Explanation:
In kary tree each node has exactly k children or no children then following relation holds
L = (k1)*n + 1
Where
L is the Number of leaf nodes
n is the Number of internal nodes.
Given
n = 8
k = 5
∴ Number of leaf nodes(L) = (k1)*n + 1= (51) *8 + 1 = 32 + 1 = 33
Note : Printing Mistake in the Question they are asking number of leaf node not left nodes
Where
L is the Number of leaf nodes
n is the Number of internal nodes.
Given
n = 8
k = 5
∴ Number of leaf nodes(L) = (k1)*n + 1= (51) *8 + 1 = 32 + 1 = 33
Note : Printing Mistake in the Question they are asking number of leaf node not left nodes
Question 196 
In which tree, for every node the height of its left subtree and right subtree differ almost by one ?
Binary search tree  
AVL tree  
Threaded Binary Tree  
Complete Binary Tree 
Question 196 Explanation:
AVL tree is a selfbalancing Binary Search Tree (BST) with height difference at most 1 it means the difference between heights of left subtrees and right subtrees can't be more than 1 for all nodes
Question 197 
A hash function f defined as f(key) = key mod 13, with linear probing is used to insert keys 55, 58, 68, 91, 27, 145. What will be the location of 79 ?
1  
2  
3  
4 
Question 197 Explanation:
Given
Hash function = f(key) = key mod 7
insertion order = 55, 58, 68, 91, 27, 145.
Hash function = f(key) = key mod 7
insertion order = 55, 58, 68, 91, 27, 145.
 Insert 55 : 55 mod 7 = 3
 Insert 58 : 58 mod 7 = 6
 Insert 68 : 68 mod 7 = 3 ; collision ; apply liner probing (68+1) mod 7 =4
 Insert 91 : 91 mod 7 = 0
 Insert 27 : 27 mod 7 = 1
 Insert 145 : 145 mod 7 = 2
 Insert 79 : 79 mod 7 = 1; collision ; apply liner probing (79+1) mod 7 =2; again collision so again apply linear probing (79+2) mod 7 =3; collision ;again apply (79+3) mod 7 =4 apply again until get free location i.e 5
Question 198 
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.
Here “__ ” denotes an empty location in the table.
3, 10, 1, 8,___ ,___,___.  
1, 3, 8, 10,___,___,___.  
1,___,3,___, 8,___,10  
3,10,___,___, 8,___,___. 
Question 198 Explanation:
Click this link for explanation : https://academyera.com/ugcnet2018IIhashing
Question 199 
Consider the tree given below
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 
Question 199 Explanation:
Discuss this question Discussion forum : https://academyera.com/ugcnetcs2012decpaper2binarytrees6
Question 200 
Given an empty stack, after performing Push(1), Push(2), Pop, Push(3), Push(4), Pop, Pop, push(5), Pop. what is the value of the top of the stack ?
4  
3  
2  
1 
Question 200 Explanation:
Question 201 
What is the value of the postfix expression ?
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5)
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5)
–3/8  
–8/3  
24  
–24 
Question 201 Explanation:
 Push 8 : Now stack contains 8
 Push 4 : Now stack contains 8,4
 Push 2 : Now stack contains 8,4,2
 Push 5 : Now stack contains 8,4,2,5(5 is top of stack)
 Encounter "+" : pop 2 elements from stack and perform operation(+) on 2 elements and push back the results back to stack. i.e 2+5 = 7 ; Now Stack contains 8,4,7
 Encounter " " : again 47=3 ; Now stack contains 8,3
 Encounter " *" : 8*3=24; finally stack contains 24
Question 202 
If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a nonempty queue ?
Neither of the pointers change  
Only front pointer changes  
Only rear pointer changes  
Both of the pointers changes 
Question 203 
The postfix expression AB + CD – * can be evaluated using a
Stack  
Tree  
Queue  
Linked list 
Question 203 Explanation:
Postfix expression can be evaluated using a stack
 Push the operands into stack
 Whenever you encounter a operator then pop top 2 operands from stack and perform operation and then push results back to the stack
 repeat it unit expression evaluates
Question 204 
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
ABFCDE  
ADBFEC  
ABDECF  
None of the above 
Question 204 Explanation:
Question 205 
A binary search tree is a binary tree :
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 
Question 205 Explanation:
All items in the left subtree are less than root  True
All items in the right subtree are greater than or equal to the root  True
Each subtree is itself a binary search tree  True
All the given statements are true
All items in the right subtree are greater than or equal to the root  True
Each subtree is itself a binary search tree  True
All the given statements are true
Question 206 
Which of the following data structure is linear type ?
Strings  
Lists  
Queues  
All of the above 
Question 206 Explanation:
In Linear Data structure the elements are arranged sequentially or linearly and attached to one another.
Arrays, linked list, stack, queue are the types of a linear data structure.
In NonLinear Data structure the elements are arranged hierarchically or nonlinear manner.
Trees and graphs are the types of a nonlinear data structure.
Arrays, linked list, stack, queue are the types of a linear data structure.
In NonLinear Data structure the elements are arranged hierarchically or nonlinear manner.
Trees and graphs are the types of a nonlinear data structure.
Question 207 
To represent hierarchical relationship between elements, which data structure is suitable ?
Dequeue  
Priority  
Tree  
All of the above 
Question 207 Explanation:
In Linear Data structure the elements are arranged sequentially or linearly and attached to one another.
Arrays, linked list, stack, queue are the types of a linear data structure.
In NonLinear Data structure the elements are arranged hierarchically or nonlinear manner.
Trees and graphs are the types of a nonlinear data structure.
Trees and Graphs are the types of nonlinear data structure.
Tree
It is a nonlinear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parentchild relationship.
Graph
A graph is a nonlinear data structure that has a finite number of vertices and edges, and these edges are used to connect the vertices. The vertices are used to store the data elements, while the edges represent the relationship between the vertices. A graph is used in various realworld problems like telephone networks, circuit networks, social networks like LinkedIn, Facebook. In the case of Facebook, a single user can be considered as a node, and the connection of a user with others is known as edges.
Arrays, linked list, stack, queue are the types of a linear data structure.
In NonLinear Data structure the elements are arranged hierarchically or nonlinear manner.
Trees and graphs are the types of a nonlinear data structure.
Trees and Graphs are the types of nonlinear data structure.
Tree
It is a nonlinear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parentchild relationship.
Graph
A graph is a nonlinear data structure that has a finite number of vertices and edges, and these edges are used to connect the vertices. The vertices are used to store the data elements, while the edges represent the relationship between the vertices. A graph is used in various realworld problems like telephone networks, circuit networks, social networks like LinkedIn, Facebook. In the case of Facebook, a single user can be considered as a node, and the connection of a user with others is known as edges.
Question 208 
Which of the following data structure is Nonlinear type ?
Strings  
Lists  
Stacks  
None of the above 
Question 208 Explanation:
In Linear Data structure the elements are arranged sequentially or linearly and attached to one another.
Arrays, linked list, stack, queue are the types of a linear data structure.
In NonLinear Data structure the elements are arranged hierarchically or nonlinear manner.
Trees and graphs are the types of a nonlinear data structure.
Arrays, linked list, stack, queue are the types of a linear data structure.
In NonLinear Data structure the elements are arranged hierarchically or nonlinear manner.
Trees and graphs are the types of a nonlinear data structure.
Question 209 
Which of the following is a bad example of recursion ?
Factorial  
Fibonacci numbers  
Tower of Hanoi  
Tree traversal 
Question 209 Explanation:
I can classify recursive programs into 3 broad categories: the good, the bad, and the silly. Here are the categories, each with an example:
 THE GOOD : TOWERS OF HANOI
 THE BAD : FIBONACCI NUMBERS
 THE SILLY : FACTORIAL
Question 210 
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
ABFCDE  
ADBFEC  
ABDECF  
ABDCEF 
Question 210 Explanation:
Question 211 
The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to
2^{0} + 2^{1} + ….. 2^{h}  
2^{0} + 2^{1 }+ ….. 2^{h – 1}  
2^{0} + 2^{1} + ….. 2^{h + 1}  
2^{1} + ….. 2^{h + 1} 
Question 211 Explanation:
Height of a tree calculated as Number of edges between root node to lowest descendent node
 In figure 1 for height =1; Total Number of Nodes =3 ; 2^{0} + 2^{1} = 3 nodes
 In figure 2 for height =2; Total Number of Nodes =7 ; 2^{0} + 2^{1} + 2^{2} = 7 nodes
Question 212 
The number of different trees with 8 nodes is
256  
255  
248  
None of these 
Question 212 Explanation:
Given,
n=8
The number of different trees with n nodes can be calculated as 2^{n}n.
=2^{n}n
=2^{8}8
=2568
=248
n=8
The number of different trees with n nodes can be calculated as 2^{n}n.
=2^{n}n
=2^{8}8
=2568
=248
Question 213 
Given a binary tree whose inorder and preorder traversal are given by
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
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 213 Explanation:
In order : E I C F B G D J H K
Preorder : B C E I F D G H J K
Preorder : B C E I F D G H J K
Post order : IEFCGJKHDB
Question 214 
Consider a hash table of size m = 10000 and the hash function h(k) = ⌊m(kA mod 1)'⌋ for A=(√5 – 1)/2 . The location to the key k=123456 is
46  
47  
41  
43 
Question 214 Explanation:
Given data,
size m = 10000
hash function: h(K) = floor [m (K*A mod 1)]
A = ( √(5) – 1)/2
key K = 123456
h(123456) = floor[10000 * (123456 * (√5 − 1) / 2) mod 1]
= floor[10000 * (76300.004115 mod 1)]
= floor[10000 * (.004115)]
= 41.15
= 41
size m = 10000
hash function: h(K) = floor [m (K*A mod 1)]
A = ( √(5) – 1)/2
key K = 123456
h(123456) = floor[10000 * (123456 * (√5 − 1) / 2) mod 1]
= floor[10000 * (76300.004115 mod 1)]
= floor[10000 * (.004115)]
= 41.15
= 41
Question 215 
Consider a hash table of size m = 10000 and the hash function h(k) = ⌊m(kA mod 1)'⌋ for A=(√5 – 1)/2 . The location to the key k=123456 is
46  
47  
41  
43 
Question 215 Explanation:
Given data,
size m = 10000
hash function: h(K) = floor [m (K*A mod 1)]
A = ( √(5) – 1)/2
key K = 123456
h(123456) = floor[10000 * (123456 * (√5 − 1) / 2) mod 1]
= floor[10000 * (76300.004115 mod 1)]
= floor[10000 * (.004115)]
= 41.15
= 41
size m = 10000
hash function: h(K) = floor [m (K*A mod 1)]
A = ( √(5) – 1)/2
key K = 123456
h(123456) = floor[10000 * (123456 * (√5 − 1) / 2) mod 1]
= floor[10000 * (76300.004115 mod 1)]
= floor[10000 * (.004115)]
= 41.15
= 41
Question 216 
When the priority queue is represented by max heap, the insertion and deletion of an element can be performed in (queue containing n elements)
Θ(n) and θ(1) respectively  
Θ(n) and θ(n) respectively  
Θ(1) and θ(1) respectively  
None of the above 
Question 216 Explanation:
In worst case Inserting an Element takes O(logn )
 Insert a new element at the last of the heap and increase the heap size by 1.
 Since it is the last element, so we first give a very large value (infinity) in the case of minheap and a very less value (inf) in the case of maxheap.
 Then we just change the key of the element by using the Increase/Decrease key operation.
 All the steps are constant time taking steps, except the Increase/Decrease key. So it will also take O(log n) time
 For deletion of a particular element first we have to search that element
Question 217 
Given an open address hash table with load factor α < 1, the expected number of probes in a successful search is
At most (1/α) ln ((1–α)/α)  
At most (1/α) ln (1/(1–α))  
At least (1/α) ln (1/(1– α))  
At least (1/α) ln (α/(1– α)) 
Question 217 Explanation:
Theorem 11.6: Given an openaddress 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.
Theorem 11.8: Given an openaddress 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.
Refer : http://www2.hawaii.edu/~nodari/teaching/f15/Notes/Topic06.html
Question 218 
The time complexity to build a heap with a list of n numbers is
O(log n)  
O(n)  
O(n logn)  
O(n^{2}) 
Question 218 Explanation:
Time complexity to build a heap with a list of n numbers is O(n)
Refer this link for more information :
https://stackoverflow.com/questions/9755721/howcanbuildingaheapbeontimecomplexity
Refer this link for more information :
https://stackoverflow.com/questions/9755721/howcanbuildingaheapbeontimecomplexity
Question 219 
The value of postfix expression :
8 3 4 + – 3 8 2 / + * 2 $ 3 + is
8 3 4 + – 3 8 2 / + * 2 $ 3 + is
17  
131  
64  
52 
Question 219 Explanation:
Given,
Postfix expression : 8 3 4 + – 3 8 2 / + * 2 $ 3 + is
Postfix expression : 8 3 4 + – 3 8 2 / + * 2 $ 3 + is
 Push 8,3,4 in a stack (834), 4 is the top of the stack.
 Read operator + and pop top 2 elements from stack and calculate 4+3=7 and push the results 7 into the stack. now the Stack contains (8,7).
 Read operator  and pop top 2 elements from stack and Calculate 87=1 and push the results 1 into the stack. now the Stack contains (1)
 Read 3,8,2 and push(3) push(8) and push(2). Stack is (1,3,8,2)
 Read operator /. and Pop 2 elements operate them and push results back into stack. Stack is (1,3,4).
 Read +. Pop 2 elements operate them and push in stack. Stack is (1,7).
 Read *. Pop 2 elements operate them and push results back to stack. Stack is (7).
 Push 2.Stack is (7,2*).
 Read $, Pop 2 elements operate them and push results back to stack. Stack is (49).
 Push 3 . stack is(49,3).
 Read + and Pop 2 elements and operate them and push results back to stack. now Stack contains (52).
Question 220 
Consider the following statements for priority queue :
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 ?
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 
Question 220 Explanation:
Statement 1 : True
Priority queue is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations operations performed on priority queue according to the priority of elements and result of the operation depends on this ordering.
Statement 2 : True
According to statement S2 there is no bounding of what kind of element a priority queue should have they may also be complex or simply a list of elements, the only thing should be considered is the priority of the elements.
So, both the statements regarding priority queue are correct.
Priority queue is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations operations performed on priority queue according to the priority of elements and result of the operation depends on this ordering.
Statement 2 : True
According to statement S2 there is no bounding of what kind of element a priority queue should have they may also be complex or simply a list of elements, the only thing should be considered is the priority of the elements.
So, both the statements regarding priority queue are correct.
Question 221 
A binary tree with 27 nodes has _______ null branches.
54  
27  
26  
None of the above 
Question 221 Explanation:
A binary tree with n nodes has n+1 null branches. So a binary tree with 27 nodes will have 28 null branches
Question 222 
The time complexity to build a heap of n elements is
O(1)  
O(lgn)  
O(n)  
O(nlgn) 
Question 222 Explanation:
Time complexity to build a heap with a list of n numbers is O(n)
Refer this link for more information :
https://stackoverflow.com/questions/9755721/howcanbuildingaheapbeontimecomplexity
Refer this link for more information :
https://stackoverflow.com/questions/9755721/howcanbuildingaheapbeontimecomplexity
Question 223 
Linear probing suffers from a problem known as
Secondary clustering  
Primary clustering  
Both (A) and (B)  
None of these 
Question 223 Explanation:
 Linear probing suffers from a problem known as Primary clustering
 Hashing several times in one area results in a cluster of occupied spaces in that area. long runs of occupied spaces build up and the average search time increases
Question 224 
Which of the following can be the sequence of nodes examined in binary search tree while searching for key 88 ?
90, 40, 65, 50, 88  
90, 110, 80, 85, 88  
190, 60, 90, 85, 88  
65, 140, 80, 70, 88 
Question 224 Explanation:
In order to find a solution for a question like above, given the data draw a binary search tree for each one of the options. The first item is the root. Any value less than the root will form the left side of the tree and any value greater than the root will form the right side of the tree. When you draw such a tree, if you find no node has a left and right child then such a sequence would be valid. If you find that the tree has a left and right child for any node then that sequence is invalid. If you draw the tree for all the 4 options given in the question you will find that only option C does not have left and right child for any node. So option C is correct
Question 225 
If we have six stack operations pushing and popping each of A, B and C such that push(A) must occur before push(B) which must occur before push(C), then A, C, B is a possible order for the pop operations, since this could be our sequence : push(A), pop(A), push(B), push(C), pop(C), pop(B).
Which one of the following orders could not be the order the pop operations are run, if we are to satisfy the requirements described above ?
Which one of the following orders could not be the order the pop operations are run, if we are to satisfy the requirements described above ?
ABC  
CBA  
BAC  
CAB 
Question 225 Explanation:
Condition : push(A) must occur before push(B) which must occur before push(C)
Possible order A, C, B
Now check all the options :
option(A) : ABC
Correct order followed the condition push(A) occur before push(B) and push(B) occur before
It is also correct because we can implement these sequence without violating the given conditions see the below sequence then you understand why option(B) is correct
option(C) : BAC
Incorrect sequence not possible to implement
Possible order A, C, B
 push(A),
 pop(A),
 push(B),
 push(C),
 pop(C),
 pop(B).
Now check all the options :
option(A) : ABC
Correct order followed the condition push(A) occur before push(B) and push(B) occur before
 push(A),
 pop(A),
 push(B),
 pop(B),
 push(C)
 pop(C),
It is also correct because we can implement these sequence without violating the given conditions see the below sequence then you understand why option(B) is correct
 push(A),
 push(B),
 push(C),
 pop(C),
 pop(B),
 pop(A),
option(C) : BAC
 push(A),
 push(B),
 pop(B),
 pop(A),
 push(C),
 pop(C)
Incorrect sequence not possible to implement
Question 226 
What is the most appropriate data structure to implement a priority queue ?
Heap  
Circular array  
Linked list  
Binary tree 
Question 226 Explanation:
Priority queue can be implemented using an array, a list, a binary search tree or a heap, although the Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list a binary search tree
In a Binary Heap,
priority queue supports following operations.
In a Binary Heap,
 getHighestPriority() operation can be implemented in O(1) time,
 insert() operation can be implemented in O(Logn) time
 deleteHighestPriority() operation can also be implemented in O(Logn) time.
 By using Fibonacci heap, insert() and getHighestPriority() operation can be implemented in O(1) time and deleteHighestPriority() operation can be implemented in O(Logn) time.
priority queue supports following operations.
 insert(item, priority): Inserts an item with given priority.
 getHighestPriority(): Returns the highest priority item.
 deleteHighestPriority(): Removes the highest priority item
Question 227 
In a complete binary tree of n nodes, how far are the two most distant nodes? Assume each edge in the path counts as !
About log_{2}n  
About 2 log_{2}n  
About n log_{2}n  
About 2n 
Question 227 Explanation:
If one node is present at extreme left side of the leaves and other node is present at extreme right side of the leaves ,then these two nodes have to cover up height 2 times. i.e,
From extreme left to root and then from Root to Extreme right .
Height of the binary tree is O(log_{2}n)
= O(log_{2}n) * O(log_{2}n)
=2 * O(log_{2}n)
From extreme left to root and then from Root to Extreme right .
Height of the binary tree is O(log_{2}n)
= O(log_{2}n) * O(log_{2}n)
=2 * O(log_{2}n)
Question 228 
A chained hash table has an array size of 100. What is the maximum number of entries that can be placed in the table ?
100  
200  
10000  
There is no upper limit 
Question 228 Explanation:
There is no limit for the number of entries in a hash table because if there are n entries ( n>1) and m slots (m>1) there is a chance in which two entries with different hash key values.
Question 229 
Recursive functions are executed in a
First in first outorder  
Last in first outorder  
Parallel fashion  
Load balancing 
Question 229 Explanation:
The recursive functions are executed in LIFO order ( Last In First Out ) Because for each function call an entry is created in stack (known as Active Record Instance), and stacks are executed in LIFO manner.
Question 230 
If the number of leaves in a strictly binary tree is an odd number, then what can you say with full conviction about total number of nodes in the tree ?
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. 
Question 230 Explanation:
 A binary tree is a strictly binary tree if each node in the tree is either a leaf node or has exactly two children.
 There is no node with one child. According to its property, a strictly binary tree with n leaf nodes always has 2n1 nodes.
 Let us consider n to be an odd number and give it a value of 3. So, the number of nodes in the tree would be 2n  1 which is 2 * 3 1 = 5. So that is also an odd number
Question 231 
At a hill station, the parking lot is one long driveway snaking up a hill side. Cars drive in and park right behind the car in front of them, one behind another. A car can’t leave until all the cars in front of it have left. Is the parking lot more like
An array  
A stack  
A queue  
A linked list 
Question 231 Explanation:
Above question clearly follows First in First out(FIFO) principle. So, we are using QUEUE data structure for FIFO condition.
Question 232 
With regard to linked list, which of the following statement is false ?
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 232 Explanation:
Deleting the first element in a singly linked list requires 0(1) operations in the worst case.
Question 233 
A hash function f defined as f(key) = key mod 7, with linear probing used to resolve collisions. Insert the keys 37, 38, 72, 48, 98 and 11 into the table indexed from 0 to 6. What will be the location of 11 ?
3  
4  
5  
6 
Question 233 Explanation:
Given hashing function
f(key) = key mod 7
with linear probing technique
linear_probing(k,i) = (f(key) + i) mod 7
f(key) = key mod 7
with linear probing technique
linear_probing(k,i) = (f(key) + i) mod 7
Question 234 
Consider the following binary search tree:
If we remove the root node, which of the node from the left subtree will be the new root?
If we remove the root node, which of the node from the left subtree will be the new root?
11  
12  
13  
16 
Question 234 Explanation:
Question 235 
If a graph requires k different colours for its proper colouring, then the chromatic number of the graph is
1
 
K
 
K1
 
K/2

Question 235 Explanation:
The chromatic number of a graph is the smallest number of colors needed to color the vertices of so that no two adjacent vertices share the same color and if a graph requires k different colors for its proper coloring, then k is the chromatic number of the graph.
Question 236 
Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation can not be implemented in O(1) time ?
Insertion at the front of the linked list.  
Insertion at the end of the linked list.  
Deletion of the front node of the linked list.  
Deletion of the last node of the linked list. 
Question 236 Explanation:
Option(A) : Insertion at the front of the linked list.
We can implement Insertion at the front of the linked list in O(1) time
We can implement Insertion at the end of the linked list in O(1) time
We can implement Deletion of the front node of the linked list in O(1) time
We can not be implement Deletion of the last node of the linked list in O(1) time but we can implement in O(n) time Because, For deleting last node in the linked list we require address of second last node of the single linked list to make "Null" in it's next pointer. Since we can not access its previous node in singly linked list, So we have to traverse the entire single linked list to get the second last node of single linked list.
We can implement Insertion at the front of the linked list in O(1) time
New_node → Next=Head; Head=New_node;Option(B) : Insertion at the end of the linked list.
We can implement Insertion at the end of the linked list in O(1) time
Tail → Next=New_node; New_node>Next=NULL;Option(C) : Deletion of the front node of the linked list.
We can implement Deletion of the front node of the linked list in O(1) time
Next_node=Head; Head=Next_node → Next; Free(Next_node);Option(D) : Deletion of the last node of the linked list.
We can not be implement Deletion of the last node of the linked list in O(1) time but we can implement in O(n) time Because, For deleting last node in the linked list we require address of second last node of the single linked list to make "Null" in it's next pointer. Since we can not access its previous node in singly linked list, So we have to traverse the entire single linked list to get the second last node of single linked list.
struct node *p,*prev; p=head; while(p) { prev=p; p=p → next; } prev → next=NULL; free(p);
Question 237 
+,,*,a,b,c,d  
A,,b,+,c,*,d  
A,b,c,d,,*,+  
,a,b,+,*,c,d 
Question 237 Explanation:
Postorder traversal of the given binary tree is 4 5 2 6 7 3 1.
Now comparing the sequence with a b – c d * + and making 1to1 correspondence with the sequence 4 5 2 6 7 3 1 , then we get
Now comparing the sequence with a b – c d * + and making 1to1 correspondence with the sequence 4 5 2 6 7 3 1 , then we get
 1 → +
 2 → 
 3 → *
 4 → a
 5 → b
 6 → c
 7 → d
Question 238 
Consider the Inorder and Postorder traversals of a tree as given below :
 Inorder : j e n k o p b f a c l g m d h I
 Postorder : j n o p k e f b c l m g h i d a
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 
Question 239 
The five items P,Q,R,S and T are pushed in a stack, one after the other starting from P. The stack is popped four times and each element is inserted in a queue. Then two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
R  
P  
Q  
S 
Question 239 Explanation:
Renaming
P,Q,R,S and T
as
A,B,C,D, and E
P,Q,R,S and T
as
A,B,C,D, and E
Question 240 
Queues serve major role in
Simulation of recursion
 
Simulation of arbitrary linked list
 
Simulation of limited resources allocation
 
Expression evaluation 
Question 240 Explanation:
 Recursion is implemented by using Stack.
 Simulation of arbitrary linked lists uses linked lists.
 Simulation of resource allocation uses queue as first entered data needs to be given first priority during resource allocation.
 Expression evaluation is implemented by using Stack.
 Simulation of heap sort uses heap data structure.
There are 240 questions to complete.