Soundarya Institute of Management and Science
CA-C3T: DATA STRUCTURES
UNIT - I [12 Hours]
Introduction and Overview: Definition, Elementary data organization, Data Structures, data Structures operations,
Abstract data types, algorithms complexity, time-space trade off. Preliminaries: Mathematical notations and
functions, Algorithmic notations, control structures, Complexity of algorithms, asymptotic notations for complexity
of algorithms. Arrays: Definition, Linear arrays, arrays as ADT, Representation of Linear Arrays in Memory,
Traversing Linear arrays, Inserting and deleting, multi-dimensional arrays, Matrices and Sparse matrices.
Two Mark Questions
1. Define data structures.
The organized collection of data and operations is known as Data structures.
Data Structure = Organized data + operations.
It is further defined into two types:
• Primitive Data Structure
• Non-Primitive Data Structure
2. Define ADT.
• Abstract data types are defined as a mathematical model of data objects that make up a data type as
well as the functions that operate on the objects such as lists, stacks, trees and graphs.
Example:- ADT of String is
Declaration : char str[100];
Operations : Length(), Concatenation(), Reverse()……
3. What do you mean by Time complexity and Space complexity?
Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a
function of the length of the input.
Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to
run as a function of the length of the input.
4. Define Sparse matrix.
Matrices which contains high number of zero entries are called Sparse matrices. In simple terms , a
matrix which contains more zero elements than non-zero elements are referred as Sparse matrix.
Ex : 10
00
5. How do you represent linear array in memory?
In memory, all the data items are stored in contiguous memory locations one after the other. Let us
consider an 1-D Array as shown below:
int value[5]={85,98,79,88,90};
Memory Representation of an array with elements ,address and indexes is shown below:
Array name value[0] value[1] value[2] value[3] value[4]
85 98 79 88 90
6. How do you represent multidimensional arrays in memory?
Multidimensional arrays are stored in the memory in the following two ways:
1.Row-Major Representation
Location[i,j]=Base address(A)+{(i*ColSize)+j}*Word Size)
2.Column-Major Representation
Location[i,j]=Base Address(A)+{i+(j*RowSize)}*WordSize)
7. How do you evaluate complexity of algorithm?
The complexity or efficiency of the algorithm can be evaluated by :
• Worst case : It gives the maximum value of T(n) for any possible input.
• Best case : It gives the minimum value of T(n) for any possible input.
• Average case : It gives the expected value of T(n).
Long Answers ( 4M / 5M / 8 M Questions )
1. State different Asymptotic notations.
Asymptotic notations are the mathematical notations used to describe the running time of an algorithm
when the input tends towards a particular value or a limiting value.
There are three asymptotic notations, they are :
• Big Oh(O)
• Big Omega (Ω)
• Big Theta (Θ)
i) Big-Oh notation: Big-Oh (O) notation represents the upper bound of the running time of an algorithm.
Thus, it gives the worst-case complexity of an algorithm.
ii) Omega notation(Ω): Omega notation represents the lower bound of the running time of an algorithm.
Thus, it provides the best case complexity of an algorithm.
iii) Big Theta (Θ) : Theta notation encloses the function from above and below. Since it represents
the upper and the lower bound of the running time of an algorithm, it is used for analyzing the
average-case complexity of an algorithm.
2. Explain various operations performed on Data structure
The various operations can be performed on Data structures are :
i) Insertion − Add a new data item in data structure.
ii) Deletion − Delete an existing data item from the data structure.
iii) Traversal − Access each data item exactly once so that it can be processed.
iv) Searching − Find out the location of the data item if it exists in the data structure
v) Sorting − Arranging the data items in some order.
vi) Merging - It is used to combine the data items of two sorted files into single file in the sorted form.
3. Write ADT of a Array
An array is a fixed-size sequence of elements of the same type.
Declaration : <data type> array_name [S1] [S2]….[Sn]
Basic Operations :
Void insert() – adding element into the list.
Void append() – adding element at the end of the list
Void delete() – remove element from the list.
Void display() – traversing or visiting each and every element in the list.
4. Write a C program to check whether the given matrix is Sparse or not.
// C program to check given matrix is sparse matrix or not
# include<stdio.h>
# include<conio.h>
void main()
{
int mat[10][10],i,j,zcount=0,nzcount=0,r,c,s[50][3],k=0;
clrscr();
printf("\n Enter r & c : ");
scanf("%d %d",&r,&c);
printf("\n Enter matrix elements : ");
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
scanf("%d",&mat[i][j]);
if(mat[i][j] == 0)
zcount++;
else
{
nzcount++;
s[k][0]=i;
s[k][1]=j;
s[k][2]=mat[i][j];
k++;
}
}
}
if(zcount > nzcount)
{
printf("\n SPARSE MATRIX \n");
printf("\n Row Col Val\n");
for(i=0;i<k;i++)
{
for(j=0;j<3;j++)
{
printf("%3d",s[i][j]);
}
printf("\n");
}
}
else
printf("\n NOT A SPARSE MATRIX");
getch();
}
5. Write a C program to traverse an array.
// C program to traverse the array
#include <stdio.h>
// Function to traverse and print the array
void printArray(int* arr, int n)
{
int i;
printf("Array: ");
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void main()
{
int arr[] = { 2, -1, 5, 6, 0, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
printArray(arr, n);
return 0;
}
6. Write a C program to insert and delete an element from an array.
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10
void DISPLAY(int A[ ], int n);
int INSERT(int A[ ], int n);
int DELETE(int A[ ], int n);
void main()
{
int A[MAXSIZE], i, ch, n;
printf(“\n Enter Number of elements in an Array:”);
scanf(“%d”, &n);
printf(“\n Enter %d elements :”, n);
for( i=0; i<n; i++)
scanf(“%d”, &A[ i ]);
while(1)
{
printf(“\n Menu:”);
printf(“\n*************”);
printf(“\n 1.Insert”);
printf(“\n 2.Delete”);
printf(“\n 3.Exit”);
printf(“\n Enter your choice “);
scanf(“%d”, &ch);
switch(ch)
{
Case 1: n=INSERT (A, n);
break;
Case 2: n=DELETE (A, n);
break;
Case 3: exit(1);
default: printf(“\n Invalid Option”);
}
}
}
/* To insert an element into an array */
int INSERT( int A, int n);
{
int LOC, ITEM,i;
if(n==MAXSIZE)
{
printf(‘\n Array is full. Insertion is not possible”);
return n;
}
printf(“\n Enter the Location to Insert an Element :”);
scanf(“%d”, &LOC);
if(LOC > n+1 || LOC < 1)
{
printf(“\n Invalid Location – Insertion not possible”);
return n;
}
printf(“\n Enter the value to Insert :”);
scanf(“%d”, &ITEM);
for( i= n-1; i>=LOC-1; i--)
A[i+1] = A[i];
A[LOC-1] = ITEM;
n=n+1;
printf(“\n The Array after Insertion :”);
DISPLAY(A,n);
return n;
}
/* To delete an element from an Array */
int DELETE(int A[ ], int n);
{
int LOC, ITEM, i;
if (n==0)
{
printf(“\n Array is Empty. Deletion is not possible”);
return n;
}
printf(“\n Enter the Location to Delete an Element:”);
scanf(“%d”, &LOC);
if (LOC > n || LOC < 1)
{
printf(“\n Invalid Location - Deletion is not Possible “);
return n;
}
for( i=LOC -1; i<n-1 ; i++)
A[i]=A[i+1];
n=n-1;
printf(“\n The Array after Deletion:”);
DISPLAY(A,n);
return n;
}
/* To display all the elements in an array */
void DISPLAY(int A[ ],int )
{
int i;
for(i=0;i<n;i++)
printf(“%d”, A[i]);
}
7. Write a C program to find the product of two matrices.
#include<stdio.h>
int main()
{
int A[10][10], B[10][10], C[10][10],i,j,k,m,n,x,y;
printf(“\n Enter Number of Rows and Columns for matrix A:”);
scanf(“%d %d “, &m, &n);
printf(“\n Enter Number of Rows and Columns for matrix B:”);
scanf(“%d %d”, &x, &y);
if(m!=y || n!=x)
{
printf(“\n Multiplication is not possible”);
return 0;
}
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
printf(“Enter the Element [%d][%d] of A:”, i+1, j+1);
scanf(“%d”, A[i][j]);
}
for(i=0;i<n;i++)
for(j=o;j<m;j++)
{
printf(“Enter the element [%d][%d] of B:”, i+1,j+1);
scanf(“%d”, &B[i][j]);
}
for(i=0;i<n;i++)
for(j=0;j<x;j++)
{
C[i][j]=0;
for(k=0;k<y;k++)
C[i][j]=C[i][j] + A[i][k]* B[k][j];
}
printf(“\n \t Product of the two matrices is \n”);
for(i=0;i<m;i++)
{
for(j=0;j<y;j++)
printf(“\t%d”, C[i][j]);
printf(“\n”);
}
return 0;
}
