DataStructures
Question 1 
Finding the diameter of the graph  
Finding the bipartite graph  
Both (a) and (b)  
None of the above 
Examples
1. Copying garbage collection, Cheney's algorithm
2. Find the diameter of the graph
3. Testing bipartiteness of a graph.
4. Finding the shortest path between two nodes u and v, with path length measured by the number of edges (an advantage over depthfirst search)
5. (Reverse) Cuthill–McKee mesh numbering
6. Ford–Fulkerson method for computing the maximum flow in a flow network
7. Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be reconstructed in an efficient manner.
8. Construction of the failure function of the AhoCorasick pattern matcher.
Question 2 
X→ Bwd→ Fwd = X→ Fwd; X→ Fwd → Bwd = X→ Bwd ;  
X→ Bwd.Fwd = X→ Fwd ; X.Fwd→ Bwd = X→ Bwd ;  
X.Bwd→ Fwd = X.Bwd ; X→ Fwd.Bwd = X.Bwd ;  
X→ Bwd→ Fwd = X→ Bwd ; X→ Fwd→ Bwd = X→ Fwd; 
we need x→ Bwd→ Fwd = x.
Fwd and in order to link z to y, we need x→ Fwd→ Bwd=x→ Bwd.
Question 3 
Which traversals of Tree1 and Tree2, respectively, will produce the same sequence?
Preorder, Postorder  
Postorder, Inorder  
Postorder, Preorder  
Inorder, Preorder 
→ Post order traverses Left, Right, Root.
→ Inorder traverses Left, Root, Right.
Tree1: Post order: GJIHEFBDCA
Tree2: In order: GJIHEFBDCA
Question 4 
A  
B  
C  
D 
Question 5 
Delete the last element of the list  
Delete the first element of the list  
Add an element after the last element of the list  
Interchange the first two elements of the list 
Option B: It needs only the operation F=F→ next
Option C: It needs only the operations L→ next=new node, L = new node
Option D: It needs only the operations T=F, F=F→ next, T→ next =F→ next, F→ next=T
→ All these operations do not depend on the length of the list.
→ Indeed in order to delete the last element from the list, we need to first locate the element before the last (which can not be accessed from L). Thus we must parse all the list from the first and till the element just before the last after which we can delete the last element and assign L to the one before.
Question 6 
all zeros  
all ones  
both zeros and ones  
different 
Question 7 
14,13,8,12,10  
14,12,13,10,8  
14,13,12,8,10  
14,13,12,10,8 
Step2: We have to perform 2 delete operations.
In maxheap (or) minheap by default we are deleting root element only.
After 1st delete, the heap structure is
Step3: After 2nd delete operation, the heap structure is
Question 8 
4  
5  
6  
3 
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum number of comparisons = 4 + 1 = 5
Question 9 
I. P has a local variable
II. P has an execution path where it does not call itself
III. P either refers to a global variable or has at least one parameter
I only  
II only  
III only  
II and III only 
→ P has an execution path where it does not call itself
→ P either refers to a global variable or has at least one parameter
Recursion Rules
Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.
The recursive calls must eventually reach a base case, which is solved without further recursion.
Question 10 
Type COLOGNE : (LIME, PINE, MUSK, MENTHOL); var a : array [COLOGNE] of REAL;  
var a : array [REAL] of REAL;  
var a : array [‘A’…’Z’] of REAL;  
var a : array [BOOLEAN] of REAL; 
Expect the option B, All remaining indexes are not real numbers.
Option A , takes enum value as index which is integer number.
Option C, takes character which is having equivalent decimal value.
Option D, has boolean value as index whose value may be 0 or 1
Question 11 
(i) Insertion of an element should be done at the last node in a circular list
(ii) Deletion of an element should be done at the last node of the circular list
Both are true  
Both are false  
First is false and second is true  
None of the above 
1.Insertion at the front of Circular linked list.
2.Insertion in the middle of the Circular linked list.
3.Insertion at the end of the Circular linked list.
Question 12 
Stack  
List  
Queue  
None of the above 
Question 13 
15  
10  
7  
9 
The number of distinct simple graphs with up to three nodes:
So, total 7 unlabeled nodes are possible. Option (C) is correct.
Question 14 
n_{2}  
n * (n1)/2  
n – 1  
(n + 1) * n/2 
Question 15 
Queue  
Stack  
Tree  
List 
→ While evaluating when left parentheses occur then it pushes into the stack when right parentheses occur pop from the stack. While at the end there is empty in the stack.
Question 16 
A secondary access path  
A physical record key  
An inverted index  
A primary key 
1. To understand how pointers and their associated data elements are allocated in Microsoft RPC, you have to differentiate between toplevel pointers and embedded pointers
2. Toplevel pointers are those that are specified as the names of parameters in function prototypes. Toplevel pointers and their referents are always allocated on the server.
3. Embedded pointers are pointers that are embedded in data structures such as arrays, structures, and unions. When embedded pointers only write output to a buffer and are null on input, the server application can change their values to nonnull. In this case, the client stubs allocate new memory for this data.
4. If the embedded pointer is not null on the client before the call, the stubs do not allocate memory on the client on return. Instead, the stubs attempt to write the memory associated with the embedded pointer into the existing memory on the client associated with that pointer, overwriting the data already there.
Question 17 
* +a − bc /− de − +fgh  
* +a −bc − /de − +fgh  
* +a − bc /− ed + −fgh  
* +ab − c /− ed + −fgh 
Question 18 
4  
0  
1  
None of these 
Note: Excluded for evaluation.
Question 19 
function F(K : integer)
integer;
begin
if (k<3) then F:=k
else F:=F(k1)*F(k2)+F(k3)
end;
5  
6  
7  
8 
F(4) = F(3)*F(2)+F(1) = 5
F(3) = F(2)*F(1)+F(0) = 2
F(2) = 2
F(1) = 1
F(0) = 0
Question 20 
b a c  
b c a  
c a b  
a b c 
Option (A):
Pop a from stack A
Push a to stack B
Print b
Print a from stack B
Print c from stack A
Order = b a c
Option (B):
Pop a from stack A
Push a to stack B
Print b from stack A
Print c from stack A
Print a from stack A
Order = b c a
Option (C):
Pop a from stack A
Push a to stack B
Pop b from stack A
Push b to stack B
Print c from stack A
Now, printing a will not be possible.
Question 21 
O(log n)  
O(n)  
O(1)  
(n^{2}) 
Question 22 
Deleting a node whose location is given  
Searching an unsorted list for a given item  
Inserting a node after the node with a given location  
Traversing the list to process each node 
Inserting the node after the node with the a given location won’t require of traversing the list to previous nodes or memory locations.In this case also, there is no difference between whether it may be linear linked list or doubly linked list.
The main purpose of double linked list is to traverse the list in both directions so Deleting the node becomes easy while traversing the both directions.
Question 23 
O(log n)  
O(n)  
O(1)  
O(n^{2}) 
Question 24 
binary search tree  
AVL tree  
completely balanced tree  
Heap 
Question 25 
1  
2  
3  
4 
However, each node of doubly linked list can have only 2 fields, i.e., XOR pointer field, and data field. This XOR pointer field can points both previous node and next node, this is the best case with data field. This is called as memory efficient
doubly linked list, Also, if we remove data node from the XOR linked list, then each node of this doubly linked list can have only 1 field, i.e., XOR pointer field. But, this is without data field so, this doubly linked list does not make sense.
Question 26 
A+B−C∗D  
+A∗−BCD  
ABC−D∗+  
A+BC−D∗ 
Given Expression = A + (B – C)* D
Prefix Notation:
A + ( B C) * D
A + (*  B C D)
+ A *  B C D
Question 27 
8 2 3 ^ / 2 3 * + 5 1 * –
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are
6,1  
5,7  
3,2  
1,5 
Rule (1): If the element is a number, Push it into stack.
Rule (2): If the element is an operator, Pop operands from the stack. Evaluate the operator operation and Push the result back into the stack.
Question 28 
3  
4  
5  
6 
Hash function = f(key) = key mod 7
Question 29 
log_{2}n nodes  
n+1 nodes  
2n nodes  
2n+1 nodes 
Note: if two leaves having the same parent are removed from the tree, the number of leaves and nonleaves will decrease by 1 because the parent will be a leaf. That means the difference between them is constant. And for a tree having just one node that difference is 1.
Question 30 
7 5 1 0 3 2 4 6 8 9  
0 2 4 3 1 6 5 9 8 7  
0 1 2 3 4 5 6 7 8 9  
9 8 6 4 2 3 0 1 5 7 
The inorder traversal of BST will gives the elements in the sorted order( ascending order)
Question 31 
I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?
A heap can be used but not a balanced binary search tree  
A balanced binary search tree can be used but not a heap  
Both balanced binary search tree and heap can be used  
Neither balanced search tree nor heap can be used 
A selfbalancing binary search tree containing n items allows the lookup, insertion, and removal of an item in O(log n) worstcase time. Since it’s a self balancing BST, we can easily find out minimum element in O(logn) time which is always the leftmost element.
Question 32 
2  
3  
4  
6 
So, height of the tree is defined maximum distance of a leaf node from the root.The root node is “10” and lead node is “5”.The maximum distance is 3
Question 33 
abc x + def ^ ^ −  
abc x + de ^ f ^ −  
ab + c × d − e^f^  
− + a × b c^^ def 
The operators in the expression are +,x, ^
First we will convert e^f ad ef^ (as highest precedence and right associativity) and later
d ^( e f ^ ) to def^^ and so on , you can find the same thing from the below steps.
The postfix expression:
a + b × c − ( d ^( e ^ f))
a + b × c − ( d ^( e f ^ ))
a + b × c − ( d e f ^ ^)
(a + (b × c)) − d e f ^ ^
(a + (b c x)) − d e f ^ ^
(a (b c x) +) − d e f ^ ^
(a b c x +)  (d e f ^ ^)
(a b c x +)  (d e f ^ ^)
a b c x + d e f ^ ^ 
Question 34 
1267  
1164  
1264  
1169 
Base or starting address of the array is 1120.
The address of the 49^{th} element = base address of array + number of elements before current element * size of element
= 1120 + 48 * 3 = 1264
Question 35 
A  
B  
C  
D 
Question 36 
n nodes  
log_{2} n nodes  
2n1  
2^{n} 
Question 37 
3230  
16230  
49152  
173458 
Between * and ^ , operator ‘^’ is highest precedence so it will execute first.
The expression consists of more than one ‘^’ operator is presented then it will follow right to left associativity.
Multiplication operator associativity is left to right.
1 * 2 ^ 3 * 4 ^ 5 * 6 = 1 * (2 ^ 3)* (4 ^ 5) * 6
= 1 * 8 * 1024 * 6
= 49152
Question 38 
5  
14  
24  
35 
So, for 4 distinct nodes, we can have (8C4)/5 = 14 distinct BSTs
Question 39 
0  
3  
4  
None of the above 
According to question, there is no information regarding children nodes of node “A”. So the degree of A is 0.
Question 40 
x:=1;
i:=1;
while (x ≤ 500)
begin
x:=2x ;
i:=i+1;
end
What is the value of i at the end of the pseudocode?
4  
5  
6  
7 
After completion of second iteration x and i values are : x = 4 and i = 3
After completion of third iteration x and i values are : x = 16 and i = 4
After completion of fourth iteration x and i values are : x =256 and i = 5
After completion of fifth iteration x and i values are : x = 65536 and i = 6(Condition is false)
Then the value of “i” is 5
Question 41 
O(n^{0.5})  
O(n)  
O(log n)  
O(n log n) 
The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left subtree, and less than or equal to any key stored in the right subtree.
The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.
The average depth of a binary search tree is log(n)
Question 42 
FGBDECA  
ABFGCDE  
BFGCDEA  
AFGBDEC 
→ Pre order properties are root,left and right
→ Based on the given sequence, we will get binary tree is
→ Based upon the inorder traversal, we will get preorder sequence is ABFGCDE.
Question 43 
0.164  
127  
8.06  
6.08 
Symbol table length=152,
Number of entries=25,
Occupation density=?
Step1: To find Occupation density require number of entries and length of symbol table.
Occupation Density = Number of entries/ Length of symbol table
= 25/152
= 0.164
Question 44 
p = getnode()
info (p) = 10
next (p) = list
list = p
result in which type of operation?
pop operation in stack  
removal of a node  
inserting a node  
modifying an existing node 
info (p) = 10 // Storing the value of 10 into the info field of new node
next (p) = list // adding new node to the existing list.
list=p // the starting address of the list will
point to the new node
Question 45 
8  
15  
14  
13 
Question 46 
1  
2  
N/2  
2N1 
Array=2N elements
Elements are used 2ordered and 3ordered
Step1: If array used 2ordered, if it contains an element which is at most two positions away from its original position in a sorted array.
Sep2: Maximum number of positions that an element can be from its position if the array were
1ordered = 1
Question 47 
2  
3  
4  
5 
The “current” binding for a given name is the one encountered most recently during execution
Dynamic scoping :
The scope of bindings is determined at run time not at Compile time .
→ For deep binding, the referencing environment is bundled with the subroutine as a closure and passed as an argument. A subroutine closure contains
– A pointer to the subroutine code
– The current set of nametoobject bindings
→ By considering dynamic scoping with deep binding when add is passed into second the environment is x = 1, y = 3 and the x is the global x so it writes 4 into the global x, which is the one picked up by the write_integer.
Question 48 
0  
1  
2  
3 
Question 49 
1200  
1408  
33  
1050 
In the given question, Array is represented with lower bound and upper bound.
The following ARRAY statement defines an array containing a total of five elements, a lower bound of 72, and an upper bound of 76. It represents the calendar years 1972 through 1976: array years{72:76} first second third fourth fifth.
The following ARRAY statement arranges the variables in an array by decades. The rows range from 6 through 9, and the columns range from 0 through 9.
array X{6:9,0:9} X60X99.
Question 50 
q[0]  
q[1]  
q[9]  
q[10] 
The front and rear pointers are initialized to point at q[2] which means third element.
First element will add at q[3] , second element will add at q[4] and so on eight element will add at q[10].
Q[10] is the end of the queue which is connected to q[0]
So ninth element can be added at q[0] pointer
Question 51 
Q  
V  
W  
X 
The inorder traversal of the above tree is UQXWPVZY
So the fourth smallest element is 4th element of the inorder which is W
Question 52 
A  
B  
C  
D 
Question 53 
0  
1  
11  
12 
661 mod 13 = 11
182 mod 13 = 0
24 mod 13 = 11, already filled, so after linear probing it will get index 12
103 mod 13 = 12, already filled, so after linear probing it will get index 1
Question 54 
30  
60  
90  
None of the above 
n=4. Here, n is number of nodes.
4^{42}=16.
Given options are wrong options.
Note: Correct answer is 16
Question 55 
Values of local variables  
Return address  
Heap area  
Information needed to access non local variables 
Variables allocated on the stack are stored directly to the memory and access to this memory is very fast, and it's allocation is dealt with when the program is compiled
Variables allocated on the heap have their memory allocated at run time and accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory . Element of the heap have no dependencies with each other and can always be accessed randomly at any time
Question 56 
Delete the first element of the list  
Interchange the first two elements of the list  
Delete the last element of the list  
Add an element at the end of the list 
2. In order to delete first element , change first pointer to the next element.It won’t require length of the linked list.
3. To interchange first two elements also, We need to work with only first two nodes only.Here also no need of length of linked list.
4. To add an element at the last node, we already has one pointer which is pointing to the last node, simple add new node to last node by storing last pointer next address to new node.
5. But in order to delete last node , we need to traverse the entire list , So it requires length of the linked list. By using the last node pointer , we can’t move to previous node in the single linked list.
Question 57 
Consider the array A = 〈4, 1, 3, 2, 16, 9, 10, 14, 8, 7〉. After building heap from the array A, the depth of the heap and the right child of maxheap are and respectively. (Root is at level 0).
3, 14  
3, 10  
4, 14  
4, 10 
Step 1: Since a heap is a almost complete binary tree so build a heap first.
Step 2: Since the above heap is not a max heap so to convert a heap into maxheap start applying maxheapify operation from the largest index parent node (node having 1 or more children).
The above Heap is the maxheap where each root node have maximum value.
Now depth of the Maxheap is 3 and right child of the Root node is 10.
Question 58 
A hash function h defined h(key) = key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?
3  
4  
5  
6 
h(44) = 44 mod 7 ⇒ 2
h(45) = 45 mod 7 ⇒ 3
h(79) = 79 mod 7 ⇒ 2 (collision occurred)
h(79) = (79+1) mod 7 ⇒ 3 (collision occurred)
h(79) = (79+2) mod 7 ⇒ 4
h(55) = 55 mod 7 ⇒ 6
h(91) = 91 mod 7 ⇒ 0
h(18) = 18 mod 7 ⇒ 4 (collision occurred)
h(79) = (18+1) mod 7 ⇒ 5
h(63) = 63 mod 7 ⇒ 0 (collision occurred)
h(63) = (63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations.
Question 59 
Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ?
Here “__” denotes an empty location in the table.
3, 10, 1, 8, ___ , ___, ___.
 
1, 3, 8, 10, ___, ___, ___.
 
1, ___, 3, ___, 8, ___, 10
 
3, 10, ___, ___, 8, ___, ___. 
h(3) = ((7*3)+3) mod 4 = 0
h(8) = ((7*8)+3) mod 4 = 3
h(10) = ((7*10)+3) mod 4 = 1
Question 60 
n/2  
(2n+1)/3  
(n1)/n  
(n1) 
[ Where L is the number of leaf nodes and I is the number of internal nodes]
→ Given data n=3.
L=(31)I +1
=2I +1 > 1
→ To find total number of nodes is nothing but sum of leaf nodes and internal nodes
n=L+I > 2
With the help of 1 and 2, we get L =(2n+1)/3/
Question 61 
Array  
Tree  
Stack  
Queue 
→ Stack to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes.
→ The functions follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls.
→ This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
Question 62 
10 10 +60 6 / * 8  is:
192  
190  
110  
92 
Question 63 
Preorder and Inorder  
Postorder and Inorder  
Postorder and Preorder  
None of these 
Consider two different trees,
TREE1
root=a;
root→ left=b;
root→ left→ right=c;
TREE2
root=a;
root→ right=b;
root→ right→ left=c;
Both the trees are different, but have same preorder and postorder sequence.
preorder  a b c
postorder  c b a
Because we cannot separate the left subtree and right subtree using the preorder or postorder traversal alone
Question 64 
Two stacks are required  
One stack is needed  
Three stacks are required  
More than three stacks are required 
Converting infix expression into post/prefix expression
Evaluating post/prefix expression
Parenthesis matching
With one stack also we can easily evaluate the expression.
Question 65 
1  
2  
3  
4 
push(s,x)
1) Enqueue x to q1 (assuming size of q1 is unlimited). pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
→ Implementing queue by using two stack:
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
Question 66 
4  
8  
16  
32 
Question 67 
Circular queue  
Priority queue  
Stack  
Dequeue 
● What makes a deque different is the unrestrictive nature of adding and removing items.New items can be added at either the front or the rear.
● Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
Question 68 
Queue  
Stack  
List  
None of above 
Question 69 
Depth First  
Breadth First  
Width First  
Depth Limited 
● Breadthfirst search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 70 
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
Prints all nodes of linked lists  
Prints all nodes of linked list in reverse order  
Prints alternate nodes of Linked List  
Prints alternate nodes in reverse order 
Input : Head of following linked list
1>2>3>4>NULL
Output : Linked list should be changed to,
4>3>2>1>NULL
Algorithm:
1. Initialize three pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr>next
// Now change next of current
// This is where actual reversing happens
curr>next = prev
// Move prev and curr one step forward
prev = curr
curr = next
Question 71 
void fun(struct node **head_ref)
{
struct node *temp=NULL;
Struct node *current=*head_ref;
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
if(temp!=NULL)
*head_ref=temp → prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <> 2 <> 3 <> 4<> 5 <> 6. What should be the modified linked list after the function call?
1<>2<>4<>3<>6<>5  
5<>4<>3<>2<>1<>6  
6<>5<>4<>3<>2<>1  
6<>5<>4<>3<>1<>2 
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
The loop meant for traversing the entire list till to end by changing prev and next pointers of all nodes.
Change prev of the head (or start) and change the head pointer in the end.
Question 72 
void fun(int n)
{
Stack s;//Say it creates an empty stack S
while(n>0)
{
// This line pushes the value of n%2 to
Stack S;
Push(&S,n%2);
n=n/2l
}
// Run while Stack S is not empty
while(!is Empty(&S)) Printf(%d",pop(&S));//pop an element from S and print it
}
What does the above function do in general order
Prints binary representation of n in reverse order  
prints binary representation of n  
Prints the value of Logn  
Prints the value of Logn in reverse order 
1) Let us take number 'NUM' and we want to check whether it's 0th bit is ON or OFF
bit = 2 ^ 0 (0th bit)
if NUM & bit == 1 means 0th bit is ON else 0th bit is OFF
2) Similarly if we want to check whether 5th bit is ON or OFF
bit = 2 ^ 5 (5th bit)
if NUM & bit == 1 means its 5th bit is ON else 5th bit is OFF.
Let us take unsigned integer (32 bit), which consist of 031 bits. To print binary representation of unsigned integer, start from 31th bit, check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”. Now check whether 30th bit is ON or OFF, if it is ON print “1” else print “0”, do this for all bits from 31 to 0, finally we will get binary representation of number. void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i > 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
}
Question 73 
abc x+def^^  
abc xde^f^  
ab +c xd e^f ^  
+ a x bc ^^def 
⟶ left to right
Step 1: abc+
Question 74 
What rotation to make  
if all childs nodes are at same level  
when the last rotation occurred  
if the tree is unbalanced 
Question 75 
log _{2} n nodes  
n+1 nodes  
2n nodes  
2n+1 nodes 
● In a binary tree  a tree where each nonleaf node has exactly two sons  number of leaves is n+1. Total number of nodes is 2n+1.
Full Binary Tree:
In the above tree,nonleaf nodes are 7 so total nodes are 2x7+1=15
Question 76 
10,8,7,3,2,1,5  
10,8,7,2,3,1,5  
10,8,7,1,2,3,5  
10,8,7,5,3,2,1 
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 77 
Both operations can be performed in O(1) time 
Question 78 
O(logn)  
O(n)  
O(nlogn)  
O(n ^{2} ) 
Possibility2: If you inserted one after the other then time complexity will be O(nlogn). For one insertion it will take O(logn) because need to apply maxHeapify. For n elements it will be O(nlogn)
Note: We can also insert all the elements once, there will be no difference on time complexity.
But according GATE solution they given possibility1.
Question 79 
O(log _{2} n)  
O(nlog _{2} n)  
O(n) 
Note: If you apply linear search it will take O(logn) and binary search it will take O(loglogn). If you want to insert an element into already created heap is O(logn) because you need to apply maxheapify.
Question 80 
no pointer  
1 pointer  
2 pointer  
3 pointer 
x → next = n1 → next
n1 → next = x
So, we need to modify two pointers only to insert node into the linked list.
Question 81 
is far less than one  
equals one  
is far greater than one  
none of these 
Load factor= n / k
where
● n is the number of entries occupied in the hash table.
● k is the number of buckets.
As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used)
The load factor is the number of keys stored in the hash table divided by the capacity. The size should be chosen so that the load factor is less than 1
Question 82 
6  
5  
4  
3  
None of the above 
Question 83 
O(n)  
O(m+n)  
O(n^2)  
O(mn) 
Question 84 
nk  
(n1)k+1  
n(k1)+1  
n(k1) 
Leaves = total nodes  internal nodes
= nk+1n
= n(k1)+1
Question 85 
Binary search  
Linear Search  
Insertion sort  
Merge Sort 
→ Merge sort is often preferred for sorting a linked list. The slow randomaccess performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
→ Insertion sort & Linear search can use linked list. Note:But Binary search also can implement using linked list but it takes O(n) time complexity.
Question 86 
An array of 50 numbers  
An array of 100 numbers  
An array of 500 numbers  
A dynamically allocated array of 550 numbers 
→ Then using array of 50 numbers is the best way to store the frequencies.
Question 87 
!2n / (!n*!(n+1))  
C(n,2n) (n+1)  
!n*C(2n,n) (n+1)  
C(2n,n)/ !n 
→ Total number of possible Binary Search Trees with n different keys
BST(n)=Cn=(2n)!/(n+1)!*n!
For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ….
So are numbers of Binary Search Trees.
→ Total number of possible Binary Trees with n different keys BT(n)=BST(n)*n!
Question 88 
3  
4  
5  
6 
37%7=2
38%7=3
72%7=2. Here, collision happened because already index 2 is already filled by 37.
According to linear probing, increment index value by 1.
2+1=3 but index 3 also filled with 38 element. So, again increment by 1.
72%7=2( getting index position in hash table 4 )
48%7=6
98%7=0
11%7=4. Here, collision happened because already index 4 is already filled by 72.
According to linear probing, increment index value by 1.
11%7=4 (getting index position in hash table 5 )
56%7=0Here, collision happened because already index 0 is already filled by 98.
According to linear probing, increment index value by 1.
56%7=0 (getting index position in hash table 1 )
Question 89 
postorder  
preorder  
inorder  
none of these 
Pre order: The root node is visited first, then the left subtree and finally the right subtree.
Post order: First we traverse the left subtree, then the right subtree and finally the root node.
Question 90 
5,4,10,8,6,49,31,43,19,17,11  
4,5,6,8,10,11,19,17,43,31,49  
4,5,8,10,6,17,31,49,43,19,11  
5,4,10,8,6,17,31,49,43,19,11 
Post order: 5,4,10,8,6,17,31,49,43,19,11
Question 91 
0.45  
0.5  
0.3  
0.34(approximately) 
So, 1 (100*99*98*97*96*95*94*93*92*91)/100 ^{10} ⇒ 0.37(approximately)
Question 92 
B+ tree  
Threaded binary tree  
Heap  
AVL tree 
Question 93 
Pass by value  
Pass by name  
Pass by reference  
Pass by pointer 
Pass by reference: An alias or reference to the actual parameter is passed to the method.Passing a pointer to the actual parameter, and indirect through the pointer
Pass by name: reevaluate the actual parameter on every use. For actual parameters that are simple variables, this is the same as call by reference. For actual parameters that are expressions, the expression is reevaluated on each access.
There is no parameter passing method with the name “ Pass by pointer”
Question 94 
A+i*N*S  
A+(i*N+j)*S  
A+(i*N+j*M)*S  
A+(i*M+j*N)*S 
M is number of the rows and N is number of Columns and S is size of the element.
The elements are storing row major order. So the elements are in the following order.
A[1,1],A[1,2],A[1,3] ….. A[1,N]
A[2,1],A[2,2],A[2,3]........A[2,N]
……
….
A[M,1],A[M,2],A[M,3]........A[M,N]
We will get the location of A[i,j] by using formula A+(i*N+j)*S where “i” is the index of the row and “j” index of the column and “N” is number of columns.
Question 95 
In a ternary tree, the number of internal nodes of degree 1,2 and 3 is 4,3 and 3 respectively. The number of leaf nodes in the ternary tree is
11  
12  
10  
9 
Number of leaf nodes = Sum of degrees of all internal nodes  number of internal nodes +1
= (4*1 + 3*2 + 3*3 )  10 + 1
= 19  10 + 1
= 10
Formula: nd  n + 1 where n is number of nodes and d is degree of the tree.
Question 96 
An attribute A of data type varchar(20) has the value ‘xyz’ and attribute B of data type char(20) has the value “Imnop” , then the attribute A has ________ spaces and attribute B has ________ spaces.
20, 20
 
3, 20  
3, 5
 
20, 5

→ varchar is a variablelength data type, the storage size of the varchar value is the actual length of the data entered, not the maximum size for this column.
→ So, A varchar(20) has only 3 spaces because its initialized to 'xyz' and B char(20) has 20 spaces as char data type occupies the storage space equivalent to the maximum size.
Question 97 
A binary search tree is constructed by inserting the following numbers in order:
60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34
The number of nodes is the left subtree is
7  
6  
3  
5 
Question 98 
Consider the singly linked list. What is the worst case time complexity of the bestknown algorithm to delete the node a, pointer to this node is q, from the list ?
O(1)  
O(lg n)
 
O(n)  
O(n lg n)

Question 99 
Consider the following postfix expression with single digit operands :
6 2 3 * / 4 2 * + 6 8 * 
The top two elements of the stack after second * is evaluated, are :
6, 3  
8, 1  
8, 2  
6, 2 
While traversing the expression if you find an element value then push it on the top of stack this way the top element of the stack will represent the second operand of an operation and the element presents after top element will represent the first operand of the operation.
While traversing the postfix expression if you find an operation symbol then pop 2 elements from the top of the stack and then after performing operation store it’s result on the top of stack.
Step 1:
Step 2:
Step 3:
Step 4:
So Pop top 2 elements from stack and save the result on the top of stack.
2*3=6
Step 5:
Again Repeat step4.
6/6=1
Step 6:
Step 7:
Step 8:
Do what we did in step4.
4*2 = 8
Question 100 
The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a maxheap. The resultant maxheap is stored in an array implementation as
<42, 35, 40, 22, 25, 26, 30>  
<42, 35, 40, 22, 25, 30, 26>
 
<42, 40, 35, 25, 22, 26, 30>
 
<42, 40, 35, 25, 22, 30, 26> 
The resultant MAX_Heap will look like
<42, 40, 35, 25, 22, 30, 26>
Question 101 
O(n)  
O(logn)  
O(loglogn)  
O(A) 
Question 102 
Simulation of recursion  
Simulation of arbitrary linked list  
Simulation of limited resources allocation  
Expression evaluation 
Question 103 
Consider the following minimax game tree search
What will be the value propagated at the root ?
6  
3  
5  
4 
Question 104 
Search tree  
Heap  
AVL tree  
B tree 
Question 105 
2 ^{k} +1  
2^{ k1}  
2 ^{k} 1  
2 ^{k1} 1 
For example
The minimum number of nodes 2 ^{2} 1=3
Question 106 
In adjacency list representation, space is saved for sparse graphs.  
Deleting a vertex in adjacency list representation is easier than adjacency matrix representation  
Adding a vertex in adjacency list representation is easier than adjacency matrix representation.  
All of the option 
● Uses O(n^{ 2} ) memory
● It fast to lookup and check for presence or absence of a specific edge between any two nodes O(1)
● It slow to iterate over all edges
● It slow to add/delete a node is a complex operation O(n ^{2} )
Adjacency List
● Use memory pending on the number of edges (not number of nodes), Which might save a lot of memory if the adjacency matrix is a sparse
● Finding the presence or absence specific edge between any two nodes Is slightly slower than with the matrix O(k) where k number of neighbors nodes
● It is fast to iterate over all edges,because you can access any node neighbors directly
● It is fast to add/delete a node is easier than the matrix representation
Question 107 
Stack for BFS and Queue for DFS  
Queue for BFS and Stack for DFS  
Stack for BFS and Stack for DFS  
Queue for BFS and Queue for DFS 
● Breadthfirst search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 108 
i)abeghf
ii)abfehg
iii)abfhge
iv)afghbe
Which are depth first traversals of the above graph?
I,II and IV only  
I and IV only  
II,III and IV only  
I,III and IV only 
● Pick a starting node and push all its adjacent nodes into a stack.
● Pop a node from stack to select the next node to visit and push all its adjacent nodes into a stack.
● Repeat this process until the stack is empty. However, ensure that the nodes that are visited are marked.
● This will prevent you from visiting the same node more than once. If you do not mark the nodes that are visited and you visit the same node more than once, you may end up in an infinite loop.
Question 109 
2,2,1,1,2  
2,2,1,2,2  
2,1,2,2,1  
2,1,2,2,2

Final Pop sequence: 22112
Question 110 
4  
5  
6  
3 
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisons = 4+1
= 5
Question 111 
It cannot be implemented  
2 stacks  
4 stacks  
1 stack 
For this,
int x=element=stack1,pop();
stack2.push(element);
Step2: Once the complete stack1 gets copied to Stack2, then we can simply call pop() on s2, it will remove the element1.
So, A queue can be implemented using 2 stacks.
Question 112 
Considering 0address instructions machine, what will be the top of the stack after executing the following sequence of instructions?
PUSH 15, PUSH 4, PUSH 6, MULT, PUSH 30, ADD, ADD
30  
69  
54  
10 
Step1: PUSH 15,PUSH 4 and PUSH 6 from bottom to top. Now top of the stack value is 6.
Step2: Perform MULT operation. 6*4=24. Now present stack values are from bottom is 15 and 24.
Step3: Next again PUSH 30. Now top of the stack is 30.
Step4: Perform ADD operation. 30+24=54
Step5: Now present stack values are from bottom is 15 and 54. Perform ADD operation.
Step6: 15+54=69
Question 113 
Which of the following data structures is used in level order traversal of a binary tree?
Skip list  
Stack  
Array
 
Queue

Example:
Level order traversal of binary tree.
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.
printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
a) print temp_node>data
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node
Note:
Level order traversal of binary tree is time Complexity is O(n) where n is number of nodes in the binary tree.
Question 114 
2 ^{h}  
2 ^{h1} 1  
2^{ h+1} 1  
2 ^{h+1} 
● The number of leaf nodes l in a perfect binary tree, is l = ( n + 1 )/2 because the number of nonleaf (a.k.a. internal) nodes
● This means that a perfect binary tree with l leaves has n = 2 l − 1 nodes. ● In a balanced full binary tree, h = ⎡ log _{2 }(l)⎤ + 1 = ⎡ log _{2} ((n + 1 )/2)⎤ + 1 = ⎡ log_{ 2} (n + 1 )⎤
● In a perfect full binary tree, l = 2 ^{h} thus n = 2^{ h+1} − 1
● The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is ( n + 1 ) , where only 1 node exists in bottommost level to the far left.
●The number of internal nodes in a complete binary tree of n nodes is ⎣ n/2⎦ .
Question 115 
Stack  
Set  
List  
Queue 
Question 116 
O(n), O(n)  
O(n), O(1)  
O(1), O(n)  
O(1), O(1) 
Question 117 
12  
13  
14  
15 
Question 118 
2  
4  
3  
5 
→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.
→ So number of probes = ⌈(log_{2} 31)⌉
= ⌈4.954196310386876⌉
⇒5
Question 119 
11,31,23,50,73,62,41  
31,11,23,50,41,62,73  
11,31,50,23,73,62,41  
11,31,23,50,62,73,41 
According to pre order we will get below graph based on Inorder is 11,23,31,41,50,62,73.
Question 120 
*(x+i) is same as *(&x[i])  
&x[i] is same as x+i1  
*(x+i) is same as *x[i]  
*(x+i) is same as *x+i 
⇒* is nothing but Value at address location
⇒&x[i] means address of ith element
⇒*(&x[i]) means Value at “i” location of “ x address”.
We can also write it into *(X+i) = X[i] =*(&x[i])
Question 121 
In a full binary tree of height 10, the number of nodes with degree 0,1, and 2 will be ____,____ and ____ respectively.
Note: Consider height of a tree as the number of nodes in the longest path from root to any leaf node
512, 0, 511
 
512, 1, 510  
511, 0, 512
 
511, 1, 511 
Full binary tree consists of either 0 or 2 childs . So one child to the node is not possible.
The number of nodes with the degree of 1 is 0.
The nodes with degree 0 are leaf nodes, 2^{h1} = 2^{9} = 512.
The nodes with degree 2 are internal nodes 2^{h1}  1 = 511.
Question 122 
Commutative but not associative  
neither commutative nor associative  
Both commutative and associative  
Associative but not commutative 
Question 123 
Is far less than one  
Equals one  
Is far greater than one  
None of the above 
Question 124 
Consider an AVL tree constructed by inserting the elements 18, 10, 5, 3, 27, 7, 35, 43, 32 one by one. Which of the following options give the number of comparisons to search the key value 45 in this AVL tree?
5  
4  
3  
2 
Question 125 
Inorder  
Preorder  
Postorder  
None of the above 
(i) Traverse the left most subtree starting at the left external node,
(ii) Visit the root, and
(iii) Traverse the right subtree starting at the left external node.
The Inorder traversal of the above tree will outputs: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Question 126 
Linked allocation
 
Indexed allocation
 
Contiguous allocation  
None of the options 
Advantages:
Faster access as all blocks are nearby.
Suitable for small sequentially accessed file
Disadvantages:
Poor performance if file grows or shrinks.
Linked Allocation:Each block stores pointer to next block
Advantages:
No fragmentation.
Suitable for large sequentially accessed file
Disadvantages:
Random access is not possible, If one link is lost, cannot access subsequent blocks
Note: In File Allocation Table (FAT) all links are cached in a table for faster access.
Indexed Allocation:A single bock stores indexes of all blocks of a file.
Advantage:
Suitable for large randomly accessed file
Eg: UNIX inode stores the first 12 or so data block pointers and then singly, doubly, and triply indirect pointers.
Question 127 
2  
4  
3  
6 
=log_{2}63
=6
Question 128 
24 tree  
B+ tree
 
BTree  
None of the options

The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:
→ a 2node has one data element, and if internal has two child nodes;
→ a 3node has two data elements, and if internal has three child nodes;
→ a 4node has three data elements, and if internal has four child nodes.
Question 129 
is far less than 1  
equals 1  
is far greater than 1  
none of the options 
Question 130 
char*str="Raj is a research scholar";  
charstr[25]="Raj is a research Scholar";  
charstr[40]="Raj is a research Scholar";
 
char[] str="Raj is a research Scholar"; 
Variable initialization syntax : Datatype varible_name[size]="sring"
(or)
Datatype variable_name[ ]=”string”
Question 131 
contain address of next node  
may contain null character
 
contain address of next pointer  
both (A) and (B) 
→ The field of each node that contains the address of the next node is usually called the 'next link' or 'next pointer'.
→ The remaining fields are known as the 'data', 'information', 'value', 'cargo', or 'payload' fields. Note: Option C is also correct.
Question 132 
'' is left associative and '*' has precedence over ''
 
'' is right associative and '*' has precedence over ''  
'' is right associative and '' has precedence over '*'  
'' is left associative and '' has precedence over '*' 
Step1: 523*52 will be 19.
Step2: if it is treated as (5(23))*(52)
Step3:  has precedence over * and if it associates from the right.
Question 133 
Struct node* { Int data; node*link; }  
Struct node { int data; Struct node*link; }  
Struct node { int data; node link; }  
Struct node* { int data; struct node*link; } 
Struct tag_name
{
Datatype variable_name;
Struct tag_name *pointer_variable;
};
Question 134 
O(lgn)  
O(nlogn)  
O(n^{2})  
O(n) 
→ The worstcase time complexity of a search in a binary search tree is O(n).
Question 135 
(a) Parenthesis balancing program
(b) Process scheduling operating system
(c) Conversion of infix arithmetic expression to postfix form
(a) and (b)  
(b) and (c)  
(a) and (c)  
(a),(b) and (c) 
Question 136 
(i) (iii) (ii)
 
(ii) (i) (iii)  
(iii) (ii) (i)  
(ii) (iii) (i) 
→ Scheduling can be implemented using Queue.
→ The inorder traversal of binary search gives sorting order.
Question 137 
5 3 1 2 4 7 8 6  
5 3 1 2 6 4 9 7  
5 3 2 4 1 6 7 8  
5 3 1 2 4 7 6 8 
Option D:
Let draw binary search tree for the given sequence,
After traversing through this tree we will get same sequence.
Question 138 
(a) Binary search in an array
(b) Breadth first search
(c) Implementing function calls
(d) Process scheduling
(b) and (d)  
(b) and (c)  
(a) and (c)  
(c) and (d) 
Binary search can be implemented by using recursion. So Stack is suitable for implementing function calls.
Question 139 
Front=rear=null  
Front=Rear!=null  
Front=Rear+1  
Front=Rear1 
Question 140 
(i1)/2 +j  
((i1)*i)/2 +j  
(i*i)/2 +j  
(i*j1)/2 
Question 141 
Probably the most widely used data structure  
A homogeneous structure  
A random access structure  
All of these 
● An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.
● Memory is allocated homogeneously and we can access any element by using index value.
Question 142 
Binary tree  
Recursive tree  
Insert sort  
Unitary tree 
Question 143 
Average path length  
Median path length  
Mode path length  
Simple deviation path length 
Question 144 
Heap  
Bubble  
Splay  
Binary 
Question 145 
Recursive  
Abstract data type  
Storage Structure  
File structure 
Question 146 
Lower bound  
Range  
Upper bound  
All of these 
Question 147 
Control array  
Primary array  
Secondary array  
An integer array 
A control array can be created only at design time, and at the very minimum at least one control must belong to it.
Features:
1. Controls that belong to the same control array share the same set of event procedures; this often dramatically reduces the amount of code you have to write to respond to a user's actions.
2. We can dynamically add new elements to a control array at run time; in other words, you can effectively create new controls that didn't exist at design time.
3. Elements of control arrays consume fewer resources than regular controls and tend to produce smaller executables. Besides, Visual Basic forms can host up to 256 different control names, but a control array counts as one against this number. In other words, control arrays let you effectively overcome this limit.
Question 148 
Tree  
Stack  
Linked List  
Queue 
Algorithm
We have Postfix[ ] Array, Stack, Infix[ ] Array
1. Scan the given expression (Infix ) from Left to Right [ one character at a time].
2. Check Whether the given character is an operator [+, , *, /, ^ etc] or operand.
3. If it is an operand, then copy it in the Prefix Array.
4. If it is a operator then,
1. Check whether, Stack is empty or not
2. If it is empty then, push the operator in the stack and go to step
3. If Stack is not empty then compare the precedence of Top of stack with operator.
4. If the Top of Stack has higher or equal precedence then pop it and copy in the postfix array.
5. If the operator has higher precedence, push it in the stack and go to step 5.
6. If Stack is not empty go back to step 4(1).
5. Continue solving the expression in usual manner until the expression come to end.
6. Pop the remaining operand in the stack and copy it to postfix array.
Question 149 
String  
Queue  
Stack  
Linked list 
→ When the called procedure is done, it issues a return instruction, which pops the address from the top of the stack and transfers control there.
→ That’s just the basic processor mechanism that makes it easy to implement procedure calls. The actual details of identifying the parameters, placing them on the stack, executing a call instruction are up to the compiler.
→ In the called function, the compiler is responsible for ensuring any registers that may be clobbered are saved, allocating stack space for local variables, and then restoring the registers and stack prior to a return.
Question 150 
5  
2  
3  
4 
Step2: According to BST, the properties are left child is smaller than his root node and right subtree is greater than his root node.
Step3: They given characters B,I,N,A,R,Y. And corresponding alphabetical number are B=2,I=9,N=14,A=1,R=18,Y=25.
Question 151 
Which of the following is wrong while inserting a node in the beginning of list?
Obtain a node from available list
 
Make the next pointer of the current head pointer to new node  
Make the node pointer of the list pointer to new node
 
Make the next pointer of the new node pointer to current head of the list

• Option B, C and D: It shows actual procedure to insert a node at beginning. So, Option A is wrong
Question 152 
+*/abdef  
a+bd*ef/  
abdef*/+  
a+b*de/f 
Inorder→ left,root and right.
a+b*dc/f
Question 153 
S  
P  
Q  
R 
Step2: Then we have to pop 4 elements. So, present having only one element,that is P.
Step3: 4 elements we have to insert into a Queue. Queue follows FIFO manner.
Step4: Again we have to delete two elements from queue and inserted into stack.
Step5: The inserted elements are T and S.
Step6: Final pop element is S.
Step7: Stack having only two elements. P and T.
Question 154 
Row major order  
Column major  
Matrix major  
Simple 
→First element address is 1000 and Second element address is 1002 and so on
→A[2][1] means Second row first element whose address is 1010.
Question 155 
3,2  
0,2  
3,0  
0,4 
→The first value is 3 and a[4] value is 0
Question 156 
A_{0} + 15s(i1)+(j1)  
A_{0} + 8s(i1)+(j1)  
A_{0} + 15s(j1)+(i1)  
A_{0} + 8s(j1)+(i1) 
A[i,j]=Base address+ j*sizeof the array(i1)+(j1)
Question 157 
If n_{A} is the number of elements in stack A and n_{B} is the number of elements in stack B, then overflow occurs when Push Operation is performed on either stack and
n_{A}=n_{B}  
n_{A}=n_{B}=n  
n_{A}+n_{B}=n  
n_{A}+n_{B}>=n 
→The sum of the n_{A} and n_{B} is equal to the number of elements there is no possibility of inserting element into stack.
Question 158 
abc*+deh/*  
ab+c*de/h*  
(a b c*)+(de/h*)  
abc*+de/h* 
=a+[bc*]d/e*h // Select highest priority operators and convert into postfix form,If same priority then go for associativity
=a+[bc*][de/]*h
=a+[bc*][de/h*]
=[abc*+][de/h*]
=abc*+de/h*
Question 159 
a) Implementation breadth first search
b) Implementation depth first search
c) Process scheduling
Which of the following is the correct option?
a and b  
a and c  
b and c  
a,b and c 
→Queue is also used for Breadth first traversal also
Question 160 
2^{h}1  
2^{h}+1  
2^{h+1}1  
2^{h+1}+1 
→The height of the binary tree is the longest path from root node to any leaf node in the tree
Question 161 
(n1)x+1  
(n1)x1  
nx+1  
nx1 
Then n value is 2 and internal node is 1 then the number of leaves are (21)1+1=2 leaves.
Question 162 
Always appends list ‘m’ at the end of list ‘n’  
Always appends list ‘n’ at the end of list ‘m’  
Append list ‘m’ at the end of list ‘n’ with possibility of error  
Appends list ‘n’ at the end of list ‘m’ with possibility of error 
→Nonavailability of the any one of the linked list leads to possibility of error.
Question 163 
2^{k1}  
2*(k1)  
2^{k+1}  
2((k+1) 
According to the handshaking lemma , the sum of the degree is 2* number of edges So the option B is suitable one.
Question 164 
Insertion – 0(1), Deletion – 0(1), Maximum – 0(1), Minimum – 0(l)  
Insertion – 0(1), Deletion – 0(1), Maximum – 0(n), Minimum – 0(n)  
Insertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1)  
Insertion – 0(n), Deletion – 0(n), Maximum – 0(n), Minimum – 0(n) 
→ Deletion will take O(n). Let, 1,2,3,4,5. Suppose we want to delete last element in the array, It will traverse end of the array. So, it takes worst case O(n) and best case O(1). But we always consider worst case time complexity.
→ Maximum will take O(1) because we know location of maximum element. So it requires only constant amount.
→ Minimum will take O(1) because we know location of maximum element. So it requires only constant amount.
Question 165 
A  
B  
F  
G 
Step2: Stack is pooped five elements then stack is look like
Step3: Popped five elements are inserted into a queue then queue is look like
Step4: Two elements are deleted from the queue
Step5: deleted queue elements are pushed back onto the stack
Top of the stack is B.
Question 166 
A  
B  
C  
D 
Option B is satisfied max heap property.
Option C is violated max heap property because 7 is greater than his root.
Option D is violated max heap property because 9,10,8,7 elements are greater than his root.
Question 167 
1  
1/n  
1/m  
n/m 
Question 168 
(A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
(B) Breadthfirst search cannot be used to find connected components of a graph.
(C) Given the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely.
(D) Depthfirstsearch can be used to find the connected components of a graph.
A  
B  
C  
D 
→ A connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
1. Kosaraju’s algorithm for strongly connected components.
2. Tarjan’s Algorithm to find Strongly Connected Components Time complexity for both algorithms are O(V+E).
Question 169 
726  
796  
506  
616 
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8. From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012=2*E
⇒ E=506
Question 170 
S1: A queue can be implemented using two stacks.
S2: A stack can be implemented using two queues.
Which of the following is correct?
S 1 is correct and S 2 is not correct.  
S 1 is not correct and S 2 is correct.  
Both S 1 and S 2 are correct.  
Both S 1 and S 2 are incorrect. 
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
→ A stack can be implemented using two queues
Question 171 
If we remove the root node, which of the node from the left subtree will be the new root?
11  
12  
13  
16 
After removing root element, binary search tree is looks like
Question 172 
Underflow occurs  
Stack operations are performed smoothly  
Overflow occurs  
None of the above 
Question 173 
(n/2) 1  
(n/2) +1  
(n–1) / 2  
(n+1) / 2 
→ The maximum height of the tree will be (n–1) / 2. It is standard property of full binary tree.
Question 174 
Implementation of recursion  
Evaluation of a postfix expression  
Job scheduling  
Reverse a string 
1. Implementation of recursion
2. Evaluation of a postfix expression
3. Expression evaluation and syntax parsing
4. Backtracking
5. Compile time memory management
6. Reverse a string
Question 175 
15  
14  
13  
12 
Step1: Total number of letters/operands with duplication is 5.
Step3: To find total number of ways, we have catalan formula.
Here, n=5
Catalan number = (2n)! / (n! * (n+1)!)
= (2*5)! / (5! * (5+1)!)
= 10! / (5! * 6!)
= 14
Note: We used catalan formula because they given in fully parenthesized to yield an infix expression.
Question 176 
P + 1  
P – 1  
P – 2  
P + 2 
2. V(G),Flow graph is defined as V(G)=EN+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G.
Question 177 
&A[0][0][0] + w(y* z* q + z* p + r)  
&A[0][0][0] + w(y* z* p + z*q + r)  
&A[0][0][0] + w(x* y* p + z* q+ r)  
&A[0][0][0] + w(x* y* q + z* p + r) 
Question 178 
h (k, i) = (h _{1} (k) + h_{ 2} (k) + i) mod m  
h (k, i) = (h _{1} (k) + h_{ 2} (k)  i) mod m  
h (k, i) = (h _{1} (k) + i h_{ 2} (k)) mod m  
h (k, i) = (h _{1} (k)  i h_{ 2} (k)) mod m 
h _{1} → hash function
h _{2} → Step function
First try h(k,0) = h 1 (k), if it is occupied, try h(k,1) etc..,
Advantage: less clusters, uses Θ(m*m) permutations of index addressing sequences.
Question 179 
θ(log _{n} h*t)  
θ(log _{t} n*h)  
θ(log _{h} n)  
θ(log _{t} n) 
Note: BTree search operation best,average and worst case will take θ(logn).
Question 180 
2 3 4 6 7 13 15 17 18 18 20  
20 18 18 17 15 13 7 6 4 3 2  
15 13 20 4 7 1718 2 3 6 18  
2 4 3 13 7 6 15 17 20 18 18 
Question 181 
(a) Depth first search is used to traverse a rooted tree.
(b) Preorder, Postorder and Inorder are used to list the vertices of an ordered rooted tree.
(c) Huffman’s algorithm is used to find an optimal binary tree with given weights.
(d) Topological sorting provides a labelling such that the parents have larger labels than their children.
Which of the above statements are true?
(a) and (b)  
(c) and (d)  
(a), (b) and (c)  
(a), (b), (c) and (d) 
→ Depthfirst search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
→ The optimal binary tree, which has minimum weighted path length when the characters of the alphabet are stored at its n terminal nodes.An optimal binary tree generates what is called a Huffman code
→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.
A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.
Question 182 
dbefacg  
debfagc  
dbefcga  
debfgca 
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g
Pre order: a b d e c f g
Post order: d e b f g c a
Question 183 
Breadth First Search  
Depth First Search  
Root Search  
Deep Search 
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 184 
1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2, ?
1  
2  
4  
8 
Question 185 
2  
3  
9  
97 
 Hash(y)=X mod 100
 Key=4594
 First 3 locations are already occupied.
 Next cell=?
Step1: Quadratic Probing function is h(k,i) = (h'(k) +c _{1} i+c _{2} i^{ 2} )mod m 0≤ i ≤ m1
where c1 and c2 constants ≠0
Step2: First pass: 4594 % 100
= 94
Sep3: Second pass: (4594 + 1 ^{2} ) % 100
= (94 + 1) % 100
= 95
Step3: Third pass: (4594 + 2 ^{2} ) % 100
= (94 + 4) %100
= 98
Step4: Fourth pass: (4594 + 1 ^{2} ) % 100
= (94 + 9) %100
= 103 % 100
= 3
Question 186 
Is a bidirectional graph  
Is directed graph  
Is graph in which number associated with arc  
Eliminates table method 
→ A weighted graph is therefore a special type of labeled graph in which the labels are numbers.
Question 187 
Advance  
Backup  
First  
Retrieve 
Question 188 
Hash addressing  
Chaining  
Both (A) and (B)  
Indexing 
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 189 
Binary search tree  
AVL  tree  
Threaded binary tree  
Complete tree 
1. Single Threaded: each node is threaded towards either the inorder predecessor or successor (left or right).
2. Double threaded: each node is threaded towards both the inorder predecessor and successor (left and right).
Question 190 
3  
4  
5  
6 
Hash function = f(key) = key mod 7
Question 191 
ABCD  
BACD  
BADC  
ABDC 
1. Using DFS method
2. Using indegree elimination method
The simplest method is indegree elimination method.
Indegrees:
A →0
B →1
D →2
C → 1 (Final)
We can assume that indegree value of A is ‘0’. So, it is starting point.
Step1: Remove ‘A’ from graph, then indegrees are
B →0
D →1
C →1
Sequence:
Step2: Remove ‘B’ from graph, then indegrees are
D →0
C →1
Sequence:
Step3: Remove ‘C’ from graph then indegrees are
C →0
Sequence:
Question 192 
2 deletions, 3 additions  
3 deletions, 2 additions  
3 deletions, 4 additions  
3 deletions, 3 additions 
Step1: Delete ‘a’ from queue. The deletion operation performs First In First Out.We will perform the deletion at front end
After deleting queue will become
Step3: Delete ‘b’ from queue. The deletion operation performs First In First Out.
After deleting queue will become
Step3: Delete ‘c’ from queue. The deletion operation performs First In First Out.
After deleting queue will become
Step4: Insert the element “c” into the queue, We will perform the insertion at rear end
The elements of queue after inserting the element ”c” are
Step5: Insert the element “b” into the queue,then the elements of queue after inserting the element ”b” are
step6: Insert the element “a” into the queue,then the elements of queue after inserting the element ”a” are
→ Step1,step2 and step3 are deletion operations and step4,step5 and step6 are deletions operations.
→ So total 3 deletions and 3 insertions are required to get required configuration.
Question 193 
post – order  
in  order  
pre  order  
linear  order 
Example:
In this traversal method, the left subtree is visited first, then the root and later the right subtree. We should always remember that every node may represent a subtree itself.
Question 194 
Hash addressing  
Chaining  
Indexing  
None of these 
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 195 
O (log _{2} n)  
O (n)  
O (n log _{2} n)  
O (1) 
Question 196 
Every tree is a bipartite graph  
A tree contains a cycle  
A tree with n nodes contains n1 edges  
A tree is a connected graph 
Note: Minimum 1 edge and maximum n1 edges.
Question 197 
1  
3  
7  
8 
a, c, d are going to unbalance.
Question 198 
(A(B+C))*D  
((AB)+C)*D  
((A+B)C)*D  
(A+(BC))*D 
Question 199 
Quick sort  
Bubble sort  
Merge sort  
Selection sort 
Bubble sort will give best complexity, when the array is very sorted. Here the number interchanges are very less.
Merge sort will will gives best time complexity but not like bubble in this case. Here the number interchanges are more.
Selection sort will always gives worst performance, whether it is sorted order or not.
Question 200 
Divide and conquer technique  
Greedy algorithm  
Back tracking  
Dynamic Programming 
Procedure:
1. Divide: select lower or upper half
2. Conquer: search selected half
3. Combine: None
Recurrence relation : T(n)=T(n/2)+Θ(1)
Using masters theorem,
a=1, b=2, k=0,p=0
T(n)=Θ(logn)
Question 201 
O (log _{2} n)  
O (n)  
O (n log _{2} n)  
O (1) 
Worst case in linked list:
Question 202 
defbc/++*  
def+/bc+*  
def+/bc *+  
None of these 
Postfix expression: d ef + / bc * +
Question 203 
Array  
Linked lists  
Stacks  
Tables 
→ Elements are accessed using an integer index to specify which element is required. Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixedlength or resizable.
Note: Arrays are directly stored in a memory location. Linked list, Stacks and table(using array) are used logical memory rather than physical memory.
Question 204 
1  
3  
7  
8 
a, c, d are going to unbalance.
Question 205 
Depth first order  
Breadth first order  
Topological order  
Linear order 
Question 206 
Every tree is a bipartite graph  
A tree contains a cycle  
A tree with n nodes contains (n1) edges  
A tree is connected graph 
Note: Minimum 1 edge and maximum n1 edges.
Question 207 
(A(B+C))*D  
((AB)+C)*D  
((A+B)C)*D  
(A+(BC)*D) 
Question 208 
Level wise printing of tree  
Implementation of priority queues  
Function call implementation  
Depth first search in a graph 
Applications:
1.Bandwidth management
2.Discrete event simulation
3.Dijkstra's algorithm
4.Huffman coding
5.Bestfirst search algorithms
6.ROAM triangulation algorithm
7.Prim's algorithm for minimum spanning tree
Question 209 
4 PUSH and 3 POP instructions  
5 PUSH and 4 POP instructions  
6 PUSH and 2 POP instructions  
5 PUSH and 3 POP instructions 
after converting postfix notation the notations are ab* cde /* +
Total 5 PUSH and 4 POP operations performed.
Question 210 
ABD^ + EF – / G+  
ABD + ^EF – / G+  
ABD + ^EF / – G+  
ABD^ + EF / – G+ 
→ Actual tree structure is
Question 211 
n nodes  
log _{2} n nodes  
2n –1 nodes  
2^{ n} nodes 
There are 4 leaf nodes in the above tree.
So, total number of nodes are 2*41
=81
=7
Question 212 
20 , 20  
3 ,20  
3, 5  
20, 5 
→ varchar is a variablelength data type, the storage size of the varchar value is the actual length of the data entered, not the maximum size for this column.
→ So, A varchar(20) has only 3 spaces because its initialized to 'xyz' and B char(20) has 20 spaces as char data type occupies the storage space equivalent to the maximum size.
Question 213 
60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34
The number of nodes is the left subtree is
7  
6  
3  
5 
Question 214 
6 2 3 * / 4 2 * + 6 8 * 
The top two elements of the stack after second * is evaluated, are :
6, 3  
8, 1  
8, 2  
6, 2 
While traversing the expression if you find an element value then push it on the top of stack this way the top element of the stack will represent the second operand of an operation and the element presents after top element will represent the first operand of the operation. While traversing the postfix expression if you find an operation symbol then pop 2 elements from the top of the stack and then after performing operation store it’s result on the top of stack.
Question 215 
<42, 35, 40, 22, 25, 26, 30>  
<42, 35, 40, 22, 25, 30, 26>  
<42, 40, 35, 25, 22, 26, 30>  
<42, 40, 35, 25, 22, 30, 26> 
The resultant MAX_Heap will look like
< 4 2, 40, 35, 25, 22, 30, 26 >
Question 216 
What will be the value propagated at the root ?
6  
3  
5  
4 
Question 217 
2^{d} – 1  
2^{d + 1} – 1  
d + 1  
d 
Properties:
→The number of nodes at depth d in a perfect binary tree = 2^{d}
→A perfect binary tree of height h has 2^{h+1} 1 nodes
→Number of leaf nodes in a perfect binary tree of height h = 2^{h}
→Number of internal nodes in a perfect binary tree of height h = 2^{h} 1
→The minimum number of nodes in a binary tree of height h = h+1
→The maximum number of nodes in a binary tree of height h = 2^{h+1} 1
Question 218 
Queue  
Linked list  
Doubly linked list  
Binary tree 
Question 219 
Inorder : j e n k o p b f a c l g m d h I
Postorder : j n o p k e f b c l m g h i d a
The Preorder traversal of the tree shall be
a b f e j k n o p c d g l m h i  
a b c d e f j k n o p g l m h i  
a b e j k n o p f c d g l m h i  
j e n o p k f b c l m g h i d a  
None of the above 
Step2:
Step3: Final tree is
Step4: Preorder traversal is Root,left and right
preorder= a b e j k n p o f d g l c m i h
Note: Given options are wrong. Excluded for evaluation.
Question 220 
Binary Search  
Polynomial Manipulation  
Insertion  
Radix Sort 
Note: We can also implement binary search using linked list but it will give time complexity is O(n) instead of O(logn).
Question 221 
Search and Insert Operations  
Search and Delete Operations  
Insert and Delete Operations  
Search, Insert and Delete Operations 
Question 222 
3, 14  
3, 10  
4, 14  
4, 10 
Step 1: Since a heap is a almost complete binary tree so build a heap first.
Step 2: Since the above heap is not a max heap so to convert a heap into maxheap start applying max heapify operation from the largest index parent node(node having 1 or more children).
The above Heap is the maxheap where each root node have maximum value. Now depth of the Maxheap is 3 and right child of the Root node is 10.
Question 223 
3  
4  
5  
6 
h(44)=44 mod 7 ⇒ 2
h(45)=45 mod 7 ⇒ 3
h(79)=79 mod 7 ⇒ 2 (collision occurred)
h(79)=(79+1) mod 7 ⇒ 3 (collision occurred)
h(79)=(79+2) mod 7 ⇒ 4
h(55)=55 mod 7 ⇒ 6
h(91)=91 mod 7 ⇒ 0
h(18)=18 mod 7 ⇒ 4 (collision occurred)
h(79)=(18+1) mod 7 ⇒ 5
h(63)=63 mod 7 ⇒ 0 (collision occurred)
h(63)=(63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations
Question 224 
cannot have more than 37 nodes  
has exactly 37 nodes  
has exactly 35 nodes  
cannot have more than 35 nodes 
Where, L= Number of leaf nodes
n= Nary tree
I = Number of intermediate nodes
Now, 19 = I(21)+1
19 = 2II+1
19 = I+1
I = 18
Total Number of nodes in a tree = Number of Intermediate nodes+Number of Leaf nodes
Total Number of nodes in a tree = 19+18
Total Number of nodes in a tree = 37
Question 225 
30  
33  
45  
None of the above 
Where, L= Number of leaf nodes
n= Nary tree
I = Number of intermediate nodes
Now, L =8(51)+1
L =8(4)+1
L =33
Total Number of nodes in a tree = Number of Intermediate nodes+Number of Leaf nodes
Total Number of nodes in a tree = 8+33
Total Number of nodes in a tree = 41
Question 226 
Binary search tree  
AVL tree  
Threaded Binary Tree  
Complete Binary Tree 
→ ALV tree
Question 227 
1  
2  
3  
4 
Question 228 
3, 10, 1, 8,___ ,___,___.  
1, 3, 8, 10,___,___,___.  
1,___,3,___, 8,___,10  
3,10,___,___, 8,___,___. 
h(3)= ((7*3)+3) mod 4 = 0
h(8)= ((7*8)+3) mod 4 = 3
h(10)= ((7*10)+3) mod 4 = 1
Question 229 
Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree.
d & h  
c & k  
g, b, c, h, i, m  
c & h 
Eccentricity of a vertex u, is
E(u) = max_{u∈v(G)} d(u, v)
i.e., the maximum distance of a node to other nodes is the eccentricity of that node
Radius: The minimum eccentricity from all the vertices is considered as the radius of the Graph G denoted by r(G).
Here radius of the graph, r(G)=3
Center: If the eccentricity of a graph is equal to its radius, then it is known as the central point of the graph.
And in above graph vertex "h" and " c" have eccentricity equal to the radius of the graph. So vertex h and c are the center of graph.
Hence correct answer is option (D).
Question 230 
4  
3  
2  
1 
Question 231 
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5)
–3/8  
–8/3  
24  
–24 
Question 232 
Neither of the pointers change  
Only front pointer changes  
Only rear pointer changes  
Both of the pointers changes 
Observe 1, 2, 3 whenever we are inserting an element into a queue (singly linked list) we are updating Rear pointer.
Question 233 
stack  
tree  
queue  
linked list 
Question 234 
ABFCDE  
ADBFEC  
ABDECF  
None of the above 
Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 235 
All items in the left subtree are less than root  
All items in the right subtree are greater than or equal to the root  
Each subtree is itself a binary search tree  
All of the above 
2. All items in the right subtree are greater than or equal to the root
3. Each subtree is itself a binary search tree
Question 236 
Strings  
Lists  
Queues  
All of the above 
Examples:
1. Array
2. Linked List
3. Stacks
4. Queues
Question 237 
Dequeue  
Priority  
Tree  
All of the above 
Priority Queue is like a regular queue or stack data structure, but here each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Tree: A tree is a data structure containing a collection of nodes. Here a node can have any number of children. A node with no child is called as leaf node and a node with 1 or more child is called parent node. Each parent node have a pointer to its children.
Question 238 
Strings  
Lists  
Stacks  
None of the above 
Examples:
1. Array
2. Linked List
3. Stacks
4. Queues
Question 239 
Factorial  
Fibonacci numbers  
Tower of Hanoi  
Tree traversal 
Condition: fibonacci(n1) + fibonacci(n2)
Recurrence relation is: T(n)=2T(n1)+C
Time Complexity: O(2^{n})
→ Factorial number using recursion is
Condition: fact(n1)*n
Recurrence relation is: T(n)=T(n+1)+1
Time Complexity: O(n)
→ Tower of Hanoi using recursion is
Step1: Hanoi(disk  1, source, aux, dest)
Step2: move disk from source to dest
Step3: Hanoi(disk  1, aux, dest, source)
Recurrence relation is: T(n)=2T(n1)+C
Time Complexity: O(2^{n})
→ Tree traversals like Preorder,Postorder and Inorder using recursion only
Note: Recursion is best in the case of Tower of Hanoi,Factorial number and Tree traversals but it is not give good performance to fibonacci numbers.
Question 240 
ABFCDE  
ADBFEC  
ABDECF  
ABDCEF 
Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 241 
2^{0} + 2^{1} + ….. 2^{h}  
2^{0} + 2^{1 }+ ….. 2^{h – 1}  
2^{0} + 2^{1} + ….. 2^{h + 1}  
2^{1} + ….. 2^{h + 1} 
Suppose, in level3, it have 2^{3}=8 nodes.
Question 242 
256  
255  
248  
None of these 
 nodes=8
 Total number of trees=?
Possibility1: To find total number of trees using n^{n2}.
= 8^{82}
= 262144 trees are possible.
Possibility2: According to given problem, they are using binary tree based on below formula
= 2^{n} n
= 2^{8} 8
= 248
Note: They are not given proper input.
Question 243 
In order : E I C F B G D J H K
Preorder : B C E I F D G H J K
The post order traversal of the above binary tree is
I E F C G J K H D B  
I E F C J G K H D B  
I E F C G K J H D B  
I E F C G J K D B H 
Question 244 
46  
47  
41  
43 
 size m=10000
 hash function h(k) = ⌊m(kA mod 1)'⌋
 A=(√5 – 1)/2
 key k=123456 location =?
Step1: Find out h(123456) = ⌊(10000 * (123456 * (√5 − 1) / 2) mod 1)⌋
= ⌊(10000 * (76300.004115 mod 1)⌋
= ⌊(10000 * (.004115))⌋
= ⌊41.15⌋
= 41
Question 245 
θ(n) and θ(1) respectively  
θ(n) and θ(n) respectively  
θ(1) and θ(1) respectively  
None of the above 
Question 246 
At most (1/α) ln ((1–α)/α)  
At most (1/α) ln (1/(1–α))  
At least (1/α) ln (1/(1– α))  
At least (1/α) ln (α/(1– α)) 
→ Given an openaddress hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.
→ Given an openaddress hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.
Question 247 
O(log n)  
O(n)  
O(n logn)  
O(n^{2}) 
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heapsize[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 MaxHeapify(A, i)
The BuildMaxHeap function that follows, converts an array A which stores a complete binary tree with n nodes to a maxheap by repeatedly using MaxHeapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a oneelement heap.
→ BuildMaxHeap runs MaxHeapify on each of the remaining tree nodes.
Question 248 
8 3 4 + – 3 8 2 / + * 2 $ 3 + is
17  
131  
64  
52 
Question 249 
S1 : It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2 : The elements of a priority queue may be complex structures that are ordered on one or several fields.
Which of the following is correct ?
Both S1 and S2 are incorrect.  
S1 is correct and S2 is incorrect.  
S1 is incorrect and S2 is correct.  
Both S1 and S2 are correct 
S2: TRUE: The elements of a priority queue may be complex structures that are ordered on one or several fields.
Question 250 
54  
27  
26  
None of the above 
Question 251 
O(1)  
O(lgn)  
O(n)  
O(nlgn) 
BuildMaxHeap(A)
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heapsize[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 MaxHeapify(A, i)
The BuildMaxHeap function that follows, converts an array A which stores a complete binary tree with n nodes to a maxheap by repeatedly using MaxHeapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a oneelement heap.
→ BuildMaxHeap runs MaxHeapify on each of the remaining tree nodes.
Question 252 
Secondary clustering  
Primary clustering  
Both (A) and (B)  
None of these 
Example: Linear probing
→ Secondary clustering is less severe, two records do only have the same collision chain if their initial position is the same.
Example: Quadratic probing
Question 253 
90, 40, 65, 50, 88  
90, 110, 80, 85, 88  
190, 60, 90, 85, 88  
65, 140, 80, 70, 88 
1. Left subtree is smaller than his root node
2. Right subtree is greater than or equal to his root
Based on above rules, the search operation will perform
Note: The sequence of searching should be continuous.
Question 254 
ABC  
CBA  
BAC  
CAB 
OptionA: According to constraint,
Push(A) then Pop(A)
Push(B) then Pop(B)
Push(C) then Pop(C)
Then the possible pop sequence is ABC. So, it is TRUE
OptionB: According to given constraint, Push(A),Push(B) and Push(C) then Pop(C),
Pop(B) and Pop(A). The possible Pop sequence is CBA. So, it is TRUE
OptionC: According to given constraint, Push(A) and Push(B) then Pop(B) and Pop(A)
then push(C) and Pop(C). The possible Pop sequence is BAC. So, it is TRUE
OptionD: This is not possible.
Question 255 
Heap  
Circular array  
Linked list  
Binary tree 
→ In a priority queue, an element with high priority is served before an element with low priority.
→ In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.
→ While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map".
→ just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
Question 256 
About log_{2}n  
About 2 log_{2}n  
About n log_{2}n  
About 2n 
level1: 1 and 2
level2: 3 and 6.
[Note: Assume that root starts from level0]
The height of the binary tree is O(log_{2}n). As per the given constraint, we have to calculate individually of left farthest node and right farthest node height.
=log_{2}n*log_{2}n
=2*log_{2}n or (log_{2}n)^{2}
Question 257 
100  
200  
10000  
There is no upper limit 
1. They given chained hash. It is like linked list.
2. Maximum number of entries that can be placed in the table.
In chained hash, we adding new element when collisions are happened.
Question 258 
LIFO  
LILO  
FILO  
FIFO 
Question 259 
2^{k}1
 
2^{k1}  
2^{k}  
2^{k}+1 
→ A Binary Tree is full if every node has 0 or 2 children.
→ In a Full Binary, number of leaf nodes is number of internal nodes plus 1
L = I + 1
Where,
L = Number of leaf nodes,
I = Number of internal nodes.
Question 260 
from leaf to root are non–increasing  
from leaf to root are non–decreasing  
from root to leaf are non–decreasing  
from root to leaf are non–increasing 
Question 261 
First in first outorder  
Last in first outorder  
Parallel fashion  
Load balancing 
Question 262 
It is an odd number.  
It is an even number.  
It cannot be equal to the number of leaves.  
It is always greater than twice the number of leaves. 
Ex: n=5
= (2*5)1
= 9
Question 263 
An array  
A stack  
A queue  
A linked list 
Question 264 
An algorithm to search for an element in a singly linked list requires 0(n) operations in the worst case.  
An algorithm for deleting the first element in a singly linked list requires 0(n) operations in the worst case.  
An algorithm for finding the maximum value in a circular linked list requires 0(n) operations.  
An algorithm for deleting the middle node of a circular linked list requires 0(n) operations. 
Question 265 
3  
4  
5  
6 
Hash function = f(key) = key mod 7
Question 266 
maximum  
minimum  
sum  
product  
None of the above 
In Max heap→ The root element is greater than of his all childs.
In Min heap→ Te root element is smaller than of his all childs.
Question 267 
Circular Queue  
Linear Queue  
Stack  
Deque 
Question 268 
A tree is a connected acyclic graph.  
A tree is a connected graph with n1 edges where ‘n’ is the number of vertices in the graph.  
A tree is an acyclic graph with n1 edges where ‘n’ is the number of vertices in the graph.  
A tree is a graph with no cycles. 
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas "A tree is a graph with no cycles." is not always correct as it can be bipartite.
Hence D does not define a tree.
Question 269 
Linked list  
Stack  
Array  
Tree 
Question 270 
100,50,75, 60, 98
 
100, 120, 90, 95, 98  
200,70,100, 95, 98  
75, 150, 90, 80, 98 
1. Left subtree is smaller than his root node
2. Right subtree is greater than or equal to his root
Based on above rules, the search operation will perform
Question 271 
for (p=list; p !=NULL; p=p →next);
p=q;
 
for (p=list; p !=NULL; p=p →next);
p →next=q;
 
for (p=list; p →next!=NULL; p=p→next);
p=q;
 
for (p=list; p →next !=NULL; p=p →next);
p →next=q;

→ To the traverse the list, we will take one pointer.
→ We will traverse the list till the end by moving the pointer to next node.
→ The pointer will point to the last node and from there the pointer next address will point to the new node.
Option D will provide the above steps.
Q
Question 272 
3^{i}  
3i  
3  
3i + 1 
Given condition is every node has at least three children.
the root node is present at level 0, here only one is present(3^{0})
at level 1, three nodes are present based upon the condition( 3^{1} nodes)
at level 2, nine nodes will be present (3^{2} nodes ) [Each node has at least three children]
and so on the at level "i", 3^{i} nodes will be present.
Question 273 
Arrays
 
Stacks  
Queues  
Linked lists 
→ Recursion is one the application of stack. It supports many applications.
Applications:
1. Expression Evaluation
2. Expression Conversion
3. Syntax Parsing
4. Backtracking
5. Parenthesis Checking
6. String Reversal
Question 274 
O(log n)  
O(n)  
Ω(n log n)  
Ω (n^{2}) 
Question 275 
A B C D E F  
A B D E F C  
A C E B D F  
None of the above 
OptionA: It is ruled out because we can’t move after C to D. It is violating DFS property.
OptionB: It is following actual DFS structure.
OptionC: It is ruled out because after visiting E we can’t visit B again. It is violating DFS properties.
Question 276 
1024  
2^{10}  1  
1000  
None of the above 
→ To find maximum number of nodes in a binary tree of depth using formula is
= 2^{h+1} 1
= 2^{11} 1
= 20481
= 2047
Question 277 
Depth first order  
Breadth first order  
Topological order  
Linear order 
→ A depthfirst order is defined to be the reverse of the order in which we last visit the nodes of the control graph when we create the Depth first spanning tree(DFST).
Question 278 
defbc/+ +  
def+/bc+*  
def+/bc*+  
None of these 
Question 279 
Level wise printing of tree.  
Implementation of priority queues.  
Function call implementation  
Depth first search in a graph 
1. CPU scheduling
2. Disk Scheduling
3. synchronization(IO Buffers, pipes, file IO, etc.)
4. Breadth First search
5. Implementation of priority queues.
Question 280 
Indexed addressing mode  
Base Register addressing mode  
Relative address mode  
Displacement mode 
The address of the operand is obtained by adding to the contents of the general register (called index register) a constant value. The number of the index register and the constant value are included in the instruction code.
→ Index Mode is used to access an array whose elements are in successive memory locations (or) contiguous memory locations.
Question 281 
e = i+n  
e = i+2n  
e = 2i+n  
e = 2^{n}+i 
→ The root has path length zero and the maximum path length in a tree is called the tree's height.
→ The sum of the path lengths of a tree's internal nodes is called the internal path length and the sum of the path lengths of a tree's external nodes is called the external path length.
External Path Length:
The sum over all external (square) nodes of the lengths of the paths from the root of an extended binary tree to each node. For example, in the tree above, the external path length is 25 (Knuth 1997, pp. 399400). The internal and external path lengths are related by
E = I + 2n,
where n is the number of internal nodes.