UNIT – I

Q1. Define DATA STRUCTURE.

Data may be organized in many different ways logical or mathematical model of a program
particularly organization of data. This organized data is called “Data Structure”.
Or
The organized collection of data is called a ‘Data Structure’.
DATA STRUCTURE=ORGANIZED DATA +ALLOWED OPERATIONS

Or
Data Structure
 Way of organizing and storing data in a computer system
 This organization is done under a common name.
 Depicts the logical representation of data in computer memory.
Or
A data structure is a particular way of storing and organizing data in a computer so that it can be
used efficiently.
Q2 . Explain Classification of Data Structures?

Data Structures classified into two categories:

1. Primitive Data Structure

2. Non-Primitive Data Structure

Primitive Data structures are directly supported by the language ie; any operation is directly performed in
these data items.
Example: integer, Character, Real numbers etc.

 Primitive Data Structures are the data structures consisting of the numbers and the characters that
come in-built into programs.
 These data structures can be manipulated or operated directly by machine-level instructions.

2
  Basic data types like Integer, Float, Character, and Boolean come under the Primitive Data
Structures.
 These data types are also called Simple data types, as they contain characters that can't be divided
further

Non-Primitive Data structures are not defined by the programming language, but are instead created by
the programmer.
Non-Primitive Data Structures are those data structures derived from Primitive Data Structures.

1. These data structures can't be manipulated or operated directly by machine-level instructions.

2. The focus of these data structures is on forming a set of data elements that is
either homogeneous (same data type) or heterogeneous (different data types).
3. Based on the structure and arrangement of data, we can divide these data structures into two sub-
categories -
a. Linear Data Structures
b. Non-Linear Data Structures

Q3. Explain a brief concept about linear data structures.

 Linear data structures organize their data elements in a linear fashion, where data elements are
attached one after the other.
 If the elements of a data structure are stored in a linear or sequential order, then it is a linear data
structure.
 Linear data structures are very easy to implement, since the memory of the computer is also
organized in a linear fashion.
 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.
 Some commonly used linear data structures are arrays, linked lists, stacks and queues.

Q4. Explain an advantages of linear data structure.

 Efficient data access: Elements can be easily accessed by their position in the sequence.

 Dynamic sizing: Linear data structures can dynamically adjust their size as elements are added or
removed.

 Ease of implementation: Linear data structures can be easily implemented using arrays or linked
lists.

 Versatility: Linear data structures can be used in various applications, such as searching, sorting,
and manipulation of data.

3
  Simple algorithms: Many algorithms used in linear data structures are simple and straightforward.

Q5. Explain importance of linear data structures.

Linear data structures are fundamental concepts in computer science and are crucial for organizing and
managing data efficiently. Here are some key points highlighting their importance:

1. Sequential Access: Linear data structures provide sequential access to their elements, meaning
each element is connected to its previous and next element. This allows for easy traversal and
manipulation of data in a sequential manner.
2. Efficient Insertion and Deletion: Linear data structures such as arrays, lists, stacks, and queues
offer efficient insertion and deletion operations, especially when performed at the ends of the
structure. For example, adding or removing elements from the end of an array or a linked list is
relatively fast.
3. Memory Efficiency: Linear data structures typically offer memory efficiency in terms of storage.
Arrays, for instance, provide contiguous memory allocation, making them efficient in terms of
memory usage.
4. Simplicity and Ease of Use: Linear data structures are generally simpler to implement and
understand compared to non-linear data structures like trees and graphs. This simplicity makes
them ideal for a wide range of applications and programming scenarios.
5. Versatility: Linear data structures can be used to implement various other data structures and
algorithms. For example, stacks and queues can be implemented using arrays or linked lists. This
versatility makes linear data structures a crucial building block for designing more complex data
structures and algorithms.
6. Application in Algorithms: Many algorithms heavily rely on linear data structures. Sorting
algorithms like insertion sort and selection sort make use of arrays and linked lists. Searching
algorithms like linear search and binary search also utilize linear data structures.
7. Real-world Applications: Linear data structures find applications in various real-world scenarios
such as managing lists of tasks, processing data streams, implementing undo functionalities in
software applications, managing resources in operating systems, and more.
8. Foundation for Abstract Data Types (ADTs): Linear data structures serve as the foundation for
defining abstract data types such as stacks, queues, and lists. These ADTs provide high-level
interfaces for manipulating data, hiding the underlying implementation details, and promoting code
reusability and modularity.

Q6. Explain the concept of Abstract Datatype.

 C is not object-oriented, but we can still manage to inject some object-oriented principles into the
design of C code.
 For example, a data structure and its operations can be packaged together into an entity called an
ADT.

4
  There’s a clean, simple interface between the ADT and the program(s) that use it.
 The lower-level implementation details of the data structure are hidden from view of the rest of the
program.
 An abstract data type (ADT) is a set of operations and mathematical abstractions , which can be
viewed as how the set of operations is implemented. Objects like lists, sets and graphs, along with
their operation, can be viewed as abstract data types, just as integers, real numbers and Booleans.

Features of ADT.

1. Modularity
 Divide program into small functions
 Easy to debug and maintain
 Easy to modify
2. Reuse
 Define some operations only once and reuse them in future
3. Easy to change the implementation

Q7. Explain in detail of Abstract Datatype(ADTs) and their implementation.

Abstract Data Types (ADTs) are a fundamental concept in computer science that allows us to define data
structures based on their behaviour and operations, rather than their implementation details. ADTs provide
a high-level interface for interacting with data, hiding the underlying implementation complexity.
Characteristics of ADTs:
1. Encapsulation: ADTs encapsulate data and operations into a single unit, allowing users to interact
with the data structure through a well-defined interface.
2. Data Abstraction: ADTs provide a clear separation between the interface and the implementation,
allowing users to focus on using the data structure without needing to understand how it is
implemented.
Common ADTs:
1. Stack: A stack is a Last-In-First-Out (LIFO) data structure that supports two primary operations: push
(to add an element) and pop (to remove the top element).
2. Queue: A queue is a First-In-First-Out (FIFO) data structure that supports two primary operations:
enqueue (to add an element to the rear) and dequeue (to remove the front element).
3. List: A list is a linear collection of elements where each element has a successor and/or predecessor.
Common operations include insertion, deletion, and traversal.
Implementation of ADTs:
ADTs can be implemented using various underlying data structures, such as arrays, linked lists, or trees,
depending on the requirements of the ADT and the efficiency desired for its operations.
Example Implementation of a Stack:
ADTs can be implemented in C using structures and functions. Here's a simple example implementation of a
stack in C

5
Program:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Define the stack structure
typedef struct
{
int items[MAX_SIZE];
int top;
} Stack;
// Initialize the stack
void initialize(Stack *stack)
{
stack->top = -1;
}
// Push operation
void push(Stack *stack, int value)
{
if (stack->top == MAX_SIZE - 1)
{
printf("Stack Overflow\n");
return;
}
stack->items[++stack->top] = value;
}
// Pop operation
int pop(Stack *stack)
{
if (stack->top == -1)
{
printf("Stack Underflow\n");
exit(1);
}
return stack->items[stack->top--];
}
// Peek operation
int peek(Stack *stack)
{
if (stack->top == -1)
{
printf("Stack is empty\n");
exit(1);
}
return stack->items[stack->top];
}
// Main function to test the stack
int main()
{
Stack stack;
initialize(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printf("Top element: %d\n", peek(&stack));
printf("Popped element: %d\n", pop(&stack));
printf("Top element after pop: %d\n", peek(&stack));
return 0;
}
Output:
Top element: 30
Popped element: 30
Top element after pop: 20

6
Explanation:
 We first push three elements (10, 20, 30) onto the stack.
 Then, we print the top element of the stack, which is 30.
 Next, we pop an element from the stack, which removes 30 from the stack.
 Finally, we print the new top element of the stack, which is 20 after popping 30.

Q8. Explain about performance analysis of an algorithm.

Analysis of algorithms (or) performance analysis refers to the task of determining how much computing
time (time complexity) and storage (space complexity) of an algorithm requires.

Algorithm efficiency describes the properties of an algorithm which relates to the amount of
resources used. An algorithm must be analyzed to determine its resources usage.

The time complexity of an algorithm is the amount of computer time it needs to run for its
completion. The space complexity of an algorithm is the amount of memory it needs to run for its
completion.

These complexities are calculated based on the size of the input. With this, analysis can be divided
into three cases as:

 Best case analysis

 Worst case analysis
 Average case analysis

Best case analysis: In best case analysis, problem statement takes minimum number of
computations for the given input parameters.

Worst case analysis: In worst case analysis, problem statement takes maximum number of
computations for the given input parameters.

Average case analysis: In average case analysis, problem statement takes average number of
computations for the given input parameters.

Based on the size of input requirements, complexities can be varied. Hence, exact representation of
time and space complexities is not possible. But they can be shown in some approximate representation
using mathematical notations known as asymptotic notations.

Q9. Describe concept of Space Complexity of an algorithm.

The process of estimating the amount of memory space to run for its completion is known as space
complexity.

Space complexity S(P) of any problem P is sum of fixed space requirements and variable space
requirements as:

Space requirement S(P) = Fixed Space Requirements + Variable Space Requirements

1. Fixed space that is independent of the characteristics (Ex: number, size) of the input and outputs. It
includes the instruction space, space for simple variables and fixed-size component variables, space
for constants and so on.

2. Variable space that consists of the space needed by component variables whose size is dependent on
the particular problem instance being solved, the space needed by the referenced variables and the
recursion stack space.

7
 When analysing the space complexity of any problem statement, concentrate solely on estimating the
variable space requirements. First determine which instance characteristics to use to measure the space
requirements. Hence, the total space requirement S(P) of any program can be represented as:

S (P) = C + SP (I)

Where,
C is a constant representing the fixed space requirements and I refer to instance
characteristics.

Example 1: float sum(float a, float b, float c)

{
return a+b+c;
}

Here, the variables a,b and c are simple variables.

Therefore Ssum = 0.

Example 2: float sum(float list[25], int n)

{
float s = 0;
int i;
for( i = 0 ; i < n ; i++)
s = s + list[i];
return s;
}

Here, the instance characteristic is n. Variable terms are n, i and s. So that count values are treated
as n for the list array, one each for n, i, and s.
Therefore Ssum (n) = n + 3.
Example 3: float sum(float list[25], int n)
{
if (n <= 0)
return 0.0;
else
return sum(list,n-1) + list[n];
}

Here, the instance characteristic is n. Recursion includes space for formal parameters, local
variables, and the return address. So that count values are treated as one for n, one for return address and
one for list[] array. Function works for n+1 times. For every call the three word counts should be worked.

Therefore Ssum (n) = 3(n + 1).

Q10. Describe concept of Time Complexity of an algorithm.

The process of estimating the amount of computing time to run for its completion is known as time
complexity.

The time T(P) taken by a program P is the sum of its compile time and its run time.

i.e., Time complexity T(P) = Compile time + Run time

8
Here,
Compile time is a fixed component and does not depends on the instance characteristics. Hence,

T(P) = C + TP (Instance characteristics)

Where, C is a fixed constant value

T(P) ≥ TP(I)
Where, I refer instance characteristic.

Time complexity of a program is calculated by determining the number of steps that a

program/function needs to solve known as step count and then express it in terms of asymptotic notations.

STEP COUNT METHOD

In Step count method, determine the number of steps that a program or a function needs to solve a
particular instance by creating a global variable count, which has an initial value of ‘0’. Now increment
count by number of program steps required by each executable statement. Finally add the total number of
times that the count variable is incremented.

Example 1: float sum(float a, float b, float c) count = 0

{
return a+b+c; count=count+1
count=count+1
}

Here, count variable is incremented by twice one for addition operation and one for return statement.

Therefore Tsum = 2.

Example 2: float sum(float list[25], int n) count = 0

{
float s = 0; count=count+1 /* Assignment */
int i;
for( i = 0 ; i < n ; i++)
{ count=count+1 /* i Assignment */
s = s + list[i]; count=count+1 /* s Assignment */
}
count=count+1 /* i last assignment */
return s; count=count+1 /* return statement */
}

Here, inside the loop count variable is incremented by two times and the loop is executed for n times
so that it becomes 2n steps. Outside the loop count is incremented by 3 steps.

Therefore Tsum (n) = 2n + 3.

9
Q11. Define searching?

Search is a process of finding a value in a list of values.

Q12. Explain linear search with example?

Linear Search (Sequential Search):

 Linear search algorithm finds a given element in a list of elements with O(n) time complexity where
n is total number of elements in the list.
 This search process starts comparing search element with the first element in the list.
 If both are matched, then result is element found otherwise search element is compared with the
next element in the list.
 Repeat the same until search element is compared with the last element in the list, if that last
element also doesn't match, then the result is "Element not found in the list".
 In linear search, search element is compared with element by element in the list.

Algorithm:
Linear Search Algorithm:
1. Input: Array arr of size n, and a target element target.
2. Initialize a variable found to false.
3. Loop through each element of the array from index 0 to n-1.
4. For each element arr[i]:
i. If arr[i] equals target, set found to true and break out of the loop.
5. After the loop:
i. If found is true, return the index i where target was found.

10
ii. If found is false, return a special value (e.g., -1) to indicate that target was not found in the
array.

11
Time Complexity:
Best Case – O(1)
Average Case – O(n)
Worst Case – O(n)
Q13. Write a C program to implement linear search?
Program:

#include <stdio.h>
// Function to perform linear search
int linearSearch(int arr[], int n, int target)
{
int i;
for (i = 0; i < n; i++)
{
if (arr[i] == target)
{
return i; // Return the index of the target element if found
}
}
return -1; // Return -1 if the target element is not found
}
int main()
{
int arr[] = {12, 45, 67, 23, 9, 5, 78};
int n = sizeof(arr) / sizeof(arr[0]); // Calculate the number of elements
in the array
int target = 23; // Element to be searched
// Perform linear search
int result = linearSearch(arr, n, target);
if (result != -1)
{
printf("Element found at index: %d\n", result);
}
else
{
printf("Element not found in the array.\n");
}
return 0;
}

Output :
Element found at index: 3
Explanation:
 The target element 23 is found at index 3 in the array arr[].

Q14. Explain Binary search with example?

Binary Search:
 Binary search algorithm finds a given element in a list of elements with O(log n) time complexity
where n is total number of elements in the list.

12
  The binary search algorithm can be used with only a sorted list of elements. The binary search
cannot be used for a list of elements arranged in random order.
 This search process starts comparing the search element with the middle element in the list. If both
are matched, then the result is "element found".
 Otherwise, we check whether the search element is smaller or larger than the middle element in
the list. If the search element is smaller, then we repeat the same process for the left sub list of the
middle element. If the search element is larger, then we repeat the same process for the right sub
list of the middle element.
 We repeat this process until we find the search element in the list or until we left with a sub list of
only one element. And if that element also doesn't match with the search element, then the result
is "Element not found in the list".
Algorithm:

1. Read the search element from the user.

2. Find the middle element in the sorted array.
3. Compare the search element with the middle element in the sorted array.
4. If both are matched, then display "Given element is found!!!" and terminate the function.
5. If both are not matched, then check whether the search element is smaller or larger than the
middle element.
6. If the search element is smaller than the middle element, repeat steps 2, 3, 4 and 5 for the left
subarray of the middle element.
7. If the search element is larger than the middle element, repeat steps 2, 3, 4 and 5 for the right
subarray of the middle element.
8. Repeat the same process until we find the search element in the array or until the subarray
contains only one element.
9. If that element also doesn’t match with the search element, then display "Element is not found in
the array!!!" and terminate the function.
Time Complexity:
Best Case – O(1)

Average Case – O(log n)

Worst Case – O(log n)

13
14
Q15. Write a C program to implement Binary search?
Program:

#include <stdio.h>
int binarySearch(int arr[], int left, int right, int key)
{
while (left <= right)
{
int mid = left + (right - left) / 2;
// Check if key is present at mid
if (arr[mid] == key)
return mid;
// If key greater, ignore left half
if (arr[mid] < key)
left = mid + 1;
// If key is smaller, ignore right half
else
right = mid - 1;
}
// If element not found, return -1
return -1;
}
int main()
{
int arr[] = {1, 2, 3, 5, 7, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 5;
int result = binarySearch(arr, 0, n - 1, key);
if (result != -1)
printf("Element %d found at index %d\n", key, result);
else
printf("Element %d not found in the array\n", key);
return 0;
}
Output :

Element 5 found at index 3

Explanation:

 binarySearch function: This function takes an array, the leftmost index, the rightmost index, and the
key to be searched as arguments. It iteratively divides the search space in half and compares the key
with the element at the middle index. Depending on the comparison, it adjusts the search space
until the element is found or the search space is exhausted.

15
  main function: It initializes an array, calculates its size, and defines the key to be searched. It then
calls the binarySearch function and prints the result based on whether the key is found or not.

Q16. Define sorting?

Sorting is the process of arranging a list of elements in a particular order (Ascending or Descending).
Q17. Explain the process of bubble sort with example?
Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not
in the intended order. The order can be ascending or descending.
How Bubble Sort Works?
1. Starting from the first index, compare the first and the second elements. If the first element is
greater than the second element, they are swapped.
2. Now, compare the second and the third elements. Swap them if they are not in order.
The above process goes on until the last element.

 The same process goes on for the remaining iterations.

 After each iteration, the largest element among the unsorted elements is placed at the end.
 In each iteration, the comparison takes place up to the last unsorted element.
 The array is sorted when all the unsorted elements are placed at their correct positions.

16
17
Algorithm:
The algorithm to sort data of the list in increasing order using bubble sort is:
1. Run two loops nested in one another.
2. The outer loop will run from i = 0 to i < n – 1, where n is the number of elements in the list.
3. The inner loop will run from j = 0 to j < n – i – 1. It is because, after each iteration of the outer
loop, one element at the end (or at the start if the order is decreasing order) will be in its right
place so we can leave it as it is.
4. In the inner loop, we will check if the arr[ j ] > arr[ j + 1 ].
i. If it’s true, then we will swap places of these elements.
ii. If false, we will continue to the next iteration.
5. This process will be repeated till the conditions of the loop are satisfied.
Program:
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j, temp;
for (i = 0; i < n-1; i++)
{
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
{
// Swap if the element found is greater than the next element
if (arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Original array: ");
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
bubbleSort(arr, n);
printf("Sorted array: ");
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);

18
 }
printf("\n");
return 0;
}
Output :

Original array: 64 34 25 12 22 11 90

Sorted array: 11 12 22 25 34 64 90

Explanation:

 The bubbleSort function implements the bubble sort algorithm. It iterates through the array and
compares adjacent elements, swapping them if they are in the wrong order. This process is repeated
until the entire array is sorted.

 In the main function, an array arr is initialized with some values. The original array is printed, then
the bubbleSort function is called to sort the array. Finally, the sorted array is printed

Q18. Explain the process of Selection sort with example?

Selection Sort:
 Selection Sort algorithm is used to arrange a list of elements in a particular order (Ascending or
Descending).
 In selection sort, the first element in the list is selected and it is compared repeatedly with all the
remaining elements in the list.
 If any element is smaller than the selected element (for Ascending order), then both are swapped
so that first position is filled with the smallest element in the sorted order.
 Next, we select the element at a second position in the list and it is compared with all the remaining
elements in the list..
 If any element is smaller than the selected element, then both are swapped. This procedure is
repeated until the entire list is sorted.
Algorithm:
1. Start traversing the array from the first element (i = 0) to the second last element.
2. For each ith element, find the minimum element (min_idx) among the elements from i+1 to n-1.
3. Swap the current element (arr[i]) with the minimum element (arr[min_idx]), if arr[min_idx] < arr[i].
4. Repeat the process until the entire array is sorted.

19
Example:

20
Complexity Analysis:
1 Time Complexity:
 Best Case: O(n^2)
 Worst Case: O(n^2)
 Average Case: O(n^2)
2 Space Complexity: O(1) - Selection Sort is an in-place sorting algorithm.

21
Program:
#include <stdio.h>
void selectionSort(int arr[], int n)
{
int i, j, min_idx, temp;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
{
if (arr[j] < arr[min_idx])
min_idx = j;
}
// Swap the found minimum element with the first element
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Original array: ");
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
selectionSort(arr, n);
printf("Sorted array: ");
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output :

Original array: 64 34 25 12 22 11 90

22
Sorted array: 11 12 22 25 34 64 90

Explanation:

 The selectionSort function implements the selection sort algorithm. It repeatedly selects the
smallest element from the unsorted portion of the array and places it at the beginning of the sorted
portion.

 In the main function, an array arr is initialized with some values. The original array is printed, then
the selectionSort function is called to sort the array. Finally, the sorted array is printed.

Q19. Explain the process of Selection sort with example?

Insertion Sort:
 Insertion sort algorithm arranges a list of elements in a particular order.
 In insertion sort algorithm, every iteration moves an element from unsorted portion to sorted
portion until all the elements are sorted in the list.
Algorithm:
1 Start traversing the array from the second element (i = 1) to the last element.
2 For each ith element, compare it with the elements before it (from i-1 to 0).
3 Move elements greater than the current element one position to the right (arr[j+1] = arr[j]) until
you find the correct position for the current element.
4 Insert the current element into its correct position (arr[j+1] = key).
Program:
#include <stdio.h>
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are greater than key, to
one position ahead of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

23
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
insertionSort(arr, n);
printf("Sorted array: ");
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output :

Original array: 64 34 25 12 22 11 90

Sorted array: 11 12 22 25 34 64 90

Explanation:

 The insertionSort function implements the insertion sort algorithm. It iterates over the array and at
each step, it takes the element at index i and inserts it into the sorted subarray arr[0..i-1].
 In the main function, an array arr is initialized with some values. The original array is printed, then
the insertionSort function is called to sort the array. Finally, the sorted array is printed.

Complexity Analysis:
Time Complexity:
Best Case: O(n) - When the array is already sorted.
Worst Case: O(n^2)
Average Case: O(n^2)
Space Complexity: O(1) - Insertion Sort is an in-place sorting algorithm.

24