# Data Structures | Subject Wise Solved Questions

## Data Structures | Subject Wise

 Question 1
Which of the following is application of Breadth First Search on the graph?
 A Finding the diameter of the graph B Finding the bipartite graph C Both (a) and (b) D None of the above
Question 1 Explanation:
• 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
• 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?
 A X→ Bwd→ Fwd = X→ Fwd; X→ Fwd → Bwd = X→ Bwd ; B X→ Bwd.Fwd = X→ Fwd ; X.Fwd→ Bwd = X→ Bwd ; C X.Bwd→ Fwd = X.Bwd ; X→ Fwd.Bwd = X.Bwd ; D 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
 Question 3
If Tree-1 and Tree-2 are the trees indicated below : Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence?
 A Preorder, Postorder B Postorder, Inorder C Postorder, Preorder D Inorder, Preorder E 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
 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 A B B C C D 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?
 A Delete the last element of the list B Delete the first element of the list C Add an element after the last element of the list D 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
 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
 A All zeros B All ones C Both zeros and ones D 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 (vi,vj) according to whether vi and vj  are adjacent or not.
For a simple graph with no self-loops, the adjacency matrix must have 0's on the diagonal. For an undirected graph, the adjacency matrix is symmetric.
 Question 7
Given a binary-max 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?
 A 14,13,8,12,10 B 14,12,13,10,8 C 14,13,12,8,10 D 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 A 4 B 5 C 6 D 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
 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
 A I only B II only C III only D 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.
 Question 10
Which of the following is an illegal array definition?
 A Type COLOGNE : (LIME, PINE, MUSK, MENTHOL); var a : array [COLOGNE] of REAL; B Var a : array [REAL] of REAL; C Var a : array [‘A’…’Z’] of REAL; D 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
 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
 A Both are true B Both are false C First is false and second is true D None of the above
Question 11 Explanation:
→Insertion operation can be performed in 3 ways in a circular linked list. they are listed below
1. Inserting At Beginning of the circular linked list
2. Inserting At End of the circular linked list
3. Inserting At Specific location in the circular linked list
→Deletion operation can be performed in 3 ways in a circular linked list. they are listed below
1. Deleting from Beginning of the circular linked list
2. Deleting from End of the circular linked list
3. Deleting a Specific Node in circular linked list
 Question 12
Which of the following data structure is useful in traversing a given graph by breadth-first search?
 A Stack B List C Queue D None of the above
Question 12 Explanation:
→ Breadth-First Search performs level-order traversal by which using a queue data structure.
→ Depth First Search using a stack data structure.
 Question 13
The number of distinct simple graphs with up to three nodes is
 A 15 B 10 C 7 D 9
Question 13 Explanation:
Assume Vertices are un-labelled. Total number of distinct simple graphs upto 3 nodes in un-labelled graph = 1+2+4=7.
Total number of distinct simple graphs upto 3 nodes in labeled graph = 11
 Question 14
The maximum number of edges in a n-node undirected graph without self loops is
 A N2 B N * (n-1)/2 C N – 1 D (n + 1) * n/2
Question 14 Explanation:
→The graph containing maximum number of edges in a n-node undirected graph without self loops is called complete graph.
→Complete Graph : A Complete Graph is a graph in which every pair of vertices is connected by an edge
→Total number of edges in a complete graph of N vertices = ( n * ( n – 1 ) ) / 2
 Question 15
The best data structure to check whether an arithmetic expression has balanced parenthesis is a
 A Queue B Stack C Tree D 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.
 Question 16
Embedded pointer provides
 A A secondary access path B A physical record key C An inverted index D 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 * +a − bc /− de − +fgh B * +a −bc − /de − +fgh C * +a − bc /− ed + −fgh D * +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
 Question 18
In a doubly linked list, the number of pointers affected for an insertion operation will be
 A 4 B 0 C 1 D 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
 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(k-1)*F(k-2)+F(k-3)
end;
 A 5 B 6 C 7 D 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
 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?
 A b a c B b c a C c a b D 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
 Question 21
The time required to search an element in a linked list of length n is
 A O(log n) B O(n) C O(1) D (n2)
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
 Question 22
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?
 A Deleting a node whose location is given B Searching an unsorted list for a given item C Inserting a node after the node with a given location D 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 back-and-forth in the list during this operation, doubly linked list will be a good help in increasing the efficiency by decreasing the time required for the operation.
 Question 23
The time required to search an element in a linked list of length n is
 A O(log n) B O(n) C O(1) D O(n2)
Question 23 Explanation:
 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
 A Binary search tree B AVL tree C Completely balanced tree D Heap
Question 24 Explanation:
Heap is a complete binary tree. Heaps are of 2 types
1. Min Heap
2. Max Heap
In Min Heap the value of each node is either greater or equal to its parents value and Root having the minimum value
In Max Heap the value of each node is equal or lesser to its parents value and Root having the maximum value
 Question 25
The minimum number of fields with each node of doubly linked list is
 A 1 B 2 C 3 D 4
Question 25 Explanation:
→In doubly linked list the minimum number of fields in a single node are 3
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 A+B−C∗D B +A∗−BCD C ABC−D∗+ 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
 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
 A 6,1 B 5,7 C 3,2 D 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 * –
• 8 is operand So, push 8 to stack, Now stack contains 8
• 2 is operand So, push 2 to stack, Now stack contains 8 2
• 3 is operand So, push 3 to stack, Now stack contains 8 2 3
• ^ is operator So, pop 3 and 2 perform operation 2^3=8 and push 8 back to stack, Now stack contains 8 8
• / is operator So, pop 8 and 8 perform operation 8/8=1 and push 1 back to stack, Now stack contains 1
• 2 is operand So, push 2 to stack, Now stack contains 1 2
• 3 is operand So, push 3 to stack, Now stack contains 1 2 3
• * is operator So, pop 3 and 2 perform operation 3*2=6,Push results back to stack, Now stack contains 1 6
So option(A) is correct one
• + pop 1 6 and perform 1+6=7 , Now push 7 back to stack 7
• push 5, stack contains 7,5
• push 1, stack contains 7,5,1
• * pop 1,5 and perform 1*5=5,push 5 back to stack 7,5
• - pop 7,5 and perform 7-5=2,push 2 back to stack 2
 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)?
 A 3 B 4 C 5 D 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
• 37 mod 7 = 2 ; 37 is stored at location 2
• 38 mod 7 = 3 ; 38 is stored at location 3
• 72 mod 7 = 2 ; location 2 is already occupied, so after linear probing 72 is stored in location 4
• 48 mod 7 = 6 ; 48 is stored at location 6
• 98 mod 7 = 0 ; 98 is stored at location 0
• 11 mod 7 = 4 ; again collision, so so after linear probing 11 is stored in location 4is stored in location 5
Finally
 Location Key 0 98 1 56 2 37 3 38 4 72 5 11 6 48
Key 11 is stored in location 5
 Question 29
A complete binary tree with n non-leaf nodes contains
 A Log2n nodes B N+1 nodes C 2n nodes D 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 non-leaf node having exactly 2 children's then it contains
n+1 leaf nodes,
2n+1 total number of node ,
(2n+1)  - (n+1) non-leaf nodes
 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?
 A 7 5 1 0 3 2 4 6 8 9 B 0 2 4 3 1 6 5 9 8 7 C 0 1 2 3 4 5 6 7 8 9 D 9 8 6 4 2 3 0 1 5 7
Question 30 Explanation:
In-order 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?
 A A heap can be used but not a balanced binary search tree B A balanced binary search tree can be used but not a heap C Both balanced binary search tree and heap can be used D 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)
 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)?
 A 2 B 3 C 4 D 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
 A Abc x + def ^ ^ − B Abc x + de ^ f ^ − C Ab + c × d − e^f^ D − + a × b c^^ def
Question 33 Explanation:
1.  Add brackets as per precedence and order of evaluation
2.  ^, ×, +, −  high precedence from right to left
3. +, −, × are left associative and ^ is right associative.
4. Move operators to the right of immediate Parenthesis for postfix.
( (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 is
 A 1267 B 1164 C 1264 D 1169
Question 34 Explanation:
Start address of the element = 49
size of each element = 3
Number of elements =48 if index start from 1(index vaue-1)
Number of elements =49 if index start from 0 (index value)

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

A = 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 A B B C C D D
Question 35 Explanation: Question 36
A full binary tree with n leaves contains:
 A N nodes B Log2 n nodes C 2n-1 D 2n
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 2n-1 nodes( total number of node) • In figure 1 number of leaf nodes =2 ; so, 2n-1 = 2*2-1=Total number of node =3
• In figure 2 number of leaf nodes =4 ; so, 2n-1 = 2*4-1=Total number of node =7
 Question 37
The expression 1 * 2 ^ 3 * 4 ^ 5 * 6 will be evaluated as
 A 3230 B 16230 C 49152 D 173458
Question 37 Explanation:
• ∧ High priority then * +
• ∧ Right Associativity
• +,* left Associativity
Given Expression : 1*2^3*4^5*6
( 1*2^3*4^5*6 )
= 1 * (2^3) * (4^5 ) * 6
=1 * 8 * 1024 * 6
=49152
 Question 38
How many distinct binary search trees can be created out of 4 distinct keys?
 A 5 B 14 C 24 D 35
Question 38 Explanation:
Number of Binary Search trees for n nodes is  calculated by using  = ( 2nCn / (n+1) )

For 4 keys or nodes  = 8C4/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?
 A 0 B 3 C 4 D 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:=2x ;
i:=i+1;
end

What is the value of i at the end of the pseudocode?
 A 4 B 5 C 6 D 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=216 and  i = 5
• During 5th iteration :  x=216  < 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:
 A O(n0.5) B O(n) C O(log n) D O(n log n)
Question 41 Explanation:
Depth of a binary search tree Question 42
The in-order traversal of a tree resulted in FBGADCE. Then the pre-order traversal of that tree would result in
 A FGBDECA B ABFGCDE C BFGCDEA D AFGBDEC
Question 42 Explanation:
In this Question they are not mentioned whether the tree is  Binary tree or Binary Search Tree(BST)
• If it the Binary tree, we can't find Preorder of tree given In-order or Post-order of a tree. For finding any of a traversal out of three traversals (In-order, Preorder, Post-order) we need atleast any two of them.
• If it Binary Search Tree(BST) then it is possible to get pre-order
According the options I assuming it is BST In-order = FBGADCE
Pre-order = ABFGCDE
 Question 43
A symbol table of length 152 is processing 25 entries at any instant. What is occupation density?
 A 0.164 B 127 C 8.06 D 6.08
Question 43 Explanation:
Occupation Density = Number of Entries / Length of Symbol Table
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?
 A 0.164 B 127 C 8.06 D 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
 Question 45
The following steps in a linked list
• p = getnode()
• info (p) = 10
• next (p) = list
• list = p
result in which type of operation?
 A Pop operation in stack B Removal of a node C Inserting a node D Modifying an existing node
Question 45 Explanation:
A node have 2 fields associate with it in single linked list
1. Data : Data field contains the information
2. Next : Next filed contains address of the next node in the sequence which points to the next node
P = get node () :
get node() will create a node then P will point to that newly created node

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

next (p) = list :
 Question 46
Which of the following number of nodes can form a full binary tree?
 A 8 B 15 C 14 D 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 2n-1 nodes( total number of node)
• In figure 1 number of leaf nodes =2 ; so, 2n-1 = 2*2-1=Total number of node =3
• In figure 2 number of leaf nodes =4 ; so, 2n-1 = 2*4-1=Total number of node =7
 Question 47
In an array of 2N elements that is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?
 A 1 B 2 C N/2 D 2N-1
Question 47 Explanation:
• An array is k-ordered array it means that array contains an element which is atmost k positions away from its original position in a sorted array.
• In 2-ordered array it means that array contains an element which is atmost 2 positions away from its original position in a sorted array.
• Maximum No of positions that an element can be from its position if the array is 1-ordered array = 1
 Question 48
Consider the following pseudocode:

x : integer := 1
y : integer := 2
x := x + y
procedure second (P: procedure)
x : integer := 2
P()
procedure first
y : integer := 3
first()
write_integer (x)

What does it print if the language uses dynamic scoping with deep binding?
 A 2 B 3 C 4 D 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?
 A 0 B 1 C 2 D 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?
 A 1200 B 1408 C 33 D 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
So total number of elements = 8 * 11 * 16 = 1408
 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, q, q…..,q.
The front and rear pointers are initialized to point at q . In which position will the ninth element be added?
 A Q B Q C Q D Q
Question 51 Explanation:
In circular queue
• Front = Rear then queue is empty
• (Rear+1) mod n == Front then queue is full
• For enqueue, we increment the REAR pointer and then insert an element
• For dequeue, we increment the FRONT and then remove the element at that position.
1st element inserted at q
2nd element at q
3rd element at q
and so on so 9th element inserted at q
Front and Rear pointers are initialized to point at q Question 52
Consider the following binary search tree T given below: Which node contains the fourth smallest element in T ? A Q B V C W D 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
 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 A B B C C D 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?
 A 0 B 1 C 11 D 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 Question 55
How many different trees are there with four nodes A, B, C and D ?
 A 30 B 60 C 90 D 16
Question 55 Explanation:
Different trees possible for n nodes = nn−2
Given n=4(A,B,C,D)
Different trees possible with 4 nodes =44-2=42=16
 Question 56
Which of the following is NOT represented in a subroutine activation record frame for a stack-based programming language?
 A Values of local variables B Return address C Heap area D 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 :
1. Argument variables passed on the stack
2. Local variables
4. Registers copies modified by the subprogram that need to be restored
Stack is used for static memory allocation and Heap for dynamic memory allocation
 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?
 A Delete the first element of the list B Interchange the first two elements of the list C Delete the last element of the list D Add an element at the end of the list
Question 57 Explanation:
 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 max-heap are and respectively. (Root is at level 0).

 A 3, 14 B 3, 10 C 4, 14 D 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 ?
 A 3 B 4 C 5 D 6
Question 59 Explanation:
Given
Hash function h(key) = key mod 7
Keys  : 44, 45, 79, 55, 91, 18, 63
• h(key) = key mod 7
• h(44) = 44 mod 7 = 2
• h(45) = 45 mod 7 = 3
• h(79) = 79 mod 7 = 2 collision occurred location 2 is filled with 44,So Apply linear probing (79+1) mod 7= 3 is also filled. So, again apply linear probing (79+2) mod 7= 4 So, 79 will occupy 4.
• h(55) = 55 mod 7 = 6
• h(91) = 91 mod 7 = 0
• h(18) = 18 mod 7 = 4   but 4 is occupied by 79 So, Apply linear probing then you get location 5.
• h(63) = 63 mod 7 = 0. but 0 is also occupied by 91 So, Apply linear probing then you get location 1. 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.
 A 3, 10, 1, 8, ___ , ___, ___. B 1, 3, 8, 10, ___, ___, ___. C 1, ___, 3, ___, 8, ___, 10 D 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 Question 61
___ number of leaf nodes in a rooted tree of n nodes, where each node is having 0 or 3 children.
 A N/2 B (2n+1)/3 C (n-1)/n D (n-1)
Question 61 Explanation:

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

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

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

 Question 62
_____ is used to convert from recursive to iterative implementation of an algorithm
 A Array B Tree C Stack D 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:
 A 192 B 190 C 110 D 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 200-8 =192
 Question 64
___ pairs of traversals is not sufficient to build tree
 A Preorder and Inorder B Postorder and Inorder C Postorder and Preorder D None of these
Question 64 Explanation:
Following combination can uniquely identify a binary tree.
1. In-order and Post-order.
2. In-order and Pre-order.
3. In-order and Level-order.
And following will not helpful to uniquely identify a binary tree.
1. Post-order and Pre-order.
2. Post-order and Level-order.
3. Preorder and Level-order.
Note : We can't build a unique Binary tree without In-order
 Question 65
A__ is a linear list in which insertions and deletions are made to from either end of the structure.
 A Circular queue B Priority queue C Stack D Dequeue
Question 65 Explanation:
Deque generally called as double-ended queue Deque is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).
• In Input-restricted deque the deletion can be made from both ends but insertion can be made at one end only.
• In output-restricted deque the insertion can be made at both ends but deletion can be made from one end only.
 Question 66
What data structures is used for depth first traversal of a graph
 A Queue B Stack C List D 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
 A Depth First B Breadth First C Width First D Depth Limited
Question 67 Explanation:
• In depth-first traversal  generally we investigate one child’s descendants before exploring its right siblings.
• In breadth-first traversal generally we explore all nodes at the same depth before moving on to any deeper nodes.
 Question 68
What does the following functions do for a given Linked list with first node as head?
{
return;
}

 A Prints all nodes of linked lists B Prints all nodes of linked list in reverse order C Prints alternate nodes of Linked List D Prints alternate nodes in reverse order
Question 68 Explanation:
Recursive call of function fun1 pushed into top of the stack before entering in to printf statement, hence last recursive call in top of the stack executes printf statement first and then second to last function which is on top of stack is popped and executed and so on.
So it Prints all nodes of linked list in reverse order

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

stack
1. fun1
2. fun1
3. fun1
4. fun1
5. fun1
Now Top of the stack is 5.fun1
5. fun1 point to element 5 and print 5
4. fun1 point to element 5 and print 4
3. fun1 point to element 5 and print 3
2. fun1 point to element 5 and print 2
1. fun1 point to element 5 and print 1
output : 5,4,3,2,1
 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
{
struct node *temp=NULL;
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
if(temp!=NULL)
}
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?
 A 1<-->2<-->4<-->3<-->6<-->5 B 5<-->4<-->3<-->2<-->1<-->6 C 6<-->5<-->4<-->3<-->2<-->1 D 6<-->5<-->4<-->3<-->1<-->2
Question 69 Explanation:
The given code snippet reverses a doubly linked list. In a doubly-linked list, each node has three fields namely data field, previous field, and next field.
The data field holds the data of the current node, the previous field holds the address of the previous node and the next field holds the address of the next node.
In order to reverse a doubly-linked list, we need to swap the previous and the next fields of all the nodes, change the previous field of the head node and the next field of the last node.
• Initially current pointer is pointed to head of the linked list.
• while loop in the program traverses the entire list till end by swapping prev and next pointers of all the nodes.
• After first iteration prev of element 1 points to next of element 1 i.e. element 2 and next of element 1 points to prev of element 1.
• After executing the while loop, the head pointer is pointed to the prev of last element i.e. 6th element. Thus making the last element as first. Hence the whole list now is reversed.
 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
 A Prints binary representation of n in reverse order B Prints binary representation of n C Prints the value of Logn D 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
 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+bxc-d^e^f is
 A abc x+def^^- B abc xde^f^- C ab +c xd -e^f ^ D -+ 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 ^ ^ -
 Question 72
A balance factor in AVL tree is used to check
 A What rotation to make B If all childs nodes are at same level C When the last rotation occurred D 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 Right-Left case. To check whether it is Right Right case or not, compare the newly inserted key with the key in right subtree root.
 Question 73
A full binary tree with n non-leaf nodes contains
 A Log​ 2​ n nodes B N+1 nodes C 2n nodes D 2n+1 nodes
Question 73 Explanation:
Refer this Link : https://academyera.com/isro-cs-2009-binary-trees-2 Figure 2
• A full binary tree with n leaves contains 2n-1 total nodes =2(4)-1=Total number of nodes is 7
• A full binary tree with n non-leaves contains 2n+1 total nodes  =2(3)+1=Total number of nodes is 7
Figure 1
• A full binary tree with n leaves contains 2n-1 total nodes =2(2)-1=Total number of nodes is 3
• A full binary tree with n non-leaves contains 2n+1 total nodes  =2(1)+1=Total number of nodes is 3
 Question 74
A priority queue is implemented as a Max-heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10,8,5,3,2.
Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is
 A 10,8,7,3,2,1,5 B 10,8,7,2,3,1,5 C 10,8,7,1,2,3,5 D 10,8,7,5,3,2,1
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
 A O(logn) B O(n) C O(nlogn) D 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.
 Question 76
In a circularly linked list organization, insertion of a record involves the modification of
 A No pointer B 1 pointer C 2 pointer D 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
 Question 77
The Average search time of hashing, with linear probing will be less if the load factor
 A Is far less than one B Equals one C Is far greater than one D 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
 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 A 6 B 5 C 4 D None
Question 78 Explanation:
 Question 79
In a circularly linked list organization, insertion of a record involves the modification of
 A No pointer B 1 pointer C 2 pointer D 3 pointer
Question 79 Explanation:
 Question 80
The average search time of hashing, with linear probing will be less if the load factor
 A Is far less than one B Equals one C Is far greater than one D None of these
Question 80 Explanation:
 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 A 6 B 5 C 4 D None
Question 81 Explanation:
 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
 A O(n) B O(m+n) C O(n2) D 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(n2)
 Question 83
In a complete k-array, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is
 A Nk B (n-1)k+1 C N(k-1)+1 D N(k-1)
Question 83 Explanation:
Total Number of Nodes= nk+1
where
n= internal nodes
k=k-arry
1=only 1 root node

We know that
Total number of nodes = Internal nodes + leaf nodes
leaf node = Total number of nodes - Internal nodes
=nk+1 - n // Total Number of Nodes= nk+1
=n(k-1)+1
 Question 84
Which among the following algorithm can’t be used with linked list?
 A Binary search B Linear Search C Insertion sort D 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 random-access performance of a linked list makes other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. Since worst case time complexity of Merge Sort is O(nLogn) and Insertion sort is O(n2), merge sort is preferred.
 Question 85
Which among the following algorithm can’t be used with linked list?
 A Binary search B Linear Search C Insertion sort D Merge Sort
Question 85 Explanation:
 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
 A 3 B 4 C 5 D 6
Question 86 Explanation:
 Question 87
Traversing a binary tree first root and then left and right subtree called__ traversal
 A Postorder B Preorder C Inorder D None of these
Question 87 Explanation:
Pre-order   : ROOT NODE,LEFT NODE,RIGHT NODE
In-order     : LEFT NODE,ROOT NODE,RIGHT NODE
Post-order : 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:
 A 5,4,10,8,6,49,31,43,19,17,11 B 4,5,6,8,10,11,19,17,43,31,49 C 4,5,8,10,6,17,31,49,43,19,11 D 5,4,10,8,6,17,31,49,43,19,11
Question 88 Explanation:
Post-order 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
 A 0.45 B 0.5 C 0.3 D 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 /10010 = (100*99*98*97*96*95*94*93*92*91)/10010
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)/10010
= 0.34(approximately)
 Question 90
A complete binary tree with the property Kni>=Kcn where Kn is nthnode value and Kc be the value of its child node is called:
 A B+ tree B Threaded binary tree C Heap D AVL tree
Question 90 Explanation:
Max-heap is a complete binary tree in which Each node(Kc) in a tree has a key which is less than or equal to the key of its parent node(Kn).
 Question 91
___ is a parameter passing method that waits to evaluate the parameter value until it is used?
 A Pass by value B Pass by name C Pass by reference D 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.
 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 A+i*N*S B A+(i*N+j)*S C A+(i*N+j*M)*S D 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)]

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
 A 11 B 12 C 10 D 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
 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.
 A 20, 20 B 3, 20 C 3, 5 D 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
 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 is
 A 7 B 6 C 3 D 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
 Question 96
Consider the singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list ?
 A O(1) B O(lg n) C O(n) D 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;

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 :
 A 6, 3 B 8, 1 C 8, 2 D 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 * -
• 6 is operand So, push 6 to stack, Now stack contains 6
• 2 is operand So, push 2 to stack, Now stack contains 6 2
• 3 is operand So, push 3 to stack, Now stack contains 6 2 3
• *  is operator So, pop 3 and 2 perform operation 2*3=6 and push 6 back to stack, Now stack contains 6 6
• /  so, 6/6 =1,Now stack contains 1
• 4 is operand So, push 4 to stack, Now stack contains 1 4
• 2 is operand So, push 2 to stack, Now stack contains 1 4 2
• * so pop top 2 operands in stack and perform the operation using given operator 2*4=8,, stack=1 8
So option(B) is correct one   stack contains 1 , 8.. below will the continuation
• + , so 1+8=9
• 6 stack contains 9 6
• 8, now stack contains 9. 6 ,8
• * so 6*8=48, so stack contains 9,48
 Question 98
The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as
 A <42, 35, 40, 22, 25, 26, 30> B <42, 35, 40, 22, 25, 30, 26> C <42, 40, 35, 25, 22, 26, 30> D <42, 40, 35, 25, 22, 30, 26>
Question 98 Explanation:
Given sequence 42, 25, 30, 40, 22, 35, 26 resultant max-heap 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
 A O(n) B O(logn) C O(loglogn) D 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
 A O(n) B O(logn) C O(loglogn) D O(A)
Question 100 Explanation:
 Question 101
Consider the following minimax game tree search What will be the value propagated at the root ?
 A 6 B 3 C 5 D 4
Question 101 Explanation:
Root node wii be 5 Question 102
Which of the following need not be a binary tree?
 A Search tree B Heap C AVL tree D B tree
Question 102 Explanation:
• B-Tree is known as self-balancing tree
• B-Trees need not be the binary tree
• In B-Tree the nodes are sorted in in-order traversal Unlike binary tree
• In B-tree a node may have more than 2 children.
 Question 103
The maximum number of nodes in a binary tree of level k, k>=1 is:
 A 2​ k​ +1 B 2​ k-1 C 2​ k​ -1 D 2​ k-1​ -1
Question 103 Explanation: Maximum number of nodes  in a binary tree of level k is  2-1   = 23-1 =7 nodes
 Question 104
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
 A In adjacency list representation, space is saved for sparse graphs. B Deleting a vertex in adjacency list representation is easier than adjacency matrix representation C Adding a vertex in adjacency list representation is easier than adjacency matrix representation. D 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(V2)

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(V2)
 Question 105
What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms?
 A Stack for BFS and Queue for DFS B Queue for BFS and Stack for DFS C Stack for BFS and Stack for DFS D 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
• DFS also called as Depth First Search.
• Depth First Search(DFS) uses the Stack as the data structure and performs 2 stages, 1st 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?
 A I,II and IV only B I and IV only C II,III and IV only D 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.
 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
 A 2,2,1,1,2 B 2,2,1,2,2 C 2,1,2,2,1 D 2,1,2,2,2
Question 107 Explanation:
push means inserting the element into stack and pop means delete the element in stack
Given
• push(1)    : push the element into stack now stack contains 1
• push(2)   : push the element into stack now stack contains 1,2 (2 is the top of the stack)
• pop          :  pop the top element from stack now stack contains 1
• push(1)   :  push the element into stack now stack contains 1,1
• push(2)  :  push the element into stack now stack contains 1,1,2
• pop         : pop the top element from stack now stack contains 1,1
• pop         : pop the top element from stack now stack contains 1
• pop         : Now stack is empty
• push(2) : stack contains 2
• pop        :  Now stack is empty
POP  sequence elements are 2,2,1,1,2
 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 A 4 B 5 C 6 D 3
Question 108 Explanation:
 Question 109
The queue data structure is to be realized by using stack. The number of stacks needed would be
 A It cannot be implemented B 2 stacks C 4 stacks D 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) Question 110
Considering 0-address instructions machine, what will be the top of the stack after executing the following sequence of instructions?
 A 30 B 69 C 54 D 10
Question 110 Explanation:
Accumulator implicitly treated as the top-of-stack location, and for successive load orders to push previously loaded operands down into the stack automatically. Arithmetic orders then operate between the two most recently loaded operands, and leave their result on the stack, so that no address specification is required. These are therefore 0-address instructions and systems which use this arrangement are frequently known as stacking machines. Given
• PUSH 15  : Now stack contains 15
• PUSH 4    : Now stack contains 15,4
• PUSH 6    : Now stack contains 15,4,6(6 is the top of the stack)
• MULT       : POP last 2 operands and perform the operation 4*6=24 , Now stack contains 15,24
• PUSH 30 :  Now stack contains 15,24,30
• ADD          : 24+30=54 ,    Now stack contains 15,54
• ADD          : 15 + 54  =69 Now stack contains 69
 Question 111
Which of the following data structures is used in level order traversal of a binary tree?
 A Skip list B Stack C Array D 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
 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
 A 2​ h B 2​ h-1​ -1 C 2​ h+1​ -1 D 2​ h+1
Question 112 Explanation:
Number of nodes in a binary tree of height h is at least h + 1  and at most 2h+1 -1  where h is the depth of the tree.
Depth of the tree : Maximum number of edges from root to leaf path.
2h+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?
 A Stack B Set C List D Queue
Question 113 Explanation:
BFS = QUEUE
DFS = Stack
 Question 114
If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations?
 A O(n), O(n) B O(n), O(1) C O(1), O(n) D 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
 A 12 B 13 C 14 D 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
 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 _________ ?
 A 2 B 4 C 3 D 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(log2 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?
 A 11,31,23,50,73,62,41 B 31,11,23,50,41,62,73 C 11,31,50,23,73,62,41 D 11,31,23,50,62,73,41
Question 117 Explanation:
In-order of BST is in Ascending order
Pre-order = 41,23,11,31,62,50,73
In-order   = 11,23,31,41,50,62,73
Draw the BST using In-order and pre-order
```                   41
/    \
23     62
/  \    / \
11  31  50  73```

Post order : 11,31,23,50,73,62,41
 Question 118
If x is a one dimensional array, then:
 A *(x+i) is same as *(&x[i]) B &x[i] is same as x+i-1 C *(x+i) is same as *x[i] D *(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 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
 A 512, 0, 511 B 512, 1, 510 C 511, 0, 512 D 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
• Degree 0 is allowed because it is leaf node in Full Binary Tree
• Degree 2 is allowed in Full Binary Tree because it contains Exactly 2 children's which is internal nodes
• Degree 1 is nothing but A node with 1 child is not allowed
So, we can eliminate Option(B) and option(D)

We know that
• A full binary tree of a given Height h has  2h-1 nodes
• Internal nodes = leaf nodes-1
Number of leaf nodes(degree 0)= 2h-1 =29=512
Number of Nodes with degree 1 = 0
Number of internal nodes(degree 2) =2h-1 -1=29-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:
 A Commutative but not associative B Neither commutative nor associative C Both commutative and associative D 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
 A Is far less than one B Equals one C Is far greater than one D None of the above
Question 121 Explanation:
 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?
 A 5 B 4 C 3 D 2
Question 122 Explanation: 45 is not present
 Question 123
In binary search tree which traversal is used for getting ascending order values?
 A Inorder B Preorder C Postorder D 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 ?
 A Linked allocation B Indexed allocation C Contiguous allocation D None of the options
Question 124 Explanation:
There are 3 major methods of storing files on the disks
1) Contiguous 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
• 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 :
 A 2 B 4 C 3 D 6
Question 125 Explanation:
A Full Binary Tree of height h has 2h-1 nodes
2h-1 = 63
Apply log on both sides
log2 2h-1  = log263
h= 6
Note :  simply use cell(log2n) then you will get the height h
 Question 126
The 2-3-4 tree is a self balancing data structure, which is also called:
 A 2-4 tree B B+ tree C B-Tree D None of the options
Question 126 Explanation:
2–3–4 tree is also called 2–4 tree Tress
It is self-balancing data structure that is commonly used to implement dictionaries
2–3–4 means Every node with children's which is internal node in the tree having Either 2 children's or 3 or 4 child nodes
• 2-node have 1 data element and  if internal has 2 children's
• 3-node have 2 data elements and if internal has 3 children's
• 4-node have 3 data elements and if internal has 4 children's Question 127
The average search time of hashing, with linear probing will be less if the load factor:
 A Is far less than 1 B Equals 1 C Is far greater than 1 D None of the options
Question 127 Explanation:
 Question 128
Which of the following is illegal declaration in C language?
 A Char*str="Raj is a research scholar"; B Charstr="Raj is a research Scholar"; C Charstr="Raj is a research Scholar"; D 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.
 Question 129
 A Contain address of next node B May contain null character C Contain address of next pointer D Both (A) and (B)
Question 129 Explanation:
Every node in single linked list contains 2 fields
2.Data Filed : This field stores information i.e data
 Question 130
The expression 5-2-3*5-2 will evaluate to 18, if:
 A '-' is left associative and '*' has precedence over '-' B '-' is right associative and '*' has precedence over '-' C '-' is right associative and '-' has precedence over '*' D '-' 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-(2-3)) * (5-2).
- 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:
 A O(lgn) B O(nlogn) C O(n2) D 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
 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 (a) and (b) B (b) and (c) C (a) and (c) D (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
 Question 133
Given the list of tasks in Col-A and list of data structure in Col-B Identify the best match A (i) B (ii) C (iii) D (ii)
Question 133 Explanation:
By using the stack we can Implement recursion
In Binay Search tree In-order 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?
 A 5 3 1 2 4 7 8 6 B 5 3 1 2 6 4 9 7 C 5 3 2 4 1 6 7 8 D 5 3 1 2 4 7 6 8
Question 134 Explanation:
Pre-order means Root node, Left subtree, Right subtree
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
(c) Implementing function calls
(d) Process scheduling
 A (b) and (d) B (b) and (c) C (a) and (c) D (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
 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?
 A Front=rear=null B Front=Rear!=null C Front=Rear+1 D Front=Rear-1
Question 136 Explanation:
Discuss this question in discussion forum : https://academyera.com/kvs-22-12-2018-part-b-queues-and-stacks-8
 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 (i-1)/2 +j B ((i-1)*i)/2 +j C (i*i)/2 +j D (i*j-1)/2
Question 137 Explanation:
Discuss this question in discussion forum : https://academyera.com/kvs-22-12-2018-part-b-arrays-2
 Question 138
An array is
 A Probably the most widely used data structure B A homogeneous structure C A random access structure D 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, A
 Question 139
The figure below represents a A Binary tree B Recursive tree C Insert sort D 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
 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
 A Average path length B Median path length C Mode path length D Simple deviation path length
Question 140 Explanation:
There are 2 types of path lengths. The Sum of the depths of internal nodes is internal path length and Sum of the depths of external nodes is the external path length Question 141
The following figure is a____ tree after zig-zig rotations A Heap B Bubble C Splay D Binary
Question 141 Explanation:
A splay tree is a self-balancing 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
1. Zig Rotation (Right Rotation)
2. Zag Rotation (Left Rotation)
3. Zig-Zag (Zig followed by Zag)
4. Zag-Zig (Zag followed by Zig)
5. Zig-Zig
6. Zag-Zag
 Question 142
Representation of data structure in memory is known as
 A Recursive B Abstract data type C Storage Structure D 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.
 Question 143
The largest element of an array index is called its
 A Lower bound B Range C Upper bound D 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 , , ,n-1]
0 is lower bond
n-1 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
 A Control array B Primary array C Secondary array D 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
 Question 145
Which of the following data structures is most suitable for evaluating postfix expressions?
 A Tree B Stack C Linked List D 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
 A String B Queue C Stack D 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?
 A 5 B 2 C 3 D 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
```                   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?
 A Obtain a node from available list B Make the next pointer of the current head pointer to new node C Make the node pointer of the list pointer to new node D 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
 Question 149
 A -+*/abdef B a+bd*-ef/ C abdef*/+- D a+b*d-e/f
Question 149 Explanation:
Expression tree is also a binary tree
In Expression tree internal node represents operators and  leaf node represents operands.
In-order traversal of expression tree produces infix version of given postfix expression
option(d) is In-order traversal of expression tree
a+b*d-c/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
 A Q P B R P C R Q D 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 Question 151
If the address of A and A are 1000 and 1010 respectively and each element occupies 2 bytes, then the array has been stored in ____ order
 A Row major order B Column major C Matrix major D 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.
• a 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 is 1010 means Second row first address whose address is 1010
So given Question is Row major order because elements are stored in adjacent locations
 Question 152
If an array is declared as Int a={3,0,1,2}, then values assigned to a and a will be
 A 3,2 B 0,2 C 3,0 D 0,4
Question 152 Explanation:

int a={3,0,1,2}

a is first element = 3
a is second element = 0
a is third element = 1
a is fourth element = 2
a is fifth element = 0

Array is declared for 5 elements a, 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 A0. Assuming that each element of the array is size of size s, element A[i,j] can be accessed at
 A A0 + 15s(i-1)+(j-1) B A0 + 8s(i-1)+(j-1) C A0 + 15s(j-1)+(i-1) D A0 + 8s(j-1)+(i-1)
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

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

• 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
Size = S
Number of rows "M" =8
Number of columns "N" = 15

A[i,j] = Base address + j* size of array(i-1)+(j-1)

A[8,15] = A +   15 * s(i-1)+(j-1)
 Question 154
Consider a single dimension array A[n], which houses two stacks as shown in the figures. A is the bottom of stack A and A[n] is the bottom of stack B If nA is the number of elements in stack A and nB is the number of elements in stack B then overflow occurs when Push Operation is performed on either stack and
 A nA=nB B nA=nB=n C nA+nB=n D nA+nB>=n
Question 154 Explanation:
Given
nA is the number of elements in stack A
nB is the number of elements in stack B
n is the total number of elements in Array

overflow occurs when
Sum of the nA Elements in stack A  and nB Elements in stack B  equal to total number of elements(n) in array i.e nA+nB=n
 Question 155
Translation of infix string a+b*c-d/e*h to postfix form is
 A abc*+deh/*- B Ab+c*de/h*- C (a b c*)+(de/h*-) D abc*+de/h*-
Question 155 Explanation:

Infix string a+b*c-d/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
b) Implementation depth first search
c) Process scheduling
Which of the following is the correct option?
 A A and b B A and c C B and c D A,b and c
Question 156 Explanation:
a) Implementation breadth first search  - 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)
 A 2h-1 B 2h+1 C 2h+1-1 D 2h+1+1
Question 157 Explanation:
Case 1 : height of the root starts with 0
A full binary tree with height h has 2h+1 -1 total number of nodes

Case 2 : height of the root starts with 1
A full binary tree with height h has 2h -1 total number of nodes
 Question 158
A complete n-ary tree is one in which every node has 0 or n children. If there are x internal nodes in a complete n-ary tree, the number of leaves is
 A (n-1)x+1 B (n-1)x-1 C Nx+1 D Nx-1
Question 158 Explanation:
In  n-ary tree where each node has n children or zero children then following relation holds
L = (n-1)*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;
}
 A Always appends list ‘m’ at the end of list ‘n’ B Always appends list ‘n’ at the end of list ‘m’ C Append list ‘m’ at the end of list ‘n’ with possibility of error D 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
 Question 160
Given a tree with k nodes, the sum of degrees of all nodes is
 A 2k-1 B 2*(k-1) C 2k+1 D 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*(k-1)
 Question 161
Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ?
 A Insertion – 0(1), Deletion – 0(1), Maximum – 0(1), Minimum – 0(l) B Insertion – 0(1), Deletion – 0(1), Maximum – 0(n), Minimum – 0(n) C Insertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1) D 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
 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 A B B C F D G
Question 162 Explanation: Question 163
 A A B B C C D D
Question 163 Explanation:
In max-heap parent node > child node
In min-heap 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 _______.
 A 1 B 1/n C 1/m D 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) Breadth-first search cannot be used to find connected components of a graph.
(C) Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely.
(D) Depth-first-search can be used to find the connected components of a graph.
 A A B B C C D D
Question 165 Explanation:
• option(A) - TRUE
• option(B) - FALSE
Breadth-first Search can be used to check connectivity of graphs.
• option(C) - TRUE
• option(D) - TRUE
 Question 166
Consider an undirected graph G where self-loops 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:
 A 726 B 796 C 506 D 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 = 2|E|
4∗3+40∗5+100∗8=2|E|
1012=2|E|
2|E|=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?
 A S1​ is correct and S ​ 2​ is not correct. B S1​ ​ is not correct and S 2​ ​ is correct. C Both S​1 and S​2​ are correct. D Both S​1​ and S​2​ 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
 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?
 A Underflow occurs B Stack operations are performed smoothly C Overflow occurs D 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
 A (n/2) -1 B (n/2) +1 C (n–1) / 2 D (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 ( n-1/ 2) Root height start with 0
 Question 170
Which of the following is not an inherent application of stack?
 A Implementation of recursion B Evaluation of a postfix expression C Job scheduling D Reverse a string
Question 170 Explanation:
Implementation of recursion             - 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 ?
 A 15 B 14 C 13 D 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
 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).]
 A P + 1 B P – 1 C P – 2 D 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)
 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 &A + w(y* z* q + z* p + r) B &A + w(y* z* p + z*q + r) C &A + w(x* y* p + z* q+ r) D &A + 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.

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+ w(y*z*p+z*q+r)
 Question 174
The hash function used in double hashing is of the form:
 A H (k, i) = (h​ 1​ (k) + h​ 2​ (k) + i) mod m B H (k, i) = (h​ 1​ (k) + h​ 2​ (k) - i) mod m C H (k, i) = (h​ 1​ (k) + i h​ 2​ (k)) mod m D 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
 Question 175
The number of disk pages access in B-Tree search, where ‘h’ is height, ‘n’ is the number of keys, and ‘t’ is the minimum degree, is:
 A Θ(log​ n​ h*t) B Θ(log​ t​ n*h) C Θ(log​ h​ n) D Θ(log​ t​ n)
Question 175 Explanation: Question 176
 A 2 3 4 6 7 13 15 17 18 18 20 B 20 18 18 17 15 13 7 6 4 3 2 C 15 13 20 4 7 1718 2 3 6 18 D 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
 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 (a) and (b) B (c) and (d) C (a), (b) and (c) D (a), (b), (c) and (d)
Question 177 Explanation:
• (a) Depth first search is used to traverse a rooted tree - True
• (b) Pre, Post, In-order 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
All the statements are true
 Question 178
The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The post-order Traversal is __________.
 A Dbefacg B Debfagc C Dbefcga D Debfgca
Question 178 Explanation:
Pre-order   : Root Left Right
In-order     : Left Root Right
Post-order : Left  Right Root

Given
Pre-order    :  a b d e c f g
In-order      :   d b e a f c g
```                             a
/   \
b      c
/ \    / \
d   e  f   g```
Post-order  : 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:
 A Breadth First Search B Depth First Search C Root Search D Deep Search
Question 179 Explanation:
Level order traversal of a tree is Breadth First Traversal for the tree.
```            1
/   \
2     3
/ \
4   5```
For 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) ?
 A 4 PUSH and 3 POP instructions B 5 PUSH and 4 POP instructions C 6 PUSH and 2 POP instructions D 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
5 PUSH and 4 POP instructions
 Question 181
Convert the following infix expression into its equivalent postfix expression (A + B^ D) / (E – F) + G
 A ABD^ + EF – / G+ B ABD + ^EF – / G+ C ABD + ^EF / – G+ D 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 :
• "()" 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
 A N nodes B Log​ 2​ n nodes C 2n –1 nodes D 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 2n-1 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.
 A 20 , 20 B 3 ,20 C 3, 5 D 20, 5
Question 183 Explanation:
 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
 A 7 B 6 C 3 D 5
Question 184 Explanation:
 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 :
 A 6, 3 B 8, 1 C 8, 2 D 6, 2
Question 185 Explanation:
 Question 186
The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as
 A <42, 35, 40, 22, 25, 26, 30> B <42, 35, 40, 22, 25, 30, 26> C <42, 40, 35, 25, 22, 26, 30> D <42, 40, 35, 25, 22, 30, 26>
Question 186 Explanation:
 Question 187
Consider the following minimax game tree search What will be the value propagated at the root ?
 A 6 B 3 C 5 D 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
 A 2d – 1 B 2d + 1 – 1 C D + 1 D 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 = 2h+1 − 1
 Question 189
The efficient data structure to insert/delete a number in a stored set of numbers is
 A Queue B Linked list C Doubly linked list D 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                     : search-O(n), insert-O(1), delete takes -O(1) time
• In Double linked list     : search-O(n), insert-O(1), delete takes -O(1) time
• In Linked linked list      : search-O(n), insert-O(1), delete takes -O(n) time
• In Binary Tree               : search-O(n), insert-O(n), delete takes -O(n) time
 Question 190
Linked Lists are not suitable for _____.
 A Binary Search B Polynomial Manipulation C Insertion D Radix Sort
Question 190 Explanation:

• 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.
Linked lists are Not Suitable for Binary search
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
 A Search and Insert Operations B Search and Delete Operations C Insert and Delete Operations D Search, Insert and Delete Operations
Question 191 Explanation:
AVL trees are always self-balanced 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)
 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 max-heap are__________ and __________ respectively. (Root is at level 0).
 A 3, 14 B 3, 10 C 4, 14 D 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 ?
 A 3 B 4 C 5 D 6
Question 193 Explanation:
 Question 194
A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves :
 A Cannot have more than 37 nodes B Has exactly 37 nodes C Has exactly 35 nodes D 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
 Question 195
A 5-ary 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 :
 A 30 B 33 C 45 D 125
Question 195 Explanation:
In k-ary tree each node has exactly k children or no children then following relation holds L = (k-1)*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) = (k-1)*n + 1= (5-1) *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 ?
 A Binary search tree B AVL tree C Threaded Binary Tree D Complete Binary Tree
Question 196 Explanation:
AVL tree is a self-balancing 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 ?
 A 1 B 2 C 3 D 4
Question 197 Explanation:
Given
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.
 A 3, 10, 1, 8,___ ,___,___. B 1, 3, 8, 10,___,___,___. C 1,___,3,___, 8,___,10 D 3,10,___,___, 8,___,___.
Question 198 Explanation:
 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.

 A D & h B C & k C G, b, c, h, i, m D C & h
Question 199 Explanation:
 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 ?
 A 4 B 3 C 2 D 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 –3/8 B –8/3 C 24 D –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 4-7=-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 non-empty queue ?
 A Neither of the pointers change B Only front pointer changes C Only rear pointer changes D Both of the pointers changes
Question 202 Explanation: During an insertion into an non-empty queue only rear pointer will change
 Question 203
The postfix expression AB + CD – * can be evaluated using a
 A Stack B Tree C Queue D Linked list
Question 203 Explanation:
Postfix expression can be evaluated using a stack
1. Push the operands into stack
2. Whenever you encounter a operator then pop top 2 operands from stack and perform operation and then push results back to the stack
3. repeat it unit expression evaluates
 Question 204
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
 A ABFCDE B ADBFEC C ABDECF D None of the above
Question 204 Explanation: Question 205
A binary search tree is a binary tree :
 A All items in the left subtree are less than root B All items in the right subtree are greater than or equal to the root C Each subtree is itself a binary search tree D 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
 Question 206
Which of the following data structure is linear type ?
 A Strings B Lists C Queues D 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 Non-Linear Data structure the elements are arranged hierarchically or non-linear manner.
Trees and graphs are the types of a non-linear data structure.
 Question 207
To represent hierarchical relationship between elements, which data structure is suitable ?
 A Dequeue B Priority C Tree D 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 Non-Linear Data structure the elements are arranged hierarchically or non-linear manner.
Trees and graphs are the types of a non-linear data structure.

Trees and Graphs are the types of non-linear data structure.

Tree
It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parent-child relationship.

Graph
A graph is a non-linear 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 real-world 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 Non-linear type ?
 A Strings B Lists C Stacks D 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 Non-Linear Data structure the elements are arranged hierarchically or non-linear manner.
Trees and graphs are the types of a non-linear data structure.
 Question 209
Which of the following is a bad example of recursion ?
 A Factorial B Fibonacci numbers C Tower of Hanoi D 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.
 A ABFCDE B ADBFEC C ABDECF D 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
 A 20 + 21 + ….. 2h B 20 + 21 + ….. 2h – 1 C 20 + 21 + ….. 2h + 1 D 21 + ….. 2h + 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 ; 20 +  21  = 3 nodes
• In figure 2 for height =2; Total Number of Nodes =7 ; 20 +  21  + 22 = 7 nodes
 Question 212
The number of different trees with 8 nodes is
 A 256 B 255 C 248 D None of these
Question 212 Explanation:
Given,
n=8
The number of different trees with n nodes can be calculated as 2n-n.
=2n-n
=28-8
=256-8
=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
 A I E F C G J K H D B B I E F C J G K H D B C I E F C G K J H D B D 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 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
 A 46 B 47 C 41 D 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
 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
 A 46 B 47 C 41 D 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
 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)
 A Θ(n) and θ(1) respectively B Θ(n) and θ(n) respectively C Θ(1) and θ(1) respectively D 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 min-heap and a very less value (-inf) in the case of max-heap.
• 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
In worst case Deletion of an Element take O(logn )
• 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
 A At most (1/α) ln ((1–α)/α) B At most (1/α) ln (1/(1–α)) C At least (1/α) ln (1/(1– α)) D At least (1/α) ln (α/(1– α))
Question 217 Explanation:
Theorem 11.6: Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.

Theorem 11.8: Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.

Refer : http://www2.hawaii.edu/~nodari/teaching/f15/Notes/Topic-06.html
 Question 218
The time complexity to build a heap with a list of n numbers is
 A O(log n) B O(n) C O(n logn) D O(n2)
Question 218 Explanation:
Time complexity to build a heap with a list of n numbers is O(n)

https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity
 Question 219
The value of postfix expression :
8 3 4 + – 3 8 2 / + * 2 \$ 3 + is
 A 17 B 131 C 64 D 52
Question 219 Explanation:
Given,
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 8-7=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 ?
 A Both S1 and S2 are incorrect. B S1 is correct and S2 is incorrect. C S1 is incorrect and S2 is correct. D 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.
 Question 221
A binary tree with 27 nodes has _______ null branches.
 A 54 B 27 C 26 D 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
 A O(1) B O(lgn) C O(n) D O(nlgn)
Question 222 Explanation:
Time complexity to build a heap with a list of n numbers is O(n)

https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity
 Question 223
Linear probing suffers from a problem known as
 A Secondary clustering B Primary clustering C Both (A) and (B) D 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 ?
 A 90, 40, 65, 50, 88 B 90, 110, 80, 85, 88 C 190, 60, 90, 85, 88 D 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 ?
 A ABC B CBA C BAC D CAB
Question 225 Explanation:
Condition : push(A) must occur before push(B) which must occur before push(C)

Possible order A, C, B
• push(A),
• pop(A),
• push(B),
• push(C),
• pop(C),
• pop(B).
Above order is CORRECT because push(A) occur before push(B) and push(B) occur before push(C)

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),
option(B) : CBA
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),
it is reverse order of ABC sequence in option(A)

option(C) : BAC
• push(A),
• push(B),
• pop(B),
• pop(A),
• push(C),
• pop(C)
option(D) : CAB
Incorrect sequence not possible to implement
 Question 226
What is the most appropriate data structure to implement a priority queue ?
 A Heap B Circular array C Linked list D 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,
• 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 !
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(log2n)
= O(log2n) * O(log2n)
=2 * O(log2n)
 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 ?
 A 100 B 200 C 10000 D 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
 A First in first out-order B Last in first out-order C Parallel fashion D 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 ?
 A It is an odd number. B It is an even number. C It cannot be equal to the number of leaves. D 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 2n-1 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
 A An array B A stack C A queue D 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 ?
 A An algorithm to search for an element in a singly linked list requires 0(n) operations in the worst case. B An algorithm for deleting the first element in a singly linked list requires 0(n) operations in the worst case. C An algorithm for finding the maximum value in a circular linked list requires 0(n) operations. D 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 ?
 A 3 B 4 C 5 D 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 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?
 A 11 B 12 C 13 D 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
 A 1 B K C K-1 D 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 ?
 A Insertion at the front of the linked list. B Insertion at the end of the linked list. C Deletion of the front node of the linked list. D 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
```New_node → Next=Head;
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;
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;
while(p)
{
prev=p;
p=p → next;
}
prev → next=NULL;
free(p);```
 Question 237 If the post order traversal gives ab-cd*+ then the label of the nodes 1,2,3.... will be
 A +,-,*,a,b,c,d B A,-,b,+,c,*,d C A,b,c,d,-,*,+ D -,a,b,+,*,c,d
Question 237 Explanation:
Post-order 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 1-to-1 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 In-order and Post-order traversals of a tree as given below :
• In-order      :  j e n k o p b f a c l g m d h I
• Post-order :  j n o p k e f b c l m g h i d a
The Pre-order traversal of the tree shall be
 A a b f e j k n o p c d g l m h i B a b c d e f j k n o p g l m h i C a b e j k n o p f c d g l m h i D j e n o p k f b c l m g h i d a
Question 238 Explanation:
In-order : j e n k o p b f a c l g m d h i
Post-order: j n o p k e f b c l m g h I d a
Constructing below binary tree using in-order and post-order traversal Pre-order : a b e j k n p o f d g l c m i h
Given key is wrong, None of the options are matching
 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
 A R B P C Q D S
Question 239 Explanation:
Renaming
P,Q,R,S and T
as
A,B,C,D, and E Question 240
Queues serve major role in
 A Simulation of recursion B Simulation of arbitrary linked list C Simulation of limited resources allocation D Expression evaluation
Question 240 Explanation:
• Recursion‏‏‎  is‏‏‎ implemented‏‏‎ by‏‏‎ using‏‏‎ Stack.