Data structure interview question

Q) What is B+ tree?
 Answer:A B+ tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a 'block' or 'node'). In a B+ tree, in contrast to a B-tree, all records are stored at the lowest level of the tree; only keys are stored in interior blocks.
            The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context. Given a storage system with a block size of b, a B+ tree which stores a number of keys equal to a multiple of b will be very efficient when compared to a binary search tree (the corresponding data structure for non-block-oriented storage
contexts).

Q) How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that cycle?
Answer: find_cycle(Node* head)
{
Node* ptr1 = head;
Node* ptr2 = head;
while(ptr1 != NULL && ptr2 != NULL && ptr2->next != NULL)
{
 if(ptr1 == ptr2)
{
 printf("\nClycle present in thr LinkList\n");
 return true;
 }
ptr1 = prt1->next;
ptr2 = ptr2->next->next;
 }
return false;
}


Q)Stack can be described as a pointer. Explain?
Answer:Because stack will contain a head pointer which will always point to the top of the Stack.All Stack Operations are done using Head Pointer. Hence Stack ca be Described as a Pointer


Q) What do you mean by Base case, Recursive case, Binding Time, Run-Time Stack and Tail Recursion?
Answer:These terms are found in Recursion.
1.Base Case:it is the case in recursion where the answer is known,or we can say the termination condition for a recursion to unwind back.For example to find Factorial of num using recursion:

int Fact(int num){

if(num==1 || num==0)//base case
return 1;
else // recursive case:
return num*Fact(num-1);
}

2.Recursive case:It is the case whcih brings us to the
closer answer.

Run Time Stack:It is a system stack us to save the frame stack of a function every recursion or every call.This frame stack consists of the return address,local variables and return value if any.

Tail Recursion:The case where the function consist of single recursive call and it is the last statement to be executed.A tail Recursion can be replace by iteration. The above funtion consists of tail recursion case.where as the below function does not.

void binary(int start,int end,int el){
int mid;
if(end>start){
mid=(start+end)/2;
if(el==ar[mid])
return mid;
else{
if(el>ar[mid])
binary(mid+1,end,ele);
else
binary(start,mid-11,ele);
}
}
}

Q) What are the methods available in storing sequential files ?
Answer:> Straight merging,
  >Natural merging,
  >Poly phase sort,
  >Distribution of Initial runs.

Q) What is the bucket size, when the overlapping and collision occur at same time?
Answer:One. If there is only one entry possible in the bucket, when the collision occurs, there is no way to accommodate the colliding value. This results in the overlapping of values.

Q) Of the following tree structure, which is, efficient considering space and time complexities?
(a) Incomplete Binary Tree
(b) Complete Binary Tree
(c) Full Binary Tree
(d) Complete Binary Tree.
Answer:
By the method of elimination:
Full binary tree loses its nature when operations of insertions and deletions are done. For incomplete binary trees, extra storage is required and overhead of NULL node checking takes place. So complete binary tree is the better one since the property of complete binary tree is maintained even after operations like additions and deletions are done on it.

Q)  List out few of the applications that make use of Multilinked Structures?
Answer:
> Sparse matrix,
 >Index generation.

Q) In an AVL tree, at what condition the balancing is to be done?
Answer:If the ‘pivotal value’ (or the ‘Height factor’) is greater than 1 or less than –1.