DSA Module-1

+1. What is a data structure? List and explain data structure operations. [8] ​

Definition [2] ...

A data structure is a representation of the logical relationships existing between individual elements of
data. A data structure is a way of organizing all data items that considers not only the elements stored but
also their relationship to each other.
A data structure is a way to organize, store, and manage data efficiently for use in algorithms and
computations.
Examples: arrays, linked lists, stacks, queues, trees, and graphs, each designed to handle specific types of
data operations and access patterns.

Basic/Primitive Operations [6]

./~attachments/[Link]
...

Traversing:
It means to access each data item exactly once so that it can be processed.
Ex: 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.
Ex: to find the names of all the students who secured 100 marks in chemistry.
Inserting:
It is used to add new data items to the given list of data items.
Ex: 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.
Ex: to delete the name of a student who has left the course.
Sorting:
Arranging data items in some order like ascending order or descending order depending on the type
of application.
Ex: arranging the names of students in a class in an alphabetical order
Merging:
Lists of two sorted data items can be combined to form a single list of sorted data items.
Ex: Combining two sorted class rank lists into one.

+2. Discuss four dynamic memory allocation functions. [8] ​

Definition ...

Dynamic memory allocation is a process of allocating, resizing, and freeing memory on a heap during runtime.

Explanation ...

It is used if there is an unpredictable storage requirement.

Memory management functions include:
malloc() - definition, syntax, example
 calloc() - definition, syntax, example
realloc() - definition, syntax, example
free() - definition, syntax, example
These functions are included in the header file <stdlib.h>

Dynamic Memory Allocation Functions ...

malloc()
Syntax: datatype *ptr = (cast type*) malloc(size in bytes);
Reserves/allocates a contiguous block of memory on the heap of specified size.
If successful, it returns a pointer to the first allocated byte or NULL if unsuccessful.
Leaves the memory uninitialized.
Ex:

1 // To allocate memory for 50 integers,

2 int *ptr;
3 ptr = (int*) malloc(50*size of(int));

calloc()
Syntax: datatype *ptr = (cast type*) calloc(n blocks, size of each block in bytes);
Allocates multiple blocks of storage each of the same size and then sets all bytes to zero.
Has 2 parameters:
n = no. Of blocks to be allocated
size = fixed size of each block
If successful, it returns a pointer to the first allocated byte or NULL if unsuccessful.
Ex:

1 int *ptr;
2 ptr = (int*) calloc(3, 2); // 3 blocks of 2 bytes each will be allocated

realloc()
Syntax: datatype *ptr = realloc(ptr, newsize);
Used to modify the size of the previously allocated memory block.
Allocates new memory space of size specified by newsize to the pointer variable ptr .
The allocated new block may be or may not be at the same region as the original block.
If successful, it returns a pointer to the first allocated byte or NULL if unsuccessful.
Ex:

1 int *arr = malloc(2 * sizeof(int));

2 arr[0] = 1;
3 arr[1] = 2;
4 arr = realloc(arr, 3 * sizeof(int));
5 arr[2] = 3;

free()
Syntax: free(ptr);
Used to deallocate/free the memory block which has been allocated using malloc() , calloc() , or
realloc() .
Once memory is deallocated, the pointer is set to NULL.
When memory is deallocated, it is returned back to the free list within the heap.
Ex:

1 int *ptr;
2 ptr = (int*) malloc(50*size of(int));
3 free(ptr);

+3. With a suitable example, discuss self-referential structures. [4] ​

Definition [1] ...

A self-referential structure is one in which one or more of its components is a pointer to itself.

Syntax [1] ...

1 struct structure_name
2 {
3 data_type member 1;
4 data_type member 2;
5 …
6 structure_name *pointer;
7 };

Explanation [1] ...

It requires dynamic memory allocation functions to explicitly obtain and release memory.
It has two components:
Data
Link = pointer to a structure
Value of link is either memory address of the structure it's pointing to or the null pointer.

Example [1] ...

1 typedef struct list {

2 char data;
3 list *link;
4 };
5 // three structures with values assigned
6 list item1, item2, item3;
7 [Link] = 'a';
8 [Link] = 'b';
9 [Link] = 'c';
10 [Link] = [Link] = [Link] = NULL;
11 //attaching structures together
12 [Link] = &item2;
13 [Link] = &item3;

Data is a single character.

List is a pointer to list structure.
Structures item1 , item2 , and item3 each contain the data item a , b , and c , and null pointer.
These structures can be attached together by replacing the null link field in item2 with one that points to
item3 and by replacing the null link field in item1 with one that points to item2 .

./~attachments/[Link]

+4. Define array. Explain different types of arrays. How can one-dimensional array be initialized?
Explain with examples.

Definition ...

An array is collection of data items of the same type in contiguous memory locations. Each value (data item) in
an array is indicated by same name that is array name and an index which indicates the position of value in an
array.

Types of Arrays ...

One-dimensional array
Also called single dimensional array.
 Simplest type of array that contains only one row for storing the values of the same type.
There's one index in a one-dimensional array.
Declaration syntax: data_type array_name [array_size];
data_type = type of data items being stored
array_name = name of the array
array_size = max. number of values that the array can hold
Ex: int a[25];
Two-dimensional array
It's an array where elements can be stored row-wise and column-wise.
Used to store a table of values of same data type.
There are two indices in a two-dimensional array.
Declaration syntax: data_type array_name[row_size][column_size];
row_size = no. of rows in the array
column_size = no. of columns in the array
Ex: int array[10][15];
Multi-dimensional array
Is an array of arrays.
It's used for representing 3 or more dimensions.
There are n indices in a multi-dimensional array.
Declaration syntax: data_type array_name[s1][s2]…[sn];
[s1] = size of 1st dimension
[s2] = size of 2nd dimension
[sn] = size of nth dimension
Ex: int survey[3][5][12];

Initialization of One-Dimensional Arrays ...

Static initialization
Array size is fixed at compile time.
Memory is allocated before execution on stack.
Dynamic initialization
Array size decided at runtime.
Memory is allocated after execution from the heap.

Various Methods of Static Initialization ...

1. Initializing all specified memory location

./~attachments/[Link]

2. Partial Array Initialization

./~attachments/[Link]

3. Initialization without Size

 ./~attachments/[Link]

4. Array Initialization with String

./~attachments/[Link]

5. Static Initialization with Loops

./~attachments/[Link]

+5. Explain with a neat block schematic diagram the different types of data structures with
examples. [4]

Diagram

./~attachments/[Link]

Classification

1. Primitive Data Structures

These are basic data structures and are directly operated upon by the machine instructions.
They consist of characters that cannot be divided and hence are also called simple data types.
Types:
Integer: Stores whole numbers (positive, negative, or zero). Ex: int a = 20;
Float: Stores decimal numbers. Ex: float a = 2.5;
Double: Stores decimal numbers with more precision than float. Ex: double a = 1.4521
Character: Stores a single character. Ex: char a = 'a';
Void: Represents no value or empty type. Used in non-return type functions and for generic pointers
(void*).
2. Non-Primitive Data Structures
These are derived from the primitive data structures.
 They emphasize on structuring a group of homogeneous or heterogeneous data items.
Types:
Linear:
A data structure is said to be linear if its elements form a sequence or a linear list.
Ex: Arrays, Queues, Stacks, Linked lists, etc.
Non-linear:
A data structure is said to be non-linear if the data are not arranged in sequence.
The insertion and deletion of data is not possible in linear fashion.
Ex: Trees and graphs.

+6. Differentiate between structures and unions with an example for each. [5] ​

./~attachments/[Link]

Structures Unions
Keyword struct is used. Keyword union is used.
Size of structure = sum of the sizes of individual Size of union = largest space occupied by one of the
members. members.
Offset address is different for the members. Offset address is same as memory is shared among the
members.
Individual memory is allocated for the members. Memory is shared by all the members of the union.
Initialization can be done simultaneously for the Initialization can't be done simultaneously for all the
members. members.