Data Structures

1.What do you mean by data structure ?

Data structure is a mechanism which is used to arrange the element in a systematic way and also define the relationship between them.

Data structure is used to analyze the algorithms on the basis of time and space.

Some examples of data structure are Arraylist,LinkedList,HashMap etc.

2.List the area where data structure is used .

Compiler design

Operating system

Database management system

Graphics

Artificial intelligent

Numerical analysis

Simulation

Statistical analysis package

3.Example the types of data structure .

There are two types of data structure.

A.linear data structure

B.non-linear data structure

A.linear data structure

A data structure is said to be linear data structure if the elements are arranged in a sequential or linear fashion.

Example :Array,stack,queue,

2.non-linear data structure

A data structure is said to be non-linear data structure if the elements are arranged in a non-sequential or non-linear fashion.

Example:

Tree,Graph

4. List the name of data structure which are used in the following areas: RDBMS,Network data model & Hierarchical data model.

RDBMS=Array

Network data model=Graph

Hierarchical data model.=Tree

5.What do you mean by array ?

Array is a collection of similar data types/elements in which elements are stored in  contiguous memory locations.

Example

Int arr[10];

6.What do you mean by linked-list ?

Linked list is a sequence of nodes where each node contains two part “data/information part”  and “link/pointer part”.

Data/information part contains the information about the data.

Link/pointer part contains the address of the next node.

7.What do you mean by stack ?

It is a linear data structure in which data is inserted and removed from the only one end known as Top.

When element is inserted into the stack then this operation is known as “push”.

When element is removed from the stack then this is known as “pop”.

It is known as LIFO(Last in first out)

8.What do you mean by queue ?

It is a linear data structure in which elements are inserted from one end and removed from the other end.

When elements are inserted into the queue then this operation is known as  rear or tail.

When elements are removed from the queue then this operation is known as front or head.

It is also known as FIFO(First in first out).

9.when we can say stack is overflow 

Top=Maxsize-1

10.What are the common operations that can be performed in data structure ?

There are various operations can be performed in data structure

1.Insertion=adding the element

2.Deletion=remove the element

3.Traversal=printing the element

4.searching=search the specific element

5.sorting=arrange the elements in ascending or descending order

11.What do you mean Tree ?

A tree is minimal connected graph which does not contain loops and circuits

12. What do you mean by Binary Tree ?

It is a special type of tree which contains at most two children ie 0,1,or 2.

13.what are infix ,prefix and postfix notations ?

Infix notation=When  operators are used between the operands then this notation is known as infix notation.

Example:X+Y,Here X & Y are the operands and + is a operator.

The expression can be written as

  A+(B*C)+D

Prefix notation(Polish notation)=When operators are used before the operands then this notation is known as prefix notation.

Example: +XY

The expression can be written as 

* / A+B C E

Postfix notation(Reverse polish notation)=When operators are used after the operands then this is known as postfix notation.

Example:XY+

The expression can be written as

A B + C D + *

14.What are the types of linked-list ?

There are generally three types of linked-list

A.Singly linked-list

B.Doubly linked-list

C.Circular linked-list

A.Singly linked-list

In this type of linked-list,every node contains the address or reference  to the next node in the list and last node address has NULL.

Example:

1 ->2 -> 3 ->NULL

C.Doubly linked-list

In this type of linked-list,every node contains the two address or reference.one address/reference points the next node and other points the previous address.

Example:

NULL<-1-<2<->3->4->NULL

C.Circular linked-list

In this type of linked,every node are connected to each.It does not contain NULL at end of the list.The last pointer of last node points to the first.

Example:

2->3->4->5->2

15.What do you mean by sorting ?

Arranging the element is an increasing order or decreasing order.

Example: 1 ->2-> 3 ->4 is an increasing order.

                4->3->2->1 is a  decreasing order.

16. What is AVL tree ?

AVL tree is a self balancing binary search tree.

It is used to find  “ balance factor” by subtracting height of  left subtree to the height of right subtree. 

Balance factor should not have more than 1.

Balance factor(BF)=h(left-subtree)-h(right-subtree);

Note: BF<=1

17.What are the approaches to write algorithms ?

A.Divide and conquer 

B.Greedy approach

C.Dynamic programming

18.List out some examples of divide and conquer

A.merge sort

B.quick sort

C.binary search 

19.List out some example of Greedy approach.

A.Travelling salesman problem

B.kruskal minimum spanning tree

C.prim’s minimum spanning tree

20.List out some example of Dynamic problem

A.Fibonacci number  series

B.Tower of Hanoi

C.project scheduling