Data Structure Interview Questions

1)What is Data Structure?

   a)Data Structure is the way of collecting and organizing the data in such a way that
      we can perform various kind of operations on these data in an effective way.

   b)Some examples of Data Structures are arrays,Linked List,Stack,Queue,etc.,

___________________________________________________________________________

2)What are the types of Data Structures?

     Data Structures are mainly classified into two types:

     a)Linear Data Structure

         i)A Data Structure is called linear if all of its elements are arranged in the
            sequential order.

        ii)In linear Data Structures,the elements are stored in a non-hierarchical way
            where each item has the successors and predecessors except the first and
            last element.

     b)Non-Linear Data Structure

         i)The Non-Linear Data Structure does not form a sequence.

        ii)That is each item (or) element is connected with two (or) more other  items
          in a non-linear arrangement.The data elements are not arranged in the
          sequential structure.

_________________________________________________________________________

3)What are the applications of Data Structure?

      a)Compiler Design

      b)Operating System

      c)Data Base Management System

      d)Numerical Analysis

      e)Graphics

      f)Artificial Intelligence

__________________________________________________________________________

4)What is Stack?

      a)Stack is one of the data structure (or) stack is a container of objects that are inserted
         and   removed according to the LAST IN FIRST OUT principle.

      b)A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of                          elements, with two principal operations:

                   1)push, which adds an element to the collection
               
                   2)pop,which removes the last element that was added.
   
                   3) In stack both the operations of push and pop takes place at the same end that
                        is top of the stack. It can be implemented by using both array and linked list.

     c)Stacks are used for maintaining function calls.

   
      d)we can always remove recursion with the help of stacks. Stacks are also used in
        cases where we have to reverse a word, check for balanced parenthesis and in
        editors where the word you typed the last is the first to be removed when you
         use undo operation. Similarly, to implement back functionality in web browsers.


__________________________________________________________________________

5)What is Queue?

     a)Queue (or) FIFO (first in, first out) is an abstract data type that serves as a collection of
        elements, with two principal operations: enqueue, the process of adding an element to
       the collection  and dequeue, the process of removing the   first element that was added.
        It can be implemented by using both array and linked list.

    b)Queue as the name says is the data structure built according to the queues of bus stop or
       train where the person who is standing in the front of the queue is the first one to get
       the ticket. So any situation where resources are shared among multiple users and served
       on first come first  serve basis. Examples include CPU scheduling, Disk Scheduling.
      Another  application of  queue  is when data is transferred asynchronously between two                        processes. Examples include IO  Buffers, pipes, file IO, etc.

________________________________________________________________________

6)What is Linked List?

      a)Linked List is a very commonly used linear data structure which consists of group of
        nodes in a  sequence.

      b)Each node holds its own data and the address of the next node hence forming a chain
       like   structure.

      c)Linked Lists are used to create trees and graphs.


___________________________________________________________________

7)What are the Advantages of Linked Lists?

     a)They are a dynamic in nature which allocates the memory when required.

     b)Insertion and deletion operations can be easily implemented.

     c)Stacks and queues can be easily executed.

     d)Linked List reduces the access time.

__________________________________________________________________

8)What are the Disadvantages of Linked Lists?

     a)The memory is wasted as pointers require extra memory for storage.

     b)No element can be accessed randomly,it has to access each node sequentially.

     c)Reverse Traversing is difficult in linked list.


__________________________________________________________________

9)What are the Applications of Linked Lists?

      a)Linked lists are used to implement stacks, queues, graphs, etc.

      b)Linked lists let you insert elements at the beginning and end of the list.

      c)In Linked Lists we don't need to know the size in advance.


___________________________________________________________

10)Give real life example of Stack?

       A good real-life example of a stack is the pile of dinner plates that you encounter when
      you eat at the local cafeteria: When you remove a plate from the pile, you take the plate
      on the top of the pile. But this is exactly the plate that was added ("inserted'') most recently
       to the pile by the dishwasher.


_______________________________________________________________

11)What is TREE, why it is being used. Explain all the traversal?

   1)Traversal is a process to visit all the nodes of a tree and may print their values too.
     Because, all  nodes are connected via edges (links) we always start from the root
     (head) node. That is, we cannot randomly access a node in a tree.

   2)A binary tree is a tree data structure in which each node has at most two children,
      which are referred to as the left child and the right child. It is implemented mainly
       using Links.

   3)In a binary tree a node should contain minimum zero sub nodes maximum two sub nodes.

   4)A node which has zero sub nodes those are called as leaf nodes.

   5)Height of the tree--->lower  to upper

   6)Depth of tree---->upper to lower

   7)Height of tree==depth of tree===Level - 1;

   8)Maximum no of nodes at level (L)=2^(L)-1;

   9)Maximum no of nodes in a binary tree=2^(h+1) -1;

 10)Binary tree is represented in different ways

         1)Left justified binary tree

         2)Right justified binary tree

         3)Binary search tree(BST)

 11)A binary tree left sub tree is less than the parent and right sub tree is greater than the parent.

 12)Inorder   - L P R

  13)Preorder - P L R

  14)Post order - L R P 

  15)Binary Search Trees(BSTs) are used to quickly check whether an element is present in
     a set or not. Heap is a kind of tree that is used for heap sort. A modified version of tree
      called Tries is  used in modern routers to store routing information.


_____________________________________________________________________________

12)What are the applications of Tree Data Structure?

       a)Manipulation of Arithmetic Expression

       b)Symbol Table Construction

       c)Syntax Analysis

_____________________________________________________________________________

13)How is an Array different from Linked List?

      a)The size of arrays is fixed,Linked Lists  are dynamic in size.

      b)Inserting and deleting  a new element in an array of elements is expensive,where
         as  both insertion and deletion can easily be done in Linked Lists.

      c)Random access is not allowed in Linked Lists.

      d)Extra Memory Space for pointer is required with each element of the Linked List.

      e)Arrays have better cache locality that can make a pretty big difference in performance.


____________________________________________________________________________