Data Structures – B24CS34

MODULE 1

INTRODUCTION TO DATA STRUCTURES

Q1) Define Data Structure.

A data structure is basically a group of data elements that are put together under one name, and
which defines a particular way of storing and organizing data in a computer so that it can be
used efficiently.

Data structures are used in almost every program or software system. Some common examples
of data structures are arrays, linked lists, queues, stacks, binary trees, and hash tables. Data
structures are widely applied in the following areas:

 Compiler Design
 Operating System
 Statistical Analysis Package
 Numerical Analysis
 Artificial Intelligence
 DBMS (Data Base Management Systems)
 Simulation
 Graphics

Q2) What are the steps to be followed while selecting a data structure to solve a problem?

When selecting a data structure to solve a problem, the following steps must be performed.

1. Analysis of the problem to determine the basic operations that must be supported. For
example, basic operation may include inserting/deleting/searching a data item from the data
structure.
2. Quantify the resource constraints for each operation.
3. Select the data structure that best meets these requirements.

Q3) Explain the different types of data structures with an example?

Data structures are generally categorized into two classes: primitive and non-primitive data
structures.
Primitive and Non-Primitive Data Structures:
Primitive data structures are the fundamental data types which are supported by a
programming language. Some basic data types are integer, real, character, and boolean. The
terms ‘data type’, ‘basic data type’, and ‘primitive data type’ are often used interchangeably.
Non-primitive data structures are those data structures which are created using primitive
data structures. Examples of such data structures include linked lists, stacks, trees, and graphs.
Non-primitive data structures can further be classified into two categories: linear and
non-linear data structures.

ISE, DBIT Page 1

Data Structures – B24CS34

Linear and Non-linear Structures:

If the elements of a data structure are stored in a linear or sequential order, then it is a linear
data structure. Examples include arrays, linked lists, stacks, and queues. Linear data structures
can be represented in memory in two different ways. One way is to have to a linear
relationship between elements by means of sequential memory locations. The other way is to
have a linear relationship between elements by means of links.
However, if the elements of a data structure are not stored in a sequential order, then it
is a non-linear data structure. The relationship of adjacency is not maintained between
elements of a non-linear data structure. Examples include trees and graphs.

Q4) Discuss the different operations that can be performed on various data structures.

The different operations that can be performed on the various data structures are as follows.

Traversing: It means to access each data item exactly once so that it can be processed. For
example, to print the names of all the students in a class.

Searching: It is used to find the location of one or more data items that satisfy the given
constraint. Such a data item may or may not be present in the given collection of data items.
For example, to find the names of all the students who secured 100 marks in mathematics.

Inserting: It is used to add new data items to the given list of data items. For example, to add
the details of a new student who has recently joined the course.

Deleting: It means to remove (delete) a particular data item from the given collection of data
items. For example, to delete the name of a student who has left the course.

Sorting: Data items can be arranged in some order like ascending order or descending order
depending on the type of application. For example, arranging the names of students in a class
in an alphabetical order, or calculating the top three winners by arranging the participants’
scores in descending order and then extracting the top three.

Merging: Lists of two sorted data items can be combined to form a single list of sorted data
items.

Q5) What is an abstract data type in data structures? What are the advantages of using
ADTs?

An abstract data type (ADT) is the way we look at a data structure, focusing on what it does
and ignoring how it does its job. For example, stacks and queues are perfect examples of an
ADT. We can implement both these ADTs using an array or a linked list.

Data type: Data type of a variable is the set of values that the variable can take. The basic data
types used in C are int, char, float, and double.

ISE, DBIT Page 2

Data Structures – B24CS34

Abstract: The word ‘abstract’ in the context of data structures means considered apart from
the detailed specifications or implementation.

In C, an abstract data type can be a structure considered without regard to its implementation.
It can be thought of as a ‘description’ of the data in the structure with a list of operations that
can be performed on the data within that structure.

The end-user is not concerned about the details of how the methods carry out their tasks. They
are only aware of the methods that are available to them and are only concerned about calling
those methods and getting the results. They are not concerned about how they work.

The advantages of using ADTs are:

In the real world, programs evolve as a result of new requirements or constraints, so a

modification to a program commonly requires a change in one or more of its data structures.
For example, if we want to add a new field to a student’s record to keep track of more
information about each student, then it will be better to replace an array with a linked structure
to improve the program’s efficiency. In such a scenario, rewriting every procedure that uses
the changed structure is not desirable. Therefore, a better alternative is to separate the use of a
data structure from the details of its implementation. This is the principle underlying the use of
abstract data types.

Q6) Explain the key features of ADT?

Abstract data types (ADTs) are a way of encapsulating data and operations on that data into a
single unit. Some of the key features of ADTs include:
 Abstraction: The user does not need to know the implementation of the data structure
only essentials are provided.
 Better Conceptualization: ADT gives us a better conceptualization of the real world.
 Robust: The program is robust and has the ability to catch errors.
 Encapsulation: ADTs hide the internal details of the data and provide a public interface
for users to interact with the data. This allows for easier maintenance and modification of
the data structure.
 Data Abstraction: ADTs provide a level of abstraction from the implementation details
of the data. Users only need to know the operations that can be performed on the data, not
how those operations are implemented.
 Data Structure Independence: ADTs can be implemented using different data
structures, such as arrays or linked lists, without affecting the functionality of the ADT.
 Information Hiding: ADTs can protect the integrity of the data by allowing access only
to authorized users and operations. This helps prevent errors and misuse of the data.
 Modularity: ADTs can be combined with other ADTs to form larger, more complex data
structures. This allows for greater flexibility and modularity in programming.

ISE, DBIT Page 3

Data Structures – B24CS34

Q7) Write a ADT for Arrays.

structure Array is
objects: A set of pairs where for each value of index there is a value from the set
item. Index is a finite ordered set of one or more dimensions, for example, {0, • • •
, n-1} for one dimension, {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2,
2)) for two dimensions, etc.
functions:
for all A € Array, i € index, x € item, j, size € integer.
Array Create(j, list) ::= return an array of j dimensions where list
is a j-tuple whose ith element is the size
of the ith dimension. Items are undefined.
Item Retrieve(A, i) ::= if (I € index) return the item associated
with index value i in array A.
else return error.
Array Store(A,i,x) ::= if (i in index)
return an array that is identical to array A
except the new pair <i, x> has been inserted.
else return error.
end Array

Q8) What is a sparse matrix? Give the representation of sparse matrix using structures?
Give the representation of sparse matrix and its transpose stored as triples?

A sparse matrix is a matrix that has very few non-zero elements spread out thinly. The
remaining elements of the matrix are considered to be 0’s. Thus, a matrix with few non-zero
elements (ie. more number of zeros) is called sparse matrix.

The sparse matrix can be single dimensional or multi-dimensional such as two-dimensional,

three-dimensional and so on.

ISE, DBIT Page 4

Data Structures – B24CS34

Sparse Matrix Representation:

#define MAX_TERMS 101

typedef struct
{
int row, col, value;
}TERM;
TERM a[MAX_TERMS};

Representation of Sparse Matrix using triples in a single dimension array:

There are two ways to represent the sparse matrix that are listed as follows -
 Array representation
 Linked list representation

Array representation of the sparse matrix

Representing a sparse matrix by a 2D array leads to the wastage of lots of memory. This is
because zeroes in the matrix are of no use, so storing zeroes with non-zero elements is wastage
of memory. To avoid such wastage, we can store only non-zero elements. If we store only non-
zero elements, it reduces the traversal time and the storage space.

In 2D array representation of sparse matrix, there are three fields used that are named as:
 Row - It is the index of a row where a non-zero element is located in the matrix.
 Column - It is the index of the column where a non-zero element is located in the matrix.
 Value - It is the value of the non-zero element that is located at the index (row, column).

ISE, DBIT Page 5

Data Structures – B24CS34

ISE, DBIT Page 6

Data Structures – B24CS34

Program 1: Write a program in C to search a given item in a sparse matrix.

#define MAX_TERMS 101
#include<stdio.h>
#include<conio.h>
typedef struct
{
int row; int col; int value;
}TERM;
void main()
{
TERM a[MAX_TERMS]; int i,key,flag=0;
clrscr();
printf("Enter the order of the matrix:");
scanf("%d%d",&a[0].row,&a[0].col);
printf("Enter the number of values:");
scanf("%d",&a[0].value);
printf("Enter the row number, col number and value:\n");
for(i=1;i<=a[0].value;i++)
{
scanf("%d%d%d",&a[i].row,&a[i].col,&a[i].value);
}
printf("The contents of the Sparse Matrix is\n");
printf("ROW\tCOLUMN\tVALUE\n");
for(i=0;i<=a[0].value;i++)
{
printf("%d\t%d\t%d\n",a[i].row,a[i].col,a[i].value);
}
printf("Enter the element to be searched:");
scanf("%d",&key);
for(i=1;i<=a[0].value;i++)
{
if(key==a[i].value)
{
flag=1;
break;
}
}
if(flag==0)
{
printf("Search is unsuccessful\n");
printf("Key element is not present");
}
else
{
printf("Search is successful\n");
printf("Key element is present");
}
getch();
}
ISE, DBIT Page 7
Data Structures – B24CS34

Program 2: Write program in C to transpose a given sparse matrix.

#define MAX_TERMS 101
#include<stdio.h>
#include<conio.h>
typedef struct
{
int row;
int col;
int value;
}TERM;
void transpose(TERM[],TERM[]);
void main()
{
TERM a[MAX_TERMS], b[MAX_TERMS];
int i,key;
clrscr();
printf("Enter the order of the matrix:");
scanf("%d%d",&a[0].row,&a[0].col);
printf("Enter the number of values:");
scanf("%d",&a[0].value);
printf("Enter the row number, col number and value:\n");
for(i=1;i<=a[0].value;i++)
{
scanf("%d%d%d",&a[i].row,&a[i].col,&a[i].value);
}
printf("The contents of the Sparse Matrix is\n");
printf("ROW\tCOLUMN\tVALUE\n");
for(i=0;i<=a[0].value;i++)
{
printf("%d\t%d\t%d\n",a[i].row,a[i].col,a[i].value);
}
transpose(a,b);
printf("The contents of the Transpose of a Sparse Matrix is\n");
printf("ROW\tCOLUMN\tVALUE\n");
for(i=0;i<=b[0].value;i++)
{
printf("%d\t%d\t%d\n",b[i].row,b[i].col,b[i].value);
}
getch();
}

void transpose(TERM a[MAX_TERMS],TERM b[MAX_TERMS])

{
int i,j,n,currentb;
n=a[0].value;
b[0].row=a[0].col;
b[0].col=a[0].row;
b[0].value=n;
ISE, DBIT Page 8
Data Structures – B24CS34

if(n>0)
{
currentb=1;
for(i=0;i<a[0].col;i++)
{
for(j=1;j<= n;j++)
{
if(a[j].col==i)
{
b[currentb].row=a[j].col;
b[currentb].col=a[j].row;
b[currentb].value=a[j].value;
currentb++;
}
}
}
}
}

Q9) Write an ADT for Sparse Matrix.

structure Sparse-Matrix is
objects: a set of triples, , where row and column are integers and form a unique
combination, and value comes from the set item.
functions:
for all a,be Sparse-Matrix, x e item, i, j, max-col, max-row g index.
Sparse-Matrix Crcate(max-row, max-col) ::= return a Sparse-Matrix that can hold up
to max—items = max—row X max-col
and whose maximum row size is max-
row and whose maximum column size is
max-col.
Sparse-Matrix Transpose(a) ::= return the matrix produced by
interchanging the row and column value
of every triple.
Sparse-Matrix Add(fl, b} ::= if the dimensions of a and b are the same
return the matrix produced by adding
corresponding items, namely those with
identical row and column values.
else return error.
Sparse-Matrix Multiply(a, b) ::= if number of columns in a equals number
of rows in b.
return the matrix d produced by
multiplying a by b according to the
formula:
d[i][j] = (a[i][k] . b[k][j]), where d(i, j)
is the (i, j)th element.
else return error.
end Sparse-Matrix.
ISE, DBIT Page 9
Data Structures – B24CS34

Q10) Explain the merge sorting technique with an example.

The Merge Sort algorithm is a divide-and-conquer algorithm that sorts an array by first
breaking it down into smaller arrays, and then building the array back together the correct way
so that it is sorted.
Divide: The algorithm starts with breaking up the array into smaller and smaller pieces until
one such sub-array only consists of one element.
Conquer: The algorithm merges the small pieces of the array back together by putting the
lowest values first, resulting in a sorted array.
The breaking down and building up of the array to sort the array is done recursively.
The working of Merge Sort algorithm is described as follows:
1. Divide the unsorted array into two sub-arrays, half the size of the original.
2. Continue to divide the sub-arrays as long as the current piece of the array has more than
one element.
3. Merge two sub-arrays together by always putting the lowest value first.
4. Keep merging until there are no sub-arrays left
Example: Sort the given array [12, 8, 9, 3, 11, 5, 4] using Merge Sort technique.

ISE, DBIT Page 10

Data Structures – B24CS34

Program 3: Develop a C program to sort the elements of an array using Merge sort technique.
#include <stdio.h>
#include <conio.h>
void mergeSort(int arr[], int start, int end);
void merge(int arr[], int start, int mid, int end);
void main()
{
double unsortedArr[] = {3, 7, 6, -10, 15, 23, 55, -13};
int size = sizeof(unsortedArr) / sizeof(unsortedArr[0]);
mergeSort(unsortedArr, 0, size - 1);
printf("Sorted array: ");
for (int i = 0; i < size; i++)
{
printf("%.1f ", unsortedArr[i]);
}
printf("\n");
getch();
}
void mergeSort(int arr[], int start, int end)
{
if (start < end)
{
int mid = (start + end) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
void merge(double arr[], int start, int mid, int end)
{
int i, j, k;
int n1 = mid - start + 1;
int n2 = end - mid;
int left[n1], right[n2];
for (i = 0; i < n1; i++)
left[i] = arr[start + i];
for (j = 0; j < n2; j++)
right[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = start;
while (i < n1 && j < n2)
{
if (left[i] <= right[j])
{
arr[k] = left[i];
i++;
}
else
ISE, DBIT Page 11
Data Structures – B24CS34

{
arr[k] = right[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = left[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = right[j];
j++;
k++;
}
}

OUTPUT:
Sorted array: -13, -10, 3, 6, 7, 15, 23, 55
Q11) Explain the Quick Sorting Technique with an example.

Quick sorting technique is one of the fastest sorting algorithms. The Quicksort algorithm takes
an array of values as input, chooses one of the values as the 'pivot' element, and moves the
other values so that lower values are on the left of the pivot element, and higher values are on
the right of it.

The last element of the array is chosen to be the pivot element, but we could also have
chosen the first element of the array, or any element in the array really. Then, the Quicksort
algorithm does the same operation recursively on the sub-arrays to the left and right side of the
pivot element. This continues until the array is sorted.

After the Quicksort algorithm has put the pivot element in between a sub-array with
lower values on the left side, and a sub-array with higher values on the right side, the algorithm
calls itself twice, so that Quicksort runs again for the sub-array on the left side, and for the
sub-array on the right side. The Quicksort algorithm continues to call itself until the sub-arrays
are too small to be sorted.

ISE, DBIT Page 12

Data Structures – B24CS34

Working of Quick Sort Technique:

1. Choose a value in the array to be the pivot element.
2. Order the rest of the array so that lower values than the pivot element are on the left,
and higher values are on the right.
3. Swap the pivot element with the first element of the higher values so that the pivot
element lands in between the lower and higher values.
4. Do the same operations (recursively) for the sub-arrays on the left and right side of the
pivot element.
Example: Sort the given array [11, 9, 12, 7, 3] using Quick Sort technique.

Step 1: Start with an unsorted array.

[ 11, 9, 12, 7, 3]
Step 2: We choose the last value 3 as the pivot element.
[ 11, 9, 12, 7, 3]
Step 3: The rest of the values in the array are all greater than 3, and must be on the right side
of 3. Swap 3 with 11.
[ 3, 9, 12, 7, 11]
Step 4: Value 3 is now in the correct position. We need to sort the values to the right of 3.
Choose the last value 11 as the new pivot element.
[ 3, 9, 12, 7, 11]
Step 5: The value 7 must be to the left of pivot value 11, and 12 must be to the right of it.
Move 7 and 12.
[ 3, 9, 7, 12, 11]
Step 6: Swap 11 with 12 so that lower values 9 and 7 are on the left side of 11, and 12 is on
the right side.
[ 3, 9, 7, 11, 12]
Step 7: 11 and 12 are in the correct positions. Choose 7 as the pivot element in sub-array
[ 9, 7], to the left of 11.
[ 3, 9, 7, 11, 12]
Step 8: Swap 9 with 7.
[ 3, 7, 9, 11, 12]

Q12) Explain the Radix Sort technique with an example.

The radix (or base) is the number of unique digits in a number system. In the decimal system
we normally use, there are 10 different digits from 0 till 9. Radix Sort uses the radix so that
decimal values are put into 10 different buckets (or containers) corresponding to the digit that
is in focus, then put back into the array before moving on to the next digit.
Note: Radix Sort is a non-comparative algorithm that only works with non-negative integers.
The Radix Sort algorithm can be described like this:

ISE, DBIT Page 13

Data Structures – B24CS34

Radix Sort Implementation:

The implementation of Radix Sort algorithm is as follows:
1. An array with non-negative integers that needs to be sorted.
2. A two dimensional array with index 0 to 9 to hold values with the current radix in focus.
3. A loop that takes values from the unsorted array and places them in the correct position
in the two dimensional radix array.
4. A loop that puts values back into the initial array from the radix array.
5. An outer loop that runs as many times as there are digits in the highest value.
Example: Sort the given array [33, 45, 40, 25, 17, 24] using Radix Sort technique.

Step 1: We start with an unsorted array, and an empty array to fit values with corresponding
radices 0 till 9.
myArray = [ 33, 45, 40, 25, 17, 24]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Step 2: We start sorting by focusing on the least significant digit.
myArray = [ 33, 45, 40, 25, 17, 24]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Step 3: Now we move the elements into the correct positions in the radix array according to
the digit in focus. Elements are taken from the start of myArray and pushed into the correct
position in the radixArray.
myArray = [ ]
radixArray = [ [40], [], [], [33], [24], [45, 25], [], [17], [], [] ]
Step 4: We move the elements back into the initial array, and the sorting is now done for the
least significant digit. Elements are taken from the end radixArray, and put into the start of
myArray.
myArray = [ 40, 33, 24, 45, 25, 17 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Step 5: We move focus to the next digit. Notice that values 45 and 25 are still in the same
order relative to each other as they were to start with, because we sort in a stable way.
myArray = [ 40, 33, 24, 45, 25, 17 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Step 6: We move elements into the radix array according to the focused digit.
myArray = [ ]
radixArray = [ [], [17], [24, 25], [33], [40, 45], [], [], [], [], [] ]
Step 7: We move elements back into the start of myArray, from the back of radixArray.
myArray = [ 17, 24, 25, 33, 40, 45 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
The sorting is finished.

ISE, DBIT Page 14

Data Structures – B24CS34

Program 4: Develop a C program to sort the elements of an array using Radix sort technique.
#include<stdio.h>
#include<conio.h>
int get_max (int a[], int n)
{
int max = a[0],i;
for (i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void radix_sort (int a[], int n)
{
int bucket[10][10], bucket_cnt[10];
int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
lar = get_max (a, n);
while (lar > 0)
{
NOP++;
lar /= 10;
}
for (pass = 0; pass < NOP; pass++)
{
for (i = 0; i < 10; i++)
{
bucket_cnt[i] = 0;
}
for (i = 0; i < n; i++)
{
r = (a[i] / divisor) % 10;
bucket[r][bucket_cnt[r]] = a[i];
bucket_cnt[r] += 1;
}
i = 0;
for (k = 0; k < 10; k++)
{
for (j = 0; j < bucket_cnt[k]; j++)
{
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
printf ("\n After pass %d : ", pass + 1);
for (i = 0; i < n; i++)
printf ("\n %d",a[i]);
}
}

ISE, DBIT Page 15

Data Structures – B24CS34

void main ()
{
int i, n, a[10];
clrscr();
printf ("\n Enter the number of elements to be sorted : ");
scanf ("%d", &n);
printf ("\n Enter the elements : ");
for (i = 0; i < n; i++)
{
scanf ("%d",&a[i]);
}
radix_sort (a, n);
printf ("\n Sorted items : ");
for (i = 0; i < n; i++)
printf ("%d\t",a[i]);
getch();
}

Q13) Explain Insertion sort technique with an example.

Insertion sort is a simple sorting algorithm that builds a sorted array one element at a time. It
works by iteratively taking elements from the unsorted part of the array and inserting them into
their correct position within the already sorted portion.
The insertion sort algorithm works as follows:
 To sort an array of size N in ascending order, iterate over the array.
 For each element (referred to as the "key"), compare it to its preceding element.
 If the key element is smaller than its predecessor, continue comparing it to the preceding
elements.
 Shift the larger elements one position forward to make room for the key element.
 Repeat the process until the array is fully sorted.

ISE, DBIT Page 16

Data Structures – B24CS34

Example: Sort the given array [4, 3, 2, 10, 12, 1, 5, 6] using insertion sort technique.

ISE, DBIT Page 17

Data Structures – B24CS34

Q14) Wh at is hashing? What are different types of hashing techniques? Construc t the
hash table for storing C built-in functions.

acos, define, float, exp, char, atan, ceil, floor

Note: Use hash table with 26 buckets and two slots per bucket.

The process of mapping large amounts of data into a smaller table using hash function, hash
value, and hash table is called hashing.
The two types of hashing techniques are:
i) Static hashing
ii) Dynamic hashing
The process of mapping large amounts of data into a table whose size is fixed during
compilation time is called static hashing.
The process of mapping large amounts of data into a table whose size is fixed during run time
is called static hashing.
Slot 0 Slot 1
0 acos Atan
1
2
3 char Ceil
4 define
5 Exp
6 float floor
…
25
Figure: Hash table with 26 buckets and two slots per bucket
Q15) Define hash function? What are the properties of a good hash function? Explain the
different hash functions with an example.
A hash function is a mathematical formula which, when applied to a key, produces an integer
which can be used as an index for the key in the hash table. The main aim of a hash function is
that elements should be relatively, randomly, and uniformly distributed. It produces a unique
set of integers within some suitable range in order to reduce the number of collisions. A good
hash function can only minimize the number of collisions be spreading the elements uniformly
throughout the array.

ISE, DBIT Page 18

Data Structures – B24CS34

The properties of a good hash function are as follows.

1) Low Cost: The cost of executing a hash function must be small, so that using the hashing
technique becomes preferable over other approaches.
2) Determinism: A hash procedure must be deterministic. This means that the same hash
value must be generated for a given input value.
3) Uniformity: A good hash function must map the keys as evenly as possible over its output
range. This means that the probability of generating every hash value in the output range
should roughly be the same. The property of uniformity also minimizes the number of
collisions.
The different hash functions are as follows.
i) Division Method.
ii) Multiplication Method.
iii) Mid-square Method.
iv) Folding Method.

i) Division Method:
It is the most simple method of hashing an integer x. This method divides x by M and then
uses the remainder obtained.
In division method, the hash function can be given as
h(x) = x mod M
where x is the key and M is the hash table size.
Note: If M is an even number then h(x) is even if x is even and h(x) is odd if x is odd.
Example 1: Calculate the hash value of key x = 1234 and M = 10
(If M is an even number then h(x) is even if x is even)
h(x) = x mod M
h (1234) = 1234 mod 10 = 4 (4 is even)
Example 2: Calculate the hash value of key x = 5463 and M = 10
(If M is an even number then h(x) is odd if x is odd)
h(x) = x mod M
h (5463) = 5463 mod 10 = 3 (3 is odd)

ii) Multiplication Method:

The steps involved in the multiplication method are as follows:
Step 1: Choose a constant A such that 0 < A < 1
Step 2: Multiply the key k by A.
Step 3: Extract the fractional part of kA.
Step 4: Multiply the result of Step 3 by the size of hash table (m).
Hence, the hash function can be given as:
h(k) =  m (kA mod 1) 

ISE, DBIT Page 19

Data Structures – B24CS34

Example: Given the hash table of size 1000, map the key 12345 to an appropriate location in
the hash table.
Choose A = 0.3456789, m = 1000 and k = 12345
h(12345) =  1000 (12345 * 0.3456789 mod 1) 
=  1000 (4267.4060205 mod 1) 
=  1000 (0.4060205) 
=  406.0205 
= 406

iii) Mid-Square Method:

The mid-square method is a good hash function which works in two steps:
Step 1: Square the value of the key. That is, find k2.
Step 2: Extract the middle r digits of the result obtained in Step 1.

In the mid-square method, the same r digits must be chosen from all the keys. Therefore, the
hash function can be given as:
h(k) = s
where s is obtained by selecting r digits from k2.
Example: Calculate the hash value for keys 1234 and 5642 using the mid-square method. The hash
table has 100 memory locations.
Note: The hash table has 100 memory locations whose indices vary from 0 to 99. This means
that only two digits are needed to map the key to a location in the hash table, so r = 2.
When k = 1234, k2 = 1522756, h(1234) = 27
1 5 2 2 7 5 6
Remove 1 5 and 5 6
2 2 7

(In 227, 7 is in unit poition, 2 is on tens position and 2 is in hundredth position. Memory
locations, whose indices are vary from 0 to 99. This means that only two digits are needed to
map the key to a location in the hash table, so r= 2. In the result we have to take value from
unit position and tenth position and the answer is 27)
When k = 5642, k2 = 31832164, h(5642) = 32

iv) Folding Method:

The folding method works in the following two steps:

Step 1: Divide the key value into a number of parts. That is, divide k into parts k1 , k2 , ..., kn ,
where each part has the same number of digits except the last part which may have lesser digits
than the other parts.
Step 2: Add the individual parts. That is, obtain the sum of k1 + k2 + ... + kn . The hash value
is produced by ignoring the last carry, if any.

ISE, DBIT Page 20

Data Structures – B24CS34

Example: Given a hash table of 100 locations, calculate the hash value using folding method
for keys 5678, 321, and 34567.
Since there are 100 memory locations to address, we will break the key into parts where each
part (except the last) will contain two digits. The hash values can be obtained as shown below:

Q16) Define and explain Hash collision with an example?

A hash collision is when two different inputs produce the same output hash value from a hash
function, leading to a conflict in data structures like hash tables where multiple inputs map to
the same index or location.
Example 1 of a Simple Hash Collision:
Consider a very simple hash function that calculates the sum of the ASCII values of the
characters in a string, and then takes the result modulo a small number (e.g., 10) to determine
an index in a hash table.

hash function: hash(string) = (sum of ASCII values of characters) % 10

 Input 1: "cat"
ASCII values: 'c' = 99, 'a' = 97, 't' = 116
Sum: 99 + 97 + 116 = 312
Hash value: 312 % 10 = 2

 Input 2: "act"
ASCII values: 'a' = 97, 'c' = 99, 't' = 116
Sum: 97 + 99 + 116 = 312
Hash value: 312 % 10 = 2

In this example, both "cat" and "act" produce the same hash value of 2, even though they are
distinct strings. This demonstrates a hash collision.

Example 2 of a Simple Hash Collision:

Figure: Collision in Hashing

ISE, DBIT Page 21

Data Structures – B24CS34

Q17) List and explain different collision resolution techniques.

Collisions occur when the hash function maps two different keys to the same location. Two
records cannot be stored in the same location. Therefore, a method used to solve the problem
of collision, also called collision resolution technique, is applied. The two most popular
methods of resolving collisions are:
1. Open addressing (or Closed Hashing)
2. Chaining

Open Addressing:

Open addressing or closed hashing computes new positions using a probe sequence and the
next record is stored in that position. In this technique, all the values are stored in the hash
table. The hash table contains two types of values: sentinel values (e.g., –1) and data values.
The presence of a sentinel value indicates that the location contains no data value at present but
can be used to hold a value.

When a key is mapped to a particular memory location, then the value it holds is checked. If it
contains a sentinel value, then the location is free and the data value can be stored in it.
However, if the location already has some data value stored in it, then other slots are examined
systematically in the forward direction to find a free slot. If even a single free location is not
found, then we have an OVERFLOW condition.

The process of examining memory locations in the hash table is called probing. Open
addressing technique can be implemented using following techniques.
1) Linear Probing
2) Quadratic Probing
3) Double Hashing.

Linear Probing:
The simplest approach to resolve a collision is linear probing. In this technique, if a value is
already stored at a location generated by h(k), then the following hash function is used to
resolve the collision:
h(k, i) = [h¢(k) + i] mod m
Where m is the size of the hash table, h¢(k) = (k mod m), and i is the probe number that varies
from 0 to m–1.
4)

Note:Linear probing is known for its simplicity. When we want to store a value, we
have to try the slots:
[h(k)] mod m, [h (k) + 1]mod m, [h (k) + 2]mod m, [h (k) + 3]mod m, [h(k) + 4]mod m,
[h(k) + 5]mod m, and so on, until a vacant location is found.

ISE, DBIT Page 22

Data Structures – B24CS34

Quadratic Probing:
In this technique, if a value is already stored at a location generated by h(k), then the following
hash function is used to resolve the collision:
h(k, i) = [h(k) + c1 i + c2 i2] mod m
where m is the size of the hash table, h (k) = (k mod m), i is the probe number that varies from
0 to m–1, and c1 and c2 are constants such that c1 and c2 ≠ 0.

Double Hashing:
Double hashing uses one hash value and then repeatedly steps forward an interval until an
empty location is reached. The interval is decided using a second, independent hash function,
hence the name double hashing. In double hashing, we use two hash functions rather than a
single function. The hash function in the case of double hashing can be given as:
h(k, i) = [h1 (k) + ih2 (k)] mod m
where m is the size of the hash table, h1 (k) and h2 (k) are two hash functions given as h1 (k) =
k mod m , h2 (k) = k mod m', i is the probe number that varies from 0 to m–1, and m' is chosen
to be less than m . We can choose m' = m–1 or m–2.

Collision Resolution by Chaining:

In chaining, each location in a hash table stores a pointer to a linked list that contains all the
key values that were hashed to that location. That is, location l in the hash table points to the
head of the linked list of all the key values that hashed to l. However, if no key value hashes to
l, then location l in the hash table contains NULL. Figure below shows how the key values are
mapped to a location in the hash table and stored in a linked list that corresponds to that
location

ISE, DBIT Page 23

Data Structures – B24CS34

Q18) Consider a hash table of size 10. Using Linear Probing, insert the keys 72, 27, 36,
24, 63, 81, 92, and 101 into the table.

ISE, DBIT Page 24

Data Structures – B24CS34

ISE, DBIT Page 25

Data Structures – B24CS34

Q19) Consider a hash table of size 10. Using Quadratic Probing, insert the keys 72, 27,
36, 24, 63, 81, and 101 into the table. Take c 1 = 1 and c2 = 3.

ISE, DBIT Page 26

Data Structures – B24CS34

ISE, DBIT Page 27

Data Structures – B24CS34

Q20) Consider a hash table of size = 10. Using Double Hashing, insert the keys 72, 27, 36,
24, 63, 81, 92, and 101 into the table. Take h1 = (k mod 10) and h2 = (k mod 8).

ISE, DBIT Page 28

Data Structures – B24CS34

ISE, DBIT Page 29

Data Structures – B24CS34

ISE, DBIT Page 30

Data Structures – B24CS34

Q21) Insert the keys 7, 24, 18, 52, 36, 54, 11, and 23 in a chained hash table of 9 memory
locations. Use h(k) = k mod m.

ISE, DBIT Page 31

Data Structures – B24CS34

ISE, DBIT Page 32