The physical meaning of the term ‘data structure’ itself explains that data structure pertains to how a particular data item is structured. We are well aware that data may be organized in many different ways. The logical or mathematical description on how the data item is organized is called data structure. At the same time it deals how the data item behaves on being stored in that particular structure. These data items may be organized in different ways, thus defining different data structure. One needs to make choice between these different data models putting in consideration that it should have sufficient structure to reflect the real world data besides being simple enough to be processed efficiently whenever necessary. The data item needs for sure to be stored in the memory of the computer. The data item may be represented in the memory in different ways. This representation of the particular data structure in memory of computer is called ‘Storage Structure’. However data item can still be stored in auxiliary memory. This representation of the storage structure in auxiliary memory is called file structure.
What is algorithm? What are its categories? Describe the properties of algorithm.
An algorithm is a well defined list of steps for solving a particular problem. Or it may be defined as the step by step procedure to solve any problem. In other words it is a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite length of time. These algorithms are written using some English like statements and statements of some programming language like c, c++, java, Pascal.
Algorithms are categorized in two major groups:
1). Iterative: These types of algorithms follow iteration methods. In doing so, they make best use of loops and conditional statements.
2). Recursive: These types of algorithms follow recursive methods. These algorithms divide complex problems to smaller problems of the same type. This can be better said that these algorithms use divide and conquer strategy.
Properties of algorithms:
i) Input: An algorithm must receive some data externally.
ii) Output: An algorithm must produce an output as a result.
iii) Finiteness: An algorithm must terminate after a finite no of steps, i.e. it must not execute infinitely. Operating system is the only algorithm which must work infinitely until we apply some external interrupt.
iv) Definiteness: The steps of the algorithm to be performed must be clear and unambiguous.
v) Effectiveness: An algorithm must be effective enough to perform the steps in the algorithm without applying intelligence.
Describe the whole classification of data structure.
Data structure can be broadly divided in to two groups:
These are the basic data structure which can be directly used or operated on the system. Examples of this type of data structure are integers, characters, string, float, pointers.
B) Non Primitive Data Structure:
This group of data structure is more complex and is derived from primitive type of data structure. It emphasizes on structuring a group of either homogeneous or non homogeneous data items.
Non primitive data structure is again categorized into linear data structure and non linear data structure.
Linear Data Structure: In such data structure processing of data item is possible in linear manner. Stacks and queues are the examples of this type of data structure where data can be processed one by one sequentially.
Non Linear Data Structure: Non linear data structures are those structure in which processing of data like insertion, deletion and traversing is not possible in linear manner. E.g. trees, graphs.
Data Structure can again be classified in to following six types:
1) Array: This is the simplest type of data structure in which a list of finite number of similar data elements is referenced respectively by a set of n consecutive numbers.
2) Linked List: It’s collection of nodes in which each node has two fields. The first part is information part which stores the data and the other one is address of the next node.
3) Stacks: It’s the data structure which follows the LIFO (last In First Out) rule. It’s a linear list in which insertion and deletion can take place only at top. It’s similar to that of pile of plates.
4) Queue: It follows FIFO (first in first out) rule. It’s a linear list of elements in which the insertion can take place at the rear of the list while deletion can take place only at the front of the list. Automobiles waiting to pass through an intersection can be taken as an example where first car in a line is the first to leave.
5) Tree: In this data structure the data items are arranged in a hierarchical manner. It is generally represented by tree like structure in which the tree is turned upside down i.e. roots on top.
6) Graph: This is another type of data structure which contains relationships between pair of elements which may not by necessary hierarchical in nature. So tree can also be considered to be a graph.
No comments:
Post a Comment