CHAPTER 1

INTRODUCTION TO DATA STRUCTURE

CONCEPT AND NEED OF DATA STRUCTURE
Q] Define data structure and give its classification. [W-14]
Data Structure
A data structure is a specialized format for organizing and storing data.
Need of Data Structure
i) Data can be organized in many ways and data structure is one of these ways.
ii) It is used to represent data in the memory of the computer so that the processing of data can
be done in easier way.
So data structure is concerned with following things:
1. Organization of Data
2. Associativity among data elements
3. Accessing Methods
4. Operations on Data
5. Processing Alternatives for Data

TYPES OF DATA STRUCTURES

Q] Define data structure. Enlist any two types of non-linear data structure. [W-15]
(Definition data structure 1M, List of non-linear data structure two types -1/2M each)
Q] Explain Primitive and Non Primitive Data Structure. [S-15]
(Primitive - 2Marks, Non Primitive 2 Marks)

ARROW COMPUTER ACADEMY DSU 8788335443

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 Used to represent a number without decimal point.

Float Used to represent a number with decimal point.

Character Used to represent single character.

Boolean Used to represent logical values either true or false.

B. Non-Primitive Data Type

Data types derived from primary data types are known as Non-Primitive data types.
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

A) Linear Data Structure:

 Elements are arranged in a Linear Fashion (one dimension).
 Linear data structure traverses the data elements sequentially.
 In linear data structure, only one data element can directly be reached.
 It includes array, stack, queues, linked list,.

B) Non Linear Data Structures:

• 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.

ARROW COMPUTER ACADEMY DSU 8788335443

 ABSTRACT DATA TYPE
The abstract datatype is special kind of datatype, whose behavior is defined by a set of values
and set of operations.
The keyword “Abstract” is used as we can use these datatypes, we can perform different
operations.
But how those operations are working that is totally hidden from the user.
The ADT is made of with primitive datatypes, but operation logics are hidden.
Abstraction for primitive types (char, int, float) is provided by the compiler.
For example, we use integer type data and also, perform various operations on them without
knowing:
(1) Representation (2) How various operations are performed on them.
Example:
int x;
x= -13;
Constant -13 is converted to 2’s complement and then stored in x.
Representation is handled by the compiler. Its implementation details remain hidden
from the user.
Some examples of ADT are Stack, Queue, List etc.

OPERATIONS ON DATA STRUCTURE

Q] Enlist various types of operation on data structure. (Any 4 operations - 2 Marks) [S-15]
Q] Describe any four operations on data structure. [W-15] (4-Marks)
(Description of any four operations: 1M each)

Operations on data structure are:

 Insertion: It is adding a new data in data structure.
 Deletion: It is removing a data from existing data structure
 Searching: It is finding location or existence of data within given data structure
 Sorting, arranging data in some logical order: It is used to arrange the data
items in some order i.e. in ascending or descending order in case of numerical
data and in dictionary order in case of alphanumeric data.
 Traversing: It is an operation that accesses each and every element.
 Merging: It is used to combine the data items of two data structure into single
data structure.

ARROW COMPUTER ACADEMY DSU 8788335443

`

CHAPTER 2

SEARCHING AND SORTING

(MARKS 12)

(R-2, U-2, A-8)

SYLLABUS
2.1 SEARCHING
2.1.1 LINEAR SEARCH
2.1.2 BINARY SEARCH

2.2 SORTING
2.2.1 BUBBLE SORT
2.2.2 INSERTION SORT
2.2.3 SELECTION SORT
2.2.4 QUICK SORT
2.2.5 RADIX SORT

ARROW COMPUTER ACADEMY DSU 8788335443

`
2.1.1 SEQUENTIAL / LINEAR SEARCH
Explain the linear search algorithm. Also give its limitations.
(Algorithm-1 Mark, Explanation-2 Marks, Limitation-1Mark; any related algorithm can be
considered)

Linear search is the easiest search technique in which each element is scanned in a sequential manner to
locate the desired element.
In this method, search begins with the first available record and proceeds to the next available record
until we find the target key or conclude that it is not found. Linear search is also called as "sequential
search”.

Example:
Consider an array with 5 elements
We are searching for element 91. To search 91 the item 91 is compared with element at A[0] then A[1]
and so on untill we find the target value or reach to the end of array.
When item is found it displays the location of an item else displays item not found.

3 21 11 91 19
0 1 2 3 4

#include<stdio.h>
#include<conio.h>
void main()
{
int a[10]={10,20,30,40,50,60,70,80,90,100};
int i,num,flag=1;
clrscr();
printf("LINEAR SEARCH");
printf("\n INPUT LIST:-\n");
for(i=0;i<=9;i++)
printf("%d\t",a[i]);
printf("\nEnter search element:");
scanf("%d",&num);
for(i=0;i<=9;i++)
{
if(num==a[i])
{
printf("\n Element found at %d index position ",i);
flag=0;
break;
}
}
if(flag==1)
printf("\n Element not found");
getch();
}

ARROW COMPUTER ACADEMY DSU 8788335443

`
2.1.2 BINARY SEARCH ALGORITHM
Binary search requires sorted list to perform searching. First find the lower index and upper index of an
array and calculate mid with the formula (lower+upper)/2.

Compare the search element with mid position element.

If both are equal then stop the search process. If both are not equal then divide list into two parts.

If the search element is less than mid position element then change the upper index value and use first
half of the list for further searching process.

If the search element is greater than mid position element than change the lower index value and use
second half of the list for further searching process.

Again find lower and upper index value and calculate mid value.

Repeat the process till element is found or lower index value is less than or equal to upper index value.

Step2:

X[5] X[6] X[7] X[8] X[9]

60 70 80 90 100

lower=5,upper=9;
mid=5+9/2=7
S==X[7] i.e 80==80
Search successful.
Element 80 is placed at the index position 7.

ARROW COMPUTER ACADEMY DSU 8788335443

`
Program to Implement Binary Search: [S-15]

#include<stdio.h>
#include<conio.h>
void main()
{
int a[10]={10,20,30,40,50,60,70,80,90,100};
int i,mid,num,upper=9,lower=0, flag=1;
clrscr();
printf("BINARY SEARCH");
printf("\n ARRAY ELEMENTS:-\n");
for(i=0;i<=9;i++)
{
printf("%d\t",a[i]);
}
printf("\nEnter search element:");
scanf("%d",&num);
while(lower<=upper)
{
mid=(upper+lower)/2;
if(num= =a[mid])
{
flag=0;
printf("\n Element found at %d index position ",mid);
break;
}
if(num>a[mid])
lower=mid+1;
else
upper=mid-1;
}
if(flag==1)
printf("\n Element not found");
getch();
}
}

ARROW COMPUTER ACADEMY DSU 8788335443

`
Distinguish between linear search and binary search. (any 4 points) [S-16]
(Any four relevant points 1M each)
**Note: example shall be considered as point of comparison

Linear Search Binary Search

Search element is compared with each element Search element is compared with mid element only
in list.
Simplest method of searching Comparatively difficult method of searching.
Easy to implement Comparatively difficult to implement
Given list of numbers can be sorted or unsorted Given list of numbers must be in sorted order
order
Linear search only requires equality Binary search requires an ordering comparison.
Comparisons.
Linear search has complexity O(n). Binary search has complexity O(log n).
Linear search is too slow to be used with large Binary search is more efficient method that could
lists. be used with large lists.
Linear search only requires sequential Access. Binary search requires random access to the data.

Q] Find location of element ‘H’ by using binary search algorithm in the given list. [S-16]
B F D A C E I G H J (Correct steps - 4 marks)
Ans: Binary search requires sorted array.
Input string:- B,F,D,A,C,E,I,G,H,J
Sorted list:- A,B,C,D,E,F,G,H,I,J
Array X [10]: used to store elements, lower is lower index of array, upper is upper index of array.
Step 1:-

lower=0,upper=9 ; mid=9/2=4.5=4
H!=E (num!=X[mid])
H>E (num>X[mid])
lower = mid+1=5
Step 2:

lower=5,upper=9;
mid=5+9/2=7
H==X[7]
Search successful.
Element H is placed at the index position 7.

ARROW COMPUTER ACADEMY DSU 8788335443

`
Find the position of element 29 using binary search method in an array ‘A’ given
below. Show each step.
A={11,5,21,3,29,17,2,43} 4M
Ans An array which is given A[ ]= {11,5,21,3,29,17,2,43} is not in sorted manner, first we need
to sort them in order;
So an array will be A[ ]={2,3,5,11,17,21,29,43} and the value to be searched is VAL = 29.
The binary search algorithm will proceed in the following manner.

Iteration 1:
BEG = 0, END = 7, MID = (0 + 7)/2 = 3
Now, VAL = 29 and A[MID] = A[3] =11
A[3] is less than VAL, therefore, we now search for the value in the second half of the array.
So, we change the values of BEG and MID.
Iteration 2:
Now, BEG = MID + 1 = 4, END = 7, MID = (4 + 7)/2 =11/2 = 5; VAL = 29 and A [MID] =
A [5] = 21
A[5] is less than VAL, therefore, we now search for the value in the second half of the segment.
So, again we change the values of BEG and MID.
Iteration 3:
Now, BEG = MID + 1 = 6, END = 7, MID = (6 + 7)/2 = 6 Now, VAL = 29 and A [MID] = A [6]=29
So, Element 29 is found at 6th location in given array A[]={2,3,5,11,17,21,29,43}.

ARROW COMPUTER ACADEMY DSU 8788335443

`
2.2 SORTING

Q] Define sorting. Enlist different sorting technique. [W-14]

(Definition - 1 Mark, Technique - 1 Mark (any 4 techniques are expected))
Q] What is sorting? Enlist two categories of sorting. [S-15]
(Definition of sorting 1M, list of two categories 1/2M each)
Q] Explain the concept of Sorting.

INTRODUCTION

Sorting: - Process by which a collection of items are arranged into ascending order or in
descending order.

The sorting is classified into two categories:

1. Internal Sorting.
2. External Sorting.

1. Internal Sorting:
In this sorting technique, all the data is retained in main memory only and the
data can be accessed randomly. Elements to be sorted are stored in an integer
array. These elements are sorted using one of the sorting algorithms.
2. External Sorting:
External sorting is carried on secondary storage. External sorting becomes necessity
if the number of elements to be sorted is too large to fit in main memory.

Sorting Techniques:

Bubble Sort

Insertion Sort

Selection Sort

Quick Sort

Radix Sort

ARROW COMPUTER ACADEMY DSU 8788335443

`
2.2.1 BUBBLE SORT
Q] Give the principal of bubble sort. (Principal-2 Marks) [S-15]
Ans: The algorithm in bubble sort involves two steps, executed over & over until data is sorted.

1. Compares two adjacent items

2. If necessary , swap (exchange) them

Sorting begins with 0th elements & it compares with 1st element in list. If 1st element is less than
0th element then interchange takes place. Like this all elements are compared with next element &
interchanged if required. At end of 1st pass largest element is placed at last position. In 2nd pass
again comparisons starts with 0th element & 2nd largest element is placed at second last position.
This process continues till list is in sorted order.

Q] Sort the following array in ascending order using bubble sort: 5, 9, 6, 2, 8, 1.

Let n be the number of elements in an array a[]. The first pass begins with the comparison of a[0]
with a[1]. If a[0] is greater than a[1], the two elements are exchanged. Larger one will be placed in
a[1] after first comparison. Comparison can move forward and after the last comparison of a[n-2]
and a[n-1], the largest element will be placed in a[n-1].

ARROW COMPUTER ACADEMY DSU 8788335443

`
Q] WAP to implement bubble sort. (Complete program 4 Marks) [S-14]
#include<stdio.h>
#include<conio.h>
void bubblesort(int a[],int n);
void main()
{
int i,n;
int a[30];
clrscr();
printf("enter the number of elements");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter the %d number",i);
scanf("%d",&a[i]);
}
bubblesort(a,n);
printf("sorted array is:");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
getch();
}
void bubblesort(int a[],int n)
{
int temp,i,j;
for(i=1;i<n;i++)
for(j=0;j<n-i;j++)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}

ARROW COMPUTER ACADEMY DSU 8788335443

`
Algorithm for bubble sort
void bubblesort(int a[],int n)
{
int temp,i,j;
for(i=1;i<n;i++)
for(j=0;j<n-i;j++)
if(a[j]>a[j+1]) // comparison between elements
{
temp=a[j]; // swap if previous element is greater than next element
a[j]=a[j+1];
a[j+1]=temp;
}
}

Analysis of Bubble Sort

Line 1 for(i=1;i<n;i++)
Line 2 for(j=0;j<n-i;j++)
Line 3 if(a[j]>a[j+1])
Line 4 exchange a[j] and a[j+1]

For a fixed value of i, the loop of lines (2 to 4) runs n-i times.

Hence total number of comparisons

ARROW COMPUTER ACADEMY DSU 8788335443

`
Q] Sort the following numbers in ascending order using bubble sort.
A= {19, 2, 27, 3, 7, 5, 31}

ARROW COMPUTER ACADEMY DSU 8788335443

`
2.2.2 SELECTION SORT
Q] Describe principal of Selection sort. [W-08, W-11, W-12]

Selection sort is a very simple sorting method. In the ith pass, we select the lowest value element
among a[i], a[i+1], ….. , a[n-1] and we swap it with a[i]. As a result after ith pass, first i elements
will be in sorted order.

Algorithm:

void selection_sort(int a[],int n)

{
int i,j,pos,temp;
for(i=0;i<n-1;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(a[pos]>a[j])
pos=j;
} Algorithm:

for(i=0; i<n-1; i++)

{
temp=a[i]; select the smallest element among
a[i]=a[pos];
a[pos]=temp; a[i], a[i+1], ….. , a[n-1] and
}
sawp it with a[i];

}
}

ARROW COMPUTER ACADEMY DSU 8788335443

`
Q] Write a program for selection sort. Write Complexity of Selection Sort. [W-15, S-17]

#include <stdio.h>
#include<conio.h>
void selection_sort(int[],int);
void main()
{
int a[100],n,i;
clrscr();
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
printf("enter the array elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}

selection_sort(a,n);

printf("The Sorted List is \n");

for(i=0;i<n;i++)
{
printf("\t %d",a[i]);
}
getch();
}

void selection_sort(int a[],int n)

{
int i,j,pos,temp;
for(i=0;i<n-1;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[pos])
pos=j;
}

{
temp=a[i];
a[i]=a[pos];
a[pos]=temp;
}

}
}

ARROW COMPUTER ACADEMY DSU 8788335443

`
Complexity of selection sort:- O (n2)
Analysis of Selection Sort:

Selection sort is not Data Sensitive. In ith pass, n-i comparisons will be needed to select the smallest element.

Thus the number of comparisons needed to sort an array having n elements

ARROW COMPUTER ACADEMY DSU 8788335443

`
2.2.3 INSERTION SORT
Q] Describe working of inserting sort. Demonstrate working of insertion sort algorithm to sort 6
elements. [W-16]

In insertion sort, sorting is done on the principal of inserting the element at it correct place in previously
sorted list.
In first pass, 1st index element is compared with 0th index element.
If 0th index element is greater than 1st index element then store 1st index element into a temporary
variable and shift 0th index element to its right by one position.
Then insert temporary variable value in 0th position.
In pass 2, compare 2nd index element with 0th index and then 1st index elements.
If required perform shift and insert operations.
In each pass fix one position and compare it with all elements placed before it.
Continue this process till last position element is compared with all elements placed before it.

Example-

ARROW COMPUTER ACADEMY DSU 8788335443

`
Program of Insertion Sort
#include <stdio.h>
#include<conio.h>
void insertion_sort(int[],int);
void main()
{
int a[100],n,i;
clrscr();
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
printf("enter the array elements\n");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}

insertion_sort(a,n);

printf("The Sorted List is \n");

for(i=0;i<n;i++)
{
printf("\t %d",a[i]);
}

getch();
}

void insertion_sort(int a[],int n)

{
int i,j,temp;

for(i=1;i<n;i++)
{
temp=a[i];

for(j=i-1;j>=0 && a[j]>temp;j--)

{
a[j+1] = a[j];
}

a[j+1] = temp;
}
}

ARROW COMPUTER ACADEMY DSU 8788335443

`
2.2.4. QUICK SORT
Q] Write an algorithm for quick sort. (4 marks) [S-14]
Q] Describe quick sort. State its advantages and disadvantages. [W-15]
(Description 2M, advantages 1M, disadvantages 1M)

Quick sort is the fastest internal sorting algorithm with the time complexity = 0(n log n).

The basic algorithm to sort an array a [ ] of n elements can be described recursively as follows :

1. If n <= 1, then return

2. Pick any element V in a[ ]. This is called the pivot.
Rearrange elements of the array by moving all elements xi > V right of V and all elements
xi <= V left of V.
If the place of the V after re-arrangement is j, all elements with value less than V, appear in
a[0], a[1] ... a [ j -1] and all those with value greater than V appear in a[j+1]……a[n-1].
3. Apply quick sort recursively to a[0] a[j - 1] and to a [ j + 1] ………….a [ n - 1].
Advantages:
1) Efficient average case as compared to any other sorting algorithm.
2) It is faster than other algorithm such1 as bubbles sort, selection sort and insertion sort.
Disadvantages:
1) It is complex and massively recursive.
2) The worst-case complexity of quick sort is O(n^2), which is worse than the O (n log n)
worst-case complexity of algorithms like merge sort, heapsort, binary tree sort, etc.

ARROW COMPUTER ACADEMY DSU 8788335443

`
2.2.5 RADIX SORT
Q) Describe radix sort algorithm. Sort the following numbers in ascending order using radix sort.
12, 8, 25, 4, 66, 2, 98, 225.

(Description of Algorithm 4Marks, radix sorting on given numbers-4Marks)

Ans: Radix sort algorithm:-

Radix Sorting: -
In this method, ten buckets (0-9) are used to sort elements of an input list.
All the elements are sorted according to their digit position from each element.
In pass one each element is placed inside the bucket with respect its unit position digit. After placing all
elements inside the buckets, read those from 0th bucket to 9th bucket.
In pass 2, elements are placed in buckets with respect to 10th position digit from each element.
In each pass one position is considered to arrange all the elements in bucket.
At the end of each pass, elements are collected from buckets and given as input to the next pass.
Total number of passes required for sorting is equal to maximum number of digits present in the largest
number from the input list.
Last pass gives sorted list after reading all elements from 0 th bucket to 9th bucket.

Algorithm:

Step 1: large = find the largest number in a[]

Step 2: passes = Number of digits in large
Step 3: Div = 1 /* divisor for extracting ith least significant digit */
Step 4: for(i=1; i <= passes; i++)
{
1. Initialize all buckets b0 to b9
2. for each number x from a[0] to a[N-1]

{
1. bucket_no=(x/div)%10
2. insert x in bucket with bucket_no
}

3. Copy elements of buckets back in array a[]

4. Div = Div *10

Step5: Exit

ARROW COMPUTER ACADEMY DSU 8788335443

`

ARROW COMPUTER ACADEMY DSU 8788335443

`
Q] Sort following elements by radix sort algorithm. 87.3, 2.34, 7.29, 3.59, 45.8, 3.79, 3.20, 422.

{**Note: As radix sort cannot be applied on decimal number, consider all number without
decimal i.e. 873,234,729,359,458,379,320,422)**}

Ans:-

OR
ARROW COMPUTER ACADEMY DSU 8788335443
`

ARROW COMPUTER ACADEMY DSU 8788335443

`

Q] Sort the given no. in ascending order using radix sort. Numbers: 348, 14, 614, 5381, 47
(Each pass- 1 Mark)

Ans: 348, 14,614,5381,47

ARROW COMPUTER ACADEMY DSU 8788335443

`
Insert element in Array

#include<stdio.h>
#include<conio.h>
void main()
{
int a[10],pos,i,n,value;
clrscr();
printf("enter no of elements in array of students:");
scanf("%d",&n);
printf("enter %d elements are:\n",size);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("enter the position where you want to insert the element:");
scanf("%d",&pos);
printf("enter the value into that poition:");
scanf("%d",&value);
if(pos>0 && pos<=n)
{
for(i=n-1;i>=pos-1;i--)
{
a[i+1]=a[i];
}
a[pos-1]=value;
printf("final array after inserting the value is\n");
for(i=0;i<=n;i++)
{
printf("%d\n",a[i]);
}
}
else
{
printf("Enter correct position");
}
getch();
}

ARROW COMPUTER ACADEMY DSU 8788335443

`
Deleting element at Given position from array
#include <stdio.h>
#include<conio.h>
void main()
{
int array[100],pos,i,n;
clrscr();
printf("Enter number of elements in array\n");
scanf("%d", &n);

printf("Enter %d elements\n", n);

for (i=0; i<n; i++)

scanf("%d", &array[i]);

printf("Enter the position where you wish to delete element\n");

scanf("%d", &pos);

if (pos>0 && pos<n+1)

{
for (i = pos-1; i<n-1; i++)
array[i] = array[i+1];

printf("Resultant array:\n");

for (i = 0; i < n - 1; i++)

printf("%d\n", array[i]);
}
else
{
printf("Deletion not possible.\n");
}

getch();
}

ARROW COMPUTER ACADEMY DSU 8788335443

LINKED LIST
Q] Define linked list with example. 2M [S17]
Q] Explain the concept of linear list with example. [S14]
(Explanation – 3 Marks, Diagram 1 Mark)

Ans:
Linked list:
It is linear collection of data elements.
Each element in linked list is called as ‘node’.
Each node contains two fields.
First is INFO which stores data & second is NEXT which is linked with address of next node in a
list.
This structure allows for efficient insertion or removal of elements from any position in the
sequence.

LINKED LIST TERMINOLOGY

Q] Explain the concept of information, Next, Null Pointer and empty list with respect to link
list. (each term 1M) [S
14][W 16]
Q] Define the term: [S 15]
i) Node ii) Address iii) Null pointer iv) Next pointer for linked list.

 Node: Each element in linked list is called as ‘node’. Each node contains two fields. First is
INFO which stores data & second is NEXT which is linked with address of next node in a
list.
 Address: Address indicates location of node.
 Info Field: It is used to store data inside the node.
 Next Pointer: Holds the Address of the next node, which intern links the nodes together.
 Null Pointer: It is used to specify end of the list. The last element of list contains NULL
pointer to specify end of list.
 Empty List: A linked list is said to be empty if head (start) node contains NULL pointer.

ARROW COMPUTER ACADEMY DSU 8788335443

OPERATIONS
Q] List and define operations of linked list. [W 15][S 16]
Ans:
The basic operations that can be performed on a list are:
1. Creation: This operation is used to create a node in the linked list.
2. Insertion: This operation is used to insert a new node
 At the beginning of the list,
 At a certain position and
 At the end.
3. Deletion: This operation is used to delete node
 From the beginning of the list: To delete first element
 From a certain position:-
 From the end.
4. Traversing: It is a process of going through all the nodes of a linked list from one end to the other
end.
5. Display: This operation is used to print all nodes’ information field.
6. Searching: To search a specific element in given linked list.
7. Count:-To count number of nodes present in list.
8. Eraseall: To free/delete all elements from the list.

INSERTING NODE IN LINKED LIST

Q] Explain insertion of new node at start and at end in singly linked list.
Q] Write an algorithm to insert a new node as the last of a singly linked list. Give example. [W 16]
Q] Write an algorithm to insert a new node at the beginning of a singly linked list. Give example. [W
14]

Ans:
Inserting node at start in the SLL (Steps):
In this operation, new node can be created and added at the beginning of a list. New node points
to existing first node and start points to newly added node.
1. Create New Node
2. Fill Data into “Data Field“
3. Make its “Pointer” or “Next Field” as NULL
4. Attach this newly Created node to the start.
a) Set the next field of new node to beginning of the linked list.
b) Change the reference pointer of the linked list (Head) to point to the new node.
5. Make new node as Starting node

ARROW COMPUTER ACADEMY DSU 8788335443

Structure of New Node:

struct node
{
int data;
struct node *next;
};

Create New Node : -

struct node *newNode;

newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = NULL;

Insert it at Beginning:-

newNode->next = head;
head = newNode;

Inserting node at last in the SLL (Steps):

1. Create New Node
2. Fill Data into “Data Field“
3. Make its “Pointer” or “Next Field” as NULL
4. Node is to be inserted at Last Position so we need to traverse SLL up to Last Node.
5. Make link between last node and new node

struct node *temp = head;

while(temp->next != NULL)
{
temp = temp->next;
}

temp->next = newNode;

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Write an algorithm to insert a node in between in a link list. (4 marks)

Algorithm to insert a node in between in a link list.

void add_at_specified(struct node *q, int loc, int no)
{
Step 1: - Begin
Step 2:- Allocate memory for new node;
struct node *newNode;
newNode = malloc(sizeof(struct node));
Step 3: set newNode->data = no ; newNode->next = NULL;
Step 4:- Create and Initialize temp to the beginning of the linked list.
struct node *temp = head;
Step 4:- Traverse temp till the previous node of the specified location. (Previous node = temp node)
Step 5: - Change next pointers to include new node in between
newNode->next = temp->next;
temp->next = newNode;
Step 6: Stop

ARROW COMPUTER ACADEMY DSU 8788335443

TRAVERSE LINKED LIST
Q] Write an algorithm to traverse a singly linked list. [W 15] [W 16]
Ans:
Traversal of Linked List always starts from the first node. In order to traverse a linked list in the
forward direction, a pointer type variable temp is assigned the address of the first node.
When temp is NULL, we know that we have reached the end of the linked list so we get out of the
while loop.

1. if ( head = =NULL)
then display "linked list is empty”.

2. Otherwise visit each node of linked list and display its data till end of the list
struct node *temp = head; // Assign a temporary pointer temp to starting node
while ( temp != NULL)
do
{
Display temp->data // display node information
temp=temp->next; // Next field of the node pointed by temp contains
the address of the next node.
}

ARROW COMPUTER ACADEMY DSU 8788335443

 Delete from a Linked List
You can delete either from the beginning, end or from a particular position.
1. Delete from beginning

Node to be deleted is node1.Create a temporary node as ‘temp’. Set ‘temp’ node with the address
of first node. Store address of node 2 in header pointer ‘start’ and then delete ‘temp’ pointer with
free function. Deleting temp pointer deletes the first node from the list.
Algorithm:
Point head to the second node
Set temp = head
head = head->next;
Make sure to free unused memory
free(temp); or delete temp;
2. Delete from end
Node to be deleted is node 3.Create a temporary node as ‘temp’ and ‘q’.
Set ‘temp’ node with the address of first node.
Traverse the list up to the second last node and mark the last node as ‘q’.
Store NULL value in address field of ‘temp’ node and then delete ‘q’ pointer with free function.
Deleting q pointer deletes the last node from the list.

Algorithm:-
 Traverse to second last element
 Change its next pointer to null

struct node* temp = head;

while(temp->next->next!=NULL)
{
temp = temp->next;
}
temp->next = NULL;

ARROW COMPUTER ACADEMY DSU 8788335443

3. Delete from middle
Node to be deleted is node3.
Create a temporary node as ‘temp’ and ‘q’.
Set ‘temp’ node with the address of first node.
Traverse the list up to the previous node of node 3 and mark the next node (node3) as ‘q’.
Store address from node ‘q’ into address field of ‘temp’ node.
Then delete ‘q’ pointer with free function.
Deleting ‘q’ pointer deletes the node 3 from the list.

for(int i=2; i< position; i++)

{
if(temp->next!=NULL)
{
temp = temp->next;
}
}

temp->next = temp->next->next;

SERARCHING ELEMENT IN LINKED LIST

Q] With suitable diagram, explain ‘searching’ of a node in a linked list. [S 15]
Q] Write an algorithm for ‘search’ operation in an unsorted linked list.[ W14][S 17]
Algorithm:
This algorithm finds KEY first appears in linked list .
Step-1: Initialize the temp pointer with the beginning of the List.
Set temp = head.
Step 2:- Repeat Step 3 while temp!=NULL
Step 3. Compare the KEY value with the Current node value;
if they match then quit there
i.e if (temp->data = = KEY),
then: print: SEARCH IS SUCCESSFUL and Exit
else:

Move the pointer to point to the next node in the list

ARROW COMPUTER ACADEMY DSU 8788335443

 Set temp=temp->next [temp now points to the next node]
4. If search is unsuccessful, print: SEARCH IS UNSUCCESSFUL
5. Exit.

Algorithm:-

struct node * temp = head;

while(temp ! = NULL)
{
if(temp -> data == key)
{
Display “Search is successful”;
break;
}
else
{
temp=temp->next;
}
}

COUNT NUMBER OF NODES IN A LINKED LIST

Q] Write an algorithm to count number of nodes in singly linked list.[S 16]

Ans:
ALGORITHM:
1. Start
2. check if the list is empty or not
if head ==NULL
OUTPUT: “Zero nodes” and exit
else goto step 3
3. Set the head pointer to a temporary variable
temp=head
4. Traverse till the last node

ARROW COMPUTER ACADEMY DSU 8788335443

while(temp!= NULL)
{
increase the node count by 1
point to the next node in the list
temp=temp->next
}
5. Display the total count of nodes OUTPUT count
6. Stop

ARROW COMPUTER ACADEMY DSU 8788335443

DOUBLY LINKED LIST
Q] Describe doubly linked list with its node structure. [S 15]
Q] Describe doubly linked list with an example.[W 14]
Q] Give node structure for doubly linked list .Write advantages of doubly linked list over
singly list. [S 16]

In Doubly-linked list each node contains two links- one to the previous node and other to the next
node.
The previous link of the first node and the next link of the last node points to NULL.
In Doubly linked list, a node comprises of total three fields

1. Data: contains information. E.g.10, 20, etc.

2. Next pointer: Contains address of the next node
3. Prev pointer: Contains address of the preceding node.

The structure defined for doubly linked list is-

struct node
{
int data;
struct node *next,* prev;
}

EXAMPLE:

Advantages:
1. Traversal is done in both the directions,
2. Insertion and deletion can be easily performed.
3. Searching an element is faster.
4. It is easy to reverse the linked list.

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Distinguish between singly linked list and doubly lined list. (4 points) (For each point -
1M)

Singly Linked List Doubly Linked List

1. It is also called One way header list 1. It is also called Two way header list
2. Can be traversed in only one direction 2. Can be traversed in both directions –
forward as well as backward
3. It has only 1 pointer 3. It has only 2 pointers
4. Node in a singly linked list has two fields 4. Node in a doubly linked list has three
– Information and next pointer fields
– information, next pointer and previous
Pointer

Q] Draw representation of linear linked list, circular linked list and doubly linked list.
[S17]

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Differentiate between linear linked list, circular linked list and doubly linked list.(
Min. 4 points each). [S 17]

Prof. Somwanshi A.A.

Program to Create Linked List, insert element at beginning, display list , search an
element.

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
}*head;

void create_list(int value)

{
struct node *temp,*newnode;
newnode = malloc(sizeof(struct node));
newnode -> data =value;
newnode -> next =NULL;
if(head==NULL)
head=newnode;
else
{
temp=head;
while(temp-> next!=NULL)
{
temp=temp-> next;
}
temp->next = newnode;
}
}

void addAtBeginning(int value)

{
struct node *newnode;
newnode= malloc(sizeof(struct node));
newnode-> data = value;
newnode-> next = NULL;
newnode-> next = head;
head=newnode;
}

void display()
{
struct node *temp;
if(head==NULL)
{
Prof. Somwanshi A.A.
printf("\n List is Emplty");
}
temp=head;
printf("\n List is \n");
while(temp!=NULL)
{
printf("%d -> ",temp->data);
temp=temp->next;
}
printf("Null");
}

int searchNode(struct node *head,int key)

{
struct node *temp = head;

//iterate the entire linked list and print the data

while(temp != NULL)
{
//key found return 1.
if(temp->data == key)
return 1;
temp = temp->next;
}
//key not found
return -1;
}

int main()
{
int data,n,i,key;
head=NULL;
printf("How many nodes u want to add in Linked List \n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter data value\n");
scanf("%d",&data);
create_list(data);
}

display(head);

printf("\n Enter value of new node to be inserted at beginning\n");

scanf("%d",&data);

Prof. Somwanshi A.A.

addAtBeginning(data);
display(head);

printf("\n Enter The Element to be Searched\n");

scanf("%d",&key);

if(searchNode(head,key) == 1)
printf("Search Found\n");
else
printf("Search Not Found\n");

return 0;
}

Q] Write a program to delete the Specific Element From the Linked List

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
}*head;

void create_list(int value)

{
struct node *temp,*newnode;
newnode = malloc(sizeof(struct node));
newnode -> data =value;
newnode -> next =NULL;
if(head==NULL)
head=newnode;
else
{
temp=head;
while(temp-> next!=NULL)
{
temp=temp-> next;
}
temp->next = newnode;
}
}

void deleteNode(int key)

Prof. Somwanshi A.A.
{
//temp is used to freeing the memory
struct node *temp,*prev;
temp = head;
prev = head;

if (temp != NULL && temp->data == key)

{
head = temp->next; // Changed head
free(temp); // free old head memory
return;
}

while (temp != NULL && temp->data != key)

{
prev = temp;
temp = temp->next;
}

prev -> next = temp -> next;

free(temp);
}

void display()
{
struct node *temp;
if(head==NULL)
{
printf("\n List is Emplty");
}
temp=head;
printf("\n List is \n");
while(temp!=NULL)
{
printf("%d -> ",temp->data);
temp=temp->next;
}
printf("Null");
}

int main()
{
int data,n,i,key;
head=NULL;
printf("How many nodes u want to add in Linked List \n");
scanf("%d",&n);
Prof. Somwanshi A.A.
for(i=0;i<n;i++)
{
printf("enter data value\n");
scanf("%d",&data);
create_list(data);
}

display(head);

printf("\n Enter The Element to be Deleted\n");

scanf("%d",&key);

deleteNode(key);

display(head);
return 0;
}

Prof. Somwanshi A.A.

STACK
Stack is a LIFO (Last In First Out) structure.
It is an ordered list of same type of elements.
A stack is a linear list where all insertion and deletion are permitted only at one end of the list.
When elements are added it grows at one end. Similarly, when elements are deleted from a
stack, it shrinks at the same end.
Formally, a stack may be defined as follows:
typedef struct stack
{
int data[SIZE]; /* SIZE is a constant, maximum number of elements that can be stored */
int top;
} stack ;

STACK AS AN ADT
Q] Describe the stack as an abstract datatype. 4M [S-17]
Ans:
An Abstract Data type is one where we can store elements and also perform certain operation
on those elements.
Stack provides such facilities.
Stack as an abstract data type contains stack elements such as array(list), stack top and its
operations such as initialize, empty, full, push, pop, display.

Stack elements: data[size], stack top

Stack operations:
(1) void initialize ( ):
It initializes a stack as an empty stack. Initial value of top is set to -1.
(2) int empty ( ):
Function checks whether the stack is empty. It returns 1 or 0 depending on whether
the stack is empty or not.
(3) int full ( ):
The function checks whether the stack is full. A stack is said to be full when the
associated array is completely filled up. Whenever the stack is full, top points to the
last element (i.e. data[SIZE-l]) of the array. The function returns 1 or 0 depending on
whether the stack is full or not.
(4) int pop ( ):
The function deletes topmost element from the stack and also returns it to the calling
program. Deletion from an empty stack will cause underflow.
When pop operation is called stack top is decremented by 1.

Algorithm for pop operation

Step 1: First check for empty i.e. if stack top is -1 means there is no element in the
stack. Then pop operation cannot be performed.
Step 2: If there is no underflow then it removes an element placed at top of the stack.
And then decrement the stack top by 1.

void push (int x):

ARROW COMPUTER ACADEMY DSU 8788335443

 Push: Push operation is used to insert an element into the stack. The function inserts
the element x onto the stack pointed by top. Insertion will cause an overflow if the
stack is full.

Algorithm for push operation

Step 1: Initially stack top is set to -1 as array started with 0 to indicate empty stack
Step 2: First check for overflow i.e.
if stack top =max-1 (maximum size of an array)
then push operation cannot be performed.
Step 3: If there is no overflow then increment the stack top by 1 and insert new element at
stack top position.

Q] Stack is linear data structure. Yes/No? Justify your answer. 2M [S 17]

(Yes:1 mark, Justification: 1 mark)
Ans: Yes.
Stack is a Linear data structure.
Justification:
Linear data structures allow organization of data elements in proper sequential manner.
Stack is linear data structure because it organizes elements in a particular sequence.
Stack allows insertion and deletion of element only from one end.

Q] Describe PUSH and POP operation on stack using array representation. [W 16]
Q] Write the procedure for implementing stack using arrays. [S 16]
(Relevant description - 4 marks)
Q] Describe the representation of stack using arrays. [W 15]
(Relevant description – 4M)
Ans:
1. Definition: Stack is a linear data structure which follows Last-In First- Out (LIFO)
principle where, elements are added and deleted from only one end called as stack top
2.

3. PUSH Operation:
a. If (top= =max-1)
then display “Stack overflow”
b. else
do top=top+1
a[top]=data
4. POP Operation:
a. If (top= = -1)
then display “Stack underflow”
b. else
ARROW COMPUTER ACADEMY DSU 8788335443
 do Data= a[top]
Top=top-1

Q] State importance of top pointer in stack. Explain stack overflow and underflow. [S 16]
(Importance - 1 mark, overflow - 1 ½, underflow - 1 ½)

Ans: Importance of top:

Top is a pointer variable which points to top most element of stack

After every push operation the top is incremented by one.
After every POP operation the top is decremented by one.
Top helps in identifying stack overflow and stack underflow condition.

Q] Describe the term stack overflow and stack underflow with example. State any
four applications of stack.
[W 15]
(Description of stack overflow 3M, underflow 3M, any four applications each ½ M)
Ans.
Stack overflow:
When a stack is full and push operation is called to insert a new element, stack is said to be
in overflow state.

ARROW COMPUTER ACADEMY DSU 8788335443

Stack underflow:
When there is no element in a stack (stack empty) and pop operation is called then stack is
said to be in underflow state.

Q] State applications of stack. [W-14]

(Any 2 Applications - 1 Mark each)

Ans: Following are the applications of stack

 Recursion
 Reversing String
 Interrupt handling
 Expression conversion & evaluation: Polish Notation
 Stack machine
 Matching parenthesis in an expression

Q] What is the effect of PUSH and POP operation on to the stack? The stack contains 10,
20, 22, 26, 28, 30 with 30 being at top of the stack. Show diagrammatically the effect of
PUSH 46, PUSH 48, POP, POP, POP, PUSH 82

[S-14]

ARROW COMPUTER ACADEMY DSU 8788335443

1) PUSH: The process of adding new element to the top of the stack is called PUSH operation.
As the new element is added to the top, after every push operation the top is incremented by
one.
2) POP: The process of deleting an element from top of the stack is called POP operation. As
deletion takes place from the top of the stack. After every POP operation the top of the stack is
decremented by one.

Q] Write an algorithm to convert infix string into postfix (Fully parenthesized) (Any correct
algorithm indicating steps for conversion 4M) [W 15]
Ans:

1. Accept infix string as an input array and add the symbol ‘#’ at the end of the array
2. Read the string symbols one – by – one from left to right
3. If the current symbol is an operand, add it into postfix array
4. If the current symbol is left parenthesis ‘(‘, push it into operator stack
5. If the current symbol is an operator POP all the operators having precedence greater than or
equal to the current operator and add it to postfix array else PUSH the current operator into
operator stack.
6. If the current symbol is right parenthesis ‘)’, POP all the operators from operator stack and Add
it to the Postfix array till the respective left parenthesis is encountered
7. Repeat Steps 2 till 6, until the end of input array indicated by ‘#’ symbol.
8. Display Postfix expression for the given infix string.

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Convert the following infix expression to its postfix form (2 marks each) [S-14]
i) A+B-C*D/E+F

ii)A*B-C^D+E/F

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Covert the following infix expression into a postfix expression and show details of
stack at each step of conversion. Expression: ((A+B)*D) (E - F)
(Correct postfix expressions - 2 Marks, For steps - 6 Marks)

ARROW COMPUTER ACADEMY DSU 8788335443

Postfix expression =AB+D*EF-^

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Convert the given infix expression to postfix expression using stack and the details of
stack at each step of conversation. EXPRESSION P* Q ↑ R – S/T +[U/V]

THE POSTFIX EXPRESSION IS:PQR↑*ST/-UV/+

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Translate the following infix expression to its equivalent prefix expression.
(x + y)* (p – q).
Evaluate the above prefix expression with following values x=2, y=3, p=6, q=2.

Evaluation of prefix expression

ARROW COMPUTER ACADEMY DSU 8788335443

Q) Convert infix string ( (A + B) * (C – D) ) /(E + F) into prefix string with stack.
Show the content of stack in each step.
(Correct answer with stack content 4M)

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Convert the following arithmetic expression P written in postfix notation into infix. [S
15]
P: 5, 6, 2, +, *, 12, 4, /, - also evaluate P for final value.

(Each 2 step carries -1 Mark)

Ans: Postfix to infix form:
Postfix expression (P): 5, 6, 2, +,*, 12, 4, /,-
Step 1: Grouping of tokens as per the sequence of evaluation.

Step 2: Operators are moved between the two operands of the group 5*(6+2)-12/4

ARROW COMPUTER ACADEMY DSU 8788335443

RECURSION

Q] Define recursion. State any two applications where recursion is used.

[W 16]

Recursion is the process of calling function by itself. A recursive function body contains
function call statement that calls itself repeatedly.

Applications:
1. Factorial of number 2. Tower of Hanoi 3. Fibonacci Series

Q) Explain how stack can be used to reverse a list using suitable example. [S
16]
(Description - 2 marks; Example - 2 marks)

Ans:

A simple application of stack is reversal of list. To reverse a list, the elements of list are pushed
onto the stack one by one as the element read from first to last. Once all elements are pushed
on the stack & they are popped one by one. Since the element last pushed in comes out first,
hence reversal of string occurs. Consider following example where a list contains elements as
{1, 2, 3, 4, 5, 6}. Every push operator will push an element on top of stack. Once all elements
are pushed, one can pop all elements and save it which results in reversing of list as {6, 5, 4, 3,
2, 1}.

Q] Define recursion. Write a ‘C’ program to calculate the factorial of number using
recursion.
(Definition – 2 Marks, Program – 6 Marks) [S 14]
Ans: A function is called by itself is called as recursion

ARROW COMPUTER ACADEMY DSU 8788335443

#include<stdio.h>
#include<conio.h>
int fact(int n);
void main()
{
int n;
clrscr();
printf("/nEnter an integer:");
scanf("%d",&n);
printf("/nThe factorial of %d is = %d",n,fact(n));
getch();
}
int fact(int n)
{
if(n==1)
return 1;
else
return(n*fact(n-1));
}
Output : Enter an integer : 6
The factorial of 6 is = 720

ARROW COMPUTER ACADEMY DSU 8788335443

Q] How stack is used in Recursion? Describe with suitable example. 4M [W 16]
Ans:
1. Recursion is the process of calling function by itself. A recursive function body contains
function call statement that calls itself repeatedly.
2. In the recursive call, each time a function executes the same number of statements
repeatedly. Each function contains local variables.
3. When a recursive function is called, before executing the same function again, the local
variables are saved in the data structure stack. This way, in each execution local variables
values are copied to the stack.
4. When the recursive function terminates one by one each element is removed from the stack
and we get the result.
Example: Factorial of number, Tower of Hanoi. Fibonacci Series

int fact(int n)
{
if(n==1)
return 1;
else
return(n*fact(n-1));
}

return(n*fact(n-1)); This statement gives recursive call to the function. Each time when
factorial function is called stack stores the value of current local variables and then next
variable. If factorial of 5 then first time stack will have 5 then in 2nd call 4 … till the last call
stack gets the element. Once it is 1 all variable values are pop & result is calculated.

Q) Define recursion. Write a ‘C’ program for multiplication of natural numbers using recursion.
(Definition -1Mark, Logic of program- 3Marks) [S 15]

Ans: Definition: - Process of calling function itself is known as recursion in C programming.

Program:-

7*5=35
7+7+7+7+7
5+5+5+5+5+5+5

#include<stdio.h>
#include<conio.h>
int multiply(int,int);
void main()
{
int a,b,p;
clrscr();
printf("Enter any two integers: ");
scanf("%d%d", &a,&b);
p = multiply(a,b);
printf("Multiplication of two integers is %d",p);

ARROW COMPUTER ACADEMY DSU 8788335443

getch();
}
int multiply(int a,int b)
{
static int product=0,i=0;
if(i < a)
{
product = product + b;
i++;
multiply(a,b);
}
return product;
}

ARROW COMPUTER ACADEMY DSU 8788335443

 QUEUE
DEFINITION
Q] Define the terms FRONT and REAR of queue. Enlist any four operations of queue. [W
15]
Q] Explain the terms front and rear with relevance to queue. List the operations to be
performed at these ends. [S 16]
(Description of front - 1 mark; rear - 1 mark; any four operations - 2 mark)

Queue is a data structure where elements are inserted at one end known as “Rear” and
deleted from the other end known as “Front”.
Queue is FIFO (First In First Out).

Front: - This end is used for deleting an element from a queue. Initially front end is set to -1.
Front end is incremented by one when an element has to be deleted from queue.

Rear: - This end is used for inserting an element in a queue. Initially rear end is set to -1. rear
end is incremented by one when a new element has to be inserted in queue.

ARRAY REPRESENTATION

Q] Sketch representation of queue as an array. [2 M] [S 17]

OPERATIONS ON QUEUE

initialize(): Initialize a queue by setting the values of rear and front to -1.
enqueue(): Inserts an element at the rear end of the queue.
dequeue(): Deletes the front element and returns the same.
empty(): It returns true (1) if the queue is empty and returns false (0) if the queue is not
empty.
full(): It returns true(1) if the queue is full and returns false(0) if the queue is not full.
display (): Prints the queue elements.

ARROW COMPUTER ACADEMY DSU 8788335443

QUEUE AS ABSTRACT DATA TYPE

Q] Describe the queue as abstract data type. (Elements - 2 Marks, Operations – 2 Marks)

Ans: Queue is a data structure where elements are inserted at one end known as “Rear” and
deleted from the other end known as “Front”.
Queue is an abstract data type because it does not only allow storing elements but also allows
perform certain operation on these elements.

Following are elements of queue

1. Front
2. Rear
3. array

Operations performed on Queue are as follows.

initialize(): Initialize a queue by setting the values of rear and front to -1.
enqueue(): Inserts an element at the rear end of the queue.
dequeue(): Deletes the front element and returns the same.
empty(): It returns true (1) if the queue is empty and returns false (0) if the queue is not
empty.
full(): It returns true(1) if the queue is full and returns false(0) if the queue is not full.
display (): Prints the queue elements.

ARROW COMPUTER ACADEMY DSU 8788335443

INSERTION AND DELETION ON QUEUE
Q] Write a code to delete an element in queue. [W 16]
Q] Write the procedure for inserting and deleting an element from queue. [W 15] [S 15]
(Insertion procedure- 2M, Deletion procedure- 2M)
Ans:
Procedure for Insert:-

Step 1: [check overflow]

if (rear = = max -1) then write “queue is full” and return, otherwise go to step 2
Step 2: [increment rear point]
rear = rear + 1
Step 3: [insert element]
a [rear] = item
Step 4: Check for Front
if(front==-1)
{
front = 0;
}
Procedure for Delete:-
Step 1: [check Underflow]
if (front == -1)
then display “queue is empty”
otherwise go to step 2
Step 2: [delete element from queue]
data = a [front]
Step 3: [check front and rear pointer]
if (front == rear)
then front = rear = -1
else
front = front + 1
Step 4: Return to calling function
.
Q] Differentiate between stack and Queue [S 17][S 15]

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Write a program for insert and delete operation perform on queue. State any two
application of queue. [S 17]

#include<stdio.h>
#include<conio.h>
#define MAX 3
int rear= -1;
int front= -1;
int arr[MAX];

void insert()
{
int x;
if(rear ==(MAX-1))
printf("\n queue is full");
else
{
printf("\n enter element to be inserted:");
scanf("%d", & x);
rear=rear+1;
arr[rear]=x;
if(front==-1)
{
front=0;
}
}
}
void del()
{
int data;
if(front==-1)
printf("\n queue is empty");
else
{
data=arr[front];
printf("\n deleted element is %d",data);

if(front==rear)
{
front=-1;
rear=-1;
}
else
front=front+1;
}
}

ARROW COMPUTER ACADEMY DSU 8788335443

void display()
{
int i;
for(i=front;i<=rear;i++)
{
printf("%d \t",arr[i]);
}
}
void main()
{
int ch;
clrscr();
while(1)
{
printf("\n1.insert()\n2.delete()\n3.display()\n4.Exit");
printf("\n Enter your Choice");
scanf("\n%d",&ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("wrong choice");
}
}
}

APPLICATION OF QUEUE

1) Simulation
2) CPU scheduling in multiprogramming and time sharing systems.
3) Queue is used in round robin scheduling algorithm
4) Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
5) In real life, Call Centre phone systems will use Queues, to hold people calling them in an
order, until a service representative is free.
6) Handling of interrupts in real-time systems.

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Explain ‘Queue Full’ and ‘Queue Empty’ condition with suitable example. [S 16]
(Description - 1 mark each; Example - 1 mark each)

Queue Full:
Before inserting an element in queue 1st check whether space is available for new element in
queue. This can be done by checking position of rear end. A queue is full when its rear pointer
points to max -1 position. Max is maximum number of elements in a queue. If rear pointer is
not equal to max-1 then a new element can be added to a queue. If queue is full then new
element cannot be added to a queue.

Example:-

Consider max=4. First element is stored at 0th position and last element is stored at 3 rd
position in queue. In the diagram given below rear pointer is pointing to max-1 (3) position so
queue is full.
Size of queue = 4

Queue Empty: Before deleting any element from queue check whether there is an element in
the queue. If no element is present inside a queue, then front is set to -1 and queue is said to
be empty.
Size of queue = 4
0 1 2 3

Front = -1

ARROW COMPUTER ACADEMY DSU 8788335443

CIRCULAR QUEUE
Q] Draw and explain circular queue. [S 15]
(Definition-1Mark, Explanation-3Marks)
Q] Describe circular queue. Give its advantages. [W 16]
Q] Define circular queue. Explain insertion and deletion operation on circular
queue.[W 14]
(Circular queue definition – 1 Mark, Diagram - 1 Mark, Explanation of insert operation -1
Mark, delete operation – 1 Mark)

Disadvantage of linear queue:

On deletion of an element from existing queue, front pointer is shifted to next position. This
results into virtual deletion of an element. By doing so memory space which was occupied by
deleted element is wasted. When elements are deleted from the queue, new elements cannot
be added in their place in the queue, i.e. the position cannot be reused and hence inefficient
memory utilization occurs. To overcome disadvantage of linear queue, circular queue is
used.

Circular Queue:
A queue, in which the last node is connected back to the first node to form a cycle, is called as
circular queue.

The above diagram represents a circular queue using array.

It has rear pointer to insert an element and front pointer to delete an element.
It works in FIFO manner where first inserted element is deleted first.
It follows circular path while performing insertion and deletion.

Initially front and rear both are initialized to -1 to represent queue empty.
First element inserted in circular queue is stored at 0th index position pointed by rear
pointer. For the very first element, front pointer is also set to 0th position.
Whenever a new element is inserted in a queue rear pointer is incremented by one.
Before inserting an element, queue full condition is checked. If rear is set to max-1 position
and front is set to 0 then queue is full. If queue is full then new element cannot be added in a
queue.
If rear is pointing to max-1 and no element is present at 0th position then rear is set to 0th
position to continue cycle.

ARROW COMPUTER ACADEMY DSU 8788335443

For deletion, front pointer position is checked and queue empty condition is checked.
If front pointer is pointing to -1 then queue is empty and deletion operation cannot be
performed.
If queue contains any element then front pointer is incremented by one to remove an element.
If front pointer is pointing to max-1 and element is present at 0th position then front pointer
is initialize to 0th position to continue cycle.

Circular queue has advantage of utilization of space. Before inserting an element in circular
queue front and rear both the pointers are checked. So if it indicates any empty space
anywhere in a queue then insertion takes place. Circular queue is full only when there is no
empty position in a queue.

Insert operation:
Step 1: Check for queue full
if rear=max–1 and front=0 then circular queue is full and insertion operation is not possible.
otherwise go to step 2
Step 2: Check position of rear pointer
If rear=max–1 then set rear=0 otherwise
increment rear by 1 i.e.(rear = rear + 1)
Step 3: Insert element at the position pointed by rear pointer.
arr[rear]=element;
Step 4: Check the position of front pointer
If front= –1 then set front as 0.

Delete operation:-
Step 1: Check for queue empty
if (front == -1)
then circular queue is empty and deletion operation is not possible.
otherwise go to step 2
Step 2: Delete the element.
element = arr [front]
Step 3: Check for position of front and rear pointers.
if (front == rear)
then
set front=rear=-1
Step 4: Check position of front
if (front == Max-1)
then set front=0;
otherwise
front = front+1
Step 4: Stop

Advantage:-
It allows insertion of an element in a queue when queue has empty space in it.
Before insertion, it checks for circular queue full. If queue is not full then it performs insert
operation to add an element in it.

ARROW COMPUTER ACADEMY DSU 8788335443

DEQUEUE
Q] Explain the concept of the double ended queue. (Explaination-3 marks, Diagram – 1
Mark)

Deque is a more generalized version of a linear queue.

The insertion in a linear queue must happen from the rear end and deletion from the front
end.
But, in deque, you can perform both insertion and deletion operations at both of its ends.
That’s why it is called a Double-Ended Queue (Deque).
It is also often called a head-tail linked list.
It is a general representation of both stack and queue and can be used as stack and queue.

The operations that can be performed on dequeues are

initialize(): Initialize a queue by making it empty.
enqueueF(): Inserts an element at the front end of the queue.
enqueueR(): Inserts an element at the rear end of the queue.
dequeueF(): Deletes the front element and returns the same.
dequeueR(): Deletes the rare element and returns the same.
empty(): It returns true (1) if the queue is empty and returns false (0) if the queue is not
empty.
full(): It returns true(1) if the queue is full and returns false(0) if the queue is not full.
display (): Prints the queue elements.

Q] Compare circular queue and double-ended queue. [S 17]

Circular Queue Double Ended Queue
Insertion and Removal operation takes place at Insertion and removal can take place at both
only one place. i.e. rear and front. end.
It is static in nature. It can grow dynamically.
It works in traditional FIFO manner It does not require to be in LIFO & FIFO
manner; removal can take place at any end.
Insertion and removal is slow as compare to Relative fast insertion and removal operation
Double Ended Queue as compare to Circular Queue.

ARROW COMPUTER ACADEMY DSU 8788335443

PRIORITY QUEUE

Q] With a neat sketch explain working of priority queue. [S 16]

Q] What is priority queue? Describe working of priority queue with suitable example.
[W 16]
Q] Describe priority queue with its advantages. 4M [W 16][S 15]

A priority Queue is a collection of elements where each element is assigned a priority and the
order in which elements are added into the queue.
The rules for processing the elements of priority queue are:
1) An element with higher priority is processed before any element of lower priority.
2) Two elements with the same priority are processed according to the order in which they
are added to the queue (FCFS).

Array representation:

Array element of priority queue has a structure with data, priority and order. Priority queue
with 5 elements:

Linked List Representation:

Above figure shows Priority Queue with 5 elements, where B & C have same priority number.
Each node in above priority queue contains three items.

ARROW COMPUTER ACADEMY DSU 8788335443

i. Information field INFO
ii. A priority number PRNo
iii. LinkNext

An example where priority queue are used is in operating systems. The operating system has
to handle a large number of jobs. These jobs have to be properly scheduled. The operating
system assigns priorities to each type of job. The jobs are placed in a queue and the job with
the highest priority will be executed first.

Advantages:
1) Preferences to the higher priority process are added at the beginning. High priority process
executes first.
2) Keep the list sorted in increasing order.

ARROW COMPUTER ACADEMY DSU 8788335443

 Tree
In linear data structure data is organized in sequential order and in non-linear data structure data is
organized in random order. A tree is a very popular non-linear data structure used in a wide range of
applications. A tree data structure can be defined as follows.

Tree data structure is a collection of data (Node) which is organized in hierarchical structure
recursively.

Definition:
A tree is a finite set of nodes where starting node is called as Root node of the tree and the
remaining nodes are represented as two sub-trees (left sub-tree and right sub-tree) of the root node.
In tree data structure, every individual element is called as Node. Node in a tree data structure stores
the actual data of that particular element and link to next element in hierarchical structure.
In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of
links.

Example

Terminology
In a tree data structure, we use the following terminology...

1. Root
In a tree data structure, the first node is called as Root Node. Every tree must have a root node. We
can say that the root node is the origin of the tree data structure. In any tree, there must be only one
root node. We never have multiple root nodes in a tree.

ARROW COMPUTER ACADEMY DSU 8788335443

2. Edge
In a tree data structure, the connecting link between any two nodes is called as EDGE. In a tree with 'N'
number of nodes there will be a maximum of 'N-1' number of edges.

3. Parent
In a tree data structure, the node which is a predecessor of any node is called as PARENT NODE. In
simple words, the node which has a branch from it to any other node is called a parent node. Parent
node can also be defined as "The node which has child / children".

4. Child
In a tree data structure, the node which is descendant of any node is called as CHILD Node. In simple
words, the node which has a link from its parent node is called as child node. In a tree, any parent node
can have any number of child nodes. In a tree, all the nodes except root are child nodes.

ARROW COMPUTER ACADEMY DSU 8788335443

5. Siblings
In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In simple words,
the nodes with the same parent are called Sibling nodes.

6. Leaf
In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words,
a leaf is a node with no child.
In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a node
with no child. In a tree, leaf node is also called as 'Terminal' node.

7. Internal Nodes
In a tree data structure, the node which has atleast one child is called as INTERNAL Node. In simple
words, an internal node is a node with atleast one child.
In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node is
also said to be Internal Node if the tree has more than one node. Internal nodes are also called as
'Non-Terminal' nodes.

ARROW COMPUTER ACADEMY DSU 8788335443

8. Degree
In a tree data structure, the total number of children of a node is called as DEGREE of that Node. In
simple words, the Degree of a node is total number of children it has. The highest degree of a node
among all the nodes in a tree is called as 'Degree of Tree'

9. Level
In a tree data structure, the root node is said to be at Level 0 and the children of root node are at Level
1 and the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, in a
tree each step from top to bottom is called as a Level and the Level count starts with '0' and
incremented by one at each level (Step).

10. Height
In a tree data structure, the total number of edges from leaf node to a particular node in the longest
path is called as HEIGHT of that Node. In a tree, height of the root node is said to be height of the
tree. In a tree, height of all leaf nodes is '0'.

ARROW COMPUTER ACADEMY DSU 8788335443

11. Depth
In a tree data structure, the total number of egdes from root node to a particular node is called
as DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in the
longest path is said to be Depth of the tree. In simple words, the highest depth of any leaf node in a
tree is said to be depth of that tree. In a tree, depth of the root node is '0'.

12. Path
In a tree data structure, the sequence of Nodes and Edges from one node to another node is called
as PATH between that two Nodes. Length of a Path is total number of nodes in that path. In below
example the path A - B - E - J has length 4.

13. Sub Tree

In a tree data structure, each child from a node forms a subtree recursively. Every child node will form a
subtree on its parent node.

ARROW COMPUTER ACADEMY DSU 8788335443

14. Ancestors of a node: All the nodes along the path from the root to that node.

Q] Describe general tree and binary tree.

1. A general tree is a data structure in that each node can

have infinite number of children
2. In general tree, root has in-degree 0 and maximum out-
degree n.
3. In general tree, each node have in-degree one and
maximum out-degree n.
4. Height of a general tree is the length of longest path from
root to the leaf of tree. Height(T) = {max(height(child1) ,
height(child2) , … height(child-n) ) +1}
5. Subtree of general tree are not ordered.

Binary Tree
 Binary tree is a special tree data structure in which each node can have at most 2 children.
 Thus, in a binary tree,
 Each node has either 0 child or 1 child or 2 children.

Example-

ARROW COMPUTER ACADEMY DSU 8788335443

 1. Full / Strictly Binary Tree-

 A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
 Full binary tree is also called as Strictly binary tree.

Example-

Here,
 First binary tree is not a full binary tree.
 This is because node C has only 1 child.

2. Complete / Perfect Binary Tree-

A complete binary tree is a binary tree that satisfies the following 2 properties-
 Every internal node has exactly 2 children.
 All the leaf nodes are at the same level.

Complete binary tree is also called as Perfect binary tree.

Example-

ARROW COMPUTER ACADEMY DSU 8788335443

 Here,
 First binary tree is not a complete binary tree.
 This is because all the leaf nodes are not at the same level.

3. Skewed Binary Tree-

A skewed binary tree is a binary tree that satisfies the following 2 properties-
 All the nodes except one node (leaf node) has one and only one child.
 The remaining node has no child.
OR
A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).

Example-

ARROW COMPUTER ACADEMY DSU 8788335443

Binary Tree Representations
Q] Describe binary tree representation.
(Array representation - 2 marks; linked representation - 2 marks)

A binary tree data structure is represented using two methods. Those methods are as follows...

1. Array Representation

2. Linked List Representation

Consider the following binary tree...

1. Array Representation of Binary Tree

In array representation of a binary tree, we use one-dimensional array (1-D Array) to represent a binary
tree.

In array representation we can assign numbers to all the nodes. Root node is assigned a no. 0 as
array starts from 0th position. A left child of root element is placed at (2d + 1) position where’d’ is
the position of parent element. A right child of root element is placed at (2d + 2) position.

Root at 0th place.

Left child at 2d+1 position.
Right child at 2d+2 position.

d is position of parent node of child node.

Consider the above example of a binary tree and it is represented as follows...

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

A B C D F G H I J - - - K - - - - - - - - -

To represent a binary tree of depth 'n' using array representation, we need one dimensional array with

a maximum size of 2n + 1.

ARROW COMPUTER ACADEMY DSU 8788335443

2. Linked List Representation of Binary Tree
We use a double linked list to represent a binary tree. In a double linked list, every node consists of
three fields. First field for storing left child address, second for storing actual data and third for storing
right child address. In this linked list representation, a node has the following structure...

Example:

struct node
{
int info;
struct node * left;
struct node * right;
} * root;

The above example of the binary tree represented using Linked list representation is shown as

follows...

ARROW COMPUTER ACADEMY DSU 8788335443

Binary Search Tree (BST)
Q] Explain Binary Search Tree (BST) with example. 4M [S-17]

A binary tree is said to be binary search tree when all nodes less than the root node are placed at the
left of root node and all nodes greater than or equal to the root node are placed at the right of root
node. The nodes in the binary search tree are ordered. The time needed to search an element from
the tree is reduced. Binary search tree also speed up the insertion and deletion operation.

Example

Expression tree
The expression tree is a binary tree in which each internal node corresponds to
the operator and each leaf node corresponds to the operand so for example
expression tree for 3 + ((5+9)*2) would be:

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Construct Expression Tree:

a + (b * c) + d * (e + f)

TRAVERSAL OF BINARY TREE

Q] Write algorithm for morder traversal for binary tree. Demonstrate with suitable example.
(**Note: Any Binary Tree Traversal shall be considered**) [W 16]

Algorithm for Inorder Traversal:

Step 1: Visit left subtree in inorder.

Step 2: Visit root node.
Step 3: Visit right subtree in inorder
Example:

Inorder traversal is: B, A, C.

In this traversal method 1st process left subtree, then root element & then right subtree.

OR
Algorithm for Preorder Traversal:
Step 1: Visit root node.
Step 2: Visit left subtree in preorder.
Step 3: Visit right subtree in preorder.

Example:
Preorder traversal is: A, B, C.
In this traversal method 1st process root element then left subtree & then right subtree.

OR
Algorithm for Postorder Traversal:
Step 1: Visit left subtree in postorder.
Step 2: Visit right subtree in postorder.
Step 3: Visit root node
Example:

ARROW COMPUTER ACADEMY DSU 8788335443

Postorder traversal is: B, C, A.
In this traversal method 1st process left subtree then right subtree & then root element.

Q] Draw a binary search tree for given sequence and write postorder traversal of tree. [S-17]
10 5 8 9 7 6 2 15.

Q] Draw tree for given expression and find inorder, preorder and postorder traversal.
(a – 2b + 5c)2 (4d – 6e)5. 8 MARKS [S-17]

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Draw tree structure for following expression. [3A + 7B] – [(6D – 4E) ^ (6C)] [W 16]

Draw the tree structure for the following expression:

(5x+7y)/(3x+5y+3z)2

ARROW COMPUTER ACADEMY DSU 8788335443

Q] Differentiate between tree and graph (Min. 2 points).

ARROW COMPUTER ACADEMY DSU 8788335443