UNIT 1 DS Ai& ds

Download as docx, pdf, or txt
Download as docx, pdf, or txt
You are on page 1of 19

DATA STRUCTURES

UNIT-I

4 MARKS

1. Define data and mention its types

Data is derived from a Latin word “datum” which means collection. So, data can be defined as
collection of facts and figures. A data item refers to a single unit of values. Data is classified into two
types:
1. Group data item
Data item that can be subdivided into different segments is called group data item. For
example: name is a group data item because it can be subdivided into different segments, i.e. first
name, middle name and last name.
2. Elementary data item
The data item that cannot be subdivided into different segments is called elementary
data item. For example: account no, ID number, etc
 Field
 Record
 File
 Data item
 Attribute and entity
 Entity set
 Elementary item
 Data

2. Describe non –linear data structure


 When the data is to be stored in the computer memory in dispersed order, it is called as non-
linear data structure.
 Non-Linear data structure is opposite to linear data structure.
 In non-linear data structure, the data values are not arranged in order and a data item is connected
to several other data items.
 It uses memory efficiently. Free contiguous memory is not required for allocating data items.
 It includes trees and graphs.

3. Define data structure and mention the need for data structure

 Data structure is a way of organizing all data types in order to represent the logical
relationship between existing elements of data.

 In other words, data Structure is a systematic way to organize data in order to use it efficiently.

Characteristics of a Data Structure:


1. Correctness − Data Structure implementation should implement its interface correctly.
2. Time Complexity − Running time or execution time of operations of data structure must be
as small as possible.
3. Space Complexity − Memory usage of a data structure operation should be as little as
possible.
Need for Data Structure:

 Data Search − Consider an inventory of 1 million (106) items of a store. If application is to


search an item. It has to search item in 1 million (106) items every time slowing down the
search. As data grows, search will become slower.
 Processor speed − Processor speed although being very high, falls limited if data grows to
billion records.
 Multiple requests − As thousands of users can search data simultaneously on a web server,
even very fast server fails while searching the data.

4. Draw the classification diagram of data structure

DATA STRUCTURES

Primitive Non-primitive
or
composite

Integer, float & double,


character, string, Boolean

Linear Non-Linear

Array linked list Stack Queue Graph Tree

5. Define array and its types.

An array is a set of finite number of data items of same type. It means an array can contain one
type of data only, either all integers , all floating numbers or all characters. It is stored in consecutive
memory locations.
In other words Array is a group of related data items,that share a common name with same data
type. An individual variable in the array is called an array element.
We can define an arrayname, rollno to represent a set of roll numbers of a group of students.
A particular value is indicated by a number called index number.
An index number is present in brackets after array name.

The general format is : type variable - name[size];


int mark [7]

Array size
Array name
Data type of array elements
Example:

M[0 M[1] M[2] M[3 M[4] M[5] M[6]


] ]
Mark

2300 2302 2304 2306 2308 2310 2312

The types of arrays used:


 One dimensional array
 Two dimensional array
 Multi dimensional array

6 MARKS

1. Write a note on primitive data structure


 Primitive data types are the data types available in most of the programming languages.
 These data types are used to represent single value.
 It is a basic data type available in most of the programming language.

Data type Description


Integer This is used to represent a number without decimal point
eg: 12, 90
Float and Double This is used to represent a number with decimal point
eg: 45.1 , 67.3
Character This is used to represent a single character within single quotes
eg: ‘c’, ‘a’
String This is used to represent single character within a double quotes
eg: “DR.M.G.R.UNIVERSITY
Boolean This is used to represent logical values either true or false

2. List out the various operations of data structure


The data appearing in our data structure is processed by means of certain operations. In fact the
particular data structure that one chooses for a given situation depends largely on the frequency with
which specific operations are performed. The following operations play a major role:
 Traversing
 Searching
 Sorting
 Insertion
 Deletion
 Merging
 Copying

Traversing:
Accessing each record exactly once so that certain items in the record may be processed. (this
accessing or processing is sometimes called ‘visiting’ the records)

Searching:
Finding the location of the record with a given key value, or finding the locations of all records,
which satisfy one or more conditions.

Sorting:
The arrangement of data in ascending or descending order is called sorting.

Insertion:
Adding new record to structure is called inserting.

Deletions:
Removing a record or set of records from data structures is called deletion process.

Merging:

When two or more than two records are combined, this process is called merging.

Copying:
The creation of duplicate data item is called copying process.

3. Write a note on ADT and its uses

ADT stands for Abstract Data Type.


 It can be defined as a collection of data items together with the operations on the data.
 The word “abstract” refers to the fact that the data and the basic operations defined on it
are being studied independently of how they are implemented.
 It involves what can be done with the data, not how has to be done.
 For ex, in the below figure the user would be involved in checking that what can be done
with the data collected not how it has to be done.

 Abstract data type is a mathematical model of a data structure.


 It is a logical description of how we view the data and the operations allowed without regard
to how they will be implemented.
 ADT concerns only with what the data is representing and not with how it will eventually be
constructed.
 It is a set of objects and operations. For example, List, Insert, Delete, Search, Sort.

 It consists of following three parts:


1. Data
2. Operation
3. Error

1. Data describes the structure of the data used in the ADT.


2. Operation describes valid operations for the ADT. It describes its interface.
3. Error describes how to deal with the errors that can occur.

Advantages of ADT
 ADT is reusable and ensures robust data structure.
 It reduces coding efforts.
 It specifies error conditions associated with operations.

4. What is the basic terminology of elementary data organization?


Data is derived from a Latin word “datum” which means collection. So, data can be defined as
collection of facts and figures. A data item refers to a single unit of values. Data is classified into two
types:
1. Group data item
2. Elementary data item

Elementary data item: The data item that cannot be sub divided into different segments is called
elementary data item.
Example :account no, id number, etc
 Data− Data are values or set of values.
 Data Item − Data item refers to single unit of values. EX : roll number, name, address etc
 Group Items − Data items that are divided into sub items are called as Group Items.
 Elementary Items − Data items that cannot be divided are called as Elementary Items.
 Attribute and Entity − An entity is that which contains certain attributes or properties, which
may be assigned values. For example : student is an entity. The attributes of the student may be
roll number, name ,address etc
 Entity Set – Entities of similar attributes form an entity set.
 Field – Field is a collection of related characters. Field is a single elementary unit of information
representing an attribute of an entity.
 Record − Record is a collection of field values of a given entity.
 File − File is a collection of records of the entities in a given entity set.

5. Define data structures .Mention the characteristics and a need for data structure

 Data structure is a way of organizing all data types in order to represent the logical
relationship between existing elements of data.

 In other words, data Structure is a systematic way to organize data in order to use it efficiently.

 Following terms are foundation terms of a data structure.

Interface -Each data structure has an interface. Interface represents the set of operations that a data
structure supports. An interface only provides the list of supported operations, type of parameters they
can accept and return type of these operations.
Implementation − Implementation provides the internal representation of a data structure.
Implementation also provides the definition of the algorithms used in the operations of the data
structure.

Characteristics of a Data Structure:


 Correctness − Data structure implementation should implement its interface correctly.
 Time Complexity − Running time or the execution time of operations of data structure must be
as small as possible.
 Space Complexity − Memory usage of a data structure operation should be as little as possible.

Need for Data Structure:


 As applications are getting complex and data rich, there are three common problems that
applications face now-a-days.
 Data Search − Consider an inventory of 1 million (106) items of a store. If the application is to
search an item, it has to search an item in 1 million (106) items every time slowing down the
search. As data grows, search will become slower.
 Processor speed − Processor speed although being very high, falls limited if the data grows to
billion records.
 Multiple requests − As thousands of users can search data simultaneously on a web server, even
the fast server fails while searching the data.

10 MARKS

1. Explain the types of data structures in detail

Types of Data Structure

DATA STRUCTURES

Primitive Non-primitive
or
composite

Integer, float & double,


character, string, Boolean

Linear Non-Linear

Array linked list Stack Queue Graph Tree

A. Primitive Data Type:

 Primitive data types are the data types available in most of the programming languages.
 These data types are used to represent single value.
 It is a basic data type available in most of the programming language.

Data type Description


Integer This is used to represent a number without decimal point
eg: 12, 90
Float and Double This is used to represent a number with decimal point
eg: 45.1 , 67.3
Character This is used to represent a single character within single quotes
eg: ‘c’, ‘a’
String This is used to represent single character within a double quotes
eg: “DR.M.G.R.UNIVERSITY
Boolean This is used to represent logical values either true or false

B. Non-Primitive Data Type:


 Data type derived from primary data types are known as Non-Primitive data types.
 It is also known as composite data type
 Non-Primitive data types are used to store group of values.
 It can be divided into two types:

1. Linear Data Structure


2. Non-Linear Data Structure

1. Linear Data Structure

 when the data is to be stored in the memory in linear form, it is called as linear data structure
 Linear data structure traverses the data elements sequentially.
 In linear data structure, only one data element can directly be reached.
 It includes array, linked list, stack and queues.

Types Description
Arrays Array is a collection of elements. It is used in mathematical problems like matrix,
algebra, etc. Each element of an array is referenced by a subscripted variable or
value, called subscript or index enclosed in parenthesis.
Linked list Linked list is a collection of data elements. It consists of two parts: Info and link.
Info gives information and link is an address of next node. Linked list can be
implemented by using pointers
Stack Stack is a list of elements. In stack, an element may be inserted or deleted at one end
which is known as top of the stack. It performs two operations: push and pop. push
means adding an element in stack and pop means removing an element in stack. It is
also called Last-in-First-Out (LIFO).
Queue Queue is a linear list of element. In queue, elements are added at one end called rear
and the existing elements are deleted from other end called front. It is also called as
First-in-First-out (FIFO)

2. Non-Linear Data Structure


 When the data is to be stored in the computer memory in dispersed order, it is called as non-
linear data structure.
 Non-Linear data structure is opposite to linear data structure.
 In non-linear data structure, the data values are not arranged in order and a data item is connected
to several other data items.
 It uses memory efficiently. Free contiguous memory is not required for allocating data items.
 It includes trees and graphs.

Type Description
Tree Tree is a flexible, versatile and powerful non-linear data structure. It is used to represent
data items processing hierarchical relationship between the grandfather and his children &
grandchildren. It is an ideal data structure for representing hierarchical data.
Graph Graph is a non-linear data structure which consists of a finite set of ordered pairs called
edges. Graph is a set of elements connected by edges. Each elements are called a vertex
and node.

2. Brief the types Asymptotic or mathematical notations


Asymptotic or mathematical notations

Asymptotic analysis of an algorithm, refers to defining the mathematical boundation/framing of


its run-time performance. Using asymptotic analysis, we can very well conclude the best
case,average case and worst case scenario of an algorithm.

Asymptotic analysis are input bound i.e., if there's no input to the algorithm it is concluded to
work in a constant time. Other than the "input" all other factors are considered constant.

Asymptotic notations are terminology that is introduced to enable us to make meaningful


statements about the time and space complexity of an algorithm.

Usually, time required by an algorithm falls under three types –

Best Case − Minimum time required for program execution.

Average Case − Average time required for program execution.

Worst Case − Maximum time required for program execution.

The different notations are:


 Big- Oh notation
 Omega notation
 Theta notation

Big- Oh notation:
A function t(n) is said to be ain O(g(n)) denoted t(n) ε O(g(n)), if t(n) is bounded above
by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c and
some non negative integer n0 such that
T(n)≤c g(n) for n≥n0

Omega notation(Ω notation)


A function t(n) is said to be in Ω(g(n)), denoted t(n) € (g(n)), if t(n)is bounded below by
some positive constant multiple of g(n) for all large n, i.e., if there exist some positive constant c
and some non negative integer n0 such that
T(n)≤c g(n) for n≥n0

Theta notation (θ-notation)


A function t(n) is said to be in θ g(n), denoted t(n)€ θ (g(n)), if t(n) is bounded both above
and below by some positive constant multiples of g(n) for all large n, i.e., if there exists some
positive constant c1 and c2 and some non negative integer n0 such that
C2 g(n) ≤ t(n) ≤c1 g(n) for n≥n0
3.Write a program coding for implementation of PUSH,POP operations for stack using arrays
with a sample output

public class StackUsingArray {


private int[] stack;
private int top;
private int maxSize;

// Constructor to initialize stack


public StackUsingArray(int size) {
stack = new int[size];
top = -1;
maxSize = size;
}

// PUSH operation
public void push(int element) {
if (top < maxSize - 1) {
stack[++top] = element;
System.out.println("PUSHED: " + element);
} else {
System.out.println("STACK OVERFLOW");
}
}

// POP operation
public int pop() {
if (top >= 0) {
System.out.println("POPPED: " + stack[top--]);
return stack[top + 1];
} else {
System.out.println("STACK UNDERFLOW");
return -1;
}
}

// Print stack elements


public void printStack() {
if (top >= 0) {
System.out.println("STACK ELEMENTS:");
for (int i = 0; i <= top; i++) {
System.out.print(stack[i] + " ");
}
System.out.println();
} else {
System.out.println("STACK IS EMPTY");
}
}

public static void main(String[] args) {


StackUsingArray stack = new StackUsingArray(5);

// PUSH operations
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);

// Print stack
stack.printStack();

// POP operations
stack.pop();
stack.pop();
stack.pop();

// Print stack
stack.printStack();

// Attempt to pop beyond empty stack


stack.pop();
stack.pop();
stack.pop();
}
}

Output:

PUSHED: 10
PUSHED: 20
PUSHED: 30
PUSHED: 40
PUSHED: 50
STACK ELEMENTS:
10 20 30 40 50
POPPED: 50
POPPED: 40
POPPED: 30
STACK ELEMENTS:
10 20
POPPED: 20
POPPED: 10
STACK UNDERFLOW
STACK UNDERFLOW
STACK IS EMPTY

4. Explain linear and non – linear data structure.

DATA STRUCTURES

Primitive Non-primitive
or
composite

Integer, float & double,


character, string, Boolean

Linear Non-Linear

array Linked list Stack Queue Graph Tree

1.Linear Data Structure


 when the data is to be stored in the memory in linear form, it is called as linear data structure
 Linear data structure traverses the data elements sequentially.
 In linear data structure, only one data element can directly be reached.
 It includes array, linked list, stack and queues.

Array:
An array is a set of finite number of data items of same type. It means an array can
contain one type of data only, either all integers , all floating numbers or all characters. It is
stored in consecutive memory locations.
The general format is : type variable - name[size];

int mark [7]

Array size
Array name
Data type of array elements
Example:
M[0] M[1] M[2] M[3] M[4] M[5] M[6]
Mar
k
2300 2302 2304 2306 2308 2310 2312

The types of arrays used:


 One dimensional array
 Two dimensional array
 Multi dimensional array

Linked list:
A linked list, or an one-way list, is a linear collection of data element, called nodes,
where the linear order is given by means of pointers. That is, each node is divided into two
parts.
 The first part contains the information of the element i.e., INFO or DATA.
 The second part contains the link field, which contains the address of the next node in
the list.
NODE
INFO LINK
 The linked list consists of a series of nodes, which are not necessarily adjacent in the
memory.
Example: The linked list with 4 nodes.

7
5 8 9
Start
Or
Head Info field Link field

Stack:
A stack is a linear data structure, also called a last in first-out (LIFO) system , in which
insertions and deletions can take place only at one end, called top. i.e., the elements are
removed from the stack in then reverse order of that in which they were inserted into the stack.
A stack is a limited access data structure-elements can be added and removed from the stack
only at the top.
A stack consists of two operations:
a) Push
b) Pop
Push: It adds the element into the stack
Pop: It removes the element from the stack

push pop

top

Queue:
A queue is a linear data structure which is also called a first-in first-out (FIFO) system,
since the first element in queue will be the first element out of the queue.
In queue deletions can take place only at one end of the list, the “front” of the list, and
insertions can take place at other end of the list, the “rear” of the list.
The front and rear are two terms used to represent the two ends of the list when it is
implemented as queue.
Eg: This structure operates in much the same way as a line of people waiting at a bus
stop. The first person in line is the first person to board the bus. Another analogy is with
automobiles waiting to pass through an intersection- the first car in line is the first car through.
Dequeue(Deletion)

Enqueue(Insertion)

Front rear

2.Non-Linear data structure

 When the data is to be stored in the computer memory in dispersed order, it is called as non-
linear data structure.
 Non-Linear data structure is opposite to linear data structure.
 In non-linear data structure, the data values are not arranged in order and a data item is connected
to several other data items.
 It uses memory efficiently. Free contiguous memory is not required for allocating data items.
 It includes trees and graphs.

Graph:
A graph is a non-linear data structure, which is having a point to point
relationship among the nodes. Each node of the graph is called a vertex and link or line
between them is called and edge.
A graph G is an ordered pair of sets (V,E) where V is a set of vertices and E is a set of
edges.
V={v1, v2,....,vn} is a set of vertices
E={e1,e2,.....,em} is a set of edges

V1 node
e1 e2
e5
V2 V3 V5

e3 e4 edge
V4

In this graph V={v1,v2,v3,v4,v5}


The edges are E={e1,e2,e3,e4,e5}

Tree:
Its is a non-linear data structure. The tree is used to represent the hierarchical relationship
between the data items.
Tree is a data structure that is hierarchical in nature.
A tree, is a finite set of nodes together with a finite set of directed edges that define parent-child
relationships.
Each directed edges that define parent-child relationships. Each directed edge connects a parent
to its child.

For example,

E B

D C F H G

Nodes={A,B,C,D,E,F,G,H}
Edges={(A,B),(A,E),(B,F),(B,G),(B,H),(E,C),(E,D)}

5. Explain in detail about the operations of data structure


The data appearing in our data structure is processed by means of certain operations. In fact the
particular data structure that one chooses for a given situation depends largely on the frequency with
which specific operations are performed. The following operations play a major role:
 Traversing
 Searching
 Sorting
 Insertion
 Deletion
 Merging
 Copying
Traversing:
Accessing each record exactly once so that certain items in the record may be processed (this
accessing or processing is sometimes called ‘visiting’ the records). For example to display all the
elements of an array, every element is visited once and only once, so it is called traversing operation.
EX :Suppose we have an array of 20 students average marks, and if we need to calculate the
average of group, we visit (read) each individual average and accumulate (sum) them. Then we will
find the array are visited once and only once. Then it is traversing of an array.
Searching:
Finding the location of the record with a given key value, or finding the locations of all records,
which satisfy one or more conditions. searching can be done using either ‘linear search’ or ‘binary
search’.

EX: Suppose we have an array of size 10 and assume elements stored are 1,2,3,23,34,54,56,21,32,33
and assume we want to search the number 23. So here the number 23 is key element. The key is
searched through the array starting from the first element till end. When it is compared with the fourth
element in it is present in the list (array) of numbers. So search is successful. This type of searching is
called linear search. In order to apply linear search, the list may not be in any particular order but when
binary search is applied the list must be ordered one.

Sorting:
The arrangement of data in ascending or descending order is called sorting. The sorting can be
done using insertion, selection or bubble sort technique.

EX : Suppose we have an array of size 10 and assume elements stored are 1,2,3,23,34,54,56,21,32,33.
The elements of the array are not in proper order. If they are arranged in ascending order the list
(array) becomes 1,2,3,21,23,32,34,54,56.

Insertion:
Adding new record to structure is called inserting. The element can be added anywhere in the
data structure.

EX: Suppose we have an array of size 20 used to store marks obtained by the students in computer
science subject. If we have already added 15 students marks according to an ascending order, then we
can add another student marks at appropriate place, by shifting the already stored element accordingly.
Then it is called insertion operation.

Deletion:
Removing a record or set of records from data structures is called deletion process. We can
delete an element from data structure from any position
.
EX : Suppose we have an array of size 20 used to store marks obtained by the students in
computer science subject. If we have already added 15 students marks according to an ascending
order, then we can delete one students marks from any place, by shifting the already stored elements
accordingly. Then it is called deletion process.

Merging:
When two or more than two records are combined, this process is called merging.

EX : Suppose we have a list of size 6, containing the elements 1,2,3,4,71,87 and we have
another list of size 5, containing the elements 9,13,21,65,67. Here both the list are in ascending order.
We can produce the third list of size 11 that will also be in ascending order, containing the element
1,2,3,4,9,13,21,65,67,71,87. The third list is called the merged list of the first and second lists. In order
to merge two lists into single list one needs to compare each element from both the lists and one of
them will go to the merged list.

Copying:
The creation of duplicate data item is called copying process. All data structures can copied.

You might also like